一、单项选择题(每题 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. 一棵二叉树有 $10$ 个叶子结点,并且每个非叶子结点都有恰好 $2$ 个孩子,则这棵树共有多少个结点?

{{ select(5) }}

• $18$
• $19$
• $20$
• $21$

6. 一个不含重边和自环的无向图有 $7$ 个顶点,最多可能有多少条边?

{{ select(6) }}

• $14$
• $18$
• $21$
• $42$

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

{{ select(7) }}

• $3$
• $4$
• $5$
• $6$

8. 后缀表达式 $abc\times +d-$ 对应的中缀表达式是?

{{ select(8) }}

• $a+ b\times c - d$
• $(a+ b)\times c - d$
• $a+ b\times (c - d)$
• $(a+ b)\times (c - d)$

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

{{ select(9) }}

• $3$
• $4$
• $5$
• $6$

10. 递归函数定义如下:

f(1) = 1
f(2) = 2
f(n) = f(n-1)+f(n-2),(n>=3)

则 f(6) 的值为?

{{ select(10) }}

• $8$
• $11$
• $13$
• $21$

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

int x = 2, y = 5;
int &r = x;
r = y;
cout << x << " " << y;

{{ select(11) }}

• 2
  5
  

• 5
  5
  

• 2
  2
  

• 程序无法通过编译

12. 下面代码片段的时间复杂度是?

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

{{ select(12) }}

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

13. 下列关于二分查找的说法,正确的是?

{{ select(13) }}

• 二分查找只能用于无序数组
• 二分查找通常要求待查找序列具有单调性
• 二分查找一定比哈希查找慢
• 二分查找每次只能排除一个元素

14. 有 $5$ 个字符,其出现频率分别为 $4,6,8,12,20$ 。若使用哈夫曼编码,则频率为 $4$ 的字符编码长度为?

{{ select(14) }}

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

15. 下面哪个STL 容器通常可以用来维护一个有序集合,并支持查找某元素是否存在?

{{ select(15) }}

• vector
• queue
• set
• stack

二、阅读程序

二、阅读程序

程序输入不超过数组或字符串定义的范围。

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

阅读程序(一)

假设输入的 $x$ , $y$ 均为非负整数,且除数字 $0$ 外没有前导零。

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

string add(string a, string b) {
    if (a.size() < b.size())
        swap(a, b);

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int c = 0;
    string r;

    for (int i = 0; i < a.size(); i++) {
        int x = a[i] - '0' + c;
        if (i < b.size())
            x += b[i] - '0';

        r += char('0' + x % 10);
        c = x / 10;
    }

    if (c)
        r += char('0' + c);

    reverse(r.begin(), r.end());
    return r;
}

int main() {
    string x, y;
    cin >> x >> y;
    cout << add(x, y) << endl;
    return 0;
}

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

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

{{ select(16) }}

• 正确
• 错误

(2) 程序输出结果一定不会含有前导零。

{{ select(17) }}

• 正确
• 错误

(3) 若删去 add 函数中的最后一次reverse(r.begin() , r.end()) ,程序仍然能正确输出两数之和。

{{ select(18) }}

• 正确
• 错误

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

{{ select(19) }}

• $18024$
• $18134$
• $19134$
• $20134$

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

{{ select(20) }}

• $O(1)$
• $O(min(n, m))$
• $O(max(n, m))$
• $O(nm)$

阅读程序(二)

假设 $1$ ≤$n$ ≤$20$ ,图中没有重边和自环。

#include <iostream>
using namespace std;

int a[25][25], d[25];
int q[1005];

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

    for (int i = 1; i <= n; i++)
        d[i] = -1;

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

    int hd = 0, tl = 0;
    d[1] = 0;
    q[tl++] = 1;

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

        for (int v = 1; v <= n; v++) {
            if (a[u][v] && d[v] == -1) {
                d[v] = d[u] + 1;
                q[tl++] = v;
            }
        }
    }

    cout << d[n] << endl;
    return 0;
}

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

