在执行锦标赛排序算法时,给定初始序列,且假设每一轮比赛中数值较小的元素胜出。若第四趟比赛后,记录r[4]的值为63,且此时胜者树的根节点值为25。则关于该排序过程,下列描述正确的是:
答案解析
A选项错误:第四趟比赛后根节点为25,表示25是目前胜者树的最小元素,并不代表r[4]之前存在小于25的值。初始序列中可能存在大于25的值,在之前的轮次中被淘汰。B选项错误:即使目前根节点是25,也不能确定r[4]之后的所有值都大于等于25。那些大于25的元素可能在之前的轮次中被淘汰,不再参与后面的比较。C选项错误:胜者树每一趟的根节点值可能发生变化,取决于本轮比赛的胜者,因此无法确定第三趟结束时根节点值必定为25。在第三趟比赛中,可能出现其他值成为胜者树的根节点,并在后续的比赛中被25取代。D选项正确:根据锦标赛排序的规则,r[4]在第四趟比赛中必然与其他元素进行比较,因为第四趟根节点的值为25,所以r[4]最终肯定输给了某个大于等于25的数值。
正确答案:D