数据结构试题B及参考答案（计算机专业）

四、算法填空题（10分）

void selectsort (int R[ ] ){

// 按递增序对R[ 0 ]～R[n-1] 进行直接选择排序 int i, j, k, temp ;

for (i=0; i<= ⑴ ; i++) { k=i ;

for (j= ⑵ ; j<=n-1; j++) if (R[ j ] ⑶ R[ k ] ) k=j; if （ ⑷ temp=R[ i ];

R[ i ] = ⑸ ; R[ k ]=temp; } }

}//selectsort

{ 5

）答案

一、填空题（每小题题号 答案 1 2 3 4 5 关系 n-i+1 bceda 物理结构（存储结构） n-1 2分，共20分）

题号 6 7 8 9 10 答案 5 2i n+1 2k-1，2i-1 n(n-1)/2 二、选择题（每小题1 D 2 B 3 A 2分，共20分）

4 A 5 A 6 D 7 B 8 B 9 A 10 D 三、简答题：（每小题1．（5分）

5分，共50）

（1）树的根结点是：A――――（1分） （2）结点E的父结点是：B―――（1分） （3）E的兄弟结点是有：D―――（1分） （4）树的深度是：4――――――（1分） （5）树的度是：3―――――――（1分）

2. （8分） 先根遍历序列：ABCDEFGHI (1.5分) 中根遍历序列：BCDAFEHIG (1.5分) 后根遍历序列：DCBFIHGEA (1.5分)

图2二叉树转换为森林： (3.5分) A E B C D F 3．（共9分） （1）（5分）

（2）（2分） a: 0110 b: 0111 c: 100 d: 11 e: 101 f: 010 g: 00

G H I 6

0 1

0 1

0

1

0 1 0

1

（3）（2分）

(4+5)*4+(10+6+8)*3+(12+18)*2=168

0 1

注：哈夫曼树不唯一。各字符的编码也不唯一。但所有字符的编码应该是一组前缀码。

4．图3的深度优先搜索序列：0 1 3 7 8 4 9 5 2 6 （2.5分） 广度优先搜索序列：0 1 2 3 4 5 6 7 8 9 （2.5分） 注：答案不唯一。

5. 用普里姆算法生成最小生成树的过程：（5分）

7

6. 得到的二叉排序树：（5分）

7.（8分）

(1) (5分)

散列函数H(k)=k mod 6；采用线性探测方法解决冲突：Hi=(H(k)+di) mod m，其中i=1,2,…,m-1，m为表长。因此本题得到的散列表为：

0 1 2 3 4 5 6 30

36 40 52 47 34

（2）等概率情况下查找成功的平均查找长度：（3分）

ASL=（=14/6=7/3 1?3?2?1?3?1?6?1）8. 所有可能的拓扑序列：(5分) V1,V5,V6,V2,V3,V4

16四、 算法填空题（10分，每空2分）

(1) n-1 (2) k+1 (3) < (4) k≠i (5) R[k ]

8