《数据结构与算法》习题集

《数据结构与算法》习题集

一、单项选择题

第1章概论

1.数据结构是一门研究非数值计算的程序设计问题中计算机的(①)以及它们之间的(②)和

运算等的学科。

①A.数据元素B.计算方法C.逻辑存储D.数据映像

②A.结构B.关系C.运算D.算法

2.数据结构被形式地定义为(K,R),其中K是(①)的有限集，R是K上的(②)的有限集。

①A.数据元素B.算法C.数据操作D.逻辑结构

②A.操作B.映像C.存储D.关系

3.在数据结构中，从逻辑上看可以把数据结构分成()。

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.线性结构和非线性结构D.内部结构和外部结构

4.数据结构在计算机内存中的表示是指()。

A.数据的存储结构B,数据结构

C.数据的逻辑结构D.数据元素之间的关系

5.在数据结构中，与所使用的计算机无关的是数据的()结构。

A.逻辑B.存储C.逻辑和存储D.物理

6.算法分析的目的是(①)，算法分析的两个主要方面是(②)。

①A.研究数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易董性和文档性

②A.空间复杂度和时间复杂度B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

7.算法指的是(①)，它必须具有输入、输出和(②)等5个特性。

①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法

②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

8.以下叙述中，正确的是()。

A.线性表的线性存储结构优于链式存储结构

B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出

D.队列的操作方式是先进后出

9.在决定选取何种存储结构时，一般不考虑()。

A.各结点的值如何B.结点个数的多少C.对数据有哪些运算

D.所用编程语言实现这种数据结构是否方便

10.在存储数据时.，通常不仅要存储各数据元素的值，而且还要存储()。

A.数据的处理方法B.数据元素的类型

C.数据元素之间的关系D.数据的存储方法

11.下面说法错误的是()。

(1)算法原地工作的含义是指不需要任何额外的辅助空间

(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度0(2,的算法

(3)所谓时间复杂度是指最坏情况下，估算执行时间的一个上界

(4)同一个算法，实现语句的级别越高，执行效率越低

A.(1)B.⑴、(2)C.⑴、(4)D.(3)

12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着()。

A.数据元素具有同一■特点

B.不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致

C.每个数据元素都一样

D.数据元素所包含的数据项的个数要相等

13.以下说法正确的是()。

A.数据元素是数据的最小单位

B.数据项是数据的基本单位

C.数据结构是带结构的各数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

14.算法的计算量的大小称为计算的()。

A.效率B.复杂性C.现实性D.难度

15.算法的时间复杂度取决于()

A.问题的规模B.待处理数据的初态C.A和B

16.计算机算法指的是【1】，它必须具备【2】这三个特性。

(1)A.计算方法B.排序方法C.解决问题的步骤序列D.调度方

法

(2)A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性D.易读性、稳定性、安全性

17.•个算法应该是()。

A.程序B.问题求解步骤的描述

C.要满足五个基本特性1).A和C.

18.下面关于算法说法错误的是()

A.算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性D.以上几个都是错误的

19.下面说法错误的是()

(1)算法原地工作的含义是指不需要任何额外的辅助空间

(2)在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2”)的算法

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

(4)同一个算法，实现语言的级别越高，执行效率就越低

A.(1)B.(1),(2)C.(1),(4)D.(3)

20.从逻辑上可以把数据结构分为()两大类。

A.动态结构、静态结构B.顺序结构、链式结构

C.线性结构、非线性结构D.初等结构、构造型结构

21.以下与数据的存储结构无关的术语是()。

A.循环队列B.链表C.哈希表D.栈

22.以下数据结构中，哪一个是线性结构()?

A.广义表B.二叉树C.稀疏矩阵D.串

23.以下那一个术语与数据的存储结构无关？()

A.栈B.哈希表C.线索树D.双向链表

24.在下面的程序段中，对x的赋值语句的频度为（）

FORi:=lTOnDO

FORj:=lTOnDO

x:=x+l;

A.0(2n)B.0(n)C.0(n2)D.O(logJ)

25.程序段FORi:=nTDOWNTO1DO

FORj:=lTOiDO

IFA[j]>A[j+l]

THENA[j]与A[j+1]对换;

其中n为正整数，则最后一行的语句频度在最坏情况下是（）

A.0(n)B.O(nlogn)C.0(n3)D.0(n2)

26.以下哪个数据结构不是多型数据类型（）

A.栈B.广义表C.有向图D.字符串

