发布时间 : 星期二 文章数据结构复习题习题全六章含答案更新完毕开始阅读
左子树查找
else BST=BST->right; // 转右
子树查找 }
return false; // 没有找到
}
2．( i-1)/2
HBT.heap[i] = HBT.heap[j] i = j
第七章 图
一、填空题
1、2
2、n(n-1)/2、n(n-1) 3、n-1
4、邻接矩阵、邻接表、边集数组 5、n*n ( 或 n行n列 ) 6、e、2e 7、出边、入边 8、e、e
9、O(n)、O(e/n)、O(e)
10、O(n2)、O(n)+O(e)、O(e)+O(n) 11、O（n2）、O（e）
12、014253、012345 13、ABCDE、ABCED 14、22
15、(0,1)5，(1,3)3，(3,2)6，(1,4)8 16、(1,3)3，(0,1)5，(3,2)6，(1,4)8 17、链栈 18、n、n-1 二、应用题 1．
(1) 采用邻接矩阵表示得到的顶点序列如下表所示： (2) 接表表
图 G4 G5 深度优先序列 广度优先序列 采用邻0 1 2 8 3 4 5 6 7 9 0 1 4 2 7 3 8 6 5 9 0 1 2 5 8 4 7 3 6 0 1 3 4 2 6 7 5 8 示得到
的顶点序列如下表所示： 的一种
图 G4 G5 深度优先序列 广度优先序列 2．唯一0 4 3 8 9 5 6 7 1 2 0 4 1 3 7 2 8 6 9 5 0 4 7 5 8 3 6 1 2 0 4 3 1 7 5 6 2 8 拓扑序
列为：1 4 0 2 3 5 7 6 8 9
第八章 查找
一、填空题
1、(n+1)/2、O(n)
2、见p264公式ASL=…、O(log2n) 3、37/12 4、顺序、有序 5、1、3
6、二叉搜索树、理想平衡树 7、6、31、19 8、索引、开始地址
9、(12,63,36)、(55,40,82)、(23,74) 10、3、3、2 11、散列 12、链接 13、2、7/5 14、5
15、开放定址、链接 16、3、2 二、应用题
1．(1) 顺序查找：
ASL = ( 1+2+3+…+25)/25 = 13 (2) 二分查找：
ASL = ( 1+2*2+4*3+8*4+10*5 )/25 = 99/25 = 3.96 ( 参见上图的二分查找树 )
2．散列函数：H(K) = k % m 其中依题意得 m = 13 H( 32 ) = 32 % 13 = 6 H( 75 ) = 75 % 13 = 10 H( 29 ) = 29 % 13 = 3 H( 63 ) = 63 % 13 = 11
H( 48 ) = 48 % 13 = 9
H( 94 ) = 94 % 13 = 3 (冲突) 设 d0 = H(K) = H(94) = 3 d1 = ( d0+1 ) % m = (3+1) = 4 H( 25 ) = 25 % 13 = 12 H( 46 ) = 46 % 13 = 7 H( 18 ) = 18 % 13 = 5
H( 70 ) = 70 % 13 = 5 (冲突) 设 d0 = H(K) = H(70) = 5
d1 = ( d0+1 ) % m = (5+1) = 6 (冲突) d2 = ( d1+1 ) % m = (6+1) = 7 (冲突) d3 = ( d2+1 ) % m = (7+1) = 8 ASL = ( 8*1+1*2+1*4 )/10 = 1.4
3．散列函数：H(K) = k % m 其中依题意得 m = 11
H( 32 ) = 32 % 11 = 10 H( 75 ) = 75 % 11 = 9 H( 29 ) = 29 % 11 = 7
H( 63 ) = 63 % 11 = 8 H( 48 ) = 48 % 11 = 4
H( 94 ) = 94 % 11 = 6 H( 25 ) = 25 % 11 = 3
H( 46 ) = 46 % 11 = 2