习题
一、选择题
1.对于线性表，在下面哪种情况下应当采用链表表示？（ ）
A.经常需要随机地存取元素
B.表中元素需要占据一片连续的存储空间
C.经常需要进行插入和删除操作
D.表中元素的个数不变
2.在带有头结点的单链表L中，要向表头插入一个由指针p指向的结点，则需执行（ ）。
A.p->next=L->next;L->next=p;
B.p->next=L;L=p;
C.p->next=L;p=L;
D.L=p;p->next=L;
3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）。
A.O（log2n）
B.O（1）
C.O（n）
D.O（n2）
4.若一个线性表中最常用的操作是存取第i个元素和查找第i个元素的前驱元素，则采用（ ）存储方式最节省时间。
A.顺序表
B.单链表
C.双向链表
D.单循环链表
5.在一个长度为n的顺序表（顺序表中元素的序号从1到n）中，在第i个元素之前插入一个新元素时，需向后移动（ ）个元素。
A.n-i
B.n-i+1
C.n-i-1
D.i
6.非空的循环单链表head的尾结点p满足（ ）。
A.p->next==head
B.p->next==NULL
C.p==NULL
D.p==head
7.在双向循环链表中，在p指针所指向的结点后插入一个指针q所指向的新结点，修改指针的操作是（ ）。
A.p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B.p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C.q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D.q->next=p->next;q->prior=p;p->next=q;p->next=q;
8.在一个长度为n的带头结点的单链表L中，设有尾指针r，则执行（ ）操作与链表的表长有关。
A.删除单链表中的第一个元素
B.在单链表中第一个元素前插入新元素
C.删除单链表中的最后一个元素
D.在单链表最后一个元素后插入新元素
9.在一个长度为n的顺序表中删除第i个元素，需要向前移动（ ）个元素。
A.n-i
B.n-i+1
C.n-i-1
D.i+1
10.在双向链表存储结构中，删除p指向的结点时修改指针的操作是（ ）。
A.p->prior->next=p->next;p->next->prior=p->prior;
B.p->prior=p->prior->prior;p->prior->next=p;
C.p->next->prior=p;p->next=p->next->next;
D.p->next=p->prior->prior;p->prior=p->next->next;
11.在具有n个结点的单链表上查找值为e的元素时，其时间复杂度为（ ）。
A.O（n）
B.O（1）
C.O（n2）
D.O（n-1）
12.一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（ ）。
A.98
B.100
C.102
D.106
13.在单链表中，指针p指向元素为e的结点，实现删除e的后继的语句是（ ）。
A.p=p->next;
B.p->next=p->next->next;
C.p->next=p;
D.p=p->next->next;
14.顺序表中，插入一个元素所需移动的元素平均数是（ ）。
A.（n-1）/2
B.n
C.n+1
D.（n+1）/2
15.循环链表的主要优点是（ ）。
A.不再需要头指针
B.已知某结点位置后能容易找到其直接前驱
C.在进行插入、删除运算时能保证链表不断开
D.在表中任一结点出发都能扫描整个链表
16.不带头结点的单链表head为空的判定条件是（ ）。
A.head==NULL
B.head->next==NULL
C.head->next==head
D.head!=NULL
17.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指向结点之后插入上述链表应执行的语句为（ ）。
A.q->next=s->next；s->next=p；
B.s->next=p；q->next=s->next；
C.p->next=s->next；s->next=q；
D.s->next=q；p->next=s->next；
18.在一个单链表中，已知q所指向结点是p所指向结点的前驱结点，若在q和p之间插入一个结点s，则执行（ ）。
A.s->next=p->next;p->next=s;
B.p->next=s->next;s->next=p;
C.q->next=s;s->next=p;
D.p->next=s;s->next=q;
二、算法分析题
1.函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。其中结点结构为
。
2.函数实现单链表的插入算法，请在空格处将算法补充完整。
3.函数ListDelete实现删除顺序表中某一元素的算法，请在空格处将算法补充完整。
4.函数实现单链表的删除算法，请在空格处将算法补充完整。
5.写出算法的功能。
三、算法设计题
1.编写算法，实现带头结点的单链表的逆置算法。
2.有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。
3.编写算法，将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。
4.设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
5.已知有两个顺序表A和B，A中的元素按照递增排列，B中的元素按照递减排列。试编写一个算法，将A和B合并成一个顺序表，使其按照递增有序排列，要求不占用额外的存储单元。
6.已知有两个带头结点的单链表A和B，A和B中的元素由小到大排列，设计一个算法，求A和B的交集C，将A和B中相同的元素插入到C中。
7.将一个无序的单链表变成一个有序的单链表，要求按照从小到大排列并且不占用额外的存储空间。
8.已知一个双向循环链表L，设计算法实现将双向循环链表L的所有结点逆置。
9.顺序表A和顺序表B的元素都是非递减排列，利用线性表的基本运算，将它们合并成一个顺序表C，要求C也是非递减排列。例如，A=（6，11，11，23），B=（2，10，12，12，21），则C=（2，6，10，11，11，12，12，21，23）。
10.已知一个整数序列A=（a0，a1，…，an-1），其中0≤ai＜n（0≤i＜n）。若存在ap1=ap2=…=apm=x且m＞n/2（0≤pk＜n，1≤k≤m），则称x为A的主元素。例如A=（0，5，5，3，5，7，5，5），则5为主元素；又如A=（0，5，5，3，5，1，5，7），则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：
（1）给出算法的基本设计思想。
（2）根据算法设计思想，采用C语言描述算法。
（3）说明算法的时间复杂度和空间复杂度。
11.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如图2.41所示。
图2.41 存储映像
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：
（1）给出算法的基本设计思想。
（2）根据算法设计思想，采用C语言描述算法。
（3）说明算法的时间复杂度。