CSP-J/S 枚举、模拟与排序综合测试

本试卷共 25 道单项选择题，每题 4 分，满分 100 分。

一、枚举与模拟

1. 枚举数组中所有无序数对，最合适的循环条件是（ ）。

{{ select(1) }}

• i=1..n，j=1..n
• i=1..n，j=i+1..n
• 只枚举 i
• 始终令 j=i

2. 对 n 个元素进行“选或不选”的二进制枚举，候选子集数量是（ ）。

{{ select(2) }}

• n
• n²
• 2^n
• n!

3. 下面代码的时间复杂度数量级是（ ）。

for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++)
        work(i,j);

{{ select(3) }}

• O(n)
• O(n²)
• O(n³)
• O(2^n)

4. 已知 x+y+z=100，为了减少枚举层数，较合适的做法是（ ）。

{{ select(4) }}

• 三个变量都从 0 枚举到 100
• 只枚举 z
• 枚举 x、y，由 z=100-x-y 推出
• 随机生成三个变量

5. 模拟算法最容易因哪一项处理不当而出错（ ）。

{{ select(5) }}

• 变量名太短
• 状态更新顺序和边界条件
• 使用了 for 循环
• 输出了换行

6. 用 dir=0,1,2,3 表示右、下、左、上，顺时针转向可写为（ ）。

{{ select(6) }}

• dir--
• dir=(dir+2)%4
• dir=(dir+1)%4
• dir=4

7. 下列关于闰年的判断正确的是（ ）。

{{ select(7) }}

• 1900 年和 2000 年都是闰年
• 1900 年是闰年，2000 年不是闰年
• 1900 年不是闰年，2000 年是闰年
• 只要能被 4 整除就是闰年

8. 约瑟夫问题只求最后幸存者时，0 下标递推常写为（ ）。

{{ select(8) }}

• ans=ans+m
• ans=(ans+m)%i
• ans=(ans+i)%m
• ans=m%i

二、基础排序

9. 带 changed 提前退出的冒泡排序，在原序列已有序时最好复杂度是（ ）。

{{ select(9) }}

• O(1)
• O(n)
• O(n log n)
• O(n²)

10. 下列排序通常是稳定排序的是（ ）。

{{ select(10) }}

• 冒泡排序
• 选择排序
• 普通快速排序
• 堆排序

11. 插入排序中，为保持稳定性，后移条件应写为（ ）。

{{ select(11) }}

• a[j] >= key
• a[j] > key
• a[j] == key
• a[j] < key

12. 选择排序通常不稳定的主要原因是（ ）。

{{ select(12) }}

• 使用了相邻交换
• 只能处理整数
• 远距离交换可能改变相等元素的相对顺序
• 比较次数太少

13. 对 1 下标数组 a[1..n] 升序排序，正确范围是（ ）。

{{ select(13) }}

• sort(a,a+n)
• sort(a+1,a+n)
• sort(a+1,a+n+1)
• sort(a,a+n+1)

14. 在 sort 的比较函数中，cmp(a,b) 返回 true 表示（ ）。

{{ select(14) }}

• a 与 b 必须相等
• a 应排在 b 前面
• b 应排在 a 前面
• 必须立刻交换 a、b

15. 下列比较函数最可能违反严格弱序要求的是（ ）。

{{ select(15) }}

• return a<b;
• return a>b;
• 多关键字严格比较
• return a<=b;

16. 关于 stable_sort，下列说法正确的是（ ）。

{{ select(16) }}

• 保证相等关键字的原相对顺序
• 一定只使用 O(1) 额外空间
• 一定比 sort 快
• 只能排序字符串

三、提高排序与应用

17. 归并排序的时间复杂度是（ ）。

{{ select(17) }}

• O(n²)
• O(n log n)
• O(log n)
• O(2^n)

18. 数组版归并排序通常需要的额外空间是（ ）。

{{ select(18) }}

• O(1)
• O(log n)
• O(n)
• O(n²)

19. 若 i<j 且满足什么条件，则 (i,j) 是逆序对（ ）。

{{ select(19) }}

• a[i]<a[j]
• a[i]>a[j]
• a[i]==a[j]
• i>j

20. 朴素快速排序在基准选择很差时，最坏复杂度可能退化为（ ）。

{{ select(20) }}

• O(1)
• O(n log n)
• O(n²)
• O(log n)

21. 当整数值域大小为 K 且不大时，计数排序复杂度通常是（ ）。

{{ select(21) }}

• O(n+K)
• O(n log n)
• O(n²)
• O(K log n)

22. 坐标离散化的主要作用是（ ）。

{{ select(22) }}

• 改变元素之间的大小关系
• 用较小排名表示大数值，同时保持相对大小关系
• 自动删除所有负数
• 把序列随机打乱

23. 使用 unique 对整个数组去重前，通常应先（ ）。

{{ select(23) }}

• 反转数组
• 清空数组
• 排序
• 二分答案

24. 排序后使用双指针查找两数和，整体复杂度通常是（ ）。

{{ select(24) }}

• O(n)
• O(n log n)
• O(n²)
• O(2^n)

25. 对长度为 n 的数组，标准选择排序的比较次数是（ ）。

{{ select(25) }}

• 与输入顺序完全无关且为 n
• 最好为 O(n)，最坏为 O(n²)
• 基本固定为 n(n-1)/2
• 始终为 0