数据结构 第二章练习题

第1题

关于线性表，下列说法中正确的是（ ）

• A. 线性表中每个元素都有一个直接前驱和一个直接后继
• B. 线性表中任意一对相邻的数据元素之间存在序偶关系
• C. 线性表中的数据元素可以具有不同的数据类型
• D. 线性表中数据元素的类型是确定的

答案：B

解析：

• A 错误。在线性表中，第一个元素没有直接前驱，最后一个元素没有直接后继。
• B 正确。线性表的逻辑结构特征就是元素之间存在着线性的、一对一的相邻关系，可以用序偶（有序对）来表示。
• C 错误。线性表要求所有元素属于相同的数据类型。
• D 也是正确的描述，但B选项描述的是线性表的逻辑结构特征，是“线性”一词的根本含义，比D选项更能体现线性表的本质。在单选题中，B是最佳选项。

第2题

以下（）是一个线性表。

• A. 由n个实数组成的集合
• B. 由所有实数组成的集合
• C. 由所有整数组成的序列
• D. 由n个字符组成的序列

答案：D

解析：

线性表有两个关键特征：有限和有序。

• A. “集合”是无序的，不符合线性表的有序性。
• B. “所有实数”是无限的，不符合线性表的有限性。
• C. “所有整数”是无限的，不符合线性表的有限性。
• D. “n个字符组成的序列”是有限且有序的，符合线性表的定义。

第3题

已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（ ）

• A. 108
• B. 180
• C. 176
• D. 112

答案：D

解析：

数组元素的地址计算公式为：$LOC(a_i) = LOC(a_1) + (i-1) * L$，其中 L 是每个元素占用的存储空间大小。

根据题意，$LOC(a_9) = 144, i = 9, L = 4$。

代入公式：$144 = LOC(a_1) + (9-1) * 4$

$144 = LOC(a_1) + 8 * 4$

$144 = LOC(a_1) + 32$

$LOC(a_1) = 144 - 32 = 112$。

第4题

在一个长度为n的顺序表的第i（1 ≤ i ≤ n+1）个元素之前插入一个元素，需向后移动（ ）个元素。

• A. n-i
• B. n-i+1
• C. n-i
• D. n-i+1

答案：B 或 D

解析：

当在第i个位置插入一个新元素时，从原来的第i个元素到最后一个元素（第n个元素）都需要向后移动一个位置。

需要移动的元素包括 $a_i$, $a_{i+1}$, …, $a_n$。

移动的元素个数为 n - i + 1。

（选项B和D内容相同）

第5题

下述哪一条（）是顺序存储结构的优点？

• A. 存储密度大
• B. 插入运算方便
• C. 删除运算方便
• D. 可方便地用于各种逻辑结构的存储表示

答案：A

解析：

• A 正确。顺序存储结构将数据元素存放在一片连续的存储空间里，不需要额外的空间来存储元素之间的逻辑关系（如指针），因此存储密度高。
• B, C 错误。顺序表的插入和删除操作平均需要移动半数元素，时间复杂度为O(n)，效率较低。
• D 错误。顺序存储结构主要适用于线性结构，对于树、图等复杂的非线性结构表示起来不方便。

第6题

顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（）可分配的存储空间。

• A. m个
• B. m个连续的
• C. n+m个
• D. n+m个连续的

答案：D

解析：

系统做法是将原来的n个元素放到新分配的n+m个空间的前n个位置。

第7题

对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为（）。

• A. O(n)， O(n)
• B. O(n)， O(1)
• C. O(1)， O(n)
• D. O(1)， O(1)

答案：C

解析：

• 访问元素：顺序存储的线性表（数组）支持随机访问，可以通过下标直接计算出元素的地址，所以时间复杂度为O(1)。
• 增加元素：增加（插入）一个元素时，平均需要移动表中一半的元素，最坏情况下（在表头插入）需要移动所有n个元素，所以时间复杂度为O(n)。

第8题

n个结点的线性表采用数组实现，算法的时间复杂度是O(1)的操作是（ ）

• A. 访问第i个结点（1 ≤ i ≤ n）和求第i个结点的直接前趋（2 ≤ i ≤ n）
• B. 在第i个结点后插入一个新结点（1 ≤ i ≤ n）
• C. 删除第i个结点（1 ≤ i ≤ n）
• D. 以上都不对

答案：A

解析：

• A 正确。访问第i个结点是O(1)。求第i个结点的直接前驱就是访问第i-1个结点，同样可以通过地址计算直接得到，也是O(1)。
• B, C 错误。插入和删除操作都需要移动后续元素来填补或腾出空间，时间复杂度为O(n)。

第9题

线性表的链接存储结构是一种（）的存储结构。

• A. 随机存取
• B. 顺序存取
• C. 索引存取
• D. 散列存取

答案：B

解析：

在链式存储结构中，要访问第i个元素，必须从头指针开始，沿着指针域逐个结点向后查找，这是一种顺序存取的方式。它不支持随机存取。

第10题

线性表采用链接存储时，其地址（ ）

• A. 必须是连续的
• B. 部分地址必须是连续的
• C. 一定是不连续的
• D. 连续与否均可以

答案：D

解析：

链式存储的优点就是利用不连续的内存单元来存储数据，各个结点的物理地址可以是任意的，既可以是连续的，也可以是不连续的。由操作系统动态分配。

第11题

在单链表中附加头结点的目的是为了（ ）

• A. 保证单链表中至少有一个结点
• B. 标识单链表中首结点的位置
• C. 方便运算的实现
• D. 说明单链表是链式存储

答案：C

解析：

