1. 一个32位无符号整数可以表示的最大值，最接近下列哪个选项?( ) {{ select(1) }}

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

2.在C++中，执行int x=255;cout<((×&(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，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对象必须以‘\0’结尾,且这个结尾符计入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. 一个 8x8 的棋盘，左上角坐标为(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

二、阅读程序(程序输入不超过数组或字符串定义的范围:判断题正确填，错误填x;除特殊说明外，判断题1.5分，选择题3分，共计40分) 第 1 题

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

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

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

• 37
• 42
• 35
• 25

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

• 6
• 252
• 3
• 2

第 2 题

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

• A. j<=i
• B. a[i]-a[j]>k
• c. j<=n
• D. a[j]<a[i]

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

• 34
• 100
• 50
• 33

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

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

第 3 题

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

• A.小于等于n
• B.大于等于0
• C.不一定大于等于1
• D.以上均是

32.如果在16行的循环前加上以下两行：“std::sort(a+1,a+n+1);

std::sort(b+1,b+n+1)”,

则答案会()。 {{ select(32) }}

• A.变大或不变
• B.变小或不变
• C.一定变大
• D.不变

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

• A.求b数组去重后的长度
• B.求b数组的最长上升子序列
• C.求b数组的长度
• D.求b数组的最大值

三、完善程序（单选题，每小题 3 分，共计 30 分） (1)(字符串解码)“行程长度编码”(Run-Length Encoding)是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：

i)如果原始字符串中一个字符连续出现N次(N≥2),在压缩字符串中它被表示为“字符+数字N”。例如，编码“A12”代表12个连续的字符A。

ii)如果原始字符串中一个字符只出现1次，在压缩字符串中它就表示为该宇符本身。例如，编码“B”代表1个字符B。

以下程序实现读取压缩宇符串并输出其原始的、解压后的形式。试补全程序。

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

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

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

• A. count +(z[i]-'0')
• B. count*10+(z[i]-'0')
• C. z[i]-'0’
• D. count + 1

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

• A. count - 1
• B. count
• C. 10
• D.z[i]-'θ’

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

• A. z[i+1]
• B. ch
• C. z.back()
• D.(char)z[i]+1

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

• A. i--
• B.i=i+2
• C. i++
• D.//不执行任何操作

(2)(精明与糊涂)有N个人，分为两类：i)精明人：永远能正确判断其他人是精明还是糊涂：ii)糊涂人：判断不可靠，会给出随机的判断。已知精明人严格占据多数，即如果精明人有k 个，则满足k>N/2。

你只能通过函数query(i,j)让第1个人判断第j个人：返回true表示判断结果为“精明人”;返回false表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心query(i,j)的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

例如，假设有三个人8、1、2。如果0说1是糊涂人，而1也说0是糊涂人，则θ和1至少有一个是糊涂人。程序将同时淘汰0和1。由于三人里至少有两个精明人，我们确定2是精明人。

试补全程序。

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

• 0
• 1
• N
• -1

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

• A. count<0
• B. count == 1
• C. count == 0
• D. query(candidate, i) == false

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

• A. query(candidate, i)== false
• B. query(i, candidate)== true
• C. query(candidate,i)== false && query(i, candidate)== false
• D. query(candidate, i)== false || query(i, candidate)== false

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

• A. count--
• B. break
• C. count++
• D. candidate = i

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

• A. N - 1
• B. count
• C. candidate
• D. 0