计算机专业基础综合数据结构(线性表)-试卷1 .pdf

计算机专业基础综合数据结构（线性表）-试卷1

(总分：72.00，做题时间：90分钟)

一、单项选择题(总题数：21，分数：42.00)

1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）

解析：

2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算

时间的存储方式是()。

（分数：2.00）

A.单链表

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

C.双链表

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

解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头

指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是

O(1)，所以答案是D。

3.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的

时间复杂度是()。

（分数：2.00）

A.O(l)

B.O(ls)

C.O(min(l，s))

D.O(max(l，s))√

解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中

的最大值。

4.线性表中存放的主要是()。

（分数：2.00）

A.整型常量

B.字符

C.数据元素√

D.信息元素

解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性

表来说，所有的数据元素的类型必须相同。

5.下面的叙述中正确的是()。I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线

性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时

间同i的值成正比

（分数：2.00）

A.仅I√

B.仅Ⅱ

C.仅Ⅲ

D.I、Ⅱ、Ⅲ

解析：解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中

查找第i个元素的时间与i的位置无关。

6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择()

存储方式最节省时间。

（分数：2.00）

A.顺序表√

B.双链表

C.带头结点的双循环链表

D.单循环链表

解析：解析：线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但

顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序

表。

7.若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式中最节省时间的是()。

（分数：2.00）

A.单链表

B.双链表

C.单循环链表

D.顺序表√

解析：解析：本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，

其特点如下：(1)顺序表可以实现随机存取，其时间复杂度为O(1)。但在顺序表中，进行插入和删除操作

需要移动大量的元素，其时间复杂度为O(n)；(2)链表中只能实现顺序查找，其时间复杂度为O(n)。但链

表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为O(1)。本题中，线性表中

常用的操作是取第i个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第i个元素的前

驱也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也不方便：双链表虽然能

快速查找第i个元素的前驱，但不能实现随机存取。

8.如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式

最节省运算时间。

（分数：2.00）

A.单链表

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

C.双链表

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

解析：解析：最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环

链表。

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

（分数：2.00）

A.问题的规模

B.待处理数据的初态

C.A和B√

D.以上都不正确

解析：解析：此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待

处理数据的初态，所以选C。A和B都不全面。

10.关于链表的特点，下面的叙述中不正确的是()。

（分数：2.00）

A.插入、删除运算方便

B.可实现随机访问