附加头结点后，对第一个数据结点的操作（如插入、删除）就和对其他结点的操作统一了，都变成了在某个结点之后的操作。同时，对空表和非空表的处理也得到了统一。这极大地简化了代码逻辑，方便了运算的实现。

第12题

链表不具有的特点是（ ）。

• A. 可随机访问任一元素
• B. 插入、删除不需要移动元素
• C. 不必事先估计存储空间
• D. 所需空间与线性表长度成正比

答案：A

解析：

链表最大的缺点就是不支持随机访问。要访问某个元素，必须从头开始顺序遍历。B、C、D都是链表的显著特点。

第13题

在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入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;

答案：B

解析：

要在q和p之间插入s，需要两步操作：

1. 让新结点s的指针指向p，即 s->next = p;

2. 让q结点的指针指向s，即 q->next = s;

   为了防止p结点的地址丢失，正确的执行顺序应该是先执行s->next = p;，再执行q->next = s;。但题目只问执行的操作集合，B选项包含了正确的两个操作。

第14题

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

• A. O(1)
• B. O(n)
• C. O(n²)
• D. O(nlog₂n)

答案：B

解析：

该操作分为两步：

1. 查找：从头开始遍历链表，找到合适的插入位置。平均需要比较 n/2 个元素，最坏情况要比较n个元素，所以查找的时间复杂度是O(n)。

2. 插入：找到位置后，修改指针的插入操作本身是O(1)。

   总的时间复杂度由耗时最长的部分决定，即O(n)。

第15题

设线性表有n个元素，以下操作中（）在顺序表上实现比在链表上实现的效率更高。

• A. 输出第i（1≤i≤n）个元素值
• B. 交换第1个和第2个元素的值
• C. 顺序输出所有n个元素
• D. 查找与给定值x相等的元素在线性表中的序号

答案：A

解析：

A. 输出第i个元素值（即随机访问），顺序表是O(1)，链表是O(n)。顺序表效率远高于链表。

B. 交换元素，两者都是O(1)。

C. 顺序输出，两者都需要遍历所有元素，都是O(n)。

D. 查找元素，两者都需要顺序比较，都是O(n)。

第16题

单循环链表的主要优点是（ ）

• A. 不再需要头指针了
• B. 从表中任一结点出发都能扫描到整个链表
• C. 已知某个结点的位置后，能够容易找到它的直接前趋
• D. 在进行插入、删除操作时，能更好地保证链表不断开

答案：B

解析：

由于循环链表的最后一个结点的指针域指向头结点（或第一个结点），形成了一个环。这使得我们可以从链表中的任意一个结点开始，都能遍历到整个链表。而C选项是双向链表的优点。

第17题

若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。

• A. 顺序表
• B. 单链表
• C. 双链表
• D. 单循环链表

答案：A

解析：

• 取第i个元素：顺序表是O(1)，而所有链表都是O(n)。

• 找第i个元素的前趋：就是取第i-1个元素，顺序表依然是O(1)，而所有链表都是O(n)。

  综合来看，顺序表对于这两个操作的效率最高。

第18题

若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节省时间。

• A. 单链表
• B. 带头指针的单循环链表
• C. 双链表
• D. 带尾指针的单循环链表

答案：D

解析：

这个操作模式是典型的队列（队尾入队，队头出队）。

使用带尾指针R的单循环链表是实现队列的高效方式：

• 删除第一个结点（出队）：第一个结点是 R->next，删除它只需要修改指针，是O(1)操作。

• 在最后一个结点后插入（入队）：在尾结点R之后插入，也只需修改指针，是O(1)操作。

  其他选项在执行这两个操作时，至少有一个是O(n)的。

第19题

若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方法最节省运算时间。

• A. 单链表
• B. 循环双链表
• C. 单循环链表
• D. 带尾指针的单循环链表

答案：B

解析：

这个操作模式是典型的栈（在同一端插入和删除）。

• 在最后一个结点后插入：需要访问最后一个结点。

• 删除最后一个结点：需要访问最后一个结点和它的前驱结点。

  要同时高效地实现这两个操作，需要能快速定位到尾结点和它的前驱。

• 循环双链表（带尾指针）能满足要求：通过尾指针直接定位到最后一个结点是O(1)，通过尾结点的prior指针找到其前驱也是O(1)。因此插入和删除都是O(1)。

• D选项虽然能快速定位尾结点，但在单链表中找其前驱需要O(n)时间。

第20题

在循环双链表的p所指结点后插入s所指结点的操作是（ ）。

• A. p->next = s; s->prior = p; p->next->prior = s; s->next = p->next;
• B. p->next = s; p->next->prior = s; s->prior = p; s->next = p->next;
• C. s->prior = p; s->next = p->next; p->next = s; p->next->prior = s;
• D. s->prior = p; s->next = p->next; p->next->prior = s; p->next = s;

答案：D

解析：

在p和p->next之间插入s，需要建立四个链接关系：

1. s的前驱指向p：s->prior = p;
2. s的后继指向p原来的后继：s->next = p->next;
3. p原来的后继的前驱指向s：p->next->prior = s;
4. p的后继指向s：p->next = s;

分析D选项的执行顺序：

1. s->prior = p; // s指向p

2. s->next = p->next; // s指向p的原后继

3. p->next->prior = s; // p的原后继指向s，此时p的next指针还没变，所以p->next仍然是原来的后继结点。

4. p->next = s; // p指向s

   这个顺序是完整且正确的，不会丢失结点。而C选项中第3步p->next = s;执行过早，会导致第4步p->next->prior=s;（此时已变成s->prior=s）出错。