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

一、单项选择题(每题 2 分,共 30 分)

1. 阅读下面代码,输出结果是?

bool x = false;
cout << x;

{{ select(1) }}

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

2. 二进制数 $1 0 1 0 1 1_{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$

1. 一个空栈依次将 $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)×d$ 对应的后缀表达式是?

{{ select(8) }}

• $abc-+d\times$
• $ab-cd\times +$
• $abc-d\times +$
• $a+bc-d\times$

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 (n>=3)

则 f(5) 的值为?

{{ select(14) }}

• $7$
• $8$
• $12$
• $13$

15. 下面哪个不能作为 C++ 变量名?

{{ select(15) }}

• sum
• num2026
• return
• _cnt

二、阅读程序

阅读程序(一)

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

#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;
}

(1) 当输入为 $10$ 时,程序输出为 $2$ $8$ 。

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

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

{{ select(18) }}

• 正确
• 错误

(4) 当输入为 $2026$ 时,程序输出为?

{{ select(19) }}

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

(5) 该程序的时间复杂度最准确地表示为?

{{ select(20) }}

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

阅读程序(二)

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

#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;
}

(1) 函数 $f$ 返回两个字符串的最长公共子串长度。

{{ select(21) }}

• 正确
• 错误

(2) 若两个输入字符串完全相同,则函数 $f$ 的返回值等于该字符串的长度。

{{ select(22) }}

• 正确
• 错误

(3) 函数 $g$ 用于判断字符串是否为回文串。

{{ select(23) }}

• 正确
• 错误

(4) 当输入为: abca bcab 程序输出为?

{{ select(24) }}

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

(5) 当输入为: abc cba 程序输出为?

{{ select(25) }}

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

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

{{ select(26) }}

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

阅读程序(三)

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

#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) 该程序求的是最长严格上升子序列长度。

{{ select(27) }}

• 正确
• 错误

(2) 若输入的所有数都相等,则程序输出 $n$ 。

{{ select(28) }}

• 正确
• 错误

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

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

6
3 1 2 2 1 4

程序输出为?

{{ select(30) }}

• $2$
• $3$
• $4$
• $5$

(5) 若输入为:

7
5 4 3 2 1 1 1

程序输出为?

{{ select(31) }}

• $2$
• $3$
• $4$
• $5$

(6) 若输入为:

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;
}

(1) ① 处应填( )

{{ select(33) }}

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

(2) ② 处应填( )

{{ select(34) }}

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

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

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

(5) ⑤ 处应填( )

{{ 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;
}

(1) ① 处应填( )

{{ select(38) }}

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

(2) ② 处应填( )

{{ select(39) }}

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

(3) ③ 处应填( )

{{ select(40) }}

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

(4) ④ 处应填( )

{{ 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])

(5) ⑤ 处应填( )

{{ select(42) }}

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