CSP-J 2024 初赛模拟

一、单项选择题：本题共 15 小题，每题 2 分，共 30 分。

每题有且仅有一个正确选项。

1. 以下不属于面向对象语言的是：

{{ select(1) }}

• $C++$
• $Java$
• $Python$
• $C 语言$

2. 有 5 个不同的小球，装入 4 个不同的盒内，每盒至少装一个球，共有多少不同的装法。

{{ select(2) }}

• 240
• 480
• 60
• 120

3. 以下哪种数据结构是非线性结构：

{{ select(3) }}

• 队列
• 栈
• 线性表
• 二叉树

4. CPU 是指：

{{ select(4) }}

• 运算器
• 控制器
• 运算器和控制器
• 运算器、控制器和主存

5. 以下不属于解释型语言的是：

{{ select(5) }}

• $java$
• $python$
• $Lua$
• $C 语言$

6. 设输入序列是 1，2，3，……，n，经过栈的作用后输出序列的第一个元素为 n，则输出序列中第 i个输出元素是：

{{ select(6) }}

• n-i
• n-i+1
• n-i-1
• 不能确定

7. 二叉树的第 k 层的节点数最多为：

{{ select(7) }}

• $2^k-1$
• $2^k+1$
• $2^k$
• $2^{k-1}$

8. 设某颗二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树的序列为：

{{ select(8) }}

• BADC
• BCDA
• CDAB
• CBDA

9. 设某完全无向图中有 n 个节点，则该无向完全图中有（ ）条边：

{{ select(9) }}

• n(n-1)/2
• n(n − 1)
• $n^2$
• $n^2-1$

10. 已知集合 S={1,2,3,4,5}，T = {2,4,6,8,10}，则S$\bigcap$T 为

{{ select(10) }}

• 2,4
• 1,2,3,4,5,6,8,10
• {2,4}
• {1,2,3,4,5,6,8,10}

11. 入栈顺序为 1 2 3 4，不可能的出栈顺序是：

{{ select(11) }}

• 4 3 2 1
• 1 3 2 4
• 3 1 2 4
• 1 4 3 2

12. 无向图的邻接矩阵是：（ ）

{{ select(12) }}

• 对称矩阵
• 零矩阵
• 上三角矩阵
• 对角矩阵

13. 在小型和微型计算机中，普遍采用的字符编码是：

{{ select(13) }}

• BCD 码
• ASCII 码
• 海明码
• 机内码

14. 32 位无符号二进制数可以表示的最大数字为：

{{ select(14) }}

• $2^{31}$
• $2^{31}-1$
• $2^{32}$
• $2^{32}-1$

15. 二进制数字 1011.01 的十进制表示为：

{{ select(15) }}

• 11.5
• 11.25
• 11.125
• 11

二、阅读程序（判断题 1.5 分，单选题每题 3 分，共计 40 分。）

阅读程序第一题

01   #include <iostream> 
02   using namespace std; 
03   int main(){ 
04     string s; 
05     cin >> s; 
06     bool flag = true; 
07     for(int i = 0; i < s.size(); i++){ 
08        if(i == 0 && s[i] >= 'a' && s[i] <= 'z'){ 
09          s[i] = s[i] - 'a' + 'A'; 
10        } 
11        if(flag && s[i] == '0') 
12         continue; 
13        else if(s[i] >= '0' && s[i] <= '9'){ 
14         flag = false; 
15      } 
16      cout << s[i]; 
17    } 
18 }

单选题

16. 若输入为 $\text{hello bob}$ ，则输出为

{{ select(16) }}

• $\text{hello bob}$
• $\text{Hello bob}$
• $\text{Hello}$
• $\text{hello}$

---

