首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
admin
2019-08-15
61
问题
写一个HeapInsen(R,key)算法,将关键字插入到堆尺中,并保证插入后R仍是堆。请分析算法的时间复杂度。提示:将key先插入R中已有元素的尾部(即原堆的长度加l的位置,插入后堆的长度加1),然后自下往上调整,使插入的关键字满足堆性质。
选项
答案
算法如下: typedef struct{ KeyType key; InfoType otherinfo; }RecType; typedef struct{ RecType Rec[MaxNum]; //MaxNum是一个常量 int len; }SeqList; HeapInsert(SeqList R,KeyType key){ int i,j; R.Rec[++R.1en].key=key; //增加新值到原堆中已有元素的尾部且堆的长度加1 i=R.len/2; j=R.1en; while(i>0){ //调整为堆 if(R.Rec[i].key<R.Rec[j].key){ R.Rec[0]=R.Rec[i];R.Ree[i]=R.Rec[j];R.Rec[i]=R.Rec[0]; } j=i;i=i/2; //继续自底向上查找 } } 设该堆对应的树高为h,则满足h≤log
2
R.1en,调整是自底向上查找,最多查找到树根,所以时间复杂度为O(log
2
R.1en)。
解析
转载请注明原文地址:https://kaotiyun.com/show/nKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列哪部戏剧不是曹禺的作品()。
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
为了顺利开展武装起义的准备工作,在彼得格勒苏维埃中成立了()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
设一段正文由字符集{A,B,C,D,E,F)中的字母组成,这6个字母在正文中出现的次数分别为{12,18,26,6,4,34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成,试计算按哈夫曼编码压缩存储这段正文共需多少个字
已知4位有效信息为1010,试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码,要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码,生成多项式G(x)=1011。
操作系统为了管理文件,设计了文件控制块(FCB),文件控制块的建立是()。
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。,文件A在该文件目录中的位置如下图所示。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:转移指令的目标地址范围是多少?
随机试题
在考生文件夹中有一个“Acc1.mdb”数据库。(1)按照下表的要求创建“课程”表。(2)在“课程”表中输入如下数据。(3)将“student”表和“成绩”表的关系设置为“一对多”,“实施参照完整性”。将“课程”表和“成绩”表的关系设置为“一对多
Thereseemstobeanelectricalproblem.I’llgetsomeoneto________it.
两套合成氨生产装置生产能力均为600kt/a,说明两套装置具有相同的生产强度。()
男,36岁,平素体健。淋雨后发热,咳嗽2天,右上腹痛伴气急、恶心1天。体检应注意有无
不属于通常所说"五淋"的是:
患者,女,35岁。因全身关节痛,面有蝶形红斑,查血有抗Sm抗体(+)。医生嘱咐其避免日光直射,病室紫外线消毒时应回避,外出穿长袖上衣及长裤,戴帽或撑伞遮阳。原因是
当建筑场地的施工控制网为方格网或轴线形式时,采用()放线最为方便。
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
年轻干部进入此门,就要脚踏实地,既不浮躁,也不消极,心静下来,神专下来,做好吃苦的准备,挽起袖子好好地干一场。外部给了很好的平台,内心要有强烈的锤炼意识。深知“烈火炼真金”,真的本领,是在艰苦中锤炼而成。“冬练三九,夏练三伏”,才能练成一身好武艺;孤愤之书
()创伤后应激障碍与遗传因素无关。
最新回复
(
0
)