真题练习

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

可打印纸质练习后拍照上传，也可以基于演算纸完成后拍照上传。除了答案请务必上传解题演算。

一、单项选择题

1. 以下不属于面向对象程序设计语言的是( )。
   • A. C++
   • B. Python
   • C. Java
   • D. C

答案: D、 C
解析:

• C 语言是面向过程的程序设计语言，不是面向对象的程序设计语言。
• 简单举个栗子：盖一座房屋。普通人会想到怎么盖，哪里有柱子，哪里要梁，哪里放桌子等等，面向对象就是把这些柱子、梁、桌子（这些东西就是一个个对象）拿过来拼成一个房屋，很多非计科专业都可以做；至于柱子该怎么建，梁要怎么搭，桌子要怎么做，这就是面向过程，需要编写底层代码，往往都是专业编程人员。
• 面向对象：C++、Python、C#、Java（C#和Java的面向对象程度比C++高）、Photoshop、画图、PPT……大多数含人机交互界面的都是面向对象，特点是所见即所得，选中对象（如）后可以操作或设置属性且立即可以看到效果。其中C++可以做界面，只不过高中竞赛中不涉及，我们主要学习C++中面向过程的部分。Python也有pygame、matplotlib等模块可以加载界面
• 面向过程：C、dos、汇编语言、html语言等，需要专业编程人员从零实现。

2. 以下奖项与计算机领域最相关的是( )。
   • A. 奥斯卡奖
   • B. 图灵奖
   • C. 诺贝尔奖
   • D. 普利策奖

答案: B、图灵奖
解析:

• 图灵奖是计算机领域最高奖项，是计算机界的“诺贝尔奖”，是由计算机协会（ACM）颁发的，每年颁发一次，奖金为 10 万美元。图灵奖是计算机领域最高奖项，是计算机界的“诺贝尔奖”，是由计算机协会（ACM）颁发的，每年颁发一次，奖金为 10 万美元。
• 诺贝尔奖是指根据瑞典化学家诺贝尔于1895年的遗嘱而设立的五个奖项，包括：物理学奖、化学奖、和平奖、生理学或医学奖和文学奖，旨在表彰在物理学、化学、和平、生理学或医学以及文学上“对人类作出最大贡献”的人士；瑞典中央银行1968年设立的诺贝尔经济学奖，用于表彰在经济学领域杰出贡献的人。
• 普利策奖又称普利策新闻奖。是根据美国报业巨头约瑟夫·普利策（Joseph Pulitzer）的遗愿于1917年设立的奖项，后发展成为美国新闻界的最高荣誉奖。
• 菲尔兹奖，是据加拿大数学家约翰·查尔斯·菲尔兹(John Charles Fields)要求设立的国际性数学奖项,于1936年首次颁发。
• 普利兹克奖是建筑领域的国际最高奖项。是由杰伊·普利兹克（Jay A. Pritzker）和妻子辛蒂发起、凯悦基金会所赞助的于1979年设立的建筑奖项。

3. 目前主流的计算机储存数据最终都是转换成( )数据进行储存。
   • A. 二进制
   • B. 十进制
   • C. 八进制
   • D. 十六进制

答案: A、二进制
解析:

• 计算机中的数据都是以二进制形式存储的，二进制是计算机中最基本的数据单位，是计算机中的数据存储和数据传输的基础。

4. 以比较作为基本运算，在 N 个数中找出最大数，最坏情况下所需要的最少的比较次数为( )
   • A. N^2
   • B. N
   • C. N-1
   • D. N+1

答案: C、N-1
解析:

• 在 N 个数中找出最大数，最坏情况下所需要的最少的比较次数为 N-1 次。因为每次比较都可以排除一个数，最后剩下一个最大数。

5. 对于入栈顺序为 a，b，c，d，e 的序列，下列( )不是合法的出栈序列。
   • A. a, b, c, d, e
   • B. e, d, c, b, a
   • C. b, a, c, d, e
   • D. c, d, a, e, b

答案: D、c, d, a, e, b
解析:

• 对于入栈顺序为 a，b，c，d，e 的序列，出栈序列为 a, b, c, d, e 是合法的，因为出栈顺序是入栈顺序的逆序。而 c, d, a, e, b 不是合法的出栈序列，因为 c 在 a 的上面，d 在 a 的上面，e 在 a 的上面，b 在 a 的上面，所以 a 不能在 b 的上面。

