首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个Heaplnsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个Heaplnsert(R,key)算法,将关键字插入到堆R中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2018-08-12
90
问题
写一个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].key
2R.len,调整是自底向上查找,最多查找到树根,所以时间复杂度为O(10g2R.1en)。
解析
转载请注明原文地址:https://kaotiyun.com/show/BuRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
下列法律文件中,规定内阁对君主负责的是()。
美国历史上第一个具有宪法性质的文件是()。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
高度为7的AVL树最少有()个结点。
快速排序最易发挥其长处的情况是()。
采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中,正确的是____。
随机试题
低氢钾型药皮有哪些特点?
男性,58岁。3小时前在投掷铅球转身后突感左侧胸痛,随即出现胸闷气短,呼吸急促,行走后症状加重,伴出汗、心悸,自行半坐位休息后症状稍有缓解而来院。既往有高血压、冠心病及肺结核病史。根据临床症状分析,考虑下列哪种疾病可能性最大
地毯的品种、规格、颜色、花色、胶料和辅料及其材质均要求符合设计要求和国家现行地毯产品标准的规定。()
现金科目的账表查询不可以在()表中查询。
某家电公司准备开发新产品。在工作午餐时,研发部经理张先生向财务部经理王女士诉苦,抱怨市场部总是提出一些超出技术可行性的产品设计要求。过了几天,下班后在电梯里,王女士遇到了市场部经理李先生,李先生向她抱怨研发部忽视客户需求,新产品没有市场价值。后来在一次递交
下列各项中,违反经济法的行为应承担的法律责任有()。
某有出口经营权实行“免抵退”税政策的工业企业(增值税一般纳税人)自产一批货物出口,企业该批货物制造成本100万元(不合出口需转出的增值税进项税),出口收入(FOB)折合人民币150万元,货物征税率17%,退税率13%,则其外销成本是多少?
在不考虑其他影响因素的情况下,企业发生的下列交易或事项中,期末会引起“递延所得税资产”科目余额增加的有()。
编译型程序设计语言若规定程序中的变量必须先定义(或声明)再引用,那么违反此规定的程序在(19)时报错。
Ifparentsbringupachildwiththeaimofturningthechildintoa【B1】______,theywillcauseadisaster.Accordingtosevera
最新回复
(
0
)