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

本卷为 CSP-J 部分，共45题，满分100分。判断题选择“正确/错误”。不含原卷的S组附加题。

一、单项选择题（15题，每题2分，共30分）

第1题

一个正整数在二进制下有100位，则它在十六进制下有（　）位。

{{ select(1) }}

• 7
• 13
• 25
• 不能确定

第2题

对长度为 $n$ 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为（　）。

{{ select(2) }}

• $\dfrac n4$
• $\dfrac{n-1}{2}$
• $\dfrac n2$
• $\dfrac{n+1}{2}$

第3题

设有一个含有13个元素的哈希表，哈希函数是：H(key) = key % 13。用线性探查法解决冲突，则对于序列 {2、8、31、20、19、18、53、27}，18应放在下标为（　）的位置。

{{ select(3) }}

• 0
• 4
• 5
• 9

第4题

使用邻接表表示一个简单有向图，图中包含 $n$ 个顶点、$m$ 条边，则该出边表中结点的个数为（　）。

{{ select(4) }}

• $n+m$
• $n\times(n-1)$
• $m$
• $n\times m$

第5题

对于一个包含 n 个结点和 m 条边的有向无环图，其拓扑排序的结果有（　）种可能。

{{ select(5) }}

• 只有1种
• 最多 n 种
• 等于 n - m 种
• 以上都不对

第6题

如果一棵二叉搜索树的后序遍历序列是 2, 5, 4, 8, 12, 10, 6，那么该树的前序遍历是（　）。

{{ select(6) }}

• 6, 4, 2, 5, 10, 8, 12
• 6, 4, 5, 2, 10, 12, 8
• 2, 4, 5, 6, 8, 10, 12
• 12, 8, 10, 5, 2, 4, 6

第7题

一棵二叉树的后序遍历序列为 H I D E B F G C A，中序遍历序列为 H D I B E A F C G，则其先序遍历序列为（　）。

{{ select(7) }}

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

第8题

具有6个结点的二叉树，左右子树有序，即区分左右子树，共有（　）种不同的形态。

{{ select(8) }}

• 42
• 90
• 132
• 720

第9题

一个无向图有8个顶点、7条边，且该图连通。则该图（　）。

{{ select(9) }}

• 一定是树
• 一定是环
• 一定含有回路
• 不可能是连通图

第10题

判断一个有 $n$ 个顶点的无向图是否为树，下列说法正确的是（　）。

{{ select(10) }}

• 只要边数等于 $n-1$ 就是树
• 只要连通且边数等于 $n-1$ 就是树
• 只要无环就是树
• 任意两点之间有且仅有一条简单路径，是树的充分条件但不是必要条件

第11题

在一棵以结点 1 为根的树中，结点 a 和结点 b 的最近公共祖先 LCA 是结点 c，a、b、c 两两不同，且 c ≠ 1。那么下列哪个 LCA 组合是不可能出现的（　）。

{{ select(11) }}

• LCA(a, c) = c
• LCA(b, c) = c
• LCA(LCA(a, b), c) = c
• LCA(a, 1) = c

第12题

若 $p$ 是大于2的质数，下列结论一定正确的是（　）。

{{ select(12) }}

• $p$ 与任意整数都互质
• $p$ 与任意与它不同的质数都互质
• $p$ 一定是2的幂
• $p+1$ 一定是质数

第13题

任意取2027个整数，其中一定能找到两个数，使它们的差能被2026整除。这一结论成立的原因是（　）。

{{ select(13) }}

• 2027个数除以2026的余数中必有两个相同
• 2027个数中必有两个相等
• 任意两个整数之差都能被4整除
• 2027大于2026，所以必存在倍数关系

第14题

有5个红球和5个蓝球，除了颜色之外完全相同。将这10个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法（　）。

{{ select(14) }}

• 25
• 30
• 6
• 120

第15题

以下哪个命令，在Linux环境下能将一个名为 std.cpp 的C++源文件编译并生成一个名为 std 的可执行文件（　）。

{{ select(15) }}

• g++ std.exe -o std.cpp
• g++ -o std.cpp std
• g++ -o std std.cpp
• g++ std.bat -o std.cpp

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

阅读程序第1题

阅读下面的程序，完成第16—21题。