6. 二进制数 101.11 对应的十进制数是( )。
   • A. 6.5
   • B. 5.5
   • C. 5.75
   • D. 5.25

答案: C、5.75
解析:

• 二进制数 101.11 对应的十进制数是 5.75。二进制数 101.11 = 12^2 + 02^1 + 12^0 + 12^(-1) + 1*2^(-2) = 5.75。

7. 6 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有( )种。
   • A. 10
   • B. 15
   • C. 30
   • D. 20

答案: B、15
解析:

• 这是一个组合问题，我们需要找出6个人中任意两人组队的不重复情况。我们可以分为三个步骤来解决这个问题：

1. 计算从6个人中选择2个人的方法数。
2. 剩下4个人中选择2个人的方法数。
3. 最后剩下2个人自动组成一队。

• 使用组合公式 $\binom{n}{k}$ 来计算组合数：

$\binom{6}{2} = \frac{6!}{2!(6-2)!} = 15$

• 选择了第一个队伍后，剩下4个人：

$\binom{4}{2} = \frac{4!}{2!(4-2)!} = 6$

• 最后2个人自动组成一队，只能有一种方法。

• 我们得到：

$15 \times 6 \times 1 = 90$

• 但是，由于队伍之间的顺序不重要，我们必须除以所有队伍的排列数，即除以 $3!$：

$\frac{90}{3!} = \frac{90}{6} = 15$

• 因此，6个人组成3队的不同组队情况有 15 种。

8. 在数据压缩编码中的哈夫曼编码方法，在本质上是一种( )的策略。
   • A. 枚举
   • B. 贪心
   • C. 递归
   • D. 动态规划

答案: B、贪心 解析:

• 哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。哈夫曼编码是一种贪心算法，它是一种最优二叉树，用于数据压缩编码。

9. 由 1，1，2，2，3 这五个数字组成不同的三位数有( )种。
   • A. 18
   • B. 15
   • C. 12
   • D. 24

答案: A、18 解析:

• 我们需要计算由数字 1、1、2、2、3 组成不同的三位数的个数。

• 三位数的形式是 ABC，其中 A、B、C 可以是 1、1、2、2、3。

• 考虑以下情况：

1. 所有三个数字都不同：

   • 选择3个不同的数字（1、2、3），其排列数为 3!： 3! = 6

2. 两个数字相同，一个数字不同：

   • 两个1和一个不同数字（2或3）：
     • 选择两个1和一个2，有以下排列： 112, 121, 211 一共有3种排列。
     • 选择两个1和一个3，有以下排列： 113, 131, 311 一共有3种排列。
   • 两个2和一个不同数字（1或3）：
     • 选择两个2和一个1，有以下排列： 221, 212, 122 一共有3种排列。
     • 选择两个2和一个3，有以下排列： 223, 232, 322 一共有3种排列。
   • 两个相同的数字是3（不可能，因为只有一个3）

• 所以共有： 3 + 3 + 3 + 3 = 12

• 将所有情况相加： 6 + 12 = 18

• 因此，由 1，1，2，2，3 这五个数字组成不同的三位数共有 18 种。

10. 以下递归函数 solve(7) 的返回值为( )。

solve(n)
if n <= 1 return 1
else if n >= 5 return n * solve(n-2)
else return n * solve(n-1)

- A. 105
- B. 840
- C. 210
- D. 420

答案: C、210 解析:

• 我们需要计算 solve(7) 的返回值。
• 根据递归函数的定义，我们可以得到以下计算过程：
• solve(7) = 7 * solve(5)
• solve(5) = 5 * solve(3)
• solve(3) = 3 * solve(2)
• solve(2) = 2 * solve(1)
• solve(1) = 1
• 将这些值代入 solve(7) 的计算过程：
• solve(7) = 7 * solve(5) = 7 * (5 * solve(3)) = 7 * (5 * (3 * solve(2))) = 7 * (5 * (3 * (2 * solve(1)))) = 7 * (5 * (3 * (2 * 1))) = 7 * (5 * (3 * 2)) = 7 * (5 * 6) = 7 * 30 = 210

二、阅读程序

题目一

#include <iostream>
using namespace std;

int n;
int a[1000];

int f(int x) {
    int ret = 0;
    for(; x; x &= x-1) ret++;
    return ret;
}

int g(int x) {
    return x & -x;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cout << f(a[i]) + g(a[i]) << ' ';
    cout << endl;
    return 0;
}

解析：

