1、计算机专业基础综合数据结构（线性表）-试卷 1 及答案解析(总分：72.00，做题时间：90 分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。（分数：2.00）A.单链表B.带有头指针的单循环链表C.双链表D.带有尾指针的单循环链表3.已知两个长度分别为 l 和 s 的降序链表，若将它们合并为一个长度为 l+s 的升序链表，则最坏情况下的时间复杂度是( )。（分数
2、：2.00）A.O(l)B.O(ls)C.O(min(l，s)D.O(max(l，s)4.线性表中存放的主要是( )。（分数：2.00）A.整型常量B.字符C.数据元素D.信息元素5.下面的叙述中正确的是( )。 I线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比（分数：2.00）A.仅 IB.仅C.仅D.I、6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。（分数：2.00）A.顺序表B.
3、双链表C.带头结点的双循环链表D.单循环链表7.若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式中最节省时间的是( )。（分数：2.00）A.单链表B.双链表C.单循环链表D.顺序表8.如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。（分数：2.00）A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表9.算法的时间复杂度取决于( )。（分数：2.00）A.问题的规模B.待处理数据的初态C.A 和 BD.以上都不正确10.关于链表的特点，下面的叙述中不正确的是( )。（分数：2.00）A.插入
4、、删除运算方便B.可实现随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比11.设线性表中有 2n 个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是( )。（分数：2.00）A.删除指定元素B.在最后一个元素的后面插入一个新元素C.顺序输出前 k 个元素D.交换第 i 个元素和第 2ni-1 个元素的值(i=0，1，n1)12.下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入( )。 void reverse(pointer h) h 为附加头结点指针 pointer p，q； P=h 一next；h 一next=NULL； while(
5、P|=null) q=P： P=P 一next： q 一next=h 一next； h 一next=(_)； （分数：2.00）A.hB.PC.qD.q 一next13.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。（分数：2.00）A.O(0)B.O(1)C.O(n)D.O(n 2 )14.线性表(a 1 ，a 2 ，a n )以链式存储方式存储时，访问第 i 位置元素的时间复杂度为( )。（分数：2.00）A.O(i)B.O(1)C.O(n)D.O(i 一 1)15.非空的循环单链表 head 的尾结点 P 满足( )。（
6、分数：2.00）A.p 一next=headB.p 一next=NULLC.p=NULLD.p=head16.双向链表中有两个指针域，即 prior 和 next，分别指向前驱及后继，设 P 指向链表中的一个结点，q指向一个待插入结点，现要求在 P 前插入 q，则正确的插入为( )。（分数：2.00）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 一prior=q；C.q 一next=P；p 一next=q；p 一prior 一n
7、ext=q；q 一next=P；D.p 一prior 一next=q；q 一next=P；q 一prior=p 一prior；p 一prior=q；17.静态链表中指针表示的是( )。（分数：2.00）A.内存地址B.数组下标C.下一元素数组下标D.左、右孩子地址18.在单链表指针为 P 的结点之后插入指针为 s 的结点，正确的操作是( )。（分数：2.00）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；19.对于一个
8、头指针为 head 的带头结点的单链表，判定该表为空表的条件是( )。（分数：2.00）A.head=NULLB.head 一next=NULLC.head-next=headD.head!=NULL20.以下与数据的存储结构无关的术语是( )。（分数：2.00）A.循环队列B.链表C.哈希表D.栈21.以下数据结构中，( )是线性数据结构。（分数：2.00）A.广义表B.二叉树C.稀疏矩阵D.串二、综合应用题(总题数：15，分数：30.00)22.综合应用题 41-47 小题。（分数：2.00）_23.有两个集合 A 和 B，利用带头结点链表表示，设头指针分别为 la 和 lb。两集合的链表
9、元素皆为递增有序。设计一个算法，将 A 与 B 合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 A 和 B 的原有结点空间上完成。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 c 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。（分数：2.00）_24.线性表(a 1 ，a 2 ，a 3 ，a n )中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为 x 的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。 (1)给出算
10、法的基本设计思想。 (2)根据设计思想，采用 C 或C+或 Java 语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。（分数：2.00）_25.已知顺序表 A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。（分数：2.00）_26.已知单链表 L 是一个递增有序表，试写一高效算法，删除表中值大于 min 且小于 max 的结点(若表中有这样的结点)，
11、同时释放被删结点的空间，这里 min 和 max 是两个给定的参数。（分数：2.00）_27.线性表(a 1 ，a 2 ，a 3 ，a n )中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容： (1)用最少的时间在表中查找数值为 x 的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增有序。（分数：2.00）_28.设有一个双链表 L，每个结点中除有 prior、data 和 next 这 3 个域外，还有一个访问频度域 freq，在链表被启用之前，其值均初始化为零。每当在链表进行一次 LocateNode(L，x)运算时，令元素值为 x
12、 的结点中 freq 域的值加 1，并调整表中结点的次序，使其按访问频度的递减排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 LocateNode 运算的算法。（分数：2.00）_29.有一个不带头结点的单链表 list，链表中结点都有两个域：数据域 data 和指针域 Iink。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_30.如果以单
13、链表表示集合，设集合 A 用单链表 LA 表示，集合 B 用单链表 LB 表示，设计算法求两个集合的差，即 A 一 B。（分数：2.00）_31.已知 3 个带头结点的线性链表 A、B、C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表 A 进行如下操作：使操作后的链表 A 中仅留下 3 个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p)，其中 m、n 和p 分别为 3 个表的长度。（分数：2.00）_32.已知非空链表 A，其指针是 list，链表中的结点由两部分组成：数据域 data 和指针域
14、 link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_33.已知一个双向链表，其结点结构为数据域 data、左指针域 llink、右指针域 rlink；设指针 P 指向双向链表中的某个结点。写出一个算法，实现 P 所指向的结点和它的前缀结点之间顺序的互换。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，
15、关键之处给出注释。（分数：2.00）_34.两个整数序列 A=a 1 ，a 2 ，a 3 ，a m 和 B=b 1 ，b 2 ，b 3 ，b n 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。（分数：2.00）_35.已知一个带有头结点的单链表 L，其结点结构由两部分组成：数据域 data，指针域 link。设计一个算法，以最高效的方法实现在单链表中删除数据域最小值结点。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_36.设有集合 A 和集合 B，要求设计生成集合 C=A
16、B 的算法，其中集合 A、集合 B 和集合 C 用链式存储结构表示。（分数：2.00）_计算机专业基础综合数据结构（线性表）-试卷 1 答案解析(总分：72.00，做题时间：90 分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。（分数：2.00）A.单链表B.带有头指针的单循环链表C.双链表D.带有尾指针的单循环链表 解析：解析：在链表中的最后一个结点之后插
17、入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是 D。3.已知两个长度分别为 l 和 s 的降序链表，若将它们合并为一个长度为 l+s 的升序链表，则最坏情况下的时间复杂度是( )。（分数：2.00）A.O(l)B.O(ls)C.O(min(l，s)D.O(max(l，s) 解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最大值。4.线性表中存放的主要是( )。（分数：2.00）A.整型常量B.字符C.数据元素 D.信息元素解
18、析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。5.下面的叙述中正确的是( )。 I线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比（分数：2.00）A.仅 I B.仅C.仅D.I、解析：解析：在线性表链式存储结构中，查找第 i 个元素的时间与 i 的位置成正比。而在顺序存储结构中查找第 i 个元素的时间与 i 的位置无关。6.对于某线性表来说，主要的操作是存取任一指定序号的元
19、素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。（分数：2.00）A.顺序表 B.双链表C.带头结点的双循环链表D.单循环链表解析：解析：线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。7.若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式中最节省时间的是( )。（分数：2.00）A.单链表B.双链表C.单循环链表D.顺序表 解析：解析：本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，其特点如下： (1
20、)顺序表可以实现随机存取，其时间复杂度为 O(1)。但在顺序表中，进行插入和删除操作需要移动大量的元素，其时间复杂度为 O(n)； (2)链表中只能实现顺序查找，其时间复杂度为 O(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为 O(1)。 本题中，线性表中常用的操作是取第 i 个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第 i 个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第 i 个元素的前驱也不方便：双链表虽然能快速查找第 i 个元素的前驱，但不能实现随机存取。8.如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删
21、除第一个元素，则采用( )存储方式最节省运算时间。（分数：2.00）A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表 解析：解析：最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。9.算法的时间复杂度取决于( )。（分数：2.00）A.问题的规模B.待处理数据的初态C.A 和 B D.以上都不正确解析：解析：此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态，所以选 C。A 和 B 都不全面。10.关于链表的特点，下面的叙述中不正确的是( )。（分数：2.00）A.插入、删除运算方便B.可实
22、现随机访问任一元素 C.不必事先估计存储空间D.所需空间与线性长度成正比解析：解析：链表的特点包括：事先不需要申请存储空间，插入和删除运算方便，但不能实现随机存取。11.设线性表中有 2n 个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是( )。（分数：2.00）A.删除指定元素 B.在最后一个元素的后面插入一个新元素C.顺序输出前 k 个元素D.交换第 i 个元素和第 2ni-1 个元素的值(i=0，1，n1)解析：解析：对于 A，删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。 对于 B，在最后一个元素的后面插入
23、一个新元素不需要移动元素，顺序表的效率和单链表相同。 对于 C，顺序输出前 k 个元素，单链表和顺序表的效率几乎相同。 对于 D，交换第 i 个元素和第 2ni 一 1 个元素的值(i=0，1，n 一 1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。12.下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入( )。 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 一ne
24、xt=(_)； （分数：2.00）A.hB.PC.q D.q 一next解析：解析：h 一next=q；表示将当前结点作为头结点后的第一元素结点插入。13.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。（分数：2.00）A.O(0)B.O(1)C.O(n) D.O(n 2 )解析：解析：此题考查的知识点是线性表基本操作的时间复杂度。顺序存储的线性表插入元素时需要从插入位置开始向后移动元素，腾出位置以便插入，平均移动次数为(n+1)2，所以复杂度为 O(n)，选 C。14.线性表(a 1 ，a 2 ，a n )以链式存储方式存储
25、时，访问第 i 位置元素的时间复杂度为( )。（分数：2.00）A.O(i)B.O(1)C.O(n) D.O(i 一 1)解析：解析：此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第 i 个位置的元素时需要从头开始向后查找，平均查找次数为(n+1)2，所以时间复杂度为 O(n)，选 C 。15.非空的循环单链表 head 的尾结点 P 满足( )。（分数：2.00）A.p 一next=head B.p 一next=NULLC.p=NULLD.p=head解析：解析：此题考查的知识点是循环单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点，所以选 A。B、C、D 均不
26、能构成非空的循环单链表。16.双向链表中有两个指针域，即 prior 和 next，分别指向前驱及后继，设 P 指向链表中的一个结点，q指向一个待插入结点，现要求在 P 前插入 q，则正确的插入为( )。（分数：2.00）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 一prior=q；C.q 一next=P；p 一next=q；p 一prior 一next=q；q 一next=P；D.p 一prior 一next=q；q 一n
27、ext=P；q 一prior=p 一prior；p 一prior=q；解析：解析：此题考查的知识点是双向链表的插入操作。在 p 前插入，要修改 p 的 prior 指针、p 的prior 所指结点的 next 指针，所以选 A。B、C、D 都将使地址丢失，连接失败。17.静态链表中指针表示的是( )。（分数：2.00）A.内存地址B.数组下标C.下一元素数组下标 D.左、右孩子地址解析：解析：静态链表中指针表示的是下一元素的数组下标。18.在单链表指针为 P 的结点之后插入指针为 s 的结点，正确的操作是( )。（分数：2.00）A.p 一next=s；s 一next=p 一next；B.s
28、一next=p 一next；p 一next=s； C.p 一next=s；p 一next=s 一next；D.p 一next=s 一next；p 一next=s；解析：解析：此题考查的知识点是单链表的插入操作。要先保存 p 的后继结点，再连入 s 结点，所以选B。A、C、D 都将使地址丢失，连接失败。19.对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是( )。（分数：2.00）A.head=NULLB.head 一next=NULL C.head-next=headD.head!=NULL解析：解析：此题考查的知识点是带头结点的单链表操作。带头结点的单链表空的时候表示只
29、有一个结点存在，但没有存信息。所以选 B。A 表示没有结点，C 表示循环单链表，D 表示有一个指针不为空，所以都不对。20.以下与数据的存储结构无关的术语是( )。（分数：2.00）A.循环队列B.链表C.哈希表D.栈 解析：解析：此题考查的知识点是对数据结构和存储结构的理解。A、B、C 描述的均为物理结构即数据的存储结构，D 是逻辑结构，所以选 D。21.以下数据结构中，( )是线性数据结构。（分数：2.00）A.广义表B.二叉树C.稀疏矩阵D.串 解析：解析：此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导、一个后继，而 A、B、C 有多个后继，均错，所以选
30、D。二、综合应用题(总题数：15，分数：30.00)22.综合应用题 41-47 小题。（分数：2.00）_解析：23.有两个集合 A 和 B，利用带头结点链表表示，设头指针分别为 la 和 lb。两集合的链表元素皆为递增有序。设计一个算法，将 A 与 B 合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 A 和 B 的原有结点空间上完成。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 c 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)分别给出算法各部分的时间复杂度。（分数：2.00）_正确答案：(正确答案：(1)算法的基本设计思想
31、：分别从 A、B 的头结点开始，依次比较 A、B 中元素的内容，如果 A 中的元素值大于 B 中的元素值，则将 B 中的结点插入结果链表，反之将 A 中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果 A、B 中两个元素值相同，只将其中的一个加入结果链表。 (2)算法的设计如下： typedef struct LNode int data： struct LNode * next： * Linkedlist； LinkedList Union(LinkedList la，lb) pa=la 一next； pb=lb 一next； 设工作指针 pa 和
32、 pb pc=la； pc 为结果链表当前结点的前驱指针 while(pa P=L 一next； 采用代表头结点的单链表 while(P p=q; 保存这个元素位置 while(qq一datamax)q=q 一next；找比 max 小的最后一个元素位置 while(p 一next!=q) h=p 一next； p=p 一next； free(h)； 释放空间 p 一next=q； 把断点链上 提示：首先想到的是拿链表中的元素一个个地与 max 和 min 比较，然后删除这个结点。其实因为已知其是有序链表，所以只要找到大于 min 的结点的直接前趋结点，再找到小于 max 的结点，然后一并把中
33、间的全部摘掉就可以了。)解析：27.线性表(a 1 ，a 2 ，a 3 ，a n )中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容： (1)用最少的时间在表中查找数值为 x 的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增有序。（分数：2.00）_正确答案：(正确答案：(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为 x 的元素”，这里应使用折半查找方法。 void SearchExchangelnsert(ElemType a；ElemType x) a 是具有 n 个元素的递增有
34、序线性表，顺序存储。本算法在表中查找数值为 x 的 元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序 low=0： high=n 一 1， low 和 high 指向线性表下界和上界的下标 while(low=high) mid=(low+high)2； 找中间位置 if(amid=x)break； 找到 x，退出 while 循环 else if(amidx)low=mid+1；到中点 mid 的右半去查 else high=mid1： 到中点 mid 的左半去查 if(amid=x q 一next 一pred=P；将 P 结点插入 p 一pred=q；q 一next=
35、p; return(P)； 返回值为 x 的结点的指针 提示：在算法中先查找数据 x，查找成功时结点的访问频度域增 1，最后将该结点按频度递减插入链表中。)解析：29.有一个不带头结点的单链表 list，链表中结点都有两个域：数据域 data 和指针域 Iink。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_正确答案：(正确答案：(1)算法的基本设计思想
36、：本题实质上是一个排序问题。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 (2)算法设计如下： typedef struct LNode int data； struct LNode *link； *linkedlist； LinkedList LinkListSort(LinkedList list) Lnode*p，*q； p=list 一link； p 是工作指针，指向待排序的当前元素 list 一link=null； 假定第一个元素有序，即链表中现只有一个结点 while(P!=null)f r
37、=p 一link； r 是 P 的后继 q=list； if(q 一datap 一data) 处理待排序结点 P 比第一个元素结点小的情况 p 一link=list： list=p；链表指针指向最小元素 else 查找元素值最小的结点 while(q 一link=null&q一link 一datap 一data)q=q 一link； p 一link=q 一link；将当前排序结点链入有序链表中 q 一link=P； P=r； p 指向下个待排序结点 )解析：30.如果以单链表表示集合，设集合 A 用单链表 LA 表示，集合 B 用单链表 LB 表示，设计算法求两个集合的差，即 A 一 B。（分
38、数：2.00）_正确答案：(正确答案：由集合运算的规则知，集合的差 A-B 为包含所有属于 A 而不属于 B 的元素，因此，算法的思路在于对于所有属于集合 A 中的元素 e，在集合 B 中进行查找，若能找到，则说明它不属于 AB，应从 LA 中删除。若 LA 的长度为 O(n)，LB 的长度为 O(m)，则该算法的时间复杂度为 O(mXn)。 算法参考伪代码如下： void Difference(LinkList*LA，LinkList * LB) 设 LA，LB 均具有头结点 Node*pre，*pre *p*r： pre=LA； p=LA 一next： p 指向 LA 表中的某一结点，而
39、pre 指向 P 的前面一个结点 while(P!=NULL) q=LB 一next； 遍历 LB 表，判断 LA 中元素是否在 LB 中 Node *while (q|=NULL&q 一data!=一data) q=q 一next if(q!=NULL) 在 LB 中找到相同结点元素，则应在 LA 中删除该结点 r=P： pre 一next=r 一next： p=p 一next： free(r)； else 未能找到，说明该结点属于 A-B 继续在 LA 中对下一个元素进行判断 pre=P： p=p 一next； )解析：31.已知 3 个带头结点的线性链表 A、B、C 中的结点均依元素值自
40、小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表 A 进行如下操作：使操作后的链表 A 中仅留下 3 个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p)，其中 m、n 和p 分别为 3 个表的长度。（分数：2.00）_正确答案：(正确答案：typedef struct LNode int data： struct LNode * next； *Linkedlist； LinkedList Common(LinkedList A，B，C) 链表 A、链表 B 和链表 C 是三个带头结点且结点元素值非递减排列的有序表 本算
41、法使链表 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一datapb 一data)u=Pa：pa=pa 一next；free(u)；结点元素值小时，后移指针 else if ( pa-datapb 一data)pb=pb 一next： else if(pa&pb) 处理链表 A 和 B 元素值相等的结点 while(pc&pc 一datapa 一data)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；
