3、543592437485712232853,删除掉最大元素后，堆屮元素为10.从空二叉树开始，严格按照二叉搜索树的插入算法(不进行旋转平衡)，逐个插入关键码｛18,73,10,5,68,99,27,41,51,32,25｝构造出一棵二义搜索树，该二义树转换为森林，则该森林的层次遍历序列为。11.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为12345,％了得到13542出栈顺序，相应的S和X的操作串为。二、单选题(18分，每题2分，最后两题每题4分)1.对初始状态为递增的表按递增顺序排序，最省时间的是()算法。A.基数排序B.桶
4、排C.直接插入排序D.归并排序2.—个n个顶点的连通无向图，其边的个数至少为()。A.n-1B.nC.n+1D.nlogn；3.线性表(aha2，...，a„)以链接方式存储时，访问第i位賈元素的时间复杂度为()A.0(i)B.0(1)C.0(n)D.0(i-1)4.使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号，下面正确的答案是()。A.(0,2)(3,5)(1,4)(2,5)(1,2)B.(0,2)(2,5)(3,5)(1,2)(1,4)C.(0,2)(3,5)(1,4)(1,2)(2,5
5、)B.(0,2)(1,2)(1,4)(2,5)(3,5)5.一个有n个结点的图，最多有()个连通分量。A.0B.1C.n-1D.n6.用二分(对半)查找法检索元素速度比用顺序法()。A.必然快B.必然慢C.相等D.不能确定7.己知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABO+DE/-，其前缀形式为()。A.-A+B*C/DEB.-A+B*CD/EC.-+*ABC/DED..-+A*BC/DE8.对序列｛15,9,7,8,20,-1，4｝进行排序，进行一趟处理(对应于排序算法中一层循环或一层递归算法)后，数据的排列变为｛
6、4,9,-1,8,20,7,15｝;则采用的是()排序。八.选择B.快速C.希尔(Shell)D.冒泡三、简答题(30分，每题10分)1.试W由二叉树的屮序序列和后序序列是否能唯•-的建立二叉树，请说明理由；若能，对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。2.设一组数据为｛1，14,27,29,55,68,10,11，23｝，现采用的散列函数是H(key)=key%13，冲突用链地址法解决，设散列表的大小为13(下标为0〜12)，试画出插入上述数据后的散列表。3.设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2,
7、若T中有6个叶结点，试(1)T树的最大深度Kmax=?最小可能深度Kmin=?(假定独根二叉树深度为0)(2)T树屮共有多少非叶结点？(3)若叶结点的权值分别为1，2,3,4,5,6。请画出一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。四、算法填空题(20分，第一题10分，第2题10分)1.下而是求二叉树高度(独根树高度是1)的递归算法，试补充完整二叉树的两指针域为lchild与rchild,算法屮0为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。intheight(
8、BinTree*p){if(){if(p->lchild=null)lh=;elselh=;if(p-〉rchild==null)rh=;elserh=;if(lh〉rh)hi=；elsehi=;}elsehi=;ret
