数据结构第二章试题 .pdf
数据结构第二章试题
第2章线性表
一、选择题
1.链表不具备的特点是（）。
A．可随机访问任意结点B.插入删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与其长度成正比
2.不带头结点的单链表head为空的判定条件是（）。
A.head==NULL
B.head-next==NULL
C.head-next==head
D.head!=NULL
3.带头结点的单链表head为空的判定条件是（）。
A.head==NULL
B.head-next==NULL
C.head-next==head
D.head!=NULL
4．带头结点的双循环链表L为空表的条件是（）。
A．L==NULLB．L-next-==NULLC．L-prior==NULL
D.L-next==L
5.非空的循环链表head的尾结点（由P所指向）满足（）。
A．p-next==NULLB．p==NULLC．p-next==head
D.p==head
6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。
A．p-prior=s;s-next=p;p-prior-next=s;s-prior=p-p
rior;
B．p-prior=s;p-prior-next=s;s-next=p;s-prior=p-pr
ior;
C．s-next=p;s-prior=p-prior;p-prior=s;p-right-nex
t=s;
D.
s-next=p;s-prior=p-prior;p-prior-next=s;p-prior=s;
7.若某表最常用的操作是在最后一个结点之后插入一个结点或删
除最后一个结点，则采用（）存储方式最节省运算时间。
A．单链表B．给出表头指针的单循环链表
C．双链表D.带头结点的双循环链表
8.某线性表最常用的操作是在最后一个结点之后插入一个节点或
删除第一个结点，故采用（）存储方式最节省运算时间。
A．单链表B．仅有头结点的单循环链表
C．双链表D.仅有尾指针的单循环链表
9.需要分配较大空间，插入和删除不需要移动元素的线性表，其
存储结构是（）。
A．单链表B．静态链表C．线性链表D.顺序存储结构
10.如果最常用的操作是取第i个结点及前驱，则采用（）存储方
式最节省时间。
A．单链表B．双链表C.单循环链表D.顺序表
11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保
持有序的时间复杂度是（）。
A．O(1)B．O(n)C．O(n*n)D.O(nlog2n)
12.在一个长度为n(n1)的单链表上，设有头和尾两个指针，执
行()操作与链表的长度有关。A．删除单链表中的第一个元素B．删除
单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
13.设线性表有n个元素，以下算法中，()在顺序表上实现比在链
表上实现效率更高。A．输出第i(0=i=n-1)个元素值B．交换第0
个元素与第1个元素的值
C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
14.设线性表有2n个元素，算法()，在单链表上实现比在顺序表上
实现效率更高。
A．删除所有值为x的元素B．在最后一个元素的后面插入一个新
元素
C.顺序输出前k个元素
D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)
15.与单链表相比，双链表的优点之一是()。
A．插入、删除操作更简单B．可以进行随机访问
C.可以省略表头指针或表尾指针
D.顺序访问相临结点更灵活
16.如果对线性表的运算只有4种