int solve(int n)
{
    int ans = 0;
    while(n > 0)
    {
        if(n > 9) ans += 9;
        else ans += n;

        n /= 10;
    }
    return ans;
}

第16题

对于任意 n ≥ 1，solve(n) 随 n 增大而严格增大（ ）。

{{ select(16) }}

• 正确
• 错误

第17题

solve(100) = 19（ ）。

{{ select(17) }}

• 正确
• 错误

第18题

若 n 的位数为 L，首位数字为 d，则 solve(n) = (L - 1) × 9 + d（ ）。

{{ select(18) }}

• 正确
• 错误

第19题

solve(2026) 的值是（ ）。

{{ select(19) }}

• 27
• 28
• 29
• 30

第20题

若 solve(x) - solve(98) = 3，则 x 可能是（ ）。

{{ select(20) }}

• 200
• 300
• 400
• 500

第21题

若 solve(n) = 36，则 n 的位数和首位数字可能是（ ）。

{{ select(21) }}

• 3位数，首位9
• 4位数，首位9
• 4位数，首位8
• 5位数，首位1

阅读程序第2题

阅读下面的程序，完成第22—28题。

int length(int x)
{
    int c = 0;
    while (x > 0) {
        c++;
        x /= 10;
    }
    return c;
}

int select(int n, int k)
{
    if (k > 0)
        return select(n/10, k-1);
    else
        return n % 10;
}

int solve(int k)
{
    int n = 1;
    while (k > length(n)) {
        k -= length(n);
        n++;
    }
    return select(n, length(n) - k);
}

第22题

select(123, 5) 的返回值为 3。

{{ select(22) }}

• 正确
• 错误

第23题

当 k 增大时，solve(k) 的返回值一定变大（ ）。

{{ select(23) }}

• 正确
• 错误

第24题

length(x) 的时间复杂度是 $\Theta(x)$（ ）。

{{ select(24) }}

• 正确
• 错误

第25题

solve(100) 执行完 while 循环后，在执行 select(n, length(n) - k) 时，n 的值是55（ ）。

{{ select(25) }}

• 正确
• 错误

第26题

若 solve(k) = 7 且 k 是一个两位数，则 k 的值可能是（ ）。

{{ select(26) }}

• 25
• 17
• 27
• 37

第27题

若 solve(k) = 0，则 k 的最小值是（ ）。

{{ select(27) }}

• 10
• 11
• 12
• 20

第28题

关于 select(n, k) 函数，以下说法正确的是（ ）。

{{ select(28) }}

• 当k为负数时，函数会无限递归
• 当k大于n的位数时，函数会返回n的最高位
• 函数返回n的十进制表示中，低位往高位数的第k+1位
• 函数返回n的十进制表示中，高位往低位数的第k+1位

阅读程序第3题

阅读下面的程序，完成第29—35题。

void print(std::string in)
{
    int q[2000] = {10, 0};
    int out[2000] = {0};
    int size = 1;
    for (char c : in)
    {
        int r = 0;
        for (int i = 0; i < size; ++i) {
            r = r * 10 + q[i];
            q[i] = r / 2;
            r = r % 2;
        }
        while (r > 0) {
            r = r * 10;
            q[size] = r / 2;
            size++;
            r = r % 2;
        }

        int d = c - '0';
        int i = size - 1;
        while (true) {
            out[i] += q[i] * d;
            int carry = out[i] / 10;
            out[i] %= 10;
            if (i > 0) {
                --i;
                out[i] += carry;
            }
            else {
                break;
            }
        }
    }

    while (size > 1 && out[size-1] == 0) {
        size--;
    }
    for (int i = 0; i < size; ++i) {
        std::cout << out[i];
    }
}

第29题

如果输入是 "0"，那么程序会输出 0。（ ）

{{ select(29) }}

• 正确
• 错误

第30题

如果输入是 "111"，那么程序会输出 675。（ ）

{{ select(30) }}

• 正确
• 错误

第31题

out 数组不需要初始化清零程序也能正确运行。（ ）

{{ select(31) }}

• 正确
• 错误

第32题

若输入的数据长度为 $n$，该程序的时间复杂度为（ ）。

{{ select(32) }}

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

第33题

程序的主要功能是（ ）。

{{ select(33) }}

