首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带头结点单链表的结点类型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
89
问题
已知一个带头结点单链表的结点类型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
学硕统考专业
相关试题推荐
分析德国法西斯上台的原因。
七君子事件
《关于建国以来党的若干历史问题的决议》
下列关于塞尔维乌斯改革的叙述错误的是()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
明成祖时期大力推崇理学,以国家力量编写了几部理学的大部头著作,下面不属于其中的是()。
隋朝建立了三省六部制,其中负责审议的部门是()。
试析第三次科学技术革命对人类社会和历史进程的影响。
编写判定给定的二叉树是否是二叉排序树的函数。
随机试题
超车遇到前方机动车不减速、不让道的情况时,要连续鸣喇叭尽快加速超越。
养阴清肺汤的功用为
测量结果显示前臂旋前0°~80°,提示
膜剂的成膜材料为
控制设备安装标高的常用测量仪器是()。
下面()组运算符的运算顺序是正确的。
根据《流动性风险管理和监管的稳健原则》,流动性风险管理和监管的基本要求是由()提出的。
由于信息不对称和预期差异,投资者会把股票回购当做公司认为其股票价格被高估的信号。()
某县人民法院审理一民事案件过程中,要求县移动通信营业部提供某通信用户的电话详单。根据我国宪法规定,下列说法何者为正确?()
Trialanderrorarethesourceofourknowledge.
最新回复
(
0
)