数据结构与算法题库
五、综合题
1．已知一棵二叉树的先序遍历序列为ABECDFGHIJ，中序遍历序列为EBCDAFHIGJ。
(1) 画出这棵二叉树;
(2) 写出该二叉树的后序遍历序列;
(3) 画出这棵二叉树的中序线索二叉树的存储结构图。
2. 已知一棵二叉树的中根遍历序列为：2，4，1，5，3，7，6，8，后根遍历序列为：4，2，5，7，8，6，3，1。
(1)画出二叉树。
(2) 写出二叉树先根遍历序列。
(3) 画出该二叉树的先序线索二叉树。   
3. 假设一颗二叉树的中序遍历序列为DCBGEAHFIJK和后序遍历序列为DCEGBFHKJIA.。
1）请画出该二叉树。
先序中序后序遍历二叉树2）请画出该二叉树的后序序线索二叉树。
3）写出该二叉树的先序遍历序列。
4. 已知一棵二叉树的先序遍历序列为ABCDEFGHIJK，中序遍历序列为CDBGFEAHJIK。
（1）请构造二叉树；
（2）画出先序线索二叉树。
（3）分别列出度为0、1和2的结点。
5.已知某通讯电文仅由a，b，c，d，e，f，g，h八个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。为这8中字母设计哈夫曼编码。
6. 假设用于通信的电文仅由5种字母ABCDE组成，每个字母出现的概率分别为0.12, 0.40, 0.
15, 0.08, 0.25。
(1) 用5个概率值为权值设计Huffman(哈夫曼)树。
(2) 计算它的带权路径长度WPL。
(3) 设计这5种字符的Huffman编码
7.按下面要求转换森林和二叉树。
（1）将图-1的二叉树转换成森林。
（2）将图-2的树转换成二叉树。
                图-1
                图-2
8. 画出下列二叉树相应的森林，并写出中序遍历森林的序列。
9. 已知一个无向网如下图所示，试用普里姆算法计算出该图的最小生成树，最小生成树为权值之和最小的生成树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。