数据结构部分习题.pdf

数据结构部分习题

第二章线性表

一、问答题
1、简述下列术语：线性表，顺序表，链表。
2、何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?
3、在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个
因素?
4、链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定
要在物理上是相邻的?
二、单选题
1、在表长为n的单链表中,算法时间复杂度为O(n)的操作是()。
A.查找单链表中第i个结点
B.在p结点之后插入一个结点
C.删除表中第一个结点
D.删除p结点的直接后继结点
2、在下列链表中不能从当前结点出发访问到其余各结点的是()。
A.单链表B.单循环链表
C.双向链表D.双向循环链表
3、线性表采用顺序存储时，其地址()
A．必须是连续的B．部分地址必须是连续的
C．一定是不连续的D．连续与否均可以
4、线性表采用链式存储结构时，其地址()
A．必须是连续的B．部分地址必须是连续的
C.一定是不连续的D．连续与否均可以
5、在长度为n的顺序表的第i个数据元素(1≤i≤n)之前插入一个数据元素,元素的移动次数
为()。
A.n-i+1B.n-iC.iD.i-1
6、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()。
A.顺序表B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表D.单链表
7、在需要经常查找结点的前驱与后继的场合中，使用()比较合适。
A．单链表B．双向链表
C．单循环链表D．循环链表
8、在一个单链表h中，若要删除由指针q所指向结点的直接后继结点，则执行（）。
A．p=q->next;p->next=q->next;
B．p=q->next;q->next=p;
C．p=q->next;q->next=p->next;
D．q->next=q->next->next;q->next=q;9、
9、链表不具有的特点是（）。
A．可随机访问任一元素
B．插入删除不需要移动元素
C．不必事先估计存储空间

D．所需空间与线性表长度成正比
10、对于一个头指针为h的带表头结点单链表，判定其为空表的条件是()。
A.h==NULL；B．h->next==NULL；
C．h!=NULL；D．h->next==h；
11、在非空单链表中，在p结点后插入一个q结点依次执行操作是()。
A.q->link=p;p->link=q；
B.q->link=p->link;p->link=q；
C.q->link=p->link；p=q；
D.p->link=q；q->link=p；
12、以下关于线性表的叙述中，正确的是()。
A.顺序表可以随机存取
B.链表可以随机存取
C.顺序表便于动态处理
D.顺序表便于插入或删除数据元素
13、在非空的单循环链表h中，某个p结点为尾结点的条件是()。
A.p==NULL；B．p->link==NULL；
C．h!=NULL；D．p->link==h；
14.设p结点是带表头结点双向循环链表的表中结点,在p结点后插入s结点语句序列中正确
的是()
A.s->next=p->next；p->next->prior=s；
p->next=s；s->prior=p；
B.p->next=s；s->next=p->next；
p->next->prior=s；s->next=p；
C.p->next=s；p->next->prior=s；
s->next=p->next；s->next=p；
D.p->next->prior=s；p->next=s；
s->next=p->next；s->next=p；

15、设p结点是带表头结点的双循环链表的表中结点，在p结点之前插入s结点的语句序列
中正确的是()。
A.s->prior=p->prior；p->prior->next=s；
p->prior=s；s->next=p；
B.p->prior=s；p->prior->next=s；
s->prior=p->prior；s->next=p；
C.p->prior->next=s；p->prior=s；
s->prior=p->prior；s->next=p；
D.p->prior=s；s->next=p；
p->prior->next=s；s->prior=p->prior；

16、以下关于静态链表的叙述中，错误的是()。
Ⅰ静态链表既有顺序存储的优点又有动态链表的优点，所以它存取表中第i个元素的时间
与i无关。
Ⅱ.静态链表能容纳的最多元素个数在表定义时就确定了，以后不能增加。
Ⅲ.静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

A.只有ⅠB.只有