电大数据结构本综合题精选.docVIP

三、综合题(每小题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=3 (1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确?若认为正确，则回答正确，若认为不正确，则举例说明。 不正确。例（图5） (2)设有数据集合 {40,29,7,73,101,4,55,2,81,92,39}，依次取集合中各数据，构造一棵二叉排序树。 图6 (1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈夫曼编码。图7 2:0000 3:0001 4:001 7:10 8:11 9:01 (2)一棵哈夫曼树有n个叶结点，它一共有多少个结点?简述理由?2n-1个，因为非叶结点数比叶结点数少一个 1.一组记录的关键字序列为(46,79,56,38,40,84) (l)利用快速排序的方法，给出以第一个记录为墓准得到的一次划分结果。(给出逐次交换元素的过程，要求以升序排列) 初始序列46,79,56,38,40,84 40,79,56,38,40,84 40,79,56,38,79,84 40,38,56,38,79,84 40,38,56,56,79,84 40,38,46,56,79,84 (2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 2.设查找表为(16,15,20,53,64,7) (1)用冒泡法对该表进行排序(要求升一序排列)，要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡?第j趟要进行多少次元素间的比较? (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。(要求以数据元素作为树结点) 求在等概率条件下，对上述有序表成功查找的平均查找长度。 平均查找长度=(1*1+2*2+3*3)/6=14/6 3. (1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由?不正确，二叉排序树要求其子树也是二叉排序树。 (2)设有查找表{7,16,4,8,20,9,6,18,5)，依次取表中数据构造一棵二叉排序树。对上述二叉树给出后序遍历的结果。 后续遍历5,6,4,9,8,18,20,16,7 设一组记录的关键字序列为(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次元素间的比较才能成功查到; 19，48，84，116，200 画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示); (3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。3次 3.(1)对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。 对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20共要进行多少次元素的比较?先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。 1.(1)已知某二叉树的先序遍历序列是aecdb，中序遍历序列是eadcb，试画出该二叉树。 (2)给出上述二叉树的后序遍历序列。 edbca. 若上述二叉树的各个结点的字符分别是 1,2,3,4,5，并恰好使该树成为一棵二叉排序树,试问a,b,c,d,e的值各为多少? e=l,a=2,d=3,c=4,b=5 (l)给定数列{8,17,5,9,21,10,7,19,6),依次取序列中的数构造丫棵二叉排序树。 (2)对上述二叉树给出中序遍历得到的序列。 5,6,7,8,9,10,1,18,19,21 3.(1)以给定权