首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。 请回答下列问题: 给出完整的合并过程,并求出最坏
设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。 请回答下列问题: 给出完整的合并过程,并求出最坏
admin
2015-12-30
40
问题
设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。
请回答下列问题:
给出完整的合并过程,并求出最坏情况下比较的总次数。
选项
答案
对于长度分别为m,n的两个有序表的合并,最坏情况下是一直比较到两个表尾元素,比较次数为m+n-1次。故,最坏情况的比较次数依赖于表长,为了缩短总的比较次数,根据哈夫曼树(最佳归并树)思想的启发,可采用如图所示的合并顺序。 [*] 根据上图中的哈夫曼树,6个序列的合并过程为: 第1次合并:表A与表B合并,生成含有45个元素的表AB; 第2次合并:表AB与表C合并,生成含有85个元素的表ABC; 第3次合并:表D与表E合并,生成含有110个元素的表DE; 第4次合并:表ABC与表DE合并,生成含有195个元素的表ABCDE; 第5次合并:表ABCDE与表F合并,生成含有395个元素的最终表。 由上述分析可知,最坏情况下的比较次数为:第1次合并,最多比较次数=10+35-1=44;第2次合并,最多比较次数=45+40-1=84;第3次合并,最多比较次数=50+60-1=109;第4次合并,最多比较次数i=85+110-1=194;第5次合并,最多比较次数=195+200-1=394。 故,比较的总次数最多为:44+84+109+194+394=825。
解析
转载请注明原文地址:https://kaotiyun.com/show/GzRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列历史事件发生的先后顺序是()①“铁幕”演说②马歇尔计划③北大西洋公约
对苏联高度集中的体制的客观评价是()。①基本上适应苏联当时的生产力发展水平②这种体制有严重缺点和弊端③后来这种体制阻碍了苏联国民经济的发展④这种体制在历史上起过积极的作用
下列对凡尔赛和约中有关德国疆界问题的表述,正确是()。
三国时期,魏、蜀、吴灭亡的先后顺序是()。
阅读材料,回答以下问题:今日中国独立自由的地位,已随不平等条约的撤废而获得。然而我们中国国民正确的反应,是义务感的激发与责任心的加强。国家的责任与国民的任务,从此更加重大。建国工作的完成,建国理想的实现,皆有待于我们的奋斗和牺牲。“天下无易事,天下无难事
阅读材料,回答以下问题:今日中国独立自由的地位,已随不平等条约的撤废而获得。然而我们中国国民正确的反应,是义务感的激发与责任心的加强。国家的责任与国民的任务,从此更加重大。建国工作的完成,建国理想的实现,皆有待于我们的奋斗和牺牲。“天下无易事,天下无难事
古埃及第24朝法老波克利斯进行改革,宣布废除奴隶制,债权人只能索取债务人的财产作抵偿,而不能占有债务人的人身,因为财产属于个人,而公民人身属于国家,国家需要他们服役。该改革旨在
(1)所有事件的最早发生时间如下:Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3,ve(3)+6}=12Ve(5)=max{ve(3)+3,ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve
设磁盘的扇区大小为4KB,磁盘转速为15000r/min,磁盘平均寻道时间为4ms,最大数据传输速率为40MB/s,磁盘控制器开销时问为1ms,计算读写一个扇区所需平均时间(不考虑I/O请求队列中的等待时间)。
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
随机试题
内蒙古自治区总面积118.3万平方千米,是中国()。
原告在行政诉讼中的义务有()。
根据以下资料,回答问题。(注:在职退休比指的是在职职工参保人数与退休职工参保人数之比)假设2021年居民医保基金收入同比增速与2020年相同,那么,2021年居民医保基金收入约为:
婴幼儿腹泻的常见诱发因素是
关于罪过,下列哪些选项是错误的?()
硝酸铵炸药的储存期为()个月。
下列有关确定控制测试范围的考虑因素的说法中,错误的有()。
与2012年3月相比,5月使用新闻网站和微博的人数差()万人。
同时在诗歌、音乐、绘画领域达到很高造诣的唐代作家是()。
Whenwillthemancome?
最新回复
(
0
)