《数据结构复习题-第10章答案2014-6-16》由会员分享，可在线阅读，更多相关《数据结构复习题-第10章答案2014-6-16（7页珍藏版）》请在金锄头文库上搜索。
1、1第 10 章 内部排序一、选择题（每小题 1 分，共 10 分）1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列的合适位置，该排序方法称为（ A ）排序法。A.插入排序 B.选择排序 C.希尔排序 D.二路归并排序2.下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择 B.冒泡 C.归并 D.堆3.若一组记录的排序码为（46, 79, 56, 38, 40, 84） ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ） 。A. 38, 40, 46, 56, 79, 84 B. 40, 38, 46
2、, 79, 56, 84 C. 40, 38， 46, 56, 79, 84 D. 40, 38, 46, 84, 56, 794.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ） 。A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序5.为实现快速排序算法，待排序序列宜采用的存储方式是（ A ） 。A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储6.若一组记录的排序码为（46, 79, 56, 38, 40, 84） ，则利用堆排序的方法建立的初始堆为（ B ） 。A. 79, 46, 56
3、, 38, 40, 84 B. 84, 79, 56, 38, 40, 46 C. 84, 79, 56, 46, 40, 38 D. 84, 56, 79, 40, 46, 38 7排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ） 。A希尔排序 B冒泡排序 C插入排序 D选择排序 8在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ D ） 。A希尔排序 B冒泡排序 C直接插入排序 D直接选择排序9堆是一种有用的数据结构。下列关键码序列（ D ）是一个堆。A94,31,53,23,16,72 B94,53
4、,31,72,16,23 C16,53,23,94,31,72 D16,31,23,94,53,7210堆排序是一种（ B ）排序。A 插入 B 选择 C 交换 D 归并 11 （ D ）在链表中进行操作比在顺序表中进行操作效率高。A 顺序查找 B 折半查找 C 分块查找 D 插入 12直接选择排序的时间复杂度为（ D ） 。 （n 为元素个数）AO(n) BO(log 2 n) CO(nlog 2 n) DO(n 2 )二、判断题（每小题 1 分，共 10 分）1.对于 n 个记录的集合进行快速排序，所需要的平均时间是 O(nlogn)。 （ 对 ）2.（101，88，46，70，34，39
5、，45，58，66，10）是堆。( 对 ) 3.如果某种排序算法是不稳定的则该方法没有实际应用价值。( )4.外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。 （ ）5.具有 n 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 （ ）6. 在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。( )27.在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过 1。( )8.冒泡排序算法关键字比较的次数与记录的初始排列次序无关。 （ ）三、填空题（每空 1 分，共 10
6、 分）1.不仅需要使用内存，而且还要使用外存的排序称为 。答：外部排序2.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 和记录的 。答：比较、移动3.直接插入排序用监视哨的作用是_。答：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。4.排序方法有_、_、_、_、_。答：插入排序 交换排序 选择排序 归并排序 基数排序5.稳定的排序方法有_、_、_、_。答：直接插入排序、冒泡排序、归并排序、基数排序、折半插入排序6.不稳定的排序方法有_、_、_、_。答：希尔排序、快速排序、简单选择排序（直接选择排序） 、堆排序、树形选择排序7.稳定的排序方法有_、_ ；不
7、稳定的排序方法有_、_ 。四、简答题（共 10 分）1.简述快速排序算法的基本思想。答：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。答案二：在待排序的 n 个记录中任取一个记录（通常取第一个记录） ，以该记录作为标准，将所有记录分成两组，使第一组中各记录的关键字都小于等于该标准关键字，而第二组中各记录的值都大于等于该标准关键字，并把该记录排放在这两组的中间位置，这样遍历一趟文件后，将文件以该记录为界分为两部分，然后再对上面两组分别重复上述过程，直到每一部分仅剩一个记录为止。2.对于下列各种排
8、序方法，哪些是稳定的？哪些是不稳定的？（1）直接插入排序； （2）希尔排序； （3）快速排序；（4）堆排序； （5）归并排序； （6）基数排序。答：（1） （5） （6）是稳定的排序方法；（2） （3） （4）是不稳定的排序方法。3.希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。答：(1) 希尔排序 512 275 275* 061 增量为 2 275* 061 512 275 增量为 1 061 275* 275 512 (2) 直接选择排序 275 275* 512 061 i = 1 061 275* 512 275 i = 2 061 275* 512 275
9、 i = 3 061 275* 275 512 (3) 快速排序 512 275 275* 275* 275 512 (4) 堆排序 275 275* 061 170 已经是最大堆，交换 275 与 170 170 275* 061 275 对前 3 个调整 275* 170 061 275 前 3 个最大堆，交换 275*与 061 061 170 275* 275 对前 2 个调整3 170 061 275* 275 前 2 个最大堆，交换 170 与 061 061 170 275* 275 4.什么是内排序? 什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的?答：内排序是排序
10、过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的数据对象间比较排序码，如果发生逆
11、序(与最终排序的顺序相反的次序) 才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“(或1) lastExchangeIndex = 1;for (j = 1; j ai+1) temp=ai; ai=ai+1; ai+1=temp; 6 分for(i=1;i=pivotdey) high;L.rlow=L.rhigh; 3 分while(low=pivotkey) 6-high;RlowRhigh; while (low=high+1; -j )L.rj+1 = L.rj; / 记录后移L.rhigh+1 = L.r0; /
12、 插入 / for / BInsertSort5.（6 分）编写简单选择排序的算法。void SelectSort (int R, int n ) / 对记录序列 R1.n作简单选择排序。for (i=1; in; +i) / 选择第 i 小的记录，并交换到位j = SelectMinKey(R, i); / 在 Ri.n 中选择关键字最小的记录if (i!=j) RiRj; / 与第 i 个记录交换 / SelectSort76.（6 分）编写归并排序的算法。 （可选）void Merge (int R, int R2, int l, int m, int h) / 将有序的记录序列 Rl.m 和 Rm+1.h/ 归并为有序的记录序列 R2l.hfor (i=l , j=m+1; i=m & j=h; +k) / 将 R 中记录由小到大地并入 R2if (Ri =Rj) R2k = Ri;else R2k = Rj;if (i=m) Rk.h = Ri.m;/ 将剩余的 Ri.m 复制到 R2if (j=h) R2k.h = Rj.h;/ 将剩余的 Rj.h 复制到 R2 / Merge
