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

本卷共 43 个独立小题，满分 100 分。

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

第 1 题

下列不属于计算机网络功能的是（ ）。

{{ select(1) }}

• 提高系统处理能力
• 提高系统可靠性
• 资源共享
• 使各计算机相对独立

第 2 题

已知有一个分辨率为 2048×1024 的图像，其储存大小为 8MB，请问这张图片的位深度为（ ）。

{{ select(2) }}

• 8
• 16
• 32
• 64

第 3 题

一个 16 位无符号二进制数的表示范围是（ ）。

{{ select(3) }}

• 0～65536
• 0～65535
• -32768～32767
• -32768～32768

第 4 题

A、B 均为一个 8 位二进制整数，A=0110 0101，B=1111 0000，则 A 异或 B 有什么结果（ ）？

{{ select(4) }}

• 结果还是 A
• 结果还是 B
• A 的前 4 位不变，后 4 位取反
• A 的前 4 位取反，后 4 位不变

第 5 题

把二进制数 1101 转换为八进制数，正确的结果是（ ）。

{{ select(5) }}

• 15
• 13
• 11
• 10

第 6 题

执行下列语句段后，i 的值为（ ）。

int f(int x) {
    return ((x > 0) ? x * f(x - 1) : 2);
}
int i = f(f(1));

{{ select(6) }}

• 8
• 4
• 2
• 无限递归

第 7 题

下列程序中，正确输出 100 99 98 97 … 3 2 1 这 100 个自然数的是（ ）。

{{ select(7) }}

• int n = 100; while (n--) { cout << n << " "; }
• int n = 101; while (n--) { cout << n << " "; }
• int n = 100; while (n) { cout << n-- << " "; }
• int n = 101; while (n) { cout << n-- << " "; }

第 8 题

下面代码的正确输出是（ ）。

#include <bits/stdc++.h>
using namespace std;

struct OIer {
    string name;
    int age;
    void coding() {
        printf("cool cool");
    }
};

int main() {
    OIer *p, *q;
    OIer a, b;
    p = &a, q = &b;
    p->name = "alice";
    p->age = 10;
    q->name = "bob";
    q->age = 11;
    swap(p, q);
    cout << p->name << " " << p->age;
    return 0;
}

{{ select(8) }}

• alice 10
• alice 11
• bob 10
• bob 11

第 9 题

清明扫墓，一队人拎着杯子和桶排队接水，大家决定先让盛水少的人先接，这样大家整体能最快接完水。这一想法最接近哪种算法思想（ ）。

{{ select(9) }}

• 分治
• 模拟
• 枚举
• 贪心

第 10 题

使用数组 a[0…5] 实现循环队列时，如果队首 front 和队尾 rear 当前分别为 5 和 1，接下来删除一个元素再加入两个元素，front 和 rear 的值分别为（ ）。

{{ select(10) }}

• 4 和 3
• 0 和 3
• 4 和 5
• 0 和 5

第 11 题

一棵深度为 d 的完全二叉树，但不是满二叉树，根结点的深度为 1，则该树最少有多少个叶子结点，最多有多少个叶子结点（ ）。

{{ select(11) }}

• 2^(d-1)+2，2^d-1
• 2^(d-2)+2，2^(d-1)
• 2^(d-2)+1，2^(d-1)-1
• 2^(d-2)，2^(d-1)-1

第 12 题

一个无向简单连通图 G 有 n 个节点和 m 条边，m 的取值范围是（ ）。

{{ select(12) }}

• m≥n-1 且 m≤n(n-1)/2
• m≥n 且 m≤n(n+1)/2
• m≤n-1
• m≥n(n-1)/2

第 13 题

将 3 颗相同的苹果放入 3 个不同的盘子中，盘子可以为空，共有（ ）种方法。

{{ select(13) }}

• 3
• 6
• 10
• 12

第 14 题

一个志愿者小组有 45 个人，每周他们都会抽出各自的一天时间去敬老院帮助老人。那么，每周去的人数最多的那天，至少会有（ ）人。

{{ select(14) }}

• 6
• 7
• 8
• 9

第 15 题

单词 hello 的字母顺序写错了，则错误的方案数有多少种（ ）。

{{ select(15) }}

• 119 种
• 36 种
• 59 种
• 48 种

二、程序阅读题（第 16—18 大题，共 18 个小题，40 分）

程序阅读（区间内恰含 m 种不同元素）

数据范围：1≤n≤10^6，1≤a_i≤2×10^3

