《数据结构》形成性考核册作业4答案
第八章答案
一、 填空题：
（1） （n+1）/2 O(n)
（2） 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） 下限值（即low值）
（13） 11 O（ ）
（14） 500 25
（15） 散列
（16） 链接
（17） 2 1.4
（18） 5
（19） n/m
（20） 开放定址法 链接法
（21） 3 2
（22）
（23） 4 5
（24） 4 8
（25） m-1 m
（26） 同一层 关键字
（27） m 两
（28）
（29） 增加1
（30） 减少1
二、 普通题：
（1） 顺序查找：ASL=13
二分查找：ASL=99/25
分块查找：ASL=6
（3） 32 75 29 63 48 94 25 46 18 70
散列地址： 6 10 3 11 9 3 12 7 5 5 散 列 表：
0 1 2 3 4 5 6 7 8 9 10 11 12
29 94 18 32 46 70 48 75 63 25
ASL=1.4
（4）ASL=1.3 （链接法散列表从略）
第九章答案
一、 填空题：
（1） 插入 选择
（2） 交换 二路归并
（3） O（n2） O（n）
（4） n-1
（5） O（log2n） O（n*log2n）
（6） （84,79,56,38,40,46）
（7） O（n*log2n） O（n2）
（8） O（log2n） O（n）
（9） 两端 中间
（10） [38 40 ] 46 [56 79 80 ]
（11） 4 4
（12）
（13） O（n） O（n*log2n） O（n）
（14） 5 4 8
（15） [ 38 46 56 79 ] [ 40 84 ]
二、 普通题：
（1）见内排序方法比较
（2）
3、堆排序：在构成初始化的过程中，每次筛运算后的数据排列为：
1 46 74 16 53 14 34 40 38 86 65 27 26
2 46 74 16 53 65 34 40 38 86 14 27 26
3 46 74 16 86 65 34 40 38 53 14 27 26
4 46 74 40 86 65 34 16 38 53 14 27 26
5 46 86 40 74 65 34 16 38 53 14 27 26
6 86 74 40 53 65 34 16 38 46 14 27 26
完全二叉树（略）
在利用堆排序的过程中，每次筛运算后的数据排列为：
1 74 65 40 53 27 34 16 38 46 14 26 86
2 65 53 40 46 27 34 16 38 26 14 74 86
3 53 46 40 38 27 34 16 14 26 65 74 86
4 46 38 40 26 27 34 16 14 53 65 74 86
5 40 38 34 26 27 14 16 46 53 65 74 86
6 38 27 34 26 16 14 40 46 53 65 74 86
7 34 27 14 26 16 38 40 46 53 65 74 86
8 27 26 14 16 34 38 40 46 53 65 74 86
9 26 16 14 27 34 38 40 46 53 65 74 86
10 16 14 26 27 34 38 40 46 53 65 74 86
11 14 16 26 27 34 38 40 46 53 65 74 86
4、 快速排序每层划分得到的数据排列结果如下：
1 [38 34 16 27 14 26 40] 46 [86 65 53 74]
2 [26 34 16 27 14] 38 40 46 [74 65 53] 86
3 [16 14] 26 [27 34] 38 40 46 [53 65] 74 86
4 14 16 26 27 34 38 40 46 53 65 74 86
5、每一趟二路归并排序结束后的数据排列为：
1 [46 74] [16 53] [14 26] [40 38] [86 65] [27 34]
2 [16 46 53 74] [14 26 38 40] [27 34 65 86]
3 [14 16 26 38 40 46 53 74] [27 34 65 86]
4 14 16 26 27 34 38 40 46 53 65 74 86
（3）
1 直接选择排序
2 直接插入排序
3 快速排序
4 归并排序
5 堆排序
上一篇：《数据结构》形成性考核册
下一篇：暂无