数据结构与算法题库五、综合题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图-28.画出下列二叉树相应的森林，并写出中序遍历森林的序列。9.已知一个无向网如下图所示，试用普里姆算法计算出该图的最小生成树，最小生成树为权值之和最小的生成树。10.已知一个无向图G=(V,E),V={A,B,C,D,E,F,G,H},E={(A,B),(A,C),(B,D),(B,E),(C,F),(C,G),(D,H),(E,H),(F,G)};(1)画出该无向图；(2)画出该图的邻接表存储结构；(3)根据存储结构，写出深度优先搜索遍历序列和广度优先搜索遍历序列。11.已知一个无向图G=(V,E),V={v1,v2,v3,v4,v5,v6,v7,v8},E={(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7),(v4,v8),(v5,v8),(v6,v7)};(1)画出该无向图；(2)画出该图的邻接表存储结构；(3)根据存储结构，写出深度优先搜索遍历序列和广度优先搜索遍历序列。12.已知一个有向图如下图所示：(1)画出该图的邻接表存储结构。(2)画出该图的逆邻接表存储结构。(3)写出拓扑排序序列。(4)写出深度优先搜索遍历序列和广度优先搜索遍历序列。13.画出如下图所示的邻接表的表示，并以顶点V1为初始源点遍历所示的有向图所得到的深度优先遍历和广度优先遍历生成森林。14.已知一个连通网如下图所示，试用Prime（普里姆）算法计算下图的最小生成树，起始点为A。15一个无向网如下图所示，试用普里姆算法计算出该图的最小生成树，起始点为A。16.请利用Prime（普里姆）算法计算下图的最小生成树。17.已知一个AOE网如下图所示：(1)写出下图的拓扑排序顺序序列；(2)试计算出该图从源点A出发到达汇点F的关键路径。18.已知一个AOE网如下图所示：(1)找出AOE网源点和汇点；(2)试计算出该图的关键路径。19.已知一个AOE网如下图所示，其中V1为源点，V6为汇点。(1)写出拓扑排序序列；(2)计算出从源点到汇点的关键路径。20.利用Dijkstra算法计算下图中从顶点A到其余各顶点的最短路径。已知一个AOE网如下图所示，试计算出该图的关键路径。21.用迪杰斯特拉算法求下图中从a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。22.用迪杰斯特拉算法求下图中从A到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。23.已知一组关键字序列12,23,45,57,20,3,78,31,15,36，哈希函数为H(Key)=Key%13(1)利用开放定址法的线性探测再散列解决冲突，构造长度为15的哈希表，计算平均查找长度ASL；(2)利用链地址法解决冲突，构造长度为10的哈希表，计算平均查找长度ASL；24．设哈希表长度为10，哈希函数为H(Key)=KeyMod7，关键字集合为{15，10，12，20，25，35，31，18}。（1）利用开放定址法的线性探测再散列解决冲突，构造哈希表，计算平均查找长度ASL。（2）利用链地址法解决冲突构造哈希表，计算平均查找长度ASL。25.已知一组数据的关键字为（22，41，53，46，30，13，1，67），哈希函数...
VIP
