排序-历年试题及参考答案.doc

(完整)排序 历年试题及参考答案(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 （k〈low |｜ k〉high）
return—1;
do ｛
pivotpos=Partition (＆L， low, high)；∥调用快速排序的划分算法
if （pivotpos〈k）
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 < j) ｛
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<i;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〈=n；i++)
｛
(1) ；
lo=1；
hi=i-l;
while （lo<=hi)
｛
mi=（lo+hi）/2;
if （ (2） ) 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<k;j++）
(3） ;
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<j;k++
（2） R[k］。key 〈 R[k -l］.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｝