小测试-04月04日
朝外信奥1队 4月4号笔测
答案版
一、单项选择题（共10题）
参考 CSP-J/S 初赛前 15 题风格。每题 3 分，共 30 分。每题有且仅有一个正确选项，绿色选项为正确答案。
1. 在下列各种排序算法中，稳定排序算法是（ ）。
答案：C。归并排序是稳定排序，其余三个在常见实现中都不稳定。
2. 在已经从小到大排好序的长度为 n 的数组中，用二分查找查找某个元素，最坏情况下时间复杂度是（ ）。
答案：B。二分查找每次将查找区间缩小一半。
3. 在下列各种图的存储方式中，更适合存储稀疏图的是（ ）。
答案：B。稀疏图边较少，用邻接表更省空间。
4. 若一个完全二叉树有 2025 个结点，根结点所在层记为第 1 层，则该二叉树的层数是（ ）。
答案：B。因为
2^10-1=1023，2^11-1=2047，所以 2025 个结点需要 11 层。5. 设
A=true, B=false, C=true，则逻辑表达式 (A && B) || (!B && C) 的值是（ ）。答案：A。前半部分为假，后半部分为真，整体为真。
6. 十六进制数
2F 转换成十进制数是（ ）。答案：C。
2F = 2*16 + 15 = 47。7. 对于序列
(7, 4, 1, 9, 3, 6, 8, 5)，其中逆序对 (i,j) 满足 i<j 且 a[i]>a[j]。若删去一个数后逆序对数量减少最多，则删去的数是（ ）。答案：A。数字 7 与后面的 4、1、3、6、5 构成 5 个逆序对，减少最多。
8. 下面关于信息安全与网络道德的做法，正确的是（ ）。
答案：C。
9. 若哈希表地址范围为
0~10，要将 2, 6, 10, 17 存入表中，采用下列哪个哈希函数不会产生冲突（ ）。答案：D。映射结果分别为
1, 2, 3, 4，互不相同。10. 书架上同一格放 5 本不同的书，其中 A 和 B 必须相邻，C 和 D 不能相邻，不同的放法共有（ ）种。
答案：C。把 A、B 看成一个整体，有
4!*2=48 种；再减去其中 C、D 也相邻的情况 3!*2*2=24 种，所以结果为 48-24=24。二、阅读程序（共2题）
参考 CSP-J/S 初赛阅读程序形式。每个阅读程序 5 小题，共 10 题，每题 7 分，共 70 分。绿色选项为正确答案。
阅读程序（1）
01 #include <bits/stdc++.h>
02 using namespace std;
03 char change(char ch) {
04 if (ch >= ‘a’ && ch <= 'z') ch -= 32;
05 return ch;
06 }
07 int main() {
08 string s1, s2;
09 cin >> s1 >> s2;
10 int cnt = 0;
11 for (int i = 0; i < (int)s1.size(); i++) {
12 for (int j = 0; j < (int)s2.size(); j++) {
13 if (change(s1[i]) == change(s2[j])) cnt++;
14 }
15 }
16 cout << cnt;
17 return 0;
18 }
11. 将第 4 行中的
32 替换成字符 ' '，程序运行结果不会改变。答案：对。空格字符
' ' 的 ASCII 码正是 32。12. 若输入数据为
ABCDE AbCdE，则程序输出为 5。答案：对。程序将所有字母转为大写比较，两字符串完全匹配，对应位置各产生 1 次计数。
13. 若输入数据为
aa A，则程序输出为 2。答案：对。s1 中的两个 ‘a’ 都会与 s2 中的 ‘A’ 匹配。
14. 当前程序输出结果是（ ）。
答案：B。输入
ABA aB 时，A 匹配 a (2次)，B 匹配 B (1次)，总共 3。15. 若输入数据为
abca Aa，则程序输出结果是（ ）。答案：C。s1 中的两个 ‘a’ 分别与 s2 中的 ‘A’ 和 ‘a’ 匹配，共 2*2=4。
阅读程序（2）
01 #include <bits/stdc++.h>
02 using namespace std;
03 int nums[8] = {1, 2, 2, 2, 4, 5, 5, 7};
04 int left_bound(int n, int target) {
05 int left = 0, right = n – 1;
06 while (left <= right) {
07 int mid = (left + right) / 2;
08 if (nums[mid] < target) left = mid + 1;
09 else right = mid - 1;
10 }
11 if (left < n && nums[left] == target) return left;
12 return -1;
13 }
14 int right_bound(int n, int target) {
15 int left = 0, right = n - 1;
16 while (left <= right) {
17 int mid = (left + right) / 2;
18 if (nums[mid] <= target) left = mid + 1;
19 else right = mid - 1;
20 }
21 if (right >= 0 && nums[right] == target) return right;
22 return -1;
23 }
24 int main() {
25 int n = 8, target = 2;
26 int l = left_bound(n, target);
27 int r = right_bound(n, target);
28 if (l == -1) cout << 0;
29 else cout << r - l + 1;
30 return 0;
31 }
16. 若数组中不存在目标值，则
left_bound 和 right_bound 都会返回 -1。答案：对。代码中最后都有针对
target 是否相等的检查，不相等则返回 -1。17. 当前程序输出结果为 3。
答案：对。数组中有 3 个 2，程序输出 target 出现的次数。
18. 若将第 25 行改为
int n = 8, target = 5;，则程序输出结果是（ ）。答案：C。数组中有 2 个 5。
19. 若将第 25 行改为
int n = 8, target = 3;，则程序输出结果是（ ）。答案：A。数组中没有 3。
20. 若将第 8 行中的
< 改成 <=，其余不变，则当前程序输出结果是（ ）。答案：A。修改后
left_bound 会变成寻找“大于 target 的第一个位置”，导致无法正确找到左边界。