首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带头结点单链表的结点类型nextNode定义为struct nextNode{int data;int freq;struct nextNode *next; };其中,data为结点值域,freq为该结点元素的访问计数,初始为O;next为指向链
已知一个带头结点单链表的结点类型nextNode定义为struct nextNode{int data;int freq;struct nextNode *next; };其中,data为结点值域,freq为该结点元素的访问计数,初始为O;next为指向链
admin
2017-04-28
74
问题
已知一个带头结点单链表的结点类型nextNode定义为struct nextNode{int data;int freq;struct nextNode *next; };其中,data为结点值域,freq为该结点元素的访问计数,初始为O;next为指向链表中该结点后继结点的指针域,设该链表所有结点按照freq值从大到小链接。请设计一个时间和空间上尽可能高效的算法,编写一个查找函数Search,从链表首结点开始查找结点data值与给定值相等的结点。如果找到,则将该结点的freq值加1,然后把它前移到与结点freq值相等的结点的后面,使得所有结点仍然都保持按照freq值从大到小链接。
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析:除去链表本身的空间外,额外的空间消耗为O(1)。 时间复杂度分析:整个算法只会对链表进行一次扫描,扫描的时候把需要的信息都记录下来,然后用O(1)的时间完成链表的修改。因此,整个算法的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/RWRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
如何全面分析十月革命的历史条件及特点?
论述中问路线的破产和民主党派的重新组合。
“瓜步之战”发生在下列哪两个政权之间?()
1543年发表解剖学专著《人体结构论》的是()。
“两个凡是”
在击溃国民党的全面进攻和重点进攻中,人民解放军的主要作战目标是()。
清初,著名学者()在抗清活动失败后东渡日本,讲学授徒,培养了大批学者,传播了中国文化。
二战后世界经济走向统一的过程中,仍然存在着多样性,出现了“两种体系、三种国家”,下列不属于社会主义国家经济类型的是()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
下列选项中,对正确接收到的数据帧进行确认的MAC协议是____。
随机试题
游某从国外归来,因携带商品过多被罗湖海关认定为走私,李某欲提起行政复议,下列关于复议机关说法正确的是:()
下列因素中与急性中毒发病的时间密切相关的有
工程咨询的业务范围包括()。
柱中箍筋直径不应小于()倍纵向钢筋的最大直径。
对某些价值小、数量多、逐一清点工作量大的财产物资,可以采用测量计算盘点法进行财产清查。
美味鸭舌,一种风味小吃,真空包装,每包15克
在个人汽车贷款贷前调查中,当借款人的居住地址与户口簿记录地址一致时,必须提供居住证明。()
甲在2005年与乙结婚登记,2010年又与丙登记结婚,并生一子。2015年甲与乙离婚。现甲与丙的婚姻()(2019年一专一第35题)
有如下函数模板定义:template<classT>Tfunc(Tx,Ty){returnx*x+y*y;}在下列对func的调用中,错误的是
A、Becausehelikestoknowmoreaboutforeigncultures.B、Becauseheisgoingtoworkinothercountriessoon.C、Becausehehas
最新回复
(
0
)