(A) 129 (B) 219 (C) 189 (D) 229
9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（ ）次线性探测。 (A) n
2
(B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2
10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。 (A) 2n
(B) n+l
(C) 2n-1
(D) 2n+l
11.设一组初始记录关键字的长度为8，则最多经过（ ）趟插入排序可以得到有序序列。 (A) 6
(B) 7
(C) 8
(D) 9
12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。 (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
二、填空题(48分，其中最后两小题各6分)
1. 设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需
要比较_____________次。
2. 快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度
为___________。
3. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。 4. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________
个，比较两次查找成功有结点数有_________个。
5. 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_________个
空指针域。
6. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为：
q=p->next；p->data=q->data；p->next=___________；feee(q)；
7. 数据结构从逻辑上划分为三种基本类型：___________、__________和___________。
33
8. 设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度
优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。
9. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，则根据一组初始
关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。 10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的
结果为_____________________。
11. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的
结果为______________________。
12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，
<6，5>}，则该图的一个拓扑序列为_________________________。 13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。
typedef struct node{int data;struct node *lchild;________________;}bitree; void createbitree(bitree *&bt) {
scanf(“%c”,&ch);
if(ch=='#') ___________;else
{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);} }
14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确
的内容。
typedef struct node {int data; struct node *next;} lklist; void lklistcreate(_____________ *&head ) {
for (i=1;i<=n;i++) {
p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;____________;} } }
34
三、算法设计题(22分)
1． 设计在链式存储结构上合并排序的算法。 2． 设计在二叉排序树上查找结点X的算法。
3． 设关键字序列(k1，k2，?，kn-1)是堆，设计算法将关键字序列(k1，k2，?，kn-1，x)调
整为堆。
35
数据结构试卷（一）参考答案
一、选择题（每题2分，共20分）
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、填空题（每空1分，共26分）
1. 正确性 易读性 强壮性 高效率 2. O(n) 3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路
8. n(n-1)/2 n(n-1)
9. （12，40） （ ） （74） （23,55，63） 10.增加1
11.O(log2n) O(nlog2n) 12.归并
三、计算题（每题6分，共24分）
36