线性表典型例题一、单项选择题[例7-1]在数据结构中，与所使用计算机无关的数据叫( ①)结构；链表是一种采用( ②)存储结构存储的线性表；链表适用于( ③)查找；在链表中进行( ④)操作的效率比在线性表中进行该操作的效率高。
①A．存储B．物理C．逻辑D．物理和逻辑②A．顺序B．网状C．星式D．链式③A．顺序B．二分法C．顺序及二分法D．随机④A．二分法查找B．快速查找C．顺序查找D．插入解析：本题考查的是基本概念。
本题答案为：①C；②D；③A；④D。
[例7-2] 链表不具备的特点是( )。
A．插入和删除不需要移动元素B．可随机访问任一结点C．不必预分配空间D．所需空间与其长度成正比解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个结点。
本题答案为：B。
[例7-3] 不带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head_>next＝＝NULLC．head_>next＝＝head D．head!＝NULL解析：在不带头结点的单链表head中，head指向第一个数据结点。
空表即该表没有结点，head＝＝NULL表示该单链表为空。
本题答案为：A。
[例7-4] 带头结点的单链表head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULLC．head—> next＝＝head D．head!＝NULL解析：在带头结点的单链表head中，head指向头结点。
空表即该表只有头结点，head —>next＝＝NULL表示该单链表为空。
本题答案为：B。
[例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。
A．head＝＝NULL B．head—>next＝＝NULLC．head—> next＝＝head D．head!＝NULL解析：在带头结点的循环单链表head中，head指向头结点。
空表即该表只有头结点，head—>next＝＝head表示该单链表为空。
本题答案为：C。
[例7-6] 线性表采用链式存储时其存储地址( )。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续不连续都可以解析：链式存储采用动态存储，地址一般不连续。
本题答案为：D。
[例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。
A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior；B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior；C．s—>next=p；s—>prior=p—>prior；p—>prior=s；p—>prior—>next=s；D．s—>next=p；s—>prior=p—>prior；p—>prior—>next=s；p—>prior=s；解析：在双向链表的* p结点前插入新结点* s的操作如图7.12所示，图中虚线为所作的操作，序号为操作顺序。
本题答案为：D。
图7.12 双向链表插入结点的过程示意图(例7-8)若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。
A．单链表B．双向链表C．给出表头指针的循环单链表D．给出尾指针的循环单链表解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。
上述四个选项中，只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。
本题答案为：D。
[例7-9] 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。
A．删除所有值为x的元素B．在最后一个元素的后面插入一个新元素C．顺序输出前k个元素D．交换其中某两个元素的值解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。
本题答案为：A。
(例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。
A．只有表头指针的不带头结点的循环单链表B．只有尾指针的不带表头结点的循环单链表C．只有表尾指针的带头结点的循环单链表D．只有尾指针的带表头结点的循环单链表解析：本题答案为：A。
具体算法如下：linklist * delfirst(linklist * h){Linklist * p＝h；while(p—> next!＝h) //找到表尾结点p＝p—>next；p—>next=h—> next；free(h)；returnp一>next；//返回头指针}二、填空题[例7-11] 在单链表中结点* p后插入结点* s的指令序列为；。
解析：在单链表中结点* p后插入结点* s，即将* p 的后继结点变为* s 的后继结点，* s 则成为* p的后继结点。
操作指令序列为：s—>next＝p—>next；p—>next＝s。
[例7-12]在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为和；而根据指针的链接方式，链表又可分为和。
解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。
[例7-13] 在单链表中，要删除某一个指定的结点，必须找到该结点的 结点。
解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next 指针域指 向该结点的后继结点。
本题答案为：前驱。
[例7-14] 在一个长度为n 的顺序表中删除第i(0≤i ≤n 一1)个元素，需向前移动 个元素。
解析：需将第i 个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。
本题答案为：n-i-1。
[例7-15] 在一个具有n 个结点的单链表，在 * p 结点后插入一个新结点的时间复杂度是 ；在给定值为x 的结点后插入一个新结点的时间复杂度是 。
解析：在 * p 结点后插入一个新结点 * s 的操作是：s —> next ＝p —> next ；p —>next ＝ s ；其时间复杂度为0(1)。
在给定值为x 的结点后插入一个结点，首先要找到该结点，然后再进行插入。
找到该 结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。
本题答案为：O(1)；O(n)。
三、应用题(例7-16) 设A 是一个线性表(a 0，a 1，…，a i ，…，a n-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在a i 和a i+1之间 (0≤i ≤n-1)的概率为1(1)/2n n n -+，则平均每插入一个元素所需要移动的元素个数是多少?解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：(012)12n n n ++++=+ 若元素插在a i 和a i+l 之间(0≤i ≤n-1)的概率为(1)/2n i n n -+，则平均每插入一个元素所需 要移动的元素个数为：10n i -=∑2222()221(1)1(1)/2(1)3n i n n n n n n n -+⎡⎤=+-++=⎣⎦++ (例7-17) 简述线性表采用顺序存储方式和链式存储方式的优缺点。
解析：顺序表的优点是可以随机访问数据元素，而且不需要额外的空间存储元素间的逻辑关系；缺点是表的大小固定，增减结点需要移动大量元素。
链表的优点是增减元素非常方便，只需要修改指针内容；缺点是只能进行顺序访问，另外在每个结点上增加指针域会造成存储空间增大。
[例7-18] 若频繁地对一个线性表进行插入和删除操作，则应采用何种存储结构来存储该线性表?为什么?解析：应采用链式结构来存储该线性表。
采用链式存储结构来存储线性表，在进行插 入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上，查找过程中平 均移动指针域的次数为表长的一半；而采用顺序存储结构存储线性表，在进行插入和删除 操作时的复杂度则体现在元素的移动上，平均需移动表中的一半元素。
因为指针域的移动 操作次数比元素的移动操作次数少得多，所以应采用链式结构来存储该线性表。
(例7—19) (1)写出在双向链表中的结点 * p 前插入一个结点 *s 的语句序列。
(2)写出判断带头结点的双向循环链表L 为空表的条件。
解析：(1)s —>prior ＝p —>prior ；p —>prior — >next ＝s ；s —>next ＝p ；p —>prior ＝s ；(2)(L＝＝L—>next)&&(L＝＝L—>prior)[例7-20] 链表所表示的元素是否是有序的?如果有序，则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?解析：链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。
链表所表示的元素在物理上不一定相邻。
有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。
四、算法设计题(例7-21)编写一个算法，将一个带头结点的单链表逆转。
要求在原链表空间上进行逆转，即不允许构造新的链表结点；解析：从单链表的一种构造方法——头插法中可以得知，该方法构造的线性表中结点的顺序与插人次序相反。
因此我们可以将表结点从前往后逐个拆下并用头插法插人新表，所构造的单链表即为原表的逆转。
具体算法如下：linklist * reverse(1inklist * h){linklist * p，*q，*r；p＝h—>next；h—>next=NULL；//构造空表while(p!＝NULL){q=p；//拆下结点p=p—> next；q—>next=h—>next；//用头插法插入h—>next=q；}return h；}(例7-22) 已知一个顺序表La的元素按值非递减有序，编写一个算法将元素x插人后保持该表仍然按值非递减有序。
解析：要让插入新元素后的顺序表仍然按值非递减有序，必须把x插入到表中第一个大于等于x的元素之前。
应先在表中找到该位置，然后后移该元素，空出一个位置，再将x 插入。
具体算法如下：insert(sqlist *La，datatype x) //La为指向顺序表的指针{int i=0，j；while(i<= La—>last) //查找插入位置i{if(x<=La—>data[i])break；i++；}for(j=La—>last+1；j>i；j--) //后移所有大于等于x的元素La—>data[j]=La—>data[j-1]；La—>data[i]＝x；//将x插入La—>last++；//表长度加1}(例7-23)用顺序表A、B表示集合，编写算法求集合A和集合B的交集C(假设A、B 表内无重复元素)。