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

admin2023-02-06 27

问题有两个集合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://kaotiyun.com/show/jbwD777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

学习疲劳是指学习者由于学习过度或学习方法不当而产生的学习效率逐渐降低，并伴有渴望停止学习活动的生理和心理现象。()

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

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

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

课程在纵向结构上的表现形式有()。

辅助生殖技术有人工授精、体外受精与胚胎移植、卵细胞浆内单精子注射、配子移植技术等。()

《灵枢.卫气》论述了"气街"，气街是指经气聚集通行的道路。

中国甲公司与法国乙公司商谈进口特种钢材，乙公司提供了买卖该种钢材的格式合同，两国均为1980年《联合国国际货物销售合同公约》缔约国。根据相关规则，下列哪一选项是正确的？（2014年卷一第40题）

一般超载潜力较大，砌筑技术容易掌握，便于群众修建的一种涵洞形式是()。

在政府对商品价格和货币工资进行严格控制的情况下，隐蔽型通货膨胀可以表现为()。

下列情形违背一物一权原则的是()。

没有行政管理决策，就没有国家行政行为，也就不能实现国家对广泛社会生活的领导、干预和管理，政府也就失去了基本功能和存在的意义。()

-5，2，3，4，11，()。

“认可”是法律产生的方式之一，下列哪一项不属于“认可”?()

Whereisthewomanfrom?