写一个Heaplnsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。提示：将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。

admin2018-08-12 62

问题写一个Heaplnsert(R，key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。提示：将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。

选项

答案算法如下： typedef struct{ KeyType key； InfoType otherinfo； }RecType； typedef struct{ RecType Rec[MaxNum]；／／MaxNum是一个常量 int len； }SeqList； HeapInset(SeqList R，KeyType key){ int i，j； R．Rec[++R．len]．key=key；／／增加新值到原堆中已有元素的尾部且堆的长度加1 i=R．len／2；j=R．len； while(i>0){ ／／调整为堆 if(R．Rec[i]．key2R．len，调整是自底向上查找，最多查找到树根，所以时间复杂度为O(10g2R．1en)。

解析

转载请注明原文地址:https://kaotiyun.com/show/BuRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

春秋时期的鲁国初税亩和战国时期以商鞅变法为代表的各国变法，在历史上产生了深刻的影响。这些变法的最大作用和产生的最主要的社会后果是()。

文艺复兴运动兴起的时间是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

在辛亥革命爆发前，孙中山领导中国同盟会发动的武装起义中影响最大的是()。

毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。

文艺复兴运动兴起的时间是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

采购职能的目标是_____。

CT扫描注意事项中，为保障CT机的良好工作状态，应做到

老年人口腔保健受到乡政府的高度重视，请来口腔保健专家指导卫生院的工作。经过讨论研究，全乡1千多位60岁以上老年人口腔保健的详细计划方案形成了第一步采取的切实可行的口腔保健措施是

影响项目质量的环境因素主要包括(　　)。

2005年年底,赵、钱、孙、李四人组建了甲有限责任公司,投资比例各占1/4。2006年,赵、钱、孙、李四人各月的工资均为800元,年底每人应分股利36000元。因此,为赵、钱、孙、李四人进行税务筹划时,应该建议他们()。

下列属于可变更、可撤销合同的有()。

现在有的教师暗示家长或学生，或明着向家长索要财物，根据家长送礼的薄厚区别对待学生。这样的老师违背了()的职业道德规范。

窗体中有文本框Textl。运行程序，输入大于0的整数m，单击按钮Commandl，程序显示由星号组成的高度和上底均为m的等腰梯形形。例如，当m=5时，显示图形如下。*****

Itisthenaturalandperhapsunderstandabletendencyofnewspaperstoconcentrateonbadnewsandbydoingsotocontributeto

计算机408

学硕统考专业

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

春秋时期的鲁国初税亩和战国时期以商鞅变法为代表的各国变法，在历史上产生了深刻的影响。这些变法的最大作用和产生的最主要的社会后果是()。

文艺复兴运动兴起的时间是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

在辛亥革命爆发前，孙中山领导中国同盟会发动的武装起义中影响最大的是()。

毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。

文艺复兴运动兴起的时间是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

既考虑作业等待时间又考虑作业执行时间的调度算法是()。

采购职能的目标是_____。

CT扫描注意事项中，为保障CT机的良好工作状态，应做到

老年人口腔保健受到乡政府的高度重视，请来口腔保健专家指导卫生院的工作。经过讨论研究，全乡1千多位60岁以上老年人口腔保健的详细计划方案形成了第一步采取的切实可行的口腔保健措施是

影响项目质量的环境因素主要包括( )。

2005年年底,赵、钱、孙、李四人组建了甲有限责任公司,投资比例各占1/4。2006年,赵、钱、孙、李四人各月的工资均为800元,年底每人应分股利36000元。因此,为赵、钱、孙、李四人进行税务筹划时,应该建议他们()。

下列属于可变更、可撤销合同的有()。

现在有的教师暗示家长或学生，或明着向家长索要财物，根据家长送礼的薄厚区别对待学生。这样的老师违背了()的职业道德规范。

窗体中有文本框Textl。运行程序，输入大于0的整数m，单击按钮Commandl，程序显示由星号组成的高度和上底均为m的等腰梯形形。例如，当m=5时，显示图形如下。*****

Itisthenaturalandperhapsunderstandabletendencyofnewspaperstoconcentrateonbadnewsandbydoingsotocontributeto

影响项目质量的环境因素主要包括(　　)。