数据结构实践教程-线性表选填

线性表习题集

一、单项选择题

基础概念题

1. 线性表是具有 $n(n \geq 0)$ 个（ ）的有限序列。

   • A. 表示素
   • B. 字符
   • C. 数据元素
   • D. 数据项

   答案：C

2. 最常用的操作是取第 i 个元素和找第 j 个元素的前驱，则线性表采用（ ）存储方式最节省时间。

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

   答案：A

3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

   • A. 顺序表
   • B. 双链表
   • C. 带头结点的双循环链表
   • D. 单循环链表

   答案：A

4. 用数组表示线性表的优点是（ ）。

   • A. 便于插入和删除操作
   • B. 便于随机存取
   • C. 可以动态地分配存储空间
   • D. 不需要占用一片相邻的存储空间

   答案：B

5. 已知顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。

   • A. 110
   • B. 108
   • C. 100
   • D. 120

   答案：B
   计算：100 + (5-1)×2 = 108

6. 下列对线性表描述正确的是（ ）。

   • A. 当线性表的长度变化较大，难以估计其存储规模时，宜采用顺序表结构
   • B. 当线性表的长度变化不大，易于事先确定其大小时，宜采用链表结构
   • C. 线性表的主要操作是查找，很少涉及插入、删除时，宜采用链表结构
   • D. 线性表的主要操作是插入和删除，宜采用链表结构

   答案：D

7. 下面关于线性表的叙述错误的是（ ）。

   • A. 线性表采用顺序存储，必须占用一片连续的存储单元
   • B. 线性表采用顺序存储，便于进行插入和删除操作
   • C. 线性表采用链接存储，不必占用一片连续的存储单元
   • D. 线性表采用链接存储，便于插入和删除操作

   答案：B
   错题分析：顺序存储的插入和删除需要移动大量元素，不便于操作

8. 下列描述线性表的叙述错误的是（ ）。

   • A. 线性表的顺序存储的元素是从小到大顺序排列的
   • B. 线性表的链接存储，便于插入、删除操作
   • C. 除第一个和最后一个元素外，其余每个元素有且仅有一个直接前驱和直接后继
   • D. 线性表可以为空

   答案：A
   错题分析：顺序存储只是物理位置相邻，元素值不一定有序

9. 下面的叙述中正确的是（ ）。

   • A. 线性表在链式存储时，查找第i个元素的时间与i的数值成正比
   • B. 线性表在链式存储时，插入第i个元素的时间与i的数值成反比
   • C. 线性表在链式存储时，插入第i个元素的时间与i的数值无关
   • D. 线性表在顺序存储时，查找第i个元素的时间与i的数值成正比

   答案：A

10. 以下说法错误的是（ ）。

    • A. 求表长，定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
    • B. 顺序存储的线性表可以随机存取
    • C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
    • D. 线性表的链式存储结构优于顺序存储结构

    答案：D
    错题分析：两种存储结构各有优缺点，没有绝对的优劣

时间复杂度与操作特性

1. 在 n 个结点的顺序表中，算法的时间复杂度是 $O(1)$ 的操作是（ ）。

   • A. 访问第 i (1 ≤ i ≤ n) 个结点和求第 i (2 ≤ i ≤ n) 个结点的直接前驱
   • B. 在第 i (1 ≤ i ≤ n) 个结点后插入一个新结点
   • C. 删除第 i (1 ≤ i ≤ n) 个结点
   • D. 将 n 个结点从小到大排序

   答案：A

2. 链表适用于（ ）查找。

   • A. 顺序
   • B. 二分法
   • C. 顺序，也能二分法
   • D. 随机

   答案：A

3. 用链表表示线性表的优点是（ ）。

   • A. 便于随机存取
   • B. 花费的存储空间比顺序表少
   • C. 便于插入与删除
   • D. 数据元素的物理顺序与逻辑顺序相同

   答案：C

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

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

   答案：B

5. 对线性表，在下列情况（ ）下应当采用链表表示。

   • A. 经常需要随机地存取元素
   • B. 经常需要进行插入和删除操作
   • C. 表中元素需要占据一片连续的存储空间
   • D. 表中元素的个数不变

   答案：B

6. 线性表 L 在（ ）情况下适用于使用链式结构实现。

   • A. 需不断删除和插入
   • B. 需经常修改结点值
   • C. 含有大量的结点
   • D. 结点结构复杂

   答案：A

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

   • A. $O(n)$
   • B. $O(1)$
   • C. $O(n^2)$
   • D. $O(\log_2 n)$

   答案：B

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

   • A. $O(1)$
   • B. $O(n)$
   • C. $O(n^2)$
   • D. $O(\log_2 n)$

   答案：B

9. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动元素。

   • A. 64
   • B. $63$
   • C. $63.5$
   • D. $7$

   答案：C
   计算：(0+1+2+…+126)/127 = (126×127/2)/127 = 63.5

链表操作与选择

1. 可以用带表头结点的链表表示线性表，也可以用不带表头结点的链表表示线性表，前者最主要的好处是（ ）。

   • A. 可以加快对表的遍历
   • B. 使空表和非空表的处理统一
   • C. 节省存储空间
   • D. 可以提高存取表元素的速度

   答案：B

2. 在单链表中，增加头结点的目的是（ ）。

   • A. 使单链表至少有一个结点
   • B. 代表开始结点
   • C. 方便运算的实现
   • D. 为了存储其他信息

   答案：C

3. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。

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

   答案：D

4. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用（ ）存储方式最节省运算时间。

   • A. 单链表
   • B. 仅有头结点的单循环链表
   • C. 双链表
   • D. 仅有尾指针的单循环链表

   答案：D

