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

第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, 79

4.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素

进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）。

A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序

1

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 ）是一个堆。

A．94,31,53,23,16,72 B．94,53,31,72,16,23 C．16,53,23,94,31,72

D．16,31,23,94,53,72

2

10．堆排序是一种（ B ）排序。

A ．插入 B ．选择 C ．交换 D ．归并

11．（ D ）在链表中进行操作比在顺序表中进行操作效率高。

A ．顺序查找 B ．折半查找 C ．分块查找 D ．插入

12．直接选择排序的时间复杂度为（ D ）。（n 为元素个数）

A．O(n) B．O(log

2

n) C．O(nlog

2

n) D．O(n

2

)

二、判断题（每小题1分，共10分）

1.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlogn)。（ 对 ）

2.（101，88，46，70，34，39，45，58，66，10）是堆。( 对 )

3.如果某种排序算法是不稳定的．则该方法没有实际应用价值。( × )

4.外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花

的时间取决于内部排序的时间。 （× ）

5.具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。（ √）

6. 在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相

3

对次序仍然保持不变，称这种排序为稳定排序。( √ )

7.在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。( √ )

8.冒泡排序算法关键字比较的次数与记录的初始排列次序无关。（ × ）

三、填空题（每空1分，共10分）

1.不仅需要使用内存，而且还要使用外存的排序称为 。答：外部排序

2.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 和

记录的 。答：比较、移动

3.直接插入排序用监视哨的作用是_______。答：免去查找过程中每一步都要检测整个

表是否查找完毕，提高了查找效率。

4.排序方法有________、_______、________、________、________。答：插入排序 交换

排序 选择排序 归并排序 基数排序

5.稳定的排序方法有________、_______、________、________。答：直接插入排序、冒

泡排序、归并排序、基数排序、折半插入排序

6.不稳定的排序方法有________、_______、________、________。答：希尔排序、快速

排序、简单选择排序（直接选择排序）、堆排序、树形选择排序

7.稳定的排序方法有________、_______ ；不稳定的排序方法有________、_______ 。

4

四、简答题（共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

5

{ 061 275* 275 512 }

(2) 直接选择排序 { 275 275* 512 061 } i = 1

{ 061 275* 512 275 } i = 2

{ 061 275*

{ 061 275*

(3) 快速排序

{ 275* 275

(4) 堆排序

170

{ 170 275*

{ 275* 170

{ 061 170

{ 170 061

{ 061 170

512

275

{ 512

512 }

{ 275

061

061

275*

275*

275*

275 } i = 3

512 }

275 275* }

275* 061 170 } 已经是最大堆，交换275与

275 } 对前3个调整

275 } 前3个最大堆，交换275*与061

275 } 对前2个调整

275 } 前2个最大堆，交换170与061

275 }

6

4.什么是内排序? 什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的?

答：内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需

进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象

的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在

排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁

盘次数和在内存中总的记录对象的归并次数。

不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排

序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的

不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在

相邻的数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因

此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。

但如果把算法中判断逆序的比较“>(或<)”改写成“≥(或≤)”，也可能造成不稳定。

参考题：

4.在什么条件下，MSD基数排序比LSD基数排序效率更高？

答：由于高位优先的MSD方法是递归的方法，就一般情况来说，不像低位优先的LSD

方法那样直观自然，而且实现的效率较低。但如果待排序的排序码的大小只取决于高位的

少数几位而与大多数低位无关时，采用MSD方法比LSD方法的效率要高。

5.堆排序是否是一种稳定的排序方法？为什么？

7

答：堆排序不是一种稳定的排序方法。因为在堆调整的过程中，关键字进行比较和交

换的所走路线是沿着根结点到叶子结点，因此对于相同的关键字就可能存在后面的先被变

换到前面。例如对于初始大J顶堆(2，1，)，第一遍堆调整为(,1)(2),因而堆排序不是稳

定的。

6.在多关键字排序时，LSD和MSD两种方法的特点是什么？

答：最高位优先（MSD）法：先对最高位关键字K0进行排序，将序列分成若干子序

列，每个子序列中的记录都具有相同的K0值，然后，分别就每个子序列对关键字K1进行

排序，按K1值不同再分成若干更小的子序列，……，依次重复，直至最后对最低位关键字

排序完成，将所有子序列依次连接在一起，成为一个有序子序列。

最低位优先（LSD）法：先对最低位关键字Kd-1进行排序，然后对高一级关键字Kd-2

进行排序，依次重复，直至对最高位关键字K0排序后便成为一个有序序列。进行排序时，

不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki (0<=i

能用稳定的排序方法。另一方面，按LSD进行排序时，可以不通过关键字比较实现排序，

而是通过若干次“分配”和“收集”来实现排序。

五、应用题（共40分）

1.已知序列{503，87，512，61，908，170，897，275，652，462}，采用基数排

序法对该序列作升序排序时的每一趟的结果。

答案依题意，采用基数排序法排序的各趟的结果如下：

8

初始：503，87，512，61，908，170，897，275，652，462

第1趟（按个位排序）：170，61，512，652，462，503，275，87，897，908

第2趟（按十为排序）：503，908，512，652，61，462，170，275，87，897

第3趟（按百为排序）：61，87，170，275，462，503，512，652，897，908

2.写出快速排序的思想，并写出序列（49，38，65，97，76，13，27，50）第一趟

快速排序的过程。

3.对一组记录（54，38，96，23，15，72，60，45，83）执行希尔排序（D=5，3，

1），记录每一趟排序结果。

4.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18) 执行希尔排序（D=6，3，1），

记录每一趟排序结果。

