【合肥工业大学1999三、2(2分)】 15.带头结点的双循环链表L中只有一个元素结点的条件是: 【合肥工业大学1999三、32000三、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 WHILE (2) DO IF pa. data=pb. data thEn(3) ELSE (4 (5) END 20.完善算法:已知单链表结点类型为: TYPE ptr= node node=RECORD data: integer: next ptr 过程 create建立以head为头指针的单链表 PROCEdURE create((1)) VAR p, g: ptr; k: integer; BEGIN new(head): q: =head: read (k) WhILE K>O DO BEGIN q. next: =NIL END,【北京师范大学1999三 21.已给如下关于单链表的类型说明: TYPE list= node node=RECORD data: integer: next: list 以下程序采用链表合并的方法,将两个已排序的单链表合并成一个链表而不改变其排序性 (升序),这里两链表的头指针分别为p和q PROCEDURE mergelink(VAR p, g: list)
【合肥工业大学 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; 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 NIL: WHILE ((p<>NIL) AND(gNIL)) DO IF (p. data<=q. data THEn BEGIN(2): r: =p: p: =p. next: END ELSE BEGIN (3) r:=g:g: =q. next: END; IF (p=NIL) THEN r. next: =g =h. next: dispose(h) END;【厦门大学2000三、2(8分)】 22.假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结 点的环形链表。各链表的表头结点的值为max,且链表中其他结点的值都小于max,在程序中 取max为9999。在各个链表中,每个结点的值各不相同,但链表p和链表q可能有值相同 的结点(表头结点除外)。下面的程序将链表q合并到链表p中,使得合并后的链表是按结 点值递增次序链接起来的带表头结点的环形链表,且链表中各个结点的值各不相同。请在划 线处填上适当内容,每个框只填一个语句或一个表达式,链表的结点类型如下 TYPE nodeptr= node type; nodetype=RECORD data: integer: link: nodepti CONST max=9999 PROCEDURE merge(var p: nodeptr: q: nodeptr) VAR r, s BEGIN WHILE (A) 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: =g. link: (I) dispose (s)END END END;【复旦大学1997五(18分)】 23. PROC ins linklist(la: linkisttp: i: integer; b: elemtp) 1a为指向带头结点的单链表的头指针,本算法在表中第i个元素之前插入元素b} p:=(1) 指针初始化,j为计数器} WHILE (p>NIL) AND ((3))DO [p: =(4 寻找第i-1个结点} IF (p=NIL) OR((5) THEN error(‘ No this position'’)
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.已知双链表中结点的类型定义为: TYpE pointer= list list=RECORD data: integer: left, right: dpo 如下过程将在双链表第i个结点(i>=0)之后插入一个元素为x的结点,请在答案栏给出题 目中 处应填入的语句或表达式,使之可以实现上述功能。 PROCEDURE insert(VAR head: pointer: i, x:integer) new(s): s. data:=x IF(i=0) THEN BEGIN S. right:=head;()head:=sEND{如果i=0,则将s结点插 入到表头后返回} ELSE BEGIN p:=head;(2):{在双链表中查找第i个结点,由p所指向 WHILe ((pONIL) AND (j<i)) DO bEGin j: =j+1: (3) END IF PONIL 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;【厦门大学2002二(12分)】 25.阅读以下算法,填充空格,使其成为完整的算法。其功能是在一个非递减的顺序存储线 性表中,删除所有值相等的多余元素。 CONST maxlen=30 TYPE sqlisttp=RECORD elem: ARRAY[l. maxlen] OF integer last: 0.. maxlen PROC exam21(VAR L: sqlisttp WHILE (1) IF L elem[i]<>L elem [j] THEN (3)] +1 ENDP;【同济大学2000二、1(10分)】 26.在本题的程序中,函数过程 Create_link_list(m)建立一个具有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请在横线处填上适当内容
ELSE [new(s) ; s↑.data:=b; s↑.next:=p↑.next; p↑.next:=s;] ENDP;{ins-linklist}【燕山大学 1998 四、1（15 分）】 24. 已知双链表中结点的类型定义为： 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 请在横线处填上适当内容