珅泽教育CSP-J第一轮模拟考第十七套

本卷共 45 题，建议限时 120 分钟，满分 100 分。判断题请选择“正确”或“错误”；其余题目均为单项选择题。

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

第 1 题

在 C++ 中执行以下代码后，变量 a 和 b 的值分别为（ ）。

int a = 5, b = 7;
a += b -= a *= b;

{{ select(1) }}

• 35，7
• 35，-28
• 7，7
• 7，-28

第 2 题

定义 $S(n)$ 为正整数 $n$ 的二进制表示中数字 1 的个数。则 $\sum_{i=0}^{15}S(i)$ 的值为（ ）。

{{ select(2) }}

• 16
• 24
• 32
• 64

第 3 题

已知二叉树的后序遍历序列为 D E B F G C A，中序遍历序列为 D B E A F C G，则其前序遍历序列为（ ）。

{{ select(3) }}

• A B D E C F G
• A B D E C G F
• A B E D C F G
• A B E D C G F

第 4 题

在 C++ 中，如果 a 和 b 都是 int 类型变量，则表达式 (a ^ b) == (a | b) 成立的条件是（ ）。

{{ select(4) }}

• a 和 b 相等
• a 和 b 互为相反数
• a 和 b 没有公共的二进制位为 1
• a 和 b 均为 0

第 5 题

在 C++ 中，以下哪个位运算表达式可以有效地判断一个正整数 x 是否是 2 的幂次方（ ）。

{{ select(5) }}

• (x & (x - 1)) == 0
• (x & -x) == 1
• (x | (x - 1)) == x
• (x ^ (x - 1)) == 1

第 6 题

一个无向图有 20 条边，其中 3 个顶点的度为 4，2 个顶点的度为 3，其余顶点的度均为 2，则该图的顶点总数为（ ）。

{{ select(6) }}

• 14
• 15
• 17
• 16

第 7 题

用某种排序算法对序列 [4, 2, 5, 1, 3] 进行升序排序。若第一趟排序后的结果为 [2, 4, 1, 3, 5]，则该排序算法最可能是（ ）。

{{ select(7) }}

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序

第 8 题

哈希表长度为 10，哈希函数为 $h(k)=k\bmod7$，采用线性探测法处理冲突。依次插入关键字 15、8、22、1，则关键字 22 最终存入的下标为（ ）。

{{ select(8) }}

• 1
• 3
• 2
• 4

第 9 题

在 C++ 中，若定义 std::map<int, std::string> mp = {{1, "A"}, {2, "B"}, {3, "C"}};，执行 mp[4] = "D"; mp[2] = "E"; 后，mp.size() 和 mp[1] 的值分别为（ ）。

{{ select(9) }}

• 3 和 "A"
• 4 和 "A"
• 4 和 ""
• 3 和 ""

第 10 题

已知函数定义如下，则 g(5) 的返回值为（ ）。

int g(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return g(n - 1) + 2 * g(n - 2);
}

{{ select(10) }}

• 11
• 8
• 9
• 13

第 11 题

以下代码的时间复杂度为（ ）。

for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

{{ select(11) }}

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

第 12 题

关于栈和队列，下列说法错误的是（ ）。

{{ select(12) }}

• 栈是后进先出的线性表
• 队列是先进先出的线性表
• 栈和队列都只能在端点进行插入和删除
• 循环队列一定比普通队列节省存储空间

第 13 题

斐波那契数列定义为 $F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)$，则 $F(2026)\bmod4=$（ ）。

{{ select(13) }}

• 0
• 1
• 2
• 3

第 14 题

在一个 $3\times3$ 的方格棋盘上，从左上角格子走到右下角格子，每次只能向右或向下移动一格，且不能经过中心格。则不同的行走路径共有（ ）条。

{{ select(14) }}

• 2
• 4
• 6
• 8

第 15 题

以下关于差分算法的说法，正确的是（ ）。

{{ select(15) }}

• 差分数组的前缀和就是原数组
• 差分数组只能处理加法操作，不能处理减法操作
• 差分算法的时间复杂度为 $\Theta(n^2)$
• 差分数组的长度必须比原数组多 1

二、阅读程序（判断题每题 1 分，选择题每题 3 分，共 40 分）

程序阅读（1）：字符串重排

using std::string;
string flip(string in)
{
    string out = "";
    for (unsigned i = 0; i < in.size(); ++i)
    {
        string buffer = "";
        buffer += in[i];
        for (unsigned j = out.size(); j > 0; --j)
        {
            buffer += out[j - 1];
        }
        out = buffer;
    }
    return out;
}

第 16 题

执行 flip("abcdef") 的返回值为 "fdbace"。（ ）

