一、单项选择题(每题 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. 十六进制数 $2 F_{1 6}$ 与二进制数 $1 0 1 1 0 1_{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) }}

• $\times +ab-cd$
• $+a\times b-cd$
• $ab+cd-×$
• $\times -+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$ 分。其中第 $16 \sim 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;
}

(程序 $1$ ,每题 $1.5$ 分)

(1) 当输入为 abcde $2$ 时,程序输出为 cdeab 。

{{ select(16) }}

• 正确
• 错误

(2) 当 $k$ 是字符串长度的倍数时,程序输出一定与原字符串相同。

{{ select(17) }}

• 正确
• 错误

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

{{ select(18) }}

• 正确
• 错误

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

{{ select(19) }}

• cspj2026
• 26cspj20
• pj2026cs
• 2026cspj

(5) 设输入字符串长度为 $n$ ,该程序的时间复杂度为?

{{ select(20) }}

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

阅读程序(二)

假设 $1 ≤ n ≤ 100$ , $1 ≤m ≤1000$ ,且所有 $vi$ , $wi$ 均为正整数。

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

(程序 $2$ ,每题 $1.5$ 分)

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

{{ select(21) }}

• 正确
• 错误

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

{{ select(22) }}

• 正确
• 错误

(3) 程序中的 $dpm$ 表示恰好装满容量 $m$ 时的最大价值。

{{ select(23) }}

• 正确
• 错误

(4) 若输入为:

3 5
2 3
3 4
4 5

程序输出为?

{{ select(24) }}

• $5$
• $7$
• $9$
• $12$

(5) 若输入为:

3 4
2 10
2 20
3 25

程序输出为?

{{ select(25) }}

• $20$
• $25$
• $30$
• $35$

(6) 该程序的时间复杂度为?

{{ select(26) }}

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

阅读程序(三)

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

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

(程序 $3$ ,每题 $1.5$ 分)

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

{{ select(27) }}

• 正确
• 错误

(2) 当输入为 $3$ 时,程序输出为 $5$ 。

{{ select(28) }}

• 正确
• 错误

(3) 当输入为 $4$ 时,程序输出为 $7$ 。

{{ select(29) }}

• 正确
• 错误

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

{{ select(30) }}

• $8$
• $13$
• $16$
• $21$

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

{{ select(31) }}

• $8$
• $10$
• $15$
• $16$

(6) 当输入为 $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;
}

(1) ① 处应填( )

{{ select(33) }}

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

(2) ② 处应填( )

{{ select(34) }}

• 0
• i
• i + 1
• n

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

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

(5) ⑤ 处应填( )

{{ select(37) }}

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

完善程序(二)

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

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

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

(1) ① 处应填( )

{{ select(38) }}

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

(2) ② 处应填( )

{{ select(39) }}

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

(3) ③ 处应填( )

{{ select(40) }}

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

(4) ④ 处应填( )

{{ select(41) }}

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

(5) ⑤ 处应填( )

{{ select(42) }}

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