数据结构与算法上机作业
第二章线性表
f一、选择题
1、若长度为
的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间
复杂度为
C
。
AOlog2

BO1
CO

DO
2
2、以下关于线性表的说法中，不正确的是B
。
A线性表中的数据元素可以是数字、字符、结构等不同类型
B线性表中包含的数据元素个数不是任意的C线性表中的每一个结点都有且只有一个直接前驱和直接后继D存在这样的线性表：表中各结点都没有直接前驱和直接后继
3、在有
个结点的顺序表上做插入、删除结点运算的时间复杂度为B
。
AO1
BO

CO
2
DOlog2

4、等概率情况下，在有
个结点的顺序表上做插入结点操作，需平均移动的结点数目为
C。
A
B
12C
2
D
12
5、在一个长度为
的顺序存储的线性表中查找值为x的元素时，平均查找长度及x同元素
的平均比较次数，假定查找每个元素的概率都相等为
C。
A
B
2
C
12D
12
6、在顺序表中，只要知道
A，就可以求出任一结点的存储地址。
A基地址
B结点大小
C向量大小
D基地址和结点大小
7、将两个各有
个元素的有序表归并为一个有序表，其最少的比较次数是A
。
A
B2
1
C2

D
1
8、线性表采用链表存储时其存储地址要求D
。
A必须是连续的
B部分地址必须是连续的
C必须是不连续的
D连续的和不连续的都可以
9、下面关于线性表的描述中，错误的是B
。
A线性表采用顺序存储，必须占用一片连续的存储单元
B线性表采用顺序存储，便于进行插入和删除操作
C线性表采用链式存储，不必占用一片连续的存储单元
D线性表采用链式存储，便于插入和删除操作
10、向具有
个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是A
AO1
BO

CO
2
DOlog2

11、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的
语句是
D
。
AHLpp
extHL
Bp
extHLHLp
Cp
extHLpHL
Dp
extHL
extHL
extp
12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是C。
Apq
extp
extq
ext
Bpq
extq
extp
Cpq
extq
extp
ext
Dq
extq
ext
extq
extq
13、设有编号为1234的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序
为D。
A1234
B1243
C1324
D1423
f14、4个元素按ABCD顺序进入S栈，执行两次PopSx运算后，栈顶元素的值是B。
AABBCCDD15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存r