首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有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
2014-01-14
30
问题
设有6个有序表A、B、c、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。请回答下列问题。
给出完整的合并过程,并求出最坏情况下比较的总次数。
选项
答案
6个表的合并顺序如下页图所示。根据下页图中的哈夫曼树,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个元素的最终表。由于合并两个长度分别为m和n的有序表,最坏情况下需要比较m+n—1次,故最坏情况下比较的总次数计算如下:第次合并:最多比较次数=10+35一1=44第2次合并:最多比较次数=45+40—1=84第3次合并:最多比较次数=50+60—1=109第4次合并:最多比较次数=85+110一1=194第5次合并:最多比较次数=195+200一1=394比较的总次数最多为:44+84+109+194+394=825。
解析
转载请注明原文地址:https://kaotiyun.com/show/9qxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
神圣同盟开始分裂的标志是()。
简述古埃及阿蒙霍特普四世宗教改革的内容及其影响。
第一次世界大战后。《凡尔赛条约》规定了国际联盟管理15年的德国地区是()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
论述新石器时代及其文化类型。
巴拉圭战争中的交战双方是()。
1852年,英国驻广州代办密切尔说:“经过和这么一个大国开放贸易十年之久,并且双方都已废除了一切独占制度,而拥有如此庞大人口的中国,其消费我们的制品竟不及荷兰的一半……这好像是一个奇怪的结局。”这是因为()。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
随机试题
中国居民膳食营养素参考摄入量是在()基础上发展起来的一组每日平均膳食营养素摄入量的参考值。
A.三尖瓣狭窄B.二尖瓣狭窄C.二尖瓣关闭不全D.主动脉瓣关闭不全E.肺动脉瓣关闭不全Duroziez征见于
根据民事诉讼法的规定,留置送达必须符合下列哪些条件?()
岩体在重力作用下,突然脱离母岩体向下坠落或滚动的现象称为:
A注册会计师发现2014年度甲公司向乙公司支付大额咨询费,乙公司是甲公司总经理的弟弟开设的一家管理咨询公司.并未包括在管理层提供的关联方清单内。下列各项应对措施中,A注册会计师通常首先采取的是()。
物业管理企业任免本一名中层干部,应当使用()。
搜索引擎技术的发展日新月异,除了常见的关键字搜索和分类搜索外,以下哪一项最不适合描述当下已知的一些新的搜索技术?()
武某因计划生育问题对村干部有意见,1999年元旦先后潜入村长、妇女主任、会计、治保委员、副村长家中,向上述5家的饭锅、水缸、饺子馅中投入剧毒灭鼠药,致上述5家的18口人中毒,其中5人死亡。武某的行为构成()。
下列关于标准模块的叙述中,错误的是
Woman:Idon’timagineyouhaveanyinterestinattendingthatlectureondrawing,doyou?Man:Oh,yes,Ido.Nowthatyouremi
最新回复
(
0
)