第二章 线性表(8)

[（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分)】

(1)a^.key:=’@’∥a的头结点用作监视哨，取不同于a链表中其它数据域的值 (2)b^.key:=p^.key∥b的头结点起监视哨作用

(3)p:=p^.next∥找到a,b表中共同字母，a表指针后移 (4)0(m*n)

22. 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。 void reverse（linklist &L）{ p=null；q=L； while（q！=null）

{ (1) ; q->next=p；p=q；(2)___ ; } (3)_____; }

【北京理工大学 2001 九.1 （6分）】 (1)L=L->next; ∥暂存后继 (2)q=L; ∥待逆置结点 (3)L=p; ∥头指针仍为L

23. 下面程序段是逆转单向循环链表的方法，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分)】

(1) p^.next<>p0 (2)r:= p^.next (3) p^.next:= q0; (4) q0:= p; (5) p:=r

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

{ q=ha ; pa=ha->next; while( (1)_______)

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

26

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

【南京理工大学 2000 三.3（10分）】 (1)pa!=ha ∥或pa->exp!=-1

(2)pa->exp==0 ∥若指数为0，即本项为常数项 (3)q->next=pa->next ∥删常数项 (4)q->next ∥取下一元素 (5)=pa->coef*pa->exp

(6)-- ∥指数项减1

(7)pa ∥前驱后移,或q->next (8)pa->next ∥取下一元素

25. 对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 typedef struct node

{int data; struct node *next; }linknode,*link;

void Insertsort(link L) { link p,q,r,u;

p=L->next; (1)______; while((2)________) { r=L; q=L->next;

while((3)________&& q->data<=p->data) {r=q; q=q->next;} u=p->next; (4)______; (5)______; p=u; } }

【北京科技大学 2001 二 （10分）】

(1)L->next=null ∥置空链表,然后将原链表结点逐个插入到有序表中 (2)p!=null ∥当链表尚未到尾

(3)q!=null ∥查p结点在链表中的插入位置，这时q是工作指针。 (4)p->next=r->next ∥或p->next=q 将p结点链入链表中

(5)r->next=p ∥r是q的前驱，u是下个待插入结点的指针。 26. 下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空；操作完成后A，B保持不变，C中元素按递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A,B)实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链表的表头结点。 typedef struct node{ int element; struct node *link;}NODE; NODE *A，*B，*C; …… 此处隐藏：401字，全部文档内容请下载后查看。喜欢就下载吧 ……