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

admin2017-11-20 60

问题已知一个带头结点单链表的结点类型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

学硕统考专业

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

中华人民共和国恢复了在联合国合法席位的时间是()。

“瓜步之战”发生在下列哪两个政权之间?()

下列有关《布列斯特和约》的说法中，错误的一项是()。

布雷顿森林体系

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

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

下列诗作中，抒写新时期青年爱国深情的是()

以下关于缺陷责任期的说法，正确的是()。

《最高人民法院关于审理建设工程施工合同纠纷案件适用法律问题的解释》规定，发包人()，致使承包人无法施工，且在催告的合理期限内仍未履行相应义务，承包人请求解除建设工程施工合同的，应予支持。

(2008年考试真题)下列关于分公司法律地位的中，正确的有()。

下列有关财务管理目标的表述中，正确的是()。

班级越大，内部越容易形成各种非正式小群体。()

对关系S和R进行集合运算，结果中既包含S中的所有元组也包含尺中的所有元组，这样的集合运算称为()。

HowPovertyChangestheBrainA)Yousawthepicturesinscienceclass—aprofileviewofthehumanbrain,sectionedbyfuncti

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

计算机408

学硕统考专业

1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。

中华人民共和国恢复了在联合国合法席位的时间是()。

“瓜步之战”发生在下列哪两个政权之间?()

下列有关《布列斯特和约》的说法中，错误的一项是()。

布雷顿森林体系

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

巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

下列诗作中，抒写新时期青年爱国深情的是()

以下关于缺陷责任期的说法，正确的是()。

《最高人民法院关于审理建设工程施工合同纠纷案件适用法律问题的解释》规定，发包人()，致使承包人无法施工，且在催告的合理期限内仍未履行相应义务，承包人请求解除建设工程施工合同的，应予支持。

(2008年考试真题)下列关于分公司法律地位的中，正确的有()。

下列有关财务管理目标的表述中，正确的是()。

班级越大，内部越容易形成各种非正式小群体。()

对关系S和R进行集合运算，结果中既包含S中的所有元组也包含尺中的所有元组，这样的集合运算称为()。

HowPovertyChangestheBrainA)Yousawthepicturesinscienceclass—aprofileviewofthehumanbrain,sectionedbyfuncti

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