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

admin2023-02-06 61

问题有两个集合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

学硕统考专业

未成年人擅自外出夜不归宿的，其所在的寄宿制学校应及时查找，不应向公安机关请求帮助。()

甲本科毕业后，心系祖国边远地区的孩子，于是他到某边远贫困地区从事教育教学工作，地方政府不需要给予甲补贴。()

布鲁纳认为，学习知识的最佳方式是发现学习。()

()是班级组织长期形成的言论上、情绪上和行动上的共同倾向，是学生思想道德、人际关系、舆论力量等方面的精神风貌的综合反映。

法国教育家涂尔干认为，教育的目的在于使儿童的身体、智力和道德状况都得到某些激励与发展，适应整个社会在总体上对儿童的要求，适应儿童将来所处的特定环境的要求。由此可以看出，涂尔干强调教育应()。

两名或两名以上的教师合作施教，根据他们的能力和特长组成“互补性”的结构，通过分工协作，他们在教学工作中分别承担不同的角色和任务，共同负责一个或几个平行班的教学工作。这是()。

实际上普通话和方言不是同一层次上的交际工具。普通话是全民共同语，是官方语言，而方言是区域性的，是民间语言。通过明确，普通话和方言可以做到并行不悖，甚至，相得益彰。填入横线处的词语最恰当的一项是：

有n个结点的二叉树，已知叶结点个数为n0。(1)写出求度为1的结点的个数的nn1的计算公式。(2)若此树是深度为h的完全二叉树，写出n为最小的公式。(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。

培养钩端螺旋体的最佳温度是

A．固阴煎B．归肾丸C．逍遥散D．两地汤E．柴胡疏肝散肾虚导致的月经先后不定期宜选用

中药半浸膏片制备时，适合作为粉料的处方饮片是()

下面的(　　)不是设备制造监理的主要工作内容。

施工定额是以()作为对象编制，表示生产产品数量与生产要素消耗综合关系的定额。

根据《期货公司监督管理办法》，期货公司应当按照()的原则，建立并完善公司治理。[2015年5月真题]

根据个人所得税法的相关规定，下列关于每次收入的确定，说法不正确的是()。

甲、乙结婚后购得房屋一套，仅以甲的名义进行了房屋产权登记。后来甲、乙感情不合，甲擅自将该房屋以市场价格出售给不知情的丙，并办理了房屋所有权变更登记。根据物权法律制度的规定，下列说法正确的是()。

学生学习“功=力×距离”，这种学习属于()。

计算机408

学硕统考专业

未成年人擅自外出夜不归宿的，其所在的寄宿制学校应及时查找，不应向公安机关请求帮助。()

甲本科毕业后，心系祖国边远地区的孩子，于是他到某边远贫困地区从事教育教学工作，地方政府不需要给予甲补贴。()

布鲁纳认为，学习知识的最佳方式是发现学习。()

()是班级组织长期形成的言论上、情绪上和行动上的共同倾向，是学生思想道德、人际关系、舆论力量等方面的精神风貌的综合反映。

法国教育家涂尔干认为，教育的目的在于使儿童的身体、智力和道德状况都得到某些激励与发展，适应整个社会在总体上对儿童的要求，适应儿童将来所处的特定环境的要求。由此可以看出，涂尔干强调教育应()。

两名或两名以上的教师合作施教，根据他们的能力和特长组成“互补性”的结构，通过分工协作，他们在教学工作中分别承担不同的角色和任务，共同负责一个或几个平行班的教学工作。这是()。

有n个结点的二叉树，已知叶结点个数为n0。(1)写出求度为1的结点的个数的nn1的计算公式。(2)若此树是深度为h的完全二叉树，写出n为最小的公式。(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。

培养钩端螺旋体的最佳温度是

A．固阴煎B．归肾丸C．逍遥散D．两地汤E．柴胡疏肝散肾虚导致的月经先后不定期宜选用

中药半浸膏片制备时，适合作为粉料的处方饮片是()

下面的( )不是设备制造监理的主要工作内容。

施工定额是以()作为对象编制，表示生产产品数量与生产要素消耗综合关系的定额。

根据《期货公司监督管理办法》，期货公司应当按照()的原则，建立并完善公司治理。[2015年5月真题]

根据个人所得税法的相关规定，下列关于每次收入的确定，说法不正确的是()。

甲、乙结婚后购得房屋一套，仅以甲的名义进行了房屋产权登记。后来甲、乙感情不合，甲擅自将该房屋以市场价格出售给不知情的丙，并办理了房屋所有权变更登记。根据物权法律制度的规定，下列说法正确的是()。

学生学习“功=力×距离”，这种学习属于()。

下面的(　　)不是设备制造监理的主要工作内容。