27.以下数据结构中，（）是非线性数据结构

A.树B.字符串C.队D.栈

28.下列数据中，（）是非线性数据结构。

A.栈B.队列C.完全二叉树D.堆

29.连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续

30.以下属于逻辑结构的是（）。

A.顺序表B.哈希表C.有序表D.单链表

31.组成数据的基本单位是（

A.数据项B.数据类型C.数据元素D.数据变量

32.下列数据组织形式中，（）的结点按逻辑关系依次排列形成一个“锁链”。

A.集合B.树形结构

C.线性结构D.图状结构

33.数据结构可以形式化地定义为（S,△）,其中S指某种逻辑结构，△是指（)

A.S上的算法B.S的存储结构

C.在S上的一个基本运算集D.在S上的所有数据元素

34.算法分析的目的是（）

A.找出数据结构的合理性B.研究算法中的输入/输出关系

C.分析算法的效率以求改进D.分析算法的易读性

35.数据结构是•门研究非数值计算的程序设计问题中计算机的⑴以及它们之间的⑵和运算

等的学科。（

（1）A.操作对象Bo计算方法C。逻辑存储1）。数据映象

（2）A.结构Bo关系C„运算Do算法

36.数据结构被形容地定义为（K,R），其中K是（1）的有限集合，R是K上的（2）有限

集合。

(1)A.算法Bo数据元素Co数据操作Do逻辑结构

(2)A.操作B。映象Co存储D«关系

37.在数据结构中，从逻辑上可以把数据结构分成

（1）A.动态结构和静态结构Bo紧凑结构和非紧凑结构

C.线性结构和非线性结构D。内部结构和外部结构

38.算法分析的目的是（1）,算法分析的两个主要方面是（2）。

（1）A.找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

（2）A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

39.计算机算法指的是（1）大，它必具备输入、输出和（2）等五个特性。

（1）A.计算方法B。排序方法

C.解决问题的有限运算序列D«调度方法

（2）A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

第2章线性表

1.线性表不具备的特点是（）。

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

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

2.不带头结点的单链表head为空的判定条件是（）。

A.head==NULLB.head->next==NULL

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

3.带头结点的单链表head为空的判定条件是（）。

A.head==NULLB.head->next==NULL

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

4.带头结点的双循环链表L为空的条件是（）。

A.L==NULLB.L->next==NULL

C.L->prior==NULLD.L->next==L

5.非空的循环单链表head的尾结点（由p所指向）满足（）。

A.p->next=NULLB.p==NULL

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

6.在循环双链表的p所指结点之前插入s所指结点的操作是()。

A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;

B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;

C.s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;

D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;

7.若某表最常用的操作是在最后一个结点之后插入--个结点或删除最后一个结点，在采用

()存储方式最节省运算时间。

A.单链表B.给出表头指针的单循环链表C.双链表D.带头结点的双循环链表

8.某线性标最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用

()存储方式最节省运算时间。

A.单链表B.仅有头结点的单循环链表C.双链表D.仅有为指针的单循环链表

9.需要分配不仅大空间，插入和删除不需要移动元素的线性表，其存储结构是()。

A.单链表B.静态链表C.线性链表D.顺序存储结构

10.如果最常用的操作是取第i个结点及其前驱，在采用()存储方式最节省时间。

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

11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是

()。

2

A.O(l)B.O(n)C.O(n)D.O(nlog2n)

12.在一个长度为n(n>l)的单链表上，设有头和尾两个指针，执行()操作与链表的长

度有关。

A.删除单链表中的第一个元素

B.删除单链表中的最后一个元素

C.在单链表第一个元素前面插入一个新元素

D.在单链表最后一个元素后插入一个新元素

13.设线性表有n个元素，以下算法中，()在顺序表上实现比在链表上实现效率更高。

A.输出第i(0<=i<=n-l)个元素值

B.交换第0个元素与第1个元素的值

C.顺序输出这n个元素的值

D.输出与给定值x相等的元素在线性表中的序号

14.设线性表中有2n个元素，算法(),在单链表上实现要比在顺序表上实现效率更高.

A.输出所有值为x的元素

B.在最后一个元素的后面插入一个新元素

C.顺序输出前k个元素

D.交换第i个元素和第2n-i-l个元素的值(i=0,l,...,n-l)

15.与单链表相比，双链表的优点之一是()。

A.插入、输出操作更简单B.可以进行随机访问

C.可以受理表头指针或表尾指针D.顺序访问相邻结点更灵活

