首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
admin
2019-01-16
56
问题
有两个集合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)算法的设计如下: typedef struct LNode{ int data; struct INode*next; }* Linkedlist; LinkedList union(IAnkedList la,lb){ pa=la一>next; pb=lb一>next; //设工作指针pa和pb pc=la; //pc为结果链表当前结点的前驱指针 while(pa&&pb){ if(pa->data
data){ pc->next=pa; pc=pa; pa=pa->next } else if(pa->data>pb->data){ pc->next=pb; pc=pb; pb=pb一>next; } else{ //处理pa一>data=pb一>data. pc->next=pa: pc=pa; pa=pa一>next; u=pb; pb=pb一>next; flee(u); } } if(pa)pc一>next=pa; //若la表未空,则链入结果表 else pc->next=pb; //若lb表未空,则链入结果表 free(lb): //释放lb头结点 return(1a); } (3)本题中的主要操作是依次比较A、B链表中的数据元素值的大小,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/ciRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
“两个凡是”
苏联实行的新经济政策与美国推行的罗斯福新政之间的相似之处是()。①面临极为困难的经济形势②最主要内容是调整和复兴工业③国家颁布法令强制干预经济④通过发展商品经济生产来恢复农业
第一次鸦片战争、第二次鸦片战争的时间,分别对应于法国的()时期和()时期。
第二次世界大战后,资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力
清廷实行厘金制度的时间是()。
提出电磁感应定律的是物理学家()。
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
比较IEEE802.11使用的CSMA/CA与IEEE802.3使用的CSMA/CD之间的区别。
随机试题
一般情况下,国家的经济制度不发生根本变化,作为社会上层基础重要组成部分的政治制度也不会发生根本性的变化。这说明政治制度具有()
现对某企业价值进行评估,有关资料如下:根据该企业前5年的经营实绩预测其未来5年的收益额分别为20万元、21万元、23万元、25万元、28万元。根据资料确定国库券利率为10%,风险报酬率为3%,资本化率为12%。假定从第6年起,每年收益额均为28万元,根据以
“母乳喂养有效”的护理诊断常用下列哪种方式陈述()
沉箱下水,沉箱尺寸:长8m、宽6m、高10m,由长3.65m、宽2.65m的4个仓格组成,沉箱底板厚0.4m。下水时,从潮汐表上查得潮高为1.0m,箱内压水顶面较当地理论深度基准面低4.0m,沉箱干舷高2.0m,浮游稳定的最小吃水6.0m,当地理论深度基准
下列不属于有限责任公司的股东会职权的是()。
坚持党的基本路线不动摇,关键是坚持四项基本原则不动摇。()
社会工作者和居民初次接触,在取得居民同意的情况下,要迅速进入热身阶段。热身阶段最主要是()。
根据“中国商业企业诚信公约”,下列说法中,正确的是()。
依法治国是现代社会的重要标志。()
数据库管理系统不具备的功能是()。
最新回复
(
0
)