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

---

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

#include <iostream>
using namespace std;

int f() {
    static int x = 1;
    x += 2;
    return x;
}

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

{{ select(1) }}

• 1 3
• 3 5
• 5 7
• 3 3

---

2. 五进制数 $123_5$ 与八进制数 $47_8$ 的和对应的十进制值是？

{{ select(2) }}

• 75
• 76
• 77
• 78

---

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

void f(int &a, int b) {
    a += b;
    b += a;
}

int main() {
    int x = 2, y = 3;
    f(x, y);
    cout << x << " " << y;
    return 0;
}

{{ select(3) }}

• 2 3
• 5 3
• 5 8
• 2 8

---

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

string s = "abacaba";
cout << s.find("aca");

{{ select(4) }}

• 0
• 1
• 2
• 3

---

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

{{ select(5) }}

• $2, 1, 4, 3$
• $3, 1, 2, 4$
• $1, 4, 3, 2$
• $2, 3, 4, 1$

---

6. 一棵有 2026 个结点的完全二叉树，叶子结点个数为？

{{ select(6) }}

• 1011
• 1012
• 1013
• 1014

---

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

{{ select(7) }}

• 3
• 4
• 5
• 6

---

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

{{ select(8) }}

• 1
• 2
• 3
• 4

---

9. 从 $1, 2, 3, 4, 5, 6, 7$ 中选出 3 个数，要求任意两个数都不相邻，共有多少种选法？

{{ select(9) }}

• 6
• 7
• 9
• 10

---

10. 递归函数定义如下：

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

{{ select(10) }}

• 31
• 41
• 51
• 61

---

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

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

{{ select(11) }}

• $O(n)$
• $O(n \log n)$
• $O(n\sqrt{n})$
• $O(n^2)$

---

12. 若 int 占 4 字节，则数组 int a[50][80]; 大约占用多少字节？

{{ select(12) }}

• 8000
• 16000
• 32000
• 4000

---

13. 一个无向森林有 20 个顶点、5 个连通块，则它有多少条边？

{{ select(13) }}

• 14
• 15
• 16
• 19

---

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

vector<int> v;
v.push_back(3);
v.push_back(1);
v.pop_back();
cout << v.size() << " " << v[0];

{{ select(14) }}

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

---

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

cout << (3 + 4 * 2 > 10 && 5);

{{ select(15) }}

• 0
• 1
• 5
• 11

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

阅读程序（一）

#include <iostream>
using namespace std;

int a[1005];

int ub(int n, int x) {
    int l = 1, r = n + 1;

    while (l < r) {
        int m = (l + r) / 2;

        if (a[m] <= x)
            l = m + 1;
        else
            r = m;
    }

    return l - 1;
}

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

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

    cin >> x;

    cout << ub(n, x) << endl;
    return 0;
}

假设 $a_1, a_2, \ldots, a_n$ 单调不降，且 $1 \le n \le 1000$。

判断题

---

16. 如果所有 $a_i$ 都小于等于 $x$，程序输出 $n$。

{{ select(16) }}

• 正确
• 错误

---

17. 函数 ub 返回的是第一个大于等于 $x$ 的位置。

{{ select(17) }}

• 正确
• 错误

---

18. 如果所有 $a_i$ 都大于 $x$，程序输出 $0$。

{{ select(18) }}

• 正确
• 错误

单项选择题

---

19. 若输入为：

5
1 2 2 4 7
2

{{ select(19) }}

• 1
• 2
• 3
• 4

---

20. 该程序中函数 ub 的时间复杂度为？

{{ select(20) }}

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

阅读程序（二）

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

int g[105][105], c[105], d[105], dp[105];
int q[105];

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

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        g[u][++c[u]] = v;
        d[v]++;
    }

    int hd = 0, tl = 0;

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;

        if (d[i] == 0)
            q[tl++] = i;
    }

    while (hd < tl) {
        int u = q[hd++];

        for (int i = 1; i <= c[u]; i++) {
            int v = g[u][i];

            if (dp[v] < dp[u] + 1)
                dp[v] = dp[u] + 1;

            d[v]--;

            if (d[v] == 0)
                q[tl++] = v;
        }
    }

    int ans = 0;

    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);

    cout << ans << endl;
    return 0;
}

假设输入是一张有向无环图，且 $1 \le n \le 100$。

判断题

---