16.如果对线性表的运算只有四种，即删除第一个元素，删除最后一个元素，在第一个元素

的前面插入新元素，在最后一个元素的后面插入新元素，则最好使用()。

A.只有表尾指针没有表头指针的循环单链表

B.只有表尾指针没有表头指针的非循环双链表

C.只有表头指针没有表尾指针的循环双链表

D.既有表头指针也有表尾指针的循环单链表

17.如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素的后面插入新元素,

最最好使用（）o

A.只有表头指针没有表尾指针的循环单链表

B.只有表尾指针没有表头指针的循环单链表

C.非循环双链表

D.循环双链表

18.设有两个长度为n的单链表，结点类型相同。若以hl为表头指针的链表是非循环链表,

以h2为表头指针的链表是循环链表，则（）。

A.对应两个链表来说，删除第一个结点的操作，其时间复杂度都是0（1）

B.对应两个链表来说，删除最好一个结点的操作，其时间复杂度都是0（n）

C循环链表要比非循环链表占用更多的存储空间

D.hl和h2是不同类型的变量

19.在长度为n的（）上，删除第一个元素，其算法的时间复杂度为0（n）。

A.只有表头指针的不带表头结点的循环单链表

B.只有表尾指针的不带表头结点的循环单链表

C.只有表尾指针的带表头结点的循环单链表

D.只有表头指针的带表头结点的循环单链表

20.下述哪一•条是顺序存储结构的优点？（）

A.存储密度大B.插入运算方便C.删除运算方便

D.可方便地用于各种逻辑结构的存储表示

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

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

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

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

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

22.线性表是具有nj（）的有限序列（n>0）。

A.表元素B.字符C.数据元素D.数据项E.信息项

23.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则

利用（）存储方式最节省时间。

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

24.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采

用（）存储方式最节省运算时间。

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

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

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

A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表

26.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用

（）存储方式最节省运算时间。

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

27.静态链表中指针表示的是（）.

A.内存地址B.数组下标C.下一元素地址D.左、右孩子地址

28.链表不具有的特点是（）。

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

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

29.下面的叙述不正确的是（）。

A.线性表在链式存储时，查找第i个元素的时间同i的值成正比

B.线性表在链式存储时，查找第i个元素的时间同i的值无关

C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比

D.线性表在顺序存储时，查找第i个元素的时间同i的值无关

30.线性表的表元存储方式有（（1））链接两种。试指出下列各表中使用的是何种存储方式：

表1是（2）存储方式；表2是（3）存储方式；表3是（4）存储方式；表4是（5）存储方

式。表左的s指向起始表元。

表1

表元编号货号数量表元间联系

1618402

220523

3103154

4501205

5781176

6910240

表2

表元编号贝化甘n数量表元间联系

1618405

220521

3103154

4501202

5781176

6910243

表3

表元编号货号数量表元间联系

1618405

220521

3103154

4501200

5781176

6910243

表4

表元编号货号数量表元间联系

12

16184052

2205210

31031546

45012003

57811761

69102435

供选择的答案：

A.连续B.单向链接C.双向链接D.不连接E.循环链接

F.树状G.网状H.随机I.顺序J.顺序循环

31.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素

的时间与i无关。

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

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

以上错误的是()o

A.(1),(2)B.(1)C.(1),(2),(3)D.(2)

32.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间

复杂度为()(l<=i〈=n+l)。

A.0(0)B.0(1)C.0(n)D.0(n2)

33.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。

A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)

34.线性表(al,a2,…,an)以链接方式存储时，访问第i位置元素的时间复杂性为()

A.0(i)B.0(1)C.0(n)D.0(i-1)

35.非空的循环单链表head的尾结点指针p满足()。

A.p->link=headB.p->link二NILC.p=NILD.p=head

36.循环链表H的尾结点P的特点是()。

A.P->NEXT=HB.P->NEXT=H->NEXTC.P=HD.P=H->NEXT

37.在一个以h为头的单循环链中，p指针指向链尾的条件是().

A.p->next=hB.p->next=NULLC.p->next->next=hD.p->data=-l

38.在双向链表指针p的结点前插入一个指针q的结点操作是()。

A.p->Llink=q;q->Rlink=p;p->Llink->R1ink=q;q->Llink=q；

B.p->Llink=q;p->Llink->Rlink=q;q->Rlinkup;q->Llink=p->Llink;

C.q->Rlink=p;q->L1ink=p->L1ink;p->L1ink->Rlink二q;p->Llink=q;

