1fori0sum
isum1【答案】O

第2章线性表
21选择题
1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间
A）顺序表
B）带头结点的双循环链表
C）单链表
D）带尾结点的单循环链表
【答案】A
2．若长度为
的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为
（）1≤i≤
1。
A）O0B）O1C）O

D）O
2
【答案】C
3．双向链表中有两个指针域，prior和
ext，分别指向前驱及后继，设p指向链表中的一个结点，q
指向一待插入结点，现要求在p前插入q，则正确的插入为（）
A）ppriorqq
extppprior
extqqpriorpprior
B）qpriorppriorpprior
extqq
extpppriorq
ext
C）q
extpp
extqpprior
extqq
extp
D）pprior
extqq
extpqpriorppriorppriorq
【答案】D
4．在一个具有
个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）
A）O
log2
）
B）O1）
C）O
）
D）O
2）
【答案】C
5．在一个以h为头指针的单循环链中，p指针指向链尾结点的条件是（）
A）p
extNULL
B）p
exth
C）p
ext
exth
D）pdata1
【答案】B
6．对于一个具有
个结点的线性表，建立其单链表的时间复杂度是（）
A）O
B）O1C）O
log2
D）O
2
【答案】A
8．在双向链表存储结构中，删除p所指的结点时须修改指针（）
A）pprior
extp
ext
p
extpriorpprior
B）ppriorppriorpriorpprior
extp
C）p
extpriorp
p
extp
ext
ext
D）p
extppriorprior
ppriorp
ext
ext
【答案】A
9．线性表采用链式存储时，其元素地址（）
A）必须是连续的
B）一定是不连续的
C）部分地址是连续的
D）连续与否均可
【答案】D
22填空题
1．线性表L（a1，a2，…，a
）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____________。
f【答案】（
1）2
2．在单链表中设置头结点的作用是_____________。
【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判
断。另外，不论链表是否为空，链表头指针不变。
3．线性表的顺序存储是通过_____________来反应元素之间的逻辑关系，而链式存储结构是通过_____________来反应元素之间的逻辑关系。
【答案】（1）数据元素的前后顺序（2）元素中的指针4．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用_____________存储结构最节省时间，相反当经r