#TK8006. CSP 2022 入门级第一轮

CSP 2022 入门级第一轮

2022 CCF 非专业级别软件能力认证第一轮

（CSP-J1）入门级 C++语言试题

认证时间：2022 年 9 月 18 日 09:30~11:30

考生注意事项：

试题纸共有 12 页，答题纸共有 1 页，满分100 分。请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

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

  1. 以下哪种功能没有涉及C++语言的面向对象特性支持： {{ select(1) }}
  • C++中调用printf函数
  • C++中调用用户定义的类成员函数
  • C++中构造一个class或struct
  • C++中构造来源于同一基类的多个派生类
  1. 有6个元素，按照6、5、4、3、2、1的顺序进入栈S，请问下列哪个出栈序列是非法的： {{ select(2) }}
  • 5 4 3 6 1 2
  • 4 5 3 1 2 6
  • 3 4 6 5 2 1
  • 2 3 4 1 5 6
  1. 运行以下代码片段的行为是：
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

{{ select(3) }}

  • 将x的值赋为201
  • 将y的值赋为101
  • 将q指向x的地址
  • 将p指向y的地址
  1. 链表和数组的区别包括： {{ select(4) }}
  • 数组不能排序，链表可以
  • 链表比数组能存储更多的信息
  • 数组大小固定，链表大小可动态调整
  • 以上均正确
  1. 栈S和队列Q的操作问题：栈S的容量至少是（ ）个数据。 {{ select(5) }}
  • 2
  • 3
  • 4
  • 6
  1. 表达式a+(b-c)d的前缀表达式为： {{ select(6) }}
  • *+a-bcd
  • +a*-bcd
  • abc-d*+
  • abc-+d
  1. 使用哈夫曼编码，字母d的编码长度为（ ）位： {{ select(7) }}
  • 1
  • 2
  • 2或3
  • 3
  1. 完全二叉树的数组存储问题：兄弟结点和右子结点的位置分别是（ ）。 {{ select(8) }}
  • 8、18
  • 10、18
  • 8、19
  • 10、19
  1. 有向连通图的邻接矩阵问题：矩阵中至少存在（ ）个非零元素。 {{ select(9) }}
  • N-1
  • N
  • N+1
  • N²
  1. 对数据结构的表述不恰当的一项： {{ select(10) }}
  • 图的深度优先遍历算法常使用的数据结构为栈
  • 栈的访问原则为后进先出，队列的访问原则是先进先出
  • 队列常常被用于广度优先搜索算法
  • 栈与队列存在本质不同，无法用栈实现队列
  1. 双向循环链表插入操作：哪组操作能完成在结点p之后插入结点s的效果。 {{ select(11) }}
  • p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
  • p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
  • s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
  • s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;
  1. 排序算法的稳定性问题：哪个选项的说法是错误的。 {{ select(12) }}
  • 冒泡排序算法是稳定的
  • 简单选择排序是稳定的
  • 简单插入排序是稳定的
  • 归并排序算法是稳定的
  1. 八进制数32.1对应的十进制数是： {{ select(13) }}
  • 24.125
  • 24.250
  • 26.125
  • 26.250
  1. 字符串abcab的子串问题：字符串abcab有（ ）个内容互不相同的子串。 {{ select(14) }}
  • 12
  • 13
  • 14
  • 15
  1. 对递归方法的描述中，正确的是： {{ select(15) }}
  • 递归是允许使用多组参数调用函数的编程技术
  • 递归是通过调用自身来求解问题的编程技术
  • 递归是面向对象和数据而不是功能和逻辑的编程语言模型
  • 递归是将用某种高级语言转换为机器代码的编程技术

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

#include <iostream>
using namespace std;

/**87701149@qq.com 北斗星编程编辑**/

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;
}

判断题

  1. 删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ） {{ select(16) }}
  • 对
  • 错
  1. 将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ） {{ select(17) }}
  • 对
  • 错
  1. 程序总是输出一个整数"0"。（ ） {{ select(18) }}
  • 对
  • 错
  1. 当输入为"2 2"时，输出为"10"。（ ） {{ select(19) }}
  • 对
  • 错
  1. 当输入为"2 2"时，输出为"59"。（ ） {{ select(20) }}
  • 对
  • 错

单选题

  1. 当输入为"13 8"时，输出为（ ）。 {{ select(21) }}
  • "0"
  • "209"
  • "197"
  • "226"

（2）

