内容发布更新时间 : 2025/5/10 8:11:10星期一 下面是文章的全部内容请认真阅读。
请补上程序中空缺的部分，并估计算法的时间复杂度。（设a，b的结点数分别为m，n） TYPE
link=^node; node=RECORD
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时，输入结束。建立一个数据以递增序组成的链表。
PROC insert( head, x);
{在链首为head的表中按递增序插入x} new(r);r＾.data:=x; IF head=NIL