• 将二进制整数转换为十进制整数
• 将二进制小数转换为十进制的小数部分
• 将十进制整数转换为二进制
• 计算输入数字字符的累加和

第34题

在循环中，语句 r = r * 10 + q[i] 的作用是（ ）。

{{ select(34) }}

• 将数组q直接拼接为一个整数
• 模拟除法运算中的被除数（用于除以2）
• 计算除法的余数
• 扩展数组q的小数部分

第35题

如果输出是 375，那么输入应该是（ ）。

{{ select(35) }}

• 001
• 011
• 101
• 111

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

完善程序（1）：路径边权异或最大值

给定含有 $N=2^4$ 个顶点的完全图，顶点编号为 $0$ 到 $N-1$。顶点 $x$ 到 $y$ 的边的权重为 G[x][y]。

请找出一条不重复经过任何点的路径，从顶点 $0$ 出发到顶点 $N-1$ 结束，使路径上所有边权的异或值尽可能大。

题意说明： 本题按有向完全图理解，G[x][y] 是从 x 到 y 的边权，反向边权不一定相同。对角线 G[x][x] 不表示可走的边，其数值不作保证，不能依赖它为0。边权为非负整数，计算在 int 范围内。初始调用为 dfs(0, 0)。回答第36—40题。

const int N = 1 << 4;
int G[N][N];
bool visited[N] = {false};

int dfs(int node, int path)
{
    if (_____(1)_____)
    {
        return _____(2)_____;
    }

    int best = 0;
    visited[node] = true;
    for (int next = 0; next < _____(3)_____; ++next)
    {
        if (_____(4)_____)
        {
            int val = dfs(next, _____(5)_____);
            if (val > best) {
                best = val;
            }
        }
    }
    visited[node] = false;
    return best;
}

第36题

（1）处应填（ ）。

{{ select(36) }}

• node == N - 1
• node == 0
• visited[node]
• path > 0

第37题

（2）处应填（ ）。

{{ select(37) }}

• 0
• path
• G[node][0]
• path ^ G[node][N-1]

第38题

（3）处应填（ ）。

{{ select(38) }}

• N
• N - 1
• N + 1
• N / 2

第39题

（4）处应填（ ）。

{{ select(39) }}

• visited[next] || next != node
• !visited[next]
• next != node
• !visited[next] || next != 0

第40题

（5）处应填（ ）。

{{ select(40) }}

• path + G[node][next]
• path + G[next][node]
• path ^ G[next][node]
• path ^ G[node][next]

完善程序（2）：传花取分游戏

两个玩家玩一个游戏，每个人的目标是让自己的总分尽可能多。游戏共有 $N=2^8$ 轮，每轮的分数在游戏开始前给定，依次记为 $A_0,A_1,\ldots,A_{N-1}$。

每轮游戏中，手上有花的人可以选择：

• 保留花：把这一轮的分数送给对方；下一轮花仍在自己手上。
• 取走这一轮的分数：这一轮得分归自己；下一轮花交给对方。

开始时持花的人称为先手。双方都采用最优策略，请补全程序，返回先手能获得的总分。所有分数及累加结果均在 int 范围内。回答第41—45题。

const int N = 1 << 8;
int s[N + 1];

int f(int n)
{
    if (_____(1)_____)
    {
        return 0;
    }
    else
    {
        int flower = f(n-1);
        return std::max(flower, _____(2)_____);
    }
}

int solve(int A[])
{
    s[0] = 0;
    for (int i = 0; i < N; ++i)
    {
        s[_____(3)_____] = s[i] + A[_____(4)_____];
    }
    return f(_____(5)_____);
}

第41题

（1）处应填（ ）。

{{ select(41) }}

• n == 0
• n == N
• n > N
• n <= N

第42题

（2）处应填（ ）。

{{ select(42) }}

• s[n]
• s[n-1]
• s[n] - flower
• s[n-1] - flower

第43题

（3）处应填（ ）。

{{ select(43) }}

• i+1
• i-2
• i-1
• i+2

第44题

（4）处应填（ ）。

{{ select(44) }}

• i
• i+1
• N-i
• N-i-1

第45题

（5）处应填（ ）。

{{ select(45) }}

• 0
• 1
• N-1
• N