一、(本题10分)给出二叉树的定义,并画出具有3个结点的....doc

厦门大学《_数据结构_》课程期末试卷信息科学与技术学院计算机科学系2007年级___专业主考教师:____试卷类型:(A卷/B卷)一、(本题10分)给出二叉树的定义,并画出具有3个结点的二叉树的所有形态。答:简单题。二、(本题15分)考虑下图:1)从顶点A出发,求它的深度优先生成树。2)从顶点E出发,求它的广度优先生成树。3)使用克鲁斯卡尔算法,求它的最小生成树(给出树的生成过程图)。三、(本题15分)假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70),哈希地址空间为0~12,若采用除留余数法H(K)=K%13构造哈希函数,并使用链地址法处理冲突,试画出最后得到的哈希表,并求出平均查找长度。解:元素32752963489425461870 哈希地址6103119312755 查找次数 1 1 1 1 1 2 1 1 1 2平均查找长度为(1*8+2*2)/10=、(本题15分)已知键值序列为{45,56,83,31,72,35,14,47,89,19},要求给出:按键值排列次序构造一棵二叉排序树。在等概率的情况下,该二叉排序树查找成功的平均查找长度。针对上述10个键值,在不同的排列次序下所构造出的不同形态的二叉排序树中,在最坏和最好情况下,二叉排序树的高度各是多少?解:总分为15分,每一小步5分。(1)455315614354783197289(2)在等概率情况下,该二叉排序树的平均检索长度是:ASL=(1+2*2+3*4+4*3)/10=29/10=(3)对于上述10个键值,在最坏情况下,每个结点(除了叶子结点)只有右孩子(或者只有左孩子),高度为10。在最好情况下,高度为└log210┘+1=4。五、(本题15分)给出一系列整数,设计算法求出总和最大的子系列,要求算法的时间复杂性在O(n)之内。答:算法思想:子序列的起始位置初值为1,总和的初值为0。扫描整数序列,一个一个地累加到当前总和,并判断当前总和:如果总和大于0,则一直累加;如果总和小于等于0,则总和清为0,并记录新的子序列起始位置。直到扫描完整个序列,返回最后的子序列起始位置。六、(本题15分)在两个有序线性表中,寻找是否存在共同元素。如果存在共同元素,返回第一个共同元素在两个线性表中的位置。请设计数据结构,并在其上设计算法。答:可以参考有序表的归并算法。七、(本题15分)在n个元素中,找出第k大的元素,最好是在O(n)的时间复杂性之内。请设计数据结构,