数据结构复习题习题全六章含答案

来源：用户分享时间：2025/5/21 18:32:35 本文由

loading 分享下载这篇文档手机版

说明：文章内容仅供预览，部分内容可能不全，需要完整文档或者需要复制内容，请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ：xxxxxx 处理（尽可能给您提供完整文档），感谢您的支持与谅解。

左子树查找

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

数据结构复习题习题全六章含答案.doc 将本文的Word文档下载到电脑，方便复制、编辑、收藏和打印