首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带头结点单链表的结点类型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
71
问题
已知一个带头结点单链表的结点类型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
学硕统考专业
相关试题推荐
简述斯巴达克起义的原因、大体经过、意义和失败原因。
论述中问路线的破产和民主党派的重新组合。
南宋永嘉学派的代表人物是()。
袁世凯得以复辟帝制不是因为()
胡适与李大钊进行“问题与主义之争”的主战场是()。
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
1905年至1907年间,围绕中国究竟是采用革命手段还是改良方式这个问题,革命派与改良派进行论战的舆论阵地是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
袁世凯在控制自己权力,实现对全国控制的过程中,主要颁布的法律不包括()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
随机试题
结合所示扭声图像,肾积水最常见的原因是
肺痈成痈化脓的病理基础,主要在于
下列属于有机材料的是()。
建筑高度为32m的飞机库,可采用()探测器。
“经营单位”栏:“成交方式”栏:
购入无形资产超过正常信用条件延期支付价款,实质上具有融资性质的,该项无形资产的计量应以购买价款的现值为基础。()
下列不属于植物体内蛋白质功能的是()。
虚假诉讼是指当事人出于非法的动机和目的,利用法律赋予的诉讼权利,采取虚假的诉讼主体、事实及证据的方法提起民事诉讼,使法院作出错误的判决、裁定、调解,从而侵害国家、集体、他人合法权益或逃避履行法律文书确定的义务的行为。根据上述定义,下列属于虚假诉讼的是:
跳马:体操:运动
在数据库设计中,描述数据间内在语义联系得到E-R图的过程属于
最新回复
(
0
)