1、计算机专业基础综合（线性表）模拟试卷 2 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。（A）单链表（B）带有头指针的单循环链表（C）双链表（D）带有尾指针的单循环链表2 已知两个长度分别为 l 和 s 的降序链表，若将它们合并为一个长度为 l+s 的升序链表，则最坏情况下的时间复杂度是( )。（A）O(l)（B） O(ls)（C） O(min(l，s)（D）O(max(l，s)3 线性表中存放
2、的主要是( )。（A）整型常量（B）字符（C）数据元素（D）信息元素4 下面的叙述中正确的是( )。I线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比（A）仅 I（B）仅 （C）仅 （D）I、5 对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( ) 存储方式最节省时间。（A）顺序表（B）双链表（C）带头结点的双循环链表（D）单循环链表6 若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式中最节省时间的是
3、( ) 。（A）单链表（B）双链表（C）单循环链表（D）顺序表7 如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( ) 存储方式最节省运算时间。（A）单链表（B）仅有头指针的单循环链表（C）双链表（D）仅有尾指针的单循环链表8 算法的时间复杂度取决于( )。（A）问题的规模（B）待处理数据的初态（C） A 和 B（D）以上都不正确9 关于链表的特点，下面的叙述中不正确的是( )。（A）插入、删除运算方便（B）可实现随机访问任一元素（C）不必事先估计存储空间（D）所需空间与线性长度成正比10 设线性表中有 2n 个元素，以下操作中，在单链表上实现要比在顺序表上实
4、现效率更高的是( ) 。（A）删除指定元素（B）在最后一个元素的后面插入一个新元素（C）顺序输出前 k 个元素（D）交换第 i 个元素和第 2ni-1 个元素的值(i=0，1，n 一 1)11 下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入( )。void reverse(pointer h) h 为附加头结点指针pointer p，q；p=h 一next；h 一next=NULL；while(p|=null) q=p；p=p 一next；q 一next=h 一next；h 一next=(_)；（A）h（B） p（C） q（D）q 一next12 若长度为 n 的线性表
5、采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。（A）O(0)（B） O(1)（C） O(n)（D）O(n 2)13 线性表(a 1，a 2，a n)以链式存储方式存储时，访问第 i 位置元素的时间复杂度为( )。（A）O(i)（B） O(1)（C） O(n)（D）O(i 一 1)14 非空的循环单链表 head 的尾结点 p 满足( )。（A）p 一next=head（B） p 一next=NULL（C） P=NULL（D）p=head15 双向链表中有两个指针域，即 prior 和 next，分别指向前驱及后继，设 p 指向链表中的一个结点，q
6、指向一个待插入结点，现要求在 p 前插入 q，则正确的插入为( )。（A）p 一prior=q；q 一 next=p；p 一prior 一next=q；q 一prior=p 一prior；（B） q 一prior=p 一prior；p 一prior 一nextpq；q 一next=p；p 一prior=q；（C） q 一next=p ；p 一next=q；p 一prior 一next=q；q 一next=p ；（D）p 一prior 一next=q；q 一next=p；q 一prior=p 一prior ；p 一prior=q；16 静态链表中指针表示的是( )。（A）内存地址（B）数组下标（
7、C）下一元素数组下标（D）左、右孩子地址17 在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是 ( )。（A）p 一next=s ；s 一next=p 一next ；（B） s 一next=p 一next；p 一next=s；（C） p 一next=s；p 一next=s 一next ；（D）p 一next=s 一next；p 一next=s；18 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是 ( )。（A）head=NULL（B） head 一next=NULL（C） head-next=head（D）head!=NULL19 以下与数据的存储结构
8、无关的术语是( )。（A）循环队列（B）链表（C）哈希表（D）栈20 以下数据结构中，( )是线性数据结构。（A）广义表（B）二叉树（C）稀疏矩阵（D）串二、综合应用题41-47 小题，共 70 分。21 有两个集合 A 和 B，利用带头结点链表表示，设头指针分别为 la 和 lb。两集合的链表元素皆为递增有序。设计一个算法，将 A 与 B 合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 A 和 B 的原有结点空间上完成。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。(3)分别给出算法各部分
9、的时间复杂度。22 线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为 x 的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。23 已知顺序表 A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+
10、或 Java 语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。24 已知单链表 L 是一个递增有序表，试写一高效算法，删除表中值大于 min 且小于 max 的结点( 若表中有这样的结点) ，同时释放被删结点的空间，这里 min 和 max是两个给定的参数。25 线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容： (1)用最少的时间在表中查找数值为 x 的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增有序。26 设有一个双链表 L，每个结点中除有 prior、da
11、ta 和 next 这 3 个域外，还有一个访问频度域 freq，在链表被启用之前，其值均初始化为零。每当在链表进行一次LocateNode(L，x)运算时，令元素值为 x 的结点中 freq 域的值加 1，并调整表中结点的次序，使其按访问频度的递减排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 LocateNode 运算的算法。27 有一个不带头结点的单链表 list，链表中结点都有两个域：数据域 data 和指针域 link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求：
12、(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或Java 语言描述算法，关键之处给出注释。28 如果以单链表表示集合，设集合 A 用单链表 LA 表示，集合 B 用单链表 LB 表示，设计算法求两个集合的差，即 A 一 B。29 已知 3 个带头结点的线性链表 A、B、C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表 A 进行如下操作：使操作后的链表 A 中仅留下 3 个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p)，其中 m、n 和 p 分别为 3 个表的长度。30 已
13、知非空链表 A，其指针是 list，链表中的结点由两部分组成：数据域 data 和指针域 link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。31 已知一个双向链表，其结点结构为数据域 data、左指针域 llink、右指针域rlink；设指针 P 指向双向链表中的某个结点。写出一个算法，实现 P 所指向的结点和它的前缀结点之间顺序的互换。要求：(1)给出算法的基本设计思想。(2)根
14、据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。32 两个整数序列 A=a1，a 2，a 3，a m 和 B=b1，b 2，b 3，b n 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。33 已知一个带有头结点的单链表 L，其结点结构由两部分组成：数据域 data，指针域 link。设计一个算法，以最高效的方法实现在单链表中删除数据域最小值结点。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。34 设有集合 A 和集合 B，要求设计生成集合 C=AB 的算法，其中集
15、合 A、集合B 和集合 C 用链式存储结构表示。计算机专业基础综合（线性表）模拟试卷 2 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是 O(1)，所以答案是 D。【知识模块】 线性表2 【正确答案】 D【试题解析】 在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最大
16、值。【知识模块】 线性表3 【正确答案】 C【试题解析】 线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。【知识模块】 线性表4 【正确答案】 A【试题解析】 在线性表链式存储结构中，查找第 i 个元素的时间与 i 的位置成正比。而在顺序存储结构中查找第 i 个元素的时间与 i 的位置无关。【知识模块】 线性表5 【正确答案】 A【试题解析】 线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。【知识模
17、块】 线性表6 【正确答案】 D【试题解析】 本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，其特点如下：(1)顺序表可以实现随机存取，其时间复杂度为 O(1)。但在顺序表中，进行插入和删除操作需要移动大量的元素，其时间复杂度为 O(n)；(2)链表中只能实现顺序查找，其时间复杂度为 O(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为 O(1)。本题中，线性表中常用的操作是取第 i 个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第 i 个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第 i 个元素的
18、前驱也不方便；双链表虽然能快速查找第 i 个元素的前驱，但不能实现随机存取。【知识模块】 线性表7 【正确答案】 D【试题解析】 最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。【知识模块】 线性表8 【正确答案】 C【试题解析】 此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态，所以选 C。A 和 B 都不全面。【知识模块】 线性表9 【正确答案】 B【试题解析】 链表的特点包括：事先不需要申请存储空间，插入和删除运算方便，但不能实现随机存取。【知识模块】 线性表10 【正确答案】 A【试题解析】 对于 A，
19、删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。对于 B，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。对于 C，顺序输出前 k 个元素，单链表和顺序表的效率几乎相同。对于 D，交换第 i 个元素和第 2ni1 个元素的值(i=0，1，n 一 1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。【知识模块】 线性表11 【正确答案】 C【试题解析】 h 一next=q；表示将当前结点作为头结点后的第一元素结点插入。【知识模块】 线性表12 【正确答案】 C【试题解析】 此题考查的知识点是线性表
20、基本操作的时间复杂度。顺序存储的线性表插入元素时需要从插入位置开始向后移动元素，腾出位置以便插入，平均移动次数为(n+1) 2，所以复杂度为 O(n)，选 C。【知识模块】 线性表13 【正确答案】 C【试题解析】 此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第 i 个位置的元素时需要从头开始向后查找，平均查找次数为 (n+1)2，所以时间复杂度为 O(n)，选 C。【知识模块】 线性表14 【正确答案】 A【试题解析】 此题考查的知识点是循环单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点，所以选 A。B、C、D 均不能构成非空的循环单链表。【知识模块】 线性
21、表15 【正确答案】 A【试题解析】 此题考查的知识点是双向链表的插入操作。在 p 前插入，要修改 p的 prior 指针、p 的 prior 所指结点的 next 指针，所以选 A。B、C、D 都将使地址丢失，连接失败。【知识模块】 线性表16 【正确答案】 C【试题解析】 静态链表中指针表示的是下一元素的数组下标。【知识模块】 线性表17 【正确答案】 B【试题解析】 此题考查的知识点是单链表的插入操作。要先保存 p 的后继结点，再连入 s 结点，所以选 B。A、C、D 都将使地址丢失，连接失败。【知识模块】 线性表18 【正确答案】 B【试题解析】 此题考查的知识点是带头结点的单链表操作
22、。带头结点的单链表空白勺时候表示只有一个结点存在，但没有存信息。所以选 B。A 表示没有结点，C表示循环单链表，D 表示有一个指针不为空，所以都不对。【知识模块】 线性表19 【正确答案】 D【试题解析】 此题考查的知识点是对数据结构和存储结构的理解。A 、B 、C 描述的均为物理结构即数据的存储结构，D 是逻辑结构，所以选 D。【知识模块】 线性表20 【正确答案】 D【试题解析】 此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导、一个后继，而 A、B、C 有多个后继，均错，所以选 D。【知识模块】 线性表二、综合应用题41-47 小题，共 70 分。21 【正
23、确答案】 (1)算法的基本设计思想：分别从 A、B 的头结点开始，依次比较A、B 中元素的内容，如果 A 中的元素值大于 B 中的元素值，则将 B 中的结点插入结果链表，反之将 A 中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果 A、B 中两个元素值相同，只将其中的一个加入结果链表。(2)算法的设计如下：typedef struct LNodeint data：struct LNode * next： * Linkedlist；LinkedList Union(Linked List la，lb) pa=la 一next；pb=lb 一 next
24、； 设工作指针 pa 和 pbpc=la； pc 为结果链表当前结点的前驱指针while(pa&pb) if(pa 一datadata) pc 一next=pa；pc=pa；pa=pa 一next；else if(pa 一datapb 一 data) pc 一 next=pb；pc=pb；pb=pb 一next；else 处理 pa 一data=pb 一datapc 一next=pa；pc=pa；pa=pa 一next；u=pb；pb=pb-next；free(u)；if(pa)pc-next=pa； 若 la 表未空，则链入结果表else pc-next=pb； 若 lb 表未空，则链入结果
25、表free(1b)； 释放 lb 头结点return(1a)：(3)本题中的主要操作是依次比较 A、B 链表中的数据元素值的大小，因此时间复杂度为 O(n)。【知识模块】 线性表22 【正确答案】 (1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为戈的元素” ，这里应使用折半查找方法。 (2)算法的设计如下： void SearchExchangelnse(ElemType a，ElemType x) int low=0； int high=n-l；int mid； low 和 high 指向线性表下界和上界的下标 while(lowhigh)
26、查找失败，插入数据元素 x int i； for(i=n-1 ；ihigh ；i 一一) ai+1=ai； 后移元素 alow=x； 插入 x 结束插入 (3) 在利用折半查找的方法查找 x 的过程中时间复杂度为 O(nlog2n)；交换元素位置时的时间复杂度为 O(1)；当查找不成功时，插入元素时的时间复杂度为 O(n)。【知识模块】 线性表23 【正确答案】 (1)基本的设计思想：先将偶数号元素复制到一个辅助空间，然后整理数组剩下的奇数号元素，最后将辅助空间中的元素复制到数组的后半部分，但这种思路的空间复杂度为 O(n)。 另一种思路： 在数组尾部从后往前找到第一个奇数号元素，将此元素与其
27、前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元素“块” 。 暂存中 “块”前面的偶数号元素，将“ 块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块” 。 暂存中 “块”前面的偶数号元素，将“ 块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块” 。 如此继续，直到前一步的“块” 前没有元素为止。 (2)算法的设计如下： void Swap(ElemType A ，int n) int i=n，v=l： i为工作指针，初始假设 n 为奇数，v 为“块” 的大
28、小 ElemType temp： 辅助变量 if(n2=0)i：n 一 1： 若 n 为偶数，则令 i 为 n1 while(i1) 假设数组从 1 开始存放。当 i=1 时，气泡浮出水面 temp=Ai 一 1； 将“ 块”前的偶数号元素暂存 for(int j=0 ；j 2)。虽然时间复杂度为 O(n2)，但因 n2 前的系数很小，实际达到的效率是很高的。算法的空间复杂度为 O(1)。【知识模块】 线性表24 【正确答案】 struet nodeDatatype data；struet node * next；ListNode；typedef ListNode * LinkList；voi
29、d DeleteList(LinkList L，DataType min，DataType max)ListNode * p， *q， *h；p=L 一next： 采用代表头结点的单链表while(p&p 一datanext；p=q： 保存这个元素位置while(q&q-datanext；找比 max 小的最后一个元素位置while(p 一next!=q)h=p 一 next；p=p 一 next；free(h)； 释放空间p 一next=q； 把断点链上提示：首先想到的是拿链表中的元素一个个地与 max 和 min 比较，然后删除这个结点。其实因为已知其是有序链表，所以只要找到大于 min
30、的结点的直接前趋结点，再找到小于 max 的结点，然后一并把中间的全部摘掉就可以了。【知识模块】 线性表25 【正确答案】 (1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为 x 的元素” ，这里应使用折半查找方法。void SearchExchangelnsert(ElemType a；ElemType x)a 是具有 n 个元素的递增有序线性表，顺序存储。本算法在表中查找数值为 x的元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序low=O：high=n-1； low 和 high 指向线性表下界和上界的下标while(
31、lowhigh) 查找失败，插入数据元素 xfor(i=n-1；ihigh；i 一一)ai+1=ai； 后移元素ai+1=x； 插入 x 结束插入 结束本算法(2)算法讨论首先是线性表的描述。算法中使用一维数组 a 表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体，对元素的引用应使用aelemi。另外，元素类型就假定是 ElemType，未指明具体类型。其次，C 中一维数组下标从 0 开始，若说有 n 个元素的一维数组，其最后一个元素的下标应是n-1。最后，本算法可以写成三个函数，即查找函数、交换后继函数与插入函数，写成三个函数显得逻辑清晰、易读。【知识模块】 线
32、性表26 【正确答案】 typedef struct DuLNodeElemType data；int freq；struct DuLNode * pred， *next； * DList；DList locate(DList L，ElemType x) L 是带头结点的按访问频度递减的双向链表DList p=L 一next，q； p 为 L 表的工作指针，q 为 p 的前驱，用于查找插入位置while(p& p 一data!=x)p=p 一next ； 查找值为 X 的结点if(!p) printf(“不存在所查结点n“) ；exit(0)；else p 一freq+； 令元素值为 x 的结
33、点的 freq 域加 1p 一next 一pred=p 一pred； 将 p 结点从链表上摘下p 一pred 一next=p 一next；q=p 一pred； 以下查找 P 结点的插入位置while(q!=L& q 一freqfreq) q=q 一pred；p 一next=q 一next；q 一next 一pred=p；将 p 结点插入p 一pred=q；q 一next=p；return(p)； 返回值为 x 的结点的指针提示：在算法中先查找数据 x，查找成功时结点的访问频度域增 1，最后将该结点按频度递减插入链表中。【知识模块】 线性表27 【正确答案】 (1)算法的基本设计思想：本题实质上
34、是一个排序问题。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。(2)算法设计如下：typedef struct LNodeint data；struct LNode * link； * linkedlist；LinkedList Link ListSort(LinkedList list) Lnode * p，*q：p=list-link； p 是工作指针，指向待排序的当前元素list-link=null； 假定第一个元素有序，即链表中现只有一个结点while(p!=2 null) r=p 一link；
35、r 是 p 的后继q=list；if(q 一datap-data) 处理待排序结点 p 比第一个元素结点小的情况p 一link=list；list=p； 链表指针指向最小元素else 查找元素值最小的结点while(q 一link=null&q 一link 一datadata) q=q 一link；p 一link=q 一link； 将当前排序结点链入有序链表中q 一link=p；p=r： p 指向下个待排序结点【知识模块】 线性表28 【正确答案】 由集合运算的规则知，集合的差 A-B 为包含所有属于 A 而不属于 B 的元素，因此，算法的思路在于对于所有属于集合 A 中的元素 e，在集合 B
36、中进行查找，若能找到，则说明它不属于 AB，应从 LA 中删除。若 LA 的长度为 O(n)，LB 的长度为 O(m)，则该算法的时间复杂度为 O(mn)。算法参考伪代码如下：void Difference(LinkList * LA，LinkList * LB) 设 LA，LB 均具有头结点Node * pre，*p，*r ；pre=LA；p=LA-next： p 指向 LA 表中的某一结点，而 pre 指向 p 的前面一个结点while(p!=NULL)q=LB 一next；遍历 LB 表，判断 LA 中元素是否在 LB 中Node * while(q!=NULL&q 一data!= 一d
37、ata)q=q 一 nextif(q!=NULL) 在 LB 中找到相同结点元素，则应在 LA 中删除该结点r=p；pre 一next=r 一next；p=p 一next；free(r)；else 未能找到，说明该结点属于 A-B。继续在 LA 中对下一个元素进行判断pre=p；p=p 一next；【知识模块】 线性表29 【正确答案】 typedef struct LNodeint data；struct LNode * next； * Linkedlist；LinkedList Common(LinkedList A，B ，C) 链表 A、链表 B 和链表 C 是三个带头结点且结点元素值非
38、递减排列的有序表本算法使链表 A 仅留下三个表均包含的结点，且结点值不重复，释放所有结点Linkedlist * pa， * pb， * pc ， * pre， *u；pa=A 一 next；pb=B 一next；pc=C 一next； pa ，pb，pc 分别是链表A，B，C 的工作指针pre=A； pre 是链表 A 中当前结点的前驱结点的指针while(pa&pb&pc) 当链表 A，B 和 C 均不空时，查找三链表共同元素while(pa&pb)if(pa 一datadata)u=pa ；pa=pa-next；free(u)；结点元素值小时，后移指针else if(pa 一datapb
39、 一data)pb=pb 一next；else if(pa&pb) 处理链表 A 和 B 元素值相等的结点while(pc&pc 一datadata)pc=pc 一next；if(pc) pc 当前结点值与 pa 当前结点值不等， pa 后移指针if(pc 一 datapa-data) u=pa；pa=pa 一next；free(u)；else pc、pa 和 pb 对应结点元素值相等if(pre=A)pre 一next=Pa ；pre=pa；Pa=pa-next； 结果表中第一个结点else if(pre 一data=pa 一data) (处理)重复结点不链入链表 A u=pa；pa=pa-
40、next；free(u)；elsepre 一next=pa；pre=pa；pa=pa 一next； 将新结点链入链表 Apb=pb 一next；pc=pc-next； 链表的工作指针后移else pc，pa 和 pb 对应结点元素值相等ifpa=null)pre 一next=null； 原链表 A 已到尾，置新链表 A 表尾else 处理原链表 A 未到尾而链表 B 或链表 C 到尾的情况pre 一next=null； 置链表 A 表尾标记while(pa!=null)u=pa；pa-pa 一next；free(u)； 删除原链表 A 剩余元素提示：留下 3 个链表中的公共数据，首先查找链表
41、A 和链表 B 中公共数据，再去链表 C 中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度为O(m+n+p)，在查找每个链表时，指针不能回溯。算法实现时，链表 A、链表 B 和链表 C 均从头到尾(严格地说链表 B、链表 C 中最多一个到尾)遍历一遍，算法时间复杂度符合 O(m+n+p)。算法主要有while(pa&pb&p)。【知识模块】 线性表30 【正确答案】 (1)算法的基本设计思想：首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下(不是删除并回收空间)，再插入到链表的最前面。(2)算法的实现如下：typedef struet LNodechar dat
42、a；struet LNode * link； * Linkedlist；LinkedList delinsert(LinkedList list) 将链表中数据域值最小的那个结点移到链表的最前面Linkedlist * p，* pre ，* q；p=listlink； p 是链表的工作指针pre=lisl； pre 指向链表中数据域最小值结点的前驱q=p； q 指向数据域最小值结点，初始假定是第一结点while(p 一link!=null)if(p 一 link 一datadata)pre=p；q=p-link； 找到新的最小值结点p=p 一 link；ifq!=list-link) 若最小值
43、是第一元素结点，则不需再操作pre 一link=q 一link； 将最小值结点从链表上摘下q-link=list 一link； 将 q 结点插到链表最前面list 一link=q；算法结束【知识模块】 线性表31 【正确答案】 (1)算法的基本思想：已知双向循环链表中的一个结点 p，与前驱交换涉及 4 个结点(p 结点，前驱结点，前驱的前驱结点，后继结点)、6 条链。(2)算法的设计如下：typedef struct DuLNodeint data；struct DuLNode * llink， * rlink；DuLNode * Linkedlist；void Exchange(Linked
44、List p) 将 p 所指结点与其前驱结点交换Linkedlist * q；q=p 一llink；q-llink-rlink=p； p 的前驱的前驱之后继为 pp-llink=q 一llink ； p 的前驱指向其前驱的前驱q-rlink=p-rlink： p 的前驱的后继为 p 的后继q-llink=p； p 与其前驱交换p-rlink-llink=q： p 的后继的前驱指向原 p 的前驱p-rlink=q： p 的后继指向其原来的前驱【知识模块】 线性表32 【正确答案】 typedef struct LNodeint data；struct LNode * next； * Linked
45、list；int Pattern(LinkedList A，B)A 和 B 分别是数据域为整数的单链表，本算法判断链表 B 是否是链表 A 的子序列。如是，返回 1；否则，返回 0，表示失败。Linkedlist * p， * pre ，* q；P=A； p 为链表 A 的工作指针，本题假定链表 A 和链表 B 均无头结点pre=p； pre 记住每趟比较中链表 A 的开始结点q=B； q 是链表 B 的工作指针while(p&q)if(p 一data=q 一 data)p=p 一next ； q=q 一next ； elsepre=pre 一next；p=pre； 链表 A 新的开始比较结点
46、q=B； q 从链表 B 第一结点开始if(q=null)return(1)； 链表 B 是链表 A 的子序列else return(0)； 链表 B 不是链表 A 的子序列算法结束提示：本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则链表 A 从上次开始比较结点的后继开始，链表B 仍从第一结点开始比较，直到链表 B 到尾表示匹配成功。链表 A 到尾链表 B 未到尾表示失败。操作中应记住链表 A 每次的开始结点，以便下趟匹配时好从其后继开始。【知识模块】 线性表33 【正确答
47、案】 (1)算法的基本思想：单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而 “最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。(2)算法的设计如下：typedef struct LNodeint data；struct LNode * next；LNode * Linkedlist：LinkedList Delete(LinkedList L) L 是带头结点的单链表，本算法删除其最小值结点Linkedlist * p，* q，* pre ；p=L-next； p 为工作指针，指向待处理的结点。假定链表非空pre=L； pre 指向最小值结点的前驱q=p； q 指向最小值结点，初始假定第一元素结点是最小值结点while(p 一next!=null)if(p 一next 一datadata)pre=p； q=p 一next； 查最小值结点p=p 一next； 指针后移pre 一next=q
