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

admin2023-02-06 43

问题有两个集合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://jikaoti.com/ti/WrPiFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

根据教师法的有关规定，下列不属于学校可以解聘教师的情形的是()。

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

外铄论认为人的发展主要依靠外在的力量，如环境的压力、刺激和要求，他人的影响和学校的教育。持这一观点的思想家有()。

从所给四个选项中，选出能与给定的①、②、③、④零件共同构成如下图所示的9×2方块组合的一项：

某智能停车场泊车的泊车位置由电脑随机派位生成。现有两排车位，每排4个，有4辆不同的车需要泊车。泊车要求至少有一车与其他车不同排，且甲乙两车在同一排。则电脑可生成几种派位方式?()

微躺青年：指面对现实中的竞争压力，既不参与过度竞争，也不消极接受现状，而在专注于本职工作的同时，合理调整工作方向，追求自我价值实现的年轻人。下列属于微躺青年的是：

H市为推动生态园林城市建设，在全市组织了一次植树活动。已知银杏、香樟、雪松三种树分别为2100株、2050株、1900株，现从这三种树中随机选取栽种到新城地区，为保证有一种树总数量为2017株，则至少选取树木的株数是：

平均动脉压(MAP)为：

下列辅食适于7个月小儿添加的是

杀死病毒与芽孢的最佳消毒剂为

民用建筑基地内关于何时应设置人行道的表述中，下列哪项正确?[2010-64]

保安服务公司性质是()。

关于加快转变经济发展方式的基本要求，下列说法不正确的是()。

【《雅尔塔协定》】南京大学2001年世界近现代史真题

Whenaliquidboils,itbecomesagas.

Theregistrationnumberofthecartherobbersdroveis______.

Thehousecaughtfireon____________,in1982.