电大数据结构综合体

1、三、综合题1. (1)对给定权值3, 1 , 4, 4, 5, 6,构造深度为5的哈夫曼树。(设根为第 (3)链接存储上述哈夫曼树，结点中共有多少个个指针域为空答：(2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58(3)共11个结点,22个指针域，除根结点外， 每个结点对应一个指针域.，共10个指针域非空，故有 22-10=12个空指针域,(1)以2, 3, 4, 7, 8, 9作为叶结点的权，构造一棵哈夫曼树 的权)，给出相应权重值叶结点的哈夫曼编码。(2) 棵哈夫曼树：求树的带权路径长度。答:(1)2：11103: 11114：1107：008:019：101 层)。(2

2、)，说明理由23971489子树根结点(124543小于等43个叶结点，它一共有多少个结点？简述理由?3. (1)(2)2n-1个，因为非叶结点数比 叶结点数少一个。如下的一棵树，给出先序遍历序列|把1,2,3,4,5,6,7,8,9填人，使它成为一棵二叉排序树 提示：设图中的树是二叉排序树，找出中序遍历序列与|请在该树中再插入一个结点 ：1 A1 A2 A4 A7 A8 A5 A9 A3 A6(2)如图19的对应关系3.5作为叶结点，并使它仍然是一棵二叉排序树1,A4A69A5A7A8A9图A17图1/6, 79,38,40, 84)(1)利用快速排序的方法，给出以第一个记录为基准得到的一次

3、划分结果(给出逐次交换 方法建立大根堆，4.一组记录的关键字序列为579,79,38,38,56,56,848484843.5,12,13,14)9356,56,(2)对上述序列用堆排(1)初始序列46, 79,4040, 38,40, 38,38,40,79,238,0，84树逐次描述建堆过程。465.设查找表为(5,6,7,8,9,10,(1)画出对上述有序表进行折半查找所对应的判定树(2)给出二叉排序树的定义，针对上述折半查找所对应的判定树的构造过程，说明判定树是否是二叉排序树(设树中没有相同结点)?(3)为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？ 答：如图(2) 二叉

4、排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树 非空，则左子树的所有结点的值都小于它的根结点的值； 若它的右子树非空，则右子树的所有结点的值都大于( 若允许结点有相同的值，则大于等于)它的根结点的值；左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。(3) . 3 次6.设查找表为(50,60,75,85,96,98,105,110,120,130)(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？(要求以数据元素作为树结点!11(2)为了折半查找元素95,经过多少次元素间的比较才能确定不能查到?I点表示活动,网)。都排在该活动的刖面，此(要求以数

5、据元素作为树结点130通常对n个元素进行冒泡排序要进行多少趟冒图叫做顶点1不存在回路75贝V所有活动可排列成叫做拓扑序列。96(要求以数据元素作为树结点)(2)1653152064A1A2A3A4A6A5A7A8A9叉排序树。1615205364715162053764n-1-j次151672053641571620536471516205364(3)平均查找长度=(1*1+2*2+3*3)/6=14/6设有查找表17，26，14，16，15，30，18，19，28，依次取表中数据构造一棵二叉 排序树对上述二叉树给出后序遍历的结果(3) .对上述二叉树给出中后序遍历的

6、结果(4) )在上述二叉树中查找元素15共要进行多少次元素的比较答(2)后序15, 16, 14, 19, 18, 28, 30, 26, 17(3) 中序14, 15, 16, 17, 18, 19, 26, 28, 30(4) 4 次6. (1)对给定权值 2， 1， 3， 3， 4，5，构造哈夫曼树。(3) 画出对上述有序表进行折半查找所对应的判定树答：(1)3次(2) 4 次1. (1)说明什么是顶点活动网(AOV网)和序列,(2)设有向图G如下，写出3)在图G中增加一条边，使图60 G仅有一条拓扑 答：(1)顶点活动网(AOV网)： 边表示活动间先后关系的 拓扑序列：在 AOV 网中

7、, 使得每个活动的所有前驱(2) 3种拓扑序列：105a, b, d, ca, d, b, cd, a, b, c(3) 仅有一条拓扑序列为：a, b, d, c2. 设查找表为(16,15,20,53,64,7),，写出每一趟的排序过程,(1) 用冒泡法对该表进行排序(要求升序排列) 泡？第j趟要进行多少次元素间的比较？(2) 在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树 (1)原序列3 .如下是一棵二叉排序树，A1,A2,A9代表1，2，3,9中各个不同数字，(1) 给出对该树中序遍历的结果(2) A3,A5,A7的值各为多少？(3) 请在该树中再插入一个结点9 .5作为叶

8、结点，并使它仍然是一棵二叉排序树答(1)中序 A7, A4, A8, A2, A5, A9, A1, A3, A6A3,A5,A7的值分别为8, 5, 14.(1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造(2) 说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。 答案：(2)中序遍历中序 2，3，4，5, 6，7，14，16，185.(1)(2)同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。(1)答wpii=4>*jwp12=451.( 1)已知某二叉树的后序遍历序列是deb

9、ca，中序遍历序列是 dbeac，试画出该二叉树。棵二叉排序树，试(2) 若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为 给出a、b、c、d、e的大小关系。(3) 给出该树的前序遍历序列。答：(1)(2) d<b<e<a<c"(3) abdec2 . (1)以3, 4, 5, 8, 9, 10作为叶结点的权，构造一棵哈夫曼树。(2)给出相应权重值叶结点的哈夫曼编码。(3) 一棵哈夫曼树有2n-1个结点，它是共有多少个权重值构造而成的？简述理由？000001011011答:(2) 3,000051089(3) n个，因为非叶结

10、点数比叶结点数少一个，而权值个数=叶结点数叉树(不要求中间3. (1)利用筛选过程把序列42 , 82, 67, 102, 16, 32 , 57, 52建成堆(小根堆)，画出相应的完全. 过程)。(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列。3. (1)(2) 102, 52, 42, 82, 16, 67, 32, 574. (1)简述拓扑排序的步骤。(2) 说明有向图的拓扑序列不一定是唯一的原因。(3) 如何利用拓扌卜排序算法判定图是否存在回路。(4) 设有向图G如下，写出首先删除顶点1的3种拓扑序列。答：(1)循环执行以下两步选择一个度为0的顶点并输出从网中删除此结点及所有

11、出边(2) 因为选择一个度为 0的顶点时不一定是唯一的(3) 由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱(4) 1523641526341562345. 设查找表为(11,12,13,14,15,16,17,18,19,20,21),元素的下标从 0开始。(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用数值表示)(2) 说明成功查找到元素 15，19各需要经过多少次比较?(3) 说明查找不到元素 10，15.5各需要经过多少次比较？(2) 4次 2次(3) 3次 4次(4) 11， 12， 13， 14， 15， 16， 17， 18， 19， 20， 216. 设有序表为(21，22，23，24，25，26，27，28，29，3