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

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

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

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

bool x = false;
cout << x;

{{ select(1) }}

• 0
• 1
• false
• 程序无法通过编译

2、二进制数 $101011_2$ 与八进制数 $36_8$ 的和对应的十进制值是？

{{ select(2) }}

• 71
• 72
• 73
• 74

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

int a = 3, b = 4;
cout << (a += b) << " " << a;

{{ select(3) }}

• 7 7
• 7 3
• 3 7
• 3 3

4、一个空栈依次将 1, 2, 3, 4, 5 入栈，下面哪个序列不可能作为出栈序列？

{{ select(4) }}

• 2, 1, 5, 4, 3
• 3, 5, 4, 2, 1
• 4, 2, 3, 1, 5
• 1, 3, 2, 5, 4

5、在单向链表中，若指针 p 指向某个结点，且 p->next 存在。若要删除 p 后面的直接后继结点，通常应执行哪条语句？

{{ select(5) }}

• p = p->next;
• p->next = p->next->next;
• p->next = p;
• p = p->next->next;

6、一棵二叉树有 13 个结点，并且每个结点的孩子数只能是 0 或 2，则这棵树有多少个叶子结点？

{{ select(6) }}

• 5
• 6
• 7
• 8

7、有向无环图中有边 (1, 3), (1, 4), (2, 4), (3, 5)。下面哪个序列是合法的拓扑排序？

{{ select(7) }}

• 1, 2, 3, 4, 5
• 3, 1, 2, 4, 5
• 1, 4, 2, 3, 5
• 2, 1, 5, 3, 4

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

{{ select(8) }}

• abc-+d*
• ab-cd*+
• abc-d*+
• a+bc-d*

9、有 4 个字符，其出现频率分别为 2, 4, 7, 9。若使用哈夫曼编码，则频率为 2 的字符编码长度为？

{{ select(9) }}

• 1
• 2
• 3
• 4

10、已知一棵二叉树的前序遍历为 A B D C E，中序遍历为 D B A E C，则其后序遍历为？

{{ select(10) }}

• D E B C A
• D B E C A
• B D E C A
• D B C E A

11、对含有 1025 个元素的有序数组进行二分查找，最坏情况下最多需要比较多少次？

{{ select(11) }}

• 9
• 10
• 11
• 12

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

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

{{ select(12) }}

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

13、有 5 名男生和 4 名女生，从中选出 3 人组成小组，要求至少有 2 名女生，共有多少种选法？

{{ select(13) }}

• 30
• 34
• 40
• 44

14、递归函数定义如下：

$$f(1) = 1 \\ f(2) = 2 \\ f(n) = f(n-1) + f(n-2) + 1 \quad (n \geq 3)$$

则 $f(5)$ 的值为？

{{ select(14) }}

• 7
• 8
• 12
• 13

15、下面哪个不能作为 C++ 变量名？

{{ select(15) }}

• sum
• num2026
• return
• _cnt

---

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填"√"，错误填"×"。

除特殊说明外，判断题每题1.5分，选择题每题3分，共40分。其中第16~18题每题2分，第32题4分。

阅读程序（一）

#include <iostream>
using namespace std;

int f(int x) {
    int s = 0;
    while (x) {
        s += x & 1;
        x >>= 1;
    }
    return s;
}

int g(int x) {
    int r = 1;
    while (r * 2 <= x)
        r *= 2;
    return r;
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << " " << g(n) << endl;
    return 0;
}

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

判断题

16、当输入为 $10$ 时，程序输出为 2 8。

{{ select(16) }}

• 正确
• 错误

17、若输入的 $n$ 是 2 的正整数次幂，则 $f(n)$ 的返回值为 1。

{{ select(17) }}

• 正确
• 错误

18、对任意合法输入 $n$，$g(n)$ 的返回值一定是不超过 $n$ 的最大的 2 的幂。

{{ select(18) }}

• 正确
• 错误

单项选择题

19、当输入为 2026 时，程序输出为？

{{ select(19) }}

• 7 1024
• 8 1024
• 8 2048
• 9 1024

20、该程序的时间复杂度最准确地表示为？

{{ select(20) }}

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

---

阅读程序（二）

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

int f(string a, string b) {
    int ans = 0;
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            int k = 0;
            while (i + k < a.size() && j + k < b.size()
                   && a[i + k] == b[j + k]) {
                k++;
            }
            ans = max(ans, k);
        }
    }
    return ans;
}

bool g(string s) {
    for (int i = 0; i < s.size() / 2; i++) {
        if (s[i] != s[s.size() - 1 - i])
            return false;
    }
    return true;
}

