夜雨聆风学习资料网

ARTICLE · 1374981

2022年CSP-J第一轮(入门级)真题及答案

2022年CSP-J第一轮(入门级)真题及答案

一、单项选择题(第 1~15 题,每题 2 分)

第 1 题 以下哪种功能没有涉及 C++ 语言的面向对象特性支持?( )

A. C++ 中调用 printf 函数 B. C++ 中调用用户定义的类成员函数 C. C++ 中构造一个 class 或 struct D. C++ 中构造来源于同一基类的多个派生类

【答案】A

解析:printf 是继承自 C 的标准库函数,直接调用它不需要创建对象,也不涉及封装、继承、多态;B/C/D 都直接用到类或继承机制。

第 2 题 有 6 个元素,按照 6、5、4、3、2、1 的顺序进入栈 S,请问下列哪个出栈序列是非法的?( )

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6

【答案】C

解析:要最先弹出 3,必须先依次压入 6、5、4、3;弹出 3、4 后栈内剩 6、5 且 5 在顶,下一步却要求弹出 6,被 5 挡住,无法实现。其余序列都可模拟成功。

第 3 题 运行以下代码片段的行为是( )。

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

【答案】D

解析:p = q 只是把 q 中保存的地址复制给 p,执行后 p 与 q 都指向 y,x、y 的值均不变。

第 4 题 链表和数组的区别包括( )。

A. 数组不能排序,链表可以 B. 链表比数组能存储更多的信息 C. 数组大小固定,链表大小可动态调整 D. 以上均正确

【答案】C

解析:数组和链表都可以排序,存储能力也不由结构直接决定;数组通常连续存储、大小固定,链表通过节点动态增删。

第 5 题 假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据,每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作,不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈,队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是( )个数据。

A. 2 B. 3 C. 4 D. 6

【答案】B

解析:队列出队顺序即元素离开栈的顺序。模拟:压 e1、e2 后弹 e2;压 e3、e4 后弹 e4、e3(此时栈内 e1、e3、e4,深度 3);压 e5、e6 后弹 e6、e5,最后弹 e1。全程最大深度为 3。

第 6 题 对表达式 a+(b-c)*d 的前缀表达式为( ),其中 +、-、* 是运算符。

A. *+a-bcd B. +a*-bcd C. abc-d*+ D. abc-+d

【答案】B

解析:b-c 的前缀为 -bc,再与 d 相乘得 *-bcd,最后与 a 相加得 +a*-bcd。C、D 是后缀表达式形式。

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

A. 1 B. 2 C. 2 或 3 D. 3

【答案】B

解析:每次合并频率最小的两个节点:10+15=25,25+16=41,29+30=59,41+59=100。d 在结点 41 内,到根恰好经过 2 条边,码长为 2。注意哈夫曼编码形态可能不唯一,但码长确定。

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

A. 8、18 B. 10、18 C. 8、19 D. 10、19

【答案】C

解析:9 为奇数,说明它是父结点(4 号)的右孩子,兄弟是 8 号;右孩子下标为 2×9+1=19。

第 9 题 考虑由 N 个顶点构成的有向连通图,采用邻接矩阵的数据结构表示时,该矩阵中至少存在( )个非零元素。

A. N-1 B. N C. N+1 D. N²

【答案】B

解析:本题按"有向连通=强连通"理解:每个顶点都要能到达其余所有顶点,N-1 条边的单向树无法保证,最少是一个覆盖全部顶点的有向环,恰用 N 条边,对应 N 个非零元素。(若按弱连通理解则是 N-1,本题以官方口径 B 为准。)

第 10 题 以下对数据结构的表述不恰当的一项为( )。

A. 图的深度优先遍历算法常使用的数据结构为栈。 B. 栈的访问原则为后进先出,队列的访问原则是先进先出。 C. 队列常常被用于广度优先搜索算法。 D. 栈与队列存在本质不同,无法用栈实现队列。

【答案】D

解析:用两个栈(一个管入队、一个管出队)就可以模拟队列,D 的"无法实现"说法错误。

第 11 题 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果(其中,next 域为结点的直接后继,prev 域为结点的直接前驱)?( )

A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

【答案】D

