发布时间 : 星期日 文章数据结构与算法分析—期末复习题及答案更新完毕开始阅读
lklist *s=hc=0;
while(ha!=0 && hb!=0)
if(ha->data
else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha;
}
数据结构试卷（六）
一、选择题(30分)
1． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权
路径长度之和为（ ）。
(A) 20 (B) 30 (C) 40 (D) 45
2．执行一趟快速排序能够得到的序列是（ ）。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
(C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。
(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序
。 ）
5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是
（ ）。
(A) 空或只有一个结点 (B) 高度等于其结点数
(C) 任一结点无左孩子 (D) 任一结点无右孩子
6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序
7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。
(A) 3 (B) 4 (C) 5 (D) 6
8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
9．二路归并排序的时间复杂度为（ ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10. 深度为k的完全二叉树中最少有（ ）个结点。
(A) 2-1
k-1
(B) 2
k-1
(C) 2+1
k-1
(D) 2-1
k
11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队
尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。
(A) front->next=s；front=s； (B) s->next=rear；rear=s；
(C) rear->next=s；rear=s； (D) s->next=front；front=s；
12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。
(A) 99 (B) 100 (C) 101 (D) 102
14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为
（ ）。
(A) O(n) (B) O(n)
2
(C) O(nlog2n) (D) O(1og2n)
15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）。
(A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和
(C) 第i行0元素的个数之和 (D) 第i列0元素的个数之和
二、判断题(20分)
1．调用一次深度优先遍历可以访问到图中的所有顶点。（ ）
2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ）