数据结构练习第二章线性表.docx

数据结构练习第二章线性表.docx

《数据结构练习第二章线性表.docx》由会员分享，可在线阅读，更多相关《数据结构练习第二章线性表.docx（100页珍藏版）》请在冰点文库上搜索。

数据结构练习第二章线性表

数据结构练习第二章线性表

一、选择题

1.下面关于线性表的叙述错误的是（）。

A.线性表采用顺序存储必须占用一片连续的存储空间

B.线性表采用链式存储不必占用一片连续的存储空间

C.线性表采用链式存储便于插入和删除操作的实现

D.线性表采用顺序存储便于插入和删除操作的实现

2.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。

A.q=p->next；p->data=q->data；p->next=q->next；free（q）；

B.q=p->next；q->data=p->data；p->next=q->next；free（q）；

C.q=p->next；p->next=q->next；free（q）；

D.q=p->next；p->data=q->data；free（q）；

3.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

A.O（n）B.O（nlog2n）C.O

（1）D.O（n2）

4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。

A.O（log2n）B.O

（1）C.O（n2）D.O（n）

5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。

A.head==0B.head->next==0

C.head->next==headD.head!

=0

6．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。

A.head==0B.head->next==0

C.head->next==headD.head!

=0

7．建立一个长度为n的有序单链表的时间复杂度为（）

A.O（n）B.O

（1）C.O（n2）D.O（log2n）

8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。

A.n-iB.n+l-iC.n-1-iD.i

9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。

A.p->right=s；s->left=p；p->right->left=s；s->right=p->right；

B.s->left=p；s->right=p->right；p->right=s；p->right->left=s；

C.p->right=s；p->right->left=s；s->left=p；s->right=p->right；

D.s->left=p；s->right=p->right；p->right->left=s；p->right=s；

10．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。

A.单向链表B.单向循环链表

C.双向链表D.双向循环链表

11．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。

A.s->next=p->next；p->next=-s；B.q->next=s；s->next=p；

C.p->next=s->next；s->next=p；D.p->next=s；s->next=q；

12．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（）个元素。

A．n-iB．n-i+1C．n-i-1D．i

13．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（　　）。

A.q->next=p->next;p->next=q;

B.p->next=q->next;q=p;

C.q->next=p->next;p->next=q;

D.p->next=q->next;q->next=p;

14．在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（　　）

A.直接前趋B.直接后继C.开始结点D.终端结点

15．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（　　　）

A.nB.2n-1C.2nD.n2

16．线性表采用链式存储结构时，要求内存中可用存储单元的地址（）

A.必须是连续的B.必须是部分连续的

C.一定是不连续的D.连续和不连续都可以

17．设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。

执行程序段

p=h;

while（p->next->next!

=h）

p=p->next;

p->next=h;

后（其中，p->next为p指向结点的指针域），则（）

A.p->next指针指向链尾结点B.h指向链尾结点

C.删除链尾前面的结点D.删除链尾结点

18．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为（）

A.236B.239C.242D.245

19．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）

A.5B.6C.7D.9

20．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是（）

A.p→llinkB.p→rlink

C.p→llink→llinkD.p→llink→rlink

21．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）

A.110B.108C.100D.120

22．关于存储相同数据元素的说法中正确的是（）

A．顺序存储比链式存储少占空间

B.顺序存储比链式存储多占空间

C.顺序存储和链式存储都要求占用整块存储空间

D.链式存储比顺序存储难于扩充空间

23．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）

A．q→next=s；p→next=s；B.q→next=s；s→next=p；

C.q→next=s；q→next=p；D.q→next=s；s→next=q；

24．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）

A．O（n）B.O

（1）

C.O（log2n）D.O（n2）

25．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（　　）

A.单链表B.仅有头指针的单循环链表

C.双链表D.仅有尾指针的单循环链表

26．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（　　）

A.n-iB.n-i+1C.n-i-1D.i