解析:必须先用 s->next 保存 p 的旧后继,并让旧后继的 prev 指向 s,最后才能改写 p->next。A/B/C 都会在某一步提前改写 p->next,导致 s->next 指向自己或丢失旧后继。

第 12 题 以下排序算法的常见实现中,哪个选项的说法是错误的?( )

A. 冒泡排序算法是稳定的 B. 简单选择排序是稳定的 C. 简单插入排序是稳定的 D. 归并排序算法是稳定的

【答案】B

解析:简单选择排序每趟把最小元素与当前位置直接交换,可能跨过相等元素,不稳定(如序列 5 5 2 第一趟后两个 5 顺序颠倒)。冒泡、插入、归并的常见实现均稳定。口诀:不稳定的有快选堆希。

第 13 题 八进制数 32.1 对应的十进制数是( )。

A. 24.125 B. 24.250 C. 26.125 D. 26.250

【答案】C

解析:整数部分 3×8+2=26,小数部分 1×8⁻¹=0.125,合计 26.125。

第 14 题 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串,则字符串 abcab 有( )个内容互不相同的子串。

A. 12 B. 13 C. 14 D. 15

【答案】B

解析:按长度去重:长度 1 有 a、b、c 共 3 个;长度 2 有 ab、bc、ca 共 3 个;长度 3 有 abc、bca、cab 共 3 个;长度 4 有 abca、bcab 共 2 个;长度 5 有 abcab 共 1 个;"任意个"含 0 个字符,再加空串 1 个,共 13 个。(非空子串为 12 个,官方答案计入空串取 13。)

第 15 题 以下对递归方法的描述中,正确的是( )。

A. 递归是允许使用多组参数调用函数的编程技术 B. 递归是通过调用自身来求解问题的编程技术 C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型 D. 递归是将用某种高级语言转换为机器代码的编程技术

【答案】B

解析:递归的核心是函数直接或间接调用自身,配合规模更小的子问题与终止条件求解。A 描述的是函数重载,C 是面向对象,D 是编译。

二、阅读程序(第 16~34 题,判断题 1.5 分、选择题 3 分)

程序输入不超过数组或字符串定义的范围;判断题正确填 √、错误填 ×。

阅读程序(1) 位运算交织(第 16~21 题)

假设输入的 x、y 均是不超过 15 的自然数,完成下面的判断题和单选题。这段代码把 x、y 的低 4 位拆开交错合并:x 的位落到结果的偶数位、y 的位落到奇数位。

01  #include <iostream>

02

03  using namespace std;

04

05  int main()

06  {

07      unsigned short x, y;

08      cin >> x >> y;

09      x = (x | x << 2) & 0x33;

10      x = (x | x << 1) & 0x55;

11      y = (y | y << 2) & 0x33;

12      y = (y | y << 1) & 0x55;

13      unsigned short z = x | y << 1;

14      cout << z << endl;

15      return 0;

16  }

第 16 题 删去第 7 行与第 13 行的 unsigned,程序行为不变。( )

【答案】√

解析:x、y ≤ 15,所有中间结果都被 0x33、0x55 掩码限制在很小的非负范围内,signed short 完全装得下,符号位不影响结果。

第 17 题 将第 7 行与第 13 行的 short 均改为 char,程序行为不变。( )

【答案】×

解析:char 只有 8 位,位运算产生的中间值可能超出其表示范围(且 char 是否有符号由实现决定);cin 对 char 还会按字符读取,行为改变。

第 18 题 程序总是输出一个整数"0"。( )

【答案】×

解析:输出随输入变化,例如输入 1 0 时输出 1,只有 x=y=0 才输出 0。

第 19 题 当输入为"2 2"时,输出为"10"。( )

【答案】×

解析:手算:x=2 经两轮掩码变为 4,y 同为 4;z = 4 | 4<<1 = 4|8 = 12,实际输出 12。

第 20 题 当输入为"2 2"时,输出为"59"。( )

【答案】×

解析:同上,实际输出 12。

第 21 题 当输入为"13 8"时,输出为( )。

A. "0" B. "209" C. "197" D. "226"

【答案】B

解析:x=13(1101₂) 两轮掩码后为 81,y=8(1000₂) 后为 64,z = 81 | 64<<1 = 81|128 = 11010001₂ = 209。

