首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设有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
22
问题
设有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
学硕统考专业
相关试题推荐
评介萨缪尔.亨廷顿的“文明冲突论”。(北京大学1996年世界通史真题)
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
下列叙述正确的是()。
从1939年春天起,国共双方军队在驻防结合部的摩擦冲突不断升级,不是这一时期惨案的是()
北魏建立和统一的时间分别是()。
洪秀全以宗教手段组织起义,主要利用的是()。
二战后的半个世纪中,资本主义各国经济史上的五个周期阶段。
三大战役的先后顺序是()
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
随机试题
患者女性,31岁,婚后22个月不孕,因发现下腹肿块8个月入院。入院前8个月,门诊超声发现左卵巢“囊实性肿块”约5cm×4cm×3cm大小,入院后超声检查发现左附件区有一不均质实性肿块,约6cm×5cm×4cm大小,肿块内少许血流信号,未见腹水、暗区。提
人工喂养方式错误的是
土的力学性质主要包括()。
下列各项中,应计入营业收入的是()。
Underatimecharterparty,thechartererpaysfor().
2012年5月10日,甲公司与乙企业签订了一份买卖合同,合同约定:乙企业向甲公司购买20吨药材;合同签订后5日内,乙企业向甲公司支付定金10万元;交货时间为7月底,交货地点为乙企业的库房,验货后3日内付清货款。2012年7月10日,甲公司委托丙运输公司将药
第四方物流最初由美国埃森哲咨询公司于______年提出。
下列属于测量要素的是()。
Signhasbecomeascientifichot【C1】______.【C2】______inthepast20yearshavespecialistsinlanguagestudyrealizedthatsigne
Thehumanbraincontains10thousandmillioncellsandeachofthesemayhaveathousandconnections.Suchenormousnumbersused
最新回复
(
0
)