一、单项选择题 （共15题，每题2分，共计30分）

1. 以下哪种数据结构遵循“先进先出”（FIFO）的原则？

A. 栈

B. 队列

C. 二叉树

D. 图

2. 在C++中，表达式 abs(-5) + sqrt(9) + pow(2, 3) 的值是（ ）。

A. 16

B. 15

C. 14

D. 13

3. 将十进制数 255 转换为十六进制数是（ ）。

A. FF

B. EF

C. FE

D. EE

4. 递归函数必须有（ ），否则会造成无限递归。

A. 递归方程

B. 循环语句

C. 边界条件

D. 返回值

5. 对长度为 nn 的数组进行冒泡排序，在最坏情况下需要进行（ ）次交换操作。

A. nn

B. nlog⁡nnlogn

C. n2n2

D. n(n−1)22n(n−1)

6. 定义数组 int arr[5] = {1, 2, 3};，则 arr[4] 的值是（ ）。

A. 0

B. 3

C. 随机值

D. 编译错误

7. 如果一棵二叉树有 10 个度为 2 的结点，则该二叉树的叶子结点数为（ ）。

A. 9

B. 10

C. 11

D. 不确定

8. 在C++中，执行以下代码后，变量 x 和 y 的值分别是（ ）。

int x = 5, y = 10;
x = x + y;
y = x - y;
x = x - y;

A. 5, 10

B. 10, 5

C. 10, 10

D. 5, 5

9. 以下关于C++语言的描述，正确的是（ ）。

A. main 函数可以是空参数

B. 每个源文件都必须有一个 main 函数

C. int 类型变量在内存中占用的字节数是固定的

D. // 既可以用于单行注释，也可以用于多行注释

10. 以下代码的输出结果是（ ）。

int sum = 0;
for (int i = 1; i <= 5; i++) {
    if (i % 2 == 0) continue;
    sum += i;
}
cout << sum;

A. 6

B. 9

C. 15

D. 死循环

11. 将运算符 +, -, *, / 按优先级从高到低排序，正确的是（ ）。

A. *, /, +, -

B. /, *, -, +

C. +, -, *, /

D. *, /, -, +

12. 一个队列的入队序列是 1, 2, 3, 4，则可能的出队序列是（ ）。

A. 4, 3, 2, 1

B. 1, 2, 3, 4

C. 1, 4, 2, 3

D. 3, 2, 4, 1

13. 在C++中，以下不能正确表示字符串的是（ ）。

A. char s[] = "Hello";

B. char s[] = {'H', 'e', 'l', 'l', 'o'};

C. char s[] = {'H', 'e', 'l', 'l', 'o', '\0'};

D. string s = "Hello";

14. 定义 int a = 5, b = 3;，则表达式 (a > b) ? a : b 的值是（ ）。

A. 5

B. 3

C. 1

D. 0

15. 使用动态规划（DP）求解斐波那契数列 F(n)（自底向上），通常需要用到（ ）。

A. 递归和记忆化

B. 深度优先搜索

C. 循环和数组

D. 贪心选择

---

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

（一）

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

判断题

1. 该程序的功能是计算输入整数 n 的所有因子之和。（ ）

2. 若输入 n 为质数，则输出结果一定是 n+1。（ ）

单选题

3. 该程序的时间复杂度是（ ）。

A. O(n)

B. O(n²)

C. O(n log n)

D. O(1)

4. 若输入 n 为 12，则输出是（ ）。

A. 28

B. 16

C. 18

D. 24

（二）

#include <iostream>
using namespace std;

void convert(int n) {
    if (n == 0) return;
    convert(n / 2);
    cout << n % 2;
}

int main() {
    int num;
    cin >> num;
    if (num == 0) {
        cout << 0;
    } else {
        convert(num);
    }
    return 0;
}

判断题

1. 该程序的功能是将输入的十进制非负整数转换为二进制数并输出。（ ）

2. 若输入 num 为 10，则程序输出为 1010。（ ） 单选题

3. 函数 convert 的调用过程体现了（ ）的算法思想。

A. 动态规划

B. 分治

C. 递归

D. 迭代

4. 若输入 num 为 0，程序输出为（ ）。

A. 空（无输出）

B. 0

C. 00

D. 程序出错

（三）

#include <iostream>
using namespace std;

const int N = 100;
int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
            }
        }
    }
    
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

判断题

1. 该程序实现了一种不稳定的排序算法。（ ）

2. 若输入数据已经是有序的，则程序中的 swap 操作一次都不会执行。（ ）

单选题 3. 该程序使用的排序算法是（ ）。

A. 选择排序

B. 插入排序

C. 冒泡排序

D. 归并排序

4. 该算法的最好情况时间复杂度是（ ）。

A. O(n)

B. O(n²)

C. O(n log n)

D. O(1)

---

三、完善程序 （共2题，每题15分，共计30分） （一）（质数判断）

题目描述：输入一个正整数 n，判断它是否为质数（素数）。如果是，输出 "Yes"，否则输出 "No"。

输入样例1：7

输出样例1：Yes

输入样例2：9

输出样例2：No

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n <= 1) {
        cout << "No" << endl;
        return 0;
    }
    if (n == 2) {
        cout << "Yes" << endl;
        return 0;
    }
    bool is_prime = true;
    for (int i = 2; i <= ①; i++) { // ① 循环边界
        if (②) {                   // ② 判断条件
            is_prime = false;
            break;
        }
    }
    if (③) {                       // ③ 输出判断
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

1. ①处应填（ ）

A. n

B. n / 2

C. sqrt(n)

D. n - 1

2. ②处应填（ ）

A. n % i == 0

B. n % i != 0

C. n / i == 0

D. n / i != 0

3. ③处应填（ ）

A. n > 1

B. is_prime

C. is_prime == true

D. B 或 C 均可

（二）（走迷宫方案数） 题目描述：一个机器人位于一个 n x m 网格的左上角，它每次只能向下或者向右移动一步。它试图到达网格的右下角。问总共有多少条不同的路径？

输入：两个整数 n 和 m (1 ≤ n, m ≤ 10)

输出：路径数目

输入样例：3 2

输出样例：3

方法提示：使用动态规划（DP），dp[i][j] 表示从 (0,0) 走到 (i,j) 的路径数。状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int dp[15][15] = {0}; // 初始化一个比输入范围稍大的数组，并初始化为0

    // 初始化第一行和第一列
    for (int i = 0; i < n; i++) dp[i][0] = 1;
    for (int j = 0; j < m; j++) dp[0][j] = 1;

    // 动态规划过程
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = ④; // ④ 状态转移
        }
    }
    cout << ⑤ << endl; // ⑤ 输出结果
    return 0;
}

4. ④处应填（ ）

A. dp[i-1][j] + dp[i][j-1]

B. dp[i+1][j] + dp[i][j+1]

C. dp[i-1][j-1] + dp[i][j]

D. dp[i][j] + 1

5. ⑤处应填（ ）

A. dp[0][0]

B. dp[n][m]

C. dp[n-1][m-1]

D. dp[m-1][n-1] 阿弥陀佛，法海祝你圆满