首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
有两个集合A和B,利用带头结点链表表示,设头指针分别为la和lb。两集合的链表元素皆为递增有序。设计一个算法,将A与B合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在A和B的原有结点空间上完成。要求: (1)给出算法的基
admin
2019-08-01
76
问题
有两个集合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年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
明清时期专制主义空前加强,据此回答问题:清代在散文方面,声势最大、影响最广的是桐城派,不属于该派的是()
租庸调制对农业生产的最大作用是()。
下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
TCP/IP网络中,某主机的IP地址为130.25.3.135,子网掩码为255.255.255.192,那么该主机所在的子网的网络地址是()。
随机试题
对于理想气体系统,在下列过程中,系统所吸收的热量、热力学能的增量和对外做的功三者均为负值的是()
属于牙源性囊肿的是
A.姜半夏B.法半夏C.清半夏D.生半夏E.炒半夏小陷胸汤在调配时,半夏应给付的是
如果天龙食品厂于1999年9月12日向新桥区人民法院提起行政诉讼,那么:①人民法院是否应受理本案?②如果受理,法院是否可以对两个诉讼请求一并审理?为什么?③如果市法院于2000年5月5日做出终审判决维持了新桥区工商局的处理决定,天龙
会计工作交接完毕后,交接双方和监交人要在移交清册上签名盖章,移交清册填制一式两份,交接双方各持一份。()
解释测验结果的参照指标是()
中低端手机的巨大出货量推动了国产手机的繁荣。但低端意味着低利润,国产手机仍____________于“来料加工,仿制生产”的流水线生产经营理念,在产品创新方面缺乏核心竞争力。目前,大多数国产手机没有实质的功能和核心创新,很难获得强大的品牌影响力,最终还是只
设向量组α,β,γ线性无关,而向量组aα一β,bβ一γ,cγ—α线性相关,则().
现有以下程序:PrivateSubCommandlClick()cl=0c2=0Fori=lTo100IfiMod3=0Thencl=el+1ElseIfiMo
WorkshoptoFocusonGrantProcessLauraChinwillpresentaworkshopThursdayshowingnonprofitgroupshowtoapplyforNeighbo
最新回复
(
0
)