初赛 DAY 3 客观题（排序算法与二分查找）

题目描述

本题为一套完整的初赛客观题测试，共 46 小题，分为八个部分：排序算法选择题、阅读程序（判断题与选择题）、完善程序（程序填空选择题）。每小题 2 分，共 92 分。

• 判断题：正确选 A，错误选 B。
• 选择题/完善程序：从 A、B、C、D 中选出正确答案。
• 阅读程序与完善程序代码中的行号仅供答题时定位参考。

---

一、排序算法选择题（第 1~5 题）

1. 以下哪个排序是稳定的？{{ select(1) }}

• 计数排序
• 选择排序
• 希尔排序
• 快速排序

2. 以下哪个排序在运行 1/3 时间之后无法获得最大值？{{ select(2) }}

• 选择
• 冒泡
• 都错误
• 插入

3. 以下哪个排序无需进行比较？{{ select(3) }}

• 选择
• 冒泡
• 计数
• 插入

4. 以下哪个选项是错误的？{{ select(4) }}

• 插入排序最好的时间复杂度为 $O(n)$
• 插入排序最坏的时间复杂度为 $O(n^2)$
• 插入排序也可以用于求解逆序对的数量
• 插入排序的原理是将最大值插入到有序序列中

5. 序列 [2,5,6,1,7,3] 进行一趟排序后，以下哪个说法错误？{{ select(5) }}

• 经过一趟选择排序 [1,5,6,2,7,3]
• 经过一趟插入排序 [2,7,5,6,1,3]
• 经过一趟冒泡排序 [2,5,1,6,3,7]
• 经过一趟选择排序 [2,5,6,1,3,7]

---

二、阅读程序：归并排序（第 6~11 题）

阅读下面的程序，完成第 6~11 题：

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int maxn = 500000, INF = 0x3f3f3f3f;
04 int L[maxn / 2 + 2], R[maxn / 2 + 2];
05 void unknown(int a[], int n, int left, int mid, int right) {
06     int n1 = mid - left, n2 = right - mid;
07     for(int i = 0; i < n1; i++)
08         L[i] = a[left + i];
09     for(int i = 0; i < n2; i++)
10         R[i] = a[mid + i];
11     L[n1] = R[n2] = INF;
12     int i = 0, j = 0;
13     for(int k = left; k < right; k++) {
14         if(L[i] <= R[j])
15             a[k] = L[i++];
16         else
17             a[k] = R[j++];
18     }
19 }
20 void unknownsort(int a[], int n, int left, int right) {
21     if(left + 1 < right) {
22         int mid = (left + right) / 2;
23         unknownsort(a, n, left, mid);
24         unknownsort(a, n, mid, right);
25         unknown(a, n, left, mid, right);
26     }
27 }
28 int main() {
29     int a[maxn], n;
30     cin >> n;
31     for(int i = 0; i < n; i++) cin >> a[i];
32     unknownsort(a, n, 0, n);
33     for(int i = 0; i < n; i++) {
34         if(i) cout << " ";
35         cout << a[i];
36     }
37     cout << endl;
38     return 0;
39 }

判断题（正确选 A，错误选 B）

6. 将第 13 行的"<"改为"<="不会改变运行结果。{{ select(6) }}

• 正确
• 错误

7. 将第 21 行的"<"改为"<="不会改变运行结果。{{ select(7) }}

• 正确
• 错误

8. 此类排序方法是高效的，但是不稳定。{{ select(8) }}

• 正确
• 错误

9. 将第 4 行的 2 个"+2"都去掉不会改变运行结果。{{ select(9) }}

• 正确
• 错误

选择题

10. 此题是哪种排序？{{ select(10) }}

• 选择排序
• 桶排序
• 归并排序
• 堆排序

11. 此题用到了（　）思想。{{ select(11) }}

• 动态规划
• 分治
• 冒泡
• 贪心

---

三、阅读程序（一）：二分答案（第 12~17 题）

阅读下面的程序，完成第 12~17 题：