{{ select(16) }}

• 正确
• 错误

第 17 题

对任意字符串 s，flip(s) 的长度与 s 的长度相等。（ ）

{{ select(17) }}

• 正确
• 错误

第 18 题

对任意字符串 s 和 t，都有 flip(s + t) == flip(t) + flip(s)。（ ）

{{ select(18) }}

• 正确
• 错误

第 19 题

对任意非空字符串 s，flip(s) 的第一个字符一定等于 s 的最后一个字符。（ ）

{{ select(19) }}

• 正确
• 错误

第 20 题

字符串长度为 $n$，该函数的时间复杂度为 $\Theta(n^2)$。（ ）

{{ select(20) }}

• 正确
• 错误

第 21 题

若 flip(s) == "pineapple"，则字符串 s 为（ ）。

{{ select(21) }}

• "apepnliep"
• "apnepilep"
• "apeplniep"
• "apenpliep"

第 22 题

若要实现与该函数完全相同的功能，理论上最优的时间复杂度为（ ）。

{{ select(22) }}

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

第 23 题

若对所有长度为 $n$ 的字符串 s 都有 flip(flip(s)) == s，则 $n$ 的最大可能值为（ ）。

{{ select(23) }}

• 1
• 2
• 3
• 4

程序阅读（2）：螺旋坐标

using pair = std::pair<int, int>;
pair find(int n, int k)
{
    if (n == 1) {
        return {1, 1};
    }
    if (k <= n - 1) {
        return {1, k};
    }
    else {
        k -= n - 1;
    }
    if (k <= n - 1) {
        return {k, n};
    }
    else {
        k -= n - 1;
    }
    if (k <= n - 1) {
        return {n, n + 1 - k};
    }
    else {
        k -= n - 1;
    }
    if (k <= n - 1) {
        return {n + 1 - k, 1};
    }
    else {
        k -= n - 1;
    }
    auto p = find(n - 2, k);
    return {p.first + 1, p.second + 1};
}

第 24 题

该函数的时间复杂度为 $\Theta(n)$。（ ）

{{ select(24) }}

• 正确
• 错误

第 25 题

该函数在每一层递归中，每条边遍历 $n$ 个元素。（ ）

{{ select(25) }}

• 正确
• 错误

第 26 题

执行 find(4, 7) 的返回值为（ ）。

{{ select(26) }}

• {3, 3}
• {3, 4}
• {4, 3}
• {4, 4}

第 27 题

若 n=4，返回值为 {2, 2} 时，k 是（ ）。

{{ select(27) }}

• 11
• 12
• 13
• 14

第 28 题

对于 n>=2，螺旋遍历中第 $3(n-1)+1$ 个元素的坐标为（ ）。

{{ select(28) }}

• {n, 1}
• {2, 1}
• {1, n}
• {n, n}

第 29 题

若 find(n-2, k) 返回 {a, b}，则 find(n, k + 4*(n-1)) 返回（ ）。

{{ select(29) }}

• {a, b}
• {a+1, b+1}
• {a-1, b-1}
• {a+1, b}

程序阅读（3）：函数图与环

using i64 = long long;
int solve(int N, i64 K, int A[])
{
    std::vector<int> path;
    std::vector<int> pos(N + 1, -1);

    int cur = 1;
    while (pos[cur] == -1)
    {
        pos[cur] = path.size();
        path.push_back(cur);
        cur = A[cur];
    }

    int start = pos[cur];
    int cycle = path.size() - start;

    if (K < start)
        return path[K];
    return path[start + ((K - start) % cycle)];
}

第 30 题

若 K=0，函数返回 0。（ ）

{{ select(30) }}

• 正确
• 错误

第 31 题

path 数组中可能包含重复的编号。（ ）

{{ select(31) }}

• 正确
• 错误

第 32 题

该算法的时间复杂度与 K 的大小有关。（ ）

{{ select(32) }}

• 正确
• 错误

第 33 题

已知 N=3, K=5，且 A[1..3]={2,3,1}，函数返回值为（ ）。

{{ select(33) }}

• 1
• 2
• 3
• 4

第 34 题

已知 N=4, K=5，且 A[1..4]={2,3,4,3}，函数返回值为（ ）。

{{ select(34) }}

• 2
• 3
• 4
• 5

第 35 题

当 K>=start 时，函数返回 path[i]，下标 i 满足（ ）。

{{ select(35) }}

• 0<=i<start
• start<=i<path.size()
• start<=i<=path.size()
• i=(K-start)%cycle

三、完善程序（共 10 题，每题 3 分，共 30 分）

完善程序（1）：两序列最大乘积

