2024年3月12日发(作者：)

计算机学科专业基础综合数据结构-1

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

一、单项选择题(总题数：25，分数：74.00)

1.在下列关于线性表的叙述中，正确的是______。

（分数：2.00）

A.线性表的逻辑顺序与物理顺序总是一致的

B.线性表的顺序存储表示优于链式存储表示

C.线性表若采用链式存储表示时，所有存储单元的地址可连续也可不连续

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

解析：[解析] 本题主要考查线性结构的特点和线性表的定义。线性表的顺序存储与链式存储在不同的情况

下各有利弊，无优劣之分。

链式存储表示要求结点内的存储单元一定连续。

2.在线性表中的每一个表元素都是数据对象，它们是不可再分的______。

（分数：2.00）

A.数据项

B.数据记录

C.数据元素 √

D.数据字段

解析：[解析] 线性表是n(n≥0)个数据元素的有限序列。数据记录、数据字段是数据库文件组织中的术语。

数据项相当于数据元素中的属性。

本题考查的依然是线性表的基本定义。

3.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应是______。

（分数：2.00）

A.将n个元素从小到大排序

B.从线性表中删除第i个元素(1≤i≤n)

C.查找第i个元素(1≤i≤n) √

D.在第i个元素后插入一个新元素(1≤i≤n)

解析：[解析] 在顺序存储的线性表中查找第i个元素时可直接访问。

4.下面的叙述正确的是______。

（分数：2.00）

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

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

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

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

解析：[解析] 本题主要考查的知识点是顺序存储结构和链式存储结构中查找一个元素的时间复杂度。顺序

存储的主要优点：可以随机存取表中任一元素，因此，查找第i个元素的时间同i的值无关。而链式存储

结构中只能按顺序查找元素，因此，查找第i个元素的时间同i的值成正比。

我们通过定义可知，顺序表可以随机存取表中任一元素，因此查找第i个元素的时间与i的值无关。

通常查找线性表数据元素的方法有 (①) 和 (②) 两种方法，其中 (①) 是一种只适合于顺序存储结构但 (③)

的方法；而 (②) 是一种对顺序和链式存储结构均适用的方法。（分数：6.00）

A.顺序查找

B.循环查找

C.条件查找

D.折半查找 √

解析：

A.顺序查找 √

B.随机查找

C.折半查找

D.分开查找

解析：

A.效率较低的线性查找

B.效率较低的非线性查找

C.效率较高的非线性查找 √

D.效率较高的线性查找

解析：[解析] 在线性表中查找指定元素采用顺序查找法和折半查找法。顺序查找法属于线性查找，效率较

低，但它适用于用顺序方式或用链接方式存储的线性表；折半查找法仅适用于已排序的顺序存储线性表，

每次根据查找值的大小将查找区间缩小一半继续查找，因此它不是线性查找，它比顺序查找的效率高一些。

若设一个顺序表的长度为n。那么，在表中顺序查找一个值为x的元素时，在等概半的情况下，查找成功

的数据平均比较次数为______。在向表中第i个元素(1≤i≤n+1)位置插入一个新元素时，为保持插入后表

中原有元素的相对次序不变，需要从后向前依次后移______个元素。在删除表中第i个元素(1≤i≤n)时，

同样地，为保持删除后表中原有元素的相对次序不变，需要从从向后依次前移______个元素。（分数：6.00）

A..n

B.n/2

C.(n+1)/2 √

D.(n-1)/2

解析：

A.n-i

B.n-i+1 √

C.n-i-1

D..i

解析：

A.n-i √

B.n-i+1

C.n-i-1

D..i

解析：[解析] 在长度为n的顺序表中，若各元素查找概率相等，则查找成功的平均查找长度为：

在有n个元素的顺序表中的第i个元素位置插入一个新元素时，需把表中从第i个到第n个的元素全部后

移一个元素位置，以空出第i个元素位置供新元素插入，需要移动的元素有n-i+1个，剩下的前n-1个元

素没有移动。

而想要在有n个元素的顺序表中删除第i个元素，需把第i+1个元素到第n个元素全部前移，以填补原来

第i个元素，需要移动n-(i+1)+1=n-i个元素。

5.在长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为______。

（分数：2.00）

A.O(n)

B.O(1) √

C.O(n2)

D.O(log2n)

解析：[解析] 在有n个元素的顺序表的表尾插入一个新元素，可直接在表的第n+1个位置插入，渐进时间

复杂度为O(1)。

6.从一个具有n个结点的有序单链表中查找值等于x的结点时，在查找成功的情况下，需要平均比较的结

点个数为______。

（分数：2.00）

A..n

B.n/2

C.(n-1)/2