2012年考研数据结构精选试题（五）

　　三、填空

　　1.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以比较快的速度存取线性表中的元素时，应采用_______存储结构。【北方交通大学 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;

　　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

　　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分)】

    考试须知：2012考研时间安排 ♦应试技巧及考场须知 ♦首发2012考研真题

    考前必看：准考证下载入口 ♦2012年考研考场规则 ♦2012考研考场查询

    复习备考：政治时事汇总 必背考点 预测试题 ♦ 英语作文预测 模板大全