#include <bits/stdc++.h>
using namespace std;
int flag[2005], n, m, a[1000005], cnt;
int ansL, ansR;
bool check(int x) {
    cnt = 0;
    memset(flag, 0, sizeof flag);
    for (int i = 1; i <= x; i++) {
        if (!flag[a[i]]) cnt++;
        flag[a[i]]++;
    }
    if (cnt == m) {
        ansL = 1, ansR = x;
        return 1;
    }
    int y = 1;
    while (x < n) {
        flag[a[y]]--;
        if (!flag[a[y]]) cnt--;
        y++, x++;
        flag[a[x]]++;
        if (flag[a[x]] == 1) cnt++;
        if (cnt == m) {
            ansL = y, ansR = x;
            return 1;
        }
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    printf("%d %d\n", ansL, ansR);
    return 0;
}

第 16 题

程序输入的 m 不能超过 2004。

{{ select(16) }}

• 正确
• 错误

第 17 题

若输入的 n<m，会输出 0 0。

{{ select(17) }}

• 正确
• 错误

第 18 题

将第 37 行代码修改为 else l=mid，程序输出不会改变。

{{ select(18) }}

• 正确
• 错误

第 19 题

若输入样例为 3 3 / 1 2 3，那么把程序第 16 行至第 27 行删去，输出不会改变。

{{ select(19) }}

• 正确
• 错误

第 20 题

若输入为 12 5 / 2 5 3 1 3 2 4 1 1 5 4 3，输出为（ ）。

{{ select(20) }}

• 1 7
• 2 8
• 1 12
• 2 7

第 21 题

程序的时间复杂度近似为（ ）。

{{ select(21) }}

• O(n log n)
• O(log n)
• O(n^2)
• O(n^1.3)

二、程序阅读题（第 16—18 大题，共 18 个小题，40 分）

程序阅读（和等于异或的子数组计数）

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
long long a[N], s[N], x[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        s[i] = s[i - 1] + a[i];
        x[i] = x[i - 1] ^ a[i];
    }
    long long ans = 0;
    int L = 1, R = 1;
    for (; R <= n; R++) {
        while (L <= R && (s[R] - s[L - 1]) != (x[R] ^ x[L - 1])) L++;
        if (L > n) break;
        ans += R - L + 1;
    }
    cout << ans;
    return 0;
}

第 22 题

将第 13 行代码改为 x[i] ^= a[i]，程序运行结果不变。

{{ select(22) }}

• 正确
• 错误

第 23 题

将第 16 行代码中的 R=1 改为 R=0，程序运行结果改变。

{{ select(23) }}

• 正确
• 错误

第 24 题

删除第 19 行代码后，程序运行结果不产生变化。

{{ select(24) }}

• 正确
• 错误

第 25 题

输入 4 / 2 5 4 6，输出为（ ）。

{{ select(25) }}

• 2
• 3
• 4
• 5

第 26 题

输入 9 / 0 0 0 0 0 0 0 0 0，输出为（ ）。

{{ select(26) }}

• 0
• 9
• 36
• 45

第 27 题

该算法的复杂度为（ ）。

{{ select(27) }}

• O(n^2)
• O(n log n)
• O(n)
• O(n^3)

二、程序阅读题（第 16—18 大题，共 18 个小题，40 分）

程序阅读（判断是否可选根成为完整二叉树）

输入不超过 10^6 的正整数 n，随后输入 n-1 条边构建一棵树。保证存在某个点作为根后，每个点的子结点数量不超过 2。

#include <iostream>
#include <vector>
using namespace std;
vector<int> edge[1000005];
int max_depth;
void f(int now, int fa, int depth) {
    max_depth = max(max_depth, depth);
    for (int i = 0; i < edge[now].size(); i++) {
        if (edge[now][i] == fa)
            continue;
        f(edge[now][i], now, depth + 1);
    }
    return;
}
int main() {
    int n;
    cin >> n;
    int t = n;
    while (--t) {
        int u, v;
        cin >> u >> v;
        edge[u].emplace_back(v);
        edge[v].emplace_back(u);
    }
    int star = 0, num = 0;
    for (int i = 1; i <= n; i++) {
        if (edge[i].size() == 2) {
            star = i;
            num++;
        }
    }
    if (num == 1) {
        f(star, 0, 1);
        cout << "yes " << max_depth;
    } else
        cout << "no";
    return 0;
}

第 28 题

若 n=1，运行上述程序输出为 no。

{{ select(28) }}

• 正确
• 错误

第 29 题

将第 33 行语句改为 f(star,1,1)，并不改变程序运行结果。

{{ select(29) }}

• 正确
• 错误

第 30 题

若 n=666666，运行上述程序可能输出 yes。

{{ select(30) }}

• 正确
• 错误

第 31 题

下列哪组输入能输出 yes（每组首数为 n，后面为 n-1 条边的端点序列）？

{{ select(31) }}

• 11 4 1 9 3 6 7 5 10 2 8 2 5 5 11 1 9 1 6 4 2
• 8 6 3 7 5 8 6 6 2 7 4 3 1 8 7
• 6 1 2 2 3 3 4 4 5 5 6
• 5 1 2 3 4 1 3 3 5

