CSP-S 2022 第一轮 第5题：假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排

题目

假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排 序算法结束后，可能出现的最坏情况是（  ）。

选项

• A. 移除受影响的数据后，最终序列是有序序列
• B. 移除受影响的数据后，最终序列是前后两个有序的子序列
• C. 移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列
• D. 移除受影响的数据后，最终序列基本无序

答案

A

题解

选 A：移除受影响的数据后，最终序列是有序序列。

基数排序通常从低位到高位逐位排序，且每一轮都是稳定排序：当前位相同的元素，保持原来的相对顺序。

某个数据发生异变，可能导致它自己的位置不正确，但不会破坏其他正常数据最终的相对顺序。对于任意两个正常数据：

• 它们的大小由“最高的不同位”决定；
• 排到这一位时，它们会被安排到正确的先后顺序；
• 后面的更高位都相同，稳定排序会保留这个顺序。

因此，所有正常数据之间仍然有序，删掉异变的数据即可。