01 #include <iostream>
02 #include <cstdio>
03 #include <algorithm>
04 
05 using namespace std;
06 
07 const int N = 1e5 + 10;
08 int n, s, cnt, ans, res;
09 int a[N], b[N];
10 
11 bool check(int mid) {
12     for (int i = 1; i <= n; i++)
13         b[i] = a[i] + i * mid;
14     sort(b + 1, b + 1 + n);
15     res = 0;
16     for (int i = 1; i <= mid && res <= s; i++)
17         res += b[i];
18     return res <= s;
19 }
20 
21 int main() {
22     scanf("%d%d", &n, &s);
23     for (int i = 1; i <= n; i++)
24         scanf("%d", &a[i]);
25     int l = 0, r = n;
26     while (l <= r) {
27         int mid = (l + r) >> 1;
28         if (check(mid)) cnt = mid, ans = res, l = mid + 1;
29         else r = mid - 1;
30     }
31     printf("%d %d\n", cnt, ans);
32     return 0;
33 }

判断题（正确选 A，错误选 B）

12. 若输入 4 100 1 2 5 6，则程序的输出为 4 54。{{ select(12) }}

• 正确
• 错误

13. 对于任意的输入，cnt 的一个必定合法的取值为 n。{{ select(13) }}

• 正确
• 错误

14. 这个程序的时间复杂度为 $O(n\log n)$。{{ select(14) }}

• 正确
• 错误

选择题

15. 当输入为 3 11 2 3 5 时，程序的输出为（ ）。{{ select(15) }}

• 1 11
• 2 11
• 3 8
• 0 0

16. 代码中 check 函数的作用是什么？（ ）{{ select(16) }}

• 判断当前数组是否有序
• 检查是否能从数组中选出 mid 个数，使得它们的总和小于或等于 s
• 判断数组的所有元素是否大于某个值
• 计算数组元素的平均值

17. 变量 cnt 和 ans 的作用分别是什么？（ ）{{ select(17) }}

• cnt 记录满足条件的最大 mid 值，ans 记录对应的总和
• cnt 记录数组的长度，ans 记录数组中的最大值
• cnt 表示排序后的最小值索引，ans 记录当前结果的最小值
• cnt 表示满足条件的元素个数，ans 记录最终的目标值

---

四、阅读程序（二）：第 k 小乘积（第 18~23 题）

阅读下面的程序，完成第 18~23 题。已知 $k \le n \times m$，保证 n、m 同阶：

01 #include<bits/stdc++.h>
02 using namespace std;
03 int n, m, k, l, r, mid;
04 int check(int g) {
05     int st = 1, ed = m, cnt = 0;
06     while(st <= n && ed >= 1) {
07         if(st * ed > g)
08             ed--;
09         else {
10             cnt += ed;
11             st++;
12         }
13     }
14     return cnt >= k;
15 }
16 int main() {
17     scanf("%d%d%d", &n, &m, &k);
18     l = 1, r = n * m;
19     while(l < r) {
20         mid = (l + r) / 2;
21         if(check(mid)) r = mid;
22         else l = mid + 1;
23     }
24     cout << l << endl;
25     return 0;
26 }

判断题（正确选 A，错误选 B）

18. 每次运行 check 时，第 7 行必定运行 n 次。{{ select(18) }}

• 正确
• 错误

19. 如果保证 m=1，则输出一定为 k。{{ select(19) }}

• 正确
• 错误

20. 若将第 21 行中的 r=mid 改成 r=mid-1，程序输出一定不变。{{ select(20) }}

• 正确
• 错误

21. 第 24 行可以改成 cout<<r<<endl;。{{ select(21) }}

• 正确
• 错误

选择题

22. 该程序的时间复杂度为（ ）。{{ select(22) }}

• $O(n)$
• $O(n\log n)$
• $O(n^2)$
• $O(nk)$

23. 若输入为 2 3 4，则输出为（ ）。{{ select(23) }}

• 1
• 2
• 3
• 6

---

五、阅读程序（三）：最长不下降子序列（第 24~31 题）

阅读下面的程序，完成第 24~31 题。输入的只可能是小写字母：

01 #include<bits/stdc++.h>
02 
03 using namespace std;
04 
05 char last[101], ch;
06 int main(){
07     int n, length = 0;
08     scanf("%d", &n);
09     for(int i = 0; i <= n; i++){
10         cin >> ch;
11         if(ch >= last[length]){
12             last[++length] = ch;
13         } else if(ch < last[1]){
14             last[1] = ch;
15         } else {
16             int l = 1, r = length, mid;
17             while(l < r - 1){
18                 mid = (l + r) / 2;
19                 if(last[mid] <= ch){
20                     l = mid;
21                 } else r = mid;
22             }
23             last[r] = ch;
24         }
25     }
26     printf("%d\n", length);
27     return 0;
28 }

