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

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

admin2015-12-30  85
问题 设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。
请回答下列问题：
根据你的合并过程，描述N(N≥2)个不等长升序表的合并策略，并说明理由。
选项
答案各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。
解析 考查二路归并和哈夫曼树以及最佳归并树。
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。
转载请注明原文地址:https://www.kaotiyun.com/show/LzRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)