第九章  排序
一． 填空题
1．排序是将一组任意排列的数据元素按      的值从小到大或从大到小重新排列成有序的序列。
2．在排序前，关键字值相等的不同记录间的前后相对位置保持      的排序方法称为稳定的排序方法。
3．在排序前，关键字值相等的不同记录间的前后相对位置      的排序方法称为不稳定的排序方法。
4．外部排序是指在排序前被排序的全部数据都存储在计算机的_____________储器中。
5．下列程序是按关键字的值从大到小进行直接选择排序的算法，将算法补充完整。
Select(list r,int n)
{for(i=1;______________;i++)
{ k=i；
for(j=i+1;_______________;j++)
if(r[k].key<r[j].key) ______________________;
if(_____________________)
swap(r[k],r[i]);      /*r[k]与r[i]交换*/
}
}
6．将下列按关键字值从小到大进行冒泡排序的算法补充完整。
Bubblesort(int n,list r)
{ flag=_____________________;
m=n-1;
while(m>0 && flag)
{flag=0;
for(i=1;i<=m;i++)
if(r[i].key____________r[i+1].key)
{flag=_________________;
swap(r[i],r[i+1]);   }
m--; }}
7．若快速排序算法中完成一趟快速排序的算法是Quickpass(SqList &r,int low,int high)，将完整的快速排序递归算法补充完整。
Quicksort(SqList &r,int s,int t)
{if(s<t)
{  i=Quickpass(L,s,t);
Quicksort(r,______  ,______);
Quicksort(r,____________);  }
二．选择题
1．直接插入排序的方法是从第（ ）个元素开始，插入前边适当位置的排序方法。
A．1      　　　B．2   　　　　 C．3  　　　　　 D．n
2．冒泡排序的方法（ ）的排序方法。
A．稳定  　　　B．不稳定 　　　 C．外部  　　　 D．选择
3．假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（    ）。
A．2            B．3             C．4            D．5
4．假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（    ）。
A．1, 3, 5, 7, 9, 12                   B．1, 3, 5, 9, 7, 12
C．1, 5, 3, 7, 9, 12                   D．1, 5, 3, 9, 12, 7
5．若一个元素序列基本有序，则选用（    ）方法较快。
A．直接插入排序                 B．简单选择排序
C．堆排序                       D．快速排序
6．若要从1000个元素中得到10个最小值元素，最好采用（    ）方法。
A．直接插入排序                 B．简单选择排序
C．堆排序                       D．快速排序






参 考 答 案
第九章  排序
一． 填空题
1．关键字
2．不变
3．可能变化
4．外部
5．i<n     j<=n     k=j     i!=k
6．1        >       1
7．s       i-1      i+1       t
二．选择题
1． B
2． A
3． B
4． B
5． A
6． C