资源描述：
《最新电大数据结构（本）综合题 精选》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、三、综合题(每小题10分，共30分)1.设查找表为(7,15,21,22,40,58,68,80,88,89,120)，元素的下标依次为1,2,3,……,11,(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)图4(2)说明成功查找到元素40需要经过多少次比较?4次(3)求在等概率条件下，成功查找的平均比较次数?ASL=(1+2*2+3*4+4*4)/11=32.(1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确?若认为正确，则回答正确，若认为不
2、正确，则举例说明。不正确。例（图5）(2)设有数据集合{40,29,7,73,101,4,55,2,81,92,39}，依次取集合中各数据，构造一棵二叉排序树。图63.(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。图72:00003:00014:0017:108:119:01(2)一棵哈夫曼树有n个叶结点，它一共有多少个结点?简述理由?2n-1个，因为非叶结点数比叶结点数少一个1.一组记录的关键字序列为(46,79,56,38,40,84)(l)利用快速排序的方法，给
3、出以第一个记录为墓准得到的一次划分结果。(给出逐次交换元素的过程，要求以升序排列)初始序列46,79,56,38,40,8440,79,56,38,40,8440,79,56,38,79,8440,38,56,38,79,8440,38,56,56,79,8440,38,46,56,79,84(2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。2.设查找表为(16,15,20,53,64,7)(1)用冒泡法对该表进行排序(要求升一序排列)，要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多
4、少趟冒泡?第j趟要进行多少次元素间的比较?(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。(要求以数据元素作为树结点)(3)求在等概率条件下，对上述有序表成功查找的平均查找长度。平均查找长度=(1*1+2*2+3*3)/6=14/63.(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由?不正确，二叉排序树要求其子树也是二叉排序树。(2)设有查找表{7,16,4,8,20,9,6,1
5、8,5)，依次取表中数据构造一棵二叉排序树。对上述二叉树给出后序遍历的结果。后续遍历5,6,4,9,8,18,20,16,71.设一组记录的关键字序列为(49,83,59,41,43,47)，采用堆排序算法完成以下操作:(要求小根堆，并画出中间过程)(1)以二叉树描述6个元素的初始堆;(2)以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆。2.设有序表为(13,19,25,36,48,51,63,84,91,116,135,200)，元素的下标依次为1,2,……,12。(1)说出有哪几个元素需要经过4
6、次元素间的比较才能成功查到;19，48，84，116，200(2)画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示);(3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。3次3.(1)对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。(2)对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20共要进行多少次元素的比较?先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查
7、找，查找20共进行3次比较。1.(1)已知某二叉树的先序遍历序列是aecdb，中序遍历序列是eadcb，试画出该二叉树。(2)给出上述二叉树的后序遍历序列。edbca.(3)若上述二叉树的各个结点的字符分别是1,2,3,4,5，并恰好使该树成为一棵二叉排序树,试问a,b,c,d,e的值各为多少?e=l,a=2,d=3,c=4,b=52.(l)给定数列{8,17,5,9,21,10,7,19,6),依次取序列中的数构造丫棵二叉排序树。(2)对上述二叉树给出中序遍历得到的序列。5,6,7,8,9,10,1,18,19,21
8、3.(1)以给定权重值1,2,12,13,20,25为叶结点，建立一棵哈夫曼树。(2)幻若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一。2n-1不一定唯一1.(1)一组记录的关键字序列为{45,40,65,43,35,95}写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结
