Relax1000 数据结构 · 第2章 线性表 · 解析¶
第2章 线性表¶
本章 31 题；解析册印刷页 10–14。
速对答案（原书）： A B C B C A C C D A D （CD） B A C D A C D B A D B D B D C A B B D
Q1¶
速对表原值： A
详细解析标注： A
由数据结构的有穷性可以知道，线性表必须是有限序列。若元素个数为 0，表示线性表空。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q2¶
速对表原值： B
详细解析标注： B
A错误，集合不是线性表，而是另一种逻辑结构，线性表有前驱后继的数据关系。
C 错误，不满足有穷性，线性表必须是有限序列。
D 错误，邻接表是表示非线性关系的存储结构。
注意：线性表各数据元素必须是同一类型。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q3¶
速对表原值： C
详细解析标注： C
A 错误，存储密度=有效存储空间/全部空间。链式存储中，需要引入指针来记录元素的前驱后继关系，所以存储密度更低。
B 错误，链式存储只支持顺序存取，顺序存储两种都支持。
C 正确，这是链式存储结构的特点。
D 错误，两者时间复杂度都是 O(n)，顺序表的时间开销在移动，链表的时间开销在遍历。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q4¶
速对表原值： B
详细解析标注： B
线性表由有限个相同类型的元素组成的序列，元素之间是一对一的有前驱后继的线性关系。A、C、D 都属于线性表，栈和队列是受限的线性表，有序表是元素之间按序排放的线性表。散列表不属于线性表。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q5¶
速对表原值： C
详细解析标注： C
I 错误，头尾分别没有前驱和后继；II 正确，单链表的存储密度比顺序表低，存储密度是指一个节点数据本身所占的存储空间和整个结点所占的存储空间之比，单链表存储密度小于 1；III 错误，经常添加或者删除用链表比较方便，修改结点值链表复杂度为 O（n）。IV 正确，只需要修改静态链表中的指针即可。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q6¶
速对表原值： A
详细解析标注： A
A错误，数组一旦确定，数据元素的容量和位置关系就是固定的，因此不能进行插入和删除等操作；注意和顺序表进行区分，顺序表是线性表的顺序存储，是物理结构，是可以增删改查的。
B 正确，稀疏矩阵压缩存储后，不能直接根据元素所在数组中的位置在内存中定址，也就意味着失去了随机存取功能；
C 正确，n 维数组的任一个元素在每一维上都有确定的位置，该维上的所有元素构成一个向量；
D 正确，数组虽然适合采用顺序存储，但在一些特殊场合，如稀疏矩阵为了节约空间，用链式存储（十字链表法）也是一种必要的选择。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q7¶
速对表原值： C
详细解析标注： C
A错误，顺序表是顺序存储的线性表，表中所有元素的类型必须相同，且必须连续存放。一维数组中的元素可以不连续存放，数组是一种扩展的逻辑结构；一维数组就是线性表，多维数组等价于多个线性表。（注意这个数组是逻辑结构的概念，注意和编程语言中的数组区分）。
B 错误，在顺序表中，逻辑上相邻的元表物理位置上也相邻。
C 正确，顺序表可以进行按下标存取，即支持随机存取。
D 错误，每个元素的类型必须相同，这是数据结构的性质。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q8¶
速对表原值： C
详细解析标注： C
当在双链表的两个结点(分别用第一个、第二个结点表示)之间插入一个新结点时，需要修改四个指针域，分别是：新结点的前驱指针域，指向第一个结点； 新结点的后继指针域，指向第二个结点； 第一个结点的后继指针域，指向新结点；第二个结点的前驱指针域，指向新结点。（删除修改 2 个即可）
Q9¶
速对表原值： D
详细解析标注： D
在插入和删除操作上，单链表和双链表都不用移动元素，都很方便，但双链表修改指针的操作更为复杂，A 错误。双链表中可以快速访问任何一个结点的前驱和后继结点，D 正确。
Q10¶
速对表原值： A
详细解析标注： A
在链表的末尾插入和删除一个结点时，需要修改其相邻结点的指针域。而寻找尾结点及尾结点的前驱结点时，只有带头结点的双循环链表所需要的时间最少。
Q11¶
速对表原值： D
详细解析标注： D
在链表中链尾插入新节点需要找到链尾指针，所以提供尾指针最合适，而删除尾结点通常需要找到尾结点的前驱结点，只有 D 选项可以在 O（1）时间复杂度完成两种操作。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q12¶
速对表原值： （CD）
详细解析标注： C、D
因为每次插入都要遍历找到尾结点，没有尾指针的单链表头插法建立的复杂度为 n×O(1)=O(n)，尾插法建立的复杂度为。
原页版面片段（用于核对图表、公式、矩阵或代码）
审计旁注（非原文）：补解析
无尾指针时，头插法建表为 O(n)；尾插法每次需遍历到表尾，总复杂度为 O(n²)。Relax 解析漏印后者。王道回源：result.md [block: b_47_4, b_47_7]。
Q13¶
速对表原值： B
详细解析标注： B
B 删除尾部元素，需要找到尾部元素的前一个元素，与链表长度有关。
Q14¶
速对表原值： A
详细解析标注： A
首先用指针变量 q 指向结点 A 的后继结点 B，然后将结点 B 的值复制到结点 A中，最后删除结点 B。
Q15¶
速对表原值： C
详细解析标注： C
B 选项是带头结点的单链表头插相关操作；C 选项是头插的操作。
Q16¶
速对表原值： D
详细解析标注： D
其本质是依次遍历 A、B，每次各取一个元素间隔插入 C。所以间隔插入的时间复杂度是〔公式/符号见原页版面片段〕 ，多余的只需要一次指针的修改，链接在 C 后面即可，所以时间复杂度为〔公式/符号见原页版面片段〕 ，答案选 D。
注意：〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕 ，但是〔公式/符号见原页版面片段〕 并不等价
原页版面片段（用于核对图表、公式、矩阵或代码）
Q17¶
速对表原值： A
详细解析标注： A
在循环单链表中，删除首元结点后，要保持链表的循环性，因此需要找到首元结点的前驱。当链表带头结点时，其前驱就是头结点，因此不论是表头指针还是表尾指针，删除首元结点的时间都为 O(1)。当链表不带头结点时，其前驱是尾结点，因此，若有表尾指针，就可在 0(1)的时间找到尾结点；若只有表头指针，则需要遍历整个链表找到尾结点，时间为 0(n)。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q18¶
速对表原值： C
详细解析标注： C
要把长度为 n 的单链表链接在长度为 m 的单链表后面，那么首先需要找到长度为m 的单链表尾结点，时间开销为 O(m)。再进行 O(1)的链接操作。所以本题选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q19¶
速对表原值： D
详细解析标注： D
为了使 p 的后继不丢失，我们要先处理 s->next=p->next。再用 p->next=s；
注意：指针是一种变量类型，这个类型的存储的内容是它指向数据的地址，结构体中，要用“->”表示他指向结点的内部数据项。如果是结构体本身，那么用 node.next 的 “.” 来表示内部的数据项。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
速对表原值： B
详细解析标注： B
删除首元结点，只需执行如下操作：p=head->next; head->next=head->next->next; free(p)；所以只需要修改一个指针：head 的 next 指针。
注意：带头结点的循环链表尾结点的 next 指针是指向头结点，而非首元结点，要注意这个细节。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q21¶
速对表原值： A
详细解析标注： A
对于 A，在单链表和顺序表上实现的时间复杂度都为 O(n)，但后者要移动很多元素，所以在单链表上实现效率更高些。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q22¶
速对表原值： D
详细解析标注： D
A 错误。分配给单链表的内存单元地址可以是不连续的。
B 错误。在顺序表和链表上顺序访问所有节点，时间复杂度均为 O(n)。
C 错误。删除最后一个元素所需时间是 O(1)。但从长度为 n 的顺序表中删除任一个元素，平均时间复杂度是 O(n)。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q23¶
速对表原值： B
详细解析标注： B
I 错误，首元结点（链表中第一个存储有效数据的结点）没有前驱，其删除不需要找到前驱。II 正确，删除修改 2 个指针，在 p、q 两非空结点后插入 s 要修改 4 个指针。III 错误，删除尾结点需要找到尾结点的前驱，因此要 O（n）时间遍历到其前驱结点。IV 正确，要注意的细节是带头结点的循环单链表中，尾结点的 next 始终指向头结点，无需修改尾结点的指针V 错误，静态链表是用数组表示各结点的前后关系，非动态申请空间。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q24¶
速对表原值： D
详细解析标注： D
具体过程如下图所示：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q25¶
速对表原值： B
详细解析标注： B
假设初始状态如下所示，p 指向的结点为 p 结点（p 指针忽略），p 的前驱为pre1，p 的前驱的前驱为 pre2，p 的后继节点为 next。至此六条指令执行完，可知完成的操作是 p 和和其前驱进行调换。答案选 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q26¶
速对表原值： D
详细解析标注： D
选项 A、B、C 的时间复杂度均为是 O(n)。选项 C 中，需要通过遍历链表才可以找到末尾元素，然后才能正确地设置末尾元素的 next 结点。D 的时间复杂度是 O（1），可以通过首元素的 prior 指针找到链表的末尾元素，然后设置相应的指针指向。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q27¶
速对表原值： C
详细解析标注： C
删除最后一个元素，要找到最后一个元素的前驱结点，所以单链表时无法实现O(1)的时间复杂度，排除 A、D。非循环双链表，无法通过尾结点找到头结点或者首元结点（第一个携带有效信息的结点），所以 B 不能 O(1)实现插入和删除第一个元素，排除。因此正确答案是 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q28¶
速对表原值： A
详细解析标注： A
双向循环链表L为空表时的结构如下图所示，L的next和prior都指向本身，只有A 选项满足条件。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q29¶
速对表原值： B
详细解析标注： B
静态链表用数组来表示线性表的链式存储结构，需要事先申请一片较大的连续的空间。且插入和删除只需要改编表项的指针编号，无需移动元素，方便插入和删除。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q30¶
速对表原值： B
详细解析标注： B
静态链表的存储空间虽然是顺序分配的，但元素的存储不是顺序的，查找时仍然需要按链依次进行，而插入、删除都不需要移动元素。静态链表的存储空间是一次性申请的，能容纳的最大元素个数在定义时就已确定。由于并非每个空间都存储了元素，因此会造成存储空间的浪费。
Q31¶
速对表原值： D
详细解析标注： D
原链表为 c->a->e->b->d->NULL，现在删除 a，那么变为 c->e->b->d->NULL，-1表示指向 NULL，-2 表示空表项（如果空表项也是-1 的话，分配新的结点无法找到空闲的表项，原理类似 OS 里的 FAT 表），所以应该把 a 所在的表项 0 中的地址改为-2，把 c 所在的表项 2 中的地址改为 4（指向 e）。如果最后一个结束的结点和空结点都用-1 表示，如果要插入一个元素，就无法分辨哪个是空闲的结点哪个是已分配的尾部结束结点，所以一般用-2 表示空闲结点，D 正确。
原页版面片段（用于核对图表、公式、矩阵或代码）
