8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：
冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；
初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y ；
二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ； 堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。 9. 在堆排序、快速排序和归并排序中，
若只从存储空间考虑，则应首先选取 方法，其次选取 快速排序方法，最后选取归并排序方法；
若只从排序结果的稳定性考虑，则应 选取 归并排序 方法；
若只从平均情况下最快考虑，则应选取 堆排序、快速排序和归并排序 方法；
若只从最坏情况下最快并且要节省内存考虑，则应选取 堆排序 方法。 三、程序填空题
(235) 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
void reverse(pointer h) /* h为附加头结点指针；*/ { pointer p,q;
p=h->next; h->next=NULL; while((1)________) {q=p; p=p->next; q->next=h->next;
h->next=(2)________; }
}
(1)p!=null ∥链表未到尾就一直作
(2)q ∥将当前结点作为头结点后的第一元素结点插入
(236) 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。
void reverse（linklist &L）{
p=null；q=L；
while（q！=null）
{ (1) ; q->next=p；p=q；(2)___ ; }
(3)_____;
}
(1) L=L->next; ∥暂存后继 (2)q=L; ∥待逆置结点 (3)L=p; ∥头指针仍为L
(237) 以下算法的功能是用头插法建立单链表的算法，请填空完善之。
Linklist CreateFromHead( ) { LinkList L;
Node *s; char c;
L=(Linklist)malloc(sizeof(Node)); /*为头结点分配存储空间*/
L->next=NULL ;
While( ( c=getchar()) !=’*’ )
{ s=(Node*)malloc(sizeof(Node)); /*为读入的字符分配存储空间*/
s->data=c;
s->next=L->next ; L->next=s ; }
return L; }
(238) 以下算法的功能是尾插法创建链表，请填空完善之。 typedef struct Node /*结点类型定义*/ { char data;
struct Node * next;
} Node, *LinkList; /* LinkList为结构指针类型*/
Linklist CreateFromTail( ) /*将新增的字符追加到链表的末尾*/ { LinkList L; Node *r, *s; char c; L=(Node * )malloc(sizeof(Node)); /*为头结点分配存储空间*/
L->next=NULL;
r=L; /*r指针指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while( ( c=getchar()) !=’$’ ) /*当输入‘$’时，建表结束*/
{ s=(Node*)malloc(sizeof(Node)); s->data=c;
；r->next=s; r=s;
}
； r->next=NULL /*将最后一个结点的next链域置为空，表示链表的结束*/
return L;
} /*CreateFromTail*/
(239) 下列算法在顺序表L中依次存放着线性表中的元素，在表中查找与e相等的元素，若 L.elem[i]=e,则找到该元素，并返回i+1，若找不到，则返回“-1” ，请填空完善之。
int Locate(SeqList L，int e) { i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while ((i<=L.last)&&(L.elem[i]!=e) ) i++;
/*顺序扫描表，直到找到值为key的元素,
或扫描到表尾而没找到*/
if ( i<=L.last ) return(i+1); /*若找到值为e的元素，则返回其序号*/
else return(-1); /*若没找到，则返回空序号*/ }
(240) 下列算法在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，i的合法取值范围是 1≤i≤L->last+2，请填空完善之。
void InsList(SeqList *L, int i, int e) { int k;
if((i<1) || (i>L->last+2)) printf(“插入位置i值不合
法”)；
if(L->last>=maxsize-1) printf(“表已满无法插入”)；
for(k=L->last;k>=i-1;k--) /*为插入元素而
移动位置*/
L->elem[k+1]=L->elem[k] ;
L->elem[i-1]=e ; /*在C语言数
组中，第i个元素的下标为i-1*/
L->last++ ;
}
(241) 下列算法是在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1，请填空完善之。
int DelList(SeqList *L, int i, int *e) { int k;
if((i<1)||(i>
L->last+1 )) printf(“删除位置不合法！”)；
*e=
L->elem[i-1] ; /* 将删除的元素存放到e所指向的变量中*/
for(k=i;i<=L->last;k++)
L->elem[k-1]=
L->elem[k] ; /*将后面的元素依次前移*/ L->last-- ; }
四、解答题
(242) 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。 (1) 写出队满的条件表达式； (2) 写出队空的条件表达式；
(3) 设m=40,rear=13,quelen=19,求队头元素的位置； (4) 写出一般情况下队头元素位置的表达式。
(1) quelen == m (2) quelen == 0
(3) ( 13 - 19 + 40 ) % 40 = 34