首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data;int freq;struct nextNode*next;}; 其中,data为结点值域,freq为该结点元素的访问计数,初始为0;next
已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data;int freq;struct nextNode*next;}; 其中,data为结点值域,freq为该结点元素的访问计数,初始为0;next
admin
2017-11-20
58
问题
已知一个带头结点单链表的结点类型nextNode定义为
struct nextNode{int data;int freq;struct nextNode*next;};
其中,data为结点值域,freq为该结点元素的访问计数,初始为0;next为指向链表中该结点后继结点的指针域,设该链表所有结点按照freq值从大到小链接。请实现一个时间和空间上尽可能高效率的算法,编写一个查找函数Search,从链表首结点开始查找结点data值与给定值相等的结点。如果找到,则将该结点的freq值加1,然后把它前移到与结点freq值相等的结点的后面,使得所有结点仍然都保持按照freq值从大到小链接。
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析:除去链表本身的空间外,额外的空间消耗为O(1)。 时间复杂度分析:整个算法只会对链表进行一次扫描,扫描的时候把需要的信息都记录下来,然后用O(1)的时间完成链表的修改。因此,整个算法的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/PNRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在下列我国建国之后的外交活动中,能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊
下列选项中,对东汉度田问题的描述中,不正确的是()
下面哪项条约没有涉及德国的赔款问题?()
埃及曾两次被波斯帝国征服,波斯第二次征服埃及的时间是()。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
在1875年宪法中关于法国立法权的叙述,不正确的是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
北约和华约两个组织对峙近半个世纪,其影响是()。
随机试题
Asprotectorofherfamily’shealth,thepoineerwomanconfrontedsituationssheneverimaginedbeforecrossingtheMississippi.
上消化道出血最常见的病因是
在骨髓涂片细胞学检查的内容中,错误的是
下列不通过“应交税费”科目核算的税类是()。
“生产成本”账户的期末余额,在编制资产负债表时,应填列在“存货”项目下。()
【2014华夏银行】M、N两数均恰含有质因数3和5,他们的最大公约数是75。已知M有12个约数,N有10个约数,那么M、N两数的和等于()。
已知双曲线的中心在原点,坐标轴为对称轴,一条渐近线方程y=,右焦点F(5,0),双曲线的实轴为A1A2,P为双曲线上一点(不同于A1,A2),直线A1P、A2P分别与直线l:x=交于M、N两点.求双曲线的方程;
(2005年单选4)我国1997年刑法关于溯及力的规定采取的是()。
关于语句 #include<iostream> usingnamespacestd; voidmain() {cout<<100.8989663<<’; cout<<fixed<<100.8989663<
A、StorethebicycleinsidethedormitoryB、AsksomeonetorepairthebicycleC、RidethebicycleoncampusD、Trytofindthebicy
最新回复
(
0
)