5.对一组记录（54，38，96，23，15，72，60，45，83）执行冒泡排序，记录每一

趟排序结果。

6.已知一组元素的排序码为（36，25，48，12，65，20），写出用直接插入排序法每

次向前面有序表插入一个元素后的排列结果。

7.写出关键字序列（265,301,751,129,937,863,742,694,076,438）执行简单选择排序

方法各趟结束时的序列状态。

9

8.写出用堆排序算法对(29，18，25，47，58，12，51，10)进行排序时，初始堆及

以后每挑好一个元素重新调整后堆的状态。

9.判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为

堆）。

（1）100，85，98，77，80，60，82，40，20，10，66

（2）100，85，40，77，80，60，66，98，82，10，20

（3）10，20，40，60，66，77，80， 82，85，98，100

10.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

11. 已知序列{503，87，512，61，908，170，897，275 ，653，462} ，请给出

采用希尔排序法对该序列作升序排序时每一趟的结果。

12.试说明归并排序的基本过程，并给出对关键字序列{47，33，6l，82，72，l1，25，

57}进行两路归并排序的示意。

13.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18).写出用下列算法从小到大排序

时

第一趟结束时的序列。

(1)希尔排序(第一趟排序的增量为5)

10

(2)快速排序(选第一个记录为枢轴(分隔))

(3)链式基数排序(基数为10)

14.给出一组关键字：28，07，39，10，65，14，61，17，50，21，写出按起泡排

序方法进行排序的过程。

15.判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，

则把它调整为堆，试给出堆排序方法在平均时间性能最坏情况下的时间性能和辅助存储量，

并与快速排序方法在以上三方面进行比较

六、算法题（共12分）

1.（6分）编写起泡排序的算法。

答案一：

void BubbleSort(Elem R[ ], int n) {

i = n;

while (i >1) {

lastExchangeIndex = 1;

for (j = 1; j < i; j++)

11

if (R[j+1].key < R[j].key)

{

Swap(R[j], R[j+1]); // temp=R[j] ; R[j]= R[j+1]; R[j+1]= temp;

lastExchangeIndex = j; //记下进行交换的记录位置

} //if

i = lastExchangeIndex; // 本趟进行过交换的最后一个记录的位置

} // while

} // BubbleSort

答案二：见教材16页

答案三：

void paixu(int a[],int n)

{

for(i=0;i

12

for(j=0;j<=9;j++)

{ for (i=0;i<10-j;i++) 2分

if (a[i]>a[i+1])

{ temp=a[i];

a[i]=a[i+1];

a[i+1]=temp;}

} 6分

for(i=1;i<11;i++)

printf("%5d,",a[i] );

printf("n");

}

2.（6分）写出一趟快速排序的算法。

答案一：

13

int partition(sqlist L, int low, int high)

{L.r[0]=L.r[low];

pivotkey=L.r[low].key; 1分

while(low

{

while(low=pivotdey) –high;

L.r[low]=L.r[high]; 3分

while(low

L.r[high]=L.r[low]; 5分

}

L.r[low]=L.r[0];

return low; 7分

}

14

答案二：（也可以使用教材274页算法10.6a）

int Partition (RedType &R[], int low, int high) {

pivotkey = R[low].key;

while (low

while (low=pivotkey)

--high;

R[low]←→R[high];

while (low

++low;

R[low]←→R[high];

}

return low; // 返回标准（枢轴）所在位置

} // Partition

15

3.（6分）编写直接插入排序的算法。

void InsertionSort ( SqList &L ) {

// 对顺序表 L 作直接插入排序。

for ( i=2; i<=; ++i )

if (L.r[i].key < L.r[i-1].key) {

L.r[0] = L.r[i]; // 复制为监视哨

for ( j=i-1; L.r[0].key < L.r[j].key; -- j )

L.r[j+1] = L.r[j]; // 记录后移

L.r[j+1] = L.r[0]; // 插入到正确位置

}

} // InsertSort

4.（6分）编写折半插入排序的算法。

void BiInsertionSort ( SqList &L ) {

16

for ( i=2; i<=; ++i ) {

L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0]

low = 1; high = i-1;

while (low<=high) {

m = (low+high)/2; // 折半

if (L.r[0].key < L.r[m].key)

high = m-1; // 插入点在低半区

else low = m+1; // 插入点在高半区

}//在 L.r[1..i-1]中折半查找插入位置；

for ( j=i-1; j>=high+1; --j )

L.r[j+1] = L.r[j]; // 记录后移

L.r[high+1] = L.r[0]; // 插入

} // for

17

} // BInsertSort

5.（6分）编写简单选择排序的算法。

void SelectSort (int R[], int n ) {

// 对记录序列]作简单选择排序。

for (i=1; i

// 选择第 i 小的记录，并交换到位

j = SelectMinKey(R, i); // 在 ] 中选择关键字最小的记录

if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换

}

} // SelectSort

6.（6分）编写归并排序的算法。（可选）

void Merge (int R[], int R2[], int

l

, int

m

, int

h

) {

// 将有序的记录序列 R[

l

..m] 和 R[m+1..

h

]

18

// 归并为有序的记录序列 R2[

l

..

h

]

for (i=

l

, j=m+1; i<=m && j<=h; ++k)

{ // 将R中记录由小到大地并入R2

if (R[i] <=R[j]) R2[k] = R[i];

else R2[k] = R[j];

}

if (i<=m) R[k..h] = ];

// 将剩余的 ] 复制到 R2

if (j<=h) R2[k..h] = R[j..h];

// 将剩余的 R[j..h] 复制到 R2

} // Merge

19