数据结构复习题及参考答案
（抽考其中50%）
哈夫曼编码树的带权路径长度一、单选题(每小题1分)
1．下列程序段的时间复杂度为（A）。
for(i=0； i<m； i++)
for(j=0； j<t； j++) c[i][j]=0；
for(i=0； i<m； i++)
for(j=0； j<t； j++)
for(k=0； k<n； k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j]；
(A) O(m*n*t)   (B) O(m+n+t)   (C) O(m+n*t)   (D) O(m*t+n)
2．下列程序段的时间复杂度为（A）。
i=0，s=0；
while (s<n) {s=s+i；i++；}
(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)
3．设顺序表中有n个数据元素，则删除表中第i个元素需要移动（A）个元素。
(A) n-i    (B) n+l-i    (C) n-1-i    (D) i
4．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（D）存储方式最节省运算时间。
(A) 单向链表     (B) 单向循环链表
(C) 双向链表     (D) 双向循环链表
5．设是由、和三棵树组成的森林，与对应的二叉树为，、和的结点数分别为、和，则二叉树B的根结点的左子树的结点数为（A）。
(A) (B)   (C) (D)
6．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（B）。
(A) s->next=p->next；p->next=-s；  (B) q->next=s； s->next=p；
(C) p->next=s->next；s->next=p；   (D) p->next=s；s->next=q；
7．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（C）。
(A)   (B) (C)   (D)
8．设输入序列为1,2,3,4,5,6，则通过栈的作用后可以得到的输出序列为（B）。
(A) 5，3，4，6，1，2     (B) 3，2，5，6，4，1
(C) 3，1，2，5，4，6     (D) 1，5，4，6，2，3
9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D）。
(A) p->right=s； s->left=p； p->right->left=s； s->right=p->right；
(B) s->left=p；s->right=p->right；p->right=s； p->right->left=s；
(C) p->right=s； p->right->left=s； s->left=p； s->right=p->right；
(D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；
10．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（B）。
(A) 10   (B) 19   (C) 28   (D) 55
11．下列各种排序算法中平均时间复杂度为是（D）。
(A) 快速排序  (B) 堆排序   (C) 归并排序   (D) 冒泡排序
12．设一棵m叉树中有个度数为1的结点，个度数为2的结点，…，个度数为m的结点，则该树中共有（D）个叶子结点。
(A)    (B) (C)   (D)
13．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（C）。
(A) n-i   (B) n-1-i   (C) n+l-i   (D) 不能确定
14. 二叉排序树中左子树上所有结点的值均（A）根结点的值。
(A) <  (B) >   (C) =   (D) >=
15．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（B）。
(A) 小于等于m的最大奇数     (B) 小于等于m的最大素数
(C) 小于等于m的最大偶数     (D) 小于等于m的最大合数
16. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（D）。
(A) 129  (B) 219   (C) 189   (D) 229
17．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（C）个。
(A) 4   (B) 5   (C) 6     (D) 7
18. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（D）次线性探测。
(A) n   (B) n(n+1)   (C) n(n+1)/2   (D) n(n-1)/2
19.设完全无向图中有n个顶点，则该完全无向图中有（A）条边。
(A) n(n-1)/2   (B) n(n-1)   (C) n(n+1)/2    (D) (n-1)/2
20.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（C）个结点。
(A) 2n   (B) n+l     (C) 2n-1    (D) 2n+l
21.设顺序表的长度为n，则顺序查的平均比较次数为（C）。
(A) n   (B) n/2   (C) (n+1)/2   (D) (n-1)/2
22.设一组初始记录关键字的长度为8，则最多经过（B）趟插入排序可以得到有序序列。
(A) 6   (B) 7   (C) 8   (D) 9
23.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查值为24的元素需要经过（C）次比较。
(A) 1   (B) 2  (C) 3     (D) 4
24.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（A）。
(A) F，H，C，D，P，A，M，Q，R，S，Y，X
(B) P，A，C，S，Q，D，F，X，R，H，M，Y
(C) A，D，C，R，F，Q，M，S，Y，P，H，X
(D) H，C，Q，P，A，M，S，R，D，F，X，Y
25.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查(二分法定块，块内顺序查)，则其平均查长度为（D）。
(A) 6   (B) 11     (C) 5   (D) 6.5
26.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（A）。
(A) 1，2，3，4   (B) 2，3，4，1   (C) 1，4，2，3   (D) 1，2，4，3
27.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（A）。
(A) 4  (B) 5   (C) 6   (D) 7
二、填空题(每小题2分)
1． 设指针p指向单链表中结点，指针s指向待插入的结点。若在p所指向的结点之前插入s所指结点，则操作序列为：
1) s->next=______；2) p->next=s；3) t=p->data；
4) p->data=_______；5) s->data=t；
2. 设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。
3． 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。
4. 快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度为___________。
5． 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。
6. 设二叉排序树的高度为h，则在该树中查关键字key最多需要比较_____次。
7． 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。
8. 设在长度为20的有序表中进行二分查，则比较一次查成功的结点数有_________个，比较两次查成功有结点数有_________个。
9． 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_____排序，如果从节省存储空间的角度来考虑则最好选择_____排序。
10. 设一棵m叉树的结点数为n，用多重链表表示其存储结构，则该树中有_________个空指针域。
11． 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查长度是___________________。
12. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为：
q=p->next；p->data=q->data；p->next=___________；delete q；
13． 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。
14. 数据结构从逻辑上划分四种基本类型：集合、线性表、_______和________。
15．设通信用电文仅有8个字母，频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为__________。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。