2024年4月30日发(作者：)

所有的胜利，与征服自己的胜利比起来，都是微不足道。

第2章 自测卷答案 姓名 班级

题号

一

二

三

四

五

六

七

总分

题分

13

10

10

10

7

10

40

100

得分

一、填空（每空1分

共13分）

1. 【严题集2.2①】在顺序表中插入或删除一个元素

需要平均移动 表中一半元素

具体移动的元素个数与 表长和该元素在表中的位置 有关

2. 线性表中结点的集合是 有限 的

结点间的关系是 一对一 的

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时

需向后移动 n-i+1 个元素

4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时

需向前移动 n-i 个元素

5. 在顺序表中访问任意一结点的时间复杂度均为 O(1)

因此

顺序表也称为 随机存取 的数据结构

6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置 必定相邻

单链表中逻辑上相邻的元素的物理位置 不一定 相邻

7. 【严题集2.2①】在单链表中

除了首元结点外

任一结点的存储位置由 其直接前驱结点的链域的值 指示

8． 在n个结点的单链表中要删除已知结点*p

需找到它的前驱结点的地址

其时间复杂度为O（n）

二、判断正误（在正确的说法后面打勾

反之打叉）（每小题1分

共10分）

（ × ）1. 链表的每个结点中都恰好包含一个指针

答：错误

链表中的结点可含多个指针域

分别存放多个指针

例如

双向链表中的结点可以含有两个指针域

分别存放指向其直接前趋和直接后继结点的指针

（ × ）2. 链表的物理存储结构具有同链表一样的顺序

错

链表的存储结构特点是无序

而链表的示意图有序

（ × ）3. 链表的删除算法很简单