06计算机——数据结构期末复习试卷
历结果序列的最后一个结点。√ 42. 二叉排序树可以是一棵空树。√
43. 任何无环的有向图，其结点都可以排在一个拓扑序列里。√ 44. 平衡二叉树的左右子树深度之差的绝对值不超过1。√
45. 在散列法中采取开散列法来解决冲突时，其装载因子的取值一定在（０，１）之间。× 46. 任何一个关键活动提前完成，那么整个工程将会提前完成。× 47. 每种数据结构都应具备三种基本运算：插入、删除、搜索。×
48. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。√
49. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的× 50. 连通分量是无向图中的极小连通子图。× 四、运算题或简答题
1．已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7};
G={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20}; 按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。 ____(0,3)2____,
____(0,2)5____,
_____(0,1)8___,
____(1,5)6____,
_____(3,6)10___,
_____(4,6)4___, _____(5,7)20___。 2. 已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7};
G={(0,2),(1,3),(1,4),(2,4),(2,5),(3,6),(3,7),(4,7),(4,8),(5,7),(6,7),(7,8)};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。 拓扑序列：1,3,6,0,2,5,4,7,8
3. 设有一个10?10的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。 B[41]（或第41个位置）
4．现有稀疏矩阵A如图所示，要求画出其三元组表示法。 15 0 0 22 0 －15 0 13 3 0 0 0 0 0 0 －6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0 三元组表示法如下图：
0 1 2 3 4 5 6 7 8 i 6 0 0 0 1 1 2 4 5 j 6 0 3 5 1 2 3 0 2 value 8 15 22 -15 13 3 -6 91 28 第6页，共17页
06计算机——数据结构期末复习试卷
5. 已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下所示，
a b c d e
0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1
0 1 1 0
（1） 画出该图的图形；
（2） 根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序
列。
(1) 该图的图形为：
(2)深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 果。
先序：a,b,c,d,e,f 中序：c,b,a,e,d,f 后序：c,b,e,f,d,a 按层：a,b,d,c,e,f
a b c e d 6. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结
7. 已知一组数列为 {13, 5, 6, 17, 32, 15}，构造一棵哈夫曼树，并计算带权路径长度WPL。 解答： （1） (3) （5） 88 5 6 1715 2432 5 6 5 6 13 5 6 1732 15 24 11 13 17 32 15 (2) 1732 15 11 13 11 13 17 15 (4) 32 56 2432 第（4）步若选单个权 为32的结点就得到如 下的哈夫曼树 88 11 13 56 32 56 32 5 6 2432 1715 24第7页，共17页 32 11 13 11 13 1715 06计算机——数据结构期末复习试卷
WPL=(5+6)×4+13×3+(32+15+17) ×2=211，另外一种的WPL一样。
8. 有一哈希表HT, 表长 n=16, 哈希函数 H(key)=key mod 13，试用开地址法中的线性探测法，将一组关键字序列 {19, 14, 33, 01, 68, 20, 84, 27} 加入 HT 中。 (只需画出空间分配, 不需要写出算法) 哈希函数为：H(key)=key mod 13 H(19)=19 mod 13=6 H(14)=14 mod 13=1 H(33)=33 mod 13=7
H(01)=01 mod 13=1 冲突 (01+1) mod 13=2 H(68)=68 mod 13=3
H(20)=20 mod 13=7 冲突 (20+1) mod 13=8
H(84)=84 mod 13=6 冲突 (84+1) mod 13=7 冲突 (84+2) mod 13=8 冲突 (84+3) mod 13=9 H(27)=27 mod 13=1 冲突 (27+1) mod 13=2 冲突 (27+2) mod 13=3 冲突 (27+3) mod 13=4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
9. 对给定的有7个顶点的有向图的邻接矩阵如下： （1）画出该有向图；
（2）若将图看成AOE网，列出其关键活动及相应的有向边。 解答： （1）
dur: e l l-e
（1）用普里姆(Prim)算法，画出图的最小生成树。
（2）去掉图中的权值，画出从顶点1出发的深度优先生成树和广度优先生成树。 ① ─ 16 ─ ② ｜＼21 11／｜ ＼5 19｜ ⑥ ｜6 ③ ｜／33 14＼｜ ／6 ⑤ ─ 18 ─ ④ 解答：（1）
1 2 1 16 2 1 16 2 1 16 2 5 第8页，共17页 6 3 6 3 6 3 6 6 5 3 5 4 5 4 5 4 5 4 06计算机——数据结构期末复习试卷
（2）
5 5 4 4 1 2 1 2 5 4 5 1 16 11 6 2 1 16 11 2 1 16 11 2 6 5 3 6 5 3 或
6 5 3 6 6 18 4 5 18 4 6 3 6 3 DFS生成树 BFS生成树 31．已知一棵树的先根和后根遍历次序如下： ABEFGCDHI EFGBCHIDA 试画出此树，并画出转化后的二叉树。
答：因为树的先根和后根遍历序列对应为相应二叉树的先序和中序遍历序列，因此可以得到其转化后的二叉树为
1）画出图G；
2）写出从定点V1出发的深度优先搜索序列和广度优先搜索序列。
A
从而此树为： B E F G H I C D E F G B A C H D I 34. 已知图G的邻接表如下图所示，则：
V1 V2 V3 V4 V5 V6 V2 V3 V6 ∧ V3 V5 ∧ V4 ∧ V4 V6 1 V3 V∧ 答：1）该图的图形如右： V2 V3 第9页，共17页 V5 V6 V4 06计算机——数据结构期末复习试卷
2）深度优先搜索序列：V1,V2,V3,V6,V5,V4 广度优先搜索序列：V1,V2,V3,V4,V3,V6
34. 已知某字符串共有8种字符，下表为各字符在该串中的出现次数，对该字符串用（0,1）进行前缀编码，问字符串的编码总长至少有多少位？并列举出各字符的编码。（要求：详细写出构造的每一步） a 2 答：
注：编码不唯一
35 b 1 c 4 d 5 e 7 f 3 g 4 h 9 0 15 1 a: 111111 b: 111110 c: 010 d: 110 e: 00 f: 1110 g: 011 h: 10
0 7 1 8 20 0 1 9 e 1 h 0 4 4 11 0 3 5 1 c g d 0 f 1 6 1 3 0 b 1 2 a 字符串的编码总长：5×1＋5×2＋4×3＋3×5＋2×9＋3×4＋3×4＋2×7＝98位 35. 设二叉树bt的二叉链表静态存储结构如下： leftchild data 0 j 0 h 0 2 f 0 3 d 9 7 b 4 5 a 0 8 c 0 0 e 0 10 g 0 1 i 0 rightchild 0 要求：（1）请画出该二叉树bt的图形表示；
（2）请分别写出前序、中序、后序遍历二叉树bt的序列。 答： e
前序遍历：abcdefhgij 中序遍历：ecbhfdjiga 后序遍历：echfjigdba
b a c j i g d h f 38. 已知带权连通图 G(V, E)如下所示，请用克鲁斯卡尔（Kruskal）算法，画出该图的最小生成树。（请写出生成过程）
第10页，共17页