第九章排序习题 数据结构.pdf

****题九 排序

一、单项选择题
1．下列内部排序算法中：
A．快速排序 直接插入排序 B.
简单选择排序 D. 涉及的存储设备的不同，排序可分为________排序和________排序。

3．直接插入排序用监视哨的作用是___________________________。

4．对 n个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。

5．下面的 c函数实现对链表 head进行选择排序的算法,排序完毕,链表中的结点按结点值从
小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：
#include <>
typedef struct node {char data; struct node *link; }node;
node *select(node *head)
{node *p,*q,*r,*s;
p=(node *)malloc(sizeof(node));
p->link=head; head=p;
while(p->link!=null)
{q=p->link; r=p;
while ((1)____________)
{ if (q->link->data<r->link->data) r=q;
q=q->link;
}
if ((2)___________) {s=r->link; r->link=s->link;
s->link= ((3)_________); ((4)_________);}
((5)________) ;
}
p=head; head=head->link; free(p); return(head);
}

6．下面的排序算法的思想是：第一趟比较将最小的元素放在 r[1]中，最大的元素放在 r[n]
中，第二趟比较将次小的放在 r[2]中，将次大的放在 r[n-1]中，„,依次下去，直到待排
序列为递增序。（注： <-->）代表两个变量的数据交换）。
void sort(SqList &r,int n) {
i=1;
while((1)______) {
min=max=1;
for (j=i+1;(2)________ ;++j)
{if((3)________) min=j; else if(r[j].key>r[max].key) max=j; }
if((4)_________) r[min] < ---- >r[j];
if(max