D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

39.在单链表指针为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;

40.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是()

A.head==NULLB.headnext-NULLC.head-*next-headD.head!=NULL

41.在一个单链表中，已知q所指结点是p所指结点的前驱，若在p、q之间插入s结点，则

执行(B)操作。

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

C、p->next=s->next;s->next=p;p->next=s;s->next=q;

42、使用双向链表存储数据，其优点是可以(A)。

A、提高检索速度B、很方便地插入和删除数据

C、节约存储空间D、很快回收存储空间

43、单链表中，增加头结点的目的是为了(A)o

A、方便运算的实现B、标识单链表

C、使单链表中至少有一个结点1)、用于标识起始结点的位置

若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用(D)存

储方式最节省时间。

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

44、带头结点的单链表h为空的判断条件是（B

A>h==NULLB、h->next==NULLC、h->next=hD、h!=NULL

45.线性表的链接实现有利于（）运算。

A.插入B.读表元素C.查找D.定位

46.设单链表中指针P指着结点A,若要删除A之后结点（若存在），则需要修改指针的操

作为（

A.p->next=p->next->nextB.p=p->next

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

47.设双链表中结点的前趋指针和后继指针的域名分别为tl和rl,则删除双链表中指针s

所指结点的操作为（）

A.s->tl->rl=s->t1;s->rl->tl=s->rl;B.s->tl->rl=s->rl;s->rl->tl=s->t1;

C.s->rl=s->tl->r1;s->t1=s->r->t1;D.s->tl=s->t1->r1;s->rl=s->r->tl;

48.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一

个指针s所指的新结点作为非空双链表中q所指地点（中间结点）的直接后继结点插入到该

双向链表中，则下列算法段能正确完成上述要求的是（）

A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;

B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;

C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;

D.以上都不对

49.下列说法正确的是（）

A.线性表的逻辑顺序与存储顺序总是一致的

B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续

C.线性表的线性存储结构优于链式存储结构

D.每种数据结构都具有插入、删除和查找三种基本运算

50.设非空单链表的数据域为data,指针域为next,指针p指向单链表中第i个结点，s

指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段

能正确完成上述要求的是（）

A.s->next=p->next;p->next=s；

B.p->next=s;s->next=p->next；

C.s->next=p->next;p->next=s;交换p->data和s->data；

D.p=s;s->next=p；

51.下面关于线性表的叙述中，错误的为（）

A.顺序表使用一维数组实现的线性表B.顺序表必须占用一片连续的存储单元

C.顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域

52.带头结点的单链表head为空的判断条件是（）

A.head=NILB.headt.next=NIL

C.headt.next=headD.head<>NIL

53.一个顺序表所占用的存储空间大小与——无关•

A.表的长度B.元素的存放顺序C.元素的类型D。元素中各字段的类型

54.设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地

址是指它所占用的单元的

A.第1个单元的地址B.第2个单元的地址

C.第3个单元的地址n第4个单元的地址

55.若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为

100,则第12个元素的存储地址是o

A.112B.144C.1480.412

56.若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合

法值

应该是——。

A.i>0B.iWnC.IWiWnD.IWiWn+l

57.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应

该是

A.i>0B.iWnC.IWiWnD。IWiWn十1

58.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动

表

中——个数据元素。

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

59.若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移

动

表中——个元素。。

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

60.若频繁地对线性表进行插入和删除操作，该线性表应该采用——存储结构。

A.散列B.顺序C.链式D.索引

61.链表中所占用的存储单元地址一定是。

A.无序的B.连续的C.不连续的D.部分连续的

62.链表中的每一个链结点所占用的存储单元——。

A.不必连续B.一定连续C.部分连续D.连续与否无所谓

63.与单链表相比，双向链表的优点之一是。

A.插入、删除操作更简单B.可以进行随机访问

C.可以省略头结点指针I).顺序访问相邻结点更灵活

64.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域中

存

放的是——«

A.list的地址B.list的内容

C.list指的链结点的值I).链表第一个链结点的地址

65.若list是某带头结点的循环链表的头结点指针，当p(p与list同类型)指向链表的最

后那

个链结点时，——。

A.该结点的指针域为空B.p为空

C.p的内容与头结点的内容相同D.该链结点指针域内容与list的内容相同

66.若listl和list2分别为一个单链表与一个双向链表的第一个结点的指针，则——。

A.Iist2比listl占用更多的存储单元B.listl与list2占用相同的存储单元

