发布时间 : 星期一 文章第十章 排序更新完毕开始阅读
3.属于不稳定排序的有_希尔排序、简单选择排序、快速排序、堆排序等__。
4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡_算法，最费时间的是_快速_算法。
2
5.不受待排序初始序列的影响，时间复杂度为O(N)的排序算法是_简单选择排序_，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_直接插入排序_。
6．直接插入排序用监视哨的作用是_免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率_。 7．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_n(n-1)/2_。
8.用链表表示的数据的简单选择排序，结点的域为数据域data，指针域next；链表首指针为head，链表无头结点。 selectsort(head) p=head;
while (p(1)!=null___) {q=p; r=(2)p->next___ while((3)r!=null_ )
{if ((4)r->data
r=(5)r->next_ ;
}
tmp=q->data; q->data=p->data; p->data=tmp; p= (6)p->next___ ; }
9．下面的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)q->link!=NULL____)
{ if (q->link->data
}
if ((2)r!=p___) {s=r->link; r->link=s->link; s->link= ((3)p->link__); ((4)p->link=s_);} ((5)p=p->link__) ; }
p=head; head=head->link; free(p); return(head); }
10．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，?,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。
void sort(SqList &r,int n) { i=1;
while((1)i for (j=i+1;(2)j<=n-i+1____ ;++j) {if((3)r[j].key if(max!=n-i+1){if ((5)max==i___) r[min] < ---- > r[n-i+1]; else ((6)r[max]<-->r[n-i+1]__); } i++; } }//sort 11．表插入排序的基本思想是在结点中设一指针字段，插入Ri时Rl到Ri-1己经用指针按排序码不减次序链结起夹，这时采用顺序比较的方法找到Ri应插入的位置，做链表插入。如此反复，直到把Rn插入为止。 （1）(6分)请完成下列表插人的算法； ①. R[0].LINK←(1)N___; R[N].LINK←(2)0 ___; ②.循环，I以-1为步长，从(3)N-1___到(4)_1__执行 （1）P← R[0].LINK; Q← 0 （2）循环，当P>0且(5)R[P].KEY （3）R[Q].LINK←I; R[I].LINK←P （2）(2分)表插入排序的最大比较次数是(7)(N+2)(N-1)/2__； （3）（2分）表插入排序的最小比较次数是(8)N-1__； （4）（2分）记录移动的次数是(9)0__； （5）（2分）需要附加的存储空间是(10)O(1)__； （6）（2分）该排序算法是否是稳定的(11)稳定____。 12.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需___3_趟，写出第一趟结束后，数组中数据的排列次序_(10,7,-9,0,47,23,1,8,98,36)_。 13．从平均时间性能而言，__快速_排序最佳。 14．对于7个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为_(4,1,3,2,6,5,7)_。 2 16．在数据表有序时，快速排序算法的时间复杂度是_O(n)_。 17．堆排序的算法时间复杂度为：_O(nlog2n)_。 21．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆__④是堆__。 ①16，72，31，23，94，53 ②94，53，31，72，16，23 ③16，53，23，94，31，72 ④16，31，23，94，53，72 ⑤94，31，53，23，16，72 堆排序是一种_选择_类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年Floyd提出的_筛选法_，对含有n个元素的序列进行排序时,堆排序的时间复杂度是_O(nlog2n)_，所需要的附加结点是_O(1)_。 22．堆是一种有用的数据结构.堆排序是一种_选择_排序，堆实质上是一棵_完全二叉树_结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_O(Nlog2N)_，所需的附加存储结点是_O(1)_。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_满足堆的性质_。 24．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果__{{D,Q,F,X,A,P,B,N,M,Y,C,W}_。 27．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_（Q,A,C,S,Q,D,F,X,R,H,M,Y）_；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_(F,H,C,D,Q,A,M,Q,R,S,Y,X)_。 28．外部排序的基本方法是归并排序，但在之前必须先生成_初始归并段(顺串)_。 30．设输入的关键字满足k1>k2>?>kn，缓冲区大小为m，用置换-选择排序方法可产生_?n/m?_个初始归并段。