一、单项选择题(共15题，每题2分，共计30分;每题有且仅有一个正确选项)

1. 在 C++ 中，下面哪个关键字用于声明一个变量， 其值不能被修改? {{ select(1) }}

• unsigned
• const
• static
• mutable

2. 八进制数$(12345670)_8$和$(07654321)_8$的和为 {{ select(2) }}

• $(22222221)_8$
• $(21111111)_8$
• $(22111111)_8$
• $(22222211)_8$

3. 阅读下述代码，请问修改 data 的 value 成员以存储 3.14，正确的方式是

union Data{
    int num;
    float value;
    char symbol;
};
union Data data;

{{ select(3) }}

• data.value = 3.14;
• value.data = 3.14;
• data -> value = 3.14;
• value->data = 3.14;

4. 假设有一个链表的节点定义如下：

struct Node { int data; Node* next; }

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员 data 的值为 42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？ {{ select(4) }}

• Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
• Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
• Node* newNode = new Node; newNode->data = 42; head->next = newNode;
• Node* newNode = new Node; newNode->data = 42; newNode->next = head;

5. 根节点的高度为1，一 棵拥有2023个节点的三叉树高度至少为（）。 {{ select(5) }}

• 6
• 7
• 8
• 9

6. 小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有（）种选择时间段的方案。 {{ select(6) }}

• 31
• 18
• 21
• 33

7. 以下关于高精度运算的说法错误的是() {{ select(7) }}

• 高精度计算主要是用来处理大整数或需要保留多位小数的运算
• 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
• 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
• 高精度加法运算的关键在于逐位相加并处理进位

8. 后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是 （）。

   {{ select(8) }}

• ((6-(2+3))*(3+8/2))^2+3
• 6-2+3*3+8/2^2+3
• (6-(2+3))*((3+8/2)^2)+3
• 6-((2+3)*(3+8/2))^2+3

9. 数$(101010)_2$和$(166)_8$的 和 为 ( ) {{ select(9) }}

• $(10110000)_2$
• $(236)_8$
• $(158)_{10}$
• $(A0)_{16}$

10. 假 设 有 一 组 字 符 {a,b,c,d,e,f}, 对应的频率分别为5%、9%、12%、13%、16%、45%。请 问 以 下 哪 个 选 项 是 字 符 a,b,c,d,e,f 分 别 对 应 的 一 组 哈 夫 曼 编 码 ? {{ select(10) }}

• 1111,1110,101,100,110,0
• 1010,1001,1000,011,010,00
• 000,001,010,011,10,11
• 1010,1011,110,111,00,01

11. 给 定 一 棵 二 叉 树 ， 其 前 序 遍 历 结 果 为 ：ABDECFG, 中 序 遍 历 结 果 为 ：DEBACFG。 请 问 这 棵 树 的 正 确 后 序 遍 历 结 果 是 什 么 ? {{ select(11) }}

• EDBGFCA
• EDBGCFA
• DEBGFCA
• DBEGFCA

12. 考 虑 一 个 有 向 无 环 图 ， 该 图 包 含 4 条 有 向 边 ： ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 4 ) 和 ( 3 , 4 ) 。 以 下 哪 个

选 项 是 这 个 有 向 无 环 图 的 一 个 有 效 的 拓 扑 排 序 ? {{ select(12) }}

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

13.在计算机中，以下哪个选项描述的数据存储容量最小（） {{ select(13) }}