• 这个程序实现了对输入的一组整数进行位操作，并输出每个整数的某种计算结果。具体来说，它对每个整数 a[i]，计算了两个函数 f(a[i]) 和 g(a[i]) 的值，然后将这两个值相加并输出。

1. 全局变量和数组声明：

   int n;
   int a[1000];
   

   这里声明了一个整数 n，表示输入的整数数量，以及一个大小为 1000 的整数数组 a，用于存储输入的整数。

2. 函数 f：

   int f(int x) {
       int ret = 0;
       for(; x; x &= x-1) ret++;
       return ret;
   }
   

   这个函数计算并返回整数 x 的二进制表示中 1 的个数。

   • ret 用于计数 1 的个数。
   • for 循环中的 x &= x-1 每次会将 x 最右边的 1 变成 0，直到 x 变成 0 为止。
   • 每次循环 ret++，最终 ret 就是 x 的二进制表示中 1 的个数。

3. 函数 g：

   int g(int x) {
       return x & -x;
   }
   

   这个函数返回整数 x 的二进制表示中最右边的 1 以及它后面的所有 0 组成的数。

   • x & -x 计算的是 x 的二进制表示中最右边的 1 以及它后面的所有 0 组成的数。例如，如果 x 是 10100（20），则 x & -x 结果是 4。

4. 主函数 main：

   int main() {
       cin >> n;
       for(int i = 0; i < n; i++) cin >> a[i];
       for(int i = 0; i < n; i++) cout << f(a[i]) + g(a[i]) << ' ';
       cout << endl;
       return 0;
   }
   

   • 首先读取整数 n，表示接下来会有 n 个整数输入。
   • 使用 for 循环读取 n 个整数并存入数组 a 中。
   • 再次使用 for 循环遍历数组 a，对每个 a[i] 计算 f(a[i]) + g(a[i]) 并输出，数值之间以空格分隔。
   • 最后输出一个换行符。

示例

假设输入如下：

3
5 8 13

那么：

• 对于 5 (二进制 101):
  • f(5) = 2 (有两个 1)
  • g(5) = 1 (最右边的 1 以及它后面的 0 组成的数是 1)
  • 输出 2 + 1 = 3
• 对于 8 (二进制 1000):
  • f(8) = 1 (有一个 1)
  • g(8) = 8 (最右边的 1 以及它后面的 0 组成的数是 8)
  • 输出 1 + 8 = 9
• 对于 13 (二进制 1101):
  • f(13) = 3 (有三个 1)
  • g(13) = 1 (最右边的 1 以及它后面的 0 组成的数是 1)
  • 输出 3 + 1 = 4

最终输出结果为：

3 9 4

判断题

11. 输入的 n 等于 1001 时，程序不会发生下标越界。( )

• 答案：❌ 错误
• 解析：数组 a 的大小为 1000，当输入的 n 等于 1001 时，会发生下标越界。

12. 输入的 a[i] 必须全为正整数，否则程序将陷入死循环。( )

• 答案：❌ 错误
• 解析：
  • 程序中的 for 循环会一直循环直到 x 变成 0，因此 a[i] 可以是任意整数，不会陷入死循环。
  • 负数在二进制中以补码形式表示，最右边的 1 以及它后面的 0 组成的数仍然是 1，因此程序不会出错。

13. 当输入为“5 2 11 9 16 10”时，输出为“3 4 3 17 5”。( )

• 答案: ❌ 错误
• 解析: 应该输出为“3 4 3 17 4”。10 = ---1010，f(10) = 2, g(10) = 2。2 + 2 = 4。

14. 当输入为“1 511998”时，输出为“18”。( )

• 答案: ✅ 正确
• 解析: 511998 = ---1111100111111111110，f(511998) = 16, g(511998) = 2。16 + 2 = 18。

15. 将源代码中 g 函数的定义(14-17 行)移到 main 函数的后面，程序可以正常编译运行。( )

• 答案: ❌ 错误
• 解析: 函数 g 的定义必须在 main 函数之前，否则编译器会报错。

单选题

16. 当输入为“2 -65536 2147483647”时，输出为( )
    • A. “65532 33”
    • B. “65552 32”
    • C. “65535 34”
    • D. “65554 33”

答案: B、“65552 32” 解析:

• -65536=11111110000000000000000,
• f(-65536)+g(-65536)=65536-655522147483647=011111111111
• f(2147483647)+g(2147483647)=31+1=32