已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data；int freq；struct nextNode*next；}；其中，data为结点值域，freq为该结点元素的访问计数，初始为0；next

admin2017-11-20 54

问题已知一个带头结点单链表的结点类型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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data；int freq；struct nextNode*next；}；其中，data为结点值域，freq为该结点元素的访问计数，初始为0；next

计算机408

学硕统考专业

战国初期，上党地区在下列哪一个国家的控制范围之内?()

以下内容不属于中国共产党为解决中西部落后问题，巩固发展国防事业而采取的三线建设的是()。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

西汉末年，()对太初历作了系统的解释，并调整为三统历。这是中国第一部记载完整的历法。

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

隋在统一全国的过程中，平定江南是一个重要的部分，帮助完成岭南一带平定的是()

试析第三次科学技术革命对人类社会和历史进程的影响。

1922年2月，美、英、法、意、日五国通过了《五国海军条约》，规定了各国海军主力舰和航空母舰的限额，以及在东亚设置海军基地的要求等内容。该条约的缔结表明()

用KMnO4标准溶液测定H2O2时，滴定至粉红色为终点。滴定完成后5分钟发现溶液粉红色消失，其原因是()。

宗某，女，3岁。8月25H住院。8月5日起病，发热3日后高热、神昏1周，抽风多次。经外院治疗，8月16日以来身热渐减至正常，但仍意识不清，呜呀胡言，吞咽困难，喉间有痰。当诊断

患者，男，47岁。3个月来阴囊湿疹，瘙痒难忍，搔破则流黄水，以致夜不成眠，小便短赤。其证候是

信用卡诈骗罪属于以下哪种罪名?()

按照《建筑安装工程费用项目组成》的规定，下列项目属于建筑安装工程费用项目的有()。

关于投资性房地产的后续计量，下列说法中正确的有()。

下列关于会计职业道德和会计法律制度关系的说法中，错误的有()。

某大学某班学生总数为32人，在第一次考试中有26人及格，在第二次考试中有24人及格，若两次考试中，都及格的有22人，那么两次考试都没有及格的人数是()

闭关政策

唯物主义发展的历史形态有()

已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data；int freq；struct nextNode*next；}； 其中，data为结点值域，freq为该结点元素的访问计数，初始为0；next

计算机408

学硕统考专业

战国初期，上党地区在下列哪一个国家的控制范围之内?()

以下内容不属于中国共产党为解决中西部落后问题，巩固发展国防事业而采取的三线建设的是()。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

西汉末年，()对太初历作了系统的解释，并调整为三统历。这是中国第一部记载完整的历法。

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

隋在统一全国的过程中，平定江南是一个重要的部分，帮助完成岭南一带平定的是()

试析第三次科学技术革命对人类社会和历史进程的影响。

1922年2月，美、英、法、意、日五国通过了《五国海军条约》，规定了各国海军主力舰和航空母舰的限额，以及在东亚设置海军基地的要求等内容。该条约的缔结表明()

用KMnO4标准溶液测定H2O2时，滴定至粉红色为终点。滴定完成后5分钟发现溶液粉红色消失，其原因是()。

宗某，女，3岁。8月25H住院。8月5日起病，发热3日后高热、神昏1周，抽风多次。经外院治疗，8月16日以来身热渐减至正常，但仍意识不清，呜呀胡言，吞咽困难，喉间有痰。当诊断

患者，男，47岁。3个月来阴囊湿疹，瘙痒难忍，搔破则流黄水，以致夜不成眠，小便短赤。其证候是

信用卡诈骗罪属于以下哪种罪名?()

按照《建筑安装工程费用项目组成》的规定，下列项目属于建筑安装工程费用项目的有()。

关于投资性房地产的后续计量，下列说法中正确的有()。

下列关于会计职业道德和会计法律制度关系的说法中，错误的有()。

某大学某班学生总数为32人，在第一次考试中有26人及格，在第二次考试中有24人及格，若两次考试中，都及格的有22人，那么两次考试都没有及格的人数是()

闭关政策

唯物主义发展的历史形态有()

已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data；int freq；struct nextNode*next；}；其中，data为结点值域，freq为该结点元素的访问计数，初始为0；next