三、应用题（30分）

1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。

2．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。

3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。

4．设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。

5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。

四、算法设计题(20分)

1. 设计判断单链表中结点是否关于中心对称算法。 2. 设计在链式存储结构上建立一棵二叉树的算法。 3. 设计判断一棵二叉树是否是二叉排序树的算法。

数据结构试卷（一）参考答案

一、选择题 1.C

2.C

3.D 8.B

4.C 9.B

5.A 10.B

6.C 7.C

二、填空题 1. (F+1) % m 2. O(n)，O(n) 3. 2n，n+1

4. s->next=p->next; s->next=s 5. n, 2e 6. 7. 8. 9.

m=2e CBA 4，16 i-j+1，0

10. n-1

三、应用题

1. 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。 2. 哈夫曼树略，WPL=78

3. (18,5,16,19,21,23)，(5，16，21，19，18，23) 4. 线性探测： 链地址法：

5. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}

四、算法设计题

1. 设计判断单链表中结点是否关于中心对称算法。 typedef struct {int s[100]; int top;} sqstack;