第九章 排序
一、选择题
1．当待排序列基本有序的情况下，最佳的排序方法是( )。
A. 插入排序 B. 选择排序
B. 归并排序 D. 快速排序
2．设有1,000个无序元素，希望选出10个最小元素，效率最高的排序方法是（ ）。
A. 快速排序 B 基数排序
D. 堆排序 D. 希尔排序
3．若待排序按关键字基本有序，不能选择哪种排序方法（ ）。
A. 冒泡排序 B. 直接选择排序
C. 直接插入排序 D. 快速排序
4．在下列排序方法，比较次数与待排序列初始状态无关的是（ ）。
A. 选择排序 B. 插入排序
C. 希尔排序 D. 冒泡排序
5．下列排序方法中，不稳定的排序方法是（ ）。
A. 归并排序 B. 直接插入排序
C. 冒泡排序 D. 直接选择排序
6．下列排序方法中，空间复杂度为Ｏ（１）的算法的是（ ）。
A. 归并排序 B. 堆排序
C. 快速排序 C. 基数排序
7．下列排序方法中不属于就地排序算法的是（ ）。
A. 希尔排序 B. 归并排序
C. 冒泡排序 D. 堆排序
8．初始关键字序列为（46，56，18，73，44，30，57，34），经过一趟排序后关键字序列为（34，30，18，44，46，73，57，56），所采用的排序方法是（ ）。
字符串长度排序A. 归并排序 B. 堆排序
C. 快速排序 C. 基数排序
9．初始关键字序列为（46，56，18，73，44，30，57，34），进行一趟归并排序结果为（ ）
A.（46，56，18，73，30，44，34，57）
B.（18，46，56，73，44，30，57，34）
C.（18，30，44，46，56，73，57，34）
D.（18，46，56，30，73，44，34，57）
10．初始关键字序列为（46，56，18，73，44），利用筛选算法所建初始堆为（ ）。
A. (18,44,46,73,56) B. (18,46,44,56,73)
C. (56,73,46,44,18) D. (18,44,46,56,73)
11．对n个关键字不同的记录进行冒泡排序,最多的比较次数是( )。
A. n B. n-1 C. n(n-1)/2 D. n(n+1)/2
12．直接插入的排序在哪种情况下比较次数为n-1 。( )
A. 待排关键字序列为逆序； B. 待排关键字序列有序；
C. 待排关键字序列无序； D. 待排关键字局部有序。
13．排序平均时间为O(nlgn)并且是稳定的排序方法是( )。
A. 归并排序 B. 堆排序
C. 快速排序 C. 基数排序
14．当待排序基本有序，应采用哪种排序方法( )。
A. 快速排序 B. 堆排序
C. 直接选择排序 D. 冒泡排序
15．当待排序按关键字随机排列，时间特性最好的排序方法是（ ）。
A. 插入排序 B. 选择排序
C. 快速排序 D. 归并排序
二、填空题
1．快速排序在 情况下时间特性最好，在 情况下时间特性最坏，最坏时间复杂度是 。
2．就稳定性而言，直接选择排序是 的排序方法；基数排序是 的排序方法；堆排序是 的排序方法；希尔排序是 的排序方法。
3．就空间特性而言，快速排序的空间复杂度为 ；基数排序的空间复杂度为 ；归并排序的空间复杂度为 ，堆排序的空间复杂度为 。
4．在插入和选择排序中，若初始关键字序列基本有序，应选用 ，若初始序列基本反序应选用 。
5．在堆排序和快速排序中，若初始关键字序列基本有序，应选用 ，若初始序列无序选用 。
6．初始关键字序列为（12，33，54，27，34，55，2，12，37，68，8）进行一趟希尔排序（设增量为3）则结果为： 。
7．通常在排序算法中的两个基本操作是 和 。
8．对n个元素进行冒泡排序，最多的比较次数是 ；最少的比较次数是 。
9．初始关键字序列为（12，33，54，27，34，55，2，12，37，68，8），进行直接插入排序，当把34插入有序序列需比较的次数是 。
10．若待排序列元素数n较大时,一般选择快速排序、堆排序或归并排序。若要求时间特性好应选择 ，要求空间特性好应选择 ；若要求算法是稳定的有选择 。
三、简答题
1.简单选择排序算法是否稳定，试举例说明。
2.初始关键字序列为23，12，43，8，45，50，35，调整其为堆结构。
3.初始关键字序列为21，34，14，56，25，73，34，65，79，86，3，7，18写出希尔排序过程（增量序列为5，3，1）。
4.初始关键字序列为23，12，43，8，45，50，35，写出归并排序过程。
5.有n个不同的英文单词，长度相等，均为m,若n＞50,m<5，则采用什么排序方法最好，为什么？
6．对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。
四、程序阅读题
1.下列程序是插入排序算法，请在划线处填上适当语句。
void insertsort(Seqlist R)
{
int i,j;
for(i=2,i<=n;i++)
if(R[i].key<R[i-1].key)
{ (1) ;
j=i-1;
do {
R[j+1]=R[j]; (2) ;}
while(R[0].key<R[j].key);
(3) ;
}//endif
}
2.阅读程序
void dbubble(Seqlist R)
{int i=1,j,tag=1;
datatype t;
while(tag)
{ tag=0;
for(j=n-i+1;j>=i+1;j--)
if(R[j].key<R[j-1])
{ tag=1;
t=R[j];R[j]=R[j-1];R[j-1]=t;
}
for(j=i+1;j<=n-i;j++)
if(R[j].key>R[j+1])
{ tag=1;
t=R[j];R[j]=R[j+1];R[j+1]=t;
}
i++;
}
}
（1）指出程序功能；
（2）若R的初始值为：3，18，18，23，28，34，45，56，67，算法执行后R的值是什么？
3．阅读下列算法，并回答下列问题：
(1)该算法采用何种策略进行排序?
(2)算法中R[n+1]的作用是什么?
Typedef struct {
KeyType key;
infoType otherinfo;
} nodeType;
typedef nodeType SqList[MAXLEN];
void sort(SqList R,int n)
{
//n小于MAXLEN-1
int k;i;
for(k=n-1;k>=1;k--)
if(R[k].key>R[k+1].key)
{
R[n+1]=R[k];
for(i=k+1;R[i].key<R[n+1].key;i++)
R[i-1]=R[i];
R[i-1]=R[n+1];
}
}
4.．阅读下列函数algo,并回答问题。
(1)假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少?
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论