2022年8月东北大学 《数据结构IIX》在线平时作业3

《数据结构Ⅱ》在线平时作业3  
一、单选题(共20道试题共100分)  
1.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为  
A.7  
B.8  
C.9  
D.10  
2.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是  
A.T[2]  
B.T[4]  
C.T[8]  
D.T[10]  
3.已知广义表的表头为a，表尾为(bc)，则此广义表为  
A..(a(bc))  
B..(abc)  
C..((a)bc)  
D..((abc))  
4.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为  
A.O(n)O(n)  
B.O(n)O(1)  
C.O(1)O(n)  
D.O(1)O(1)  
5.倒排文件的主要优点是  
A.便于进行插入和删除运算  
B.便于进行文件的恢复  
C.便于进行多关键字查询  
D.节省存储空间  
6.ISAM文件的周期性整理是为了空出  
A.磁道索引  
B.柱面索引  
C.柱面基本区  
D.柱面溢出区  
7.下列关键字序列中，构成小根堆的是  
A.{84，46，62，41，28，58，15，37}  
B.{84，62，58，46，41，37，28，15}  
C.{15，28，46，37，84，41，58，62}  
D.{15，28，46，37，84，58，62，41}  
8.若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为  
A.1和n+1  
B.1和n/2  
C.－1和n  
D.－1和n+1  
9.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为  
A.1和5  
B.2和4  
C.4和2  
D.5和1  
10.以下属于逻辑结构的是  
A.顺序表  
B.哈希表  
C.有序表  
D.单链表  
11.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是  
A.10  
B.11  
C.12  
D.15  
12.以下数据结构中，属于线性结构的是  
A.广义表  
B.二叉树  
C.稀疏矩阵  
D.串  
13.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11a21…an1)  
(a12a22…an2)…，（a1na2n…ann）)并且可以通过求表头head和求表尾tail的运算求  
取矩阵中的每一个元素，则求得a21的运算是  
A.head(tail(head(L)))  
B.head(head(head(L)))  
C.tail(head(tail(L)))  
D.head(head(tail(L)))  
14.对长度为n的关键字序列进行堆排序的空间复杂度为  
A.O（log2n）  
B.O（1）  
C.O（n）  
D.O（n*log2n）  
15.已知有向图G=(VE)，其中V={V1V2V3V4V5V6V7}，E={<V1V2><V1V3><V1V4><V2V5><V3V5><V3V6><V4V6><V5V7><V6V7>}G的拓扑序列是  
A.V1V3V4V6V2V5V7  
B.V1V3V2V6V4V5V7  
C.V1V3V4V5V2V6V7  
D.V1V2V5V3V4V6V7  
16.在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是  
A.LL型  
B.LR型  
C.RL型  
D.RR型  
17.算法分析的目的是  
A.辨别数据结构的合理性  
B.评价算法的效率  
C.研究算法中输入与输出的关系  
D.鉴别算法的可读性  
18.下面关于数据结构正确的说法是  
A.一种数据类型  
B.数据的存储结构  
C.一组性质相同的数据元素的集合  
D.相互之间存在一种或多种特定关系的数据元素的集合  
19.有关二叉树下列说法正确的是  
A.二叉树的度为2  
B.一棵二叉树的度可以小于2  
C.二叉树中至少有一个结点的度为2  
D.二叉树中任何一个结点的度都为2  
20.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上  
A.操作的有限集合  
B.映象的有限集合  
C.类型的有限集合  
D.关系的有限集合