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

admin2015-12-30 64

问题设有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

学硕统考专业

《吕氏春秋》载：“公作则迟，有所匿其力也；分地则速，无所匿其力也。”这条材料反映的实质问题是()。

对苏联高度集中的体制的客观评价是()。①基本上适应苏联当时的生产力发展水平②这种体制有严重缺点和弊端③后来这种体制阻碍了苏联国民经济的发展④这种体制在历史上起过积极的作用

维也纳会议争论的焦点问题是()。

下列关于基督教的叙述，不正确的是()。

发现电磁感应现象的科学家是()。

晚清时期清帝年号的正确排序是()

洋务派创办军事工业的方式是()。

阅读下面史料，回答问题：材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下：合众国525000吨；英帝国525000吨；法国175000吨；意大利175000吨；日本315000吨。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2．…，em)；i＝l；while(所剩边数>＝顶点数){从图中删去ei；若图不再连通，则恢复ei；i＝i＋l；

关于问题和答案设计下列说法不正确的是()。

肝硬化腹水患者，每日进水量应限制在

A．泻痢B．咳喘痰多C．食积气滞、腹胀便秘D．水肿E．疟疾

机电工程项目部执行所属企业有关计量器具的管理制度中的内容有()。

纳税人账簿、凭证、财务会计制度比较健全，能够如实反映生产经营成果，正确计算应纳税款的，税务机关应当对其采用的税款征收方式是()。

甲公司20×3年财务报表于20×4年4月10日对外报出。假定其20×4年发生的下列有关事项均具有重要性，甲公司应当据以调整20×3年财务报表的是()。(2014年)

关于抑郁性神经症的主要临床特点表现，正确的是()。

吴老师以“学生不愿动手表现的问题”为研究对象，从教学环境、教学策略等方面进行了反复试验、反思、改进，这种研究方法是()。

修改宪法时必须由全国人大常委会或三分之一以上的全国人大代表提议，并由全国人大以全体代表的三分之二以上的多数通过。()

PassiveSmokingisWorkplaceKillerPressuremountedonBritainonMondaytotakeactionon(1)smokingwithnewresearchshowing