CSP-J2026 初赛模拟卷01

ID: 10117

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

bitworld

标签>

CSP-J

初赛

模拟

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

在 C++ 中，若希望函数内的局部变量在多次函数调用之间保留上一次的值，应使用哪个关键字？

const
static
extern
register

二进制数 $(110101)_2$ 与十六进制数 $(1A)_{16}$ 的和对应的十进制值是？

已知 int x = 5;，下面哪一项可以正确声明一个引用变量 r，使其引用 x？

int r = &x;
int &r = x;
int *r = x;
int &&r = &x;

一个空栈依次将 $1, 2, 3, 4, 5$ 入栈，下面哪个序列不可能作为出栈序列？

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

一棵有 31 个结点的满二叉树，其叶子结点个数为？

已知一棵二叉树的前序遍历为 A B D E C F，中序遍历为 D B E A C F，则其后序遍历为？

D E B F C A
D B E F C A
E D B F C A
D E B C F A

一个有 8 个顶点、10 条边的无向连通图，至少删除多少条边后可以变成一棵树？

下列排序算法的常见实现中，通常不稳定的是？

冒泡排序
简单选择排序
直接插入排序
归并排序

有 4 名男生和 3 名女生，从中选出 3 人组成小组，要求至少有 1 名女生，共有多少种选法？

后缀表达式 3 4 + 5 * 6 - 对应的中缀表达式是？

$3 + 4 \times 5 - 6$
$(3 + 4) \times (5 - 6)$
$(3 + 4) \times 5 - 6$
$3 + 4 \times (5 - 6)$

在 C++ 中，表达式 (char)('A' + 5) 的值是？

'E'
'F'
'G'
'5'

对含有 2026 个元素的有序数组进行二分查找，最坏情况下最多需要比较多少次？

一个不含自环的有向图有 6 个顶点，若用邻接矩阵表示，矩阵中最多可能有多少个非零元素？

有 6 个字符，其出现频率分别为 $5, 7, 10, 15, 20, 43$ 。若用哈夫曼编码，频率为 7 的字符编码长度为？

下面哪一个通常不是编译器？

GCC
Clang
MSVC
Chrome

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分） (1)

#include <iostream>
using namespace std;

int f(int x) {
    int s = 0;
    while (x) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

int g(int x) {
    int r = 0;
    while (x) {
        r = r * 10 + x % 10;
        x /= 10;
    }
    return r;
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << " " << g(n) << endl;
    return 0;
}

假设输入的 $n$ 是不超过 1000000 的正整数。

判断题

当输入为 1203 时，程序输出为 6 3021。

正确
错误

对任意合法输入 $n$ ，都有 $g(g(n)) = n$ 。

正确
错误

对任意合法输入 $n$ ，都有 $f(n) = f(g(n))$ 。

正确
错误

选择题

当输入为 100200 时，程序输出为？

3 200100
3 2001
4 2001
4 1002

该程序的时间复杂度最准确地表示为？

$O(1)$
$O(n)$
$O(\log n)$
$O(n \log n)$

(2)

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

bool ck(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char t = st.top();
            st.pop();

            if (c == ')' && t != '(') return false;
            if (c == ']' && t != '[') return false;
            if (c == '}' && t != '{') return false;
        }
    }
    return st.empty();
}

int main() {
    string s;
    cin >> s;
    cout << ck(s) << endl;
    return 0;
}

假设输入字符串只包含 (、)、[、]、{、} 这 6 种字符。

判断题

当输入为 ([]{}) 时，程序输出为 1。

正确
错误

只要字符串中每种左括号和右括号数量分别相等，程序就一定输出 1。

正确
错误

若程序输出为 1，则输入字符串长度一定是偶数。

正确
错误

选择题

当输入为 ([)] 时，程序输出为？

0
1
true
false

当输入为 {[()][]} 时，程序输出为？

0
1
8
false

设输入字符串长度为 $n$ ，该程序的时间复杂度为？

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

(3)

#include <iostream>
using namespace std;

int a[10][10], dp[10][10];

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

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

    if (a[1][1]) dp[1][1] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!a[i][j]) {
                dp[i][j] = 0;
                continue;
            }
            if (i == 1 && j == 1) continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

假设 $1 \le n, m \le 8$ ，输入的 $a_{ij}$ 只可能为 0 或 1。其中 1 表示该格子可以经过，0 表示该格子不能经过。

判断题

如果 $a_{11} = 0$ ，程序一定输出 0。

正确
错误

程序中的 $dp_{ij}$ 表示从左上角走到位置 $(i, j)$ 的合法路径数量。

正确
错误

若将两层循环改为外层枚举 $j$ ，内层枚举 $i$ ，程序输出结果总是不变。

正确
错误

选择题

若输入为：

程序输出为？

若输入为：

程序输出为？

若 $n = m = 4$ ，且所有 $a_{ij}$ 都为 1，程序输出为？

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

（1）下面程序使用插入排序将数组从小到大排序，请补全程序。

#include <iostream>
using namespace std;

int a[1005];

void ins(int n) {
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int j = ①;
        while (j >= 0 && ②) {
            a[j + 1] = ③;
            ④;
        }
        ⑤;
    }
}

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

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

    ins(n);

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

    return 0;
}

① 处应填？

0
i
i - 1
n - 1

② 处应填？

a[j] < x
a[j] > x
a[i] > x
j > x

③ 处应填？

a[j + 1]
x
a[j]
a[i]

④ 处应填？

i++
j++
i--
j--

⑤ 处应填？

a[j] = x
a[j + 1] = x
a[i + 1] = x
x = a[j + 1]

（2）下面程序用数组模拟一个队列，支持三种操作：

1 x：将 $x$ 加入队尾；
2：若队列非空，弹出队首；
3：若队列非空，输出队首元素，否则输出 empty。

请补全程序。

#include <iostream>
using namespace std;

int q[1005];
int hd = 0, tl = 0;

void ps(int x) {
    q[①] = x;
    ②;
}

void pp() {
    if (③) ④;
}

bool em() {
    return ⑤;
}

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

    while (m--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            ps(x);
        } else if (op == 2) {
            pp();
        } else {
            if (em()) cout << "empty" << endl;
            else cout << q[hd] << endl;
        }
    }

    return 0;
}

假设操作次数不超过 1000，不会因为入队次数过多导致数组越界。

① 处应填？

hd
tl
tl + 1
hd + 1

② 处应填？

hd++
tl++
hd--
tl--

③ 处应填？

hd < tl
hd == tl
hd > tl
tl == 0

④ 处应填？

tl++
hd++
tl--
hd--

⑤ 处应填？

hd < tl
hd > tl
hd == tl
q[hd] == q[tl]

#10117. CSP-J2026 初赛模拟卷01

还没有账户？

登录