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

---

1. 阅读下面代码，输出结果是？

#include <iostream>
using namespace std;

int x = 5;

void f() {
    int x = 3;
    x += 2;
}

int main() {
    f();
    cout << x;
    return 0;
}

{{ select(1) }}

• 3
• 5
• 7
• 程序无法通过编译

---

2. 十六进制数 $(2F)_{16}$ 与二进制数 $(101101)_2$ 的和对应的十进制值是？

{{ select(2) }}

• 86
• 90
• 92
• 94

---

3. 阅读下面代码，输出结果是？

int a[4] = {2, 4, 6, 8};
int *p = a;
cout << *(p + 2);

{{ select(3) }}

• 2
• 4
• 6
• 8

---

4. 一个队列初始为空，依次执行如下操作：

push 4
push 7
pop
push 9
pop
push 1

此时队列中从队首到队尾的元素依次为？

{{ select(4) }}

• $1, 9$
• $7, 9, 1$
• $4, 7, 9, 1$
• $9, 1$

---

5. 一棵完全二叉树用数组存储，根结点存储在下标 1 的位置。若某结点下标为 12，则它的父结点下标和左儿子下标分别为？

{{ select(5) }}

• $5, 24$
• $6, 24$
• $6, 25$
• $7, 24$

---

6. 一个无向图有 9 个顶点、12 条边，则所有顶点的度数之和为？

{{ select(6) }}

• 12
• 18
• 21
• 24

---

7. 有向无环图中有边 $(1,3), (2,3), (2,4)$。该图共有多少种不同的拓扑排序？

{{ select(7) }}

• 3
• 4
• 5
• 6

---

8. 中缀表达式 $(a + b) \times (c - d)$ 对应的前缀表达式是？

{{ select(8) }}

• *+ab-cd
• +a*b-cd
• ab+cd-*
• *-+abcd

---

9. 由字母 A, A, B, C, D 组成的不同字符串共有多少个？

{{ select(9) }}

• 30
• 45
• 60
• 120

---

10. 递归函数定义如下：

f(0)=1
f(1)=1
f(n)=f(n-1)+2*f(n-2)  (n>=2)

则 $f(5)$ 的值为？

{{ select(10) }}

• 11
• 15
• 21
• 31

---

11. 阅读下面代码，输出结果是？

int x = 3;
int *p = &x;
(*p)++;
cout << x;

{{ select(11) }}

• 2
• 3
• 4
• 程序无法通过编译

---

12. 下面代码片段的时间复杂度是？

for (int i = 1; i <= n; i *= 2)
    for (int j = 1; j <= n; j++)
        cout << i + j << endl;

{{ select(12) }}

• $O(n)$
• $O(\log n)$
• $O(n \log n)$
• $O(n^2)$

---

13. 按顺序向一棵空二叉搜索树中插入 $4, 2, 6, 1, 3, 5, 7$，则该二叉搜索树的后序遍历为？

{{ select(13) }}

• $1, 3, 2, 5, 7, 6, 4$
• $1, 2, 3, 4, 5, 6, 7$
• $7, 6, 5, 4, 3, 2, 1$
• $2, 1, 3, 6, 5, 7, 4$

---

14. 有 5 个字符，其出现频率分别为 $2, 3, 7, 9, 18$。若使用哈夫曼编码，则频率为 2 的字符编码长度为？

{{ select(14) }}

• 1
• 2
• 3
• 4

---

15. 下面哪个 STL 容器最适合描述"先进先出"的数据结构？

{{ select(15) }}

• stack
• queue
• set
• map

---

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

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

string rot(string s, int k) {
    int n = s.size();
    k %= n;

    string t;
    for (int i = k; i < n; i++)
        t += s[i];

    for (int i = 0; i < k; i++)
        t += s[i];

    return t;
}

int main() {
    string s;
    int k;
    cin >> s >> k;
    cout << rot(s, k) << endl;
    return 0;
}

假设输入字符串非空，且只包含小写字母和数字。

判断题

---

16. 当输入为 abcde 2 时，程序输出为 cdeab。

{{ select(16) }}

• 正确
• 错误

---

17. 当 $k$ 是字符串长度的倍数时，程序输出一定与原字符串相同。

{{ select(17) }}

• 正确
• 错误

---

18. 该程序实现的是将字符串向右循环移动 $k$ 位。

{{ select(18) }}

• 正确
• 错误

---

选择题

---

19. 当输入为 cspj2026 10 时，程序输出为？

{{ select(19) }}

• cspj2026
• 26cspj20
• pj2026cs
• 2026cspj

---

20. 设输入字符串长度为 $n$，该程序的时间复杂度为？

