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;
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
{ 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．线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？【西安电子科技大学 1999软件 二、1 （5分）】
2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，
表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。【重庆大学 2000 二、5】 3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？ 【北京航空航天大学 1998 一、2（4分）】 4．线性结构包括______、______、_______和_______。线性表的存储结构分成______和______。请用类PASCＡL语言描述这两种结构。【华北计算机系统工程研究所1999一、2（10分）】 5．线性表（a1，a2，?，an）用顺序映射表示时，ai和ai+1（1<=i 【东南大学 1996 一、1 （5分）】 6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 【厦门大学 2000 五、1 （14%/3分）】 7. 试述头结点,首元结点,头指针这三个概念的区别. 【武汉交通科技大学 1996 二、2 (3分)】【西安电子科技大学2001计应用 二、1（5分）】 8. 已知有如下定义的静态链表： TYPE component=RECORD data:elemtp; next:0..maxsize END VAR stalist:ARRAY[0..maxsize] OF component; 以及三个指针:av指向头结点，p指向当前结点，pre指向前驱结点，现要求修改静态链表中next域中的内容，使得该静态链表有双向链表的功能，从当前结点p既能往后查找，也能往前查找： （1） 定义next域中的内容。(用老的next域中的值表示)； （2） 如何得到当前结点p的前驱（pre）的前驱，给出计算式; （3） 如何得到p的后继，给出计算式;【中科院计算所 2000 四（10分）】 9. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 【西安电子科技大学1999计应用一、1 （5分）】 10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？ 【中国人民大学 2001 二、4 （2分）】 11. 下面是一算法的核心部分，试说明该算法的功能。 pre:=L↑.next; {L是一单链表，结点有数据域 data和指针域 next} IF pre<>NIL THEN WHILE pre↑.next<>NIL DO BEGIN p:=pre↑.next; IF p↑.data>=pre↑.data THEN pre:=p ELSE return(false) END; return(true); 【燕山大学 2000 七、1 （7分）】 12. 设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。 【北京科技大学 2000 一、3】 13. 设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作（PASCAL语句）。【北京科技大学 1999 一、2 （2分）】 14. 有线性表(a1,a2,?,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个