第54卷 算法与程序设计—排序算法—河北省计算机类—考纲百套卷
|
2份
|
18页
|
70人阅读
|
0人下载
内容正文：
编写说明：河北省对口招生计算机类《考纲百套卷》，依据《河北省普通高等学校对口招生考试大纲（2028版专业课）计算机类》编写。本专辑涵盖9门课程，第一部分是专业核心模块训练卷，第二部分为各门课程的综合训练卷。本专辑共98份试卷。
本试卷是第54卷为专业核心模块训练卷，按《算法与程序设计》中"算法程序卷9——排序算法"范围和要求编写。具体内容为：掌握选择法、冒泡法、插入等排序算法
河北省对口招生职业技能考试
算法与程序设计 试卷
（算法程序卷9——排序算法）
考试时间：90分钟 满分：100分
一、单项选择题（共20题，每题2分，共40分）
1. 冒泡排序的最坏时间复杂度是（）
A.O(n) B.O(n²) C.O(n log n) D.O(1)
2. 以下哪个是稳定排序算法（）
A.快速排序 B.堆排序 C.冒泡排序 D.希尔排序
3. 冒泡排序的时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(2ⁿ)
4. 以下排序算法中，时间复杂度为O(n log n)的是（）。
A.冒泡排序 B.选择排序 C.快速排序 D.插入排序
5. 快速排序的平均时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(log n)
6. 下列排序算法中，不稳定排序是（）。
A.冒泡排序 B.插入排序 C.快速排序 D.归并排序
7. 以下排序算法中，最好情况时间复杂度为O(n)的是（）。
A.冒泡排序（加优化） B.快速排序 C.选择排序 D.堆排序
8. 排序算法的稳定性是指（）。
A.算法运行时间稳定 B.排序后相同关键字的元素相对顺序保持不变
C.空间复杂度不变 D.时间复杂度不变
9. 下列排序算法中，哪些是稳定排序（）。
A.冒泡排序 B.插入排序 C.归并排序 D.以上都是
10. 直接插入排序的时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(2ⁿ)
11. 选择排序的时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(2ⁿ)
12. 以下关于冒泡排序的说法，正确的是（）。
A.冒泡排序是不稳定排序 B.冒泡排序通过反复交换相邻元素实现排序
C.冒泡排序最好情况时间复杂度为O(n²) D.冒泡排序不需要进行元素比较
13. 直接插入排序的核心思想是（）。
A.将待排序元素插入到已排序序列的合适位置 B.反复交换相邻的逆序元素
C.每次选出最小元素放到有序序列末尾 D.将序列分成两部分，分别排序后合并
14. 选择排序的核心操作是（）。
A.交换相邻元素 B.插入元素到有序序列
C.找出当前未排序序列中的最值元素 D.将序列拆分后合并
15. 以下排序算法中，空间复杂度为O(1)的是（）。
A.冒泡排序 B.快速排序 C.归并排序 D.堆排序
16. 优化后的冒泡排序，当（）时，可提前结束排序过程。
A.待排序序列为空 B.待排序序列已有序 C.待排序序列长度为1 D.已交换过一次元素
17. 下列关于插入排序的说法，错误的是（）。
A.插入排序是稳定排序 B.插入排序适合数据量较小的场景
C.插入排序的最坏时间复杂度为O(n²) D.插入排序不需要进行元素移动
18. 选择排序与冒泡排序的共同点是（）。
A.都是稳定排序 B.时间复杂度都是O(n²)
C.空间复杂度都是O(n) D.都不需要元素交换
19. 以下关于排序算法的应用场景，说法正确的是（）。
A.数据量较大时优先使用冒泡排序 B.要求排序稳定且数据量小时可使用插入排序
C.选择排序适合要求稳定排序的场景 D.以上都正确
20. 下列排序算法中，不需要进行元素交换的是（）。
A.冒泡排序 B.选择排序 C.插入排序 D.快速排序
二、填空题（共10空，每空1分，共10分）
21. 冒泡排序的核心是通过反复______相邻的逆序元素，逐步将最大（或最小）元素“冒泡”到序列末尾。
22. 直接插入排序是将待排序元素插入到______序列的合适位置，从而实现排序。
选择排序每次从______序列中选出最小（或最大）元素，放到有序序列的末尾。
24. 排序算法的______是指排序后，相同关键字的元素相对顺序保持不变。
25. 冒泡排序、插入排序的最坏时间复杂度均为______。
26. 优化后的冒泡排序，若某一趟排序中没有发生______，则说明序列已有序，可提前结束排序。
27. 直接插入排序中，待排序元素与已排序序列元素进行______，找到合适的插入位置。
28. 选择排序的空间复杂度为______，属于原地排序算法。
29. 若要求排序后相同关键字元素的相对顺序不变，应选择______排序（填“稳定”或“不稳定”）算法。
30. 插入排序适合______（填“数据量小”或“数据量大”）的场景，排序效率较高。
三、判断题（共5题，每题2分，共10分）
31. 冒泡排序是稳定排序算法。（ ）
32. 选择排序的时间复杂度不受待排序序列有序程度的影响，始终为O(n²)。（ ）
33. 插入排序的最好情况时间复杂度为O(n)，此时待排序序列已有序。（ ）
34. 稳定排序算法一定比不稳定排序算法效率高。（ ）
35. 冒泡排序和选择排序都属于交换类排序算法。（ ）
四、程序分析题（共1题，每题10分，共10分）
36. 阅读下面的C#程序，分析其功能并写出运行结果。
using System;
class Program
{
static void Main()
{
string s = "Hello World";
int count = 0;
foreach (char c in s)
{
if (c == 'l')
count++;
}
Console.WriteLine(count);
Console.WriteLine(s.Length);
}
}
程序运行结果：___________________
五、写运行结果题（共2题，每题5分，共10分）
37. 分析下面C#程序段的输出结果：
using System;
class Program
{
static void Main()
{
int a = 5, b = 3;
Console.WriteLine(a / b);
Console.WriteLine(a % b);
Console.WriteLine((double)a / b);
}
}
程序运行结果：___________________
38. 分析下面C#程序段的输出结果：
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
List<int> lst = new List<int> { 1, 2, 3, 4, 5 };
lst.Add(6);
lst.Remove(3);
Console.WriteLine(lst.Count);
Console.WriteLine(lst[2]);
}
}
程序运行结果：___________________
六、程序改错题（共1题，每题5分，共5分）
39. 下面程序判断闰年，但有2处错误，请找出并改正：
using System;
class Program{
static void Main(){
int year = 2024;
if(year % 4 == 0)
Console.WriteLine("是闰年");
}
}
请找出程序中的错误，并写出正确答案。
七、程序填空题（共3题，每题5分，共15分）
40. 下面程序用选择排序对数组升序排列，请填写空白处：
using System;
class Program
{
static void Main()
{
int[] a = { 64, 25, 12, 22, 11 };
int n = a.Length;
for (int i = 0; i < n - 1; i++)
{
int minIdx = i;
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[minIdx])
minIdx = _____;
}
int temp = a[minIdx];
a[minIdx] = a[i];
a[i] = _____;
}
foreach (int x in a)
Console.Write(x + " ");
}
}
41. 下面程序判断一个数是否为素数，请填写空白处：
using System;
class Program
{
static bool IsPrime(int n)
{
if (n < 2) return false;
for (int i = 2; i <= _____; i++)
{
if (n % i == 0) return false;
}
return true;
}
static void Main()
{
for (int i = 1; i <= 20; i++)
{
if (IsPrime(i))
Console.Write(i + " ");
}
}
}
42. 下面程序用于求数组最大值及其位置，请填写空白处：
using System;
class Program{
static void Main(){
int[] a = {3, 7, 2, 9, 1};
int max = a[0];
int pos = 0;
for(int i = 1; i < a.Length; i++){
if(_____){
max = a[i];
pos = _____;}
}
Console.WriteLine("max=" + max + " pos=" + pos);
}
}
学科网（北京）股份有限公司
$
编写说明：河北省对口招生计算机类《考纲百套卷》，依据《河北省普通高等学校对口招生考试大纲（2028版专业课）计算机类》编写。本专辑涵盖9门课程，第一部分是专业核心模块训练卷，第二部分为各门课程的综合训练卷。本专辑共98份试卷。
本试卷是第54卷为专业核心模块训练卷，按《算法与程序设计》中"算法程序卷9——排序算法"范围和要求编写。具体内容为：掌握选择法、冒泡法、插入等排序算法
河北省对口招生职业技能考试
算法与程序设计 试卷
（算法程序卷9——排序算法）
考试时间：90分钟 满分：100分
一、单项选择题（共20题，每题2分，共40分）
1. 冒泡排序的最坏时间复杂度是（）
A.O(n) B.O(n²) C.O(n log n) D.O(1)
【答案】B
【解析】冒泡排序的最坏情况是待排序序列完全逆序，此时需要进行n-1趟排序，每趟排序需比较n-i次（i为趟数），总比较次数为n(n-1)/2，时间复杂度为O(n²)。
2. 以下哪个是稳定排序算法（）
A.快速排序 B.堆排序 C.冒泡排序 D.希尔排序
【答案】C
【解析】稳定排序是指排序后相同关键字的元素相对顺序保持不变。冒泡排序仅交换相邻逆序元素，相同关键字元素不会发生相对位置变化，属于稳定排序；A、B、D选项均为不稳定排序。
3. 冒泡排序的时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(2ⁿ)
【答案】C
【解析】冒泡排序无论最好、最坏情况，核心时间复杂度均为O(n²)；其中最好情况（待排序序列有序）可通过优化提前结束排序，但时间复杂度仍属于O(n²)范畴。
4. 以下排序算法中，时间复杂度为O(n log n)的是（）。
A.冒泡排序 B.选择排序 C.快速排序 D.插入排序
【答案】C
【解析】A、B、D选项（冒泡、选择、插入排序）的时间复杂度均为O(n²)；快速排序的平均时间复杂度为O(n log n)，是效率较高的排序算法之一。
5. 快速排序的平均时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(log n)
【答案】B
【解析】快速排序通过分治思想将序列拆分排序，平均情况下时间复杂度为O(n log n)；最坏情况（待排序序列有序或逆序）时间复杂度为O(n²)，但实际应用中效率优于冒泡、选择等排序。
6. 下列排序算法中，不稳定排序是（）。
A.冒泡排序 B.插入排序 C.快速排序 D.归并排序
【答案】C
【解析】不稳定排序是指排序后相同关键字的元素相对顺序发生变化。快速排序在分区过程中会交换不相邻元素，可能导致相同关键字元素相对位置改变，属于不稳定排序；A、B、D选项均为稳定排序。
7. 以下排序算法中，最好情况时间复杂度为O(n)的是（）。
A.冒泡排序（加优化） B.快速排序 C.选择排序 D.堆排序
【答案】A
【解析】加优化的冒泡排序，当待排序序列已有序时，仅需一趟遍历（无元素交换）即可结束排序，最好情况时间复杂度为O(n)；B、C、D选项最好情况时间复杂度均不为O(n)。
8. 排序算法的稳定性是指（）。
A.算法运行时间稳定 B.排序后相同关键字的元素相对顺序保持不变 C.空间复杂度不变 D.时间复杂度不变
【答案】B
【解析】排序算法的稳定性定义为：排序后，具有相同关键字的元素，其在原始序列中的相对顺序保持不变；A、C、D选项均不符合稳定性的定义。
9. 下列排序算法中，哪些是稳定排序（）。
A.冒泡排序 B.插入排序 C.归并排序 D.以上都是
【答案】D
【解析】冒泡排序、插入排序、归并排序均满足“排序后相同关键字元素相对顺序不变”的条件，均属于稳定排序算法。
10. 直接插入排序的时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(2ⁿ)
【答案】C
【解析】直接插入排序的核心是将待排序元素插入已排序序列，最坏和平均时间复杂度均为O(n²)；最好情况（序列有序）时间复杂度为O(n)，但整体归类为O(n²)排序算法。
11. 选择排序的时间复杂度是（）。
A.O(n) B.O(n log n) C.O(n²) D.O(2ⁿ)
【答案】C
【解析】选择排序每次从无序序列中选出最值元素，无论待排序序列是否有序，都需要进行n-1趟遍历和比较，时间复杂度始终为O(n²)。
12. 以下关于冒泡排序的说法，正确的是（）。
A.冒泡排序是不稳定排序 B.冒泡排序通过反复交换相邻元素实现排序 C.冒泡排序最好情况时间复杂度为O(n²) D.冒泡排序不需要进行元素比较
【答案】B
【解析】A选项错误，冒泡排序是稳定排序；B选项正确，冒泡排序的核心操作是反复交换相邻的逆序元素，逐步将最值元素“冒泡”到序列末尾；C选项错误，优化后的冒泡排序最好情况时间复杂度为O(n)；D选项错误，冒泡排序需通过元素比较判断是否为逆序，才能进行交换。
13. 直接插入排序的核心思想是（）。
A.将待排序元素插入到已排序序列的合适位置 B.反复交换相邻的逆序元素 C.每次选出最小元素放到有序序列末尾 D.将序列分成两部分，分别排序后合并
【答案】A
【解析】A选项是直接插入排序的核心思想；B选项是冒泡排序的核心思想；C选项是选择排序的核心思想；D选项是归并排序的核心思想。
14. 选择排序的核心操作是（）。
A.交换相邻元素 B.插入元素到有序序列 C.找出当前未排序序列中的最值元素 D.将序列拆分后合并
【答案】C
【解析】选择排序的核心的是“选最值、放有序”，即每次从当前未排序序列中找出最小（或最大）元素，将其放到已排序序列的末尾；A选项是冒泡排序操作，B选项是插入排序操作，D选项是归并排序操作。
15. 以下排序算法中，空间复杂度为O(1)的是（）。
A.冒泡排序 B.快速排序 C.归并排序 D.堆排序
【答案】A
【解析】空间复杂度O(1)表示算法不需要额外的辅助空间（原地排序）。冒泡排序仅通过交换相邻元素实现排序，无需额外空间；B选项快速排序空间复杂度为O(log n)~O(n)，C选项归并排序为O(n)，D选项堆排序为O(1)，但题干中仅A选项符合核心考点（冒泡、选择、插入排序）。
16. 优化后的冒泡排序，当（）时，可提前结束排序过程。
A.待排序序列为空 B.待排序序列已有序 C.待排序序列长度为1 D.已交换过一次元素
【答案】B
【解析】优化后的冒泡排序会增加一个标记，若某一趟排序中没有发生任何元素交换，说明待排序序列已完全有序，无需继续后续趟数，可提前结束排序，提升效率。
17. 下列关于插入排序的说法，错误的是（）。
A.插入排序是稳定排序 B.插入排序适合数据量较小的场景 C.插入排序的最坏时间复杂度为O(n²) D.插入排序不需要进行元素移动
【答案】D
【解析】A、B、C选项说法均正确；D选项错误，插入排序中，为了给待排序元素腾出合适的插入位置，需要将已排序序列中大于（或小于）待排序元素的元素依次向后移动。
18. 选择排序与冒泡排序的共同点是（）。
A.都是稳定排序 B.时间复杂度都是O(n²) C.空间复杂度都是O(n) D.都不需要元素交换
【答案】B
【解析】A选项错误，选择排序是不稳定排序，冒泡排序是稳定排序；B选项正确，两者的时间复杂度均为O(n²)；C选项错误，两者空间复杂度均为O(1)；D选项错误，两者均需要进行元素交换（选择排序交换最值元素与有序序列末尾元素，冒泡排序交换相邻逆序元素）。
19. 以下关于排序算法的应用场景，说法正确的是（）。
A.数据量较大时优先使用冒泡排序 B.要求排序稳定且数据量小时可使用插入排序 C.选择排序适合要求稳定排序的场景 D.以上都正确
【答案】B
【解析】A选项错误，数据量较大时，冒泡排序效率低，优先使用快速排序、归并排序等高效算法；B选项正确，插入排序稳定，且数据量小时排序效率高，适合该场景；C选项错误，选择排序是不稳定排序，不适合要求稳定排序的场景。
20. 下列排序算法中，不需要进行元素交换的是（）。
A.冒泡排序 B.选择排序 C.插入排序 D.快速排序
【答案】C
【解析】A选项冒泡排序通过交换相邻逆序元素排序；B选项选择排序通过交换最值元素与有序序列末尾元素排序；C选项插入排序通过移动元素腾出位置，将待排序元素插入，无需交换；D选项快速排序通过交换元素实现分区排序。
二、填空题（共10空，每空1分，共10分）
21. 冒泡排序的核心是通过反复______相邻的逆序元素，逐步将最大（或最小）元素“冒泡”到序列末尾。
【答案】交换
【解析】冒泡排序的核心操作是“交换相邻逆序元素”，每一趟排序都会将当前未排序序列中的最大（或最小）元素交换到序列末尾，逐步实现整体有序。
22. 直接插入排序是将待排序元素插入到______序列的合适位置，从而实现排序。
【答案】已排序
【解析】直接插入排序的核心思想是“边排序边有序”，将待排序序列中的元素依次插入到已排好序的子序列中，逐步扩大有序序列范围，最终实现整体排序。
23. 选择排序每次从______序列中选出最小（或最大）元素，放到有序序列的末尾。
【答案】未排序
【解析】选择排序分为有序序列和未排序序列两部分，每次从未排序序列中找出最值元素，将其移动到有序序列的末尾，直至未排序序列为空。
24. 排序算法的______是指排序后，相同关键字的元素相对顺序保持不变。
【答案】稳定性
【解析】稳定性是排序算法的重要特性之一，稳定排序可保证相同关键字元素的原始相对顺序不变，适用于对元素相对位置有要求的场景。
25. 冒泡排序、插入排序的最坏时间复杂度均为______。
【答案】O(n²)
【解析】冒泡排序和插入排序均属于简单排序算法，最坏情况（待排序序列逆序）下，时间复杂度均为O(n²)，效率低于快速排序、归并排序等高级排序算法。
26. 优化后的冒泡排序，若某一趟排序中没有发生______，则说明序列已有序，可提前结束排序。
【答案】元素交换
【解析】优化后的冒泡排序会添加一个交换标记，若某一趟排序中没有任何元素交换，说明所有元素已处于有序状态，无需继续后续排序，可提前终止，减少不必要的比较。
27. 直接插入排序中，待排序元素与已排序序列元素进行______，找到合适的插入位置。
【答案】比较
【解析】直接插入排序中，待排序元素需与已排序序列中的元素从后向前依次比较，判断自身应插入的位置，比较完成后移动元素并插入。
28. 选择排序的空间复杂度为______，属于原地排序算法。
【答案】O(1)
【解析】原地排序算法是指不需要额外辅助空间，仅在原始序列中进行操作。选择排序仅通过交换元素实现排序，无需额外空间，空间复杂度为O(1)。
29. 若要求排序后相同关键字元素的相对顺序不变，应选择______排序（填“稳定”或“不稳定”）算法。
【答案】稳定
【解析】稳定排序的核心特性是排序后相同关键字元素的相对顺序保持不变，若业务场景要求保留原始相对顺序，需选择稳定排序算法（如冒泡、插入排序）。
30. 插入排序适合______（填“数据量小”或“数据量大”）的场景，排序效率较高。
【答案】数据量小
【解析】插入排序的时间复杂度为O(n²)，数据量较小时，排序次数少、效率高；数据量较大时，排序次数激增，效率大幅下降，不适合该场景。
三、判断题（共5题，每题2分，共10分）
31. 冒泡排序是稳定排序算法。（ ）
【答案】√
【解析】冒泡排序仅交换相邻的逆序元素，对于相同关键字的元素，不会发生相对位置的交换，因此属于稳定排序算法。
32. 选择排序的时间复杂度不受待排序序列有序程度的影响，始终为O(n²)。（ ）
【答案】√
【解析】选择排序无论待排序序列是否有序，都需要进行n-1趟遍历，每趟遍历需找出未排序序列的最值元素，总比较次数固定，时间复杂度始终为O(n²)。
33. 插入排序的最好情况时间复杂度为O(n)，此时待排序序列已有序。（ ）
【答案】√
【解析】当待排序序列已有序时，插入排序无需移动元素，仅需遍历一遍序列即可完成排序，此时时间复杂度为O(n)，是插入排序的最好情况。
34. 稳定排序算法一定比不稳定排序算法效率高。（ ）
【答案】×
【解析】排序算法的效率由时间复杂度决定，与稳定性无关。例如，稳定排序中的冒泡排序（O(n²)）效率低于不稳定排序中的快速排序（平均O(n log n)）。
35. 冒泡排序和选择排序都属于交换类排序算法。（ ）
【答案】×
【解析】冒泡排序属于交换类排序算法（通过交换元素实现排序）；选择排序属于选择类排序算法（通过选择最值元素实现排序），并非交换类排序算法。
四、程序分析题（共1题，每题10分，共10分）
36. 阅读下面的C#程序，分析其功能并写出运行结果。
using System;
class Program
{
static void Main()
{
string s = "Hello World";
int count = 0;
foreach (char c in s)
{
if (c == 'l')
count++;
}
Console.WriteLine(count);
Console.WriteLine(s.Length);
}
}
程序运行结果：___________________
【答案】3
11
五、写运行结果题（共2题，每题5分，共10分）
37. 分析下面C#程序段的输出结果：
using System;
class Program
{
static void Main()
{
int a = 5, b = 3;
Console.WriteLine(a / b);
Console.WriteLine(a % b);
Console.WriteLine((double)a / b);
}
}
程序运行结果：___________________
【答案】1
2
1.6666666666666667
38. 分析下面C#程序段的输出结果：
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
List<int> lst = new List<int> { 1, 2, 3, 4, 5 };
lst.Add(6);
lst.Remove(3);
Console.WriteLine(lst.Count);
Console.WriteLine(lst[2]);
}
}
程序运行结果：___________________
【答案】5
4
六、程序改错题（共1题，每题5分，共5分）
39. 下面程序判断闰年，但有2处错误，请找出并改正：
using System;
class Program{
static void Main(){
int year = 2024;
if(year % 4 == 0)
Console.WriteLine("是闰年");
}
}
请找出程序中的错误，并写出正确答案。
【答案】错误：闰年条件不完整。正确条件为 (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
七、程序填空题（共3题，每题5分，共15分）
40. 下面程序用选择排序对数组升序排列，请填写空白处：
using System;
class Program
{
static void Main()
{
int[] a = { 64, 25, 12, 22, 11 };
int n = a.Length;
for (int i = 0; i < n - 1; i++)
{
int minIdx = i;
for (int j = i + 1; j < n; j++)
{
if (a[j] < a[minIdx])
minIdx = _____;
}
int temp = a[minIdx];
a[minIdx] = a[i];
a[i] = _____;
}
foreach (int x in a)
Console.Write(x + " ");
}
}
【答案】['j', 'temp']
41. 下面程序判断一个数是否为素数，请填写空白处：
using System;
class Program
{
static bool IsPrime(int n)
{
if (n < 2) return false;
for (int i = 2; i <= _____; i++)
{
if (n % i == 0) return false;
}
return true;
}
static void Main()
{
for (int i = 1; i <= 20; i++)
{
if (IsPrime(i))
Console.Write(i + " ");
}
}
}
【答案】['Math.Sqrt(n)', 'sqrt(n)']
42. 下面程序用于求数组最大值及其位置，请填写空白处：
using System;
class Program{
static void Main(){
int[] a = {3, 7, 2, 9, 1};
int max = a[0];
int pos = 0;
for(int i = 1; i < a.Length; i++){
if(_____){
max = a[i];
pos = _____;}
}
Console.WriteLine("max=" + max + " pos=" + pos);
}
}
【答案】['a[i] > max', 'i']
学科网（北京）股份有限公司
$
资源预览图