阅读程序(2) 扔鸡蛋 DP(第 22~27 题)

假设输入的 n、m 均是不超过 100 的正整数,完成下面的判断题和单选题。程序背景是经典的"高楼扔鸡蛋":n 层楼、m 个鸡蛋,求最坏情况下确定临界楼层所需的最少尝试次数;f 是递归写法,g 是同一转移的递推(DP)写法。

01  #include <algorithm>

02  #include <iostream>

03  #include <limits>

04

05  using namespace std;

06

07  const int MAXN = 105;

08  const int MAXK = 105;

09

10  int h[MAXN][MAXK];

11

12  int f(int n, int m)

13  {

14      if (m == 1) return n;

15      if (n == 0) return 0;

16

17      int ret = numeric_limits<int>::max();

18      for (int i = 1; i <= n; i++)

19          ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);

20      return ret;

21  }

22

23  int g(int n, int m)

24  {

25      for (int i = 1; i <= n; i++)

26          h[i][1] = i;

27      for (int j = 1; j <= m; j++)

28          h[0][j] = 0;

29

30      for (int i = 1; i <= n; i++) {

31          for (int j = 2; j <= m; j++) {

32              h[i][j] = numeric_limits<int>::max();

33              for (int k = 1; k <= i; k++)

34                  h[i][j] = min(

35                      h[i][j],

36                      max(h[i - k][j], h[k - 1][j - 1]) + 1);

37          }

38      }

39

40      return h[n][m];

41  }

42

43  int main()

44  {

45      int n, m;

46      cin >> n >> m;

47      cout << f(n, m) << endl << g(n, m) << endl;

48      return 0;

49  }

第 22 题 当输入为"7 3"时,第 19 行用来取最小值的 min 函数执行了 449 次。( )

【答案】×

解析:设 c(n,m) 为 min 的执行次数,边界 c(0,·)=c(·,1)=0,转移 c(n,m)=n+Σ(c(n-i,m)+c(i-1,m-1))。逐层计算 c(n,2)=1,3,7,15,31,63,127(n=1..7),c(7,3)=448 次,不是 449。

第 23 题 输出的两行整数总是相同。( )

【答案】√

解析:f 与 g 使用完全相同的边界和状态转移,只是递归与递推的书写差别,结果恒相等。

第 24 题 当 m 为 1 时,输出的第一行总为 n。( )

【答案】√

解析:f 的第一个出口就是 if (m == 1) return n;,只有一个鸡蛋时只能从低到高逐层试,最坏 n 次。

第 25 题 算法 g(n, m) 最为准确的时间复杂度分析结果为( )。

A. O(n^(3/2)·m) B. O(nm) C. O(n²m) D. O(nm²)

【答案】C

解析:i、j、k 三层循环:Σi × m × i ≈ n²m/2 量级,为 O(n²m)。

第 26 题 当输入为"20 2"时,输出的第一行为( )。

A. 4 B. 5 C. 6 D. 20

【答案】C

解析:两个鸡蛋、t 次尝试最多覆盖 1+2+…+t = t(t+1)/2 层;t=5 只能覆盖 15 层,t=6 覆盖 21 层 ≥ 20,故为 6。

第 27 题 当输入为"100 100"时,输出的第一行为( )。

A. 6 B. 7 C. 8 D. 9

【答案】B

解析:鸡蛋充足时可近似二分,t 次最多区分 2ᵗ-1 层;2⁶-1=63 不够,2⁷-1=127 ≥ 100,故为 7。

阅读程序(3) 平方根:二分 + 牛顿迭代(第 28~34 题)

假设 int 为 32 位有符号整数类型,输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数,完成下面的判断题和单选题。solve1 用二分求 ⌊√n⌋,solve2 做k 次牛顿迭代逼近 √n,最后输出 ans 与判断 ans² 是否恰等于 n 的结果(0 或 1)。

01  #include <iostream>

02

03  using namespace std;

04

05  int n, k;

06

07  int solve1()

08  {

09      int l = 0, r = n;

10      while (l <= r) {

11          int mid = (l + r) / 2;

12          if (mid * mid <= n) l = mid + 1;

13          else r = mid - 1;

14      }

15      return l - 1;

16  }