#include <algorithm>
#include <iostream>
#include <limits>
/**87701149@qq.com 北斗星编程编辑**/
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;
}

假设输入的 n、m 均是不超过 100 的正整数，完成下面的判断题和单选题：

判断题

22.当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ） {{ select(22) }}

  • 对
  • 错

23.输出的两行整数总是相同的。（ ） {{ select(23) }}

  • 对
  • 错

24.当 m 为 1 时，输出的第一行总为 n。（ ） {{ select(24) }}

  • 对
  • 错

单选题

25.算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。 {{ select(25) }}

  • 𝑂(𝑛3/2𝑚)
  • 𝑂(𝑛m)
  • 𝑂(𝑛2𝑚)
  • 𝑂(𝑛𝑚2)

26.当输入为“20 2”时，输出的第一行为（ ）。 {{ select(26) }}

  • "4"
  • "5"
  • "6"
  • "20"

27.（4 分）当输入为“100 100”时，输出的第一行为（ ）。 {{ select(27) }}

  • "6"
  • "7"
  • "8"
  • "9"
#include <iostream>
using namespace std;
/**87701149@qq.com 北斗星编程编辑**/

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;
}

判断题

28.该算法最准确的时间复杂度分析结果为𝑂(log 𝑛𝑛 + 𝑘𝑘)。（ ） {{ select(28) }}

  • 对
  • 错

29.当输入为"9801 1"时，输出的第一个数为"99"。（ ） {{ select(29) }}

  • 对
  • 错

30.对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成"1"。（ ） {{ select(30) }}

  • . 对
  • . 错

31.该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ） {{ select(31) }}

  • . 对
  • . 错

单选题

32.当输入为“2 1”时，输出的第一个数最接近（ ）。 {{ select(32) }}

  • 1
  • 1.414
  • 1.5
  • 2

33.当输入为“3 10”时，输出的第一个数最接近（ ）。 {{ select(33) }}

  • 1.7
  • 1.732
  • 1.75
  • 2

34.当输入为"256 11"时，输出的第一个数（ ）。 {{ select(34) }}

  • 等于 16
  • 接近但小于 16
  • 接近但大于 16
  • 前三种情况都有可能

三、完善程序（单选题，每小题 3 分，共计 30 分） （1）（枚举因数）从小到大打印正整数 n 的所有正因数。 试补全枚举程序。


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

/**87701149@qq.com 北斗星编程编辑**/

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 << ⑤ << " ";
    }
}

35.①处应填（ ） {{ select(35) }}

  • n % i == 0
  • n % i == 1
  • n % (i-1) == 0
  • n % (i-1) == 1

36.②处应填（ ） {{ select(36) }}

  • n / fac[k]
  • fac[k]
  • fac[k]-1
  • n / (fac[k]-1)

37.③处应填（ ） {{ select(37) }}

  • (i-1) * (i-1) == n
  • (i-1) * i == n
  • i * i == n
  • i * (i-1) == n

38.④处应填（ ） {{ select(38) }}

  • n-i
  • n-i+1
  • i-1
  • I

39.⑤处应填（ ） {{ select(39) }}

  • n / fac[k]
  • fac[k]
  • fac[k]-1
  • n / (fac[k]-1)

（2）（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。

试补全程序。


#include <bits/stdc++.h>
using namespace std;
/**87701149@qq.com 北斗星编程编辑**/

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;
}

40.①处应填（ ） {{ select(40) }}

  • image[r][c] == prev_color
  • image[r][c] != prev_color
  • image[r][c] == new_color
  • image[r][c] != new_color

41.②处应填（ ） {{ select(41) }}

  • image[cur.r+1][cur.c] = new_color
  • image[cur.r][cur.c] = new_color
  • image[cur.r][cur.c+1] = new_color
  • image[cur.r][cur.c] = prev_color

42.③处应填（ ） {{ select(42) }}

  • Point(pt.r, pt.c)
  • Point(pt.r, pt.c+1)
  • Point(pt.r+1, pt.c)
  • Point(pt.r+1, pt.c+1)

43.④处应填（ ） {{ select(43) }}

  • prev_color = image[p.r][p.c]
  • new_color = image[p.r][p.c]
  • image[p.r][p.c] = prev_color
  • image[p.r][p.c] = new_color

44.⑤处应填（ ） {{ select(44) }}

  • queue.push(p)
  • queue.push(pt)
  • queue.push(cur)
  • queue.push(Point(ROWS,COLS))
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 53ms
  4. Powered by Hydro v5.0.0-beta.7 Community