2025年CSP-J第一轮笔试模拟试卷（一）

一、单项选择题（共15题，每题2分，共计30分）

以下与电子邮件相关的协议是（ ）。 A. FTP B. SMTP C. HTTP D. DNS

二进制数11010110转换为十进制的结果是（ ）。 A. 214 B. 216 C. 218 D. 220

一棵有7个结点的完全二叉树的高度是（ ）。 A. 3 B. 4 C. 5 D. 6

设x=3，y=5，以下逻辑运算表达式结果为真的是（ ）。 A. (x>y) && (x<y) B. (x!=y) || (x>y) C. (x+y) == 8 D.!(x==y)

以下数据结构中，插入和删除操作不需要移动元素的是（ ）。 A. 数组 B. 栈 C. 队列 D. 链表

冒泡排序算法的时间复杂度是（ ）。 A. O(n) B. O(nlogn) C. O(n²) D. O(1)

在C++中，以下哪个关键字用于声明常量变量？（ ） A. static B. const C. auto D. volatile

已知有序表(10, 15, 20, 25, 30, 35, 40)，采用二分查找法查找元素25，需要比较的次数是（ ）。 A. 1 B. 2 C. 3 D. 4

若一棵二叉树的先序遍历为ABC，中序遍历为BAC，则该二叉树的后序遍历为（ ）。 A. BCA B. CBA C. ACB D. ABC

以下关于图的说法错误的是（ ）。 A. 有向图可能存在环 B. 无向图中任意两点间可能存在多条边 C. 连通图的任意两点间存在路径 D. 树一定是连通图

十进制数-37的8位二进制补码是（ ）。 A. 10010101 B. 10100101 C. 11010101 D. 11100101

以下哪个算法常用于图的广度优先搜索？（ ） A. 栈 B. 队列 C. 递归 D. 分治

有5个不同颜色的球，从中任取3个，不同的取法有（ ）种。 A. 5 B. 10 C. 15 D. 20

下列代码段的时间复杂度是（ ）。

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

 for (int j=1; j<=i; j++) {

    // 执行一次操作

 }

}

A. O(n) B. O(n²) C. O(nlogn) D. O(1) 15. 以下不属于算法基本特征的是（ ）。 A. 有穷性 B. 确定性 C. 输入/输出 D. 唯一性 二、程序理解题（共3题，每题10分，共计30分） 题1：阅读以下程序，回答问题。

#include

using namespace std;

int func(int n) {

 if (n == 1) return 1;

 return func(n-1) + n;

}

int main() {

 int x = 5;

 cout << func(x) << endl;

 return 0;

}

（1）程序输出结果为（ ）。 A. 5 B. 10 C. 15 D. 20 （2）函数func的调用次数为（ ）。 A. 3 B. 4 C. 5 D. 6 （3）该程序的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n²) D. O(logn) 题2：阅读以下程序，判断正误。

#include

using namespace std;

int isPrime(int n) {

 if (n <= 1) return false;

 for (int i=2; i*i<=n; i++) {

    if (n % i == 0) return false;

 }

 return true;

}

int main() {

 int x = 17;

 if (isPrime(x)) cout << "是质数" << endl;

 else cout << "不是质数" << endl;

 return 0;

}

（1）程序输出结果为"是质数"。（ ） A. 正确 B. 错误 （2）函数isPrime的时间复杂度为O(n)。（ ） A. 正确 B. 错误 （3）若将x改为21，输出结果将变为"不是质数"。（ ） A. 正确 B. 错误 题3：阅读以下程序，回答问题。

#include

using namespace std;

int main() {

 int a = {1, 3, 5, 7, 9};

 int sum = 0;

 for (int i=0; i<5; i++) {

    if (a[i] % 2 == 0) continue;

    sum += a[i];

 }

 cout << sum << endl;

 return 0;

}