21. 如果图中没有任何边，程序输出 1。

{{ select(21) }}

• 正确
• 错误

---

22. 数组 $d$ 在读入后表示每个点的出度。

{{ select(22) }}

• 正确
• 错误

---

23. 程序结束时，$dp_i$ 表示以点 $i$ 结尾的最长路径包含的点数。

{{ select(23) }}

• 正确
• 错误

单项选择题

---

24. 若输入为：

5 4
1 3
2 3
3 4
2 5

{{ select(24) }}

• 2
• 3
• 4
• 5

---

25. 若输入为：

4 4
1 2
2 3
3 4
1 3

{{ select(25) }}

• 2
• 3
• 4
• 5

---

26. 该程序的主要计算部分时间复杂度为？

{{ select(26) }}

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

阅读程序（三）

#include <iostream>
using namespace std;

int n, a[20], ans;

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

    dfs(p + 1, s + a[p]);
    dfs(p + 1, s - a[p]);
}

int main() {
    cin >> n;

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

    dfs(1, 0);

    cout << ans << endl;
    return 0;
}

假设 $1 \le n \le 15$，输入的所有 $a_i$ 均为非负整数。

判断题

---

27. 若所有 $a_i$ 的和为奇数，程序一定输出 0。

{{ select(27) }}

• 正确
• 错误

---

28. 若所有 $a_i$ 都为 $0$，程序输出 $2^n$。

{{ select(28) }}

• 正确
• 错误

---

29. 该程序的时间复杂度为 $O(2^n)$。

{{ select(29) }}

• 正确
• 错误

单项选择题

---

30. 若输入为：

3
1 1 2

{{ select(30) }}

• 0
• 2
• 3
• 4

---

31. 若输入为：

4
1 2 3 4

{{ select(31) }}

• 0
• 2
• 4
• 6

---

32. 若输入为：

5
1 1 1 1 2

{{ select(32) }}

• 4
• 5
• 6
• 8

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

完善程序（一）

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

#include <iostream>
using namespace std;

int a[1005];

void qs(int l, int r) {
    if (l >= r)
        return;

    int i = l, j = r;
    int x = ①;

    while (②) {
        while (a[i] < x)
            i++;

        while (③)
            j--;

        if (i <= j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;

            ④;
            j--;
        }
    }

    if (l < j)
        qs(l, j);

    if (i < r)
        ⑤;
}

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

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

    qs(1, n);

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

    return 0;
}

---

33. ① 处应填？

{{ select(33) }}

• a[l]
• a[(l + r) / 2]
• a[r]
• l + r

---

34. ② 处应填？

{{ select(34) }}

• i <= j
• i < l
• j > r
• i == j

---

35. ③ 处应填？

{{ select(35) }}

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

---

36. ④ 处应填？

{{ select(36) }}

• i--
• j++
• i++
• r--

---

37. ⑤ 处应填？

{{ select(37) }}

• qs(l, i)
• qs(j, r)
• qs(i, j)
• qs(i, r)

完善程序（二）

下面程序求使用给定硬币面值凑出金额 $m$ 所需的最少硬币数量。每种硬币可以使用任意多次。若无法凑出，输出 -1。请补全程序。

#include <iostream>
using namespace std;

const int INF = 1000000000;

int c[105], dp[1005];

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

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

    dp[0] = 0;

    for (int i = 1; i <= m; i++)
        dp[i] = INF;

    for (int i = 1; i <= n; i++) {
        for (int j = ①; j <= m; j++) {
            if (②)
                dp[j] = ③;
        }
    }

    if (④)
        cout << -1 << endl;
    else
        cout << ⑤ << endl;

    return 0;
}

---

38. ① 处应填？

{{ select(38) }}

• 0
• 1
• c[i]
• m

---

39. ② 处应填？

{{ select(39) }}

• dp[j] < dp[j - c[i]] + 1
• dp[j - c[i]] + 1 < dp[j]
• dp[j] == 0
• j < c[i]

---

40. ③ 处应填？

{{ select(40) }}

• dp[j - c[i]] + 1
• dp[j] + 1
• dp[c[i]]
• c[i]

---

41. ④ 处应填？

{{ select(41) }}

• dp[0] == INF
• dp[m] == 0
• dp[m] < INF
• dp[m] == INF

---

42. ⑤ 处应填？

{{ select(42) }}

• n
• m
• dp[m]
• INF