C.listl和list2应该是相同类型的指针变量D.双向链表比单链表占用更多的存储单

元

67.在表达式中，符号p->link表不--。

A.p所指的链结点的指针域(位置)

B.p所指的链结点的指针域的内容

C.p所指的链结点的下一个链结点的地址

I),p所指的链结点的下一个链结点的地址(出现在表达式中)

68.在一个具有n个链结点的线性链表中查找某个链结点，若查找成功，需要平均比较

——个链结点。

A.nB.n/2C.(n+1)/2D.(n-1)/Q

69.从一个具有n个链结点的有序线性链表(即链结点按照数据域值有序链接)中插入一个

新的链结点，并且仍然保持链表有序的时间复杂度为——。

A.0(1)B.0(n)C.0(n(2))D.0(log2(n))

70.给定具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为一一。

A.0(1)B.0(n)C.0(n(2))D.0(log2(n))

71.在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执

行----。

A.q->link=p；p->link=q；B.q->link=p->link；p->link=q；

C.q->link=p->link；p=q；D.p->link=q；q->link=p；

72.若删除非空线性链表中由p所指的链结点的直接后继链结点的过程是依次执行

A.r=p->link；p->link=r；free(r)；

B.r=p->link；p->link=r->link；free(r)；

C.r=p->link；p->link=r->link；free(p)；

D.p->link=p->link->link；free(p)；

73.在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的动作依次

为：p->llink=Q；p->rlink=q->rlink；q->rlink=p；----。(空白处为一条赋值

语句)

A.q->llink=pB.q->rlink->llink=p

C.p->fiink->l1ink=pD.p->l1ink->l1ink=p

74.在非空双向循环链表中由q所指的那个链结点前面插入一个p所指的链结点的动作对

应的语句依次为:p->rlink=Q；p->llink=q->llink；q->[link=p；----,(空白

处为一条赋值语句)

A.q->rlink=p；B.q->llink->rlink=p；

C.p->rlink->rlink=p；D.p->l1ink->rlink=p；

75.在包含有1000个数据元素的线性表中实现如下四个操作，所需要的执行时间最长的是

—0

A.线性表采用顺序存储结构，在第10个元素后面插入一个新的元素

B.线性表采用链式存储结构，在第10个元素后面插入一个新的元素

C.线性表采用顺序存储结构，删除第990个元素

D.线性表采用链式存储结构，删除p所指的链结点

76.不带头结点的单链表head为空的判定条件是3)。

A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL

77.带头结点的单链表head为空的判定条件是(1)。

A.head=NULLB.head->next=NULLC.head->next=headD.!=NULL

78.非空的循环单链表head的尾结点（由P所指向）满足（1）。

A.p->next=NULLB.p=NULLC.p->next=headD.p=head

79.在循环双链表的p所指结点之后插入S所指向的结点的操作是（1）。

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;

80.在一个单链表中，已知p所指结点是前驱结点，若在q和p之间插入S结点，则执行（1）。

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

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

81.在一个单链表中，若p所指结点不是最后结点，在p之后插入S所指结点，则执行（l）o

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;D.p->next=s;s->next=p;

82.在一个单链表中，若删除P所指结点的后续结点，刚执行（1）。

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

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

83.假设双链表结点的类型如下：

Typedefstructlinknode

（

Intdata;/*数据域*/

Structlinknode*llink;/*llink是指向前驱结点的指针域*/

Structlinknode*rlink/*rlink是指向后续结点的指针域*/

}bnode

下面给出的算法段是要把一个q所指新结点作为非空双向链表中的P所指结点的前驱结点插

入到该双链表中，能正确完成要求的算法段是（1）。

A.q->rlink=p;

q->llink=p->llink;

p->llink=q;

p->llink->rlink=q;

B.p->llink=q;

q->rlink=p;

p->Hink->r1ink=q;

q->llink=p->llink;

C.q->Hink=p->llink;

q->rlink=p;

p->Hink->rlink=q;

p->llink=q;

D.以上都不对

第3章栈和队列

1.栈的特点是（①）列的特点是（②）。

A.先进先出B.先进后出

2.栈和队列的共同点是（）。

A.都是先进后出B.都是先进先出

C.只允许在端点插入和删除元素D.没有共同点

3.•个栈的进栈序列是a,b,c,d,e,则栈不可能的输出序列是（）o

A.edcbaB.decbaC.dceabD.abcde

4.若已知一个栈的进栈序列是1,2,3,…,n,其输出序列为pi,p2,p3,…,Pn，若pi=n,则pi（k=ivn）

