2023年CSP-J初赛试卷
以下对递归方法的描述中，正确的是：（ ）
递归是允许使用多组参数调用函数的编程技术
递归是通过调用自身来求解问题的编程技术
递归是面向对象和数据而不是功能和逻辑的编程语言模型
递归是将用某种高级语言转换为机器代码的编程技术
一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有 （ ）个内容互不相同的子串。
12
13
14
15
八进制数 32.1 对应的十进制数是（ ）。
24.125
24.250
26.125
26.250
以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
冒泡排序算法是稳定的
简单选择排序是稳定的
简单插入排序是稳定的
归并排序算法是稳定的
以下哪组操作能完成在双向循环链表结点 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;
以下对数据结构的表述不恰当的一项为：（ ）。
图的深度优先遍历算法常使用的数据结构为栈
栈的访问原则为后进先出，队列的访问原则是先进先出。
队列常常被用于广度优先搜索算法。
栈与队列存在本质不同，无法用栈实现队列。
考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在 （ ）个非零元素。
N-1
N
N+1
N的平方
一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位 置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子 结点的位置分别是（ ）。
8、18
10、18
8、19
10、19
假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为 （ ）位。
1
2
2或3
3
对表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符。
*+a-bcd
+a*-bcd
abc-d*+
abc-+d
对假设栈S和队列Q的初始状态为空。存在e1~e6六个互不相同的数据，每个数据按照 进栈S、出栈S、进队列Q、出队列Q的顺序操作，不同数据间的操作可能会交错。已知
栈 S
2 3 4 6
链表和数组的区别包括（ ）。
数组不能排序，链表可以
链表比数组能存储更多的信息
数组大小固定，链表大小可动态调整
以上均正确
运行以下代码片段的行为是（ ）
int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;
将x的值赋为201 将y的值赋为101 将 q 指向 x 的地址 将 p 指向 y 的地址
有 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
以下哪种功能没有涉及 C++语言的面向对象特性支持：（ ）。
C++中调用 printf 函数
C++中调用用户定义的类成员函数
C++中构造一个 class 或 struct
C++中构造来源于同一基类的多个派生类
第1题 判断
16. （2分）当输入为“2 2 2”时，输出为“1.7321”
第2题 判断
17. （2分）将第7行中的"（s-b）*（s-c）"改为"（s-c）*（s-b）"不会影响程序运行的结果
第3题 判断
18. （2分）程序总是输出四位小数
第4题 单选
19. 当输入为“3 4 5”时，输出为
A. "6.0000"
B. "12.0000"
C. "24.0000"
D. "30.0000"
第5题 单选
20. 当输入为“5 12 13”时，输出为（ ）
A. "24.0000"
B. "30.0000"
C. "60.0000"
D. "120.0000"
第1题 判断
【判断题】
f函数的返回值小于等于min(n,m）。（ ）
第2题 判断
f函数的返回值等于两个输入字符串的最长公共子串的长度。（ ）
第3题 判断
当输入两个完全相同的字符串时，g函数的返回值总是true（ ）
第4题 单选
【单选题】
将第19行中的“v[m][n]”替换为“v[n][m]”，那么该程序（ ）
行为不变
只会改变输出
一定非正常退出
可能非正常退出
第5题 单选
当输入为“csp-j p-jcs”时，输出为（ ）
“0”
“1”
“T”
“F”
第6题 单选
当输入为“csppsc spsccp”时，输出为：（ ）
“T”
“F”
“0”
“1”
第1题 判断
假设输入的n是绝对值不超过1000的整数，完成下面的判断题和单选题。
如果输入的n为正整数，solve2函数的作用是计算n所有的因子的平方和（ ）
第2题 判断
13~14行的作用是避免n的平方根因子i（或n/i）进入第16行而被计算两次（ ）
第3题 判断
如果输入的n为质数，solve2（n）的返回值为n2+1（ ）
第4题 单选
（4分）如果输入的n为质数p的平方，那么solve2（n）的返回值为（ ）
A.p2+p+1
B.n2+n+1
C.n2+1
D.p4+2p2+1
第5题 单选
31.当输入为正整数时，第一项减去第二项的差值一定（ ）
A. 大于0
B. 大于等于0,且不一定大于0
C. 小于0
D. 小于等于0,且不一定小于0
第6题 单选
32. 当输入为“5”时，输出为（ ）
A. "651 625"
B. "650 729"
C. "651 676"
D. "652 625"
三、完善程序(单选题，每小题3分，共计 3 分)
(1)(寻找被移除的元素)问题:原有长度为 n+1,公差为1等差升序数列，将数列输到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或最后之一个元素。需要在数组不连续时，找出被移除的元素。
试补全程序
第1题 单选
①处应填（ ）
1
nums[0]
right
left
第2题 单选
②处应填（ ）
left = mid+1
right = mid-1
right = mid
left = mid
第3题 单选
③处应填（ ）
left = mid+1
right = mid-
right = mid
left = mid
第4题 单选
④处应填（ ）
left + nums[0]
right + nums[0]
mid + nums[0]
right + 1
第5题 单选
⑤处应填（ ）
nums[0] + n
nums[0] + n - 1
nums[0] + n + 1
nums[n-1]
(2)（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace）一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。
第1题 单选
①处应填（ ）
j
i
m
n
第2题 单选
②处应填（ ）
j
i
m
n
第3题 单选
③处应填（ ）
str1[i-1]==str2[j-1]
str1[i]==str2[j]
str1[i-1]!=str2[j-1]
str1[i]!=str2[j]
第4题 单选
④处应填（ ）
dp[i-1][j-1]+1
dp[i-1][j-1]
dp[i-1][j]
dp[i][j-1]
第5题 单选
⑤处应填（ ）
dp[i][j] + 1
dp[i-1][j-1]+1
dp[i-1][j-1]
dp[i][j]