C.改变第i个元素的值（1<=i<=n） D.在第i个元素后插入一个新元素（1<=i<=n）
4.下列关于线性表说法正确的是（ ）。
Ⅰ.顺序存储方式只能用于存储线性结构
Ⅱ.取线性表的第i个元素的时间同i的大小有关
Ⅲ.静态链表需要分配较大的连续空间，插入和删除不需要移动元素
Ⅳ.在一个长度为n的有序单链表中插入一个新结点并仍保持有序的时间复杂度为O（n）
Ⅴ.若用单链表来表示队列，则应该选用带尾指针的循环链表
A.Ⅰ、Ⅱ B.Ⅰ、Ⅲ、Ⅳ、Ⅴ C.Ⅳ、Ⅴ D.Ⅲ、Ⅳ、Ⅴ
5.设线性表中有2n个元素，（）在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第2n-i-l个元素的值（i=0,…,n-1）
6.在一个单链表中，已知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;
7.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是（ ）。
A.O
（1） B.O（n） C.O（n2-------） D.O（nlog2------n）
8.将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度釆用大O形式表示应该是（）。
A.O
（1） B.O（n） C.O（m） D.O（n+m）
9.单链表中，增加一个头结点的目的是为了（ ）。
A.使单链表至少有一个结点 B.标识表结点中首结点的位置
C.方便运算的实现 D.说明单链表是线性表的链式存储
10.在一个长度为n的带头结点的单链表h上，设有尾指计r，则执行（）操作与链表的表长有关。
A.删除单链表中的第一个元素
B.删除单链表中最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
11.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）；对于不带头结点的单链表，则判定空表的条件为（）。
A.head==NULL B.head->next=NULL
C.head->next==head D.head!
=NULL
12.下面关于线性表的一些说法中，正确的是（ ）。
A.对一个设有头指针和尾指针的单链表执行删除最后一个元素的操作与链表长度无关
B.线性表中每个元素都有一个直接前趋和一个直接后继
C.为了方便插入和删除数据，可以使用双链表存放数据
D.取线性表第i个元素的时间同i的大小有关
13.某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则釆用（）存储方式最省时间。
A.单链表 B.仅有头指针的单循环链表
C.双链表 D.仅有尾指针的单循环链表
14.在双链表中向p所指的结点之前插入一个结点q的操作为（）。
A. p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;
B.q->prior=p->prior;p->prior->next=q;q->next=p;p->priop=q->next;
C.q->next=p;p->next=q;q->prior->next=q;q->next=p;
D.p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;
15.在双向链表存储结构中，删除p所指的结点时必须修改指针（）。
A.p->llink->rlink=p->rlink;p->rlink->llink=p->llink;
B.p->llink=p->llink->llink;p->llink->rlink=p;
C.p->rlink->llink=p;p->rlink=p->rlink->rlink;
D.p->rlink=p->llink->llink;p->llink=p->rlink->rlink;
16.在长度为n的有序单链表中插入一个新结点，并仍然保持有序的时间复杂度是（）。
A.O
（1） B.O（n） C.O（n2---------） D.O（nlog2--------n）
17.与单链表相比，双链表的优点之一是（ ）。
A.插入、删除操作更方便 B.可以进行随机访问
C.可以省略表头指针或表尾指针 D.访问前后相邻结点更灵活
18.带头结点的双循环链表L为空的条件是（ ）。
A.L->prior==L&&L->next==NULL
B.L->prior==NULL&&L->next==NULL
C.L->prior==NULL&&L->next==L
D.L->prior==L&&L->next==L
19. 一个链表最常用的操作是在末尾插入结点和删除结点，则选用（）最节省时间。
A.带头结点的双循环链表 B.单循环链表
C.带尾指针的单循环链表 D.单链表
20.设对n（n>1）个元素的线性表的运算只有4种：
删除第一个元素；删除最后一个元素；在第一个元素之前插入新元素；在最后一个元素之后插入新元素，则最好使用（）。
A.只有尾结点指计没有头结点指针的循环单链表
B.只有尾结点指针没有头结点指针的非循环双链表
C.只有头结点指针没有尾结点指针的循环双链表
D.既有头结点指针也有尾结点指针的循环单链表
21. —个链表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则选用（）最节省时间。
A.不带头结点的单循环链表 B.双链表
C.不带头结点且有尾指针的单循环链表 D.单链表
22.静态链表中指针表示的是（ ）。
A.下一元素的地址 B.内存储器地址
C.下一个元素在数组中的位置 D.左链或右链指向的元素的地址
23.需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为（）。
A.单链表 B.静态链表 C.顺序表 D.双链表
二、综合应用题
1.设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。
2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。
3.设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
4.试编写在带头结点的单链表L中删除一个最小值结点的高效算法（假设最小值结点是唯一的）。
5.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O
（1）。
6.有一个带头结点的单链表L，设计一个算法使其元素递增有序。
7.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有大于最小值小于最大值的元素（若存在）。
8.给定两个单链表，编写算法找出两个链表的公共结点。
9.给定一个带表头结点的单链表，设head为头指针，结点的结构为（data, next），data为整型元素，next为指针，试写出算法：
按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：
不允许使用数组作为辅助空间）。
10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。
11.设C={a1,b1,a2,b2,…,an,bn}为线性表，釆用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1,a2,…,an},B={bn,…,b2,b1}
12.在一个递增有序的线性表中，有数值相同的元素存在。
若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。
例如（7,10,10,21,30,42,42,42,51,70）将变作（7,10,21,30,42,51,70）。
13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
14.设A和B是两个单链表（带头结点），其中元素递增有序。
设计一个算法从A和B中公共元素产生单链表C，要求不破坏A、B的结点。
15.已知两个链表A和B分别表示两个集合，其元素递增排列。
编制函数，求A与B的交集，并存放于A链表中。
16.两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。
17.设计一个算法用于判断带头结点的循环双链表是否对称。
18.有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2链接到链表h1之后，要求链接后的链表仍保持循环链表形式。
19.设有一个带头结点的循环单链表，其结点值均为正整数。
设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。
20.设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针）、data（数据）和next（后继指针）域外，还有一个访问频度域freq。
在链表被启用前，其值均初始化为零。
每当在链表中进行一次Locate（L,x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的前面，以便使频繁访问的结点总是靠近表头。
试编写符合上述要求的Locate（L,x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
21.【2009年计算机联考真题】
已知一个带有表头结点的单链表，结点结构为
假设该链表只给出了头指针list。
在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。
若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。
要求：
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，釆用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。
22.【2012年计算机联考真题】
假定釆用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。
设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。
要求：
1）给出算法的基本设计思想。
2）根据设计思想，釆用C或C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度。
答案与解析
一、单项选择题
1.B
两种存储结构有不同的适用场合，不能简单地说谁好谁坏，Ⅰ错误。
链式存储用指针表示逻辑结构，而指针的设置是任意的，故可以很方便地表示各种逻辑结构；顺序存储则只能用物理上的邻接关系来表示逻辑结构，Ⅱ正确。
在顺序存储中，插入和删除结点需要大量的移动元素，效率较低，Ⅲ的描述刚好相反。
顺序存储结构既可以随机存取也能顺序存取，而链式结构只能进行顺序存取，Ⅳ正确。
2. B
要求较快速地插入和删除，排除A、D。
散列存储通过散列函数映射到物理空间，不能反映数据之间的逻辑关系，排除C。
链式存储中的静态链表满足这一要求。
3. C
对n个元素进行排序的时间复杂度最快也要O（n）（初始有序），通常是O（nlog2---------n）或O（n2------）。
在顺序表中删除第i个元素，或在第i个元素之后插入一个新元素，如想保持其它元素原来的顺序，时间复杂度为O（n），因此A、B、D均错误。
在顺序存储的线性表中更改第i个元素的值，直接用下标访问并重新赋值即可，时间复杂度为O
（1）。
4. D
顺序存储方式同样适合图和树的存储，如满二叉树的顺序存储，Ⅰ错误。
若线性表釆用顺序存储方式，则取其第i个元素的时间与i的大小无关，Ⅱ错误。
Ⅲ是静态链表的特有性质。
单链表只能顺序查找插入位置，时间复杂度为O（n），若为顺序表，可釆用折半查找，时间复杂度可降至O（log2-------n）,Ⅳ正确。
队列需要在表头删除元素，表尾插入元素，故釆用带尾指针的循环单链表较为方便，插入和删除的时间复杂度都是O
（1），Ⅴ正确。
5. A
A中对于单链表和顺序表上实现的时间复杂度都为O（n），但后者要移动很多元素，所以在单链表上实现效率更高。
B和D效率刚好相反，C无区别。
6. C
s插入后，q成为s的前驱，而p成为s的后继，选项C满足此条件。
7. D
若先建立链表，然后依次直接插入建立有序表，则每插入一个元素就需遍历链表寻找插入位置，此即链表的插入排序，时间复杂度为O（n2-----）。
若先将数组排好序，然后建立链表，建立链表的时间复杂度为O（n），而数组排序的最少时间复杂度为O（nlog2-----------n），故时间复杂度为O（nlog2----------n）。
本题问最少时间复杂度，故选D。
8. C
先遍历长度为m的单链表，找到这个长度为m的单链表的尾结点，然后将其next域置为另一个单链表的首结点，其时间复杂度为O（m）。
9. C
单链表设置头结点的目的是为了方便运算的实现，主要好处体现在：
第一，有头结点后，插入和删除数据元素的算法统一了，不再需要判断是否在第一个元素之前插入或删除第一个元素；第二，不论链表是否为空，链表指针不变。
10. B
删除单链表的最后一个结点需要置其前驱结点的指针域为NULL，故需要的时间为O（n），与表长有关。
其他操作均与表长无关，读者可以自行模拟。
11. B,A
在带头结点的单链表中，头指针head指向头结点，头结点的next域指向第1个元素结点，head->next==NULL表示该单链表为空。
在不带头结点的单链表中，head直接指向第1个元素结点，head==NULL表示该单链表为空。
12. C
双链表能很方便地访问前驱和后继，故删除和插入数据较为方便。
A显然错误。
B表中第一个元素和最后一个元素不满足题设要求。
D未考虑顺序存储的情况。
B、C、D在删除尾结点时，都需要先查找其前驱结点，时间复杂度为O（n）。
13. D
在最后一个元素之后插入元素，需要先找到最后一个元素，故A、B和C的时间复杂度均为O（n）。
B因为没有特殊的指针指示头结点或尾结点，故需从某一结点向固定的方向顺序依次搜索插入和删除的位置，时间复杂度也为O（n）。
D的两种算法的时间复杂度都是O
（1），如下图所示。
14. D
为了在p之前插入结点q，可以将p的前一个结点的next域指向q，将q的next域指向p，将q的prior域指向p的前一个结点，将p的prior域指向q。
仅D满足条件。
15. A
与上一题的分析基本类似，只不过这里是删除一个结点，注意将p的前、后两结点链接起来。
注，请读者仔细对比上述两题，弄清双链表的插入和删除的方法。
16. B
假设单链表递增有序（递减的情况同理），在插入数据为x的结点之前，先要在单链表中找到第一个大于x的结点的直接前驱p，在p之后插入该结点。
查找过程的时间复杂度为O（n），插入过程的时间复杂度为O
（1），因此时间复杂度为O（n）。
17. D
在双链表中可以快速访问任何一个结点的前后相邻结点，而在单链表中只能快速访问任何一个结点的后继结点。
18. D
循环单链表L判空的条件是头结点（头指针）的prior和next域都指向它自身。
19. A
在链表的末尾插入和删除一个结点时，需要修改其相邻结点的指针域。
而寻找尾结点以及尾结点的前驱结点，只有带头结点的双循环链表所需要的时间最少。
20. C
对于A，删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O（n）。
对于B，删除首结点*p时，需要找到*p结点，这里没有直接给出头结点指针，而通过尾结点的prior指针找到*p结点的时间复杂度为O（n）。
对于D，删除尾结点*p时，需要找到*p的前一个结点，时间复杂度为O（n）。
对于C，执行这4种算法的时间复杂度均为O
（1）。
21. C
对于A，在最后一个元素之后插入一个元素的情况与普通单链表相同，时间复杂度为O（n）；而删除表中第一个元素时，为保持单循环链表的性质（尾结点的指计指向第一个结点），需要首先遍历整个链表找到尾结点，然后再执行删除操作，时间复杂度也为O（n）。
对于B，双链表的情况与单链表的相同，一个是O（n），一个是O
（1）。
对于C，与A的分析对比，因为已经知道了尾结点的位置，省去了遍历链表的过程，因此插入和删除的时间复杂度均为O
（1）。
对于D，要在最后一个元素之后插入一个元素，需要遍历整个链表才能找到插入位置，时间复杂度为O（n）；删除第一个元素的时间复杂度为O
（1）。
22. C
静态链表中的指针又称游标，指示下一个元素在数组中的下标。
23. B
静态链表用数组表示，因此需要预先分配较大的连续空间，静态链表同时还具有一般链表的特点，即插入和删除不需要移动元素。
二、综合应用题
1.解答：
设f（L，x）的功能是删除以L为首结点指针的单链表中所有值等于x的结点，则显然有f（L->next,x）的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点。
由此，可以推出递归模型如下：
终止条件：
f（L,x）≡不做任何事情; 若L为空表或只有一个结点
f（L,x）≡删除*L结点;f（L->next,x）; 若L->data==x
递归主体：
f（L, x）≡f（L->next,x）; 其他情况
本题代码如下：
1.voidDel_X_3（Linklist&L,ElemTypex）{
2.//递归实现在单链表L中删除值为x的结点
3.LNode*p;//p指向待删除结点
4.if（L==NULL）//递归出口
5.return;
6.
7.if（L->data==x）{//若L所指结点的值为x
8.p=L;//删除*L,并让L指向下一结点
9.L=L->next;
10.free（p）;
11.Del_X_3（L,x）;//递归调用
12.}else//若L所指结点的值不为x
13.Del_X_3（L->next,x）;//递归调用
14.}
算法需要借助一个递归工作栈，深度为O（n），时间复杂度为O（n）。
有读者认为直接free掉p结点会造成断链，实际上因为L为引用，是直接对原链表进行操作，因此不会断链。
2.解答：
解法一：
用p从头至尾扫描单链表，pre指向*p结点的前驱。
若p所指结点的值为x，则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。
本题代码如F：
1.voidDel_X_1（Linklist&L,ElemTypex）{
2.//L为带头的单链表，本算法删除L中所有值为x的结点
3.LNode*p=L->next,*pre=L,*q;//置p和pre的初始值
4.
5.while（p!
=NULL）{
6.if（p->data==x）{
7.q=p;//q指向该结点
8.p=p->next;
9.pre->next=p;//删除*q结点
10.free（q）;//释放*q结点的空间
11.}else{//否则，pre和p同步后移
12.pre=p;
13.p=p->next;
14.}//else
15.}//while
16.}
本算法是在无序单链表中删除满足某种条件的所有结点，这里的条件是结点的值为x。
实际上，这个条件是可以任意指定的，只要修改if条件即可，比如，我们要求删除值介于mink和maxk之间的所有结点，则只需将if语句修改为if（p->data>mink&&p->data解法二：
釆用尾插法建立单链表。
用p指针扫描L的所有结点，当其值不为x时将其链接到L之后，否则将其释放。
本题代码如下：
1.voidDel_X_2（Linklist&L,ElemTypex）{
2.//L为带头的单链表，本算法删除L中所有值为x的结点
3.LNode*p=3->next,*r=L,*q;//r指向尾结点，其切值为头结点
4.
5.while（p!
=NULL）{
6.if（p->data!
=x）{//*p结点值不为x时将其链接到L尾部
7.r->next=p;
8.r=p;
9.p=p->next;//继续扫描
10.}else{//*p结点值为x时将其释放
11.q=p;
12.p=p->next;//继续扫描
13.free（q）;//释放空间
14.}
15.}//while
16.r->next=NULL;//插入结束后置尾结点指针为NULL
17.}
上述两个算法扫描一遍链表，时间复杂度为O（n），空间复杂度为O
（1）。
3.解答：
考虑到从头到尾输出比较简单，本题的思路很自然地联系到借助上题链表逆置的方法来实现，改变链表的方向，然后就可以从头到尾实现反向输出了。
此外，本题还可以借助一个栈来实现，每经过一个结点时，将该结点放入栈中。
在遍历完整个链表后，再从栈顶开始输出结点值即可。
既然能用栈的思想解决，也就很自然地联想到了用递归来实现，每当访问一个结点时，先递归输出它后面的结点，再输出该结点自身，这样链表就反向输出了。
如下图所示：
本题代码如下：
1.voidR_Print（LinkListL）{
2.//从尾
升级会员 