int main() {
    string x, y;
    cin >> x >> y;
    cout << f(x, y) << " " << g(x + y) << endl;
    return 0;
}

假设输入的两个字符串只包含小写字母，且长度均不超过 100。

判断题

21、函数 f 返回两个字符串的最长公共子串长度。

{{ select(21) }}

• 正确
• 错误

22、若两个输入字符串完全相同，则函数 f 的返回值等于该字符串的长度。

{{ select(22) }}

• 正确
• 错误

23、函数 g 用于判断字符串是否为回文串。

{{ select(23) }}

• 正确
• 错误

单项选择题

24、当输入为：

abca bcab

程序输出为？

{{ select(24) }}

• 2 0
• 3 0
• 3 1
• 4 0

25、当输入为：

abc cba

程序输出为？

{{ select(25) }}

• 1 0
• 2 0
• 1 1
• 3 1

26、设两个输入字符串长度分别为 $n$, $m$，该程序中函数 f 最坏情况下的时间复杂度为？

{{ select(26) }}

• $O(n + m)$
• $O(nm)$
• $O(nm \log(n + m))$
• $O(nm \min(n, m))$

---

阅读程序（三）

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

int a[105], dp[105];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

假设 $1 \leq n \leq 100$，输入的所有整数均在 int 范围内。

判断题

27、该程序求的是最长严格上升子序列长度。

{{ select(27) }}

• 正确
• 错误

28、若输入的所有数都相等，则程序输出 $n$。

{{ select(28) }}

• 正确
• 错误

29、程序中的 $dp_i$ 表示以第 $i$ 个数结尾的最长不下降子序列长度。

{{ select(29) }}

• 正确
• 错误

单项选择题

30、若输入为：

6
3 1 2 2 1 4

程序输出为？

{{ select(30) }}

• 2
• 3
• 4
• 5

31、若输入为：

7
5 4 3 2 1 1 1

程序输出为？

{{ select(31) }}

• 2
• 3
• 4
• 5

32、若输入为：

8
2 1 3 2 4 3 5 4

程序输出为？

{{ select(32) }}

• 3
• 4
• 5
• 6

---

三、完善程序

单项选择题，每题3分，共30分。

完善程序（一）

下面程序将两个升序数组合并成一个升序数组，请补全程序。

#include <iostream>
using namespace std;

int a[1005], b[1005], c[2010];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    int i = 1, j = 1, k = 0;
    while (  ①  ) {
        if (  ②  )
            ③  ;
        else
            c[++k] = b[j++];
    }
    while (i <= n)
        c[++k] = a[i++];
    while (  ④  )
        ⑤  ;
    for (int t = 1; t <= k; t++)
        cout << c[t] << " ";
    return 0;
}

33、① 处应填？

{{ select(33) }}

• i <= n || j <= m
• i < n && j < m
• i <= n && j <= m
• i == n && j == m

34、② 处应填？

{{ select(34) }}

• a[i] <= b[j]
• a[i] >= b[j]
• i <= j
• n <= m

35、③ 处应填？

{{ select(35) }}

• c[++k] = b[j++]
• c[++k] = a[i++]
• a[++k] = c[i++]
• b[++k] = c[j++]

36、④ 处应填？

{{ select(36) }}

• i <= n
• i <= m
• j <= m
• j <= n

37、⑤ 处应填？

{{ select(37) }}

• c[++k] = a[i++]
• c[++k] = b[i++]
• c[++k] = a[j++]
• c[++k] = b[j++]

---

完善程序（二）

下面程序求两个字符串的最长公共子序列长度，请补全程序。

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

int dp[105][105];

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size();
    int m = b.size();
    for (int i = 1; i <=  ① ; i++) {
        for (int j = 1; j <=  ② ; j++) {
            if (  ③  )
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] =  ④  ;
        }
    }
    cout <<  ⑤  << endl;
    return 0;
}

38、① 处应填？

{{ select(38) }}

• n - 1
• n
• m
• m - 1

39、② 处应填？

{{ select(39) }}

• n
• n - 1
• m
• m - 1

40、③ 处应填？

{{ select(40) }}

• a[i] == b[j]
• a[i - 1] == b[j - 1]
• a[i] != b[j]
• i == j

41、④ 处应填？

{{ select(41) }}

• dp[i - 1][j - 1] + 1
• dp[i - 1][j - 1]
• max(dp[i - 1][j], dp[i][j - 1])
• max(dp[i][j], dp[i - 1][j - 1])

42、⑤ 处应填？

{{ select(42) }}

• dp[0][0]
• dp[n][0]
• dp[0][m]
• dp[n][m]