发布时间 : 星期四 文章数据结构试题B及参考答案（计算机专业）更新完毕开始阅读01c91d4af7ec4afe04a1df11
四、算法填空题（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