[CSPJ2609 初赛] 模拟题二十

ID: 770

客观题

尝试: 6

已通过: 1

难度: 10

上传者:

Fan_z

标签>

csp-j

初赛

一、单项选择题(每题 $2$ 分,共 $30$ 分)

在 C++ 中,下列哪个关键字用于在编译时确定一个表达式的值,并且该值不可更改?( )

const
constexpr
static
volatile

某数在二进制下为 $1101.101$ ,其十进制值为?( )

$13.625$
$13.5$
$11.625$
$11.5$

下列存储器层次中,访问速度最快的是?( )

L1 Cache
主存 (RAM)
SSD
寄存器

一个算法的时间复杂度为 $O(n\log_2 n)$ ,若 $n$ 增大到 $16$ 倍,则运行时间大约变为原来的多少倍?( )

$16$
$256$
$64$
$128$

在 C++ 中,delete[] 用于?( )

释放单个对象
释放数组对象
释放静态变量
释放栈变量

根高度为 $1$ ,高度为 $6$ 的满四叉树总节点数为( )

$1024$
$4096$
$512$
$1365$

一个班级有 $8$ 名男生和 $6$ 名女生,从中选 $5$ 人,要求男女均不少于 $2$ 人,方案数是?( )

$5040$
$1940$
$1400$
$2100$

一个 $32$ 位无符号整数能表示的最大十进制整数是?( )

$2^{32}$
$2^{32}-1$
$2^{31}-1$
$2^{31}$

后缀表达式 9 4 2 * - 7 3 / + 对应中缀表达式为( )

$(9-4*2)+(7/3)$
$9-(4*2+7)/3$
$(9-4)(2+7)/3$
$9-4*(2+7/3)$

有向图边集 $\{(2,3),(1,2),(1,4),(3,4)\}$ ,属于合法拓扑排序的是( )

$1,2,3,4$
$1,4,2,3$
$1,2,4,3$
$1,3,2,4$

某算法的时间复杂度为 $O(2^n)$ ,当 $n=20$ 时运行时间为 $1$ 秒,则 $n=30$ 时大约需要多少秒?( )

约 $1000$ 秒
约 $1024$ 秒
约 $30$ 秒
约 $2^{30}$ 秒

下列不属于操作系统内核软件的是( )

macOS
FreeBSD
MySQL
HarmonyOS

设 int a=12(二进制 $1100$ ),执行 a = a >> 2 | a << 2,a 结果为( )

$48$
$3$
$15$
$51$

要在双向链表中,将新节点 $p$ 插入到节点 $q$ 之后,下列操作序列正确的是?( )

p->prev = q; p->next = q->next; q->next->prev = p; q->next = p;
p->prev = q; p->next = q->next; q->next = p; q->next->prev = p;
p->prev = q; p->next = q->next; if(q->next) q->next->prev = p; q->next = p;
p->prev = q; p->next = q->next; q->next = p; if(p->next) p->next->prev = p;

用 Huffman 编码对频率分别为 $3,5,6,9,12$ 的符号编码,其平均码长的理论下界(香农熵)最接近?( )

$2.1$
$2.3$
$2.5$
$2.7$

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

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。判断题正确填「正确」,错误填「错误」。

阅读程序(一)

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<long long> fib;
    fib.push_back(1), fib.push_back(2);
    while (fib.back() <= 1e9) {
        int sz = fib.size();
        fib.push_back(fib[sz - 1] + fib[sz - 2]);
    }
    long long n;
    cin >> n;
    vector<long long> res;
    for (int i = fib.size() - 1; i >= 0; i--) {
        if (fib[i] <= n) {
            res.push_back(fib[i]);
            n -= fib[i];
        }
    }
    sort(res.begin(), res.end());
    cout << res[0];
    for (int i = 1; i < res.size(); i++) {
        cout << "+" << res[i];
    }
    return 0;
}

(1) 程序输出的序列中,任意两个相邻数字都是斐波那契数列中的相邻项。

正确
错误

(2) 程序的时间复杂度为 $O(\log n)$ 。

正确
错误

(3) 若输入 $n=10$ ,程序的输出是:( $2$ 分)

2+8
1+2+3+4
2+3+5
1+2+3+5

(4) 若输入 $n=100$ ,输出序列中最大的数字是:( $2$ 分)

$55$
$34$
$89$
$13$

(5) 程序的核心算法类似于:( )

动态规划
贪心算法
分治算法
回溯算法

