题目
在外部排序中,使用败者树对初始为升序的归并段进行多路归并,败者树中记录'冠军'的结点[1]保存的是()。A. 最大关键字B. 最大关键字所在的归并段号C. 最小关键字D. 最小关键字所在的归并段号
在外部排序中,使用败者树对初始为升序的归并段进行多路归并,败者树中记录'冠军'的结点[1]保存的是()。
A. 最大关键字
B. 最大关键字所在的归并段号
C. 最小关键字
D. 最小关键字所在的归并段号
题目解答
答案
C. 最小关键字
解析
步骤 1:理解败者树的概念
败者树是一种用于多路归并排序的树形结构,其中每个节点保存一个关键字和一个指针,指针指向关键字所在的归并段。败者树的根节点保存的是当前所有关键字中的最小值,即“冠军”。
步骤 2:分析败者树中记录'冠军'的结点
在败者树中,记录'冠军'的结点保存的是当前所有关键字中的最小值。由于归并段是升序的,所以这个最小值就是当前所有归并段中最小的关键字。
步骤 3:确定答案
根据败者树的定义和归并段的升序特性,记录'冠军'的结点保存的是最小关键字。
败者树是一种用于多路归并排序的树形结构,其中每个节点保存一个关键字和一个指针,指针指向关键字所在的归并段。败者树的根节点保存的是当前所有关键字中的最小值,即“冠军”。
步骤 2:分析败者树中记录'冠军'的结点
在败者树中,记录'冠军'的结点保存的是当前所有关键字中的最小值。由于归并段是升序的,所以这个最小值就是当前所有归并段中最小的关键字。
步骤 3:确定答案
根据败者树的定义和归并段的升序特性,记录'冠军'的结点保存的是最小关键字。