🏷️ 知识点：基数排序
下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是（）。
A. 直接插入排序 B. 起泡排序 C. 基数排序 D. 快速排序
[tag_link] 正确答案：C 基数排序 的元素移动次数与关键字的初始排列次序无关，而其他三种排序都是与关键字的初始排列明显相关的。
设数组 S[] = {93, 946, 372, 9, 146,151, 301, 485, 236, 327, 43, 892}, 采用最低位优先（LSD）基数排序将 S 排列成升序序列。第 1 趟分配、收集后，元素 372 之前、之后紧邻的元素分别是 ( )
A. 43,892 B. 236,301 C. 301,892 D. 485,301
[tag_link]
正确答案：C
LSD 基数排序 第一趟根据最低位对数组进行排序，得到的结果为 {151, 301, 372, 892, 93, 43, 485, 946, 146, 267, 327}。
对 {05,46,13,55,94,17,42} 进行基数排序，一趟排序的结果是（ ）。
A. 05,46,13,55,94,17,42
B. 05,13,17,42,46,55,94
C. 42,13,94,05,55,46,17
D. 05,13,46,55,17,42,94
[tag_link]
正确答案：C
基数排序通常从最低有效位（LSD）开始，对数字的每一位进行稳定排序。 给定序列 {05,46,13,55,94,17,42} 均为两位数，第一趟排序根据个位数字进行。 首先，提取每个数字的个位：05（个位 5）、46（个位 6）、13（个位 3）、55（个位 5）、94（个位 4）、17（个位 7）、42（个位 2）。 按照个位数字分配桶（0-9），保持稳定性： 个位 2:42 个位 3:13 个位 4:94 个位 5:05、55（保持原序，05 在 55 前） 个位 6:46 个位 7:17 按桶顺序收集数字，得到序列：42,13,94,05,55,46,17。 这与选项 C 一致。 选项 A 是原始序列； 选项 B 是完全排序后的结果； 选项 D 不符合个位排序顺序。 因此，一趟排序结果为 C。
对给定的关键字序列 110，119，007，911，114，120，122 进行基数排序，则第 2 趟分配收集后得到的关键字序列是（）。
A.007，110，119，114，911，120，122
B.007，110，119，114，911，122，120
C.007，110，911，114，119，120，122
D.110，120，911，122，114，007，119
[tag_link] 正确答案：C基数排序 一般使用低位优先，即第 1 趟排序是按照个位数字的大小来排序的，第 2 趟排序是按照十位数字的大小进行排序的，排序的过程如下图所示。
若要求排序是稳定的，且关键字为实数，则在下列排序算法中应选()。
A. 直接插入排序 B. 选择排序 C. 基数排序 D. 快速排序
[tag_link]
正确答案：A
以下排序算法中时间复杂度为O(nlog₂n) 且稳定的是()。
A. 堆排序 B. 快速排序 C. 归并排序 D. 直接插入排序
[tag_link]
正确答案：C
设被排序的结点序列共有n 个结点，在该序列中的结点已十分接近有序的情况下，用直 接插入排序、归并排序和快速排序对其进行排序，这些算法的时间复杂度应为()。
A. O(n),O( n),O(n) B.O(n), O(nlog₂n),O(nlog₂n) C. O(n),O(nlog₂n),O(n²) D.O(n²),O(nlog₂ n),O(n²)
[tag_link]
正确答案：C
下列排序算法中属于稳定排序的是(①), 平均时间复杂度为O(nlog₂n)的是(②),在 最好的情况下，时间复杂度可以达到线性时间的有(③)。(注：多选题) I. 冒泡排序 IⅡ. 堆排序 Ⅲ . 选择排序 IV. 直接插入排序 V. 希尔排序 VI. 归并排序 VII. 快速排序
[tag_link]
正确答案：
就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是()。
A. 堆排序<快速排序<归并排序 B. 堆排序<归并排序<快速排序 C. 堆排序>归并排序>快速排序 D. 堆排序>快速排序>归并排序
[tag_link]
正确答案：A
排序趟数与序列的初始状态无关的排序算法是()。 I. 快速排序Ⅱ . 简单选择排序]Ⅲ . 冒泡排序 IV. 基数排序
A. I 、Ⅲ B.Ⅱ 、IV C.I 、Ⅱ 、IV D.I 、IV
[tag_link]
正确答案：B
排序趟数与序列的初始状态有关的排序算法是()。
A. 直接插入排序 B.2 路归并排序 C. 快速排序 D. 堆排序
[tag_link]
正确答案：C
对n 个元素进行排序，其排序趟数肯定为n-1 趟的排序算法是()。
A. 直接插入排序和快速排序 B. 冒泡排序和快速排序 C. 简单选择排序和直接插入排序 D. 简单选择排序和冒泡排序
[tag_link]
正确答案：C
若序列的初始状态为{1,2,3,4,5,10,6,7,8,9},要想使得排序过程中的元素比较次数最 少，则应该采用()方法。
A. 插入排序 B. 选择排序 C. 希尔排序 D. 冒泡排序
[tag_link]
正确答案：A
对于元素个数相同的不同初始序列，总比较次数大致相同的排序算法是()。
A. 折半插入排序和简单选择排序 B. 基数排序和归并排序 C. 冒泡排序和快速排序 D. 堆排序
[tag_link]
正确答案：A
一般情况下，以下查找效率最低的数据结构是()。
A. 有序顺序表 B. 二叉排序树 C. 堆 D. 平衡二叉树
[tag_link]
正确答案：C
一台计算机具有多核CPU,可以同时执行相互独立的任务。归并排序的各个归并段可以 并行执行，在下列排序算法中，不可以并行执行的有()。 I. 基数排序 II. 快速排序 I. 冒泡排序 IV. 堆排序
A. I 、Ⅲ B. I 、Ⅱ C.I 、Ⅲ 、IV D.Ⅱ 、IV
[tag_link]
正确答案：A
设关键字序列为{3,7,6,9,7,1,4,5,20},对其进行排序的最小交换次数是多少?
[tag_link]
A
设顺序表用数组A[]表示，表中元素存储在数组下标1～m+n 的范围内，前m 个元素递 增有序，后n 个元素递增有序，设计一个算法，使得整个顺序表有序。 1)给出算法的基本设计思想。 2)根据设计思想，采用C/C++描述算法，关键之处给出注释。 3)说明你所设计算法的时间复杂度与空间复杂度。
[tag_link]
C
设有一个数组中存放了一个无序的关键序列K₁,K₂…,Kn 。 现要求将Kn放在将元素排序 后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。
[tag_link]
C