17

18  double solve2(double x)

19  {

20      if (x == 0) return x;

21      for (int i = 0; i < k; i++)

22          x = (x + n / x) / 2;

23      return x;

24  }

25

26  int main()

27  {

28      cin >> n >> k;

29      double ans = solve2(solve1());

30      cout << ans << ' ' << (ans * ans == n) << endl;

31      return 0;

32  }

第 28 题 该算法最准确的时间复杂度分析结果为 O(log n + k)。( )

【答案】√

解析:solve1 是在 [0, n] 上的二分,O(log n);solve2 固定迭代 k 次,每次常数操作,O(k);合计 O(log n + k)。

第 29 题 当输入为"9801 1"时,输出的第一个数为"99"。( )

【答案】√

解析:9801 = 99²,solve1 返回 99;一次牛顿迭代 (99 + 9801/99)/2 = 99,输出 99。

第 30 题 对于任意输入的 n,随着所输入 k 的增大,输出的第二个数会变成"1"。( )

【答案】×

解析:第二个数判断 ans*ans 是否恰好等于 n。若 n 不是完全平方数,无论迭代多少次 ans 只是逼近 √n,浮点意义下很难严格满足 ans²==n,不会"变成 1"。

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

【答案】×

解析:二分中 l 只会增长到 ⌊√n⌋+1(约 217),此后 mid ≤ (√n+1+n)/2 ≈ 23600,mid² ≈ 5.6×10⁸,远小于 int 上限约 2.15×10⁹,在 n ≤ 47000 的约束下不会溢出,无需转 64 位。(这是全卷著名的争议题,官方判 ×。)

第 32 题 当输入为"2 1"时,输出的第一个数最接近( )。

A. 1 B. 1.414 C. 1.5 D. 2

【答案】C

解析:solve1 得 ⌊√2⌋=1;一次牛顿迭代 x=(1+2/1)/2=1.5,输出 1.5。

第 33 题 当输入为"3 10"时,输出的第一个数最接近( )。

A. 1.7 B. 1.732 C. 1.75 D. 2

【答案】B

解析:10 次牛顿迭代收敛到 √3 ≈ 1.732。

第 34 题 当输入为"256 11"时,输出的第一个数( )。

A. 等于 16 B. 接近但小于 16 C. 接近但大于 16 D. 前三种情况都有可能

【答案】A

解析:256 是完全平方数,solve1 得 16,牛顿迭代不动点 x=(16+256/16)/2=16,输出恰好等于 16。

三、完善程序(第 35~44 题,单选题,每小题 3 分)

完善程序(1) 枚举因数(第 35~39 题)

(枚举因数)请按升序列出正整数 n 的所有正因子。尝试完成这段枚举代码。程序利用因数的成对对称性:先收集所有小于 √n 的因数,特判完全平方数,再倒序输出对应的 n/fac[k],即可 O(√n) 升序输出全部因数。

#include <iostream>

#include <vector>

#include <cmath>

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

    }

    return 0;

}

第 35 题 ①处应填( )。

A. n % i == 0 B. n % i == 1 C. n % (i-1) == 0 D. n % (i-1) == 1

【答案】A

解析:判断 i 是否为 n 的因数,即 n 能否被 i 整除(余数为 0)。

第 36 题 ②处应填( )。

A. n / fac[k] B. fac[k] C. fac[k]-1 D. n / (fac[k]-1)

【答案】B

解析:fac 中按升序存的是小于 √n 的因数本身,正序遍历直接输出 fac[k]。

第 37 题 ③处应填( )。

A. (i-1)*(i-1) == n B. (i-1)*i == n C. i*i == n D. i*(i-1) == n

【答案】C

解析:循环条件是 i*i < n,循环结束后 i 是使 i*i ≥ n 的最小整数;若 n 为完全平方数,恰好有 i*i == n。

第 38 题 ④处应填( )。

A. n-i B. n-i+1 C. i-1 D. i

【答案】D

解析:n 为完全平方数时,i 就是那个单独的中间因数 √n,直接输出 i。

第 39 题 ⑤处应填( )。

