1、计算机学科专业基础综合数据结构-1 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：25，分数：74.00)1.在下列关于线性表的叙述中，正确的是_。（分数：2.00）A.线性表的逻辑顺序与物理顺序总是一致的B.线性表的顺序存储表示优于链式存储表示C.线性表若采用链式存储表示时，所有存储单元的地址可连续也可不连续D.每种数据结构都应具备三种基本运算：插入、删除和查找2.在线性表中的每一个表元素都是数据对象，它们是不可再分的_。（分数：2.00）A.数据项B.数据记录C.数据元素D.数据字段3.对于顺序存储的线性表，其算法的时间复杂度为 O(1)的运算应是_。（分数
2、：2.00）A.将 n 个元素从小到大排序B.从线性表中删除第 i 个元素(1in)C.查找第 i 个元素(1in)D.在第 i 个元素后插入一个新元素(1in)4.下面的叙述正确的是_。（分数：2.00）A.线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关B.线性表在链式存储时，查找第 i 个元素的时间同 i 的值成反比C.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比D.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关通常查找线性表数据元素的方法有 () 和 () 两种方法，其中 () 是一种只适合于顺序存储结构但 () 的方法；而 () 是一种对顺
3、序和链式存储结构均适用的方法。（分数：6.00）A.顺序查找B.循环查找C.条件查找D.折半查找A.顺序查找B.随机查找C.折半查找D.分开查找A.效率较低的线性查找B.效率较低的非线性查找C.效率较高的非线性查找D.效率较高的线性查找若设一个顺序表的长度为 n。那么，在表中顺序查找一个值为 x 的元素时，在等概半的情况下，查找成功的数据平均比较次数为_。在向表中第 i 个元素(1in+1)位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移_个元素。在删除表中第 i 个元素(1in)时，同样地，为保持删除后表中原有元素的相对次序不变，需要从从向后依次前移_个元素
4、。（分数：6.00）AnB.n/2C.(n+1)/2D.(n-1)/2A.n-iB.n-i+1C.n-i-1DiA.n-iB.n-i+1C.n-i-1Di5.在长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为_。（分数：2.00）A.O(n)B.O(1)C.O(n2)D.O(log2n)6.从一个具有 n 个结点的有序单链表中查找值等于 x 的结点时，在查找成功的情况下，需要平均比较的结点个数为_。（分数：2.00）AnB.n/2C.(n-1)/2D.(n+1)/27.在一个具有 n 个结点的单链表中插入一个新结点并可以不保持原有顺序的算法的时间复杂度是_。（分数：2.00）A.O(
5、1)B.O(n)C.O(n2)D.O(nlog2n)8.给定有 n 个元素的一维数组，建立一个有序单链表的时间复杂度是_。（分数：2.00）A.O(1)B.O(n)C.O(n2)D.O(m+n)9.已知单链表 A 长度为 m，单链表 B 长度为 n，若将 B 连接到 A 的末尾，在没有链尾指针的情形下，算法的时间复杂度应为_。（分数：2.00）A.O(1)B.O(m)C.O(n)D.O(m+n)10.已知 L 是带表头的单链表，L 是表头指针，则摘除首元结点的语句是_。（分数：2.00）A.L=L-link;B.L-link=L-link-link;C.L=L-link-link;D.L-li
6、nk=L;设单链表中结点的结构为 Typedef struct.node /链表结点定义 ElemType data; /数据 struct node*link; /结点后继指针 LinkedNode;（分数：16.00）(1).不带头结点的单链表 first 为空的判定条件是_。（分数：2.00）A.first=NULL；B.first-link=NULL;C.first-link=first；D.first!=NULL;(2).带头结点的单链表 first 为空的判定条件是_。（分数：2.00）A.first=NULL;B.first-link=NULL;C.first-link=firs
7、t;D.first!=NULL;(3).已知单链表中结点 * q 是结点 * p 的直接前驱，若在 * q 与 * p 之间捅入结点 * s，则应执行以下_操作。（分数：2.00）A.s-link=p-link;p-link=s;B.q-link=s;s-link=p;C.p-link=s-link;s-link=p;D.first!=NULL;(4).已知单链表中结点 * p 不是链尾结点，若在 * p 之后插入结点 * s，则应执行下列_操作。（分数：2.00）A.s-link=p；p-link=s；B.p-link=s；s-link=p；C.s-link=p-link；p=s；D.s-l
8、ink=p-link；p-link=s；(5).若想在单链表中摘除结点 * p( * p 既不是第一个也不是最后一个结点)的直接后继，则应执行以下_操作。（分数：2.00）A.p-link=p-link-link;B.p=p-link;p-link=p-link-link;C.p-link=p-link;D.p=p-link-link;(6).非空的循环单链表 first 的链尾结点(由 p 所指向)满足_。（分数：2.00）A.p-link=NULL;B.p=NULL;C.p-link=first;D.p=first;(7).设 rear 是指向非空的带表头结点的单循环链表的链尾结点的指针。
9、若想删除链表第一个结点，则应执行以下_操作。（分数：2.00）A.s=rear;rear=rear-link;delete s;B.rear=rear-link;delete rear;C.rear=rear-link-link;delete rear;D.s=rear-link-link;rear-link-link=s-link;delete s;(8).设双向循环链表中结点的结构为(data，lLink，rLink)，且不带表头结点。若想在结点 * p 之后捅入结点 * s，则应执行以下_操作。（分数：2.00）A.p-rLink=s;s-lLink=p;p-rLink-lLink=s;
10、s-rLink=p-rLink;B.p-rLink=s;p-rLink-lLink=s;s-lLink=p;s-rLink=p-rLink;C.s-lLink=p;s-rLink=p-rLink;p-rLink=s;p-rLink-lLink=s;D.s-lLink=p;s-rLink=p-rLink;p-rLink-lLink=s;p-rLink=s;11.利用双向链表做线性表的存储结构的优点是_。（分数：2.00）A.便于进行插入和删除的操作B.提高按关系查找数据元素的速度C.节省空间D.便于销毁结构释放空间12.已知 L 是一个不带表头的，在表头插入结点 * p 的操作是_。（分数：2.
11、00）A.p=L;p-link=L;B.p-link=L;p=L;C.p-link=L;L=p;D.L=p;p-link=L;13.已知 L 是带表头的单链表，删除首元结点的语句是_。（分数：2.00）A.L=L-link;B.L-link=L-link-link;C.L=L;D.L-link=L;14.在以下有关静态链表的叙述中，错误的是_。 (1)静态链表既有顺序存储的优点，又有链接存储的优点。所以，它存取表中第 i 个元素的时间与 i 无关。(2)静态链表中可容纳元素个数的最大数目在定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。（分数
12、：2.00）A.(1)(2)B.(1)C.(1)(2)(3)D.(2)15.若某表最常用的操作是在最后一个结点之后插入一个结点后再删除最后一个结点，则采用_存储方式最节省运算时间。（分数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表16.静态链表中指针表示的是_。（分数：2.00）A.内存地址B.数组的下标C.下一元素数组下标D.左、右孩子地址17.顺序表是线性表的_存储表示。（分数：2.00）A.有序B.连续C.数组D.顺序存取18.线性表是具有 n 个_的有限序列(n0)。（分数：2.00）A.表元素B.字符C.数据元素D.数据项19.下述哪一条是顺序存储结构的优点
13、?（分数：2.00）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示20.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为_(1in+1)。（分数：2.00）A.O(0)B.O(1)C.O(n)D.O(n2)21.若循环队列以数组 Q0，m-1作为其存储结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1) MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是_。（分数：2.00）A.rear-lengthB.(rear-len
14、gth+m) MOD mC.(rear-length+l+m) MOD mD.m-length数据结构反映了数据元素之间的结构关系。单链表是一种_，它对于数据元素的插入和删除_。（分数：4.00）A.顺序存储线性表B.非顺序存储非线性表C.顺序存储非线性表D.非顺序存储线性表A.不需移动结点，不需改变结点指针B.不需移动结点，只需改变结点指针C.只需移动结点，不需改变结点指针D.既需移动结点，又需改变结点指针二、综合应用题(总题数：1，分数：26.00)22.已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。用 C 语言编写一函数，求 A 和 B 的交集，并存放于 A 链表中。 （分
15、数：26.00）_计算机学科专业基础综合数据结构-1 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：25，分数：74.00)1.在下列关于线性表的叙述中，正确的是_。（分数：2.00）A.线性表的逻辑顺序与物理顺序总是一致的B.线性表的顺序存储表示优于链式存储表示C.线性表若采用链式存储表示时，所有存储单元的地址可连续也可不连续D.每种数据结构都应具备三种基本运算：插入、删除和查找 解析：解析 本题主要考查线性结构的特点和线性表的定义。线性表的顺序存储与链式存储在不同的情况下各有利弊，无优劣之分。 链式存储表示要求结点内的存储单元一定连续。2.在线性表中的每一个表
16、元素都是数据对象，它们是不可再分的_。（分数：2.00）A.数据项B.数据记录C.数据元素 D.数据字段解析：解析 线性表是 n(n0)个数据元素的有限序列。数据记录、数据字段是数据库文件组织中的术语。数据项相当于数据元素中的属性。 本题考查的依然是线性表的基本定义。3.对于顺序存储的线性表，其算法的时间复杂度为 O(1)的运算应是_。（分数：2.00）A.将 n 个元素从小到大排序B.从线性表中删除第 i 个元素(1in)C.查找第 i 个元素(1in) D.在第 i 个元素后插入一个新元素(1in)解析：解析 在顺序存储的线性表中查找第 i 个元素时可直接访问。4.下面的叙述正确的是_。（
17、分数：2.00）A.线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关B.线性表在链式存储时，查找第 i 个元素的时间同 i 的值成反比C.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比D.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关 解析：解析 本题主要考查的知识点是顺序存储结构和链式存储结构中查找一个元素的时间复杂度。顺序存储的主要优点：可以随机存取表中任一元素，因此，查找第 i 个元素的时间同 i 的值无关。而链式存储结构中只能按顺序查找元素，因此，查找第 i 个元素的时间同 i 的值成正比。 我们通过定义可知，顺序表可以随机存取表中任一元素，因
18、此查找第 i 个元素的时间与 i 的值无关。通常查找线性表数据元素的方法有 () 和 () 两种方法，其中 () 是一种只适合于顺序存储结构但 () 的方法；而 () 是一种对顺序和链式存储结构均适用的方法。（分数：6.00）A.顺序查找B.循环查找C.条件查找D.折半查找 解析：A.顺序查找 B.随机查找C.折半查找D.分开查找解析：A.效率较低的线性查找B.效率较低的非线性查找C.效率较高的非线性查找 D.效率较高的线性查找解析：解析 在线性表中查找指定元素采用顺序查找法和折半查找法。顺序查找法属于线性查找，效率较低，但它适用于用顺序方式或用链接方式存储的线性表；折半查找法仅适用于已排序的
19、顺序存储线性表，每次根据查找值的大小将查找区间缩小一半继续查找，因此它不是线性查找，它比顺序查找的效率高一些。若设一个顺序表的长度为 n。那么，在表中顺序查找一个值为 x 的元素时，在等概半的情况下，查找成功的数据平均比较次数为_。在向表中第 i 个元素(1in+1)位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移_个元素。在删除表中第 i 个元素(1in)时，同样地，为保持删除后表中原有元素的相对次序不变，需要从从向后依次前移_个元素。（分数：6.00）AnB.n/2C.(n+1)/2 D.(n-1)/2解析：A.n-iB.n-i+1 C.n-i-1Di解析
20、：A.n-i B.n-i+1C.n-i-1Di解析：解析 在长度为 n 的顺序表中，若各元素查找概率相等，则查找成功的平均查找长度为： 5.在长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为_。（分数：2.00）A.O(n)B.O(1) C.O(n2)D.O(log2n)解析：解析 在有 n 个元素的顺序表的表尾插入一个新元素，可直接在表的第 n+1 个位置插入，渐进时间复杂度为 O(1)。6.从一个具有 n 个结点的有序单链表中查找值等于 x 的结点时，在查找成功的情况下，需要平均比较的结点个数为_。（分数：2.00）AnB.n/2C.(n-1)/2D.(n+1)/2 解析：解析
21、有序单链表在查找成功时的查找性能与一般单链表相同。7.在一个具有 n 个结点的单链表中插入一个新结点并可以不保持原有顺序的算法的时间复杂度是_。（分数：2.00）A.O(1) B.O(n)C.O(n2)D.O(nlog2n)解析：解析 此时插在链头即可。8.给定有 n 个元素的一维数组，建立一个有序单链表的时间复杂度是_。（分数：2.00）A.O(1)B.O(n)C.O(n2) D.O(m+n)解析：解析 每插入一个元素，就需遍历链表找插入位置，此即链表插入排序。9.已知单链表 A 长度为 m，单链表 B 长度为 n，若将 B 连接到 A 的末尾，在没有链尾指针的情形下，算法的时间复杂度应为_
22、。（分数：2.00）A.O(1)B.O(m) C.O(n)D.O(m+n)解析：解析 需要寻找表 A 的链尾，遍历表 A 的 m 个结点。10.已知 L 是带表头的单链表，L 是表头指针，则摘除首元结点的语句是_。（分数：2.00）A.L=L-link;B.L-link=L-link-link; C.L=L-link-link;D.L-link=L;解析：解析 首元结点在表头结点后面，实际摘除的是表头结点后面的结点。设单链表中结点的结构为 Typedef struct.node /链表结点定义 ElemType data; /数据 struct node*link; /结点后继指针 Linke
23、dNode;（分数：16.00）(1).不带头结点的单链表 first 为空的判定条件是_。（分数：2.00）A.first=NULL； B.first-link=NULL;C.first-link=first；D.first!=NULL;解析：(2).带头结点的单链表 first 为空的判定条件是_。（分数：2.00）A.first=NULL;B.first-link=NULL; C.first-link=first;D.first!=NULL;解析：(3).已知单链表中结点 * q 是结点 * p 的直接前驱，若在 * q 与 * p 之间捅入结点 * s，则应执行以下_操作。（分数：2.
24、00）A.s-link=p-link;p-link=s;B.q-link=s;s-link=p; C.p-link=s-link;s-link=p;D.first!=NULL;解析：(4).已知单链表中结点 * p 不是链尾结点，若在 * p 之后插入结点 * s，则应执行下列_操作。（分数：2.00）A.s-link=p；p-link=s；B.p-link=s；s-link=p；C.s-link=p-link；p=s；D.s-link=p-link；p-link=s； 解析：(5).若想在单链表中摘除结点 * p( * p 既不是第一个也不是最后一个结点)的直接后继，则应执行以下_操作。（分
25、数：2.00）A.p-link=p-link-link; B.p=p-link;p-link=p-link-link;C.p-link=p-link;D.p=p-link-link;解析：(6).非空的循环单链表 first 的链尾结点(由 p 所指向)满足_。（分数：2.00）A.p-link=NULL; B.p=NULL;C.p-link=first;D.p=first;解析：(7).设 rear 是指向非空的带表头结点的单循环链表的链尾结点的指针。若想删除链表第一个结点，则应执行以下_操作。（分数：2.00）A.s=rear;rear=rear-link;delete s;B.rear=
26、rear-link;delete rear;C.rear=rear-link-link;delete rear;D.s=rear-link-link;rear-link-link=s-link;delete s; 解析：(8).设双向循环链表中结点的结构为(data，lLink，rLink)，且不带表头结点。若想在结点 * p 之后捅入结点 * s，则应执行以下_操作。（分数：2.00）A.p-rLink=s;s-lLink=p;p-rLink-lLink=s;s-rLink=p-rLink;B.p-rLink=s;p-rLink-lLink=s;s-lLink=p;s-rLink=p-rLi
27、nk;C.s-lLink=p;s-rLink=p-rLink;p-rLink=s;p-rLink-lLink=s;D.s-lLink=p;s-rLink=p-rLink;p-rLink-lLink=s;p-rLink=s; 解析：解析 (1)(2)若单链表不带表头结点， * first 即为首元结点(第一个结点)，链表为空即 first为空；若单链表带有表头结点， * first 即为表头结点，链表为空即表头结点后面没有首元结点，first-link 为空。 (3)已知单链表中结点 * q 是结点 * p 的直接前驱，若在 * q 与 * p 之间插入结点 * s，需要把 * s 链接到 *
28、q 之后，把 * p 链接到 * s 之后：q-link=s;s-link=p。 (4)已知单链表中结点 * p 不是链尾结点，若在 * p 之后插入结点 * s，需要把原来 * p 后的结点先链接到 * s 之后，再把 * s 链接到 * p 之后：s-link=p-link;p-link=s。 (5)若想在单链表中摘除结点 * p( * p 既不是第一个也不是最后一个结点)的直接后继，需要做重新链接工作，让 * p 的后继的后继成为 * p 的后继：p-link=p-link-link。 (6)非空的循环单链表 first 的链尾结点为 * p，则 * p 的后继为空：p-link=NUL
29、L。 (7)设 rear 是非空带表头结点的单循环链表的链尾指针。若想删除链表第一个结点，必须先保存要删除的表头结点的后继结点地址：s=rear-link-link；再做重新链接工作，让 * s 的后继链接到表头结点之后：rear-link-link=s-link；最后做删除：delete s。 (8)若想在不带表头结点的双向循环链表中的结点 * p 之后插入结点 * s，需在两个链上做插入，插入过程中要小心，不要让其中任何一个链断掉。选项 A 和选项 B 首先排除，因为第一条语句 p-rlink=s 就让后继链断掉了，选项 C 和选项 D 前两条语句 s-llink=p；s-rlink=p-
30、rlink 合理，让 * s 的前驱、后继都链接好且未影响原来的两个链，但选项 C 的第三条语句 p-rlink=s 又断开了后继链，排除它就剩下选项 D，它是对的。11.利用双向链表做线性表的存储结构的优点是_。（分数：2.00）A.便于进行插入和删除的操作B.提高按关系查找数据元素的速度 C.节省空间D.便于销毁结构释放空间解析：解析 查找直接前驱和直接后继的时间代价都是 O(1)。12.已知 L 是一个不带表头的，在表头插入结点 * p 的操作是_。（分数：2.00）A.p=L;p-link=L;B.p-link=L;p=L;C.p-link=L;L=p; D.L=p;p-link=L;
31、解析：解析 要插入在表头，同时改变表头指针。13.已知 L 是带表头的单链表，删除首元结点的语句是_。（分数：2.00）A.L=L-link;B.L-link=L-link-link; C.L=L;D.L-link=L;解析：解析 先把首元结点从链中摘下来，再把它的后继链接到表头结点之后。14.在以下有关静态链表的叙述中，错误的是_。 (1)静态链表既有顺序存储的优点，又有链接存储的优点。所以，它存取表中第 i 个元素的时间与 i 无关。(2)静态链表中可容纳元素个数的最大数目在定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。（分数：2.00
32、）A.(1)(2) B.(1)C.(1)(2)(3)D.(2)解析：解析 静态链表还是链表，逻辑顺序与物理顺序不一定一致。15.若某表最常用的操作是在最后一个结点之后插入一个结点后再删除最后一个结点，则采用_存储方式最节省运算时间。（分数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 解析：解析 本题考查的是各种链表的主要特点，顺序表的主要特点是查找方便，而链表的主要特点是插入和删除元素方便。引入双向循环链表更是为了满足查找、插入、删除多方面的性能。16.静态链表中指针表示的是_。（分数：2.00）A.内存地址B.数组的下标C.下一元素数组下标 D.左、右孩子地址解析：
33、解析 静态链表可用一维数组来实现。静态链表借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组的下标)，称之为静态指针。17.顺序表是线性表的_存储表示。（分数：2.00）A.有序B.连续C.数组 D.顺序存取解析：解析 顺序表是线性表的数组存储表示，也称为线性表的顺序存储结构。注意，顺序存取是一种读写方式，不是存储方式，有别于顺序存储。18.线性表是具有 n 个_的有限序列(n0)。（分数：2.00）A.表元素B.字符C.数据元素 D.数据项解析：解析 本题考查的是线性表的基本概念，要熟记。19.
34、下述哪一条是顺序存储结构的优点?（分数：2.00）A.存储密度大 B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示解析：解析 本题主要考查的知识点是顺序存储结构的特点。顺序存储的主要优点：可以顺序存取表中任意元素；主要缺点：在插入、删除某一元素时，需要移动大量元素。20.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为_(1in+1)。（分数：2.00）A.O(0)B.O(1)C.O(n) D.O(n2)解析：解析 本题主要考查的知识点是顺序存储结构中，插入元素的时间复杂度。由于在插入过程中，需要移动第 i 个位置后面所有的元素
35、，因此时间复杂度为：O(n)。21.若循环队列以数组 Q0，m-1作为其存储结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1) MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是_。（分数：2.00）A.rear-lengthB.(rear-length+m) MOD mC.(rear-length+l+m) MOD m D.m-length解析：解析 按照循环队列的定义，因为元素移动按照 rear=(rear+1) MOD m 进行，则当数字 Qm-1存放了元素之后，下一个入队的元素将存放到 Q0中
36、，因此队列的首元素的实际位置是(rear-length+1+m) MOD m。数据结构反映了数据元素之间的结构关系。单链表是一种_，它对于数据元素的插入和删除_。（分数：4.00）A.顺序存储线性表 B.非顺序存储非线性表C.顺序存储非线性表D.非顺序存储线性表解析：A.不需移动结点，不需改变结点指针B.不需移动结点，只需改变结点指针 C.只需移动结点，不需改变结点指针D.既需移动结点，又需改变结点指针解析：解析 数据结构通常指的是数据的逻辑结构，它反映了数据元素之间的逻辑关系，单链表属于线性表的一种存储结构，它的每个结点有两个域(data，link)，data 域存放元素值，link 域存放
37、表中逻辑上相邻的下一结点的地址指针。通过结点指针，线性表中所有元素按照逻辑顺序链接起来，而在物理上，结点之间的存储位置可以与逻辑顺序不一致，所以单链表是一种非顺序存储的线性表。在单链表中删除或插入元素比较方便，无须改变结点的存储位置，只要修改几个结点的指针即可。二、综合应用题(总题数：1，分数：26.00)22.已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。用 C 语言编写一函数，求 A 和 B 的交集，并存放于 A 链表中。 （分数：26.00）_正确答案：()解析：LinkedList la; la=(LinkedList) malloc(sizeof(LNode); la-
38、next=ha; /申请头结点,以便操作 pa=ha; /pa 是 ha 链表的工作指针 pb=hb; /pb 是 hb 链表的工作指针 pre=la; /pre 指向当前待合并结点的前驱 while(pa pa=pa-next: else if(pa-datapb-data) /处理 hb 中的数据 R=(LinkedList) malloc (sizeof (LNode); /申请空间 R-data=pb-data; pre-next=r; pre=r; /将新结点链入结果链表 pb=pb-next; /hb 链表中工作指针后移 else /处理 pa-data=pb-data; pre-next=pa; Pre=pa; pa=pa-next; /两结点数据相等时,只将 ha 的数据链入 pb=pb-next; /不要 hb 的相等数据 if(pa!=null)pre-next=pa; /将两链表中剩余部分链入结果链表 else pre-next=pb; free(la); /释放头结点,ha、hb 指针未被破坏 /算法 Union 结束 解析 因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。如果遇上相等的元素，只需记录一个，并同时向后移动链表工作指针。
