一、单项选择题(每题 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)

则 f(5) 的值为?

{{ 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$

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填“$\surd$”,错误填“$\times$”。

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

阅读程序(一)

下面程序在非降序数组 $a_1 \ldots a_n$ 中查找最后一个小于等于 $x$ 的下标(从 $1$ 开始)。若不存在则输出 $0$。假设 $1 \leq n \leq 1000$。

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

(程序 1,每题 2 分)

(1) 函数 ub 返回最后一个小于等于 $x$ 的下标。

{{ select(16) }}

• 正确
• 错误

(2) 函数 ub 返回第一个大于 $x$ 的下标。

{{ select(17) }}

• 正确
• 错误

(3) 若所有元素都大于 $x$,程序输出 $0$。

{{ select(18) }}

• 正确
• 错误

(4) 若输入为:

5
1 2 2 4 7
2

程序输出为?

{{ select(19) }}

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

(5) 函数 ub 的时间复杂度为?

{{ select(20) }}

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

阅读程序(二)

下面程序求有向无环图中最长路径经过的点数。假设 $1 \leq n \leq 100$。

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

(程序 2,每题 1.5 分)

(1) 若图中没有任何边,程序输出 $1$。

{{ select(21) }}

• 正确
• 错误

(2) 程序输出的是图中每个点出度的最大值。

{{ select(22) }}

• 正确
• 错误

(3) $dp_v$ 表示以 $v$ 结尾的最长路径经过的点数。

{{ select(23) }}

• 正确
• 错误

(4) 若输入为:

5 4
1 3
2 3
3 4
2 5

程序输出为?

{{ select(24) }}

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

(5) 若输入为:

4 4
1 2
2 3
3 4
1 3

程序输出为?

{{ select(25) }}

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

(6) 该程序主要计算部分的时间复杂度为?

{{ select(26) }}

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

阅读程序(三)

下面程序统计给每个数前面加上 $+$ 或 $-$ 后,表达式值为 $0$ 的方案数。假设 $1 \leq n \leq 15$。

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

(程序 3,每题 1.5 分)

(1) 当表达式值为 $0$ 时,该方案会被计入 ans。

{{ select(27) }}

• 正确
• 错误

(2) 变量 ans 的初值为 $0$。

{{ select(28) }}

• 正确
• 错误

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

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

3
1 1 2

程序输出为?

{{ select(30) }}

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

(5) 若输入为:

4
1 2 3 4

程序输出为?

{{ select(31) }}

• $0$
• $2$
• $4$
• $6$

(6) 若输入为:

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

(1) ① 处应填( )

{{ select(33) }}

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

(2) ② 处应填( )

{{ select(34) }}

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

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

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

(5) ⑤ 处应填( )

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

(1) ① 处应填( )

{{ select(38) }}

• 0
• 1
• c[i]
• m

(2) ② 处应填( )

{{ select(39) }}

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

(3) ③ 处应填( )

{{ select(40) }}

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

(4) ④ 处应填( )

{{ select(41) }}

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

(5) ⑤ 处应填( )

{{ select(42) }}

• n
• m
• dp[m]
• INF