csp-j初赛测评

第1题中级 2分单选

一个8×8的棋盘，左上角坐标为(1,1)，右下角为(8,8)。一个机器人从(1,1)出发，每次只能向右或向下走一格。要到达(4,5)，有多少种不同的路径？（）

A. 20

B. 35

C. 56

D. 70

第2题中级 2分单选

某同学用冒泡排序对数组{6,1,5,2,4}进行升序排序，请问需要进行多少次元素交换？（）

A. 5

B. 6

C. 7

D. 8

第3题中级 2分单选

考虑以下C++函数，在main函数调用solve后，x和y的值分别是？（）

A. 5, 10

B. 10, 5

C. 10, 10

D. 5, 5

第4题中级 2分单选

函数calc(n)的定义如下，则calc(5)的返回值是多少？（）

A. 5

B. 6

C. 7

D. 8

第5题中级 2分单选

给定一个初始为空的整数栈S和一个空的队列P。按顺序处理输入的整数队列A：7、5、8、3、1、4、2。对于队列A中的每一个数，执行规则：如果该数是奇数，则将其压入栈S；如果该数是偶数，且栈S非空，则弹出一个栈顶元素，并加入到队列P的末尾；如果该数是偶数，且栈S为空，则不进行任何操作。当队列A中的所有数都处理完毕后，队列P的内容是什么？（）

A. 5, 1, 3

B. 7, 5, 3

C. 3, 1, 5

D. 5, 1, 3, 7

第6题中级 2分单选

编译器的主要作用是什么（）

A. 直接执行源代码

B. 将源代码转换为机器代码

C. 进行代码调试

D. 管理程序运行时的内存

第7题中级 2分单选

有5个男生和3个女生站成一排，规定3个女生必须相邻，问有多少种不同的排列方式（）

A. 4320种

B. 5040种

C. 3600种

D. 2880种

第8题中级 2分单选

在C/C++中，(char)('a'+13)与下面的哪一个值相等（）

A. 'm'

B. 'n'

C. 'z'

D. '3'

第9题中级 2分单选

假设有序表中有1000个元素，则用二分法查找元素x最多需要比较（）次

A. 25

B. 10

C. 7

D. 1

第10题中级 2分单选

下面哪一个不是操作系统名字（）

A. Notepad

B. Linux

C. Windows

D. macOS

第11题中级 2分单选

在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（）。

A. unsigned

B. const

C. static

D. bool

第12题中级 2分单选

假设有一个链表的节点定义如下：

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并确保新节点插入到原先头部节点的前面（成为新的头部），执行的步骤应该是（）。

A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;

B. Node* newNode = new Node; newNode->data = 42; head->next = newNode;

C. Node* newNode = new Node; newNode->data = 42; newNode->next = head->next; head->next = newNode;

D. Node* newNode = new Node; newNode->data = 42; head = newNode;

第13题中级 2分单选

根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（）。

A. 6

B. 7

C. 8

D. 9

第14题中级 2分单选

以下哪个不是操作系统？（）

A. Linux

B. Windows

C. Android

D. HTML

第15题中级 2分单选

后缀表达式"6 2 3 + - 3 8 2 / + * 2 ^ 3 +"对应的中缀表达式是（）

A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3

B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3

C. (6 - (2 + 3) * 3 + 8 / 2) ^ 2 + 3

D. 6 - (2 + 3) * 3 + 8 / 2 ^ 2 + 3

第16题中级 2分判断

阅读程序（3）

将第18行的"f[i][j]=std::max(f[i][j],std::max(f[i-1][j],f[i][j-1]));"删去后，并不影响程序运行结果。（）

T. 正确

F. 错误

第17题中级 1分判断

阅读程序（2）

假设输入的n为正整数，输出的答案一定小于等于n，大于等于1。（）

T. 正确

F. 错误

第18题中级 1分判断

阅读程序（3）

当程序运行完毕后，对于所有的1≤i,j≤n，都一定有f[i][j]≤f[n][n]。（）

T. 正确

F. 错误

第19题中级 1分判断

阅读程序（1）

当输入为"10"时，程序的第一个输出为"4"，第二个输出为"17"。（）

T. 正确

F. 错误

第20题中级 1分判断

阅读程序（1）

若将isPrime(i)函数中的条件改为i<=n/2，输入"20"时，countPrimes(20)的输出将变为"6"。（）

T. 正确

F. 错误

第21题中级 1分判断

阅读程序（1）

sumPrimes函数计算的是从2到n之间的所有素数之和。（）

T. 正确

F. 错误

第22题中级 1分判断

阅读程序（3）

当b为负数时，customFunction（a，b）会陷入无限递归。（）

T. 正确

F. 错误

第23题中级 1分判断

阅读程序（3）

当输入为"2 3"时，customFunction（2,3）的返回值为"64"。（）

T. 正确

F. 错误

第24题中级 1分判断

阅读程序（2）

当输入两个完全相同的字符串时，g函数的返回值总是true（）

T. 正确

