一、单项选择题

（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

第 1 题

一个32位无符号整数可以表示的最大值， 最接近下列哪个选项？（ ）

{{ select(1) }}

• 4 X $10^9$
• 3 X $10^{10}$
• 2 X $10^9$
• 2 X $10^{10}$

第 2 题 在C++中，执行int x = 255; cout « (x & (x - 1)）；后， 输出的结果是？（ ）

{{ select(2) }}

• 255
• 254
• 128
• 0

第 3 题 函数calc(n)的定义如下， 则calc(5)的返回值是多少？ （ ）

int calc(int n) {
    if (n <= 1) return 1; 
    if(n % 2 == 0) return calc(n / 2) + 1; 
    else return calc(n - 1) + calc(n - 2); 
}

{{ select(3) }}

• 5
• 6
• 7
• 8

第 4 题 用5个权值10, 12, 15, 20, 25构造哈夫曼树， 该树的带权路径长度是多少？( )

{{ select(4) }}

• 176
• 186
• 196
• 206

第 5 题 在一个有向图中， 所有顶点的入度之和等于所有顶点的出度之和， 这个总和等于？（ ）

{{ select(5) }}

• 顶点数
• 边数
• 顶点数＋边数
• 顶点数*2

第 6 题 从5位男生和4位女生中选出4人组成一个学习小组， 要求学习小组中男生和女生都有。有多少种不同的选举方法？（ ）

{{ select(6) }}

• 126
• 121
• 120
• 100

第 7 题 假设a, b, c都是布尔变量， 逻辑表达式(a && b) || (!c && a) 的值与下列哪个表达式不始终相等？( ) {{ select(7) }}

• a && (b || !c)
• (a || !c) && (b || !c) && (a || a)
• a && (!b || c)
• !(!a || !b) || (a && !c)

第 8 题 已知f[0]=1, f[1]=1，并且对于所有n>=2有f[n]=(f[n-1]+f[n-2])%7，那么f[2025]的值是多少？（ ） {{ select(8) }}

• 2
• 4
• 5
• 6

第 9 题 下列关于C++ string 类的说法，正确的是？( ) {{ select(9) }}

• string对象的长度在创处后不能改变。
• 可以使用＋运算符直接连接一个string对象和一个char类型的字符。
• string的length()和size()方法返回的值可能不同。
• string对象必须以'\O'结尾，且这个结尾符计入length()。

第 10 题 考虑以下C++函数：

void solve (int &a, int b) { 
    a=a+b; 
    b=a-b; 
    a=a-b; 
}
int main() { 
    int x=5, y=10; 
    solve (x,y); 
}

在main函数调用solve后，x和y的值分别是？ （ ） {{ select(10) }}

• 5,10
• 10,5
• 10,10
• 5,5

第 11 题 一个8 X 8的棋盘，左上角坐标为(1,1)，右下角为(8,8)。一个机器人从(1,1)出发，每次只能向右或向下走一格。要到达(4,5)，有多少种不同的路径？ （ ） {{ select(11) }}

• 20
• 35
• 56
• 70

第 12 题 某同学用冒泡排序对数组{6, 1, 5, 2, 4}进行升序排序，请问需要进行多少次元素交换？（ ） {{ select(12) }}

• 5
• 6
• 7
• 8

第 13 题 十进制数$720_{10}$ 和八进制数$270_8$的和用十六进制表示是多少？( ) {{ select(13) }}

• $388_{16}$
• $3DE_{16}$
• $288_{16}$
• $990_{16}$

第 14 题 一棵包含1000个结点的完全二叉树，其叶子结点的数量是多少？( ) {{ select(14) }}

• 499
• 512
• 500
• 501

第 15 题 给定一个初始为空的整数栈S和一个空的队列P。我们按顺序处理输入的整数队列A:7, 5, 8, 3, 1, 4, 2。对于队列A中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈S；如果该数是偶数，且栈S非空，则弹出一个栈顶元素，并加入到队列P的末尾；如果该数是偶数，且栈S为空，则不进行任何操作。当队列A中的所有数都处理完毕后，队列P的内容是什么？( ) {{ select(15) }}

• 5,1,3
• 7,5,3
• 3,1,5
• 5,1,3,7

二、阅读程序

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

阅读程序（一）

1  #include <algorithm> 
2  #include <cstdio> 
3  #include <cstring> 
4  inline int gcd(int a, int b) {
5      if (b == 0) 
6          return a; 
7      return gcd(b, a % b); 
8  } 
9  int main() { 
10     int n;
11     scanf("%d",&n);
12     int ans=0;
13     for(int i=1;i<=n;++i){
14         for(int j=i+1;j<=n;++j){
15             for(int k=j+1;k<=n;++k){
16                 if(gcd(i,j)==1 && gcd(j,k)==1 && 
17                      gcd(i,k)==1){
18                     ++ans;
19                 }
20             }
21         }
22     }
23 printf("%d\n",ans);
24 return 0;
25 }

判断题：

16. (1分）当输入为2时，程序并不会执行第16行的判断语句。（ ） {{ select(16) }}

• 正确
• 错误

17. 将第16行中的 “ &&gcd(i,k)==1"删去不会影响程序运行结果。（ ） {{ select(17) }}

• 正确
• 错误

18. 当输入的n>=3的时候，程序总是输出一个正整数。（ ） {{ select(18) }}

• 正确
• 错误

单选题：

19. 将第7行的 “gcd(b,a%b)”,改为 “gcd(a,a%b)”后，程序可能出现的问题是（ ）。 {{ select(19) }}

• 输出的答案大于原答案。
• 输出的答案小于原答案。
• 程序有可能陷入死循环。
• 可能发生整型溢出问题。

20. 当输入为8的时候，输出为（ ）。 {{ select(20) }}

• 37
• 42
• 35
• 25

21. 调用gcd(36,42)会返回（ ）。 {{ select(21) }}

• 6
• 252
• 3
• 2

阅读程序（二）

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #define ll long long
5  int n, k;
6  int a[200007];
7  int ans[200007];
8  int main(){
9      scanf ("%d%d", &n, &k); 
10     for (int i = 1; i <= n;++i) {
11         scanf("%d", &a[i]);
12     }
13     std::sort(a + 1, a + n + 1); 
14     n = std::unique(a + 1, a+ n + 1) - a - 1;
15     for (int i = 1, j = 0; i <= n; ++ i) { 
16         for (; j < i && a [ i] -a [ j + 1] > k; ++ j)
17         ;
18         ans[i] = ans[j] + 1;
19     }
20     printf("%d\n", ans[n]);
21     return 0;
22 }

判断题：

22. 当输入为 “3 1 3 2 1”时，输出结果为2（ ）。 {{ select(22) }}

• 正确
• 错误

23. 假设输入的n为正整数，输出的答案一定小于等于n,大于等于1（ ）。 {{ select(23) }}

• 正确
• 错误

24. 将第14行的"n=std::unique(a+1, a+n+1)-a-1;"删去后，有可能出现与原本代码不同的输出结果（ ）。 {{ select(24) }}

• 正确
• 错误

单选题：

25. 假设输入的a数组和k均为正整数，执行第18行代码时，一定满足的条件不包括（ ）。 {{ select(25) }}

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

26. 当输入的n=100、k=2、a={l,2,...,100}时，输出为( )。 {{ select(26) }}

• 34
• 100
• 50
• 33

27. 假设输入的a数组和k均为正整数，但a数组不一定有序，则若误删去第13行的" std::sort (a+1, a+n+1); "，程序有可能出现的问题有（ ）。 {{ select(27) }}

• 输出的答案比原本答案更大
• 输出的答案比原本答案更小
• 出现死循环行为
• 以上均可能发生

阅读程序（三）

1  #include <algorithm> 
2  #include <cstdio> 
3  #include <cstring> 
4  #define ll long long 
5  int f[5007][5007]; 
6  int a[5007], b[5007]; 
7  int n; 
8  int main() { 
9      scanf("%d", &n); 
10     for (int i = 1; i <= n;++i) {
11         scanf("%d", &a[i]); 
12     }
13     for (int i = 1; i <= n;++i) {
14         scanf("%d", &b[i]); 
15     }
16     for (int i = 1; i <= n;++i) { 
17         for (int j = 1; j < = n; ++ j) { 
18             f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1])); 
19             if (a[i] == b[j]) { 
20                 f[i][j] = std::max(f[i][j], f[i - 1][j -1] + 1); 
21             }
22         }
23     }
24     printf("%d\n", f[n][n]); 
25     return 0;
26 }