第 32 题

上述程序最准确的时间复杂度为（ ）。

{{ select(32) }}

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

第 33 题

若 n=10^6-1，则输出的 max_depth 可能的最小值和最大值分别是多少（ ）。

{{ select(33) }}

• 60，999999
• 21，499999
• 20，500000
• 13，500001

三、完善程序题（第 19—20 大题，共 10 个小题，30 分）

完善程序（双向冒泡排序）

为 n 个数进行双向冒泡排序，求最终排序结果。

#include <iostream>
using namespace std;
void bidirectionalBubbleSort(int a[], int n) {
    int low = 0, high = ①;
    bool flag = true;
    while (②) {
        flag = false;
        for (int i = low; i < high; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                ③;
            }
        }
        high--;
        for (int i = high; i > low; i--) {
            if (a[i] < a[i - 1]) {
                swap(a[i], a[i - 1]);
                flag = true;
            }
        }
        ④;
    }
}
int main() {
    int n, a[500] = {};
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    bidirectionalBubbleSort(a, n);
    for (int i = 0; i < n; i++) {
        cout << ⑤ << " ";
    }
    return 0;
}

第 34 题

①处应填（ ）。

{{ select(34) }}

• n
• n+1
• n-1
• n/2

第 35 题

②处应填（ ）。

{{ select(35) }}

• low<high && flag==true
• low>high && flag==true
• low<high && flag==false
• low>high && flag==false

第 36 题

③处应填（ ）。

{{ select(36) }}

• flag=false
• flag=low
• flag=high
• flag=true

第 37 题

④处应填（ ）。

{{ select(37) }}

• low++
• low--
• high++
• high--

第 38 题

⑤处应填（ ）。

{{ select(38) }}

• i
• a[i]
• a[i+1]
• a[i-1]

三、完善程序题（第 19—20 大题，共 10 个小题，30 分）

完善程序（区间不完美度之和）

题目描述

如果一个数等于它的所有因数（小于自身的）之和，那么这个数就是完美的。例如，28 是完美的，因为 $28=1+2+4+7+14$。基于这个定义，我们将数字 $n$ 的不完美度定义为 $f(n)$，它等于 $n$ 与 $n$ 的所有因数（小于 $n$ 的）之和的差的绝对值，因此完美数的不完美度为 0，其余自然数的不完美度都大于 0。

例如：

$f(6)=|6-(1+2+3)|=0$

$f(11)=|11-1|=10$

$f(24)=|24-(1+2+3+4+6+8+12)|=12$

写一个程序，对于正整数 $A$ 和 $B$，计算 $A$ 和 $B$ 之间所有数字不完美度之和，即 $f(A)+f(A+1)+\cdots+f(B)$。

输入描述

第一行输入包含两个整数 $A$ 和 $B$（$1\le A\le B\le 10^7$），表示题目中的 $A$ 和 $B$。

输出描述

输出一个整数，表示 $f(A)+f(A+1)+\cdots+f(B)$。

输入样例 #1

1 9

输出样例 #1

21

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e7 + 5;
LL ans;
int a, b, len;
int prim[N], psum[N], s[N];
bool vis[N];
void sieve(int x) {
    for (int i = 2; ①; i++) {
        if (!vis[i]) {
            prim[++len] = ②;
            psum[i] = s[i] = ③;
        }
        for (int j = 1; j <= len && i * prim[j] <= x; j++) {
            vis[i * prim[j]] = 1;
            if (i % prim[j] == 0) {
                psum[i * prim[j]] = ④;
                s[i * prim[j]] = s[i] / psum[i] * psum[i * prim[j]];
                break;
            }
            psum[i * prim[j]] = prim[j] + 1;
            s[i * prim[j]] = s[i] * psum[i * prim[j]];
        }
    }
}
int main() {
    scanf("%d%d", &a, &b);
    sieve(max(a, b));
    s[1] = 1;
    for (int i = a; i <= b; i++)
        ans += abs(s[i] - ⑤);
    printf("%lld\n", ans);
    return 0;
}

第 39 题

①处应填（ ）。

{{ select(39) }}

• i<x
• i*i<=x
• i<=x
• i*i<x

第 40 题

②处应填（ ）。

{{ select(40) }}

• psum[i]
• i
• s[i]
• i+1

第 41 题

③处应填（ ）。

{{ select(41) }}

• prim[i]
• i
• prim[len]
• i+1

第 42 题

④处应填（ ）。

{{ select(42) }}

• psum[i]*prim[j]+1
• i
• prim[j]
• psum[i]

第 43 题

⑤处应填（ ）。

{{ select(43) }}

• i
• 2*i
• psum[i]
• psum[prim[j]]