给定长度为 $n$ 的整数序列 $a$ 和长度为 $m$ 的整数序列 $b$，请分别从两序列中各取一个数，使两数乘积最大。

#include <algorithm>
#include <utility>

std::pair<int, int> find(int n, int a[])
{
    _____(1)_____;
    for (int i = 1; i < n; ++i)
    {
        _____(2)_____;
        mn = std::min(mn, a[i]);
    }
    _____(3)_____;
}

int solve(int n, int a[], int m, int b[])
{
    auto [maxa, mina] = _____(4)_____;
    auto [maxb, minb] = find(m, b);
    return _____(5)_____;
}

第 36 题

（1）处应填（ ）。

{{ select(36) }}

• int mx = 0, mn = 0;
• int mx = a[0], mn = 0;
• int mx = a[0], mn = a[0];
• int mx = 10000, mn = -10000;

第 37 题

（2）处应填（ ）。

{{ select(37) }}

• mn = std::max(mx, a[i]);
• mx = std::max(mx, a[i]);
• mx = std::min(mx, a[i]);
• mx = std::max(mx, a[0]);

第 38 题

（3）处应填（ ）。

{{ select(38) }}

• return {mn, mx};
• return {mx, mx};
• return {a[0], mn};
• return {mx, mn};

第 39 题

（4）处应填（ ）。

{{ select(39) }}

• find(n, a)
• find(m, b)
• find(n, b)
• find(m, a)

第 40 题

（5）处应填（ ）。

{{ select(40) }}

• std::max({maxa * maxb, maxa * minb})
• std::min({maxa * maxb, maxa * minb, mina * maxb, mina * minb})
• std::max({maxa * maxb, maxa * minb, mina * maxb, mina * minb})
• std::max({maxa * maxb, mina * minb})

完善程序（2）：三个杯子倒水

三个无刻度杯子的容量分别为 $a、b、c$，初始时第三杯装满。每次倒水直到源杯空或目标杯满；求能得到的最小正水量及达到它的最少步数。

const int INF = 1000000000;
struct Node { int a, b; };
int dist[5001][5001];
int ans, cost;

void bfs(int cap[])
{
    queue<Node> q;
    q.push({0, 0});
    dist[0][0] = 0;
    while (!q.empty())
    {
        Node u = q.front(); q.pop();
        int a = u.a, b = u.b;
        int c = _____(1)_____;
        int cur = dist[a][b];
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                int w[3] = {a, b, c};
                if (_____(2)_____) continue;
                int pour = _____(3)_____;
                w[i] -= pour;
                w[j] += pour;
                int na = w[0], nb = w[1];
                if (dist[na][nb] == -1)
                {
                    _____(4)_____;
                    q.push({na, nb});
                    int nc = cap[2] - na - nb;
                    if (_____(5)_____)
                    {
                        ans = na;
                        cost = cur + 1;
                    }
                    if (nb > 0 && (nb < ans || (nb == ans && cur + 1 < cost)))
                    {
                        ans = nb;
                        cost = cur + 1;
                    }
                    if (nc > 0 && (nc < ans || (nc == ans && cur + 1 < cost)))
                    {
                        ans = nc;
                        cost = cur + 1;
                    }
                }
            }
        }
    }
}

pair<int, int> solve(int cap[])
{
    ans = INF;
    cost = INF;
    for (int i = 0; i <= cap[0]; ++i)
        for (int j = 0; j <= cap[1]; ++j)
            dist[i][j] = -1;
    bfs(cap);
    return {ans, cost};
}

第 41 题

（1）处应填（ ）。

{{ select(41) }}

• cap[0] - a - b
• cap[1] - a - b
• cap[2] - a - b
• a + b - cap[2]

第 42 题

（2）处应填（ ）。

{{ select(42) }}

• i == j && w[i] == 0
• i != j && w[i] > 0 && w[j] < cap[j]
• w[i] == 0 || w[j] == cap[j]
• i == j || w[i] == 0 || w[j] == cap[j]

第 43 题

（3）处应填（ ）。

{{ select(43) }}

• min(w[i], cap[j] - w[j])
• min(w[i], cap[i] - w[j])
• max(w[i], cap[j] - w[j])
• min(w[j], cap[i] - w[i])

第 44 题

（4）处应填（ ）。

{{ select(44) }}

• dist[na][nb] = cur + 1;
• dist[na][nb] = cur;
• dist[a][b] = cur + 1;
• dist[na][nb] = 0;

第 45 题

（5）处应填（ ）。

{{ select(45) }}

• na > 0 && (na < ans || (na == ans && cur + 1 < cost))
• na > 0 && na < ans
• na < ans || (na == ans && cur + 1 < cost)
• na > 0 && na < ans && cur + 1 < cost