人武学院《数据结构》课后习题答案和期末综合练习.doc

第十章内部排序 一、基本知识题答案 1. 排序：将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。 内部排序：数据存储在内存中，并在内存中加以处理的排序方法叫内部排序。 堆：堆是一个完全二叉树，它的每个结点对应于原始数据的一个元素，且规定如果一个结点有儿子结点，此结点数据必须大于或等于其儿子结点数据。 稳定排序：一种排序方法，若排序后具有相同关键字的记录仍维持原来的相对次序，则称之为稳定的，否则称为不稳定的。 2. 回答下面问题 (1) 5000个无序的数据，希望用最快速度挑选出其中前10个最大的元素，在快速排序、堆排序、归并排序和基数排序中采用哪种方法最好？为什么？ (2) 大多数排序算法都有哪两个基本操作？ 答：(1)采用堆排序最好。 因为以上几种算法中，快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。 (2)两个基本操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身。 3. 3. 已知序列{17，25，55，43，3，32，78，67，91}，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。 答：采用冒泡排序法排序时的各趟结果如下： 初始：17，25，55，43，3，32，78，67，91 第1趟：17，25，43，3，32，55，67，78，91 第2趟：17，25，3，32，43，55，67，78，91 第3趟：17，3，25，32，43，55，67，78，91 第4趟：3，17，25，32，43，55，67，78，91 第5趟：3，17，25，32，43，55，67，78，91 第5趟无元素交换，排序结束。 4. 已知序列{491，77，572，16，996，101，863，258，689，325}，请分别给出采用快速排序、堆排序和基数排序法对该序列作递增排序时每一趟的结果。 答：采用快速排序法排序时的各趟结果如下： 初始：491，77，572，16，996，101，863，258，689，325 第1趟：[325，77，258，16，101] 491 [863，996，689，572] 第2趟：[101，77，258，16] 325，491 [863，996，689，572] 第3趟：[16，77] 101 [258] 325，491 [863，996，689，572] 第4趟：16 [77] 101 [258] 325，491 [863，996，689，572] 第5趟：16，77，101 [258] 325，491 [863，996，689，572] 第6趟：16，77，101，258，325，491 [863，996，689，572] 第7趟：16，77，101，258，325，491 [572，689] 863 [996] 第8趟：16，77，101，258，325，491，572 [689] 863 [996] 第9趟：16，77，101，258，325，491，572，689，863 [996] 第10趟：16，77，101，258，325，491，572，689，863，996 采用堆排序法排序时各趟的结果如下图所示： (a) 初始堆 (b) 建堆 (c) 交换996和77，输出996 (d) 筛选调整 采用基数排序法排序时各趟的结果如下： 初始：491，77，572，16，996，101，863，258，689，325 第1趟（按个位排序）：491，101，572，863，352，16，996，77，258，689 第2趟（按十位排序）：101，16，352，258，863，572，77，689，491，996 第3趟（按百位排序）：16，77，101，258，352，491，572，689，863，996 5. 已知序列{86，94，138，62，41，54，18，32}，请给出采用插入排序法对该序列作递增排序时，每一趟的结果。 答：采用插入排序法排序时各趟的结果如下： 初始：(86)，94，138，62，41，54，18，32 第1趟：(86，94)，138，62，41，54，18，32 第2趟：(86，94，138)，62，41，54，18，32 第3趟：(62，86，94，138)，41，54，18，32 第4趟：(41，