第1关：选择题、填空题、判断题
任务描述
本关任务：学习完线性表后，应掌握线性表相关的基础知识。
线性表知识点归纳
(1)线性表是由n(n≥0)个数据元素组成的有限序列，所有元素的性质相同，元素之间呈现线性关系，即除开始元素以外，每个元素只有唯一的前驱，除终端元素以外，每个元素只有唯一的后继。
(2)在线性表中，通过序号来唯一标识一个元素，所以同一个线性表中可以存在值相同的元素。
(3)顺序表采用数组存放元素，既可以顺序查找，也可以随机查找(对于给定的序号i，在常量时间内找到对应的元素值)。
(4)分配给顺序表的所有内存单元地址必须是连续的。
(5)当从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时需向前移动n-i个元素，所以删除算法的时间复杂度为O(n)。
(6)在一个长度为n的顺序表中插入第i个元素(1≤i≤n+1)时需向后移动n-i+1个元素，所以插入算法的时间复杂度为O(n)。
(7)链表由若干内存结点构成，结点的次序由地址确定，通过指针域反映数据的逻辑关系。
(8)一个链表的所有结点的地址既可以连续，也可以不连续。
(9)对链表只能顺序查找，不能随机查找，即给定序号i，不能在常量时间内找到对应的结点。
(1O)对链表插入或删除结点不需要移动结点，只需要调整相应结点的指针域。
(11) 在单链表中存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的后继结点。
(12)在带头结点的单链表中，通常用头结点指针标识整个单链表;在不带头结点的单链表中，通常用首结点指针标识整个单链表。
(13)单链表只能按从前向后一个方向遍历。
(14)在单链表中，插入一个新结点需要找到插入位置的前驱结点，通过修改两个指针域来实现。如插入一个新结点作为第i个结点，需要查找到第i-1个结点p，然后在结点p的后面插入新结点。
(15)在单链表中，删除一个结点需要找到该结点的前驱结点，只需要修改一个指针域。如删除第i个结点，需要查找到第i-1个结点p，然后删除结点p的后继结点。
(16)双链表可以按从前向后、从后向前两个方向遍历。
(17)在双链表中，插入一个新结点需要找到插入位置的前驱结点或者后继结点，通过修改4个指针域来实现。如插入一个新结点作为第i个结点，需要查找到第i-1个结点p，然后在结点p的后面插入新结点;或者查找到第i个结点q，然后在结点q的前面插入新结点。
(18)在双链表中，删除一个结点通过该结点就可以直接实现，只需要修改两个指针域。如删除第i个结点，只需要查找到第i个结点p，然后通过修改其前驱和后继结点的相应指针域来删除它。
(19)循环链表分为循环单链表和循环双链表，循环单链表的结点构成一个查找环路，循环双链表的结点构成两个查找环路。
(2O)在循环单链表中没有指针域为空的结点。
(21)在循环双链表中可以通过O(1)的时间找到尾结点，删除它的时间复杂度为O(1)。
(22)线性表除了顺序表和链表两类存储结构以外，还可以设计成静态链表，静态链表采用静态空间分配方式，其中元素采用链表方式操作。静态链表不再具有随机查找特性。
(23)有序表是一种按元素值有序排列的线性表，可以采用顺序表或链表存储。
(24)长度分别为n、m的两个有序表采用二路归并方法合并成的一个有序表的时间复杂度为O(n+m)，这是一种高效的方法。
开始你的任务吧，祝你成功！
习题及答案
1、正确选项：A
线性表是（ ）。
A、
一个有限序列，可以为空
B、
一个有限序列，不可以为空
C、
—个无限序列，可以为空
D、
一个无限序列，不可以为空
2、正确选项：B
在一个长度为n的顺序表中向第i个元素（1≤i≤n+1)之前插入一个新元素时需要向后移动（ ）个元素。
A、
n-i
B、
n-i+1
C、
n-i-1
D、
i
3、正确选项：B
一个顺序表所占用存储空间的大小与( )无关。
A、
顺序表的长度
B、
顺序表中元素的数据类型
C、
顺序表中元素各数据项的数据类型
D、
顺序表中各元素的存放次序
4、正确选项：C
顺序表具有随机存取特性指的是( )。
A、
査找值为x的元素与顺序表中元素的个数n无关
B、
查找值为x的元素与顺序表中元素的个数n有关
C、
查找序号为i的元素与顺序表中元素的个数n无关
D、
查找序号为i的元素与顺序表中元素的个数n有关
5、正确选项：B
顺序表和链表相比存储密度较大，这是因为( ) 。
A、
顺序表的存储空间是预先分配的
B、
顺序表不需要增加指针来表示元素之间的逻辑关系
C、
链表的所有结点是连续的
D、
顺序表的存储空间是不连续的
6、正确选项：A
链表不具有的特点是 ( ) 。
A、
可随机访问任一元素
B、
插入、删除不需要移动元素
C、
不必事先估计存储空间
D、
所需空间与线性表长度成正比
7、正确选项：D
当线性表采用链式存储结构时，各结点之间的地址 。
A、
必须是连续的
B、
一定是不连续的
C、
部分地址必须是连续的
D、
连续与否均可以
8、正确选项：D
在线性表的下列存储结构中，读取指定序号的元素所花费时间最少的是 ( )。
A、
单链表
B、
双链表
C、
循环链表
D、
顺序表
9、正确选项：D
若线性表最常用的运算是存取第i个元素及其前驱元素值，则采用（） 存储方式节省时间。
A、
单链表
B、
双链表
C、
循环单链表
D、
顺序表
10、正确选项：C
对于含有n个元素的顺序表，其算法的时间复杂度为O(1)的操作是（）。
A、
将n个元素从小到大排序
B、
删除第i个元素（1≤i≤n）
C、
查找第i个元素
D、
在第i个元素之后插入一个元素
11、正确选项：A
设某个线性表有n个元素，在以下运算中，( )在顺序表上实现比在链表上实现效率更高。
A、
输出第i个元素（1≤i≤n）值
B、
交换第1个元素与第2个元素的值
C、
顺序输出所有n个元素的值
D、
求第1个值为x的元素的逻辑序号
12、正确选项：C
以下关于单链表的叙述正确的是( )。
(1) 结点除自身信息以外还包括指针域，存储密度小于顺序表
(2) 找第i个结点的时间为O(1)
(3) 在插入、删除运算时不必移动结点
A、
仅(1)、(2)
B、
仅(2)、(3)
C、
仅(1)、(3)
D、
(1)、(2)、(3)
13、正确选项：B
通过含有n(n≥1)个元素的数组a，采用头插法建立一个单链表L，则L中结点值的次序( )。
A、
与数组a的元素次序相同
B、
与数组a的元素次序相反
C、
与数组a的元素次序无关
D、
以上都不对
14、正确选项：B
在单链表中，若p结点不是尾结点，在其后插入s结点的操作是( )。
A、
s->next=p;
p->next=s;
B、
s->next=p->next;
p->next=s;
C、
s->next=p->next;
p=s;
D、
p->next=s;
s->next=p;
15、正确选项：D
在一个含有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为( )。
16、正确选项：D
在一个单链表中，删除p结点（非尾结点）之后的一个结点的操作是( )。
A、
p->next=p
B、
p->next->next=p->next
C、
p->next->next=p
D、
p->next=p->next->next
17、正确选项：A
在单链表中删除p所指结点的后继结点，该算法的时间复杂度是( )。
18、正确选项：D
与单链表相比，双链表的优点之一是( )。
A、
插入、删除操作更简单
B、
可以进行随机访问
C、
可以省略表头指针或表尾指针
D、
访问前后相邻结点更方便
19、正确选项：A
在长度为n(n≥1)的双链表L中，在p结点所指结点之前插入一个新结点的时间复杂度为( )。
20、正确选项：A
在长度为n(n≥1)的双链表L中，删除尾结点的时间复杂度为( )。
21、正确选项：A
在长度为n(n≥1)的双链表L中，删除p所指结点的时间复杂度为( )。
22、正确选项：A
在长度为n(n≥1)的双链表L中，删除p所指结点的前驱结点的时间复杂度为( )。
23、正确选项：A
在不带头结点的循环单链表L中，至少有一个结点的判断条件是( )。
A、
L!=NULL
B、
L->next!=L
C、
L->next==L
D、
L->next==NULL
24、正确选项：D
在不带头结点的循环单链表L中，尾结点p的判断条件是( )。
A、
L!=NULL
B、
L->next!=L
C、
p==NULL
D、
p->next==L
25、正确选项：B
在带头结点的循环单链表L中，至少有一个结点的判断条件是（ ）。
A、
L->next!=NULL
B、
L->next!=L
C、
L->next==NULL
D、
L->next==L
26、正确选项：D
在带头结点的循环单链表L中，尾结点p的判断条件是（ ） 。
A、
L->next!=NULL
B、
L->next!=L
C、
p==NULL
D、
p->next==L
27、正确选项：A
在只有尾结点指针rear没有头结点的非空循环单链表中，删除开始结点的时间复杂度为（ ）。
28、正确选项：A
在长度为n（n≥1）的循环双单链表L中，删除尾结点的时间复杂度为( )。
29、正确选项：D
某线性表最常用的运算是在尾元素之后插入元素和删除尾元素，则以下( )
存储方式最节省运算时间。
A、
单链表
B、
循环单链表
C、
双链表
D、
循环双链表
30、正确选项：D
某线性表最常用的运算是在尾元素之后插入元素和删除开始元素，则以下（ ）存储方式最节省运算时间。
A、
单链表
B、
仅有头结点指针的循环单链表
C、
双链表
D、
仅有尾结点指针的循环单链表
31、正确选项：C
如果对含有n(n≥1)个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用 （ ） 。
A、
只有尾结点指针没有头结点的循环单链表
B、
只有尾结点指针没有头结点的非循环双链表
C、
只有首结点指针没有尾结点指针的循环双链表
D、
既有头指针也有尾指针的循环单链表
32、正确选项：D
以下关于有序表的叙述正确的是（ ）。
A、
有序表只能采用顺序表存储
B、
有序表中元素之间的关系是非线性关系
C、
有序表只能采用链表存储
D、
有序表既可以采用顺序表存储，也可以采用链表存储
33、正确选项：A
将两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的元素比较次数是（ ）。
A、
n
B、
2n-1
C、
2n
D、
n-1
34、正确选项：D
将两个长度分别为n、m的递增有序顺序表归并成一个有序顺序表，其元素最多的比较次数是 ( )(MIN表示取最小值）。
A、
n
B、
m+n
C、
MIN(m,n)
D、
m+n-1
35、正确答案：
填空1：指针、指针域
在线性表的链式存储结构中，元素之间的逻辑关系是通过▁▁▁决定的。
填空1答案：
指针
36、正确答案：
填空1：(n-1)/2
在有n个元素的顺序表中删除任意一个元素所需移动元素的平均次数为▁▁▁。
填空1答案：
(n-1)/2
37、正确答案：
填空1：n-i
在一个长度为n(n≥1)的顺序表中删除第i个元素（1≤i≤n)时需向前移动 ▁▁▁ 个元素。
填空1答案：
n-i
38、正确答案：
填空1：n/2
在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为 ▁▁▁ 。
填空1答案：
n/2
39、正确答案：
填空1：L->next==NULL
带头结点的单链表L为空的判定条件是 ▁▁▁ 。
填空1答案：
L->next==NULL
40、正确答案：
填空1：pre=pre->next
填空2：pre->next=p->next、pre->next=pre->next->next
以下算法是删除带头结点的单链表L中所指的结点并释放它，请填空。
bool Delp(LinkNode* &L, LinkNode* p) {
LinkNode *pre = L;
while (pre->next != p)
▁▁▁ ;
if (pre == NULL)
return false;
else {
▁▁▁ ;
free§;
return true;
}
}
填空1答案：
pre = pre->next
填空2答案：
pre->next = p->next
41、正确答案：
填空1：O(m+n)、O(n+m)
两个长度分别为m、n的有序单链表，在采用二路归并算法产生一个有序单链表时，算法的时间复杂度为 ▁▁▁ 。
填空1答案：
O(m+n)
42、正确选项：错误
在一个含有n(n≥1)个元素的线性表中，所有元素值不能相同。
正确
错误
43、正确选项：错误
顺序表具有随机存取特性，所以查找值为x的元素的时间复杂度为O(1)。
正确
错误
44、正确选项：错误
线性表(含n个元素）的基本运算之一是删除第i个元素，其中i的有效取值范围是0≤i≤n-1。
正确
错误
45、正确选项：错误
顺序表采用一维数组存放线性表中的元素，所以顺序表与一维数组是等同的。
正确
错误
46、正确选项：错误
在含有n个结点的单链表L中，将p所指结点（非首结点）与其前驱结点交换，时间复杂度为O(1)。
正确
错误
47、正确选项：正确
在含有n个结点的双链表L中，将p所指结点（非首结点）与其前驱结点交换，时间复杂度为O(1)。
正确
错误
48、正确选项：正确
在含有n个结点的双链表L中删除p所指的结点，时间复杂度为O(1)。
正确
错误
49、正确选项：错误
在循环单链表中，从表中任一结点出发都可以通过指针前后移动操作遍历整个循环链表。
正确
错误
50、正确选项：错误
在含有n个结点的循环单链表L中删除p所指结点（非首结点）的前驱结点，时间复杂度为O(1)。
正确
错误
51、正确选项：错误
从长度为n的顺序表中删除任何一个元素所需要的时间均为O(n)。
正确
错误
52、正确选项：正确
在单链表中删除一个结点，首先需要找到该结点的前驱结点。
正确
错误
53、正确选项：正确
在循环单链表中没有为空的指针域。
正确
错误
54、正确选项：错误
线性表的顺序存储结构总是优于链式存储结构。
正确
错误
55、正确选项：正确
对于单链表来说，需要从头结点出发才能扫描表中的全部结点。
正确
错误
56、正确选项：正确
对于循环单链表来说，从表中任一结点出发都能扫描整个链表。
正确
错误
