2．应用题
（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
③将这棵二叉树转换成对应的树（或森林）。
A AC EM A BC BC F G DEE D
null FGH (3)
FGH (1) (2)
（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
① 试为这8个字母设计赫夫曼编码。
② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32
（100）
0 1 （40） （60） 19 21 32 （28） 0 1 0 1 （17） （11） 19 21 32 0 1 7 10 6 （5）
0 1 0 1 2 3
7 10 6 0 1
2 3
方案比较： 字母对应出现字母对应出现 编号 编码 频率 编号 编码 频率 1 1100 0.07 1 000 0.07 2 00 0.19 2 001 0.19 3 11110 0.02 3 010 0.02 4 1110 0.06 4 011 0.06 10 0.32 5 100 0.32 5 6 101 0.03 方案1的WPL＝
BM D H
2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61
方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码
3．算法设计题
以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。 int LeafNodeCount(BiTree T) {
if(T==NULL)
return 0; //如果是空树，则叶子结点个数为0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1
else
return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); }
（3）交换二叉树每个结点的左孩子和右孩子。 void ChangeLR(BiTree &T) { BiTree temp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; } ChangeLR(T->lchild); ChangeLR(T->rchild); }
第6章 图
1．选择题
CBBBCBABAADCCDDB 2．应用题
（1）已知如图6.27所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；
④ 逆邻接表。
（2）已知如图6.28所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树
??43?????? ? 4 ? 5 59??????3 5 ? ? 5 ? ? ? 5 ? ???55?7654??
??9?7?3??? ????63?2???? ????5?2?6??????54??6??? ? a b c d e f g h → b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f
2 → c 5 → d 4
5 5 7 3 2 6 6
→ d → d → e → f → g → h → g → e → h → f ^ ^ ^ ^
9 ^ 5 ^
图6.28 无
6 → g 5 → h 4^
（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
（4）有向网如图6.29所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。
图6.29 邻接矩阵
D 终点 b c d e f g S 终点集 {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} {a,c,f,e,d,g} {a,c,f,e,d,g,b} 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) 15 (a,b) 14 (a,c,f,d,g) 15 (a,b) i=1 i=2 i=3 i=4 i=5 i=6
第7章 查找
1．选择题
CDCABCCCDCBCADA 2．应用题
（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
① 画出描述折半查找过程的判定树；
② 若查找元素54，需依次与哪些元素比较？ ③ 若查找元素90，需依次与哪些元素比较？
④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
①先画出判定树如下（注：mid=?(1+12)/2?=6）：
30
5 63
3 7 42 87
4 24 54 72 95
②查找元素54，需依次与30, 63, 42, 54 元素比较； ③查找元素90，需依次与30, 63,87, 95元素比较；
④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08
（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。 12
7 17
2 11 16 21 4 9 13
验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21
（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
① 画出哈希表的示意图；
② 若查找关键字63，需要依次与哪些关键字进行比较？ ③ 若查找关键字60，需要依次与哪些关键字比较？
④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 ①画表如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 ②查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no;