（1）程序输出结果为（ ）。 A. 15 B. 20 C. 25 D. 30 （2）循环执行次数为（ ）。 A. 3 B. 4 C. 5 D. 6 （3）若将continue改为break，输出结果将变为（ ）。 A. 1 B. 3 C. 4 D. 0 三、程序填空题（共3题，每题10分，共计30分） 题1：补全以下代码，实现求1到n之间所有质数的和。

#include

using namespace std;

int isPrime(int n) {

 if (________) return false;

 for (int i=2; i*i<=n; i++) {

    if (n % i == 0) return false;

 }

 return true;

}

int sumPrimes(int n) {

 int s = 0;

 for (int i=2; i<=n; i++) {

    if (________) {

       s += i;

    }

 }

 return s;

}

int main() {

 int x = 20;

 cout << sumPrimes(x) << endl;

 return 0;

}

：____ ：____ 题2：补全以下代码，实现冒泡排序（升序）。

#include

using namespace std;

void bubbleSort(int a[], int n) {

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

    for (int j=0; j<________; j++) {

       if (a[j] > a[j+1]) {

          int temp = a[j];

          a[j] = a[j+1];

          a[j+1] = temp;

       }

    }

 }

}

int main() {

 int a[] = {5, 3, 8, 2, 1};

 int n = 5;

 bubbleSort(a, n);

 for (int i=0; i<n; i++) {

    cout << a[i] << " ";

 }

 return 0;

}

：____ 题3：补全以下代码，实现计算斐波那契数列的第n项。

#include

using namespace std;

int fib(int n) {

 if (n <= 2) return 1;

 return fib(n-1) + ________;

}

int main() {

 int x = 6;

 cout << fib(x) << endl;

 return 0;

}

：____

以下是答案解析：

一、单项选择题

B

FTP（文件传输协议）、HTTP（超文本传输协议）、DNS（域名系统）与电子邮件无关，SMTP（简单邮件传输协议）用于发送邮件。

A

按权展开：11010110 = 1×2^7 + 1×2^6 + 1×2^4 + 1×2^2 = 128 + 64 + 16 + 4 = 214

A

完全二叉树的高度公式：h = ⌊log₂n⌋ + 1，n=7时，h=3。

D

A项逻辑矛盾，B项x>y不成立，C项x+y=8不成立，D项!(x==y)为真。

D

链表通过指针连接，插入删除只需修改指针，无需移动元素。

C

两层循环，时间复杂度为O(n²)。

B

const声明常量，static用于静态变量，auto自动类型推导，volatile防止编译器优化。

B

二分查找：第一次比较中间值25，第二次比较找到，共2次。

A

先序ABC，中序BAC，可知根为A，左子树B，右子树C，后序遍历左-右-根，即BCA。

D

树是连通无环图，但连通图不一定无环。

A

-37的原码为10100101，反码11011010，补码10010101。

B

广度优先搜索使用队列实现。

B

C₅² = 5×4/2 = 10种组合。

B

外层循环n次，内层循环次数为1+2+...+n，总次数为n(n+1)/2，即O(n²)。

D

算法特征包括有穷性、确定性、输入/输出、可行性，无需唯一性。

二、程序理解题 题1

（1）C

func(5) = func(4) + 5 = func(3) + 4 + 5 =... = 1 + 2 + 3 + 4 + 5 = 15 （2）C

func递归调用5次（从n=5到n=1） （3）B

递归次数为O(n) 题2

（1）A

17是质数，正确输出 （2）B

时间复杂度为O(√n)，因i*i≤n （3）A

21不是质数，输出正确 题3

（1）A

仅计算奇数项：1+3+5+7+9=25 （2）C

循环执行5次，每次判断a[i]%2 （3）B

break后仅执行第一次循环，sum=3

三、程序填空题 题1

：n <= 1

：isPrime(i) 题2

：n-1-i

每次循环确定一个最大值的位置，内层循环次数减少 题3

：fib(n-2)

斐波那契数列递归公式：f(n) = f(n-1) + f(n-2)