首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有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
15
问题
设有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
学硕统考专业
相关试题推荐
在1875年宪法中关于法国立法权的叙述,不正确的是()。
中国古代的移民主要有两个大的流向:或者由北方草原内迁人中原,或者由中原迁入江南,这两大迁移最主要的影响是()。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
晚清时期清帝年号的正确排序是()
人民解放军转入战略进攻的方向为大别山地区,主要是由于()。①大别山战略位置重要②大别山有良好的群众基础③占据大别山可以从根本上改变战局
《凡尔赛条约》中,战胜国以()方式处置德国的全部海外殖民地。
1918年美国总统威尔逊提出“十四点原则”,内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。
将两个长度为N的有序表归并到一个长度为2N的有序表,最少需要比较的次数是(),最多需要比较的次数是()。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:转移指令的目标地址范围是多少?
随机试题
卵巢肿瘤最常起源于
2020年3月5日,周某就其发明M向国家知识产权局提出发明专利申请,其后,又于2021年2月3日就同样的发明M在美国提出发明专利申请,同时提出优先权请求。根据国际优先权原则,发明M的优先权日是()。
行政法律关系主体包括________和________。
党的十三大第一次比较系统地提出和论述了()
基底核通常包括
适用于头顶部的包扎法是
在下列哪些情况下可以考虑采用新设法人融资方式( )。
基金上市交易公告书披露的事项包括()。I.募集情况与上市交易安排Ⅱ.基金托管人报告Ⅲ.基金合同摘要Ⅳ.基金持有人结构
这笔借款使该欧洲公司承担的汇率风险类型是()。如果采取远期外汇交易防范汇率风险,那么该公司应卖出()万元6个月欧元期汇。
《经济日报》评论员文章是这样表述经济“新常态”的:新常态之新,意味着不同以往;新常态之常,意味着相对稳定。由此可见,经济“新常态”的提出()①折射出事物是绝对运动与相对静止的统一②揭示了矛盾的普遍性和特殊性的相互联结③体现了事物的性质决定于矛
最新回复
(
0
)