第10章 排序自测题答案.doc

在数据结构领域，排序是核心概念之一，它涉及如何有效地组织和比较数据。本章主要讨论了四种经典的排序算法：直接插入排序、冒泡排序、快速排序和归并排序，以及一种特殊的数据结构——堆。 1. 排序算法通常包含两个基本操作：比较和移动。比较用于确定元素之间的相对顺序，而移动则是将元素调整到正确的位置。 2. 直接插入排序在处理给定序列（54，38，96，23，15，72，60，45，83）时，将第7个记录60插入到有序表时，至少需要比较6次才能找到合适的位置。 3. 冒泡排序在最坏的情况（即输入逆序）下，需要进行n*(n-1)/2次比较，时间复杂度为O(n^2)。快速排序在最坏情况下也有相同的时间复杂度，这是因为每次划分只能减少一个元素，导致递归深度达到n。 4. 归并排序在平均情况下的时间复杂度为O(nlogn)，需要额外的空间O(n)来存储临时数组。 5. 各排序算法的特征如下： - 冒泡排序一趟后，序列变为H C Q P A M S R D F X Y。 - 希尔排序一趟后，序列变为P A C S Q H F X R D M 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。 - 堆排序初始建堆的结果是A D C R F Q M S Y P H X。 6. 存储空间考虑时，优先选择堆排序，因为它原地排序，不需要额外空间；稳定性考虑时，选择归并排序，因为它保持相等元素的相对顺序；平均速度最快时，堆排序、快速排序和归并排序都可能，取决于具体数据；最坏情况且节省内存，仍选堆排序。 7. 单项选择题的答案： - 1. C. 10次 - 2. C. 插入排序 - 3. D. 选择排序 - 4. B. 从大到小排列好的情况比较次数最多 - 5. D. n(n-1)/2次 - 6. B. O(n^2) - 7. C. 40, 38, 46, 56, 79, 84 - 8. D. 16, 23, 53, 31, 94, 72 - 9. B. 选择排序 - 10. C. 完全二叉树 堆是一种特殊的完全二叉树，满足堆属性，即父节点的关键字总是大于或等于（或小于或等于）其子节点的关键字。这种数据结构常用于实现堆排序，一种选择排序，其中元素的选择基于堆的性质。堆排序在最坏情况下时间复杂度为O(nlogn)，但不需要额外的连续存储空间，因此在空间效率上优于归并排序。