2022年 CSP-J 第一轮（入门级）

满分 100 分

时长 120 分钟

共 44 题

答题卡已答 0/44

已答正确错误编程题

选单项选择题（共 15 题，共 0 分）

以下哪种功能没有涉及 C++语言的面向对象特性支持：（）。

C++ 中构造一个 class 或 struct

C++ 中构造来源于同一基类的多个派生类

C++ 中调用用户定义的类成员函数

C++ 中调用 printf 函数

有 $6$ 个元素，按照 $6$、$5$、$4$、$3$、$2$、$1$ 的顺序进入栈 $S$，请问下列哪个出栈序列是非法的

4 5 3 1 2 6

2 3 4 1 5 6

5 4 3 6 1 2

3 4 6 5 2 1

运行以下代码片段的行为是（）。

int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

将 y 的值赋为 101

将 q 指向 x 的地址

将 x 的值赋为 201

将 p 指向 y 的地址

链表和数组的区别包括（）。

链表比数组能存储更多的信息

数组不能排序，链表可以

以上均正确

数组大小固定，链表大小可动态调整

对假设栈 $S$ 和队列 $Q$ 的初始状态为空。存在 $e_1$~$e_6$ 六个互不相同的数据，每个数据按照进栈 $S$、出栈 $S$、进队列 $Q$、出队列 $Q$ 的顺序操作，不同数据间的操作可能会交错。

已知栈 $S$ 中依次有数据 $e_1$、$e_2$、$e_3$、$e_4$、$e_5$ 和 $e_6$ 进栈，队列 $Q$ 依次有数据 $e_2$、$e_4$、$e_3$、$e_6$、$e_5$ 和 $e_1$ 出队列。则栈 $S$ 的容量至少是（）个数据。

$2$

$6$

$4$

$3$

对表达式 a+(b-c)*d 的前缀表达式为（），其中 +、-、* 是运算符。

abc-d*+

*+a-bcd

abc-+d

+a*-bcd

假设字母表 {$a, b, c, d, e$} 在字符串出现的频率分别为 $10$%, $15$%, $30$%, $16$%, $29$%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 $d$ 的编码长度为（）位。

$2$ 或 $3$

$1$

$3$

$2$

一棵有 $n$ 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 $1$ 个位置。若存储在数组第 $9$ 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（）。

$10$、$19$

$8$、$18$

$10$、$18$

$8$、$19$

考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（）个非零元素。

$N^{2}$

$N-1$

$N+1$

$N$

以下对数据结构的表述不恰当的一项为：（）。

栈的访问原则为后进先出，队列的访问原则是先进先出

队列常常被用于广度优先搜索算法。

图的深度优先遍历算法常使用的数据结构为栈

栈与队列存在本质不同，无法用栈实现队列。

以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（）。

p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;

s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

以下排序算法的常见实现中，哪个选项的说法是错误的：（）。

冒泡排序算法是稳定的

简单插入排序是稳定的

归并排序算法是稳定的

简单选择排序是稳定的

八进制数 $32.1$ 对应的十进制数是（）

$24.125$

$24.250$

$26.250$

$26.125$

一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（）个内容互不相同的子串。

$12$

$15$

$14$

$13$

以下对递归方法的描述中，正确的是：（）

递归是允许使用多组参数调用函数的编程技术

递归是面向对象和数据而不是功能和逻辑的编程语言模型

递归是将用某种高级语言转换为机器代码的编程技术

递归是通过调用自身来求解问题的编程技术

阅阅读程序（共 19 题，共 0 分）

程序代码请先阅读以下程序

#include <iostream>

using namespace std; 

int main()  
{
    unsigned short x, y;
    cin >> x >> y;
    x = (x | x << 2) & 0x33;
    x = (x | x << 1) & 0x55;
    y = (y | y << 2) & 0x33;
    y = (y | y << 1) & 0x55;
    unsigned short z = x | y << 1;
    cout << z << endl;
    return 0;
}

假设输入的 x、y 均是不超过 $15$ 的自然数，删去第 7 行与第 13 行的 unsigned，程序行为不变。（）

错误

正确

假设输入的 x、y 均是不超过 $15$ 的自然数，将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（）

假设输入的 x、y 均是不超过 $15$ 的自然数，程序总是输出一个整数“0”。（）

