小米课
返回首页 | 淘宝问答 | 提交答案
关键字: 威胁 防范 国外 科技优势 考核 电大 汉语专题 赤脚医生 | 时间:2024-09-20 06:06

发布时间:2024-09-20 06:06

| 人浏览

【答案】《数据结构》形成性考核册作业4

《数据结构》形成性考核册作业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 堆排序 

答案有错

上一篇:《数据结构》形成性考核册

下一篇:暂无

小米课手机端XML联系我们