为（）。

A.iB.n=iC.n-i+1D.不确定

5.若已知一个栈的进栈序列是1,2,3.n,其输出序列为pi,p2,p3,…,Pn，若Pn=n,则pi（l<=i<n）

为（）。

A.iB.n=iC.n-i+1D.不确定

6.若已知一个栈的进栈序列是1,2,3.n,其输出序列为P|,P2,P3,…,Pn，若Pl=l，则P2为（）。

A.可能是2B.不一定是2C.可能是1D.一定是1

7.若已知一个栈的进栈序列是1,2,3,其输出序列为pi,p2,p3,…,p”若p3=l，则Pi为

（）。

A.可能是2B.一定是2C.不可能是2D.不可能是3

8.若已知一个栈的进栈序列是Pl,P2,P3,...,Pn，输出序列是1,2,3,..,110若Pn=l,则Pi（l<=i<n）

为（）。

A.n-i+1B.n-iC.iD.有多种可能

9.判定一个栈ST（最多元素为MaxSize）为空的条件是（）。

A.ST->top!=-1B.ST->top==-l

C.ST->top!=MaxSize-1D.ST->top=MaxSize-l

10.判定一个栈ST（最多元素为MaxSize）栈满的条件是（）。

A.ST->top!=-lB.ST->top==-l

C.ST->top!=MaxSize-lD.ST->top==MaxSize-l

11.最不适合用作链枝的链表是（）0

A.只有表头指针没有表尾指针的循环双链表

B.只有表尾指针没有表头指针的循环双链表

C.只有表尾指针没有表头指针的循环单链表

D.只有表头指针没有表尾指针的循环单链表

12.向一个栈顶指针为HS的链栈中插入一个S所指结点时，则执行（）。

A.HS->next=S；B.S->next=HS->next;HS->next=S;

C.S->next=HS;HS=S;D.S->next=HS;HS=HS->next;

13.从一个栈顶指针为HS的链栈中输出一个结点时，用x表层被删除结点的值，则执行

（）。

A.x=HS;HS=HS->next;B.x=HS->data;

C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next;

14.一个队列的入队序列是1,2,3,4,则队列的输出序列是（）。

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1

15.判定一个队列QU（最多有MaxSize个元素）为空的条件是（）。

A.QU->rear-QU->front==MaxSizeB.QU->rear-QU->front-l==MaxSize

C.QU->front==QU->rearD.QU->front==QU->rear+1

16.判定一个队列QU（最多有MaxSize个元素）队满件是（）。

A.QU->rear-QU->front==MaxSizeB.QU->rear-QU->front-l==MaxSize

C.QU->front==QU->rearD.QU->front==QU->rear+1

17.循环顺序队列中是否可以插入下一个元素，（）。

A.与对队头指针和队尾指针的值有关

B.只与队尾指针的值有关，与队头指针的值无关

C只与数组的大小有关，与队首指针和队尾指针的值无关

D.与曾经进行多少次插入操作有关

18.判定一个循环队列QU（最多有MaxSize个元素）为空的条件是（）。

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==（QU->rear+1）%MaxSizeD.QU->front!=（QU->rear+1）%MaxSize

19.判定一个循环队列QU（最多有MaxSize个元素）队满的条件是（）。

A.QU->front==QU->rearB.QU->front!=QU->rear

C.QU->front==（QU->rear+l）%MaxSizeD.QU->front!=（QU->rear+1）%MaxSize

20.循环队列用数组A[0,m-l]存放其元素值，已知其头尾指针分别是front和rear,则当前队

列中的元素个数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front

21.若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是（）。

A.1和5B.2和4C.4和2D.5和1

22.最不适合用作链队的链表是（）°

A.只带队头指针的非循环链表B.只带队头指针的循环双链表

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

23.在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是（）o

A.f->next=s;f=s;B.r->next=s;r=s;

C.s->next=r;r=s;D.s->next=f;f=s;

24.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是（）o

A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;

25.用单链表表示的链队的队头在链表的（）位置。

A.链头B.链尾C.链中

26.对于栈操作数据的原则是（）。

A.先进先出B.后进先出C.后进后出D.不分顺序

27.在作进栈运算时，应先判别栈是否（①），在作退栈运算时应先判别栈是否（②）。当栈中

元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为（③）。为了增加内存空间的

利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（④）分别设

在这片内存空间的两端，这样，当（⑤）时，才产生上溢。