{{ select(20) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n^2)$

---

(2)

#include <iostream>
using namespace std;

int v[105], w[105], dp[1005];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            if (dp[j] < dp[j - v[i]] + w[i])
                dp[j] = dp[j - v[i]] + w[i];
        }
    }

    cout << dp[m] << endl;
    return 0;
}

假设 $1 \le n \le 100$，$1 \le m \le 1000$，且所有 $v_i, w_i$ 均为正整数。

判断题

---

21. 第 13 行的循环从大到小枚举 $j$，可以保证每个物品最多被选一次。

{{ select(21) }}

• 正确
• 错误

---

22. 若将第 13 行改为从 $v_i$ 到 $m$ 递增枚举 $j$，程序仍然总能求出每个物品最多选一次的最优值。

{{ select(22) }}

• 正确
• 错误

---

23. 程序中的 $dp_m$ 表示恰好装满容量 $m$ 时的最大价值。

{{ select(23) }}

• 正确
• 错误

---

选择题

---

24. 若输入为：

3 5
2 3
3 4
4 5

程序输出为？

{{ select(24) }}

• 5
• 7
• 9
• 12

---

25. 若输入为：

3 4
2 10
2 20
3 25

程序输出为？

{{ select(25) }}

• 20
• 25
• 30
• 35

---

26. 该程序的时间复杂度为？

{{ select(26) }}

• $O(n)$
• $O(m)$
• $O(nm)$
• $O(n^2 m)$

---

(3)

#include <iostream>
using namespace std;

int n, ans;

void dfs(int p, int la) {
    if (p > n) {
        ans++;
        return;
    }

    dfs(p + 1, 0);

    if (!la)
        dfs(p + 1, 1);
}

int main() {
    cin >> n;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

假设输入的 $n$ 是不超过 20 的正整数。

判断题

---

27. 当输入为 1 时，程序输出为 2。

{{ select(27) }}

• 正确
• 错误

---

28. 当输入为 3 时，程序输出为 5。

{{ select(28) }}

• 正确
• 错误

---

29. 当输入为 4 时，程序输出为 7。

{{ select(29) }}

• 正确
• 错误

---

选择题

---

30. 当输入为 5 时，程序输出为？

{{ select(30) }}

• 8
• 13
• 16
• 21

---

31. 若删去第 13 行的 if (!la) 判断，直接执行 dfs(p + 1, 1);，当输入为 4 时，程序输出为？

{{ select(31) }}

• 8
• 10
• 15
• 16

---

32. 当输入为 6 时，程序输出为？

{{ select(32) }}

• 18
• 20
• 21
• 32

---

三、完善程序（单选题，每题 3 分，共计 30 分）

（1）下面程序使用选择排序将数组从小到大排序，请补全程序。

#include <iostream>
using namespace std;

int a[1005];

void sel(int n) {
    for (int i = 0; i < n; i++) {
        int p = ①;

        for (int j = ②; j < n; j++) {
            if (③)
                p = j;
        }

        int t = a[i];
        a[i] = ④;
        ⑤ = t;
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    sel(n);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

---

33. ① 处应填？

{{ select(33) }}

• i
• 0
• i + 1
• n - 1

---

34. ② 处应填？

{{ select(34) }}

• 0
• i
• i + 1
• n

---

35. ③ 处应填？

{{ select(35) }}

• a[j] < a[p]
• a[j] > a[p]
• j < p
• a[i] < a[j]

---

36. ④ 处应填？

{{ select(36) }}

• a[i]
• a[p]
• a[j]
• t

---

37. ⑤ 处应填？

{{ select(37) }}

• a[i]
• a[p]
• a[j]
• p

---

（2）下面程序输出所有长度为 $2n$ 的合法括号序列，请补全程序。

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

int n;

void dfs(int l, int r, string s) {
    if (①) {
        cout << s << endl;
        return;
    }

    if (②)
        dfs(③, r, s + "(");

    if (④)
        dfs(l, ⑤, s + ")");
}

int main() {
    cin >> n;
    dfs(0, 0, "");
    return 0;
}

其中 $l$ 表示已经放入的左括号数量，$r$ 表示已经放入的右括号数量。

---

38. ① 处应填？

{{ select(38) }}

• l == r
• l == n
• r == n
• l == n && r == n

---

39. ② 处应填？

{{ select(39) }}

• l < n
• l > n
• r < n
• r > l

---

40. ③ 处应填？

{{ select(40) }}

• l - 1
• l + 1
• r + 1
• n

---

41. ④ 处应填？

{{ select(41) }}

• l < r
• l == r
• r < l
• r == n

---

42. ⑤ 处应填？

{{ select(42) }}

• r - 1
• r + 1
• l + 1
• n