排序历年试题及参考答案(08)

第8章 排序

（2008年1月）

11、下列排序方法中，稳定的排序方法为（ ）

A、希尔排序 B、堆排序

C、快速排序 D、直接插入排序

12、对下列关键字序列进行快速排序时，所需进行比较次数最少的是（ ）

A、（1，2，3，4，5，6，7，8） B、（8，7，6，5，4，3，2，1）

C、（4，3，8，6，1，7，5，2） D、（2，1，5，4，3，6，7，8）

23、在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有___________。

（2008年10月）

11、对长度为n的关键字序列进行堆排序的空间复杂度为（ ）

A、 O（log2n） B、 O（1）

C、 O（n） D、 O（n*log2n）

12、已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）

所采用的排序方法是（ ）

A、 插入排序 B、 冒泡排序

C、 快速排序 D、 归并排序

23、在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 。

28、某类物品的编号由一个大写英文字母及2位数字（0…9）组成，形如E32。运用基数排序

对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。 E13，A37，F43，B32，B47，E12，F37，B12

第一趟：

第二趟：

第三趟：

33、阅读下列对正整数关键字序列L操作的算法，并回答问题：

（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值；

（2）简述函数f33的功能。

int Partition (SeqList*L, int low, int high);

∥对L[low…high]做划分，返回基准记录的位置，并使左部的关键字

∥都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字 int f33 (SeqList L, int k){

int low, high, pivotpos;

low=1;

high=L.length;

if (khigh)

return-1;

do {

pivotpos=Partition (&L, low, high);∥调用快速排序的划分算法

if (pivotpos

low=pivotpos+1;

else if (pivotpos>k)

high=pivotpos-1;

}while (pivotpos!=k);

return L.data [pivotpos];

}

（1）

（2）

（2009年1月）

12、下列关键字序列中，构成大根堆的是( )

A、5，8，1，3，9，6，2，7 B、9，8，1，7，5，6，2，33

C、9，8，6，3，5，l，2，7 D、9，8，6，7，5，1，2，3

23、对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_________。

27、对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。

(1)写出排序过程中前两趟的划分结果；

(2)快速排序是否是稳定的排序方法?

(1)

(2)

33、下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。

#define MAXLEN 100

typedef int KeyType;

typedef struct {

KeyType key;

InfoType otherinfo;

} NodeType ;

typedef NodeType SqList[ MAXLEN ];

void f33 ( SqList R, int n)

{ int i,j,k;

NodeType t;

i =0;

j =n-l;

while (i

for ( (1) )

if (R[k]、key > R[k +l]、key) {

t = R[k];

R[k] = R[k +1];

R[k +1] = t;

}

j--;

for (k =j; k > i; k -- )

if ( (2) ) {

t = R[k];

R[k] = R[k-1];

R[k-1] = t;

}

(3) ;

}

}

(1)

(2)

(3)

（2009年10月）

13、对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为

基准的一次划分的结果为（ ）

A、(5，1，4，3，6，2，8，7) B、(5，1，4，3，2，6，7，8)

C、(5，1，4，3，2，6，8，7) D、(8，7，6，5，4，3，2，1)

24、若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是

________的。

29、对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构

建的初始(大根)堆及前两趟重建堆之后的序列状态。

初始堆：

第1趟：

第2趟：

（2010年1月）

13、下列排序算法中不稳定的是（ ）

A、快速排序 B、归并排序

C、冒泡排序 D、直接插入排序

23、对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_________。

28、已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，

85)，用堆排序方法建小根堆，请给出初始建堆后的序列。

32、数组A[]中存储有n个整数，请阅读下列程序。

void f32(int A[],int n)

{

int i,j,k,x;

k=n-1;

while(k>0)

{

i=k;

k=0;

for(j=0;j

if(A[j]>A[j+1])

{

x=A[j];

A[j]=A[j+1];

A[j+1]=x;

k=j;

}//end of if

}//end of while

return;

}

请回答下列问题：

(1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么?

(2)说明该算法的功能。

（2010年10月）

12、如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是

( )

A、不稳定的 B、稳定的

C、基于交换的 D、基于选择的

22、影响排序效率的两个因素是关键字的___________次数和记录的移动次数。

32、下面程序实现插入排序算法。

typedef struct{

int key;

Info otherinfo;

}SeqList;

void InsertSort(SeqList R［］,int n)

{/* 待排序列保存在R［1、、n］中*/

SeqList x；

int i，j，k，lo,hi,mi;

for (i=2；i

{

lo=1；

hi=i-l;

while (lo

{

mi=(lo+hi)/2;

if ) break;

if (R［mi］、key>x、key) hi=mi-l;

else lo=mi+l;

}

if (mi=lo) k=i - mi;

else k=i - mi-1;

for (j=0；j

R［i-j］=x；

}

}

在空白处填写适当的内容，使该程序功能完整。

(1)

(2)

(3)

（2011年1月）

11、平均时间复杂度为O(n log n)的稳定排序算法是（ ）

A、快速排序 B、堆排序

C、归并排序 D、冒泡排序

12、已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（ ）

A、(18,22,30,46,51,68,75,83) B、(30,18,22,46,51,75,83,68)

C、(46,30,22,18,51,75,68,83) D、(30,22,18,46,51,75,68,83)

23、当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是________________。

28、已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题：

(1)画出堆排序的初始堆（大根堆）；

(2)画出第二次重建堆之后的堆。

参考答案

（2008年1月）

11、D

12、C

23、快速排序

（2008年10月）

11、B

12、B

23、选择排序

28、

第一趟：B32，E12，B12，E13，F43，A37，B47，F37

第二趟：E12，B12，E13，B32，A37，F37，F43，B47

第三趟：A37，B12，B32，B47，E12，E13，F37，F43

33、

（1）20

（2）查找关键字序列L中第k小的元素

（2009年1月）

12、D

23、15，12，11，10，8，16，18，17，13，19

27、对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。

(1)写出排序过程中前两趟的划分结果；

(2)快速排序是否是稳定的排序方法?

(1)第1趟2,3,1,5,9,6,8,7

第2趟1,2,3,5,7,6,8,9

(2)不是

33、

(1) k=i;k

(2) R[k].key

(3) i++

（2009年10月）

13、C

24、稳定

29、

初始堆：(96，55，63，48，22，31，50，37，11)

第1趟：(63，55，50，48，22，31，11，37，96)

第2趟：(55，48，50，37，22，31，11，63，96)

（2010年1月）

13、A

23、{42，13，94，55，05，46，17 }

28、(12，15，14，18，16，36，18， 60，25，85)

32、

(1) {2，4，6，7，8，10}

(2) 对数组A中的n个整数进行（冒泡）排序。

（2010年10月）

12、B

22、比较

32、

(1) x=R[i]

(2) R[mi].key==x.key

(3) R[i-j]= R[i-j-1]

（2011年1月）

11、C

12、D

23、直接插入排序

28、

(1) {96，63，78，25，57，11，44}

(2) {63，57，44，25，11，78，96}