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

在C++中，用于动态分配单个整型内存空间的正确关键字和语句是（ ）。

A. int p = new int;

B. int* p = new int;

C. int p = new int;

D. int p = new int*;

一个完整的二叉树有2025个节点，那么它的高度是（ ）。（根节点高度为1）

A. 10

B. 11

C. 12

D. 13

后缀表达式 6 5 2 3 + 8 * + 3 + * 的值是（ ）。

A. 192

B. 288

C. 144

D. 200

有向图G的邻接矩阵如下所示，请问节点0的出度和入度分别是（ ）。

[0, 1, 1, 0]

[0, 0, 1, 1]

[0, 0, 0, 1]

[0, 0, 0, 0]

A. 出度：2，入度：0

B. 出度：0，入度：2

C. 出度：1，入度：1

D. 出度：2，入度：1

将{5, 2, 7, 3, 4, 1, 6}依次插入一个初始为空的大顶堆（Max Heap）中，最终堆中序列可能是（ ）。

A. {7, 5, 6, 2, 4, 1, 3}

B. {7, 5, 6, 3, 4, 1, 2}

C. {7, 6, 5, 4, 3, 2, 1}

D. {7, 5, 4, 6, 3, 2, 1}

在C++中，执行以下代码后，变量x的值是（ ）。

int x = 10;
int& y = x;
y = 20;
int z = 30;
y = z;
z = 40;

A. 10

B. 20

C. 30

D. 40

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

A. n

B. n-1

C. n(n-1)/2

D. n²

前缀表达式 + * 2 3 4 等价的中缀表达式是（ ）。

A. 2 * 3 + 4

B. (2 * 3) + 4

C. 2 * (3 + 4)

D. + * 2 3 4

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

A. 4, 3, 2, 1

B. 1, 4, 2, 3

C. 1, 2, 3, 4

D. 3, 2, 4, 1

定义int a[5][6];，请问a[2][4]是数组中的第几个元素（假设按行优先存储）？（ ）

A. 第16个

B. 第17个

C. 第18个

D. 第19个

十进制数100.625对应的十六进制表示是（ ）。

A. 64.A

B. 3E.A

C. 64.5

D. 3E.5

一棵二叉树的中序遍历序列是DBEAFGC，后序遍历序列是DEBGFCA，则其前序遍历序列是（ ）。

A. ABCDEFG

B. ABDECFG

C. ABEDCGF

D. ABDECGF

在C++中，关于STL容器vector，以下说法错误的是（ ）。

A. 可以使用[]运算符随机访问元素

B. 在尾部插入元素的时间复杂度是O(1)

C. 在中间插入元素可能会导致所有迭代器失效

D. 其存储空间必须是连续的

有6个元素{1, 2, 3, 4, 5, 6}依次入栈，下列哪个不是合法的出栈序列？（ ）

A. 3, 2, 5, 6, 4, 1

B. 1, 5, 4, 6, 3, 2

C. 4, 5, 3, 6, 2, 1

D. 2, 3, 4, 1, 5, 6

使用深度优先搜索（DFS）遍历一个具有n个顶点、e条边的图，所需的最大空间复杂度（主要考虑栈空间）为（ ）。

A. O(n)

B. O(e)

C. O(n log n)

D. O(n²)

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

程序一

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

判断题

16. 该程序的功能是统计输入字符串中大写元音字母的个数。（ ）
18. 若输入字符串为"Hello World!"，则程序输出为3。（ ）

选择题 19. 若输入字符串为"qwertyuiopasdfghjklzxcvbnm"，则程序输出为（ ）。

A. 4

B. 5

C. 6

D. 7

程序二

#include <iostream>
using namespace std;

int func(int n) {
    if (n <= 1) {
        return n;
    }
    return func(n - 1) + func(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << func(n) << endl;
    return 0;
}

判断题 19. 当输入n为负数时，程序可能会陷入无限递归或得到错误结果。（ ）

20. 该函数func的时间复杂度是O(2^n)。（ ）

选择题 21. 输入为10时，输出结果是（ ）。

A. 34

B. 55

C. 89

D. 144

程序三

#include <iostream>
using namespace std;

int main() {
    int a[101] = {0};
    int n, num;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        a[num]++;
    }
    for (int i = 0; i < 101; i++) {
        while (a[i] > 0) {
            cout << i << " ";
            a[i]--;
        }
    }
    return 0;
}

判断题 22. 该程序实现了对输入n个数的快速排序算法。（ ） 23. 该程序的空间复杂度是O(1)。（ ）

选择题 24. 如果输入是 5 [回车] 3 1 4 1 5，则输出是（ ）。 A. 1 1 3 4 5 B. 5 4 3 1 1 C. 1 3 4 1 5 D. 3 1 4 1 5

该算法的时间复杂度是（ ）。 A. O(n) B. O(n log n) C. O(n²) D. O(n + k) (k为常数100)

三、完善程序（单选题，每小题3分，共计30分） 程序一：（最大子数组和 - 经典算法） 给定一个整数数组，找出其中连续子数组的最大和。

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

int main() {
    int n;
    cin >> n;
    int nums[100];
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int maxSum = nums[0];
    int currentSum = 0;
    for (int i = 0; i < n; i++) {
        ①;
        if (currentSum > maxSum) {
            ②;
        }
        if (currentSum < 0) {
            ③;
        }
    }
    cout << maxSum << endl;
    return 0;
}

①处应填（ ）

A. currentSum = nums[i]

B. currentSum += nums[i]

C. maxSum += nums[i]

D. currentSum = maxSum

②处应填（ ）

A. maxSum = currentSum

B. currentSum = maxSum

C. maxSum = nums[i]

D. maxSum = i

③处应填（ ）

A. currentSum = 0

B. currentSum = maxSum

C. maxSum = 0

D. i = 0

程序二：（图的广度优先遍历 - BFS） 使用邻接矩阵graph（graph[i][j]为1表示有边从i到j）进行BFS遍历。

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

const int N = 100;
int graph[N][N] = {0};
bool visited[N] = {false};

void bfs(int start, int n) {
    queue<int> q;
    cout << start << " ";
    visited[start] = true;
    ④;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && ⑤) {
                cout << i << " ";
                visited[i] = true;
                ⑥;
            }
        }
    }
}

int main() {
    // ... 省略输入图结构的代码
    int startNode;
    cin >> startNode;
    bfs(startNode, n); // n为节点数
    return 0;
}

④处应填（ ）

A. q.push(start)

B. q.pop()

C. q.push(0)

D. q.front()

⑤处应填（ ）

A. !visited[i]

B. visited[i]

C. graph[i][node] == 1

D. i != node

⑥处应填（ ）

A. q.push(node)

B. q.pop()

C. q.push(i)

D. q.front()