🏷️ 知识点：插入排序
对5个不同的数据元素进行直接插入排序，最多需要进行的比较次数是()。注意， 哨兵的比较不计入次数。
A. 8 B. 10 C.15 D.25
[tag_link]
正确答案：B
在待排序的元素序列基本有序的前提下，效率最高的排序算法是()。
A. 直接插入排序 B. 简单选择排序 C. 快速排序 D. 归并排序
[tag_link]
正确答案：A
对有n 个元素的顺序表采用直接插入排序算法进行排序，在最坏情况下所需的比较次数 是(),在最好情况下所需的比较次数是()。
A. n-1 B.n+1 C. n/2 D.n(n-1)/2
[tag_link]
正确答案：
数据序列{8,10,13,4,6,7,22,2,3}只能是()两趟排序后的结果。
A. 简单选择排序 B. 冒泡排序 C. 直接插入排序 D. 堆排序
[tag_link]
正确答案：C
用直接插入排序算法对下列4个表进行(从小到大)排序，比较次数最少的是()。 A.94,32,40,90,80,46,21,69 B.21,32,46,40,80,69,90,94
C. 32,40,21,46,69,94,90,80 D.90,69,80,46,21,32,94,40
[tag_link]
正确答案：B
在下列算法中，()算法可能出现下列情况：在最后一趟开始之前，所有元素都不在 最终位置上。
A. 堆排序 B. 冒泡排序 C. 直接插入排序 D. 快速排序
[tag_link]
正确答案：C
排序趟数与序列的原始状态有关的排序方法是（ ）。
A. 插入排序 B. 选择排序 C. 冒泡排序 D. 快速排序
[tag_link]
正确答案：C
排序算法的趟数通常指完成排序所需的全过程遍历次数。 对于选项中的几种排序方法：插入排序和选择排序的趟数都是固定的，与序列的原始状态无关。 插入排序需要 n-1 趟将每个元素插入已排序部分，选择排序也需要 n-1 趟选择最小元素，它们的趟数仅由元素个数决定。
冒泡排序的趟数则与序列的原始状态密切相关。 在优化后的冒泡排序中，每一趟遍历比较相邻元素，如果某一趟没有发生任何交换，说明序列已经有序，排序可以提前结束。 因此，在最好情况下（序列已有序），只需一趟即可完成； 在最坏情况下（序列逆序），需要 n-1 趟。 这使得趟数直接受原始序列顺序影响。
快速排序的性能虽与原始状态有关，但“排序趟数”并非其标准描述方式，它更侧重于递归深度或划分次数，这些虽与原始状态相关，但概念上不如冒泡排序的趟数明确。 因此，本题中排序趟数与序列原始状态有关的方法是冒泡排序。
希尔排序属于()。
A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序
[tag_link]
正确答案：A
设线性表中每个元素有两个数据项 k1 和 k2，现对线性表按以下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的在后；在 k1 值相同的情况下，再看 k2，k2 值小的在前，大的在后。满足这种要求的排序方法是（ ）。
A. 先按 k1 进行直接插入排序，再按 k2 进行简单选择排序 B. 先按 k2 进行直接插入排序，再按 k1 进行简单选择排序 C. 先按 k1 进行简单选择排序，再按 k2 进行直接插入排序 D. 先按 k2 进行直接选择排序，再按 k1 进行直接插入排序
[tag_link]
正确答案：D
该排序要求为先按k1排序，k1相同时再按k2排序，属于多关键字排序。
为实现此类排序，通常需先按次要关键字（k2）排序，再按主要关键字（k1）进行稳定排序，从而在k1相同的情况下保持k2的顺序。
分析各选项：A先按k1进行直接插入排序（稳定），再按k2进行简单选择排序（不稳定），第二次不稳定排序可能破坏已排好的k1顺序，不满足要求； B先按k2进行直接插入排序（稳定），再按k1进行简单选择排序（不稳定），第二次不稳定排序可能打乱k1相同时的k2顺序，不符合要求； C先按k1进行简单选择排序（不稳定），再按k2进行直接插入排序（稳定），第一次不稳定排序导致k1顺序混乱，第二次稳定排序按k2进行，最终序列主要按k2排序，而非先k1后k2，同样不满足； D先按k2进行直接选择排序（不稳定），再按k1进行直接插入排序（稳定），第一次按k2排序后序列整体k2有序，第二次稳定排序按k1进行，能保证k1有序的同时，对k1相同的元素保持第一次排序后的k2顺序，从而实现先k1后k2的排序要求，故D正确。
对一组数据（84,47,15,21,25）排序，数据在排序的过程中的变化如下：
A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序
[tag_link]
正确答案：C
观察排序过程中的变化：初始序列为 (84,47,15,21,25)。 第一步变为 (25,47,15,21,84)，这类似于快速排序中选择第一个元素 84 作为枢轴进行分区的结果：将小于 84 的元素移至左边，大于的移至右边，最终 84 被放置到正确位置（末尾）。 第二步变为 (21,25,15,47,84)，这对应于对左子序列 (25,47,15,21) 进行快速排序的分区操作，选择 25 作为枢轴，经过交换和调整后得到此序列。 这些步骤符合快速排序的分区递归特性。
其他排序方法不符：冒泡排序每趟通过相邻交换将最大元素移至末尾，第一趟后应为 (47,15,21,25,84)，与第二步不同； 插入排序逐步构建有序序列，不会直接将 84 移至末尾； 堆排序需先建堆再交换调整，但第二步到第三步的变化不似堆调整过程。 因此，所选方法为快速排序。
数据序列（2,1,4,9,8,10,6,20）只能是（ ）排序的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序
[tag_link]
正确答案：A
首先分析序列（2,1,4,9,8,10,6,20）作为各排序算法两趟后的可能性。 冒泡排序两趟后，最大和第二大元素应位于末尾，但序列末尾为 6 和 20，第二大的 10 不在倒数第二，排除 B。 选择排序两趟后，最小和第二小元素应位于前两位，但序列前两位为 2 和 1，而非 1 和 2，排除 C。 插入排序两趟后，前两个元素应有序，但序列前两位为 2 和 1（无序），排除 D。
快速排序的可能在于：序列中元素 4 满足左边（2,1）均小于 4，右边（9,8,10,6,20）均大于 4，符合快速排序一趟分区后枢轴就位的特征。 考虑两趟操作：第一趟以最后一个元素 20 为枢轴进行分区，由于 20 最大，分区后序列不变； 第二趟对左子序列（2,1,4,9,8,10,6）以 4 为枢轴进行分区，使 4 就位，且左子序列保持为 2,1,4,9,8,10,6，从而得到当前序列。 尽管枢轴选择可能非标准（如选中间元素），但快速排序允许不同策略，而其他算法均不匹配，因此 A 正确。
在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是（）
Ⅰ. 归并排序的程序代码更短Ⅱ. 归并排序的占用空间更少Ⅲ. 归并排序的运行效率更高
A. 仅 Ⅱ B. 仅 Ⅲ C. 仅 Ⅰ、Ⅱ D. 仅 Ⅰ、Ⅲ
[tag_link]
正确答案：B
参考 排序算法复杂度 ，归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n), 后者是O(1)。但是前者时间复杂度是O(nlogn), 后者是O(n2)。所以 B 正确。
对序列{15,9,7,8,20,-1,4}采用希尔排序，经一趟后序列变为{15,-1,4,8,20,9,7},则 该次采用的增量是()。
A. 1 B.4 C. 3 D.2
[tag_link]
正确答案：B
对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
[tag_link]
正确答案：D
本题考察 插入排序 ，折半插入排序与直接插入排序是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数n，两者都是n−1趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 O(1)。折半插入排序的比较次数与序列初态无关，为O(nlog2n)：直接插入排序的比较次数与序列初态有关，为O(n)∼O(n2)。
对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是（ ）。
I. 直接插入排序过程中元素之间的比较次数更少
II. 直接插入排序过程中所需要的辅助空间更少
III. 直接插入排序过程中元素的移动次数更少
A. 仅 I B. 仅 III C. 仅 I，II D. 仅 I，II 和 III
[tag_link]
正确答案：A
考虑较极端的情况，对于有序数组， 直接插入排序 的比较次数为n−1，简单选择排序的比较次数始终为1+2+⋯+n−1=n(n−1)/2，I 正确。两种排序方法的辅助空间都是O(1)，无差别，II 错误。初始有序时，移动次数均为 0；对于通常情况，直接插入排序每趟插入都 需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少很多，III 错误。
若序列{15,9,7,8,20,-1,4}经一趟排序后变成{9,15,7,8,20,-1,4},则采用的是() 方法。
A. 选择排序 B. 快速排序 C. 直接插入排序 D. 冒泡排序
[tag_link]
正确答案：C
对序列{98,36,-9,0,47,23,1,8,10,7}采用希尔排序，下列序列()是增量为4的一趟 排序结果。
A. {10,7,-9,0,47,23,1,8,98,36} B.{-9,0,36,98,1,8,23,47,7,10} C. {36,98,-9,0,23,47,1,8,7,10} D. 以上都不对
[tag_link]
正确答案：A
对序列{E,A,S,Y,Q,U,E,S,T,I,O,N} 按照字典顺序排序，采用增量d=6,3,1 的希尔排 序算法。则前两趟排序后，关键字的总比较次数为()。
A. 15 B.17 C.16 D.18
[tag_link]
正确答案：B
已知输入序列{13,24,7,1,8,9,11,56,34,51,2,77,5},增量序列d=5,3,1, 采用希尔排 序算法进行排序，则两趟排序后的结果为()。
A. 1,7,8,9,13,24,11,34,51,2,5,56,77 B. 1,7,5,2,8,9,24,11,34,51,13,77,56 C. 2,11,5,1,8,9,24,7,34,51,13,77,56 D. 2,5,11,1,8,9,7,24,34,13,51,77,56
[tag_link]
正确答案：B
折半插入排序算法的时间复杂度为()。
A. O(n) B.O(nlog₂n) C.O(n²) D.O(n³)
[tag_link]
正确答案：C
有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，()算法 不一定会出现此种情况。
A. 希尔排序 B. 堆排序 C. 冒泡排序 D. 快速排序
[tag_link]
正确答案：A
以下排序算法中，不稳定的是()。
A. 冒泡排序 B. 直接插入排序 C. 希尔排序 D. 归并排序
[tag_link]
正确答案：C
以下排序算法中，稳定的是()。
A. 快速排序 B. 堆排序 C. 直接插入排序 D. 简单选择排序
[tag_link]
正确答案：C
【2014 统考真题】用希尔排序算法对一个数据序列进行排序时，若第一趟排序结果为 9,1,4,13,7,8,20,23,15,则该趟排序采用的增量(间隔)可能是()。
A. 2 B.3 C.4 D.5
[tag_link]
正确答案：B
给出关键字序列{4,5,1,2,6,3}的直接插入排序过程。
[tag_link]
B
给出关键字序列{50,26,38,80,70,90,8,30,40,20}的希尔排序过程(取增量序列为d= {5,3,1},排序结果为从小到大排列)。 338 2 0 2 7 年 数 据 结 构 考 研 复 习 指 导
[tag_link]
A
(10分)现有 n(n>100000)个数保存在一维数组 M中，需要查找 M中最小的10个数，请回答下列 问题。
(1) 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不 需要程序实现。
(2)说明你所设计的算法平均情况下的时间复杂度和空间复杂度。
[tag_link]
[tag_link]
【答案 1】 定义含 10 个元素的数组 A，初始时元素值均为该数组类型能表示的最大数 MAX。 for M 中的每个元素 s if (s < A[9]) 丢弃 A[9]并将 s 按升序插入到 A 中； 当数据全部扫描完毕，数组 A[0]~A[9]保存的即是最小的 10 个数。 【答案 2】 定义含 10 个元素的大根堆 H，元素值均为该堆元素类型能表示的最大数 MAX。 for M 中的每个元素 s if （s < H 的堆顶元素） 删除堆顶元素并将 s 插入到 H 中； 当数据全部扫描完毕，堆 H 中保存的即是最小的 10 个数。 组成原理 43 某 CPU 中部分数据通路如图所示，其中，GPRs 为通用寄存器组；FR 为标志寄存器，用于存放 ALU 产生的标志信息；带箭头虚线表示控制信号，如控制信号 ReaD. Write 分别表示主存读、主存写，MDRin 表示内部总线上数据写入 MDR，MDRout 表示 MDR 的内容送内部总线。 MAR