a_作业题第四次作业习题课

1、数据结构与算法分析第四次作业张仁涛 MF1332089张源MF1332090统考题:6.下列二叉排序树中,满足平衡二叉树定义的是BC.A.B.D.统考题:7. 下列叙述中, 不符合m阶B 树定义要求的是A. 根结点最多有m棵子树B. 所有叶结点都在同一层上C. 各结点内关键字均升序或降序排列D. 叶结点之间通过指针链接DExercise 1 Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search

2、tree. Show the result of deleting the root333331414141669333141414262626559997 P is a leaf P has exactly one nonempty subtree P has exactly two nonempty subtrees31426597对于第三种情况：1.可以归结为第一种情况(也可能为第二种情况），即用被删结点的左子树的最大值 2 来替换（最后归结为删除叶子结点2）或用被删结点的右子树的最小值 4 来替换（最后归结为第二种情况的删除4）2.也可以归结为第二种情况，即使得被删结点只有一个分支，如

3、下，把被删结点的左子树挂到右子树上；或把被删结点的右子树挂到左子树上24146162595977方案一方案二Exercise 2 写一递归函数实现在带索引的二叉搜索树(IndexBST)中查找第k个小的元素 对于任一节点node，leftsize=左子树中元素个数+1 查找以node为根节点的二叉搜索树中第k个小的元素 If k=n.leftsize,则查找目标为node本身 If kn.leftsize,则目标元素在右子树中leftSizeleftelementright Public BinaryNode findkth(BinaryNode t,int k) if(k=0 | t=nul

4、l)return null; if(kt.leftsize)return findkth(t.right ,k- t.leftsize);elsereturn t;Exercise 3 对一棵空的AVL树，分别画出插入关键码为 16，3， 7，11，9，28，18，14，15后的AVL树1616167左双333167777316316右单31111119169711左单3711161693928281111716右双71839282839161811117187182839162839161414左双11157182839151416Exercise 4 写一个程序判断一个二叉树是不是二叉搜索

5、树 二叉搜索树必须满足： 或者是空树 如果不是空树，则对于任意一个节点 左子树（如果有）中所有节点都小于该节点右子树（如果有）中所有节点都大于该节点 左子树（如果有）也是二叉搜索树 右子树（如果有）也是二叉搜索树方法1:检验左子树的最大值和右子树的最小值 Public boolean isBST(Node n) If (n=null) return true;If (n.left!=null & max(n.left).elementn.element) return false;If (n.right!=null & min(n.right).elementn.element) return

6、 false;return isBST(n.left) & isBST(n.right);方法1 Public Node max (Node n) If (n=null) return null;While (n.right!=null) n=n.right; Return n; Public Node min (Node n) If (n=null) return null;While (n.left!=null) n=n.left; Return n;方法2：中序排列 Public boolean isBST(Node n) If(n=null) return true; List l =

7、 inOrderList(n); int i,j;For(i=0,j=1;j=l.get(j) return false;Return true;方法2 Public List inOrderList(Node n) List l = new ArrayList(); inOrderList(n, l);Return l; Public void inOrderList(Node n, List l) If(n=null) return; inOrderList(n.left, l); l.add(n.element); inOrderList(n.right, l); 5.设有序顺序表中的元

8、素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908. 试画出对其进行二分法搜索时的判定树, 并计算搜索成功的平均搜索长度。 分析：共14个数，所以共log2(14+1)向上取整为4层 建树方法：从根节点起，每次取中间位置的数作为节点内容，若中间有两个则取后一个。 017,094,154,170,275,503,509,512,553,612,677,765,897,908512170765084612908503017094275897509553677平均搜索长度：l=(1+2*2+3*4+4*7)/14=45/14 6.在

9、一棵表示有序集S 的二叉搜索树中, 任意一条从根到叶结点的路径将S分为三部分: 在该结点左边结点中的元素组成集合S1; 在该路径上的结点中的元素组成集合S2; 在该路径右边结点中的元素组成集合S3,S=S1US2US3. 若对于任意的aS1,bS2,有a=b9-12-11，令a=8，b=7.75948121115 7.将关键码DEC, FEB,NOV, OCT, JUL,SEP,AUG,APR, MAR, MAY, JUN, JAN 依次插入到一棵初始为空的AVL 树中, 画出每插入一个关键码后的AVL 树, 并标明平衡旋转的类型.DEC, FEB,NOV, OCT, JUL,SEP,AUG,

10、APR,MAR, MAY, JUN,JANDECDECDECFEB左单FEBDECFEBNOVNOVFEBFEBDECNOVDECNOVJULOCTOCTSEP,AUG,FEBNOVDECNOVFEBOCT左单旋转SEPJULOCTDECJULSEPNOVFEBOCTSEPDECJULAUGAPR, MAR, MAY, JUN,JANNOVNOVFEBOCT右单旋转FEBOCTSEPSEPDECAUGJULJULAUGAPRDECMARAPRMAY, JUN,JANNOVNOVFEBOCTFEBOCT左单旋转SEPSEPAUGAUGJULMARAPRDECAPRDECMARMAYJULMAYJ

11、UN,JANMARNOVFEBOCT左双旋转FEBNOVSEPAUGMAROCTAUGJULMAYAPRDECMAYJULSEPJUNAPRDECJUNJANMARFEBNOVOCTAUGJULMAYSEPJUNAPRDECJAN按月份的结果JULMAROCTNOVFEBMAYSEPDECAPRJUNJANAUGExercise 8 分别delete 50 ,40 in the following 3阶B-树.5060 80309520405570Delete 50找出50的左子树的最大值（40）或者右子数的最小值（55）来代替。55558060 8030309595204060 702040

12、70v Delete 405060 803095205570506060 8080509520 305570709520 3055 10. 分别画出插入65, 15, 40, 30后的3阶B-树。554580908525355060709555插入6545809085253550606570955580554565 80 90456590859585253550607025355060709v 插入15558045659085558025355060709525 4565905580851535506070954565908515 25 3550607095v 插入40558025 45659

13、085153550607095558025 4565908515354050607095v 插入30558025 4565908515354050607095558025 35 4565905580153085405060709525 456590158530 35 4050607095v355580254565901530854050607095553580254565901530854050607095 8. 对于一个高度为h 的AVL 树, 其最少结点数是多少?反之, 对于一个有n 个结点的AVL 树,其最大高度是多少?最小高度是多少?设T h 为一棵高度为h，且结点个数最少的平衡二叉树

14、。假设右子树高度为h-1，因结点个数最少,左子树高度只能是h-2这两棵左子树,右子树高度分别为h-2, h-1,也一定是结点数最少的:h-2h-1h h = 0 T 0h = 1h =2h = 3h = 4TT 12n = 1n = 2n = 4T 3n = 7T 4n = 12以上五棵平衡二叉树，又称为Fibonacci树。也可以这样说一棵高度为h的树，其右子树高度为h-1的Fibonacci树，左子树是高度为h-2的Fibonacci树，即Th - 2Th - 1假设N h表示一棵高度为h的Fibonacci树的结点个数，则N h =Nh - 1 + Nh - 2 + 1N 0 = 1 ,

15、 N 1 = 2 , N 2 = 4 , N 3 = 7 , N4 = 12 ,. . .N 0 + 1 =2 , N 1 + 1 = 3 , N2 + 1 = 5 , N 3 + 1 = 8 , N4 + 1 = 13 , N h + 1满足费波那契数的定义，并且N h+ 1= F h + 3. . .f 00f 11f 21f 32f 43f 55f 6. . .8. . .费波那契数F i 满足下列公式11+511- 5iiFi = ( ) - ( )52521-5|1-5 | 1 , ( )1i相当小2251+51h + 3N h + 1 = ( )+ O ( 1 )2i5费波那契数树

16、是具有相同高度的所有平衡二叉树中结点个数最少的( 1+5n +1Nh +1= 15h + 32) + O( 1 )对于一个有N 个结点的AVL 树, 是多少?最小高度是多少?其最大高度费波那契数树是具有相同高度的所有平衡二叉树中结i个数最少的，点h + 3n +1Nh +1= 1( 1+5) + O( 1 )52 1 log (n+1)+0(1)3 log (n+1) hlog1 +522222这就是h的最大值；至于h的最小值，是一颗完全二叉树的时候，高度最小，有h + 12 -1=n，所以h=log (n+1)-1.21. 给定输入 4371，1323，6173，4199，4344，9679

17、，1989 哈希函数为 h(x) = x mod 10, 指出下列结果：a. 分离链接散列表；b. 使用线性探测的开放定址散列表； c.使用平方探测的开放定址散列表；d.第二个散列函数为h2(x)=7-(x mod 7)开放定址散列表。v h(4371)=1v h(1323)=h(6173)=3v h(4344)=4v h(4199)= h(1989)= h(9679)= 9a分离链接散列表 4371, 1323, 6173, 4199, 4344, 9679, 1989 41999679198943441323617343710123456789b使用线性探测的开放定址散列表4371 mod

18、 10 = 11323 mod 10 = 36173 mod 10 = 3 4371, 1323, 6173, 4199, 4344, 9679, 1989 collision (3+1) mod 10 = 44199 mod 10 = 94344 mod 10 = 4collision (4+1) mod 10 = 59679 mod 10 = 9collision (9+1) mod 10 = 01989 mod 10 = 9collision (9+1) mod 10 = 0collision (9+2) mod 10 = 1collision (9+3) mod 10 = 209679

19、143712198931323461735434467894199c 使用平方探测的开放定址散列表 4371, 1323, 6173, 4199, 4344, 9679, 1989 4371 mod 10 = 11323 mod 10 = 36173 mod 10 = 3collision (3+12) mod 10 = 44199 mod 10 = 94344 mod 10 = 4collision (4+12) mod 10 = 59679 mod 10 = 9collision (9+1) mod 10 = 01989 mod 10 = 9collision (9+12) mod 10

20、= 0collision (9+22) mod 10 = 3collision (9+32) mod 10 = 809679143712313234617354344678198994199d第二个散列函数为h2(x)=7-(x mod 7)开放定址散列表。4371 mod 10 = 11323 mod 10 = 36173 mod 10 = 3collision (3+ h2(6173) mod 10 = 44199 mod 10 = 94344 mod 10 = 4collision (4+ h2(4344) mod 10 = 79679 mod 10 = 9collision (9+ h2(9679) mod 10 = 1collision (9+ 2*h2(9679) mod 10 = 3collision (9+ 3*h2(9679) mod 10 = 51989 mod 10 = 9collision