17. 若输入为 $\text{I'am}$ ，则输出为

{{ select(17) }}

• $\text{i'am}$
• $\text{I'am}$
• $\text{iam}$
• $\text{Iam}$

18. 若输入为 $\text{0123456789}$ ，则输出为

{{ select(18) }}

• $\text{123456789}$
• $\text{0123456789}$
• $\text{0}$
• $\text{以上答案均不对}$

19. 若输入为 $\text{hello007}$ ，则输出为

{{ select(19) }}

• $\text{hello007}$
• $\text{Hello007}$
• $\text{hello7}$
• $\text{Hello7}$

阅读程序第二题（共 15 分）

程序的输入为一个仅包含大写字母的字符串和一个正整数$\text{k}$

01 #include <iostream> 
02 using namespace std; 
03 int vis[100]; 
04 int main(){ 
05     string s; 
06     int k, ans = 0, r = -1, cnt = 0; 
07     cin >> s >> k; 
08     s = s + "a"; 
09     for(int i = 0; i < s.size(); i++){ 
10         while(cnt <= k && r < (int)s.size() - 1){ 
11            r++; 
12            vis[s[r]-'A']++; 
13            if(vis[s[r]-'A'] == 1) cnt++; 
14         } 
15         ans = max(r - i, ans); 
16         vis[s[i]-'A']--; 
17         if(vis[s[i] - 'A'] == 0) cnt--;
18      } 
19     cout << ans << endl; 
20 }

判断题

20. 若删除第 8 行，程序的运行结果可能会发生改变。

{{ select(20) }}

• 正确
• 错误

21. 若删除第 10 行中的 (int) ，程序的运行结果可能会发生改变。

{{ select(21) }}

• 正确
• 错误

22. 程序的输出一定大于 0。 {{ select(22) }}

• 正确
• 错误

23. 输入的字符串的长度不能超过 100，否则有可能会程序崩溃。 {{ select(23) }}

• 正确
• 错误

24. 若输入的字符串包含小写字母，则程序有可能崩溃。 {{ select(24) }}

• 正确
• 错误

25. 若输入的字符串仅包含大写字母，则无论 是 30 还是 40，程序的输出都一定相同。 {{ select(25) }}

• 正确
• 错误

选择题

26. 若输入为 $\text{ZHOUZIGAO 4}$ ，则输出为？

{{ select(26) }}

• 5
• 4
• 3
• 2

27. 该代码的时间复杂度为？ .

{{ select(27) }}

• $O$($n^2$)
• $O$($nlogn$)
• $O$($n$)
• $O$$(n\sqrt{n})$

阅读程序第三题（共 13 分）

01#include <bits/stdc++.h> 
02 using namespace std; 
03 const int maxn = 2e5 + 5; 
04 string str; 
05 int num[30], n; 
06 long long F[maxn]; 
07 long long comb(int n, int m){ 
08      if(m < 0 || m > n) return 0; 
09      return F[n] / F[m] / F[n-m]; 
10 } 
11 long long dfs(int len, int now){ 
12    if(len == n - 1) return 1; 
13    if(len != -1 && now < str[len] - 'A'){ 
14       int need = n - len - 1; 
15       long long tmp = 1; 
16       for(int i = 0; i < 26; i++) 
17          if(num[i]){ 
18             tmp *= comb(need, num[i]); 
19             need -= num[i]; 
20          } 
21        return tmp; 
22     } 
23    long long tmp = 0; 
24    for(int i = 0; i < 26; i++){ 
25      if(i <= str[len+1] - 'A' && num[i]){ 
26        num[i]--; 
27        tmp += dfs(len + 1, i); 
28        num[i]++; 
29        } 
30     } 
31   return tmp; 
32 }
33int main(){ 
34    F[0] = 1; 
35    for(int i = 1; i < maxn; i ++){ 
36       F[i] = F[i-1] * 1ll * i; 
37    } 
38    cin >> str; 
39    n = str.size(); 
40    for(int i = 0; i < n; i++) 
41       num[str[i]-'A']++; 
42       cout << dfs(-1,30); 
43 }

判断题(1.5*4=6)

28. 若删除第 8 行，程序运行结果一定不变。 {{ select(28) }}

• 正确
• 错误

29. 若将第 36 行改为 F[i] = F[i-1] * i，程序运行结果一定不变。 {{ select(29) }}

• 正确
• 错误

30. 若输入的字符串长度大于 24，则程序的运行结果可能为负数。 {{ select(30) }}

• 正确
• 错误

31. 若删除第 34 行，则无论输入什么，输出都为 0。 {{ select(31) }}

• 正确
• 错误

选择题

32. 若输入的字符串为 CCCCCCCCCC (10 个 C)，则输出为？ {{ select(32) }}

• 1
• 10
• 55
• 3628800（10 的阶乘）

33. （4 分）若输入的字符串为 DBDC，则输出为？ {{ select(33) }}

• 2
• 4
• 8
• 24

三、完善程序（单选题，每小题 3 分，共计 30 分）

1.（求众数）给出一个数字n ，接下来给出 n个数字，求这 n个数字中出现次数最多的数字。

提示：先排序数组，使得所有相同的数字在连续的一段。然后统计每一段数字的长度，最长的长度对应的数字即为众数。

01#include <iostream>
02 using namespace std;
03 const int maxn = 1e5 + 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    sort(a + 1, a + 1 + n);
12    int max_time = 0, cnt = 0, ans;
13    for(int i = 1; i <= n; i++){
14      if(**1**){
15         cnt++;
16      }else{
17          if(cnt > max_time){
18            max_time = cnt;
19            **2**;
20          }
21          **3**;
22       }
23     } 
24      if(cnt > max_time)
25         **4**;
26      cout << **5** << endl;
27  }

34. 1 处应填 {{ select(34) }}

• a[i] != a[i-1]
• a[i] == a[i-1]
• a[i] > max_time
• a[i] < max_time

35. 2 处应填 {{ select(35) }}

• ans = max_time
• cnt = 0
• ans = a[i]
• ans = a[i-1]

36. 3 处应填 {{ select(36) }}

• ans = max_time
• cnt = 0
• ans = a[i]
• ans = a[i-1]

37. 4 处应填 {{ select(37) }}

• ans = max_time
• ans = a[i]
• cnt = 1
• ans = a[n]

38. 5 处应填

{{ select(38) }}

• ans
• cnt
• max_time
• a[n]

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

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

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 = **1**, pos; // 确定二分法的上界和下界 
14       while(l <= r){ 
15         int mid = (l + r) / 2; 
16         if(**2**){ 
17           l = mid + 1; 
18           pos = mid; 
19         }else{ 
20           r = mid - 1; 
21          } 
22       } 
23       **3**{ // 向右移动，腾出位置 
24         a[j] = a[j-1]; 
25       } 
26       a[pos] = **4**; 
27     } 
28     for(int i = 1; i <= n; i++) 
29        cout << a[i] << endl; 
30  }

39.1 处应填

{{ select(39) }}

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

40. 2 处应填

{{ select(40) }}

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

41. 3 处应填

{{ select(41) }}

• 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--)

42. 4 处应填

{{ select(42) }}

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

43. 该算法的平均时间复杂度和最坏时间复杂度分别为

{{ select(43) }}

• $O$($n^2$)，$O$($n^2$)
• $O$($nlogn$)，$O$($nlogn$)
• $O$($nlogn$)，$O$($n^2$)
• $O$$(n\sqrt{n})$，$O$($n^2$)