数据结构复习题.ppt

复习题算法与数据结构

1.给定二叉树的两种遍历序列，分别是：(1)已知一棵二叉树的先序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。(2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。答案

2.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。?答案

3.假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.

(1)为这8个字母设计哈夫曼编码。

(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?答案

4.对于如图所示的有向图，试写出：

???(1)从顶点①出发进行深度优先有哪些信誉好的足球投注网站所得到的深度优先生成树和序列；

???(2)从顶点②出发进行广度优先有哪些信誉好的足球投注网站所得到的广度优先生成树和序列；

答案

5.假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。(a)??????????????(b)?答案

6.对下图所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。答案

7.对下图所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径。答案

8.用弗洛伊德算法求下图所示的有向图的所有顶点之间的最短路径。写出二维数组和路径在执行该算法的过程中各步的状态。答案

解：?(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点：

??????????????????????

?????????????????????/?\

???????????????????

??????????????????/?????/\

????????????????

???????????????/\????????/

????????????

?(2)以同样的方法可画出该二叉树：

????????????????????

????????????????????/\

???????????????????

????????????????????\??????\

??????????????????????

???????????????????/\??????

???????????????ABCDEFGHIABFCGDHE

2.解：

?(a)前序序列：12345?

????中序序列：24531?

????后序序列：54321

?(b)前序序列：12345?

????中序序列：13542?

????后序序列：54321

?(c)前序序列

????中序序列

????后序序列

?(d)前序序列：124735689?

????中序序列：742153896?

????后序序列：742589631

3.解：

?(1)哈夫曼编码

接下页

根据上图可得编码表：

a:1001

b:01

c:10111

d:1010

e:11

f:10110

g:00

h:1000

(2)用三位二进制数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：

??????4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

??????2.61/3=0.87=87%

?????其平均码长是等长码的87%。

???所以平均压缩率为13%。

4.【解答】

?(1)以顶点①为根的深度优先生成树（不唯一）：①②③④⑤

???

5.答:

???

6.

7.解：循环状态表如下：

循环?????集合?KD[1]D[2]D[3]D[4]D[5]D[6]

初始化?{1}?-??0??20??15??∞??∞??∞

????1??????