判断题（正确选 A，错误选 B）

24. 要使输出等于 n，输入的所有字符必须满足第 i 个字符 ASCII 整数值小于第 i+1 个字符的 ASCII 整数值（$1 \le i \le n-1$）。{{ select(24) }}

• 正确
• 错误

25. 若输入字符个数超过 101 个，一定会发生数组下标溢出。{{ select(25) }}

• 正确
• 错误

26. 若将第 18 行替换为 mid = l + ((r - l) >> 1)，程序运行结果不会改变。{{ select(26) }}

• 正确
• 错误

27. 程序运行过程中，变量 r 的值可能会等于 n。{{ select(27) }}

• 正确
• 错误

28. 如果第 11 行修改为 ch > last[length]，最终输出的结果可能会有 30。{{ select(28) }}

• 正确
• 错误

单选题

29. 第 23 行 last[r] = ch 最多会运行（ ）次。{{ select(29) }}

• 1
• n-2
• n-1
• n

30. 若输入 n = 100，且第 17 行的 while 循环运行了至少一次，那么输出结果不可能是（ ）。{{ select(30) }}

• 2
• 3
• 98
• 100

31. 若输入数据为 4 b c d a e，则输出是（ ）。{{ select(31) }}

• 4
• 2
• 5
• 3

---

六、完善程序（一）：选择数对（第 32~36 题）

（选择数对） 有 n 个小朋友分别拿着一个数字，现在要求你将小朋友两两配对，要求每对小朋友手上的数字之差大于给定值 k。问最多可以从数组中选出多少对符合条件的小朋友。（每个小朋友最多只能和另外一个小朋友配对，不能脚踏两条船）

输入格式：第一行给出 n，k 分别表示小朋友的个数，以及参数 k。接下来给出 n 个数字，表示每个小朋友手上的数字。($1 \le n, k \le 10^5$)

提示：二分最终的结果，对于二分的结果 mid，在 check 函数中 $O(n)$ 判断能否选出 mid 对小朋友符合要求，最终保留二分的结果。

程序中 ①~⑤ 处为待填空位置，完成第 32~36 题：

01 #include <iostream>
02 #include <algorithm>
03 using namespace std;
04 const int maxn = 1e5 + 5;
05 int a[maxn], n, k;
06 bool check(int mid) { // 要配对 mid 队
07     bool flag = true;
08     for(int i = 1, ①; j <= n; j++, i++) {
09         if(②)
10             flag = false; //不满足要求
11     }
12     return flag;
13 }
14 int main() {
15     cin >> n >> k;
16     for(int i = 1; i <= n; i++)
17         cin >> a[i];
18     int l = ③, r = n, ans;
19     sort(a+1, a+1+n);
20     while(l <= r) {
21         int mid = (l + r) / 2;
22         if(check(mid)) {
23             ④;
24             ans = mid;
25         } else {
26             ⑤;
27         }
28     }
29     cout << ans << endl;
30 }

32. ① 处应该填的代码是（ ）。{{ select(32) }}

• j = 1
• j = n - mid
• j = n - mid + 1
• j = mid

33. ② 处应该填的代码是（ ）。{{ select(33) }}

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

34. ③ 处应该填的代码是（ ）。{{ select(34) }}

• 1
• 0
• n/2
• a[1]

