小赛码CSP-J2024复习计划
CSP-J 2022初赛真题

*
您的校区：
*
您的姓名：

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

1.
以下哪种功能没有涉及 C++语言的面向对象特性支持：（）。
A. C++中调用 printf 函数
B. C++中调用用户定义的类成员函数
C. C++中构造一个 class 或 struct
D. C++中构造来源于同一基类的多个派生类
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
3.
运行以下代码片段的行为是（）。

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

A. 将 x 的值赋为 201
B. 将 y 的值赋为 101
C. 将 q 指向 x 的地址
D. 将 p 指向 y 的地址
4.
链表和数组的区别包括（ ）。
A. 数组不能排序，链表可以
B. 链表比数组能存储更多的信息
C. 数组大小固定，链表大小可动态调整
D. 以上均正确
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
6.
对表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符。
A. *+a-bcd
B. +a*-bcd
C. abc-d*+
D. abc-+d
7.
假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为 （ ）位。
A. 1
B. 2
C. 2 或 3
D. 3
8.
一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位 置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子 结点的位置分别是（ ）。
A. 8、18
B. 10、18
C. 8、19
D. 10、19
9.
考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在 （ ）个非零元素。
A. N-1
B. N
C. N+1
D. N²
10.
以下对数据结构的表述不恰当的一项为：（ ）。
A. 图的深度优先遍历算法常使用的数据结构为栈。
B. 栈的访问原则为后进先出，队列的访问原则是先进先出。
C. 队列常常被用于广度优先搜索算法。
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;
12.
以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
A. 冒泡排序算法是稳定的
B. 简单选择排序是稳定的
C. 简单插入排序是稳定的
D. 归并排序算法是稳定的
13.
八进制数 32.1 对应的十进制数是（ ）。
A. 24.125
B. 24.250
C. 26.125
D. 26.250
14.
一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有 （ ）个内容互不相同的子串。
A. 12
B. 13
C. 14
D. 15
15.
以下对递归方法的描述中，正确的是：（ ）
A. 递归是允许使用多组参数调用函数的编程技术
B. 递归是通过调用自身来求解问题的编程技术
C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型
D. 递归是将用某种高级语言转换为机器代码的编程技术
二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题1.5分，选择题3 分，共计40分）
代码1.

假设输入的 x、y 均是不超过 15 的自然数，完成下面的判断题和单选题：
判断题 每题1.5分
16.
删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ）
对
错
17.
将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）
对
错
18.
程序总是输出一个整数“0”。（ ）
对
错
19.
当输入为“2 2”时，输出为“10”。（ ）
对
错
*
20.
当输入为“2 2”时，输出为“59”。（ ）
对
错
选择题（每题3分）
21.
当输入为“13 8”时，输出为（ ）。
A. “0”
B. “209”
C. “197”
D. “226”
代码2：

 

假设输入的 n、m 均是不超过 100 的正整数，完成下面的判断题和单选题：
判断题（每题1.5分）
22.
当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）
对
错
23.
输出的两行整数总是相同的。（ ）
对
错
24.
当 m 为 1 时，输出的第一行总为 n。（ ）
对
错
选择题（每题3分）
*
25.
算法 g(n,m)最为准确的时间复杂度分析结果为（ ）。
A.
B.
C.
D.
26.
当输入为“20 2”时，输出的第一行为（ ）。
A. “4”
B. “5”
C. “6”
D. “20”
27.
（4 分）当输入为“100 100”时，输出的第一行为（ ）。
A. “6”
B. “7”
C. “8”
D. “9”
代码3


假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：
判断题
28.
该算法最准确的时间复杂度分析结果为𝑂(log 𝑛 + 𝑘)。（ ）
对
错
29.
当输入为“9801 1”时，输出的第一个数为“99”。（ ）
对
错
*
30.
对于任意输入的 n，随着所输入 k 的增大，输出的第二个数会变成“1”。（ ）
对
错
*
31.
该程序有存在缺陷。当输入的 n 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）
对
错
单选题
32.
当输入为“2 1”时，输出的第一个数最接近（ ）。
A. 1
B. 1.414
C. 1.5
D. 2
33.
当 n=100 时，最好情况下，与第 12 行的比较运算执行的次数最接近的是:（）。
A. 1.7
B. 1.732
C. 1.75
D. 2
34.
当输入为“256 11”时，输出的第一个数（ ）。
A. 等于 16
B. 接近但小于 16
C. 接近但大于 16
D. 前三种情况都有可能

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

（1）（枚举因数）从小到大打印正整数 n 的所有正因数。 试补全枚举程序。

  


35.
①处应填（ ）
A. n % i == 0
B. n % i == 1
C. n % (i-1) == 0
D. n % (i-1) == 1
36.
②处应填（ ）
A. n / fac[k]
B. fac[k]
C. fac[k]-1
D. n / (fac[k]-1)
37.
③处应填（）
A. (i-1) * (i-1) == n
B. (i-1) * i == n
C. i * i == n
D. i * (i-1) == n
38.
④处应填（）
A. n-i
B. n-i+1
C. i-1
D. I
39.
⑤处应填（）
A. n / fac[k]
B. fac[k]
C. fac[k]-1
D. n / (fac[k]-1)
    （2）（洪水填充）现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给 定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色 都与起始像素颜色相同），替换为给定的颜色。 试补全程序
   
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
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
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)
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
44.
⑤处应填（）
A. queue.push(p)
B. queue.push(pt)
C. queue.push(cur)
D. queue.push(Point(ROWS,COLS))
问卷星提供技术支持
举报