2.7 线性表的典型试题精选与解析
2.7.1 典型试题
一、单项选择题
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、非空的循环单链表head的尾结点p满足（ ）。
A．p->next==head
B．p->next==NULL
C．p==NULL
D．p==head
4、在双向循环链表中，在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;
5、线性表采用链式存储时，结点的存储地址（ ）。
A．必须是连续的
B．必须是不连续的
C．连续与否均可
D．和头结点的存储地址相连续
6、（2016年全国统考试题）已知表头元素为c的单链表在内存中的存储状态如下表所示。
现将f存放在1014H处并插入到单链表，若f在逻辑上位于a和e之间，则a、e、f的链接地址依次是（ ）。
A．1010H，1014H，1004H
B．1010H，1004H，1014H
C．1014H，1010H，1004H
D．1014H，1004H，1010H
7、从表中任一结点出发，都能扫描整个表的是（ ）。
A．单链表
B．顺序表
C．循环链表
D．静态链表
8、在一个长度为n的带头结点的单链表L中，设有尾指针r，则执行（ ）操作与链表的表长有关。
A．删除单链表中的第一个元素
B．在单链表中第一个元素前插入新元素
C．删除单链表中的最后一个元素
D．在单链表最后一个元素后插入新元素
9、在双向链表存储结构中，删除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;
10、（2016年统考试题）已知一个带有表头结点的双向循环链表L，结点结构为
，其中prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指向的结点，正确的语句序列是（ ）。
A．p->next->prev=p->prev;p->prev->next=p->prev;free（p）;
B．p->next->prev=p->next;p->prev->next=p->next;free（p）;
C．p->next->prev=p->next;p->prev->next=p->prev;free（p）;
D．p->next->prev=p->prev;p->prev->next=p->next;free（p）;
11、不带头结点的单链表head为空的判定条件是（ ）。
A．head==NULL
B．head->next==NULL
C．head->next==head
D．head!=NULL
12、（哈尔滨工业大学考研试题）将长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为（ ）。
A．O（1）
B．O（n）
C．O（m）
D．O（m+n）
13、在一个单链表中，已知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;
14、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（ ）。
A．O（n）
B．O（1）
C．O（n2）
D．O（n-1）
15、在一个单链表中，若删除p所指向结点的后继结点，则执行（ ）。
A．p->next=p->next->next;
B．p=p->next;p->next=p->next->next;
C．p=p->next;
D．p=p->next->next;
16、已知指针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;
17、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（ ）。
A．p=p->next;
B．p->next=p->next->next;
C．p->next=p;
D．p=p->next->next;
18、（北京理工大学考研试题）在一个单链表中，指针p指向其中某个结点，若在该结点前插入一个由指针s指向的结点，则需执行（ ）。
A．s->next=p->next;p->next=s;
B．p->next=s;s->next=p;
C．r=p->next;p->next=s;s->next=r;
D．仅靠已知条件无法实现
19、（华中科技大学考研试题）某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next->next==head成立时，线性表的长度可能是（ ）。
A．1或2
B．2
C．3
D．0或2
20、（2013年全国统考试题）已知两个长度分别为m和n的升序链表，如果将它们合并为一个长度为m+n的降序排列的链表，则最坏情况下算法时间复杂度为（ ）。
A．O（n）
B．O（m*n）
C．O（min（m，n））
D．O（max（m，n））
二、综合分析题
1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。其中结点结构为
。
2、以下是实现单链表的插入算法，请在空格处将算法补充完整。
3、以下是实现单链表的删除算法，请在空格处将算法补充完整。
4、写出算法的功能。
5、一元稀疏多项式以带头结点的循环单链表按降幂排列，结点包含3个域：系数coef、指数exp和指针next。现对该链表求一阶导数，链表的头指针为h，头结点的exp域的值为-1。
6、对单链表中元素按插入法排序的C语言描述算法如下，其中L为链表头结点指针，NLLL表示指针为空。请填充算法中标出的空白处，完成其功能。
三、算法设计题
1、编写算法，实现带头结点单链表的逆置。
2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。
3、编写算法，将一个无序的单链表变成一个有序的单链表，要求按照从小到大排列并且不占用额外的存储空间。
4、已知有两个带头结点的单链表A和B，A和B中的元素由小到大排列，设计一个算法，求A和B的交集C，将A和B中相同的元素插入C中。
5、利用单链表的基本运算，实现如果在单链表A中出现的元素，在单链表B中也出现，则将A中该元素删除。如果把单链表看成是集合，这其实是求两个集合的差集A-B，即所有属于集合A而不属于集合B的元素。
6、编写算法，将两个非递减排列的单链表A和B合并得到C，C中的元素仍按照非递减排列。
7、已知有两个带头结点的双向循环链表A和B，它们的元素均是按照递增排列，编写算法，将A和B合并成一个双向循环链表，并使合并后链表中的元素也按照递增排列。
8、已知一个双向循环链表L，设计算法实现将双向循环链表L的所有结点逆置。
9、（西北大学考研试题）编写程序，要求完成：（1）建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。（2）在此链表上实现对二进制数加1的运算，并输出运算结果。
10、（2012年全国统考试题）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如图2-32所示。
图2-32 存储映像
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：
（1）给出算法的基本设计思想。
（2）根据算法设计思想，请采用C语言描述算法。
（3）说明算法的时间复杂度。
11、（2019年全国统考试题）设线性表（a1，a2，a3，…，an-1，an）采用带头结点的单链表保存，链表中的结点定义如下：
请设计一个空间复杂度为O（1）且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L’=（a1，an，a2，an-1，a3，an-2，…）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法时间复杂度。
12、（南京航空航天大学考研试题）假设A为递增有序的单链表（长度为n），B为递减有序的单链表（长度为m），编写算法，利用原链表的结点存储空间，将A和B合并成一个递增有序的单链表，要求时间复杂度为O（n+m），并给出算法思想。