Relax1000 数据结构 · 第2章 线性表 · 题目¶
第2章 线性表¶
本章 31 题；题目册印刷页 7–11。
Q1¶
线性表是一个（ ）。
- A．有限序列，可以为空
- B．有限序列，不能为空
- C．无限序列，可以为空
- D．无限序列，不能为空
原页版面片段（用于核对图表、公式、矩阵或代码）
Q2¶
（ ）是一个线性表。
- A．由 n 个实数组成的集合
- B．由 100 个字符组成的序列
- C．由所有整数组成的序列
- D．邻接表
原页版面片段（用于核对图表、公式、矩阵或代码）
Q3¶
关于线性表的顺序存储和链式存储，下列说法正确的是（ ）。
- A．链式存储方式存储密度大于顺序存储方式
- B．都支持随机访问
- C．链式存储中，逻辑上相邻的元素在物理上不一定相邻
- D．在 k 个位置进行插入，顺序存储比链式存储更方便
Q4¶
下列选项中，不属于线性表的是（）。
- A．有序表
- B．散列表
- C．队列
- D．栈
Q5¶
下列说法错误的是（ ）。
I．单链表是一种线性表，每个元素都有其前驱和后继
II．单链表的存储密度比顺序表低
III．需要经常修改线性表 L 中的结点值，用链表比较方便
IV．静态链表删除或插入不需要移动元素
- A．III、IV
- B．I、II、III
- C．I、III
- D．I、II、III、IV
Q6¶
下述说法不正确的是（ ）。
- A．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作
- B．稀疏矩阵以三元组表压缩存储后，必会失去随机存取功能
- C．从逻辑结构上看，n 维数组的每个元素均属于 n 个向量
- D．数组也能采用链式存储结构
原页版面片段（用于核对图表、公式、矩阵或代码）
Q7¶
下列关于顺序表的叙述中，正确的是（ ）。
- A．顺序表可以利用一维数组表示，因此顺序表与一维数组在逻辑结构上是相同的
- B．在顺序表中，逻辑上相邻的元素物理位置上不一定相邻
- C．顺序表可以进行随机存取
- D．在顺序表中，每个元素的类型不必相同
原页版面片段（用于核对图表、公式、矩阵或代码）
Q8¶
在双链表的两个结点之间插入一个新结点，需要修改（ ）个指针域。
- A．1
- B．3
- C．4
- D．2
Q9¶
与单链表相比，双链表的优点之一是（ ）。
- A．插入、删除操作更方便
- B．可以进行随机访问
- C．可以省略表头指针或表尾指针
- D．访问前后相邻结点更灵活
Q10¶
一个链表最常用的操作是在末尾插入结点和删除结点，则选用（ ）最节省时间。
- A．带头结点的双循环链表
- B．单循环链表
- C．带尾指针的单循环链表
- D．单链表
Q11¶
设一个链表最常用的操作是在链尾之后插入新结点和删除链表的尾结点，则选（ ）效率最高。
- A．单链表
- B．循环单链表
- C．带链尾指针的循环单链表
- D．带头结点的循环双链表
Q12¶
对于没有尾指针的单链表，将 n 个元素采用头插法建立单链表的时间复杂度为（ ），采用尾插法建立单链表的时间复杂度为（ ）。
- A．〔公式/符号见原页版面片段〕 1
- B．O(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕)
- C．O(〔公式/符号见原页版面片段〕)
- D．O(〔公式/符号见原页版面片段〕2)
原页版面片段（用于核对图表、公式、矩阵或代码）
审计旁注（非原文）：补解析
无尾指针时，头插法建表为 O(n)；尾插法每次需遍历到表尾，总复杂度为 O(n²)。Relax 解析漏印后者。王道回源：result.md [block: b_47_4, b_47_7]。
Q13¶
有一个单向链表，头指针和尾指针分别为 p, q，以下（ ）操作的复杂度会受链表长度的影响。
- A．删除头部元素
- B．删除尾部元素
- C．头部元素之前插入一个元素
- D．尾部元素之后插入一个元素
原页版面片段（用于核对图表、公式、矩阵或代码）
Q14¶
设指针变量 p 指向单链表中结点 A，若删除该结点，则需要修改指针的操作序列为（ ）。
- A．q=p->next; p->data=q->data; p>next=q->next; free(q);
- B．q=p->next; q->data=p->data; p>next=q->next; free(q);
- C．q=p->next; p->next=q->next; free(q)；
- D．q=p->next; p->data=q->data; free(q);
原页版面片段（用于核对图表、公式、矩阵或代码）
Q15¶
不带头结点的单链表，设头指针为 h，指针 s指向插入结点，那么头插的操作应该是（ ）。
- A．h->next = s->next;
- B．s->next = h->next; h->next = s;
- C．s->next = h; h = s;
- D．h->next = s; h = s;
原页版面片段（用于核对图表、公式、矩阵或代码）
Q16¶
设 有 线 性 表 A= 〔公式/符号见原页版面片段〕1 〔公式/符号见原页版面片段〕2 … 〔公式/符号见原页版面片段〕 ,B= 〔公式/符号见原页版面片段〕1 〔公式/符号见原页版面片段〕2 … 〔公式/符号见原页版面片段〕 。 将 线 性 表 A 、 B 交 叉 合 并 为 线 性 表C= 〔公式/符号见原页版面片段〕1 〔公式/符号见原页版面片段〕1 〔公式/符号见原页版面片段〕2 〔公式/符号见原页版面片段〕2 … ，线性表 A、B和 C均以单链表结构存储，A、B 中长度更大的，后续多出的元素全部放在 C 的最后，那么时间复杂度为（ ）。
- A．〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕
- D．以上都错误
原页版面片段（用于核对图表、公式、矩阵或代码）
Q17¶
设有一个长度为 n 的循环单链表，若从表中删除首元结点的时间复杂度达到 0(n)，则此时采用的循环单链表的结构可能是（ ）。
- A．只有表头指针，没有头结点
- B．只有表尾指针，没有头结点
- C．只有表尾指针，带头结点
- D．只有表头指针，带头结点
原页版面片段（用于核对图表、公式、矩阵或代码）
Q18¶
长度为 n的单链表链接在长度为 m的单链表（都为不带头结点只有头指针的单链表）后面的时间复杂度为（ ）。
- A．O(1)
- B．O(n)
- C．O(m)
- D．O(m+n)
原页版面片段（用于核对图表、公式、矩阵或代码）
Q19¶
一个带头结点的非空单链表，结点结构为：{data | next}，其中 next 是指向后继结点的指针，p指针指向该单链表中的一个结点，在 p 指向的结点后插入一个由 s 指针指向的新结点，正确操作是（ ）。
- A．s->next = p; p->next = s;
- B．p->next = s; s->next = p->next;
- C．s->next = s; p->next = s;
- D．s->next = p->next; p->next = s;
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
对带头结点的循环单链表，删除首元结点（非最后一个结点），需要修改（ ）个指针。
- A．0
- B．1
- C．2
- D．3
Q21¶
设线性表中有 2n 个元素，算法（ ）在单链表上实现要比在顺序表上实现效率更高。
- A．删除所有值为 x 的元素
- B．在最后一个元素的后面插入一个新元素
- C．顺序输出前 K 个元素
- D．交换第 i 个元素和第 2n-i-1 个元素的值(i=0，1，…，n-1)
原页版面片段（用于核对图表、公式、矩阵或代码）
Q22¶
下列说法正确的是（ ）。
- A．分配给单链表的内存单元地址必须是连续的
- B．与顺序表相比，在链表中顺序访问所有节点，其算法的效率比较低
- C．从长度为 n 的顺序表中删除任何一个元素，时间复杂度都是 O(1)
- D．向顺序表中插入一个元素，平均要移动大约一半的元素
原页版面片段（用于核对图表、公式、矩阵或代码）
Q23¶
下列说法正确的是（ ）。
I．不带头结点单链表中，无论是插入还是删除元素，都需要找到其前驱
II．删除带头结点的循环双链表中某结点时，只需要修改两个指针域
III．带尾指针的单向循环链表中，删除尾结点的时间复杂度是 O（1）
IV．带头结点不带尾指针的单向循环链表，在链头插入一个元素的时间复杂度是 O（1）V．链式存储结构都是动态申请空间，各元素逻辑上相邻，物理上不一定相邻
- A．I、IV、V
- B．II、IV
- C．III、IV、V
- D．I、II、V
原页版面片段（用于核对图表、公式、矩阵或代码）
Q24¶
在双链表中 p 所指的结点之前插入一个结点 q 的操作为（ ）。
- A．p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;
- B．q->prior=p->prior; p->prior->next=q; q->next=p; p->prior=q->next;
- C．q->next=p; p->next=q; q->prior->next=q; q->next=p;
- D．p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;
原页版面片段（用于核对图表、公式、矩阵或代码）
Q25¶
已知带头结点的非空循环双链表，指针 p 指向链表中非首且非尾的任意一个结点，则执行下列语句序列实现的功能是（ ）。p->pre->pre->next = p; p->next->pre = p->pre; p->pre->next = p->next; p->next = p->pre; p->pre = p->pre->pre; p->next->pre = p;
- A．删除 p 指向的结点
- B．将 p 指向的结点之前的结点插入 p 结点之后
- C．将 p 指向的结点与其后继结点互换
- D．将 p 指向的结点的后继与 p 指向的结点的前驱互换
原页版面片段（用于核对图表、公式、矩阵或代码）
Q26¶
下列操作可以在 O（1）的时间复杂度内完成的是（ ）。
- A．删除仅带头节点的单链表的第 n 个元素
- B．在仅带头结点的单链表末尾添加一个元素
- C．删除只有头指针的单向循环链表的首元结点
- D．删除只带头结点的双向循环链表的首元结点
原页版面片段（用于核对图表、公式、矩阵或代码）
Q27¶
设对 n(n>1)个元素的线性表的运算只有 4 种：①删除第一个元素；②删除最后一个元素；③在第一个元素之前插入新元素；④在最后一个元素之后插入新元素，则最好使用（ ）。
- A．只有尾结点指针没有头结点指针的循环单链表
- B．只有尾结点指针没有头结点指针的非循环双链表
- C．只有头结点指针没有尾结点指针的循环双链表
- D．既有头结点指针又有尾结点指针的循环单链表
Q28¶
带头结点的双向循环链表 L为空表的条件是（ ）。
- A．L->next == L;
- B．L == NULL;
- C．L->next->prior == NULL;
- D．L->prior == NULL;
原页版面片段（用于核对图表、公式、矩阵或代码）
Q29¶
现有一块连续空间能用来保存数据，且常需要插入、删除数据，那么最适合使用（ ） 。
- A．单链表
- B．静态链表
- C．双链表
- D．顺序表
Q30¶
下列关于静态链表的说法中，正确的是（ ）。
I．静态链表兼具顺序表和单链表的优点，因此存取表中第 i个元素的时间与 i 无关
II．静态链表能容纳的最大元素个数在表定义时就确定了，以后不能增加
III．静态链表与动态链表在元素的插入、删除上类似，不需要移动元素
IV．相比动态链表，静态链表可能浪费较多的存储空间
- A．I、II、III
- B．II、III、IV
- C．I、III、IV
- D．I、II、IV
Q31¶
已知表头元素为 c 的单链表在内存中的存储状态如下表所示：下标 元素 链接地址0 a 4 1 b 3 2 c 0 3 d -1 4 e 1删除元素 a 后，数组下标为 0，2 的表项中地址内容为（ ）。
- A．2, 4
- B．-1, 4
- C．-1, 3
- D．-2, 4
原页版面片段（用于核对图表、公式、矩阵或代码）
