首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带头结点单链表的结点类型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
38
问题
已知一个带头结点单链表的结点类型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://jikaoti.com/ti/fIfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
如何全面分析十月革命的历史条件及特点?
“灌木林原野事件”
永嘉之乱后,北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大
古埃及中王国时期出现了一个新兴的手工业部门,对世界文明做出了巨大贡献。这一新兴的手工业部门是()。
下列选项中,对东汉度田问题的描述中,不正确的是()
为加强君权,皇太极时代开始直接控制的“上三旗”不包括()。
新文化运动中,把斗争矛头指向孔孟儒学的直接原因是()。
在1875年宪法中关于法国立法权的叙述,不正确的是()。
苏联的第一个五年计划是从什么时候开始实行的?()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
随机试题
反补贴措施包括___________、___________和___________。
第一审行政判决书的理由部分应当写明哪些内容?
临床上诊断劳力型心绞痛最重要的依据是
lac操纵子结构基因的表达条件是
推拿法治疗头痛常选用的穴位不包括
水运工程施工监理合同管理的内容包括()。
以人为本是中国共产党根本宗旨和执政理念的集中体现。()
一年级有2个班,男女生人数比是4:3,一班男女生人数比为3:4,二班男女生人数比为5:2。问一班、二班男生人数比是多少?()
AnnualGrammyAwards
中华人民共和国的成立和“社会主义改造”的完成,意味着中国人民选择并成功走上了社会主义道路。从社会发展的历史选择性的角度看,中国人民走上社会主义道路,其原因在于
最新回复
(
0
)