• 字节 (byte)
• 比特 (bit)
• 字 (word)
• 千字节 (kilobyte）

14. 一 个 班 级 有 1 0 个 男 生 和 1 2 个 女 生 。 如 果 要 选 出 一 个 3 人 的 小 组 ， 并 且 小 组 中 必 须 至 少 包含 1 个 女 生 ， 那 么 有 多 少 种 可 能 的 组 合 ? ( ) {{ select(14) }}

• 1420
• 1770
• 1540
• 2200

15. 以下哪个不是操作系统 ? ( ) {{ select(15) }}

• Linux
• Windows
• Android
• HTML

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题 1.5 分，选择题 3分，共计 40分）

1.

1   #include<iostream>
2  #include<cmath>
3  using namespace std;
4  
5  double f(double a,double b,double c){
6      double s=(a+b+c)/2;
7      return sqrt(s*(s-a)*(s-b)*(s-c));
8  }
9  int main(){
10   cout.flags(ios::fixed);
11   cout.precision(4);
12   
13   int a,b,c;
14   cin>>a>>b>>c;
15   cout<<f(a,b,c)<<endl;
16   return 0;
17 }

假设输入的所有数都为不超过1000的正整数，完成下面的判断题和单选题：

• 判断题

16. 当输入为“2 2 2”时，输出为“1.7321”（ ） {{ select(16) }}

• 正确
• 错误

17. 将第7行中的（s-b）*（s-c）改为（s-c）*（s-b）不会影响程序运行的结果（ ） {{ select(17) }}

• 正确
• 错误

18. 程序总是输出四位小数（ ） {{ select(18) }}

• 正确
• 错误

• 选择题

19. 当输入为“3 4 5”时，输出为（ ） {{ select(19) }}

• 6.0000
• 12.0000
• 24.0000
• 30.0000

20. 当输入为“5 12 13”时，输出为（ ） {{ select(20) }}

• 24.0000
• 30.0000
• 60.0000
• 120.0000

2.

1  #include<iostream>
2  #include<vector>
3  #include<algorithm>
4  using namespace std;
5  int f(string x,string y){
6     int m=x.size();
7     int n=y.size();
8     vector<vector<int>>v(m+1,vector<int>(n+1,0));
9     for(int i=1;i<=m;i++){
10        for(int j=1;j<=n;j++){
11             if(x[i-1]==y[j-1]){
12                 v[i][j]=v[i-1][j-1]+1;
13             }else{
14                 v[i][j]=max(v[i-1][j],v[i][j-1]);
15             }
16         }
17     }
18     return v[m][n];
19 }
20 bool g(string x,string y){
21     if(x.size() != y.size()){
22         return false;
23     }
24     return f(x+x,y)==y.size();
25 }
26 int main(){
27     string x,y;
28     cin>>x>>y;
29     cout<<g(x,y)<<endl;
30     return 0;
31 }

• 判断题

21. 函数的返回值小于等于 min⁡{𝑛,𝑚}。 {{ select(21) }}

• 正确
• 错误

22. f函数的返回值等于两个输入字符串的最长公共子串的长度。（） {{ select(22) }}

• 正确
• 错误

23. 当输入两个完全相同的字符串时，g 函数的返回值总是 true。（） {{ select(23) }}

• 正确
• 错误

24. 将第19行中的v[m][n]替换为v[n][m]，那么该程序（）。 {{ select(24) }}

• 行为不变
• 只会改变输出
• 一定非正常退出
• 可能非正常退出

25. 当输入为“csp-j p-jcs”时，输出为（）。 {{ select(25) }}

• 0
• 1
• T
• F

26. 当输入为“csppsc spsccp”时，输出为（）。 {{ select(26) }}

• T
• F
• 0
• 1

3.

1  #include <iostream>
2  #include <cmath>
3  using namespace std;
4
5  int solve1(int n){
6      return n*n;
7 }
8
9  int solve2(int n){
10    int sum=0;
11    for(int i=1;i<=sqrt(n);i++){
12         if(n%i==0){
13             if(n/i==i){
14                 sum+=i*i;
15             }else{
16                 sum+=i*i+(n/i)*(n/i);
17             }
18         }
19     }
20     return sum;
21 }
22 int main(){
23     int n;
24     cin>>n;
25     cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
26     return 0;
27 }

假设输入的$𝑛$是绝对值不超过1000的整数，完成下面的判断题和单选题。

• 判断题

27. 如果输入的$𝑛$为正整数，solve2函数的作用是计算$𝑛$所有的因子的平方和（ ） {{ select(27) }}

• 正确
• 错误

28. 第13~14行的作用是避免$𝑛$的平方根因子$𝑖$（或$𝑛/𝑖$）进入第16行而被计算两次（ ） {{ select(28) }}

• 正确
• 错误

29. 如果输入的$𝑛$为质数，solve2（n）的返回值为$𝑛^2+1$（ ） {{ select(29) }}

• 正确
• 错误

• 选择题

30. (4分)如果输入的$𝑛$为质数$𝑝$的平方，那么solve2（n）的返回值为（ ） {{ select(30) }}

• $𝑝^2+𝑝+1$
• $n^2+n+1$
• $n^2+1$
• $p^4+2p^2+1$

31. 当输入为正整数时，第一项减去第二项的差值一定（ ） {{ select(31) }}

• 大于0
• 大于等于0且不一定大于0
• 小于0
• 小于等于0且不一定小于0

32. 当输入为“5”时，输出为（ ） {{ select(32) }}

• 651.625
• 650.729
• 651.676
• 652.625

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

1. (寻找被移除的元素)问题: 原有长度为 𝑛+1公差为 1 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $𝑛$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4  int find_missing(vector<int>& nums) {
5      int left = 0, right = nums.size() - 1;
6      while (left < right){
7          int mid = left + (right - left) / 2;
8          if (nums[mid] == mid + ①) {
9              ②;
10         } else {
11             ③;
12         }
13     }
14     return ④;
15 }
16 int main() {
17     int n;
18     cin >> n;
19     vector<int> nums(n);
20     for (int i = 0; i < n; i++) cin >> nums[i];
21     int missing_number = find_missing(nums);
22     if (missing_number == ⑤) {
23         cout << "Sequence is consecutive" << endl;
24     }else{
25         cout << "Missing number is " << missing_number << endl;
26     }
27     return 0;
28 }

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

• 1
• nums[0]
• right
• left

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

• left=mid+1
• right=mid-1
• right=mid
• left=mid

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

• left=mid+1
• right=mid-1
• right=mid
• left=mid

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

• left+nums[0]
• right+nums[0]
• mid+nums[0]
• right+1

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

• nums[0]+n
• nums[0]+n-1
• nums[0]+n+1
• nums[n-1]

2.（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace），一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

试补全程序。

1  #include <iostream>
2  #include <string>
3  #include <vector>
4  using namespace std;
5  int min(int x, int y, int z) {
6      return min(min(x, y), z);
7  }
8  int edit_dist_dp(string str1, string str2) {
9      int m = str1.length();
10     int n = str2.length();
11     vector<vector<int>> dp(m + 1, vector<int>(n + 1));
12     for (int i = 0; i <= m; i++) {
13         for (int j = 0; j <= n; j++) {
14             if (i == 0)
15                 dp[i][j] = ①;
16             else if (j == 0)
17                 dp[i][j] = ②;
18             else if (③)
19                 dp[i][j] = ④;
20             else
21                 dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤);
22         }
23     }
24     return dp[m][n];
25 }
26 int main() {
27     string str1, str2;
28     cin >> str1 >> str2;
29     cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl;
30     return 0;
31 }

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

• j
• i
• m
• n

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

• j
• i
• m
• n

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

• str1[i-1]==str2[j-1]
• str1[i]==str2[j]
• str1[i-1]!=str2[j-1]
• str1[i]!=str2[j]

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

• dp[i-1][j-1]+1
• dp[i-1][j-1]
• dp[i-1][j]
• dp[i][j-1]

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

• dp[i][j] + 1
• dp[i-1][j-1]+1
• dp[i-1][j-1]
• dp[i][j]