习题2

2.1 选择题

（1）线性表是具有n个________的有限序列（n≠0）。

A.表元素 B.字符

C.数据元素 D.数据项

（2）顺序表的存储结构是一种________的存储结构。

A.随机存取 B.顺序存取

C.索引存取 D.HASH存取

（3）在一个长度为n的顺序表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动________个元素。

A.n-i B.n-i+1

C.n-i-1 D.i

（4）链表是一种采用________存储结构存储的线性表。

A.顺序 B.链式

C.星式 D.网状

（5）下面关于线性表的叙述错误的是________。

A.线性表采用顺序存储方式，必须占用一片连续的存储空间

B.线性表采用链式存储方式，不必占用一片连续的存储空间

C.线性表采用链式存储方式，便于插入和删除操作的实现

D.线性表采用顺序存储方式，便于插入和删除操作的实现

（6）设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用________存储方式最节省运算时间。

A.单向链表 B.单向循环链表

C.双向链表 D.双向循环链表

（7）设指针q指向单链表中的结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为________。

A.s->next=p->next；p->next=-s； B.q->next=s； s->next=p；

C.p->next=s->next；s->next=p； D.p->next=s；s->next=q；

（8）设指针变量p指向单链表结点A，则删除结点A的后继结点B的操作为________。

A.p->next=p->next->next B.p=p->next

C.p=p->next->next D.p->next=p

（9）在一个以h为头的单循环链表中，p指针指向链尾的条件是________。

A.p->next=h B.p->next=NULL

C.p->next->next=h D.p->data=-1

（10）对于只在首尾两端进行插入操作的线性表，宜采用的存储结构为________。

A.顺序表 B.用头指针表示的单循环链表

C.单链表 D.用尾指针表示的单循环链表

2.2 填空题

（1）线性表是n个元素的_____________________________。

（2）线性表的存储结构有_____________________________。

（3）设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。

（4）设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。

（5）若频繁地对线性表进行插入与删除操作，该线性表应采用______________存储结构。

（6）链式存储结构中的结点包含________________域和_______________域。

（7）在双向链表中，每个结点有两个指针域，一个指向_________，另一个指向_________。

（8）对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。

（9）设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。

（10）设指针变量p指向单链表中的结点A，则删除结点A后继结点（假设存在）的语句序列为：

s=p->next；p->next=___________; free(s);

2.3 将一顺序表A中的元素逆置。例如，原来顺序表A中元素是100，90，80，70，60，50，40，逆置以后为40，50，60，70，80，90，100。要求算法所用的辅助空间要尽可能地少。用非形式算法描述，并编写C语言程序。

2.4 编写一算法输出已知顺序表A中元素的最大值和次最大值。用非形式算法描述，并编写C语言程序。

2.5 设一顺序表中元素值递增有序。写一算法，将元素x插到表中适当的位置，并保持顺序表的有序性。

2.6 设有两个按元素值递增有序的顺序表A和B（单链表A和B），编一程序将A表和B表归并成一个新的递增有序的顺序表C（单链表C）（值相同的元素均保留在C表中）。

2.7 设有两个线性表A和B，皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的线性表C，使C为A和B的交集，且C中元素也递增有序。