27．对于长度为n的顺序表执行删除操作，则其结点的移动次数（　　　）

A.最少为0，最多为nB.最少为1，最多为n

C.最少为0，最多为n-1D.最少为1，最多为n-1

28．在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（　　　）

A.p->next=qB.p->next=q->next

C.p=q->nextD.p->next=q->next->next

29．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（　　　）

A．O

（1）B．O（n）

C．O（nlog2n）D．O（n2）

30．顺序存储的线性表（a1,a2,…,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（　　）

A．nB．n/2

C．n+1D．（n+1）/2

31．设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（）。

A．p->next=p->next->nextB．p=p->next

C．p=p->next->nextD．p->next=p

32．线性表的链式存储实现有利于（）运算。

A．插入B．读表元

C．查找D．定位

33．从一个长度为n的顺序表中删除第i个元素（1≤i≤n），需向前移动（）个元素。

A．n-iB．n-i+1

C．n-i-1D．i

34．在一个长度为n的顺序存储线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需向后移动（）个元素。

A．n-iB．n-i+1

C．n-i-1D．i

35．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（）。

A．s->next=p->next;p->next=s;B．q->next=s;s->next=p;

C．p->next=s->next;s->next=p;D．p->next=s;s->next=q;

36．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

A.HL=p;p->next=HL;

B.p->next=HL;HL=p;

C.p->next=HL;p=HL;

D.p->next=HL->next;HL->next=p;

37．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。

A.p=q->next;p->next=q->next;

B.p=q->next;q->next=p;

C.p=q->next;q->next=p->next;

D.q->next=q->next->next;q->next=q;

38．线性表采用链式存储时，其地址（）。

A．必须是连续的B．部分地址必须是连续的

C．一定是不连续的D．连续与否均可以

39．在一个长度为n的线性表中插入第i个元素的操作中，i的取值范围是

A．1≤i≤nB．0≤i≤nC．1≤i≤n+1D．1≤i≤n-1

40．如果要查找单链表中的第i个元素，应该从（B）开始进行查找。

A．第i个结点B．头结点C．尾结点D．任意一个结点

41．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（C）。

A.nB.n/2C.（n+1）/2D.（n-1）/2

42．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（D）。

A.q->next=p->next;p->next=q;

B.p->next=q->next;q=p;

C.q->next=p->next;p->next=q;

D.p->next=q->next;q->next=p;

43.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行（D）。

A.s→link=p→link;p→link=s;B.p→link=s;s→link=q;

C.p→link=s→link;s→link=p;D.q→link=s;s→link=p;

44.线性链表不具有的特点是（A）。

A．随机访问B．不必事先估计所需存储空间大小

C．插入与删除时不必移动元素D．所需空间与线性表长度成正比

45.下述哪一条是顺序存储结构的优点？

（C）。

A． 插入运算方便B．可方便地用于各种逻辑结构的存储表示

C．存储密度大D．删除运算方便

46.下面关于线性表的叙述中，错误的是哪一个？

（B）。

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

47.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表

48．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。

A. 单链表B.仅有头指针的单循环链表

C.双链表D.仅有尾指针的单循环链表

49．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（A）最节省时间。

A.带头结点的双循环链表B.单循环链表

C.带尾指针的单循环链表D.单链表

50．若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（D）。

A.单链表B.双向链表C.单循环链表D.顺序表

51．静态链表中指针表示的是（C）

A.下一元素的地址B.内存储器的地址

C.下一元素在数组中的位置D.左链或右链指向的元素的地址

52．在n个结点的线性表的数组实现中，算法的时间复杂性是O

（1）的操作是（A）

A. 访问第i个结点（1≤i<=n）和求第i个结点的直接前驱（2≤i<=n）

B. 在第i个结点后插入一个新结点（1≤i<=n）

C. 删除第i个结点（1≤i<=n）

D. 以上都不对

