有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在A和B的原有结点空间上完成。 (1)给出算法的基本设计思想。

admin2023-02-06 67

问题有两个集合A和B，利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在A和B的原有结点空间上完成。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)分别给出算法各部分的时间复杂度。

选项

答案(1)算法的基本设计思想：分别从A、B的头结点开始，依次比较A、B中元素的内容，如果A中的元素值大于B中的元素值，则将B中的结点插入结果链表，反之将A中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果A、B中两个元素值相同，只将其中的一个加入结果链表。 (2)算法的设计如下： [*] (3)本题中的主要操作是依次比较A、B链表中的数据元素值的大小，因此时间复杂度为O(n)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/jbwD777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下列关于课程计划编制原则的说法正确的是()。

任何一个班里都可能有学困生，学困生的转化是教师尤其是班主任的一项重要工作。下列不属于学困生特征的是()。

小张和小王是夫妻，在不同城市的税务局工作，为了解决夫妻分居的问题，小张所在机关用函向对方机关联系，商洽调动。这种做法属于文种使用错误。()

在班级开展的各种活动中，每一个成员都会通过自己和他人的表现以及所获得的评价，判断其表现的优势与不足。这主要体现了班级的()。

布鲁纳认为不论教师教什么学科，务必使学生理解该学科的基本结构。依此而建立的课程理论是()。

小雨是个敏感、细心的女孩，同时她又多疑、孤僻、多愁善感、不善于和同学交往，同学们都叫她“林妹妹”。小雨的气质类型属于()。

顺应性迁移是指将原有的经验应用于新情境时，需调整原有的经验或对新旧经验加以概括，形成一种能包容新旧经验的更高一级的经验结构，以适应外界的变化。根据上述定义，下列体现顺应性迁移的是：

人民检察院以王某涉嫌伤害案提起公诉，人民法院审理后认为起诉指控的事实清楚，证据确实、充分，但根据案件审理情况，应当认定王某构成故意伤害罪，而非人民检察院指控的故意杀人罪。那么，人民法院应当如何处理?

护士为不孕妇女介绍易受孕的时间，下列哪项正确()

已办理检验检疫手续的出口货物，因故需变更输入国家或地区的应重新报检。(　　)

我国实行联合缉私、统一处理、综合治理的缉私体制，海关在打击走私中处于主导地位并负责与有关部门的执法协调工作。

在探索战略与结构的关系方面，钱德勒在其经典著作《战略和结构》中，首次提出组织结构服从战略的理论。下列说法中，属于该理论观点的有()。

假如你生活在第二次工业革命时期，你不可能享受到的生活是用电脑上网。()

下边四个图形中，只有一个是由左边的四个图形拼合（只能通过上、下、左、右平移）而成的，请把它找出来：

下列关于赠与合同的说法，正确的有

WritingaResearchPaperI.ResearchPaperandOrdinaryEssayA.Similarityin【T1】________:

【B1】【B15】

计算机408

学硕统考专业

下列关于课程计划编制原则的说法正确的是()。

任何一个班里都可能有学困生，学困生的转化是教师尤其是班主任的一项重要工作。下列不属于学困生特征的是()。

小张和小王是夫妻，在不同城市的税务局工作，为了解决夫妻分居的问题，小张所在机关用函向对方机关联系，商洽调动。这种做法属于文种使用错误。()

在班级开展的各种活动中，每一个成员都会通过自己和他人的表现以及所获得的评价，判断其表现的优势与不足。这主要体现了班级的()。

布鲁纳认为不论教师教什么学科，务必使学生理解该学科的基本结构。依此而建立的课程理论是()。

小雨是个敏感、细心的女孩，同时她又多疑、孤僻、多愁善感、不善于和同学交往，同学们都叫她“林妹妹”。小雨的气质类型属于()。

顺应性迁移是指将原有的经验应用于新情境时，需调整原有的经验或对新旧经验加以概括，形成一种能包容新旧经验的更高一级的经验结构，以适应外界的变化。根据上述定义，下列体现顺应性迁移的是：

人民检察院以王某涉嫌伤害案提起公诉，人民法院审理后认为起诉指控的事实清楚，证据确实、充分，但根据案件审理情况，应当认定王某构成故意伤害罪，而非人民检察院指控的故意杀人罪。那么，人民法院应当如何处理?

护士为不孕妇女介绍易受孕的时间，下列哪项正确()

已办理检验检疫手续的出口货物，因故需变更输入国家或地区的应重新报检。( )

我国实行联合缉私、统一处理、综合治理的缉私体制，海关在打击走私中处于主导地位并负责与有关部门的执法协调工作。

在探索战略与结构的关系方面，钱德勒在其经典著作《战略和结构》中，首次提出组织结构服从战略的理论。下列说法中，属于该理论观点的有()。

假如你生活在第二次工业革命时期，你不可能享受到的生活是用电脑上网。()

下边四个图形中，只有一个是由左边的四个图形拼合（只能通过上、下、左、右平移）而成的，请把它找出来：

下列关于赠与合同的说法，正确的有

WritingaResearchPaperI.ResearchPaperandOrdinaryEssayA.Similarityin【T1】________:

【B1】【B15】

已办理检验检疫手续的出口货物，因故需变更输入国家或地区的应重新报检。(　　)