(1) 若存在边 ($1$ , $n$),且 $n$ > $1$ ,程序一定输出 $1$ 。

{{ select(21) }}

• 正确
• 错误

(2) 程序输出的是从 $1$ 号点到 $n$ 号点经过的最少边数。

{{ select(22) }}

• 正确
• 错误

(3) 如果 $1$ 号点无法到达 $n$ 号点,程序输出 $‐1$ 。

{{ select(23) }}

• 正确
• 错误

(4) 若输入为:

5 5
1 2
2 5
1 3
3 4
4 5

程序输出为?

{{ select(24) }}

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

(5) 若输入为:

6 5
1 2
2 3
3 4
4 5
5 6

程序输出为?

{{ select(25) }}

• $3$
• $4$
• $5$
• $6$

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

{{ select(26) }}

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

阅读程序(三)

假设 $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] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }

        ans = max(ans, dp[i]);
    }

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

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

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

{{ select(27) }}

• 正确
• 错误

(2) 程序中的 $dpi$ 表示前 $i$ 个数中的最长上升子序列长度。

{{ select(28) }}

• 正确
• 错误

(3) 因为判断条件使用的是 a[j] < a[i] ,所以相等的两个元素不能同时作为同一个被统计的上升子序列中的相邻元素。

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

6
3 1 2 1 8 5

程序输出为?

{{ select(30) }}

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

(5) 若输入为:

8
5 1 6 2 7 3 8 4

程序输出为?

{{ select(31) }}

• $3$
• $4$
• $5$
• $6$

(6) 若输入为:

8
2 1 4 3 5 7 6 8

程序输出为?

{{ select(32) }}

• $3$
• $4$
• $5$
• $6$

三、完善程序

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

完善程序(一)

下面程序使用归并排序将数组从小到大排序,请补全程序。

#include <iostream>
using namespace std;

int a[1005], b[1005];

void mg(int l, int r) {
    if (①) return;

    int m = (l + r) / 2;

    mg(l, m);
    mg(②, r);

    int i = l, j = m + 1, k = l;

    while (③) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }

    while (i <= m) ④;
    while (j <= r) b[k++] = a[j++];

    for (int i = l; i <= r; i++)
        ⑤;
}

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

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

    mg(1, n);

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

    return 0;
}

(1) ① 处应填( )

{{ select(33) }}

• l >= r
• l > r
• l == 0
• r == 0

(2) ② 处应填( )

{{ select(34) }}

• m
• m + 1
• l + 1
• r - 1

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

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

(5) ⑤ 处应填( )

{{ select(37) }}

• b[i] = a[i]
• a[i] = b[i]
• a[l] = b[r]
• b[l] = a[r]

完善程序(二)

下面程序对一个有向图进行拓扑排序。若图中存在环,输出 $cycle$ ;否则输出一种拓扑序。

#include <iostream>
using namespace std;

int g[105][105], c[105], d[105];
int q[105], ans[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;
        ①;
    }

    int hd = 0, tl = 0;
    for (int i = 1; i <= n; i++) {
        if (②)
            q[tl++] = i;
    }

    int tot = 0;

    while (hd < tl) {
        int u = ③;
        ans[++tot] = u;

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

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

    if (⑤) {
        cout << "cycle" << endl;
    } else {
        for (int i = 1; i <= n; i++)
            cout << ans[i] << " ";
    }

    return 0;
}

(1) ① 处应填( )

{{ select(38) }}

• d[v]++
• d[u]++
• c[v]++
• c[u]++

(2) ② 处应填( )

{{ select(39) }}

• c[i] == 0
• d[i] != 0
• d[i] == 0
• i == 1

(3) ③ 处应填( )

{{ select(40) }}

• q[tl++]
• q[hd++]
• q[hd]
• q[--tl]

(4) ④ 处应填( )

{{ select(41) }}

• d[v]--
• d[v]++
• c[v]--
• c[u]--

(5) ⑤ 处应填( )

{{ select(42) }}

• tot == n
• tot > n
• hd == tl
• tot < n