53．

（1）静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

（2）静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（B）。

A．

（1），

（2）B．

（1）C．

（1），

（2）,（3）D.

（2）

54．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）。

A．O（n）O（n）B.O（n）O

（1）C.O

（1）O（n）D.O

（1）O

（1）

55．单链表中，增加一个头结点的目的是为了C）。

A．使单链表至少有一个结点B．标识表结点中首结点的位置

C．方便运算的实现D．说明单链表是线性表的链式存储

56．对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（D）。

A．p->right=s;s->left=p;p->right->left=s;s->right=p->right;

B．p->right=s;p->right->left=s;s->left=p;s->right=p->right;

C．s->left=p;s->right=p->right;p->right=s;p->right->left=s;;

D．s->left=p;s->right=p->right;p->right->left=s;p->right=s;

57．对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（B）。

A.顺序存储方式B.链式存储方式C.散列存储方式D.以上均可以

58．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：

（B）。

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;

59．线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构

C.索引存取的存储结构D.Hash存取的存储结构

60．顺序表是线性表的（B）

A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构

61．带头结点的单链表head为空的条件是（B）

A、head=NULLB、head->next=NULLC、head->next=headD、head!

=NULL

62．链表不具有的特点是（B）

A．插入、删除不需要移动元素B．可随机访问任一元素

C．不必事先估计存储空间D．所需空间与线性长度成正比

63．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。

A．顺序表B．双链表

C．带头结点的双循环链表D．单循环链表

64．下面关于线性表的叙述中，错误的是哪一个？

（B）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

二、填空题

1．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。

n+1-i，n-i

2.设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。

p>llink->rlink=p->rlink;p->rlink->llink=p->rlink

3．设指针变量p指向单链表中结点A，则删除结点A的语句序列为：

q=p->next；p->data=q->data；p->next=___________；feee（q）；q->next

4．在带头结点的单链表L中,第一个元素所对应的结点的指针表达式是_____________。

L->next

5．在双向循环链表中，在结点*Ｐ之前插入结点*Ｓ的语句序列是：

S->prior=P->prior;S->next=P;P->prior=S;__________________。

S->prior->next=S;

6．在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_____O

（1）____和______O

（1）____。

7．在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向__和_。

前驱、后继

8．在循环队列中，存储空间为0~n-1。

设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_______。

_（rear+1）%n=front

9．下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。

typedefstructnode{intdata;structnode*next;}lklist;

voidlklistcreate（_____________*&head）

{

for（i=1;i<=n;i++）

{

p=（lklist*）malloc（sizeof（lklist））;scanf（“%d”,&（p->data））;p->next=0;

if（i==1）head=q=p;else{q->next=p;____________;}

}

}

lklist，q=p

10．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：

1）s->next=___________；2）p->next=s；3）t=p->data；

4）p->data=___________；5）s->data=t；p->next，s->data

11．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：

s->next=p->next;_________________;。

p->next=s

12．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。

head->rlink，p->llink

13．设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s；p->right->left=s；（设结点中的两个指针域分别为left和right）。

s->left=p，p->right

14．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。

s->next=p->next;p->next=s

15．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则应执行语句：

。

p->next=HL;HL=p;

16．在采用独立结点构成的双向链表中，设p和q分别是具有Dnode*类型的指针变量。

若双向链表中p结点之后插入一个q结点，其操作步骤为：

；

；

；

；

q->right=p->right;

if（p->right）p->right->left=q;

q->left=p;

p->right=q;

17．对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为________________。

O（n）O

（1）

18．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动___n-i+1_____个元素。

19．设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“__s->rl->tl=s->tl_______”。

20．设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。

现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__head=p________”。

21．单链表中逻辑上相邻的两个元素在物理位置上_____不一定_____相邻。

22．在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是_____n-i_____。

23．在顺序表上读表元算法的时间复杂度为___O

（1）____。

24．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语