5. 在长度为 $n$ 的（ ）上，删除第一个结点，其算法的时间复杂度为 $O(n)$。

   • A. 只有表头指针的不带表头结点的单循环链表
   • B. 只有表尾指针的不带表头结点的单循环链表
   • C. 只有表尾指针的带表头结点的单循环链表
   • D. 只有表头指针的带表头结点的单循环链表

   答案：B

6. 如果对线性表的常用运算有4种，即删除第一个元素，删除最后一个元素，在第一个元素前插入新元素，在最后一个元素后插入新元素，则最好使用（ ）。

   • A. 只有表尾指针没有表头指针的单循环链表
   • B. 只有表尾指针没有表头指针的非循环单链表
   • C. 只有表头指针没有表尾指针的双循环链表
   • D. 既有表头指针也有表尾指针的单循环链表

   答案：D

7. 在一个长度为 $n(n>1)$ 的单链表上，设有头和尾两个指针，执行（ ）操作与链表的长度有关。

   • A. 删除单链表中的第一个元素
   • B. 删除单链表中的最后一个元素
   • C. 在单链表第一个元素前插入一个新元素
   • D. 在单链表最后一个元素后插入一个新元素

   答案：B

8. 在带有头结点的单链表 HL 中，要向表头插入一个由指针 $p$ 指向的结点，则执行（ ）。

   • A. $p->next=HL; HL=p;$
   • B. $p->next=HL->next; HL->next=p;$
   • C. $p->next=HL; p=HL;$
   • D. $HL=p; p->next=HL;$

   答案：B

9. 在单链表中，已知指针 $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

10. 在一个单链表中，若删除 $p$ 指针所指结点的后继结点，则执行（ ）。

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

    答案：A

双链表与循环链表

1. 与单链表相比，双链表的优点之一是（ ）。

   • A. 插入、删除操作更简单
   • B. 可以进行随机访问
   • C. 可以省略表头指针或表尾指针
   • D. 顺序访问相邻结点更灵活

   答案：D

2. 指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点,要将两个链表链接成一个新的单循环链表,应执行的操作为（ ）。

   • A. p1->next=p2->next; p2->next=p1->next;
   • B. p2->next=p1->next; p1->next=p2->next;
   • C. p=p2->next; p1->next=p; p2->next=p1->next;
   • D. p=p1->next; p1->next=p2->next; p2->next=p;

   答案：D

3. 在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。

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

   答案：C

4. 在双向循环链表结点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

5. 在双向链表存储结构中,删除p所指的结点时须修改指针（ ）。

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

   答案：A

6. 在一个双链表中,删除*p结点之后的一个结点的操作是（ ）。

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

   答案：A

7. 设rear是指向非空带头结点的单循环链表的尾指针,则删除表首结点的操作可表示为（ ）。

   • A. p=rear; rear=rear->next; free§;
   • B. rear = rear -> next -> next; free(rear);
   • C. p = rear -> next -> next; rear -> next -> next = p -> next; free§;
   • D. 以上都不对

   答案：C

8. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

   • A. n
   • B. 2n - 1
   • C. 2n
   • D. n - 1

   答案：A

二、填空题

1. 顺序表中逻辑上相邻的元素物理位置（一定）相邻，单链表中逻辑上相邻的元素物理位置（不一定）相邻。

2. 对一个线性表经常进行的是存取操作，很少进行插入和删除操作时，则采用顺序存储结构为宜；当经常进行的是插入和删除操作时，则采用链式存储结构为宜。

3. 在长度为 $n$ 的顺序表中第 i (1 <= i <= n + 1) 个位置上插入一个数据元素，要移动表中n-i+1个元素。

4. 在长度为 $n$ 的顺序表中删除第 i (1 <= i <= n) 个数据元素，要移动表中n-i个元素。

5. 对于一个长度为 $n$ 的顺序存储的线性表，在表头插入元素的时间复杂度为$O(n)$，在表尾插入元素的时间复杂度为$O(1)$。

6. 对于一个长度为 $n$ 的单链表，在表头插入结点的时间复杂度为$O(1)$，在表尾插入结点的时间复杂度为$O(n)$。

7. 线性表 L = (a_1, a_2, …, a_n) 的存储结构为顺序表，则等概率情况下插入一个元素平均移动（n/2）个元素，等概率情况下删除一个元素平均移动（(n-1)/2）个元素。

8. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较**(n+1)/2**个结点。

9. 在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。

10. 判断一个带有头结点的单链表 L 是否为空的 C 语句是（L->next == NULL）。

11. 对于一个具有 n 个结点的单链表，在已知的结点 * p 后插入一个新结点的时间复杂度为$O(1)$，在给定值为 x 的结点后插入一个新结点的时间复杂度为$O(n)$。

12. 在带尾指针的单循环链表的表尾插入一个新结点的时间复杂度为$O(1)$，删除表尾结点的时间复杂度为$O(n)$。

13. 已知单链表 A 长度为 m，单链表 B 长度为 n，若将 B 连接在 A 的末尾，在没有链尾指针的情形下，算法的时间复杂度应为$O(m)$。

14. 在单向链表 P 指针所指结点之后插入 s 指针所指结点的操作是（s->next = p->next; p->next = s;）。

15. 在无表头结点的单链表 L 的表头插入 s 结点的语句序列是（s->next = L; L = s;）。

16. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共（4）个。

17. 在非空双向循环链表中，在结点 q 的前面插入结点 p 的过程如下：

    p->prior=q->prior;
    q->prior->next=p;
    p->next=q;
    q->prior=p;