数据结构(c语言版)课后习题答案完整版资料

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;

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4