F. 错误

第25题中级 1分判断

阅读程序（2）

f函数的返回值等于两个输入字符串的最长公共子串的长度。（）

T. 正确

F. 错误

第26题中级 1分判断

阅读程序（2）

f函数的返回值小于等于min(n,m）。（）

T. 正确

F. 错误

第27题中级 1分判断

阅读程序（1）

假设输入的所有数都为不超过1000的正整数：

程序总是输出四位小数（）

T. 正确

F. 错误

第28题中级 1分判断

阅读程序（1）

假设输入的所有数都为不超过1000的正整数：

将第7行中的"（s-b）*（s-c）"改为"（s-c）*（s-b）"不会影响程序运行的结果（）

T. 正确

F. 错误

第29题中级 1分判断

阅读程序（1）

假设输入的所有数都为不超过1000的正整数：

当输入为“2 2 2”时，输出为“1.7321”（）

T. 正确

F. 错误

第30题中级 1分判断

阅读程序（2）

当m为1时，输出的第一行总为n。（）

T. 正确

F. 错误

第31题中级 1分判断

阅读程序（2）

假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数。

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

T. 正确

F. 错误

第32题中级 1分判断

阅读程序（2）

假设 int 为 32 位有符号整数类型，输入的 n 是不超过 47000 的自然数、k 是不超过 int表示范围的自然数。

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

T. 正确

F. 错误

第33题中级 1分判断

阅读程序（1）

当输入为"2 2"时，输出为"59"。（）

T. 正确

F. 错误

第34题中级 2分单选

完善程序（2）

（精明与糊涂）有N个人，分为两类：
i）精明人：永远能正确判断其他人是精明还是糊涂；
ii）糊涂人：判断不可靠，会给出随机的判断。
已知精明人严格占据多数，即如果精明人有k个，则满足k>N/2。
你只能通过函数query(i,j)让第i个人判断第j个人：返回true表示判断结果为"精明人"；返回false表示判断结果为"糊涂人"。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。
以下程序利用"精明人占多数"的优势。设想一个"消除"的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

③处应填（）

A. query(candidate,i)==true

B. query(i,candidate)==true

C. query(candidate,i)==false

D. query(candidate,i)==false||query(i,candidate)==false

第35题中级 2分单选

完善程序（2）

（精明与糊涂）有N个人，分为两类：
i）精明人：永远能正确判断其他人是精明还是糊涂；
ii）糊涂人：判断不可靠，会给出随机的判断。
已知精明人严格占据多数，即如果精明人有k个，则满足k>N/2。
你只能通过函数query(i,j)让第i个人判断第j个人：返回true表示判断结果为"精明人"；返回false表示判断结果为"糊涂人"。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。
以下程序利用"精明人占多数"的优势。设想一个"消除"的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

①处应填（）

A. 0

B. 1

C. N

D. -1

第36题初级 3分单选

完善程序（2）

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace）一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

④处应填（）

A. dp[i-1][j-1]+1

B. dp[i-1][j-1]

C. dp[i-1][j]

D. dp[i][j-1]

第37题初级 3分单选

完善程序（2）

（编辑距离）给定两个字符串，每次操作可以选择删除（Delete）、插入（Insert）、替换（Replace）一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

②处应填（）

A. j

B. i

C. m

D. n

第38题中级 2分单选

完善程序（1）

（字符串解码）"行程长度编码"（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：
i）如果原始字符串中一个字符连续出现N次（N≥2），在压缩字符串中它被表示为"字符+数字N"。例如，编码"A12"代表12个连续的字符A。
ii）如果原始字符串中一个字符只出现1次，在压缩字符串中它就表示为该字符本身。例如，编码"B"代表1个字符B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

⑤处应填（）

A. i

B. i--

C. i++

D. count++

第39题中级 2分单选

完善程序（1）

（字符串解码）"行程长度编码"（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：
i）如果原始字符串中一个字符连续出现N次（N≥2），在压缩字符串中它被表示为"字符+数字N"。例如，编码"A12"代表12个连续的字符A。
ii）如果原始字符串中一个字符只出现1次，在压缩字符串中它就表示为该字符本身。例如，编码"B"代表1个字符B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

①处应填（）

A. i<z.length()

B. i<z.length()-1

C. i+1<z.length()

D. i+1<=z.length()

第40题中级 3分单选

完善程序（2）

（汉诺塔问题）给定三根柱子，分别标记为 A、B 和 C。初始状态下，柱子 A 上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子 C 上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则：只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。每次只能移动一个圆盘。小圆盘必须始终在大圆盘之上。

②处应填（）

A. src,tmp

B. src,tgt

C. tmp,tgt

D. tgt,tmp

第41题中级 3分单选

完善程序（1）

问题：给定一个正整数 n，希望判断这个数是否为完全平方数，即存在一个正整数 x 使得 x 的平方为 n。

①处应填（）

A. 1

B. 2

C. 3

D. 4

第42题中级 3分单选

完善程序（1）

问题：给定一个正整数 n，希望判断这个数是否为完全平方数，即存在一个正整数 x 使得 x 的平方为 n。

②处应填（）

A. (int)floor(sqrt(num)-1)

B. (int)floor(sqrt(num))

C. floor(sqrt(num/2))-1

D. floor(sqrt(num/2))

第43题中级 3分单选

完善程序（2）

（汉诺塔问题）给定三根柱子，分别标记为 A、B 和 C。初始状态下，柱子 A 上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子 C 上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则：只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部。每次只能移动一个圆盘。小圆盘必须始终在大圆盘之上。

⑤处应填（）

A. 0

B. 1

C. i-1

D. i

第44题中级 2分单选

以下对递归方法的描述中，正确的是：( )

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

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

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

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

第45题中级 2分单选

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

A. 12

B. 13

C. 14

D. 15

第46题中级 2分单选

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

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

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

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

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

第47题中级 2分单选

以下哪组操作能完成在双向循环链表结点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;

第48题中级 2分单选

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

A. 数组不能排序，链表可以

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

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

D. 以上均正确

第49题中级 2分单选

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

A. 将x的值赋为201

B. 将y的值赋为101

C. 将q指向x的地址

D. 将p指向y的地址

第50题中级 2分单选

假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（）

A. 1111，1110，101，100，110，0

B. 1111，1110，101，100，110，0

C. 1111，1110，101，100，110，0

D. 1111，1110，101，100，110，0

第51题中级 2分单选

一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（）

A. 1420

B. 1770

C. 1540

D. 2200

第52题中级 3分单选

阅读程序（3）

如果输入x=3和y=3，则程序的最终输出为（）

A. 27

B. 81

C. 144

D. 256

第53题中级 3分单选

阅读程序（2）

当输入的cost数组为{1,100,1,1,1,100,1,1,100,1}时，程序的输出为（）

A. 6

B. 7

C. 8

D. 9

第54题中级 3分单选

完善程序（1）

（枚举因数）从小到大打印正整数n的所有正因数。

①处应填( )

A. n % i == 0

B. n % i == 1

C. n % (i-1) == 0

D. n % (i-1) == 1

试卷题目预览

一个8×8的棋盘，左上角坐标为(1,1)，右下角为(8,8)。一个机器人从(1,1)出发，每次只能向右或向下走一格。要到达(4,5)，有多少种不同的路径？（）

某同学用冒泡排序对数组{6,1,5,2,4}进行升序排序，请问需要进行多少次元素交换？（ ）

考虑以下C++函数，在main函数调用solve后，x和y的值分别是？（ ）

函数calc(n)的定义如下，则calc(5)的返回值是多少？（ ）

编译器的主要作用是什么（ ）

有5个男生和3个女生站成一排，规定3个女生必须相邻，问有多少种不同的排列方式（ ）

在C/C++中，(char)('a'+13)与下面的哪一个值相等（ ）

假设有序表中有1000个元素，则用二分法查找元素x最多需要比较（ ）次

下面哪一个不是操作系统名字（ ）

在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）。

假设有一个链表的节点定义如下：

根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）。

以下哪个不是操作系统？（ ）

后缀表达式"6 2 3 + - 3 8 2 / + * 2 ^ 3 +"对应的中缀表达式是（ ）

阅读程序（3）

阅读程序（2）

阅读程序（3）

阅读程序（1）

阅读程序（1）

阅读程序（1）

阅读程序（3）

阅读程序（3）

阅读程序（2）

阅读程序（2）

阅读程序（2）

阅读程序（1）

阅读程序（1）

阅读程序（1）

阅读程序（2）

阅读程序（2）

阅读程序（2）

阅读程序（1）

完善程序（2）

完善程序（2）

完善程序（2）

完善程序（2）

完善程序（1）

完善程序（1）

完善程序（2）

完善程序（1）

完善程序（1）

完善程序（2）

以下对递归方法的描述中，正确的是：( )

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

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

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

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

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

假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）

一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）

阅读程序（3）

阅读程序（2）

完善程序（1）

📝 题目纠错

💬 吐槽/建议

某同学用冒泡排序对数组{6,1,5,2,4}进行升序排序，请问需要进行多少次元素交换？（）

考虑以下C++函数，在main函数调用solve后，x和y的值分别是？（）

函数calc(n)的定义如下，则calc(5)的返回值是多少？（）

编译器的主要作用是什么（）

有5个男生和3个女生站成一排，规定3个女生必须相邻，问有多少种不同的排列方式（）

在C/C++中，(char)('a'+13)与下面的哪一个值相等（）

假设有序表中有1000个元素，则用二分法查找元素x最多需要比较（）次

下面哪一个不是操作系统名字（）

在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（）。

根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（）。

以下哪个不是操作系统？（）

后缀表达式"6 2 3 + - 3 8 2 / + * 2 ^ 3 +"对应的中缀表达式是（）

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

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

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

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

假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码？（）

一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么有多少种可能的组合？（）