假设输入的 x、y 均是不超过 $15$ 的自然数，当输入为“2 2”时，输出为“10”。（）

假设输入的 x、y 均是不超过 $15$ 的自然数，当输入为“2 2”时，输出为“59”。（）

假设输入的 x、y 均是不超过 $15$ 的自然数，当输入为“13 8”时，输出为（）。

$0$

$197$

$226$

$209$

程序代码请先阅读以下程序

#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 105;
const int MAXK = 105;

int h[MAXN][MAXK];

int f(int n, int m) 
{
    if (m == 1) return n;
    if (n == 0) return 0;
    
    int ret = numeric_limits<int>::max();
    for (int i = 1; i <= n; i++) 
        ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
    return ret;
}

int g(int n, int m) 
{
    for (int i = 1; i <= n; i++)
        h[i][1] = i;
    for (int j = 1; j <= m; j++)
        h[0][j] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            h[i][j] = numeric_limits<int >::max();
            for (int k = 1; k <= i; k++)
                h[i][j] = min(
                    h[i][j], 
                    max(h[i - k][j], h[k - 1][j - 1]) + 1);
        }
    }

    return h[n][m];
}

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

程序代码请先阅读以下程序

#include <iostream>

using namespace std;

int n, k;

int solve1()
{
    int l = 0, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (mid * mid <= n) l = mid + 1;
        else r = mid - 1;
    }
    return l - 1;
}

double solve2(double x)
{
    if (x == 0) return x;
    for (int i = 0; i < k; i++)
        x = (x + n / x) / 2;
    return x;
}

int main()
{
    cin >> n >> k;
    double ans = solve2(solve1());
    cout << ans << ' ' << (ans * ans == n) << endl;
    return 0;
}

完完善程序（共 10 题，共 0 分）

程序代码请先阅读以下程序

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

int main() {
    int n;
    cin >> n;
    
    vector<int> fac;
    fac.reserve((int)ceil(sqrt(n)));
    
    int i;
    for (i = 1; i * i < n; ++i) {
        if (①) {
            fac.push_back(i);
        }
    }
    
    for (int k = 0; k < fac.size(); ++k) {
        cout << ② << " ";
    }
    if (③) {
        cout << ④ << " ";
    }
    for (int k = fac.size() - 1; k >= 0; --k) {
        cout << ⑤ << " ";
    }
}

程序代码请先阅读以下程序

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

const int ROWS = 8;
const int COLS = 8;

struct Point {
    int r, c;
    Point(int r, int c) : r(r), c(c) {}
};

bool is_valid(char image[ROWS][COLS], Point pt, 
              int prev_color, int new_color) {
    int r = pt.r;
    int c = pt.c;
    return (0 <= r && r < ROWS && 0 <= c && c < COLS && 
            ① && image[r][c] != new_color);
}

void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
    queue<Point> queue;
    queue.push(cur);
    
    int prev_color = image[cur.r][cur.c];
    ②;
    
    while (!queue.empty()) {
        Point pt = queue.front();
        queue.pop();
        
        Point points[4] = {③ , Point(pt.r - 1, pt.c), 
                           Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
        for (auto p : points) {
            if (is_valid(image, p, prev_color, new_color)) {
                ④;
                ⑤;
            }
        }
    }
}

int main() {
    char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'}, 
                              {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'}, 
                              {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'}, 
                              {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'}, 
                              {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'}, 
                              {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'}, 
                              {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'} 
                              {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};

    Point cur(4, 4);
    char new_color = 'y';
    
    flood_fill(image, cur, new_color);
    
    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            cout << image[r][c] << " ";
        }
        cout << endl;
    }
    // 输出：
    // g g g g g g g g
    // g g g g g g r r
    // g r r g g r g g
    // g y y y y r g r
    // g g g y y r g r
    // g g g y y y y r
    // g g g g g y g g
    // g g g g g y y g
    
    return 0;
}

选 单项选择题（共 15 题，共 0 分）

阅 阅读程序（共 19 题，共 0 分）

完 完善程序（共 10 题，共 0 分）

考试完成

选单项选择题（共 15 题，共 0 分）

阅阅读程序（共 19 题，共 0 分）

完完善程序（共 10 题，共 0 分）