35. ④ 处应该填的代码是（ ）。{{ select(35) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

36. ⑤ 处应该填的代码是（ ）。{{ select(36) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

---

七、完善程序（二）：插入排序（第 37~41 题）

（插入排序） 对一段长度为 n 的数组使用插入排序的算法进行从小到大排序。

提示：插入排序共有 n 轮，第 i 轮时使用二分查找找到第 i 个数字应该插入的位置，然后将 pos 到 i 位置向右移动，再将数字 i 放入 pos 位置。保持数组下标 $1 \sim i$ 的元素有序，继续进行下一轮插入排序。

程序中 ①~⑤ 处为待填空位置，完成第 37~41 题：

01 #include <iostream>
02 using namespace std;
03 const int maxn = 1000 + 5;
04 int a[maxn];
05 int main() {
06     int n;
07     cin >> n;
08     for(int i = 1; i <= n; i++) {
09         cin >> a[i];
10     }
11     for(int i = 1; i <= n; i++) {
12         int temp = a[i];
13         int l = 1, r = ①, pos; // 确定二分法的上界和下界
14         while(l <= r) {
15             int mid = (l + r) / 2;
16             if(②) {
17                 l = mid + 1;
18                 pos = mid;
19             } else {
20                 r = mid - 1;
21             }
22         }
23         ③ { // 向右移动，腾出位置
24             a[j] = a[j-1];
25         }
26         a[pos] = ④;
27     }
28     for(int i = 1; i <= n; i++)
29         cout << a[i] << endl;
30 }

37. ① 处应填（ ）。{{ select(37) }}

• n
• i
• i-1
• i+1

38. ② 处应填（ ）。{{ select(38) }}

• mid <= a[i]
• mid >= a[i]
• a[mid] <= a[i]
• a[mid] >= temp

39. ③ 处应填（ ）。{{ select(39) }}

• for(int j = pos; j <= i-1; j++)
• for(int j = i-1; j >= pos; j--)
• for(int j = pos; j <= i; j++)
• for(int j = i; j >= pos; j--)

40. ④ 处应填（ ）。{{ select(40) }}

• a[i]
• temp
• a[l]
• a[r]

41. 该算法的平均时间复杂度和最坏时间复杂度分别为（ ）。{{ select(41) }}

• $O(n^2)$，$O(n^2)$
• $O(n\log n)$，$O(n\log n)$
• $O(n\log n)$，$O(n^2)$
• $O(n^n)$，$O(n^2)$

---

八、完善程序（三）：切割（第 42~46 题）

（切割） 将一个单调递增的数组从某一位置切成两半，然后交换左半边和右半边。现在给出交换后的数组，多次询问，每次给出一个元素 k，问数组中是否存在该元素。

提示：先使用二分查找，找到切割点，则切割点左边的数组单调递增，右边的数组单调递增，再对半边数组进行二分查找，寻找元素 k。

程序中 ①~⑤ 处为待填空位置，完成第 42~46 题：

01 #include <iostream>
02 using namespace std;
03 const int maxn = 1e5 + 5;
04 int a[maxn];
05 bool binary_search(int l, int r, int k) { // 用于实现二分查找，判断 [l,r] 中是否有 k 出现
06     while(①) {
07         int mid = (l + r) >> 1;
08         if(a[mid] == k) {
09             ②;
10         } else if(a[mid] > k) {
11             r = mid;
12         } else {
13             l = mid;
14         }
15     }
16     return a[l] == k || a[r] == k;
17 }
18 int main() {
19     int n, m, k;
20     cin >> n;
21     for(int i = 1; i <= n; i++) {
22         cin >> a[i];
23     }
24     int L = 1, R = n, pos;
25     while(L <= R) {
26         int mid = (L + R) / 2;
27         if(③) {
28             L = mid + 1;
29             pos = mid;
30         } else {
31             R = mid - 1;
32         }
33     }
34     cin >> m; // 表示共有 m 次询问
35     while(m--) {
36         cin >> k;
37         if(k >= a[1]) {
38             if(④)    cout << "YES" << endl;
39             else    cout << "NO" << endl;
40         } else {
41             if(⑤)    cout << "YES" << endl;
42             else    cout << "NO" << endl;
43         }
44     }
45 }

42. ① 处应填（ ）。{{ select(42) }}

• l <= r
• l < r
• l + 1 < r
• l >= r

43. ② 处应填（ ）。{{ select(43) }}

• break
• return true
• l = mid + 1
• r = mid - 1

44. ③ 处应填（ ）。{{ select(44) }}

• a[mid] > k
• mid > k
• a[mid] >= a[1]
• a[mid] > a[1]

45. ④ 处应填（ ）。{{ select(45) }}

• binary_search(L, R, k)
• binary_search(1, pos+1, k)
• binary_search(L, pos, k)
• binary_search(1, pos, k)

46. ⑤ 处应填（ ）。{{ select(46) }}

• binary_search(pos, R, k)
• binary_search(pos+1, R, k)
• binary_search(pos+1, n, k)
• binary_search(L, R, k)