(6) 若将程序中的斐波那契数列改为以 $1,1$ 开头(即 fib.push_back(1); fib.push_back(1);),输入 $n=7$ ,输出为:( )

1+1+5
1+2+3
1+6
2+5

阅读程序(二)

#include <bits/stdc++.h>
using namespace std;
int n, m, t[10005], x[10005], y[10005], dp[10005], ans;
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) cin >> t[i] >> x[i] >> y[i];
    for (int i = 0; i < m; ++i) {
        dp[i] = 1;
        for (int j = max(0, i - 2 * n); j < i; ++j) {
            int diff = t[i] - t[j];
            int dist = abs(x[i] - x[j]) + abs(y[i] - y[j]);
            if (dist <= diff) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

(1) 程序的时间复杂度为 $O(m^2)$ 。

正确
错误

(2) 交换内外两层循环顺序 for (int i = 0; i < m; ++i) 与 for (int j = max(0, i - 2 * n); j < i; ++j),程序运行结果不会改变。

正确
错误

(3) 如果 dist <= diff 条件成立,则从 $j$ 到 $i$ 一定可以在时间差内到达,但反过来不一定成立。

正确
错误

(4) 程序的核心算法是:( )

贪心算法
分治算法
回溯算法
动态规划

(5) 若输入 $n=5$ , $m=3$ ,数据为:( $2$ 分)

1 2 3
1 2 3
1 2 3

输出为:( )

(6) 若输入 $n=5$ , $m=4$ ,数据为:( $2$ 分)

输出为:( )

阅读程序(三)

#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char from, char to, char aux) {
    if (n == 0) return;
    hanoi(n - 1, from, aux, to);
    cout << from << "->" << n << "->" << to << '\n';
    hanoi(n - 1, aux, to, from);
}
int main() {
    int n;
    char a, b, c;
    cin >> n >> a >> b >> c;
    hanoi(n, a, b, c);
    return 0;
}

(1) 如果输入 3 A B C,程序会输出 $8$ 行移动步骤。

正确
错误

(2) 如果原来输入 3 A B C,现输入为 3 A C B,输出结果会完全相同。

正确
错误

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

正确
错误

(4) 程序的空间复杂度为 $O(n)$ 。

正确
错误

(5) 程序输出的移动步骤中,最大的盘子(编号 $n$ )只会移动一次。

正确
错误

(6) 若输入 2 A B C,程序输出为:( $2$ 分)

A->1->B A->2->C B->1->C
A->1->C A->2->B C->1->B
A->1->B A->2->C B->1->A
A->1->C A->2->B B->1->C

(7) 程序总共的递归调用次数(包括 $n=0$ 的调用)为:( )

$2^n-1$
$2^n$
$2^{n+1}-1$
$2^{n+1}$

(8) 若输入 3 A B C,第 $5$ 行输出为:( )

A->1->C
A->2->B
C->1->A
C->2->B

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

完善程序(一)

P1993 小 K 的农场

小 K 在 MC 里面建立了很多很多的农场,总共 $n$ 个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共 $m$ 个),以下列三种形式描述:

农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物;
农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物;
农场 $a$ 与农场 $b$ 种植的作物数一样多。

但是,由于小 K 的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

输入:第一行两个整数 $n$ 和 $m$ 。接下来 $m$ 行:

第一个数是 $1$ ,接下来三个整数 $a,b,c$ ,表示农场 $a$ 比农场 $b$ 至少多种植了 $c$ 个单位的作物;
第一个数是 $2$ ,接下来三个整数 $a,b,c$ ,表示农场 $a$ 比农场 $b$ 至多多种植了 $c$ 个单位的作物;
第一个数是 $3$ ,接下来两个整数 $a,b$ ,表示农场 $a$ 种植的数量和 $b$ 一样多。

若存在某种情况与记忆吻合,输出 Yes,否则输出 No。

样例:

