第2章线性表 205 501 20 5 781 17 6 6 910 24 表元编号 数量 元阿联系 618 5 781 6 910 24 供选择的答案： A,连续B,单向链接C.双向链接D.不连接E循环链接 .网状H.随机L顺 循 静态 的 表的优点 它存取表中第个元素的时间与无关 三去 后不能增加。 以上错误的是( )【南京理工 大学2000 时需做元素的移动。 31.5分)】 人若长度品的线表采限存结的。关希位宜据入-个新元素的算法的时间复杂度为(）c=K=+.【比 1 (2 京航空航天大学1999一、1(2分)】 0.0n2 14.对于顺序存储的线性表」 访问结点和增加 删除结点的时间复杂度为()。 .0h)0a) c.0a)0)D.0)0) 【青岛大学2000五、1(2分)】 15.线性表(al,2,.,an)以链接方式存储时，访问第位置元素的时间复杂性为() A.0(iDB.0(1)C.0(n) D.0(1)【中山大学1999一、2】 16.非空的循环单链表hed的尾结点p1满足()。【武汉大学2000二、10】 A.p↑.mk=head B.p↑.lmk=Nl C.p=N IL D.p=head 循环链表H的尾结点P的特点是()。【中山大学1998二、2(2分)】 A NEXT=H PHD·P=H 在 个以h为头的单循环链中，p指针指向链尾的条件是()【南京理工大学198一、15(2分)】 p 完成在双循环链表结点D之后插入 D.p e D.p 9 操作 【北方交通大学1999一、4(3分)】 .proou-p:p .prou=s;s .next=p u-s,p .hext-s. orou=p:s .next=p .next .prou- 在双同循环链表中在指针所指向的结监前插个指针所指向的新结点，其修改指针的操作是()。【北京邮电大学 1998二、2(2分)】 注双向链表的结点结构为(mk,da血，rmk)。供选择的答案： A.p↑.k:=q:gt.rlnk:=D pt.link↑.rink:=q:q↑.k:=q pt.llink:=q:pf.mk↑rik:=q；q↑rk:=p: q↑.ik=p↑.nk: q↑rimk:=p:q↑.nk:=p↑.k:p↑.lnk↑，k:=q;p↑.ink:=q; q↑.nk=p↑.k:q↑k=p:p↑.nk:=q:p↑.k:=q:(编者按：原题如此) 在非空双向循环链表中q所指的结点前插入一个由即所指的链结点的过程依次为： rlink (p) q:lmkp)←mkq):imkq)←p:( rlnk (llink (p))-p D.rlnk(rlink (p))+-p 22 ]链表中有两个指针域 k和ik,分别指回前驱及后继，设p指向链表中 一个结点，q指向一待插入结点，现要求 ht/%.con /oran/docum/t02.h加（第2/17页）2010-4-511004
第2章 线性表 2 205 2 1 3 103 15 4 4 501 20 0 5 781 17 6 6 910 24 3 表元编号 货号 数量 表元间联系 1 2 1 618 40 5 2 2 205 2 1 0 3 103 15 4 6 4 501 20 0 3 5 781 17 6 1 6 910 24 3 5 表4 s→ 供选择的答案： A.连续 B.单向链接 C.双向链接 D.不连接 E.循环链接 F.树状 G.网状 H.随机 I.顺序 J.顺序循环 【上海海运学院 1995 二、1（5分）】 12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ ）【南京理工大学 2000 一、3（1.5分）】 A．（1），（2） B．（1） C．（1），（2）,(3) D.（2） 13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。【北 京航空航天大学 1999 一、1（2分）】 A. O(0) B. O(1) C. O(n) D. O(n2) 14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 【青岛大学 2000 五、1（2分）】 15．线性表（ a1,a2,.,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1）【中山大学 1999 一、2】 16．非空的循环单链表head的尾结点p↑满足（ ）。【武汉大学 2000 二、10】 A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head 17．循环链表H的尾结点P的特点是（ ）。【中山大学 1998 二、2（2分）】 A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT C．P:=H D．P:=H^.NEXT 18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ ）【南京理工大学1998 一、15（2分）】 A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1 19．完成在双循环链表结点p之后插入s的操作是（ ）；【北方交通大学 1999 一、4（3分）】 A． p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next; B． p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next; C． s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ; D． s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s; 20．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。【北京邮电大学 1998 二、2（2分）】 注:双向链表的结点结构为(llink,data,rlink)。 供选择的答案： A． p↑.llink：=q； q↑.rlink：=p； p↑.llink↑.rlink：=q； q↑.llink：=q； B． p↑.llink：=q； p↑.llink↑.rlink：=q ； q↑.rlink：= p； q↑.llink:=p↑.llink； C． q↑.rlink：=p； q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q; p↑.llink：=q; D． q↑.llink:=p↑.llink；q↑.rlink:=p； p↑.llink：=q；p↑.llink：=q；（编者按：原题如此） 21．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为: rlink(p) ← q; llink(p) ← llink(q); llink(q) ← p; （ ） A．rlink(q) ← p B．rlink(llink(q)) ← p C．rlink(llink(p)) ← p D．rlink(rlink(p)) ← p 【北京航空航天大学 2000 一、1（2分）】 22． 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 2／17 页）2010-4-15 11:00:46
第2章线性表 在p前插入 ,则正确的插入为()【南京理工大学1996 ,1(2分)】 link'.rlink=q:q .rlnk:=p:pik=g”rik :p”rk=q:p.ik.rlhk=q:gnk D.p".IInk".rlnk=q:q".rlnk=p:q".Wlink=p".lnk:p".Ink=q 23.在双向链表指针p的结点前插入一个指针g的结点操作是()。【青岛大学2000五、2(2分)】 A.p->LInk=qn->Rlnk=pp->Llink->R link=qn->Llnk=q: B.p>Llink=qp->Llink->R Ink=q>R lnk=pn>Llink=p->Llink; C.q->R link=pn>LInk=p->LInkp->Llink->R link=qp->Llnk=q: q>Llink=p-> R Ik=qp->LInk=qp->Llk=q; 2 在单链表指针为的结点之后插入指针为s的结点，正确的操作是：()。 p->nextss>next=p->next;B.s>nextp->nextp->nexts D.p->nexes>nextp->nexes 不指针为 的带头结点的单链表，判定该表为空表的条件是() C hea nex ad D head =NULI 言丁商大学2001 双向链表存储结构中，删除所指的结点时须修改指针()。 ".Ulnk) .Unk=(p.k).Dink ()rlink=p (p".rlink).Ilnk=p p".rlnk=(p.rlink).rlink p".rlnk=(p".llnk)".Ilink p".Ilnk=(p".rlnk)".rlnk 【西安电子科技大学1998一 ,1(2分)】 27.双向链表中有两个指针域，k和nk分别指向前趋及后继，设p指向链表中的一个结点，现要求刑去p所指结点，则正确 的删除是( (链中结点数大于2，p不是第一 个结点) A.p".Ilnk .rlink=p hk;p.hk .rlink=p dipose(p);p.llnk".rlink=p".Ilink:p".Ilnk ,rlnk=p .rlink r p B,C都不对。 【南京理工大学199 判 裤岁中的斗结占仅起标识的作用 （)【南言航空航天大受17一1(1分)】 2顺序存储结构的主要缺 占是不利干插入成刷 ()【南京航空航天大学1997 一、2(1分)】 3。线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。 【北京邮电大学1998 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。() 【北京邮电大学2002 2(1分)】 .对任何数据结构链式存储结构 定优于顺序存储结构。()【南京航空航天大学1997 一、3(1分)】 5. 顺序存储方式只能用于存储线性结构。 【中科院软件所1999六 ,1-2(2分)】【上海海运学院1997 1(1分)】 集合与线性表的区别在于是否按关键字排序。（)【大连海事大学2001一、5(1分)】 直不发生变化的链表。()【合肥工业大学2000 1(1分)】 的特点是每 素的秀都有 后 【合 工业大学2001 (1分)】 ￥1997二、9(2分)】 存储结术 【青岛大学2001四 【者岛大￥200 (1分)】 是顺序存 11分) 很方便的插入除数据， 可以使用双向链表存放数据 【上洋 2(1分)】 15.顺序存储方式的优点是存储密度大，且插入、除运算效率高。 【上海海运学院1996一、1(1分)】【上海海运学院1999 1(1分)】 16链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（)【上海海运学院 1998一、2(1分)】 一·性表的元素总数基本稳定，且根少注行插人和别除提作，但要求以最快的速度存取线性衣中的元素时，应采用 填空 h电/w.biiong.oon加M 1 entaoyan/使502h加（第3/17页）2010-4曰511046
第2章 线性表 在p前插入q，则正确的插入为（ ）【南京理工大学1996 一、1（2分）】 A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink; B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink; C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p; D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q; 23．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。【青岛大学 2000 五、2（2分）】 A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; 24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 【青岛大学 2001 五、3（2分）】 25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 【北京工商大学 2001 一、5（3分）】 26. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink; B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p; C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink; 【西安电子科技大学 1998 一、1（2分）】 27. 双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确 的删除是（ ）（链中结点数大于2，p不是第一个结点） A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p); B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink; C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink; D．以上A，B，C都不对。 【南京理工大学 1997 一、1（2分）】 二、判断 1. 链表中的头结点仅起到标识的作用。( )【南京航空航天大学 1997 一、1（1分）】 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )【南京航空航天大学1997 一、2（1分）】 3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 【北京邮电大学 1998 一、2（2分）】 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 【北京邮电大学 2002 一、2（1分）】 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 一、3（1分）】 6．顺序存储方式只能用于存储线性结构。( ) 【中科院软件所 1999 六、1-2（2分）】【上海海运学院 1997 一、1（1分）】 7．集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5 ( 1分)】 8. 所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 2000 二、1（1分）】 9. 线性表的特点是每个元素都有一个前驱和一个后继。( )【合肥工业大学2001 二、1（1分）】 10. 取线性表的第i个元素的时间同i的大小有关. ( )【南京理工大学 1997 二、9（2分）】 11. 循环链表不是线性表. ( )【南京理工大学 1998 二、1（2分）】 12. 线性表只能用顺序存储结构实现。( )【青岛大学 2001 四、2（1分）】 13. 线性表就是顺序存储的表。( )【青岛大学 2002 一、1（1分）】 14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( ) 【上海海运学院 1995 一、1（1分）】 【上海海运学院 1997 一、2（1分）】 15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 【上海海运学院 1996 一、1（1分）】 【上海海运学院 1999 一、1（1分）】 16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 【上海海运学院 1998 一、2（1分）】 三、填空 1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 3／17 页）2010-4-15 11:00:46
第2章线性表 2线性储结枸 【北方交 大 学2001 4】 通大学用 假定删除表中任一元素的概率相同，则刷除 一个元素平均需要移动元素的个数是 【北 9 伪指针域，己知指针px指向单链表中daa为x的结点，指针py指向daa为y的新结点 需要执行以下 五与 个长度为的面序表中第个元素 (1<==)之前插入一个元素时，需向后移动 个元者 在单链表中设置头结点的作用是 【哈尔滨工业大学2000二、1(1分)】 对干 个具有个结点的单链表，在已知的结点物p后插入一个新结点的时间复杂度为 _,在给定值为x的结点后插入 个新结点的时间复杂度为 【哈尔滨工业大学2001一、1(2分)】 7.根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 和 ：而又根据指针的连接方 式，连表义可分分成 【西安电子利料技大字1998一 4(3分)】 在双向循环链表中，向所指的结点之后插入指针所指的结点，其操作是] 。【中国 业大 03) 9,在双向链表结构中，若要求在印指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： ；p.pDr=S FS (福州接存储 序存储结 特点是分刀】 来一 之间的 【中山大学199 1(1分)】 表示元素之间的 关系的 式存储结构是通过 2001 表示元素之间的关系的。【北京理工大 12.对于双向链表，在两个结点之间插入 个新结点需修改的指针共 个，单链表为 个 3分)】 13.循环单链表的最大优点是 【福州大学1998 3包分)】 .已知指针D指向单链表L中的某结点，则删除其后继结点的语句是： 【合肥工业大学1999 (2分)】 15 ,带头结点的双循环链表L中只有 一个元素结点的条件是： 【合肥工业大学1999 32000 22) 16.在单链表L中，指针所指结点有后继结点的条件是： 【合肥工业大学2001三、3(2分)】 17带头结点的双循环链表L为空表的条件是： 北泉理山 大学2000 (2分) 】【青岛大学2002三 ,1(2分)】 、字2002 法的横 【青 2(2分)】 句 【清华大学1994五(15分)】 为 指针的 连表分别表示有序表A和B,本算法判别表A是否包含在表B内，若是，则返回“u”,否则返 回“e”】 BEG N =hh .next:(1) IF padata=pbdata TH EN (3)ELSE (4): (5) END- 20.完善算法：己知单链表结点类型为： TYPE pt=node: node=record data:nteger:next:ptr END: 过程ceae建立以head为头指针的单链表。 ae（)H BEG:PU: k:nteger (head) W HLEK>ODO q=head;read (k) BEG IN nDm/使02h加（第4/17页）2010-451104
第2章 线性表 _存储结构。【北方交通大学 2001 二、4】 2．线性表L=（a1,a2,.,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 _。【北方交通大学 2001 二、9】 3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_； _;【华中理工大学 2000 一、4（2分）】 4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_个元素。 【北京工商大学 2001 二、4（4分）】 5．在单链表中设置头结点的作用是_。【哈尔滨工业大学 2000 二、1（1分）】 6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_,在给定值为x的结点后插入一 个新结点的时间复杂度为_。【哈尔滨工业大学 2001 一、1（2分）】 7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_；而又根据指针的连接方 式，链表又可分成_和_。【西安电子科技大学1998 二、4（3分）】 8． 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_、_、_、_。【中国 矿业大学 2000 一、1（3分）】 9. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句： s^ .next:=p； s^ .prior:= _；p^ .prior:=s；_:=s； 【福州大学 1998 二、7 (2分)】 10．链接存储的特点是利用_来表示数据元素之间的逻辑关系。【中山大学 1998 一、1 （1分）】 11.顺序存储结构是通过_表示元素之间的关系的;链式存储结构是通过_表示元素之间的关系的。【北京理工大 学 2001 七、2 （2分）】 12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。 【南京理工大学 2000 二、2 （3分）】 13. 循环单链表的最大优点是：_。【福州大学 1998 二、3 (2分)】 14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_ 【合肥工业大学 1999 三、2 （2分）】 15. 带头结点的双循环链表L中只有一个元素结点的条件是：_ 【合肥工业大学 1999 三、3 2000 三、2（2分）】 16. 在单链表L中，指针p所指结点有后继结点的条件是：_ 【合肥工业大学 2001 三、3 （2分）】 17.带头结点的双循环链表L为空表的条件是：_。 【北京理工大学 2000 二、1 （2分）】 【青岛大学 2002 三、1 （2分）】 18. 在单链表p结点之后插入s结点的操作是：_。【青岛大学 2002 三、2（2分）】 19. 请在下列算法的横线上填入适当的语句。【清华大学 1994 五 （15分）】 FUNCTION inclusion(ha,hb:linklisttp):boolean; {以ha和hb为头指针的单链表分别表示有序表A和B，本算法判别表A是否包含在表B内，若是，则返回“true”，否则返 回“false”} BEGIN pa:=ha^.next; pb:=hb^.next; （1） ; WHILE（2） DO IF pa^.data=pb^.data THEN（3） ELSE（4） ; （5） END; 20．完善算法：已知单链表结点类型为： TYPE ptr=^node； node=RECORD data：integer； next：ptr END； 过程create建立以head为头指针的单链表。 PROCEDURE create ( (1) )； VAR p,q：ptr； k：integer； BEGIN new（head）； q:=head；read（k）； WHILE k>0 DO BEGIN (2); (3); (4); (5); read（k） END; http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 4／17 页）2010-4-15 11:00:46
第2章线性表 D北范大学19三】 21.己给如下关于单链表的类型说明： TYPE lit=node node=RECO RD data:nteger:next:list: END 以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分 别为pq. PRO CEDURE m ergelink(VAR p.q:list): VAR h,r:list: BEG N -NI THEN BEG NN ELSE BEG IN _r=p:p=p.next F (p=N IL)TH EN r'.next=q; q:q=q".next:EN D (45 p=h.next:dispose(h): END:【厦门大学2000三、2(8分)】 22.假设链表即和链表q中的结点值都是整数，且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的 值为mr,且链表中其他结点的值都小于max,在程序中取max为9999。在各个链表中，每个结点的值各不相同，但链表p和链表 可能有值相同的结点（表头结点除外） 下面的程序将链表q合并到链表即中，使得合并后的链表是按结点值递增次序链接起 来的带表头 的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达 式，链表的结点类型如下 etype: dat:nteger:lnk:nodeptr: END PROCEDU =9999 erge(VAR pnodepn nodept): VAR r.s:nodeptr: BEG N W H ILE (A)DO BEG IN W H ILE r'.link'.data<q".link'.data DO (B) IF r .hk .da妇>q.nk.data TH EN BE s=C)D)=s.link:s.Iink=();()=s:(G);EN D ELSE BEG N )k:():dipos END END; 1p0 大学1997五(18分)】 算法在表中第个元素之前插入元素 0) 指针初始化 计数 =(4 得找第1个结 FD=NL)0R(⑤)】 TH EN enor 'No thisposition') ELSE [new(;s↑.daa=b:st.next=p↑.next:p↑next=sJ ENDP:ms1ikst【燕山大学1998四、1(15分)】 24.已知双链表中结点的类型定义为： ht电w.biiong.oon加 m付caum en taocan/使02.h加（第5/17页）2010-4-曰5110046
第2章 线性表 q^.next：=NIL; END;【北京师范大学 1999 三】 21. 已给如下关于单链表的类型说明： TYPE list=^node ; node=RECORD data: integer; next: list; END; 以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（ 升序），这里两链表的头指针分 别为p和q. PROCEDURE mergelink(VAR p,q:list): VAR h,r: list; BEGIN （1）_ h^.next:= NIL; r:=h; WHILE((p<>NIL) AND (q<>NIL)) DO IF (p^.data<=q^.data) THEN BEGIN （2）_； r:=p; p:=p^.next； END ELSE BEGIN （3）_； r:=q; q:=q^.next; END; IF (p=NIL) THEN r^.next:=q; （4）_； p:=h^.next; dispose(h); END;【厦门大学 2000 三、2 （8分）】 22．假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的 值为max,且链表中其他结点的值都小于max，在程序中取max为9999。在各个链表中，每个结点的值各不相同，但链表p和链表 q可能有值相同的结点（表头结点除外）。下面的程序将链表q合并到链表p中，使得合并后的链表是按结点值递增次序链接起 来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达 式，链表的结点类型如下 TYPE nodeptr=^nodetype； nodetype=RECORD data：integer； link：nodeptr; END； CONST max=9999; PROCEDURE merge(VAR p:nodeptr;q:nodeptr); VAR r,s: nodeptr; BEGIN r:=p; WHILE (A)_ DO BEGIN WHILE r^.link^.data<q^.link^.data DO (B)_; IF r^.link^.data>q^.link^.data THEN BEGIN s:=(C)_; (D)_:=s^.link; s^.link:=(E)_; (F)_ _:=s; (G)_; END ELSE BEGIN (H)_; s:=q^.link; (I)_; dispose(s) END END; dispose(q) END;【复旦大学 1997 五 （18分）】 23．PROC ins_linklist(la:linkisttp; i:integer; b:elemtp); {la为指向带头结点的单链表的头指针，本算法在表中第i个元素之前插入元素b} p:=(1) ; j:=(2) ;{指针初始化，j为计数器} WHILE (p<>NIL) AND ((3) ) DO [p:=(4) ; j:=j+1；] {寻找第 i-1 个结点} IF (p=NIL) OR ((5) ) THEN error (‘No this position’) ELSE [new(s) ; s↑.data:=b; s↑.next:=p↑.next; p↑.next:=s;] ENDP;{ins-linklist}【燕山大学 1998 四、1（15分）】 24. 已知双链表中结点的类型定义为： http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 5／17 页）2010-4-15 11:00:46
第2章线性表 in teger:eft,righ tdpo in er 如下过程将在双链表第个结点（=0）之后插入一个元素为x的结点，请在答案栏给出题目中处应填入的语句或表达 式，使之可以实现上述功能 PRO CEDU RE insertV AR head pointerix:in teger); VAR sp dpointer:iinteger: BEG I new(s):s.data=x F(住O)TH EN BEG IN s,iht=head:)head=sEND如果主O,则将结点插入到表头后返回} ELSE BEG IN p=head;② :在双链表中查找第个结点，由所指向} WHLE(p<>NL)AND()D0BEGN=子1：③)_END: Fp<>N s'.right=p pi动t=s:⑥END END:【厦门大学2002二(12分)】 读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，刷除所有值相等的多余 CON ST maxln=30 TYPE sqlisttp=RECORD ekm ARRA Y [1.m ax en]0 F integer asto.m ax en END: PRO C exam 21 (V AR Ls listtp): 1:e2 W H LE (1) _DO 10分)】 的程序中 nkst)建立一个具有n个结点的环形链表程序过程p s,im)对由C ate link_list 的目有 的环 定的次序 深个给出并 结 参数 指明从起始结 成前次被删除 结之后的第 人结点作为 本次被输出并除的结点。例，。对于图中具有个结点的环形链表，在调用即us63.2后，将输出13,42请在横线 →0 处填上适当内容，每空只填一个语句。 TYPE nodepu RECO RD E nodept END: FUNCTON CR .th e lnk list(n:nteger):nodeptr: VAR head,pq:nodeptr:iin teger: ht电.con /au/oran ocum/02h加（第6/17页）2010-4-5104E
第2章 线性表 TYPE dpointer=^list; list=RECORD data:integer; left,right:dpointer; END; 如下过程将在双链表第i个结点（i>=0）之后插入一个元素为x的结点，请在答案栏给出题目中_处应填入的语句或表达 式，使之可以实现上述功能。 PROCEDURE insert(VAR head:dpointer;i,x:integer); VAR s,p:dpointer; j: integer; BEGIN new(s); s^.data:=x; IF(i=0)THEN BEGIN s^.right:=head; (1)_ head:=s END{如果i=0,则将s结点插入到表头后返回} ELSE BEGIN p:=head; (2)_；{在双链表中查找第i个结点,由p所指向} WHILE ((p<>NIL) AND (j<i)) DO BEGIN j:=j+1; (3) _ END; IF p<>NIL THEN IF （p^.right=NIL） THEN BEGIN p^.right:=s; s^.right:=NIL; (4) _END ELSE BEGIN s^.right:=p^.right; (5) _;p^.right:=s; (6) END ELSE writeln(‘can not find node!’) END END;【厦门大学 2002 二 （12分）】 25．阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余 元素。 CONST maxlen=30 TYPE sqlisttp=RECORD elem:ARRAY[1.maxlen] OF integer; last:0.maxlen END; PROC exam21(VAR L:sqlisttp); j:=1; i:=2; WHILE (1)_ DO [ IF L.elem[i]<>L.elem[j] THEN [ (2)_; (3)_]; i:=i+1 ] (4) _; ENDP;【同济大学 2000 二、1 (10分)】 26．在本题的程序中，函数过程Create_link_list(n)建立一个具有n个结点的环形链表;程序过程 josephus(n,i,m)对由Create_link_list (n)所建立的具有n个结点的环形链表按一定的次序逐个输出并删除链表中的所有结点，参数 n(n>0)指明环形链表的结点个 数，参数 i(1<=i<=n)指明起始结点，参数 m (m>0)是步长，指明从起始结点或前次被删除并输出的结点之后的第m个结点作为 本次被输出并删除的结点。例如，对于下图中具有6个结点的环形链表，在调用 josephus(6,3,2)后，将输出 5,1,3,6,4,2 请在横线 处填上适当内容，每空只填一个语句。 TYPE nodeptr=^nodetype; nodetype=RECORD data: intrger; link: nodeptr END; VAR n,i,m: integer; FUNCTION Create_link_list(n: integer): nodeptr; VAR head,p,q: nodeptr; i:integer; http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/shiti/st02.htm（第 6／17 页）2010-4-15 11:00:46