首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带头结点单链表的结点类型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
84
问题
已知一个带头结点单链表的结点类型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
学硕统考专业
相关试题推荐
试以英国为例分析工业革命的深远影响。
下列选项中,对东汉度田问题的描述中,不正确的是()
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
詹天佑自主设计修建了中国第一条铁路是在()。
五四运动后,马克思主义在中国广泛传播。1920年在上海出版了最早的《共产党宣言》中文全译本,译者是()
隋朝建立了三省六部制,其中负责审议的部门是()。
设某计算机有四个中断源,优先顺序按1→2→3→4降序排列,若1、2、3、4中断源的服务程序中对应的屏蔽字分别为1110、0100、0110、1111,试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求,画出CPU执行程序的轨迹。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:该指令系统最多可有多少条指令?该计算机最多有
随机试题
关于梯度切换率高的完整描述,正确的是
房屋租金可分为()。
对该宗土地进行城市用地适用性评价,该宗土地属于()类建设用地。在下列合同中,属于从合同的有()。
《标准施工合同》中的通用条款规定,发包人暂停施工的责任,()。
下列关于费用的表述正确的有()。
经海关批准,实行集中申报的进出口货物,应当适用的税率是()。
发文登记一般采用的形式是()。
某些律师承认交警便衣执勤是“隐蔽执法”行为,但却是“不得已而为之”。言下之意即明知违法,但因为可以取得更好的执法效果就可以故意违法。这就好比战争中为了保护多数人的安全,就可以打着“人权”的幌子剥夺少数人的生命,而本身却是最大的不尊重“人权”。同理,知法犯法
IQ
A、 B、 C、 D、 A
最新回复
(
0
)