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

admin2023-02-06 38

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

学硕统考专业

在教育活动中，教师负责组织、引导学生沿着正确的方向，采用科学的方法，获得良好的发展。这句话的意思是说()。

关于教育测量中信度和效度的关系，下面表述正确的是()。

学生李明在上学的路上，因帮助突然生病的路人而迟到。老师征询大家的意见，是否按班规对李明进行处罚。张阳认为，李明帮助别人是对的，不应该处罚他。张阳的道德发展水平最可能处于()。

教师在心理健康教育工作中采取发展、预防和矫正相结合的原则，即将发展学生心理素质与预防、矫正心理问题结合起来，并重点关注()。

下雨不举行运动会，气温低不举行运动会，不举行运动会就举行表演，然后现在正举行运动会。由此可以推断出，必真条件包括()。　①不下雨　②气温高　③不表演

往某水库中注水，A泵注水400立方米后，换用注水速度是A泵2倍的B泵，已知B泵注水700立方米的时间比A泵注水400立方米的时间少50分钟，则A泵的注水速度为每分钟多少立方米?

Ourbodiesexperienceanebbandflowofenergythroughouttheday.Thisiscalledacircadianrhythm,andithasbeenstudied【C

Shehasstored______booksasⅠ.

老年男性，进行性黄疸2个月伴中上腹持续性疼痛，夜间平卧时明显，消瘦。查体：慢性消耗性病容，皮肤巩膜黄染，腹平坦。脐上偏右深压痛，Courvoisier征阳性，未及异常包块。该患者诊断首先考虑

A、苦杏仁苷B、萝卜苷C、山慈菇苷AD、芦荟苷E、鸟苷能水解产生氢氰酸的是()。

根据我国宪法规定，下列哪些人员须中华人民共和国主席根据全国人民代表大会的决定和全国人民代表大会常务委员会的决定予以任免?()

(2008年)图8-16所示电路中，电容的初始能量为0，设开关S在t=0时刻闭合，此后电路将发生过渡过程，那么，决定该过渡过程的时间常数，即()。

总分类账应根据记账凭证逐笔登记，明细分类账应根据原始凭证汇总登记。　　　　(　　)

科学发展观的根本方法是()。

A、 B、 C、 D、 B

计算机408

学硕统考专业

在教育活动中，教师负责组织、引导学生沿着正确的方向，采用科学的方法，获得良好的发展。这句话的意思是说()。

关于教育测量中信度和效度的关系，下面表述正确的是()。

学生李明在上学的路上，因帮助突然生病的路人而迟到。老师征询大家的意见，是否按班规对李明进行处罚。张阳认为，李明帮助别人是对的，不应该处罚他。张阳的道德发展水平最可能处于()。

教师在心理健康教育工作中采取发展、预防和矫正相结合的原则，即将发展学生心理素质与预防、矫正心理问题结合起来，并重点关注()。

下雨不举行运动会，气温低不举行运动会，不举行运动会就举行表演，然后现在正举行运动会。由此可以推断出，必真条件包括()。 ①不下雨 ②气温高 ③不表演

往某水库中注水，A泵注水400立方米后，换用注水速度是A泵2倍的B泵，已知B泵注水700立方米的时间比A泵注水400立方米的时间少50分钟，则A泵的注水速度为每分钟多少立方米?

Ourbodiesexperienceanebbandflowofenergythroughouttheday.Thisiscalledacircadianrhythm,andithasbeenstudied【C

Shehasstored______booksasⅠ.

老年男性，进行性黄疸2个月伴中上腹持续性疼痛，夜间平卧时明显，消瘦。查体：慢性消耗性病容，皮肤巩膜黄染，腹平坦。脐上偏右深压痛，Courvoisier征阳性，未及异常包块。该患者诊断首先考虑

A、苦杏仁苷B、萝卜苷C、山慈菇苷AD、芦荟苷E、鸟苷能水解产生氢氰酸的是()。

根据我国宪法规定，下列哪些人员须中华人民共和国主席根据全国人民代表大会的决定和全国人民代表大会常务委员会的决定予以任免?()

(2008年)图8-16所示电路中，电容的初始能量为0，设开关S在t=0时刻闭合，此后电路将发生过渡过程，那么，决定该过渡过程的时间常数，即()。

总分类账应根据记账凭证逐笔登记，明细分类账应根据原始凭证汇总登记。 ( )

科学发展观的根本方法是()。

A、 B、 C、 D、 B

下雨不举行运动会，气温低不举行运动会，不举行运动会就举行表演，然后现在正举行运动会。由此可以推断出，必真条件包括()。　①不下雨　②气温高　③不表演

总分类账应根据记账凭证逐笔登记，明细分类账应根据原始凭证汇总登记。　　　　(　　)