资源描述：
《数据结构应用题练习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。21、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请指出结点P的父结点，左子女，右子女。3、给出下列二叉树的先序序列。4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。答案：二叉树形态（2）设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC①画出这棵二叉树。②画出这棵二叉树的后序线索树。③将这棵二叉树转换成对应的树（或森林）。 ABMFD(3)CEMHG (1)(2)1
2、、已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H,A,C,K,I,L,F。i.写出该二叉树的后序序列；ii.画出该二叉树；iii.求该二叉树的高度(假定空树的高度为－1)和度为2、度为1、及度为0的结点个数。该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。该二叉树的形式如图所示：ABJKIFCGEDLH该二叉树高度为：5。度为2的结点的个数为：3。度为1的结点的个数为：5。度为0的结点个数为：4。5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼
3、树的带权路径长度。答案：WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=696、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。答案：(1)树形态：(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79（3）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。①试为这8个字母设计赫夫曼编码。②试设计另一种由二进制表示的等长编码方案。③对于上述实例，比较两
4、种方案的优缺点。解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6],(7,10)】, ……19,21,3201010119213201010171060123（100）（40）（60）192132（28）（17）（11）7106（5）23方案比较：字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率10000.07200
5、10.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL＝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结论：哈夫曼编码优于等长二进制编码2．应用题（1）已知如图6.27所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。图6.27有向图2AOE网G如下所示，求关
6、键路径。（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）答案：(1)最早发生时间和最迟发生时间：(2)关键路径：（2）已知如图6.28所示的无向网，请给出：①邻接矩阵；②邻接表；③最小生成树图6.28无向网a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。图6.29邻接矩阵（2）
7、根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程。（用图或者表的方式均可）。答案：(1)广度优先遍历序列：1;2,3,4;5;6(2)最小生成树（prim算法）V1V5V4V6V761V2V8V561.对下面的有向图，从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。遍历得到的DFS生成森林和BFS生成森林如下图：V1V5V4V6V761V2V8V56DFS生成森林V1V5V4V6V761V2V8V56BFS生成森林（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线
8、性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：①画出哈希表的示意
