的关系。
【厦门大学 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，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。
（1）线性表中元素无序。（2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。
【北京邮电大学 1994 七 （7分）】
15．设pa，pb分别指向两个带头结点的有序（从小到大）单链表。仔细阅读如下的程序，并回答问题：
（1） 程序的功能。（2） s1，s2中值的含义。（3） pa，pb中值的含义。 PROCEDURE exam(pa,pb) BEGIN
p1:=pa↑.next; p2:=pb↑.next; pa↑.next:=∧; s1:=0; s2:=0;
WHILE p1≠∧ AND p2≠∧ DO
[ CASE p1↑.data dispose(p) ]; p1↑.data>p2↑.data: p2:=p2↑.next; p1↑.data=p2↑.data: [p:=p1; p1:=p1↑.next; p↑.next:= pa↑.next; pa↑.next:= p; p2:= p2↑.next;s1:=s1+1; ]; END ]; WHILE p1≠∧ DO [ p:=p1; p1:=p1↑.next; dispose(p); s2:=s2+1 ] END;【南京航空航天大学 1995 十 （9分）】 16．写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。 结点结构为：(llink,data,rlink) 【北京邮电大学 1992 三、4 （25/4分）】 p 10231530 17．按照下列题目中的算法功能说明，将算法描述片段中的错误改正过来。 （1） （４分）下面的算法描述片段用于在双链表中删除指针变量p所指的结点： p^.rlink←p^.llink^.rlink; p^.llink←p.^rlink^.llink dispose(p); （2） （６分）下面的算法描述片段用于在双链表中指针变量p所指结点后插入一个新结点： new(q); q^.llink←p; p^.rlink←q; q^.rlink←p^.rlink; q←p^.rlink^.llink; 【山东大学 1999 八（10分）】 18．已知L是一个数据类型linkedlist的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能。【山东科技大学 2001 一、2 （5分）】 TYPE linkedlist=↑node; node=RECORD data:datatype; next:linkedlist END; PROC Mp(pa,pb:linkedlist); PROC subp(s,q: linkedlist); p:=s; WHILE p↑.next<>q DO p:=p↑.next; p↑.next:=s ENDP; subp(pa,pb); subp(pb,pa); ENDP; 19．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语言描述语句。【北京科技大学 2001 一、3 （2 分）】 20．本题给出一个子程序的框图，如图2，试填空完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表f1，f2，f3中的相同整数。假定在调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1的例子所示。 注：在图2的框图中：found和exit均为布尔型的变量，可取值为true和false。val是整型变量，用来存放第一个均出现在f1，f2，f3中的相同整数。若f1，f2和f3中无相同的整数，found 的值为false，否则found的值为true。f1↑.link表示访问f1所指结点的link域。 【哈尔滨工业大学 1999 三 （15分）】 21. 一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法： （1）说明该算法的功能。（2）在空缺处填写相应的语句。 void unknown (BNODETP *L) { ? p=L->next; q=p->next; r=q->next； while (q!=L) { while (p!=L) && (p->data>q->data) p=p->prior； q->prior->next=r；(1) ______； q->next=p->next；q->prior=p； (2) ______；(3) ______； q=r；p=q->prior； (4) ______； } } 【北京理工大学 1999 第二部分 数据结构 [7] （8分）】 五、算法设计题 1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两 个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 【北京大学 1998 三、1 （5分）】 类似本题的另外叙述有： （1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 PROCEDURE merge(ha,hb); （2）已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。写出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。【燕山大学 1998 五 （20分）】 2. 图（编者略）中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学 1992 二 （15分）】 类似本题的另外叙述有： (1) 已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪B【合肥工业大学 1999 五、1（8分）】 （2）已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学 2001 六（10分）】 （3）设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法（即L1∩L2）。要求结果链表仍是从小到大排序，但无重复元素。【南京航空航天大学 1996 十一（10分）】