数据结构复习3.docx
《数据结构复习3.docx》由会员分享,可在线阅读,更多相关《数据结构复习3.docx(29页珍藏版)》请在冰点文库上搜索。
数据结构复习3
一选择题
1.下述哪一条是顺序存储结构的优点?
()
A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示
2.下面关于线性表的叙述中,错误的是哪一个?
()
A.线性表采用顺序存储,必须占用一片连续的存储单元。
B.线性表采用顺序存储,便于进行插入和删除操作。
C.线性表采用链接存储,不必占用一片连续的存储单元。
D.线性表采用链接存储,便于插入和删除操作。
3.线性表是具有n个()的有限序列(n>0)。
A.表元素B.字符C.数据元素D.数据项E.信息项
4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用()存储方式最节省时间。
A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表
5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表
6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用()最节省时间。
A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表
7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用()存储方式最节省运算时间。
A.单链表B.双链表C.单循环链表D.带头结点的双循环链表
8.静态链表中指针表示的是().
A.内存地址B.数组下标C.下一元素地址D.左、右孩子地址
9.链表不具有的特点是()
A.插入、删除不需要移动元素B.可随机访问任一元素
C.不必事先估计存储空间D.所需空间与线性长度成正比
10.下面的叙述不正确的是()
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.顺序循环
12.
(1)静态链表既有顺序存储的优点,又有动态链表的优点。
所以,它存取表中第i个元素的时间与i无关。
(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。
(3)静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
以上错误的是()
A.
(1),
(2)B.
(1)C.
(1),
(2),(3)D.
(2)
13.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=i<=n+1)。
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)
15.线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为()
A.O(i)B.O
(1)C.O(n)D.O(i-1)
16.非空的循环单链表head的尾结点p↑满足()。
A.p↑.link=headB.p↑.link=NILC.p=NILD.p=head
17.循环链表H的尾结点P的特点是()。
A.P^.NEXT:
=HB.P^.NEXT:
=H^.NEXTC.P:
=HD.P:
=H^.NEXT
18.在一个以h为头的单循环链中,p指针指向链尾的条件是()
A.p^.next=hB.p^.next=NILC.p^.next.^next=hD.p^.data=-1
19.完成在双循环链表结点p之后插入s的操作是();
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所指向的新结点,其修改指针的操作是()。
注:
双向链表的结点结构为(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
22.双向链表中有两个指针域,llink和rlink,分别指回前驱及后继,设p指向链表中的一个结点,q指向一待插入结点,现要求在p前插入q,则正确的插入为()
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的结点操作是()。
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;
25.对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是()
A.head==NULLB.head→next==NULLC.head→next==headD.head!
=NULL
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;
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都不对。
二、判断
1.链表中的头结点仅起到标识的作用。
()
2.顺序存储结构的主要缺点是不利于插入或删除操作。
()
3.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。
()
4.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。
()
5.对任何数据结构链式存储结构一定优于顺序存储结构。
()
6.顺序存储方式只能用于存储线性结构。
()
7.集合与线性表的区别在于是否按关键字排序。
()
8.所谓静态链表就是一直不发生变化的链表。
()
9.线性表的特点是每个元素都有一个前驱和一个后继。
()
10.取线性表的第i个元素的时间同i的大小有关.()
11.循环链表不是线性表.()
12.线性表只能用顺序存储结构实现。
()
13.线性表就是顺序存储的表。
()
14.为了很方便的插入和删除数据,可以使用双向链表存放数据。
()
15.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
()
16.链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高。
()
三、填空
1.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用_______存储结构。
2.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是________。
3.设单链表的结点结构为(data,next),next为指针域,已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点,若将结点y插入结点x之后,则需要执行以下语句:
_______;______;
4.在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动________个元素。
5.在单链表中设置头结点的作用是________。
6.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________
7.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成________和_______;而又根据指针的连接方式,链表又可分成________和________。
8.在双向循环链表中,向p所指的结点之后插入指针f所指的结点,其操作是_______、_______、_______、________。
9.在双向链表结构中,若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:
s^.next:
=p;s^.prior:
=________;p^.prior:
=s;________:
=s;
10.链接存储的特点是利用________来表示数据元素之间的逻辑关系。
11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
12.对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个,单链表为_______个。
13.循环单链表的最大优点是:
________。
14.已知指针p指向单链表L中的某结点,则删除其后继结点的语句是:
________
15.带头结点的双循环链表L中只有一个元素结点的条件是:
________
16.在单链表L中,指针p所指结点有后继结点的条件是:
__
17.带头结点的双循环链表L为空表的条件是:
________。
18.在单链表p结点之后插入s结点的操作是:
_______。
19.请在下列算法的横线上填入适当的语句。
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;
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;
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;
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}
24.已知双链表中结点的类型定义为:
TYPEdpointer=^list;
list=RECORD
data:
integer;left,right:
dpointer;
END;
如下过程将在双链表第i个结点(i>=0)之后插入一个元素为x的结点,请在答案栏给出题目中______处应填入的语句或表达式,使之可以实现上述功能。
PROCEDUREinsert(VARhead:
dpointer;i,x:
integer);
VARs,p:
dpointer;j:
integer;
BEGIN
new(s);s^.data:
=x;
IF(i=0)THENBEGINs^.right:
=head;
(1)___head:
=sEND{如果i=0,则将s结点插入到表头后返回}
ELSEBEGINp:
=head;
(2)_______;{在双链表中查找第i个结点,由p所指向}
WHILE((p<>NIL)AND(j
=j+1;(3)_END;
IFp<>NILTHEN
IF(p^.right=NIL)
THENBEGINp^.right:
=s;s^.right:
=NIL;(4)__END
ELSEBEGINs^.right:
=p^.right;(5)_;p^.right:
=s;(6)END
ELSEwriteln(‘cannotfindnode!
’)
END
END;
25.阅读以下算法,填充空格,使其成为完整的算法。
其功能是在一个非递减的顺序存储线性表中,删除所有值相等的多余元素。
CONSTmaxlen=30
TYPEsqlisttp=RECORD
elem:
ARRAY[1..maxlen]OFinteger;
last:
0..maxlen
END;
PROCexam21(VARL:
sqlisttp);
j:
=1;i:
=2;
WHILE
(1)______DO
[IFL.elem[i]<>L.elem[j]THEN[
(2)_______;(3)______];
i:
=i+1]
(4)________;
ENDP;
】
27.对于给定的线性链表head,下面的程序过程实现了按结点值非降次序输出链表中的所有结点,在每次输出一个结点时,就把刚输出的结点从链表中删去。
请在划线处填上适当的内容,使之成为一个完整的程序过程,每个空框只填一个语句。
TYPEnodeptr=^nodetype;
nodetype=RECORD
data:
integer;link:
nodeptr
END;
VARhead:
nodeptr;
PROCEDUREsort_output_delete(head:
nodeptr);
VARp,q,r,s:
nodeptr;
BEGINWHILEhead<>NILDO
BEGINp:
=NIL;q:
=head;r:
=q;s:
=q^.link;
WHILEs<>NILDO
BEGINIFs^.data(1)__;
(2)___END;
r:
=s;(3)___
END;
write(q^.data:
5);
IFp=NILTHEN(4)___ELSE(5)____;
dispose(q);
END;
writeln
END;
28.下面函数的功能是在一个按访问频度不增有序的,带头结点的双向链环上检索关键值为x的结点,对该结点访问频度计数,并维护该链环有