设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。请回答下列问题:
问答题 给出完整的合并过程,并求出最坏情况下比较的总次数。
【正确答案】正确答案:对于长度分别为m,n的两个有序表的合并,最坏情况下是一直比较到两个表尾元素,比较次数为m+n-1次。故,最坏情况的比较次数依赖于表长,为了缩短总的比较次数,根据哈夫曼树(最佳归并树)思想的启发,可采用如图所示的合并顺序。
【答案解析】
问答题 根据你的合并过程,描述N(N≥2)个不等长升序表的合并策略,并说明理由。
【正确答案】正确答案:各表的合并策略是:在对多个有序表进行两两合并时,若表长不同,则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想,依次选择最短的两个表进行合并,可以获得最坏情况下最佳的合并效率。
【答案解析】解析:考查二路归并和哈夫曼树以及最佳归并树。 本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的Merge()函数;对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。