判断题：

28. 当输入 “4 1 2 3 4 1 3 2 2"时，输出为2。（ ） {{ select(28) }}

• 正确
• 错误

29. 当程序运行完毕后，对于所有的1<=i,j<=n,都一定有f[i][j]<=f[n][n]。（ ） {{ select(29) }}

• 正确
• 错误

30. 将第18行的"f[i][j]=std::max(f[i][j],std::max(f[i-1][j],f[i][j-1]));"删去后，并不影响程序运行结果。 （ ） {{ select(30) }}

• 正确
• 错误

单选题：

31. 输出的答案满足的性质有( )。 {{ select(31) }}

• 小于等于n
• 大于等于0
• 不一定大于等于1
• 以上均是

32. 如果在16行的循环前加上以下两行："std::sort(a+1,a+n+1); std::sort (b+1, b+n+1)",则答案会（ ）。 {{ select(32) }}

• 变大或不变
• 变小或不变
• 一定变大
• 不变

33. 如果输入的a={l,2,..., n}，而且b数组中数字均为1~n中的正整数，则上述代码等价于下面哪个问题： （ ）。 {{ select(33) }}

• 求b数组去重后的长度
• 求b数组的最长上升子序列
• 求b数组的长度
• 求b数组的最大值

三、完善程序

