首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
admin
2019-08-01
72
问题
有两个集合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 LNode * next: }* Linkedlist; LinkedList Union(LinkedList la,lb){ pa=la一>next; pb=lb一>next; //设工作指针pa和pb pc=la; //pc为结果链表当前结点的前驱指针 while(pa&&pb){ if(pa一>data<pb一>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: free(u); } } if(pa)pc->next=pa; //若la表未空,则链入结果表 else pc->next=pb: //若lb表未空,则链入结果表 free(1b); //释放lb头结点 return(1a); } (3)本题中的主要操作是依次比较A、B链表中的数据元素值的大小,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/VACi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
完整地表述电磁场理论的物理学家是()。
真理标准问题大讨论
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
随机试题
在以下什么情况下货币供给增加?()
注射氯化钙如有外漏,应立即用何药作局部封闭
不是急性肝衰竭的临床表现的是
属于双面嵌体的是()
根据《税收征收管理法》的规定,纳税人未按期缴纳税款的,税务机关除责令限期缴纳外,从滞纳税款之日起,按日加收滞纳税款的()的滞纳金。
培训讲师应该具备的培训行为能力包括()。
设a=log36,b=log0.20.1,c=log714,则a,b、c大小关系是()。
刚刚来到单位,小赵对你做事指手画脚,还不时冷嘲热讽;小李对你特别亲热。尤其对你私生活非常感兴趣;小孙特别热情.第一次见你就称兄道弟。你怎么处理和他们的关系?
根据以下资料,回答91-95题2008年末,上海市百强企业集团年末资产总计28121.41亿元,比上年增长6.9%:从业人员123.39万,下降2.3%。全年完成营业收入15328.40亿元,增长7.9%;实现利润总额821.22亿元,下降40.5%。
A.嗜中性粒细胞B.破骨细胞C.髓石D.透明小体E.牙周袋牙体吸收有()。
最新回复
(
0
)