设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：根据你的合并过程，描述N(N≥

admin2015-12-30 71

问题设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。
请回答下列问题：
根据你的合并过程，描述N(N≥2)个不等长升序表的合并策略，并说明理由。

选项

答案各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

解析考查二路归并和哈夫曼树以及最佳归并树。
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。

转载请注明原文地址:https://kaotiyun.com/show/LzRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

《凡尔赛和约》中，战胜国以何种方式处置德国的全部海外殖民地?()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

近现代以来，国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。

下列科技文化成就，产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为带书。④马钧发明翻车

1918年美国总统威尔逊提出“十四点原则”，内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。

一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。

若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为()。

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是()。

当前客观事物的个别属性在人脑中的直接反映，是指()

签订的下列建设工程施工合同中，属于无效合同的有()。

阴险狡诈的人不被人信赖，所以善良的人不阴险狡诈。能得出上述结论的必要前提是()。

《卓越绩效评价准则》国家标准主体内容，共包括7个类目和()个评分项。

江南运河沿线的城市有()。

在教学中讲授“果实”概念时，既要选能够食用的果实，又要选不能食用的果实，这样才有利于学生准确地掌握“果实”概念。这是运用了()。

内耗效应，是指在社会或部门内部因不协调或矛盾等造成的人力、物力等方面无谓的消耗而产生的负效应现象，其本质是它对外没有作功而只是内部消耗能量。根据上述定义，下列属于内耗效应的是()。

有如下两个关系，其中雇员信息表关系EMP的主键是雇员号，部门信息表关系DEPT的主键是部门号。若执行下面列出的操作，(19)操作不能成功执行。

Risingtemperaturesandoverfishinginthepristine(未受污染的)watersaroundtheAntarcticcouldseekingpenguinpopulationspushe