数据结构（线性表）练习题与答案1

1、线性表是()。

A.一个有限序列，可以为空

B.一个有限序列，不可以为空

C.一个无限序列，可以为空

D.一个无限序列，不可以为空

正确答案：A

解析：线性表是具有n(n20)个数据元素的有限序列。

2、线性表的基本运算Listinsert(也L,i,e)表示在线性表L中第i

个位置上插入一个元素e,若L的长度为n,则i的合法取值是

()O

A.iWiWn

B.lWiWn+1

C.OWiWnT

D.OWiWn

正确答案：B

解析：线性表的基本运算Listinsert(&L,i,e)中，位置i是指

逻辑序号，可以在L的位置1到位置n+1插入元素。

3、顺序表具有随机存取特性，指的是()。

A.查找值为x的元素与顺序表中元素个数n无关

B.查找值为x的元素与顺序表中元素个数n有关

C.查找序号为i的元素与顺序表中元素个数n无关

D.查找序号为i的元素与顺序表中元素个数n有关

正确答案：C

解析：一种存储结构具有随机存取特性指的是，对于给定的序号

i,在0(1)时间内找到对应元素值。

4、在顺序表中删除一个元素所需要的时间()。

A.与删除元素的位置及顺序表的长度都有关

B.只与删除元素的位置有关

C.与删除任何其他元素所需要的时间相等

D.只与顺序表的长度有关

正确答案：A

解析：当从顺序表中删除元素时，为了保持顺序表的逻辑特性，需

要移动元素以覆盖该删除的元素。因此在顺序表中删除一个元素与

该元素的位置及顺序表的长度都有关。

5、在n(n>l)个运算的顺序表中，算法时间复杂度为0(1)的运算

是()。

A.访问第i个元素(2WiWn)并求其前驱元素

B.在第i个元素之后插入一个新元素

C.删除第i个元素

D.将这n个元素递增排序

正确答案：A

解析：访问第i个元素(2WiWn)即L->data[iT]和求其前驱元

素L->data[i-2]的时间复杂度均为0(1)。

6、关于线性表的顺序存储结构和链式存储结构的描述中，正确的是

()O

I.线性表的顺序存储结构优于链式存储结构

n.顺序存储结构比链式存储结构的存储密度高

in.如需要频繁插入和删除元素，最好采用顺序存储结构

IV.如需要频繁插入和删除元素，最好采用链式存储结构

A.I、II、III

B.II.IV

C.IKIII

D.IlkIV

正确答案：B

解析：线性表的顺序存储结构和链式存储结构各有优缺点，不能简

单比较好坏，所以I错误。链式存储结构使用指针表示逻辑关系，

所以存储密度比较低，所以n正确。如频繁使用插入和删除操作，

链式存储结构更优于顺序存储结构，所以in错误，w正确。

7、在单链表中，增加一个头节点的目的是为了（）。

A.使单链表至少有一个节点

B.标识链表中某个重要节点的位置

C.方便插入和删除运算的实现

D.表示单链表是线性表的链式存储结构

正确答案：C

解析：在单链表中增加一个头节点的主要目的是使删除和插入节

点操作更简单，方便运算的实现。

8、通过含有n（n21）个元素的数组a,采用头插法建立一个单链

表L,则L中节点值的次序（）。

A.与数组a的元素次序相同

B.与数组a的元素次序相反

C.与数组a的元素次序无关

D.以上都不对

正确答案：B

解析：采用头插法建立单链表时，后面的节点插入到最前端，所以

L的节点值次序与数组a的元素次序相反。

9、某算法在含有n(n2l)个节点的单链表中查找值为x节点，其

时间复杂度是()。

A.0(log2n)

B.0(1)

C.0(n2)

D.0(n)

正确答案：D

解析：需要从首节点出发逐一查找每个节点。

10、在长度为n(nNl)的单链表中删除尾节点的时间复杂度为

()O

A.0(1)

B.0(log2n)

C.0(n)

D.0(n2)

正确答案：C

解析：在长度为n(n2l)的单链表中删除尾节点时，需要找倒

数第2个节点，此时时间复杂度为0(n)。

11、关于线性表的正确说法是()。

A.每个元素都有一个前驱和一个后继元素

B.线性表中至少有一个元素

C.表中元素的排序顺序必须是由小到大或由大到小

D.除第一个元素和最后一个元素外，其余每个元素有且仅有一个前

驱和一个后继元素

正确答案：D

解析：线性表属典型的线性结构。

12、以下关于顺序表的叙述中，正确的是（）。

A.顺序表可以利用一维数组表示，因此顺序表与一维数组在结构上

是一致的，它们可以通用

B.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻

C.顺序表和一维数组一样，都可以进行随机存取

D.在顺序表中每一个元素的类型不必相同

正确答案：C

解析：顺序表中所有元素必须连续存放，而一维数组中所有元素

可以不连续存放，另外，一维数组只有按下标的存、取两个操作，

而顺序表可以进行线性表的插入、删除等操作，所以选项A错误。

在顺序表中，逻辑上相邻的元素在物理位置上也一定相邻，所以选

项B错误。顺序表中每一个元素的类型必须相同，所以选项D错误。

13、以下属于顺序表的优点是（）。

A.插入元素方便

B.删除元素方便

C.存储密度大

D.以上都不对

正确答案：C

解析：顺序表的存储密度为1,所以其存储密度大。

14、设线性表中有n个元素，以下运算中，（）在单链表上实现要

比在顺序表上实现效率更高。

A.删除指定位置元素的后一个元素

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

C.顺序输出前k个元素

D.交换第i个元素和第n-i+1个元素的值（i=L2,n）

正确答案：A

解析：在顺序表中插入元素和删除元素时需要移动较多元素，而在

单链表上执行同样的操作不需要移动元素，只需修改相关节点的指

针域。

15、以下关于单链表的叙述中正确的是()。

I.节点除自身信息外还包括指