PROCEDURE delmax (L:pointer);
VAR p,q,r:pointer; m:integer;
BEGIN
r:=L； p:=L↑.next;
IF p<>NIL THEN
[ m:=p↑.data; (1)________; p:=p↑.next;
WHILE p<>NIL DO
[ IF (2)________THEN [ (3)________ ; m:=p↑.data; ]
(4)________; p:=p↑.next; ]
q:=r↑.next; (5)______; dispose(q);
]
END;【北京科技大学 1998 二】
36．对单链表中元素按插入方法排序的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分）】
37．下面是一个求两个集合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运算执行完毕，再删除并释放表示结果集合的链表的表头结点。
程序(a)（编者略去这个PASCAL程序）
程序（b）
typedef struct node{ int element; struct node *link;
}NODE;
NODE *A，*B，*C;
NODE *append (NODE *last,int e)
{ last->link=(NODE*) malloc (sizeof(NODE));
last->link->element=e;
return(last->link); }
NODE *difference(NODE *A,NODE *B)
{NODE *C,*last;
C=last=(NODE*) malloc (sizeof(NODE));
while (1)___
if (A->element
else if (2) ___ { A=A->link; B=B->link; } ELSE (3) ___ ;
while (4) __
{ last=append(last,A->element); A=A->link; }
(5) ___; last=C; C=C->link; free (last); return (C); }
/*call form:C=difference(A,B);*/【上海大学 2000 一、4 （10分）】
三．填空题
1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py
4 ．n-i+1
5．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
6．O(1)，O(n) 7．单链表，多重链表，（动态）链表，静态链表
8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
9．p^.prior s^.prior^.next
10． 指针 11．物理上相邻 指针 12．4 2
13．从任一结点出发都可访问到链表中每一个元素。
14．u=p->next; p->next=u->next; free(u); 15．L->next->next==L 16．p->next!=null
17．L->next==L && L->prior==L 18．s->next=p->next;p->next=s;
19．(1) IF pa=NIL THEN return(true);
(2) pb<>NIL AND pa^.data>=pb^.data
(3) return(inclusion(pa,pb));
(4) pb:=pb^.next;
(5) return(false);
非递归算法：
(1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)pa:=pa^.next; pb:=pb->next;
(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IF pa=NIL THEN return(true) ELSE return(false);
[注]：本题是在链表上求模式匹配问题。非递归算法中用指针pre指向主串中开始结点（初始时为第一元素结点）。若主串与子串对应数据相等，两串工作指针pa和pb后移；否则，主串工作指针从pre的下一结点开始（这时pre又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若pa为空，则匹配成功，返回true，否则，返回false。
20．A．VAR head:ptr B. new(p) C. p^.data:=k D. q^.next:=p E. q:=p(带头结点) 21．（1）new(h);∥生成头结点，以便于操作。
（2）r^.next:=p; (3) r^.next:=q; (4) IF (q=NIL) THEN r^.next:=p;
22．A: r^.link^.data<>max AND q^.link^.data<>max
B: r:=r^.link C: q^.link D: q^.link E: r^.link F: r^.link
G: r:=s（或r:= r^.link） H: r:=r^.link I: q^.link:=s^.link
23．(1)la (2)0 (3)j 24.(1)head^.left:=s ∥head的前驱指针指向插入结点 (2)j:=1; (3)p:=p^.right ∥工作指针后移 (4)s^.left:=p (5)p^.right^.left:=s; ∥p后继的前驱是s (6)s^.left:=p; 25.(1)i<=L.last ∥L.last 为元素个数 (2)j:=j+1 ∥有值不相等的元素 (3)L.elem[j]:=L.elem[i] ∥元素前移 (4)L.last:=j ∥元素个数 26.(A)p^.link:=q;∥拉上链，前驱指向后继 (B)p:=q;∥新的前驱 (C)p^.link:=head;∥形成循环链表 (D)j:=0; ∥计数器，记被删结点 (E)q:=p^.link∥记下被删结点 (F)p^.link=q^.link ∥删除结点 27. (1)p:=r;∥r指向工作指针s的前驱，p指向最小值的前驱。 (2)q:=s;∥q指向最小值结点，s是工作指针 (3)s:=s^.link∥工作指针后移 (4)head:=head^.next;∥第一个结点值最小； (5)p^link:=q^.link;∥跨过被删结点（即删除一结点） 28．(1) l^.key:=x;∥头结点l这时起监视哨作用 (2) l^.freq:=p^.freq ∥头结点起监视哨作用 (3) q->pre->next=q->next; q->next->pre=q->pre; ∥先将q结点从链表上摘下 q^.next:=p; q^.pre:=p^.pre; p^.pre->next:=q; p^.pre:=q; ∥结点q插入结点p前 (4) q^.freq=0 ∥链表中无值为x的结点，将新建结点插入到链表最后（头结点前）。 29．(1)a^.key:=’@’∥a的头结点用作监视哨，取不同于a链表中其它数据域的值 (2)b^.key:=p^.key∥b的头结点起监视哨作用