key: char: next: link END PRoc jj(a, b: link: VAR c: link) VAR p, q, link new(c):c. next: =c: g: =a; p:=a.next WHILE p>a DO WHILE p.key=p.next.keyD0[q:=p;p=p.next]:{跳过相同字母} r: =b. next:(2) WHILE r. key >p. key do r: =r.next IF rob THEN q. next: =p. next: (3) s. next: =c. next: c. next:=s: c: =s ELSE p: p. next next: END 算法时间复杂度为0_(4)【北京工业大学2000四(15分)】 30.以下程序的功能是实现带附加头结点的单链表数据结点逆序连接,请填空完善之。 void reverse(pointer h) /*h为附加头结点指针;类型 pointer同算法设计第3题*/ pointer p, q p=h->next: h->next=NULL lg=p: p=p->next: g->next=h->next: h->next=(2) }【西南交通大学2000一、9】 31.下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法,该算法用L返回逆 置后的链表的头指针,试在空缺处填入适当的语句。 void reverse (linklist &L)( while (q! =null) g->next=p: p=q:(2) I 【北京理工大学2001九、1(6分)】 32.下面程序段是逆转单向循环链表的方法,p是原链表头指针,逆转后链表头指针仍为 (可以根据需要增加标识符) p: po: go: =NIL WHILE (1) egin(2 (3) p. next: =qo po^.next:=p;po:=p;【中国人民大学2000二、1(4分)】 33.一个无头结点的线性链表(不循环)有两个域。数据域data,指针域next,链首head, 下面算法用read(num)读入数据,当num小于0时,输入结束。建立一个数据以递增序组 成的链表key:char; next:link END; PROC jj(a,b:link; VAR c:link); VAR p,q,r,s:link; BEGIN new(c);c^.next:=c; q:=a; p:=a^.next; WHILE p<>a DO [（1）___； WHILE p^.key=p^.next^.key DO [q:=p; p=p^.next];｛跳过相同字母｝ r:=b^.next ; （2）_____; WHILE r^.key <>p^.key DO r:=r^.next; IF r<>b THEN [ s:=p; q^.next:=p^.next; （3） ; s^.next:=c^.next; c^.next:=s; c:=s ] ELSE [ q:=p; p:=p^.next ] ]; c:=c^.next； END; 算法时间复杂度为 O（4）___ 【北京工业大学 2000 四 (15 分)】 30. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 void reverse(pointer h) /* h 为附加头结点指针；类型 pointer 同算法设计第 3 题*/ { pointer p,q; p=h->next; h->next=NULL; while((1)________) {q=p; p=p->next; q->next=h->next; h->next=(2)________; } }【西南交通大学 2000 一、9】 31. 下面是用 c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用 L 返回逆 置后的链表的头指针，试在空缺处填入适当的语句。 void reverse（linklist &L）{ p=null；q=L； while（q！=null） { (1) ; q->next=p；p=q；(2)___ ; } (3)_____; }【北京理工大学 2001 九、1 （6 分）】 32．下面程序段是逆转单向循环链表的方法，p0 是原链表头指针，逆转后链表头指针仍为 p0。 （可以根据需要增加标识符） p:= p0; q0:=NIL; WHILE （1）________ DO BEGIN （2）________; （3）________;（4）______;（5）________ END; p^.next:= q0; p0 ^.next:=p; p0:=p;【中国人民大学 2000 二、1（4 分）】 33．一个无头结点的线性链表(不循环)有两个域。数据域 data，指针域 next，链首 head， 下面算法用 read(num)读入数据，当 num 小于 0 时，输入结束。建立一个数据以递增序组 成的链表