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

admin2023-02-06 36

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

学硕统考专业

某校通过创设良好的环境，如提供美观清洁的校园、朴实庄重的校舍、明亮整洁的教室，营造良好的学风班风来对学生进行道德教育。这种做法体现的德育方法的是()。

“挂钥匙儿童”是指因父母出去工作，放学后独自在家、无人照看的孩子。这是()对孩子带来的负面影响。

党在新世纪新阶段的任务包括()。

根据十九大精神，全面从严治党需要把()摆在首位。

某装修公司订购了一条长为2．5m的条形不锈钢管，要剪裁成60cm和43cm长的两种规格长度不锈钢管若干根，所裁钢管的横截面与原来一样，不考虑剪裁时材料的损耗，要使剩下的钢管尽量少，此时材料的利用率为：

某市举行庆典活动，将依次升空105架无人机，升空方式如下：每架无人机间距均相等，第一次升空n架，第二次升空n—1架，以此类推，最终在夜空中组成一个近似等边三角形背景的灯光秀，那么第10次升空的无人机数量是：

公司某部门开展活动要拍照留念，该部门7个人排成一排，7人身高各不相同，其中部“经理最高站在中间，从中间到两边由高到低依次排序，其排序的方法有()种。

下列4幅图是红军长征宣传图，按照发生时间先后排序正确的是：①②③④

心肌收缩时胞质内增多的钙离子最重要来源于

设f(1／x)=x()2，则f(x)=_______．

在《宝玉挨打》中，贾政狠打宝玉的根本原因是

54岁女性，脑动脉硬化症病史3年，突感眩晕、呕吐、言语不清。查体：声音嘶哑、吞咽困难、言语含混，左眼裂小、瞳孔小、水平眼震、左面部右半身痛觉减退，左侧指鼻试验不准．诊断

关于注册证书和执业印章失效情形的说法，正确的有()。

某建筑工地施工需要使用各种机械设备，在施工阶段这些机械设备的噪声LAeqdB()不得超过的限值。

金融市场运行的关键是()。

建立评价学生全面发展的评价指标体系必须包括()。

WhendidMissGreenbecomeaswimmingstar?HowoldisMissGreennow?

Youcanperformallthosefunctionsthatyouperformatpresentwithyourmobiledevicesbutofmuchhigherspeedthan【M1】______