1．选择题
ABCCB DCCDC BCCBB CC
2．填空题
（1）3
（2）2，4，（23，38，15）
（3）堆排序，快速排序，归并排序，归并排序，快速排序，堆排序
（4）希尔排序、选择排序、快速排序和堆排序
（5）快速排序，基数排序
（6）堆排序，快速排序
（7）插入排序，选择排序
（8）n-1
3．问答题
（1）排序过程如下。
初始序列： 17 18 60 40 7 32 73 65 85
第1趟排序：7 17 18 60 40 32 65 73 85
第2趟排序：7 17 18 32 60 40 65 73 85
第3趟排序：7 17 18 32 40 60 65 73 85
最终结果： 7 17 18 32 40 60 65 73 85
（2）排序过程如下。
初始序列： 503 87 512 61 908 170 897 275 653 462
第1趟排序：462 87 275 61 170 503 897 908 653 512
第2趟排序：170 87 275 61 462 503 897 908 653 512
第3趟排序：61 87 170 275 462 503 897 908 653 512
第4趟排序：61 87 170 275 462 503 897 908 653 512
第5趟排序：61 87 170 275 462 503 512 653 897 908
第6趟排序：61 87 170 275 462 503 512 653 897 908
最终结果： 61 87 170 275 462 503 512 653 897 908
（3）排序过程如下。
初始序列： 503,17,512,908,170,897,275,653,426,154,509,612,677,765,703,94
第1次排序（d1=8）：426,17,509,612,170,765,275,94,503,154,512,908,677,897,703,653
第2次排序（d2=4）：170,17,275,94,426,154,509,612,503,765,512,653,677,897,703,908
第3次排序（d3=2）：170,17,275,94,426,154,503,612,509,653,512,765,677,897,703,908
第4次排序（d1=1）：17,94,154,170,275,426,503,509,512,612,653,677,703,765,897,908
（4）排序过程如下。
初始序列： (70),83,100,65,10,32,7,9
第1次排序：(70,83),100,65,10,32,7,9
第2次排序：(70,83,100),65,10,32,7,9
第3次排序：(65,70,83,100),10,32,7,9
第4次排序：(10,65,70,83,100),32,7,9
第5次排序：(10,32,65,70,83,100),7,9
第6次排序：(7,10,32,65,70,83,100),9
第7次排序：(7,9,10,32,65,70,83,100)
（5）排序过程如下。
初始序列： 10 18 4 3 6 12 1 9 18 8
第1趟排序：10 18 3 4 6 12 1 9 8 18
第2趟排序：3 4 10 18 1 6 9 12 8 18
第3趟排序：1 3 4 6 9 10 12 18 8 18
第4趟排序：1 3 4 6 8 9 10 12 18 18
最终结果： 1 3 4 6 8 9 10 12 18 18
4．上机操作题
（1）利用奇偶转换排序使整个数组有序。
①没有交换元素为止即结束排序。
②实现本题奇偶转换排序的函数如下。
void oesort(int A[],int n)
{
int i,flag;
do
{
flag=0;
for(i=1;i<=n;i++) /*奇数扫描*/
{
if(A[i]>A[i+1])
{
flag=1;
t=A[i+1];A[i+1]=A[i];A[i]=t;
}
i++;
}
for(i=2;i<=n;i++) /*偶数扫描*/
{
if(A[i]>A[i+1])
{
flag=1;
t=A[i+1];A[i+1]=A[i];A[i]=t;
}
i++;
}
} while(flag!=0);
}
（2）采用快速排序的一趟排序思想，算法描述如下：
Void split(int a[],int n)
{
int i=0,j=n-1,x;
while (i<j)
{
while(i<j&&a[j]>=0)
j--;
while(i<j&&a[i]<0)
i++;
if(i<j)
{
x=a[i];a[i]=a[j];a[j]=x;}
}
}
}
（3）另设一个数组c[n]，其中c[j]保存排序码值比r[j]的排序码值小的记录个数。算法如下：
Void Coumtsort(ReeType r[ ],int n)
{
int I,j,x,*c;
ReeType s;
c=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
c[i]=0;
for(i=0;i<n,i++)
for(j=i+1;j<n;j++)
if(r[i].key<r[j].key)
c[j]++;
else
c[i]++;
for(i=0;i<n;i++)
while(c[i]!=i)
{
x=c[i];s=r[i];
c[i]=c[x];r[i]=r[x];
c[x]=x;r[x]=s;
}
free(c);
}
（4）算法如下：
Void HeapIns(RecType r[],int n,int x)
{
int i;
i=n/2-1;
if(r[i].key<=x)
r[n].key=x;
else
{
j=n;
while(i>=0&&r[i].key>x)
{
r[j]=r[i];
j=i;i=(i-1)/2;
}
r[j].key=x;
}
}
（5）该题实际上是实现计数排序的过程。对应的算法如下：
void CountSort(NodeType R[],int n)
{
int i,j;
for(i=0;i<n;i++) /*置初值*/
R[i].count=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(R[i].key<R[j].key)
R[i].count++;
else
R[i].count=1;
}