《最新电大数据结构（本）综合题 精选.doc》由会员分享，可在线阅读，更多相关《最新电大数据结构（本）综合题 精选.doc（3页珍藏版）》请在三一办公上搜索。
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)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确?若认为正确，则回答正确，若认为不正确，则举例说明。 不正确。例（图5） (2)设有数据集合 40,29,7,7
2、3,101,4,55,2,81,92,39，依次取集合中各数据，构造一棵二叉排序树。图63. (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,
3、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)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。(要求以数据元素作为树结点) (3) 求在等概率条件下，对上述有序表成功查找的平均
4、查找长度。 平均查找长度=(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,71. 设一组记录的关键字序列为(49,83,59,41,43,47)，采用堆排序算法完成以下操作:(要求小根堆，并画出中间过程)(1)
5、以二叉树描述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(2) 画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示);(3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。3次3.(1)对给定数列7,16,4,8,20,9,6,18,5，依次取数列中的数据，构造一棵二叉排序树。(2) 对一个给定的查找值，简述针
6、对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20共要进行多少次元素的比较?先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找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),依次取序列中
7、的数构造丫棵二叉排序树。 (2)对上述二叉树给出中序遍历得到的序列。5,6,7,8,9,10,1,18,19,213.(1)以给定权重值1,2,12,13,20,25为叶 结点，建立一棵哈夫曼树。 (2)幻若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一。2n-1不一定唯一1. (1)一组记录的关键字序列为 45,40,65,43,35,95写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的结果)。45 40 65 43 35 9535 40 65 43 35 9535 40 65 43 65 953
8、5 40 43 43 65 9535 40 43 45 65 95(2) 同样对序列45,40,65,43,35,95利用直接插入排序，写出逐次插入过程(从第一个元素一直到第六个元素)。40 45 65 43 35 9540 43 45 65 35 9535 40 43 45 65 952. (1)利用筛选过程把序列 42,82,67,102,16,32,57,52建成堆(小根堆儿画出相应的完全二叉树(不要求中间过程)。(2) 写出对上述堆对应的完全二叉树进行中序遍历得到的序列。102 ,52 ,42 ,82 ,16 ,67 ,32 ,573. (1)设有一个整数序列 50,38,16,82,
9、110, 13, 64，依次取出序列中的数，构造一棵二叉排序树。右图(2)利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到,为了查找15,经多少次元素间的比较可知道查找失败。三次; 四次1. (1)已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树。右图(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的),并恰好使该树成为一棵二叉排序树,试给出a、b、c、d、e的大小关系。dbeanext=head2; p2-next=head1;(2)单向链表的链域为next,设指针p指向单向链表中的某个结点,指针S指向一个要插入链表的新结点
10、,现要把s所指结点插入p所指结点之后,某学生采用以下语句:p-next=s; s-next=p-next;这样做正确吗?若正确则回答正确,若不正确则说明应如何改写.不对,s-next=p-next; p-next=s;2. (1)画出对长度为10的有序表进行折半查找的判定树(以序号1,2,10表示树结点)。右图(2) 对上述序列进行折半查找,求等概率条件下,成功查找的平均查找长度。ASL=(l*l+2*2+3*4+4*3)/10=29/103. (1)利用筛选法,把序列37,77,62,97,11,27,52,47建成堆(小根堆),画出相应的完全二叉树。(2)写出对上述堆所对应的二叉树进行前序遍历得到的序列.11,37,47,97,77,27,62,52“电大天堂”