（单选题，每小题 3 分，共计 30 分）

完善程序(一)

1. (字符串解码) “行程长度编码 ” (Run-Length Encoding)是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则 如下：i)如果原始字符串中一个字符连续出现N次(N>=2)，在压缩字符串中它被表示为”字符＋数字N"。例如，编码 "A12"代表12个连续的字符A。ii)如果原始字符串中一个字符只出现1次，在压缩字符串中它就表示为该字符本身。例如，编码 "B"代表1个字符B。 以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

1  #include <cctype> 
2  #include <iostream> 
3  #include <string> 
4  using namespace std; 
5
6  int main() { 
7      string z; 
8      cin >> z; 
9      string  s = "";
10
11     for (int i = 0; i < z.length(); ) {
12         char ch = z[i];
13
14         if ( ____(1)____ && isdigit(z[i + 1])) {
15             i++; 
16             int count = 0; 
17             while (i < z.length() && isdigit(z[i])) {
18                 count = ____(2)____; 
19                 i++;
20             } 
21             for (int j = 0; j <＿＿＿(3)＿＿; ++j) {
22                s+=ch;
23            }
24        } else {
25                   s+=____(4)____; 
26                   ____(5)____;
27        }
28    }
29
30    cout << s << endl; 
31    return 0; 
32 }

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

• i < z.length()
• i - 1 >= 0
• i + 1 < z.length()
• isdigit(z[i])

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

• count + (z[i] - '0')
• count * 10 + (z[i] - '0')
• z[i] - '0'
• count + 1

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

• count - 1
• count
• 10
• z[i] - '0'

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

• z[i+1]
• ch
• z.back()
• (char)z[i] + 1

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

• i--
• i = i + 2
• i++
• //不执行任何操作

完善程序(二)

2.（精明与糊涂）有N个人，分为两类：i)精明人：永远能正确判断其他人是精明还是糊涂；ii)糊涂人：判断不可靠，会给出随机的判断。已知精明人严格占据多数，即如果精明入有k个，则满足k > N/2。 你只能通过函数query(i,j)让第i个人判断第j个人：返回true表示判断结果为 “精 明人” ；返回false表示判断结果为 ＂糊涂人＂ 。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心query(i,j)的内部实现。 以下程序利用 “精明人占多数” 的优势。设想一个 “消除＂的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。 例如，假设有三个人0、1、2。如果0说1 是糊涂人，而1也说0是糊涂人，则0和1至少有一个是糊涂人。程序将同时淘汰0和1。由于三人里至少有两个精明人，我们确定2是精明人。 试补全程序。

01 #include <iostream> 
02 #include <vector> 
03 using namespace std; 
04 
05 int N; 
06 bool query(int i, int j); 
07 
08 int main() { 
09     cin >> N; 
10
11     int candidate = 0; 
12     int count =____(1)____;
13
14     for (int i = 1; i < N; ++i) { 
15         if (____(2)____) {
16             candidate = i;
17             count = 1; 
18         } else { 
19             if (____(3)____) {
20                 ____(4)____;
21             } else { 
22                    count++; 
23             }
24        }
25    }
26    cout << ____(5)____ << endl;
27    return 0;
28 }

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

• 0
• 1
• N
• -1

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

• count < 0
• count == 1
• count == 0
• query(candidate, i) == false

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

• query(candidate, i) == false
• query(i, candidate) == true
• query(candidate, i) == false && query(i, candidate) == false
• query(candidate, i) == false || query(i, candidate) == false

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

• count--
• break
• count++
• candidate = i

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

• N - 1
• count
• candidate
• 0