A. n / fac[k] B. fac[k] C. fac[k]-1 D. n / (fac[k]-1)

【答案】A

解析:与 fac[k] 成对的因数是 n/fac[k];fac 倒序递减时 n/fac[k] 递增,恰好升序输出所有大于 √n 的因数。

完善程序(2) 洪水填充(第 40~44 题)

(洪水填充)在一个由字符表示颜色的 8×8 像素图像中进行颜色填充:给定起始像素与目标颜色,将起始像素以及所有经上、下、左、右四方向移动可达、且颜色与起始像素相同的像素,替换为目标颜色。程序用 BFS 队列实现,请补全代码。

#include <iostream>

#include <queue>

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[] = {③, 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)) {

                ④;

                ⑤;

            }

        }

    }

}

main 函数中的图像数据(起点 cur(4,4),新颜色 'y'):起点所在的蓝色 b 区域会被整块染成 y。

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;

    }

    return 0;

}

第 40 题 ①处应填( )。

A. image[r][c] == prev_color B. image[r][c] != prev_color C. image[r][c] == new_color D. image[r][c] != new_color

【答案】A

解析:合法性判断要求目标像素仍为原颜色(尚未被填充且属于同一连通块)。

第 41 题 ②处应填( )。

A. image[cur.r+1][cur.c] = new_color B. image[cur.r][cur.c] = new_color C. image[cur.r][cur.c+1] = new_color D. image[cur.r][cur.c] = prev_color

【答案】B

解析:起点无需判断,直接染色标记为已填充,防止之后重复入队。

第 42 题 ③处应填( )。

A. Point(pt.r, pt.c) B. Point(pt.r, pt.c+1) C. Point(pt.r+1, pt.c) D. Point(pt.r+1, pt.c+1)

【答案】C

解析:四个方向已有上、右、左(pt.r-1 / pt.c+1 / pt.c-1),缺的是正下方 Point(pt.r+1, pt.c)。

第 43 题 ④处应填( )。

A. prev_color = image[p.r][p.c] B. new_color = image[p.r][p.c] C. image[p.r][p.c] = prev_color D. image[p.r][p.c] = new_color

【答案】D

解析:新访问到的合法像素 p 应立即染成新颜色(入队即染色,避免重复)。

第 44 题 ⑤处应填( )。

A. queue.push(p) B. queue.push(pt) C. queue.push(cur) D. queue.push(Point(ROWS,COLS))

【答案】A

解析:把刚染色的邻居 p 入队,后续以 p 为中心继续向外扩散。

全卷答案速查表

单项选择 1-15:  A C D C B B B C B D D B C B B

阅读程序1 16-21:√ × × × ×  B(输入"2 2"实际输出 12;"13 8"输出 209)

阅读程序2 22-27:× √ √  C C B

阅读程序3 28-34:√ √ × ×  C B A

完善程序1 35-39:A B C D A

完善程序2 40-44:A B C D A

全卷小结

🎯 本卷关键词:栈与队列的手算模拟(第 2、5 题,出入栈交错推演是近年高频考点)、哈夫曼树与完全二叉树下标(第 7、8 题)、双向链表插入的指针顺序(第 11 题,先保存旧后继再改 p->next)、位运算交织(阅读程序 1)、扔鸡蛋 DP(阅读程序 2,递归与递推同构)、二分 + 牛顿迭代(阅读程序 3)、因数成对枚举与 BFS 洪水填充(完善程序)。整体难度友好,但第 9、14、31 题为全卷著名的争议题,考场上按官方口径作答即可。

📢 下期预告:2022年CSP-S第一轮(提高级)真题及答案,欢迎持续关注,每天一套真题带答案,稳步冲击 CSP/NOIP!

题目版权归 CCF 所有,本文仅作学习交流之用;答案经多个独立来源交叉核对,若与官方公布不一致,以官方为准。

💪 建议先掐 120 分钟独立做完全卷再对照答案复盘:第 5 题亲手模拟一遍出入栈,阅读程序 1 的"2 2"和"13 8"务必逐位手算,阅读程序 2 想清楚 f 与 g 为什么恒相等,第 22 题的 448 次可以写个计数程序验证,完善程序两题补完代码后自己跑一遍样例。加油,我们明天见!

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料