该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

单项选择题15题（每题2分），阅读程序17题（共40分），完善程序10题（每题3分），共100分

一、单项选择题

共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 \times f(n-2) \quad (n \geq 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分。其中第16∼18题每题2分，第32题4分。

阅读程序（一）

#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)$

---

阅读程序（二）

#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 \leq n \leq 100$，$1 \leq m \leq 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)$

---

阅读程序（三）

#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分。

完善程序（一）

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

#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

---

完善程序（二）

下面程序输出所有长度为 $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