第7章_排序_考点9_基数排序_2016年考研核心考点命题思路解密_数据结构.pdfVIP

2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 考点9 基数排序 一．选择题部分 1. 设一组初始记录关键字序列为(345，253 ，674，924，627)，则用基数排序需要进行（ ） 趟的分配和回收才能使得初始关键字序列变成有序序列。 A. 3 B. 4 C. 5 D. 8 2. 有n 个记录的文件，如关键字位数为d，基数为r ，则基数排序共要进行 （ ）遍 分配与收集。 A. n B. d C. r D. n - d 3. 已知一组关键字为{25，48 ，36，72，79 ，82，23 ，40 ，16，35}，进行一趟基数排序 的结果是 （ ）。 A. {25，36，48 ，72，23 ，40 ，79，82，16，35} B. {40，72，82，23 ，25 ，35，36，16，48 ，79} C. {16，25 ，23 ，36，35，48 ，40 ，72，79，82} D. {16，23 ，25 ，35，36，40 ，48 ，72，79，82} 二．简答题部分 1. 对278 、109、063、930、589、184、505、269 、008、083 进行基数排序，并给出详细 的排序过程。 2. 对如图7.33 所示的初始状态序列进行链式基数排序。 278 109 063 930 589 184 505 269 008 083 图7.33 参 考 答 案 一．选择题部分 1. A 【解析】本题属于比较简单的基数排序常识。对于 3 位数，需要进行三次分配和收集 2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 才能使得初始关键字序列变成有序序列。读者可以参考本考点的综合应用题部分的习题。 2. B 【解析】基数排序的分配和收集次数，与关键字的位数相等，与基数和记录数量无关。 而基数，是决定“桶”数量的数。比如，对三位整数进行基数排序，需要排序3 次，个位、 十位、百位各一次。需要10 个桶，每个桶用来装排序时该位分别为0~9 的关键字。 3. B 【解析】对给定的关键字进行一趟基数排序，排序的结果，使得最低位有序，即个位 有序，对应的排序过程如图7.34 所示。 25 48 36 72 79 82 23 40 16 35 82 35 16 40 72 23 25 36 48 79 桶0 桶1 桶2 桶3 桶4 桶5 桶6 桶7 桶8 桶9 图7.34 对上图的基数排序结果进行收集，得到图7.35 的排序结果。可知，本题选择B 答案。 40 72 82 23 25 35 36 16 48 79 图7.35 二．综合应用题部分 1. 【解析】基数排序通过“分配”和“收集”过程来实现排序。首先初始化10 个“桶”， 桶其实就是队列。按个位大小把待排序列依次放入到这十个桶中。第一趟的排序过程如图 7.36 所示。 278 109 063 930 589 184 505 269 008