二叉树数据结构复习

二叉树数据结构复习

ID:40044547

大小:200.50 KB

页数:19页

时间:2019-07-18

二叉树数据结构复习_第1页
二叉树数据结构复习_第2页
二叉树数据结构复习_第3页
二叉树数据结构复习_第4页
二叉树数据结构复习_第5页
资源描述:

《二叉树数据结构复习》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、二叉树复习题算法与数据结构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、哈夫曼编码。(2)若用这三位二进制数(0…7)对这8个字母进行等长编码,则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?答案4.对于如图所示的有向图,试写出:(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树;(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树;答案5.假设图的顶点是A,B...,请根据下述的邻接矩阵画出相应的无向图或有向图。(a)              (b)答案6.对下图所示的连通图,请分别用Prim和Kruskal算法构造其最小生成树。答案7.对下图所示的有向图,试利用Dijkstra算法求出从

3、源点1到其它各顶点的最短路径。答案8.用弗洛伊德算法求下图所示的有向图的所有顶点之间的最短路径。写出二维数组和路径在执行该算法的过程中各步的状态。答案解:(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF,则可以根据前序序列找到根结点为A,由此,通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点,又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点:/                                        /     /                           

4、      /        /(2)以同样的方法可画出该二叉树:/                                                                                          /ABCDEFGHIABFCGDHE2.解:(a)前序序列:12345中序序列:24531后序序列:54321  (b)前序序列:12345中序序列:13542后序序列:54321  (c)前序序列:12357864中序序列:17583524后序序列:78563421  (d)前序序列:1247

5、35689中序序列:742153896后序序列:7425896313.解:(1)哈夫曼编码接下页根据上图可得编码表:a:1001b:01c:10111d:1010e:11f:10110g:00h: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)以顶点①为根的深度优先生成树(不唯

6、一):①②③④⑤5.答:6.7.解:循环状态表如下: 循环     集合KD[1]D[2]D[3]D[4]D[5]D[6]初始化{1} -  0  20  15  ∞  ∞  ∞     1        {1,3} 3  0  19  15  ∞  ∞  25      2      {1,3,2} 2  0  19  15  ∞  29  25     3    {1,3,2,6} 6  0  19  15  292925       4  {1,3,2,6,4} 4  0  19  15  292925      51,3,2,6,4,5} 5  

7、0  19  15  292925      6同上-同上                     从源点1到各点的路径如下所示:1到2:1321到3:131到4:13641到5:13251到6:1368.解:例ACB264311041160230初始:路径:ABACBABCCA046602370加入V2:路径:ABABCBABCCACAB0411602370加入V1:路径:ABACBABCCACAB046502370加入V3:路径:ABABCBCABCCACAB

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。