数据结构复习题-第10章答案2014-6-16.doc

第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, 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, 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,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(log2 n) CO(nlog2 n) DO(n2 )二、判断题（每小题1分，共10分）1.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlogn)。（ 对 ）2.（101，88，46，70，34，39，45，58，66，10）是堆。( 对 ) 3.如果某种排序算法是不稳定的则该方法没有实际应用价值。( )4.外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。 （ ）5.具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（ ）6. 在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。( )7.在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。( )8.冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（ ）三、填空题（每空1分，共10分）1.不仅需要使用内存，而且还要使用外存的排序称为 。答：外部排序2.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 和记录的 。答：比较、移动3.直接插入排序用监视哨的作用是_。答：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。4.排序方法有_、_、_、_、_。答：插入排序 交换排序 选择排序 归并排序 基数排序5.稳定的排序方法有_、_、_、_。答：直接插入排序、冒泡排序、归并排序、基数排序、折半插入排序6.不稳定的排序方法有_、_、_、_。答：希尔排序、快速排序、简单选择排序（直接选择排序）、堆排序、树形选择排序7.稳定的排序方法有_、_ ；不稳定的排序方法有_、_ 。四、简答题（共10分）1.简述快速排序算法的基本思想。答：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。答案二：在待排序的n个记录中任取一个记录（通常取第一个记录），以该记录作为标准，将所有记录分成两组，使第一组中各记录的关键字都小于等于该标准关键字，而第二组中各记录的值都大于等于该标准关键字，并把该记录排放在这两组的中间位置，这样遍历一趟文件后，将文件以该记录为界分为两部分，然后再对上面两组分别重复上述过程，直到每一部分仅剩一个记录为止。2.对于下列各种排序方法，哪些是稳定的？哪些是不稳定的？（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 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个调整 170 061 275* 275 前2个最大堆，交换170与061 061 170 275* 275 4.什么是内排序? 什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的?答：内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“(或)”改写成“(或)”，也可能造成不稳定。参考题：4.在什么条件下，MSD基数排序比LSD基数排序效率更高？答：由于高位优先的MSD方法是递归的方法，就一般情况来说，不像低位优先的LSD方法那样直观自然，而且实现的效率较低。但如果待排序的排序码的大小只取决于高位的少数几位而与大多数低位无关时，采用MSD方法比LSD方法的效率要高。5.堆排序是否是一种稳定的排序方法？为什么？答：堆排序不是一种稳定的排序方法。因为在堆调整的过程中，关键字进行比较和交换的所走路线是沿着根结点到叶子结点，因此对于相同的关键字就可能存在后面的先被变换到前面。例如对于初始大J顶堆(2，1，)，第一遍堆调整为(,1)(2),因而堆排序不是稳定的。6.在多关键字排序时，LSD和MSD两种方法的特点是什么？答：最高位优先（MSD）法：先对最高位关键字K0进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的K0值，然后，分别就每个子序列对关键字K1进行排序，按K1值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。最低位优先（LSD）法：先对最低位关键字Kd-1进行排序，然后对高一级关键字Kd-2进行排序，依次重复，直至对最高位关键字K0排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki (0=i1) lastExchangeIndex = 1;for (j = 1; j i; j+) if (Rj+1.key Rj.key) Swap(Rj, Rj+1); / temp=Rj ; Rj= Rj+1; Rj+1= temp; lastExchangeIndex = j; /记下进行交换的记录位置 /ifi = lastExchangeIndex; / 本趟进行过交换的最后一个记录的位置 / while / BubbleSort答案二：见教材16页答案三：void paixu(int a,int n)for(i=0;in;i+) scanf (%d,&ai); for(j=0;j=9;j+) for (i=0;iai+1) temp=ai; ai=ai+1; ai+1=temp; 6分for(i=1;i11;i+) printf(%5d,ai ); printf(n); 2.（6分）写出一趟快速排序的算法。答案一：int partition(sqlist L, int low, int high) L.r0=L.rlow; pivotkey=L.rlow.key; 1分 while(lowhigh)while(low=pivotdey) high; L.rlow=L.rhigh; 3分 while(lowhigh&L.rlow.key=pivotkey) +low; L.rhigh=L.rlow; 5分L.rlow=L.r0;return low; 7分答案二：（也可以使用教材274页算法10.6a）int Partition (RedType &R, int low, int high) pivotkey = Rlow.key; while (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhigh & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 返回标准（枢轴）所在位置 / Partition3.（6分）编写直接插入排序的算法。void InsertionSort ( SqList &L ) / 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) L.r0 = L.ri; / 复制为监视哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移L.rj+1 = L.r0; / 插入到正确位置 / InsertSort4.（6分）编写折半插入排序的算法。void BiInsertionSort ( SqList &L ) for ( i=2; i=L.length; +i ) L.r0 = L.ri; / 将 L.ri 暂存到 L.r0low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key =high+1; -j ) L.rj+1 = L.rj; / 记录后移L.rhigh+1 = L.r0; / 插入 / 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 个记录交换 / SelectSort6.（6分）编写归并排序的算