数据结构1800题（答案全）(11)

WHILE s <> NIL DO

BEGIN IF s^.data < q^.data THEN BEGIN (1)__; (2)___ END ；

r:= s ； (3)___

END；

write(q^.data : 5) ；

IF p=NIL THEN (4)___ ELSE (5)____ ；

dispose (q) ；

END；

writeln

END；【复旦大学 1996 七（20分） 1995 一（12分）与本题相似】 28．下面函数的功能是在一个按访问频度不增有序的，带头结点的双向链环上检索关键值为x的结点，对该结点访问频度计数，并维护该链环有序。若未找到，则插入该结点。所有结点的频度域初值在建表时都为零。请将程序中四处空缺补写完整。

TYPE

link=^node

node=RECORD

key:char; freq:integer; pre,next:link;

END;

VAR l:link;

FUNCTION loc(l:link;x:char):link;

VAR p,q:link;

BEGIN

p:=l^.next; （1）_；

WHILE p^.key<>x DO p:=p^.next;

IF p=l THEN [ new(q); q^.key:=x; q^.freq:=0 ]

ELSE {找到}

[ p^.freq:=p^.freq+1; q:=p; （2）______；

WHILE q^.freq>p^.pre^.freq DO p:=p^.pre;

IF p<>q THEN [ （3）______ ] ]；

IF （4）_ THEN [q^.next:=p, q^.pre;=p^.pre; p^.pre^.next:=q; p^.pre:=q]

return(q);

END;【北京工业大学 1999 五 (12分)】

29．循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。（设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

THEN[ head:=(1) _____; r＾.next:= (2)________ ]

ELSE IF (3)___ THEN [r＾ .next:=head; head:=r]

ELSE [p:=head;

WHILE (4)___ AND (p＾.next≠NIL ) DO[q:=p; (5)___ ];

IF (6)___ THEN [ q＾ .next:=(7)___; r＾.next:= (8)____; ]

ELSE [p＾.next:=(9)____; r＾.next:= (10)___; ]

]

ENDP;

PROC creat(head);

head:= (11)______; read(num);

WHILE num>0 DO

[ insert(head,num); read(num) ]

ENDP;【南京理工大学 1999 三、4（11分）】

34. 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef ，指数域exp和指针域 next；现对链表求一阶导数 ，链表的头指针为ha，头结点的exp域为 –1。

derivative(ha)

{ q=ha ; pa=ha->next;

while( (1)_______)

{ if ( (2)____) { ( (3)__); free(pa); pa= ( (4) _); }

else{ pa->coef ( (5) ___); pa->exp( (6)___); q=( (7) __);}

pa=( (8)________);

}

} 【南京理工大学 2000 三、3（10分）】

35.下面是删除单链表L中最大元素所在结点的类PASCAL语言算法，请在横线填上内容，完成其功能。

TYPE pointer =↑node；

node=RECORD

data:integer; next: pointer

END;