《第8章排序练习题答案.doc》由会员分享，可在线阅读，更多相关《第8章排序练习题答案.doc（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流第8章排序练习题答案.精品文档.第8章排序练习题答案填空题1. 大多数排序算法都有两个基本的操作： 比较 和 移动 。2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 3 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用 选择 。正序时两种方法移动次数均为0，但比较次数量级不同，插入法：n-1即O(n)，选择法：O(n2)反序时两种方法比较次数量级相同，均为O(n2)，但移动次数不同，插入法：O
2、(n2)，选择法：3(n-1)即O(n)4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间复杂度是 O(n2) 。若对其进行快速排序，在最坏的情况下所需要的时间复杂度是 O(n2) 。6. 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间是 O(n) 。7 对于n个记录的表进行2路归并排序，整个归并排序需进行 log2n 趟（遍）。8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关
3、键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X；快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ；堆排序初始建堆的结果是 Y S X R P C M H Q D F A 。（大根堆）9. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 堆排序 方法，其次选取 快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应 选取归并排序方法；若只从平均情况下最快考虑，则应选取快速排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。