Yes

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005, INF = 0x3f3f3f3f;
struct Edge {
    int to, weight;
};
int n, m;
vector<Edge> g[MAXN];
int dist[MAXN], cnt[MAXN], vis[MAXN];
bool spfa() {
    memset(dist, 0x3f, sizeof(dist));
    memset(cnt, 0, sizeof(cnt));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(0);
    ①;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to, w = g[u][i].weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    ②;
                    if (③) return false;
                }
            }
        }
    }
    return true;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int op, a, b, c;
        cin >> op;
        if (op == 1) {
            cin >> a >> b >> c;
            ④;
        } else if (op == 2) {
            cin >> a >> b >> c;
            ⑤;
        } else {
            cin >> a >> b;
            g[a].push_back({b, 0});
            g[b].push_back({a, 0});
        }
    }
    for (int i = 1; i <= n; i++) {
        g[0].push_back({i, 0});
    }
    if (spfa()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

(1) ① 处应填( )

dist[0] = 0, vis[0] = true, cnt[0]++
dist[1] = 1, vis[1] = true, cnt[1]++
dist[0] = 1, vis[0] = true, cnt[0]++
dist[1] = 0, vis[1] = true, cnt[1]++

(2) ② 处应填( )

vis[v] = false, cnt[v]++
vis[v] = true, cnt[v]++
vis[u] = false, cnt[u]++
vis[u] = true, cnt[u]++

(3) ③ 处应填( )

cnt[u] > n
cnt[u] < n
cnt[v] > n
cnt[v] < n

(4) ④ 处应填( )

g[a].push_back({a, c})
g[a].push_back({a, -c})
g[a].push_back({b, c})
g[a].push_back({b, -c})

(5) ⑤ 处应填( )

g[b].push_back({b, -c})
g[b].push_back({b, c})
g[b].push_back({a, -c})
g[b].push_back({a, c})

完善程序(二)

P4447 [AHOI2018 初中组] 分组

小可可的学校信息组总共有 $n$ 个队员,每个人都有一个实力值 $a_i$ 。现在要把 $n$ 个队员分成若干小组去参加比赛。每个小组的队员实力值必须连续,且一个队不需要两个实力相同的选手。例如 $[1,2,3,4,5]$ 合法; $[1,2,3,5]$ 不合法(不连续); $[0,1,1,2]$ 不合法(出现两个实力值为 $1$ 的选手)。

小可想给出一个合法分组方案,满足所有人都恰好分到一个小组,使得人数最少的组内人数最多,输出这个最大值。实力值可能是负数,分组数量没有限制。

输入两行:第一行正整数 $n$ ;第二行 $n$ 个整数 $a_i$ 。输出一行一个正整数。

样例:

7
4 5 2 3 -4 -3 -5

样例解释:分为 $2$ 组,一组实力值 $[4,5,2,3]$ ,一组 $[-4,-3,-5]$ ,最小组人数为 $3$ 。

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
int n, a[1000005];
int q[1000005], k[1000005], top, ans = 1e9;

void heapify(int i, int size) {
    int maxn = i, l = 2 * i, r = 2 * i + 1;
    if (l <= size && a[l] > a[maxn])
        maxn = l;
    if (r <= size && a[r] > a[maxn])
        maxn = r;
    if (maxn != i) {
        swap(a[i], a[maxn]);
        ①;
    }
}

void heapSort() {
    if (n <= 1) return;
    for (int i = n / 2; i >= 1; --i) {
        ②;
    }
    for (int i = n; i > 1; --i) {
        swap(a[1], a[i]);
        ③;
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    heapSort();
    q[0] = 1e9 + 1;
    for (int i = 1; i <= n; i++) {
        int l = 0, r = top;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (a[i] >= q[mid]) {
                l = mid;
            } else {
                ④;
            }
        }
        if (q[l] != a[i]) {
            k[++top] = 1, q[top] = a[i] + 1;
        } else {
            ⑤;
        }
    }
    for (int i = 1; i <= top; i++) ans = min(ans, k[i]);
    cout << ans << "\n";
    return 0;
}

(1) ① 处应填( )

heapify(l, size)
heapify(maxn, size / 2)
heapify(maxn, size)
heapify(r, size / 2)

(2) ② 处应填( )

heapify(0, i)
heapify(i, 0)
heapify(n, i)
heapify(i, n)

(3) ③ 处应填( )

heapify(1, i - 1)
heapify(0, i - 1)
heapify(0, i)
heapify(1, i)

(4) ④ 处应填( )

r = mid - 1
r = mid << 1
r = mid + 1
r = mid >> 1

(5) ⑤ 处应填( )

k[l]++, q[r]++
k[l]++, q[l]++
k[r]++, q[l]++
k[r]++, q[r]++

#770. [CSPJ2609 初赛] 模拟题二十

一、单项选择题(每题 222 分,共 303030 分)

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

单项选择题,每题 333 分,共 303030 分。

还没有账户？

登录

一、单项选择题(每题 $2$ 分,共 $30$ 分)

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