在外排序中,利用败者树对初始为升序的归并段进行多路归并,败者树中记录"冠军"的结点保存的是( )
A、最大关键字
B、最小关键字
C、最大关键字所在的归并段号
D、最小关键字所在的归并段号
在外部排序的多路归并过程中,败者树...
用户登录可进行刷题及查看答案
在外部排序的多路归并过程中,败者树是一种用于高效选取最小关键字的数据结构。下面详细分析败者树中 “冠军” 结点的存储内容:
一、败者树的基本原理
败者树本质上是一棵完全二叉树,其每个非叶结点记录的是 “败者” 信息(即两两比较中较小的一方在比较中失利,暂存于父结点),而真正的 “胜者”(当前最小关键字)则逐级向上比较,最终在根结点的父结点(或特定标记位置)记录。
以 k 路归并为例,败者树的叶结点对应 k 个归并段的当前待比较元素,非叶结点存储比较后的败者信息,而冠军(最小关键字)的位置需要通过树的结构确定。
二、“冠军” 结点的存储内容分析
比较过程:每次从 k 个归并段的当前元素中选取最小关键字时,通过败者树的两两比较,非叶结点保存的是每一轮比较中的败者(即较大的元素所在的归并段号或关键字),而胜者(较小元素)继续向上比较。
最终结果:经过所有比较后,最小关键字(冠军)对应的叶结点位置会被记录在败者树的某个特定结点中。由于败者树的设计目标是快速找到最小关键字,因此 “冠军” 结点需要保存该最小关键字所在的归并段号,以便后续从该归并段读取下一个元素。
三、选项辨析
A、最大关键字:错误。败者树用于找最小关键字,与最大关键字无关。
B、最小关键字:错误。败者树的叶结点存储当前元素的关键字,而非叶结点不直接存储最小关键字,而是通过比较过程确定其位置。
C、最大关键字所在的归并段号:错误。非叶结点记录的是败者(较大元素)的归并段号,但冠军结点需记录最小关键字的位置。
D、最小关键字所在的归并段号:正确。败者树的 “冠军” 结点用于标记当前最小关键字对应的归并段,以便后续操作。
四、结论
败者树通过比较过程确定最小关键字的位置,其 “冠军” 结点保存的是最小关键字所在的归并段号。
答案:D
登录后提交答案
暂无评论,来抢沙发