计算机专业基础综合(数据结构)模拟试卷8(题后含答案及解析).pdfVIP

计算机专业基础综合（数据结构）模拟试卷8(题后含答案及解析)

题型有：1.单项选择题2.综合应用题

单项选择题1-40小题，每小题2分，共80分。下列每题给出的四个选项中，

只有一个选项是最符合题目要求的。

1．若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除

第一个结点，则下面最节省运算时间的存储方式是()。

A．单链表

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

C．双链表

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

正确答案：D

解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，

所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针

的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。知识模

块：数据结构

2．已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s

的升序链表，则最坏情况下的时间复杂度是()。

A．D(l)

B．D(ls)

C．D(min(l，s))

D．D(max(l，s))

正确答案：D

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

的次数最少是m和n中的最大值。知识模块：数据结构

3．线性表中存放的主要是()。

A．整型常量

B．字符

C．数据元素

D．信息元素

正确答案：C

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

符型，但对于一个线性表来说，所有的数据元素的类型必须相同。知识模块：

数据结构

4．下面的叙述中正确的是()。I．线性表在链式存储时，查找第i

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

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

值成正比

A．仅Ⅰ

B．仅Ⅱ

C．仅Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

正确答案：A

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

而在顺序存储结构中查找第i个元素的时间与i的位置无关。知识模块：数据结

构

5．对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进

行插入运算，那么应该选择()存储方式最节省时间。

A．顺序表

B．双链表

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

D．单循环链表

正确答案：A

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

序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后

进行插入运算，因此，本题最合适的选项是顺序表。知识模块：数据结构

6．若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方

式中最节省时间的是()。

A．单链表

B．双链表

C．单循环链表

D．顺序表

正确答案：D

解析：本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结

构有顺序表和链表两种，其特点如下：(1)顺序表可以实现随机存取，其时

间复杂度为O(1)。但在顺序表中，进行插入和删除操作需要移动大量的元素，

其时间复杂度为O(n)；(2)链表中只能实现顺序查找，其时间复杂度为O(n)。

但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度

为D(1)。本题中，线性表中常用的操作是取第i个元素，所以应选择随机存

取结构，即顺序表；同时在顺序表中查找第i个元素的前驱也很方便。单链表和

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

能快速查找第i个元素的前驱，但不能实现随机存取。知识模块：数据结构

7．如果线性表中最常用的操作是在最后一个元素之后插入