CSP-J 2022 第一轮试题

场次：2022年CSP-J第1轮
考试时长：120 分钟
满分：100 分
题目来源：第三方来源（社区转写，非官方，仅供参考）

单项选择题

本分区标题为平台补的结构性占位，原卷（来源件）未收录。

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

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

C++ 中调用 printf 函数

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

C++ 中构造一个 class 或 struct

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

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

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

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

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

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

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

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

将 $x$ 的值赋为 $201$

将 $y$ 的值赋为 $101$

将 $q$ 指向 $x$ 的地址

将 $p$ 指向 $y$ 的地址

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

数组不能排序，链表可以

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

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

以上均正确

对假设栈 $S$ 和队列 $Q$ 的初始状态为空。存在 $e_1\sim 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$

$3$

$4$

$6$

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

*+a-bcd

+a*-bcd

abc-d*+

abc-+d

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

$1$

$2$

$2$ 或 $3$

$3$

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

$8$ 、 $18$

$10$ 、 $18$

$8$ 、 $19$

$10$ 、 $19$

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

$N-1$

$N$

$N+1$

$N^2$

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

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

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

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

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

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

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;

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

冒泡排序算法是稳定的

简单选择排序是稳定的

简单插入排序是稳定的

归并排序算法是稳定的

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

$24.125$

$24.250$

$26.125$

$26.250$

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

$12$

$13$

$14$

$15$

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

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

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

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

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

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

判断题「√」表示正确，「×」表示错误

阅读程序共 10.5 分6 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/6

程序

01 #include <iostream>0203 using namespace std;0405 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判断1.5 分
删去第 $7$ 行与第 $13$ 行的 unsigned，程序行为不变。
17判断1.5 分
将第 $7$ 行与第 $13$ 行的 short 均改为 char，程序行为不变。
18判断1.5 分
程序总是输出一个整数“0”。
19判断1.5 分
当输入为 2 2 时，输出为 10。
20判断1.5 分
当输入为 2 2 时，输出为 59。
21单选3 分
单选题
1. 当输入为 13 8 时，输出为（）。
A
$0$

B
$209$

C
$197$

D
$226$

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

完善程序共 15 分5 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/5

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

试补全程序。

程序

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

40（①）单选空位 ①3 分
① && image[r][c] != new_color)

A
image[r][c] == prev_color

B
image[r][c] != prev_color

C
image[r][c] == new_color

D
image[r][c] != new_color
41（②）单选空位 ②3 分
int prev_color = image[cur.r][cur.c];
②;

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
42（③）单选空位 ③3 分
Point points[4] = {③, Point(pt.r - 1, pt.c),

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)
43（④）单选空位 ④3 分
```
            ④;
```
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
44（⑤）单选空位 ⑤3 分
```
            ⑤;
```
A
queue.push(p)

B
queue. push (pt)

C
queue.push(cur)

D
queue. push(Point (ROWS, COLS))

CSP-J 2022 第一轮试题