数据结构习题集

1 概述

一、选择题：

1、下列算法的时间复杂度是（ ） for(i=0;i

c[i]=i；

A．O（1） B．O（n） C．O（log2n） D．O（nlog2n）

2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ ）

A．索引存储方法 B．顺序存储方法 C．链式存储方法 D．散列存储方法

3、以下哪一个术语与数据的存储结构无关？（ ）。

A.顺序表 B.链表

C.散列表 D.队列

4、算法在发生非法操作时可以做出处理的特性称为（ ）。

A．正确性 B．易读性 C．健壮性 5、逻辑结构是指数据元素的（ ）。 A．关联方式 B．存储方式 6、研究数据结构就是研究（ ）。

A．数据的逻辑结构

B．数据的存储结构

C．数据的逻辑结构和存储结构

C．结构

D．高效性

D．数据项

D．数据的逻辑结构、存储结构及其数据的运算 7、从逻辑上可以把数据结构分为（ ）。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 8、以下有关数据的叙述中错误的是（ ）。

A．计算机能够处理的数据包括整数、实数、字符、声音、图像等 B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式 C．数据存储结构的实现依赖于计算机语言 D．数据的运算是定义在数据的逻辑结构上的 9、数据的基本单位是（ ）。

A.数据结构 B.数据元素 C.数据项 D.文件 10、下列算法的时间复杂度是（ ） for(i=0;i

for(j=0;j

A．O（m2） B．O（n2） C．O（m×n） D．O（m+n） 11、算法分析的两个主要方面是（ ）。

A．正确性和简明性 C．可读性和可维护性 二、填空题：

B．数据复杂性和程序复杂性 D．时间复杂性和空间复杂性

1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（ ）和（ ）。 2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（ ）无关，是

独立于计算机的。

3、( )结构与数据元素本身的内容和形式无关。

4、程序段“for(i=1;i<=n;i++) {k++; for(j=1;j<=n;j++) x=x+k;}”的时间复杂度为( )。 5、数据的存储结构（物理结构）可以用（ ）、（ ）、（ ）及散列存储等四种存储方法表示。 三、判断题：

1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （ ） 2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （ ） 3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ ） 4、数据的机内表示称为数据的存储结构。 （ ） 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ） 6、线性表的链式存储结构优于顺序存储结构。 （ ） 7、数据元素是数据的最小单位。 （ ） 8、基于某种逻辑结构之上的运算，其实现是惟一的。 （ ）

2 线性表

一、 选择题：

1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。

A．n B．n/2 C．n/3 D．n/4

2、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ ）

A．S->next=P->next;P->next=S B．P->next=S->next;S->next=P； C．P->next=P;P->next=S； D．P->next=S;S->next=P；

3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ）

A．Ｏ（1） B．Ｏ（log2n） C．O（n） D．O（n2）

4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ） A．顺序表 B．用头指针表示的单循环链表 C．用尾指针表示的单循环链表 D．单链表 5、线性表是（ ）

1

A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（ ） A．O（n） B．O（1） C．O（log2n） D．O（n） 7、线性表采用链式存储时，结点的地址（ ） A．必须是连续的 B．必须是不连续的

C．连续与否均可 D．必须有相等的间隔 8、在单链表中，增加头结点的目的是（ ）

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

C．方便运算的实现 D．说明单链表是线性表的链式存储实现 9、带头结点的单链表head为空的判定条件是（ ）

A．head = NULL； B．head - > next = NULL； C．head - > next = head； D．head ! = NULL；

10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ ）

A．Ｏ（1） B．Ｏ（n） C．Ｏ（n2） D．Ｏ（log2n） 11、下列有关线性表的叙述中，正确的是（ ） A．线性表中的元素之间是线性关系 B．线性表中至少有一个元素

C．线性表中任何一个元素有且仅有一个直接前趋 D．线性表中任何一个元素有且仅有一个直接后继

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

A．直接前趋 B．直接后继 C．开始结点 D．终端结点 13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A．n B.2n-1 C.2n D.n-1 14、链表不具有的特点是（ ）。

A．随机访问 B．不必事先估计存储空间 C．插入删除时不需移动元素 D．所需的空间与线性表成正比

15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入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; 16、链表具有的特点是（ ）。

A．可随机访问任一元素

B．插入、删除需要移动元素

2

C．不必事先估计存储空间 D．存储空间是静态分配的 17、一个顺序表一旦说明，其中可用空间大小（ ）

A．已固定 B．可以改变 C．不能固定 D．动态变化

18、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）

2

存储方式最节省时间。

A． 顺序表 B．单链表 件是（ ）。

A．P->next==Q

C．双向链表 D．单循环链表

19、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前驱的条

B．Q->next==P

C．P==Q D．P->next==Q->next 20、链表不具有的特点是（ ）。

A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性表长度成正比 21、下面关于线性表的叙述中，错误的是（ ）。

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

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

C．线性表采用链接存储，不必占用一片连续的存储单元 D．线性表采用链接存储，便于进行插入和删除操作

22、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前趋（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n）

C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序

23、在一个单链表中，若删除p指向结点的后继结点，则执行的操作为（ ）。

A．q=p->next;p->next=p->next->next;free(q); B．p=p->next;q=p->next;p=q->next;free(q);

C．q=p->next->next;p=p->next;free(q); D．p=p->next->next;q=p->next;free(q); 二、 填空题：

1、在双链表中要删除已知结点*p，其时间复杂度为（ ）。

2、在仅有尾指针R指示的单循环链表R中，在表尾插入一个结点S的语句序列是（ ）。 3、在带头结点的双链表Ｌ中，指针Ｐ所指结点是开始结点的条件是（ ）。 4、在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为（ ）。 5、在一个长度为n的顺序表中第i个元素（1 ≤ i ≤ n）之前插入一个元素时，需向后移动（ ）个元素。

6、在双循环链表中，若要在指针p所指结点之前插入指针s所指的结点，则需执行下列语句：s->prior=p->prior;p->prior->next=s;( )和p->prior=s;。 7、已知指针p指向双向链表中的一个结点（非首结点、非尾结点），则将结点s插入在p结点的直接后继位置的语句是（ ）s->prior=p；s->next->prior=s；p->next=s; 8、已知带表头结点的单链表L，指针p指向L链表中的一个结点（非首结点、非尾结点），则删除结点p的直接后继结点的语句是（ ）；删除首结点的语句是（ ）。

3

三、 判断题：

1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。（ ） 2、顺序存储的线性表可以随机存取。 （ ） 3、线性表采用顺序存储，必须占用一片连续的存储单元。 （ ） 4、线性表的顺序存储结构优于链式存储结构。 （ ） 四、 程序设计题：

1、已知带头结点的单链表head中的结点是按整数值递增排序的，写一算法将值为x的结点插入到表head中，使head仍然有序。

2、用尾插入法建立带头结点的单链表。

3、写出将整数i插入到无头结点的链栈中的算法。

4、对给定的单链表L，编写一个删除L中值为x的结点的直接前趋结点算法。]

3 栈和队列

一、选择题：

1、循环队列是空队列的条件是（ ） A．Q - > rear = = Q - > front B．（Q - > rear + 1）%maxsize = = Q - > front C．Q - > rear = = 0 D．Q - > front = = 0 2、链栈与顺序栈相比，比较明显的优点是（ ）

A．插入操作更加方便 B．删除操作更加方便 C．不会出现下溢的情况 D．不会出现上溢的情况

3、若一个栈的输入序列是１，２，３，??，n，输出序列的第一个元素是ｎ，则第ｉ个

输出元素是（ ） A．n - i B．n – i + 1 C．i D．不确定 4、栈与一般线性表的区别主要在（ ）

A．元素个数 B．元素类型 C．逻辑结构 D．插入、删除元素的位置 5、一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除结点，则

执行（ ） A．x = top;top = top - > next； B．x = top - > data；

C．top = top - > next;x = top - > data；

D．x = top - > data;top = top - > next；

6、对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（ ） A．1，2，3 B．3，2，1 C．3，1，2 D．2，1，3 7、在链接队列执行入队操作（ ）

4

本文来源：https://www.bwwdw.com/article/k47v.html