《科大18春《数据结构》在线作业2》由会员分享，可在线阅读，更多相关《科大18春《数据结构》在线作业2（7页珍藏版）》请在金锄头文库上搜索。
1、 - (单选题) 1: 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）。 A: 无头结点的双向链表 B: 带尾指针的循环链表 C: 无头结点的单链表 D: 带头指针的循环链表 正确答案: B (单选题) 2: 队和栈的主要区别是（ ）。 A: 逻辑结构不同 B: 存储结构不同 C: 所包含的运算个数不同 D: 限定插入和删除的位置不同 正确答案: D (单选题) 3: 通常将链串的结点大小设置为大于1是为了（ ）。 A: 提高串匹配效率 B: 提高存储密度 C: 便于插入操作 D: 便于删除操作 正确答案: (单选题) 4: 在具有n个结点的有序单链表中插入
2、一个新结点并使链表仍然有序的时间复杂度是（ ）。 A: O(1) B: O(n) C: O(nn) D: O(n2) 正确答案: B (单选题) 5: 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（ ）。 A: 5 B: 8 C: 11 D: 18 正确答案: C (单选题) 6: 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）。 A: 0 B: 1 C: 48 D: 49 正确答案: D (单选题) 7: 一棵含18个结点的二叉树的高度至少为（ ）。 A: 3 B: 4 C: 5 D: 6 正确答案: C (单选题)
3、 8: 与线性表相比，串的插入和删除操作的特点是（ ）。 A: 通常以串整体作为操作对象 B: 需要更多的辅助空间 C: 算法的时间复杂度较高 D: 涉及移动的元素更多 正确答案: (单选题) 9: 已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（ ）。 A: 7 B: - C: 9 D: 10 正确答案: (单选题) 10: 下面程序段的时间复杂度是（ ）。 for(i=0;in;i+) for(j=1;jm;j+) Aij=0； A: O(n) B: O(m+n+1) C: O(m+n) D: O(m*n) 正确答案: D (单选题) 11: 在线性表的下列运算中，不改变数
4、据元素之间结构关系的运算是（ ）。 A: 插入 B: 删除 C: 排序 D: 定位 正确答案: D (单选题) 12: 执行下列程序段后，串X的值为（ ）。 S=abcdefgh; T=xyzw; substr (X,S,2,strlen(T); substr (Y,S, stelen(T),2); strcat (X,Y); A: cdefgh B: cdxyzw C: cdefxy D: cdefef 正确答案: D (单选题) 13: 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）。 A: 栈 B: 队列 C: 树 D: 图 正确答案: C (单
5、选题) 14: 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需（ ）。 A: 前移一个位置 B: 后移一个位置 C: 不动 D: 视情况而定 正确答案: (单选题) 15: 设串sl=Data Structures with Java,s2=it，则子串定位函数index(s1,s2)的值为（ ）。 A: 15 B: 16 C: 17 D: 18 正确答案: D (单选题) 16: 已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序 列为（ ）。 A: 5，4，3，2，1，6 B: 2，3，5，6，1，4 C: 3，2，5，4，1
6、，6 D: 1，4，6，5，2，3 正确答案: C (多选题) 1: 算法以下几种特性（ ）。 A: 有穷性 B: 确定性- C: 可行性 D: 输入和输出 正确答案: ,B,C,D (多选题) 2: 通用的处理哈希冲突的方法有（ ）。 A: 开放定址法 B: 再哈希法 C: 链地址法 D: 建立公共溢出区 正确答案: ,B,C,D (判断题) 1: 两个空串联接得到的串的长度为0。 A: 错误 B: 正确 正确答案: B (判断题) 2: 设S1=“good“,S2=“ “,S3=“book“，则S1，S2和S3依次联接后的结果是”good book” 。 A: 错误 B: 正确 正确答案:
7、 B (判断题) 3: 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为 O(n)。 A: 错误 B: 正确 正确答案: B (判断题) 4: 在对链队列作出队操作时，不会改变front指针的值。 A: 错误 B: 正确 正确答案: (判断题) 5: 假设以行优先顺序存储三维数组A567，其中元素A000的地址为1100，并且每个元素占2个存储 单元，则A432的地址是1264。 A: 错误 B: 正确 正确答案: (判断题) 6: 假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A98 7的存储地址是501。 A: 错误 B: 正确
8、 正确答案: (判断题) 7: 在二叉树的第i层上至多可以有2i个结点。 A: 错误 B: 正确 正确答案: (判断题) 8: 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。 A: 错误 B: 正确 正确答案: B (判断题) 9: 结点数为20的二叉树可能的最大高度为4。 A: 错误 B: 正确 正确答案: (判断题) 10: 如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。 A: 错误 B: 正确- 正确答案: B (判断题) 11: 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2
9、+1。 A: 错误 B: 正确 正确答案: B (判断题) 12: 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。 A: 错误 B: 正确 正确答案: B (判断题) 13: 二叉树是度为2的有序树。 A: 错误 B: 正确 正确答案: (判断题) 14: 字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串. A: 错误 B: 正确 正确答案: (判断题) 15: 产生冲突现象的两个关键字称为该散列函数的同义字。 A: 错误 B: 正确 正确答案: B (判断题) 16: 二叉树中的叶子结点就是二叉树中没有左右子树的结点。 A: 错
10、误 B: 正确 正确答案: B (判断题) 17: 两个串相等的充分必要条件是两个串的长度相等且字母相同。 A: 错误 B: 正确 正确答案: B (判断题) 18: 一棵树可以只有1个结点。 A: 错误 B: 正确 正确答案: B (判断题) 19: 队列的队尾位置通常是随着入队操作而变化的。 A: 错误 B: 正确 正确答案: B (判断题) 20: 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。 A: 错误 B: 正确 正确答案: (判断题) 21: 在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的定位操作。 A: 错误 B: 正确 正确答案
11、: B (判断题) 22: 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。 A: 错误 B: 正确 正确答案: (单选题) 1: 若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（ ）。 A: 无头结点的双向链表 B: 带尾指针的循环链表- C: 无头结点的单链表 D: 带头指针的循环链表 正确答案: B (单选题) 2: 队和栈的主要区别是（ ）。 A: 逻辑结构不同 B: 存储结构不同 C: 所包含的运算个数不同 D: 限定插入和删除的位置不同 正确答案: D (单选题) 3: 通常将链串的结点大小设置为大于1是为了（ ）。 A: 提高串匹配效
12、率 B: 提高存储密度 C: 便于插入操作 D: 便于删除操作 正确答案: (单选题) 4: 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（ ）。 A: O(1) B: O(n) C: O(nn) D: O(n2) 正确答案: B (单选题) 5: 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（ ）。 A: 5 B: 8 C: 11 D: 18 正确答案: C (单选题) 6: 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）。 A: 0 B: 1 C: 48 D: 49 正确答案: D (单
13、选题) 7: 一棵含18个结点的二叉树的高度至少为（ ）。 A: 3 B: 4 C: 5 D: 6 正确答案: C (单选题) 8: 与线性表相比，串的插入和删除操作的特点是（ ）。 A: 通常以串整体作为操作对象 B: 需要更多的辅助空间 C: 算法的时间复杂度较高 D: 涉及移动的元素更多 正确答案: (单选题) 9: 已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（ ）。 A: 7 B: 8 C: 9 D: 10 正确答案: (单选题) 10: 下面程序段的时间复杂度是（ ）。 for(i=0;in;i+) for(j=1;jm;j+) Aij=0；- A: O(n) B: O(m+n+1) C: O(m+n) D: O(m*n) 正确答案: D (单选题) 11: 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。 A: 插入 B: 删除 C: 排序 D: 定位 正确答案: D (单选题) 12: 执行下列程序段后，串X的值为（ ）。 S
