第二章 线性表.docx
《第二章 线性表.docx》由会员分享，可在线阅读，更多相关《第二章 线性表.docx（103页珍藏版）》请在冰点文库上搜索。
第二章线性表
第2章线性表
一选择题
1．下述哪一条是顺序存储结构的优点？
（）【北方交通大学2001一、4（2分）】
A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示
2．下面关于线性表的叙述中，错误的是哪一个？
（）【北方交通大学2001一、14（2分）】
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（）的有限序列（n>0）。
【清华大学1998一、4（2分）】
A．表元素B．字符C．数据元素D．数据项E．信息项
4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
【哈尔滨工业大学2001二、1（2分）】
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
【南开大学2000一、3】
A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。
A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表
【合肥工业大学2000一、1（2分）】
7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用（）存储方式最节省运算时间。
【北京理工大学2000一、1（2分）】
A．单链表B．双链表C．单循环链表D．带头结点的双循环链表
8.静态链表中指针表示的是（）.【北京理工大学2001六、2（2分）】
A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址
9.链表不具有的特点是（）【福州大学1998一、8（2分）】
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
10.下面的叙述不正确的是（）【南京理工大学1996一、10（2分）】
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B.线性表在链式存储时，查找第i个元素的时间同i的值无关
C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比
D.线性表在顺序存储时，查找第i个元素的时间同i的值无关
11.线性表的表元存储方式有（
（1））和链接两种。
试指出下列各表中使用的是何种存储方式：
表1是（
（2））存储方式；表2是（（3））存储方式；表3是（（4））存储方式；表4是（（5））存储方式。
表左的s指向起始表元。
表元编号
货号
数量
表元间联系
1
618
40
2
2
205
2
3
3
103
15
4
4
501
20
5
5
781
17
6
6
910
24
0
表1
s→
表元编号
货号
数量
表元间联系
1
618
40
5
2
205
2
1
3
103
15
4
4
501
20
2
5
781
17
6
6
910
24
3
表2
s→
表元编号
货号
数量
表元间联系
1
618
40
5
2
205
2
1
3
103
15
4
4
501
20
0
5
781
17
6
6
910
24
3
表3
s→
表元编号
货号
数量
表元间联系
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=headB．p↑.link=NILC．p=NILD．p=head
17．循环链表H的尾结点P的特点是（）。
【中山大学1998二、2（2分）】
A．P^.NEXT:
=HB．P^.NEXT:
=H^.NEXTC．P:
=HD．P:
=H^.NEXT
18．在一个以h为头的单循环链中，p指针指向链尾的条件是（）【南京理工大学1998一、15（2分）】
A.p＾.next=hB.p＾.next=NILC.p＾.next.＾next=hD.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）←pB．rlink（llink（q））←pC．rlink（llink（p））←pD．rlink（rlink（p））←p
【北京航空航天大学2000一、1（2分）】
22．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在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==NULLB．head→next==NULLC．head→next==headD．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:
=pp^.rlink:
=（p^.rlink）^.rlink
D．p^.rlink:
=（p^.llink）^.llinkp^.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．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
【北方交通大学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三、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分）】
FUNCTIONinclusion（ha,hb:
linklisttp）:
boolean;
{以ha和hb为头指针的单链表分别表示有序表A和B，本算法判别表A是否包含在表B内，若是，则返回“true”，否则返回“false”}
BEGIN
pa:
=ha^.next;pb:
=hb^.next;
（1）;
WHILE
（2）DO
IFpa^.data=pb^.dataTHEN（3）ELSE（4）;
（5）
END;
20．完善算法：
已知单链表结点类型为：
TYPEptr=^node；
node=RECORD
data：
integer；next：
ptr
END；
过程create建立以head为头指针的单链表。
PROCEDUREcreate（
（1））；
VARp,q：
ptr；k：
integer；
BEGIN
new（head）；q:
=head；read（k）；
WHILEk>0DO
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.
PROCEDUREmergelink（VARp,q:
list）:
VARh,r:
list;
BEGIN
（1）______
h^.next:
=NIL;r:
=h;
WHILE（（p<>NIL）AND（q<>NIL））DO
IF（p^.data<=q^.data）
THENBEGIN
（2）___；r:
=p;p:
=p^.next；END
ELSEBEGIN（3）____；r:
=q;q:
=q^.next;END;
IF（p=NIL）THENr^.next:
=q;
（4）__；
p:
=h^.next;dispose（h）;
END;【厦门大学2000三、2（8分）】
22．假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。
各链表的表头结点的值为max,且链表中其他结点的值都小于max，在程序中取max为9999。
在各个链表中，每个结点的值各不相同，但链表p和链表q可能有值相同的结点（表头结点除外）。
下面的程序将链表q合并到链表p中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。
请在划线处填上适当内容，每个框只填一个语句或一个表达式，链表的结点类型如下
TYPEnodeptr=^nodetype；
nodetype=RECORD
data：
integer；link：
nodeptr;
END；
CONSTmax=9999;
PROCEDUREmerge（VARp:
nodeptr;q:
nodeptr）;
VARr,s:
nodeptr;
BEGIN
r:
=p;
WHILE（A）___DO
BEGIN
WHILEr^.link^.dataIFr^.link^.data>q^.link^.data
THENBEGINs:
=（C）_;（D）_:
=s^.link;s^.link:
=（E）_;（F）__:
=s;（G）_;END
ELSEBEGIN（H）__;s:
=q^.link;（I）__;dispose（s）END
END;
dispose（q）
END;【复旦大学1997五（18分）】
23．PROCins__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））
THENerror（‘Nothisposition’）
ELSE[new（s）;s↑.data:
=b;s↑.next:
=p↑.next;p↑.next:
=s;]
ENDP;{ins-linklist}【燕山大学1998四、1（15分）】
24.已知双链表中结点的类型定义为：
TYPEdpointer=^list;
list=RECORD
data:
integer;left,right:
dpointer;
END;
如下过程将在双链表第i个结点（i>=0）之后插入一个元素为x的结点，请在答案栏给
升级会员 