2024CSP-J原创初赛模拟卷10

（认证时间：2023年9月16日 09:30~11:30）
*
基本信息：
姓名：
姓名：
班级：
班级：
学校:
学校:

一、单项选择题（每题只有一个正确选项，每题2分，共30分）

*
1. 以下哪一项不是组成冯诺依曼计算机的部件（）
A. 运算器
B. 存储器
C. 输入设备
D. 网络设备
*
2. 两位老师带四个学生去坐有六个位置的圆形旋转木马，那么两位老师不相邻的概率是（）
A.3/5
B.2/3
C.11/15
D.1/2
*
3. 已知一棵二叉树的先序遍历序列为 ABDGCEFH， 中序遍历序列为 DGBAECHF，则后序遍历序列为（）
A. GDBAEHFC
B. GDBEHFCA
C. GDBEFHCA
D. GDBECHFA
*
4.关于以下代码片段，正确的是（）
int a[5], *pa;
pa = a;
pa = pa +2;
A.指针 pa指向a[2]
B.指针 pa指向的内容是a[0]+2
C.指针 pa指向a[0]
D.代码语法有误，无法正常运行
*
5.王老师去银行兑换面值5元，10元，20元的人民币，已知王老师总共花费500元，且兑换得人民币45张，则有多少种兑换方法（）。
A.13
B.14
C.15
D.16
*
6.八进制数字777和二进制数字111的和是 （）
A.（1000000110）2
B.（516）10
C.（1066）8
D.（517）10
*
7.班上的6位学生将要去3个不同的考点参加C++编程大赛，每个考点由一名老师带领两名同学参加，现有3位老师可带领学生们参赛，人员分配由班主任决定，请你帮班主任算算一共有几种不同的参赛方案（）
A.360种
B.540种
C.720种
D.1080种
*
8. 小明买了一个存储空间为 256G 的手机，用于存放 256G 内容的硬件属于哪一种硬件?
A. 内存
B. 外存
C. 高速缓冲存储器(cache)
D. 输入设备
*
9.张老师最近在想要办理一个新的宽带网络，运营商给了张老师四种方案，张老师想要办理性价比最高的一条（即宽带速率/宽带价格最大），请你帮张老师算一算以下哪个方案性价比最高（）
A.129元/月 300Mb/s
B.62元/月 20MB/s
C.500元/月 1000Mb/s
D.200元/月 100MB/s
*
10.元素A，B，C，D，E依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则以下不可能的出栈序列是（）。
A. EDCBA
B. DCEAB
C. DECBA
D. ABCDE
*
11.在一个包含n个顶点的有向图中，如果所有顶点的出度和为s，则所有顶点的入度和为（）
A.n
B.s
C.n-1
D.s-(s/n)
*
12.某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度（根结点在第1层）为（）
A.3
B.6
C.8
D.12
*
13. 一棵二叉树不具有的性质是（ ）
A. 可能有结点没有孩子
B. 一定没有环
C. 每个结点最多两个孩子
D. 每个节点都有父亲结点
*
14.在一个单链表中，已知q节点是p节点的前驱节点，若在p和q之间插入节点s，则必须执行（）
A.s->next=p->next;p->next=s;
B.s->next=p;q->next=s;
C.p->next=s->next;s->next=p;
D.p->next=s;s->next=q;
*
15.func(12)的结果是
int func (int x) {
return 2 == x ? 1 : x + func(x - 2);
}
A.29
B.33
C.37
D.41

二、程序阅读理解题（共3大题。程序输入不超过数组或字符串定义的范围，除特殊说明外，判断题1.5分，选择题3分，共计40分）

（1）（10分）



判断题

*
16.该算法的时间复杂度为（ ）
对
错
*
17. q中的元素最多不超过n*m个（ ）(2.5分)
对
错
*
18.将58行的代码删去，程序的运行情况是（）
A.运行结果错误
B.对程序运行无影响
C.运行效率降低
D.运行效率加快
*
19. 将dis数组的初始值从inf改为下列中的哪一个，程序一定仍能正常运行（）
A.n+m
B.n*m/2
C.2*n
D.maxn²

（2）（14.5分）



l判断题

*
20. 将第30行改为double mid = (l+r) >>1，程序仍能正常运行( )
对
错
*
21. 将31行的r=mid改为r=mid-1,程序结果将会错误（ ）
对
错
*
22. 将eps的值改为1e-2,程序运行结果仍然正确( ) (2.5分)
对
错
*
23. 若把17行删去，输出的结果（）
A.一定比原来大
B.一定比原来小
C.不变
D.无法确定
*
24. 计算该算法的时间复杂度（）
A.O(n^2)
B.O(n)
C.O(n log r)
D.O(n log n)
*
25. 将l（英文L）的初始值改为1，则程序将会（）
A. 仍能正确运行
B. 仍能正确运行，且效率更高
C. 运算结果可能会错误
D. 运算结果一定会错误

（3）（15.5分）



假定在所有数据中，保证m<=10*n

l判断题

*
26. 在该程序中，任何一个p数组里面的元素最多只会被调用一次（ ）
对
错
*
27. 将42行的排序删去，程序的运行结果不会改变，但运行时间增加（ ）（2分）
对
错
*
28. 在一次输入中输入的一组r,s 分别为 8 2,则程序将会（）
A. 因发生数组越界程序中断
B. 因栈溢出而中断
C. 无任何影响，可以正确运行
D. 整数溢出，输出不合理数据
*
29. 将题目中第24行的endp[c]改为p[c].size()，以下情况不可能发生的是（）
A. 程序运行时间变长
B. 变量未被使用而浪费内存空间
C. 对程序效率几乎无影响
D. 程序发生错误运行中断
*
30. 题目中dfs函数的最坏时间复杂度是（）
A.O(n)
B.O(n*m)
C.O(m^n)
D.O(m)
*
31. 该算法最坏情况下时间复杂度为 （）
A.O(m log m)
B.O(n log n)
C.O(n)
D.O(m)

三、程序完善题（共2大题，每个选择题3分，共计30分）

1. （选择数对）有 n 个小朋友分别拿着一个数字，现在要求你将小朋友两两配对，要求每对小朋友手上的数字之差大于给定值 k。问最多可以从数组中选出多少对符合条件小朋友。（每个小朋友最多只能和另外一个小朋友配对，不能脚踏两条船）

输入格式：第一行给出 n，k 分别表示小朋友的个数，以及参数 k。()，接下来给出 n 个数字，表示每个小朋友手上的数字。

提示：二分最终的结果，对于二分的结果 mid，在 check 函数中 O(n) 判断能否选出 mid 对小朋友符合要求，最终保留二分的结果。


*
32. 1 处应该填的代码是: （）
A. j = 1
B. j = n - mid
C. j = n - mid + 1
D. j = mid
*
33. 2 处应该填的代码是:（）
A.a[i] - a[j] > k
B. a[i] - a[j] <= k
C. a[j] - a[i] > k
D. a[j] - a[i] <= k
*
34. 3 处应该填的代码是:（）
A. 1
B. 0
C. n/2
D. a[1]
*
35. 4 处应该填的代码是:（）
A. l = mid
B. r = mid
C. l = mid + 1
D. r = mid - 1
*
36. 5 处应该填的代码是:（）
A. l = mid
B. r = mid
C. l = mid + 1
D. r = mid - 1

2．（接龙）对于一个长度为k的整数序列:，我们称之为接龙序列当且仅当的首位数字等于的末位数字，对于所有。

现在给定一个长度为n的数列，请问从中最少删除多少个数，使得剩下的序列是一个接龙序列。

数据保证：1<=n<=10^5,1<=ai<=10^9



*
37. ①处应填（）
A. (x % p)
B. (x / p)
C. (x / 10) % p
D. (x % 10) / p
*
38. ②处应填（）
A. x / 10
B. x % 2
C. x % 10
D.x[-1]
*
39. ③处应填（）
A. dp[i+1][fi]
B. dp[i+1][la]
C. dp[i][fi]
D. dp[i][la]
*
40. ④处应填（）
A. dp[i][fi]
B. dp[i][la]
C. dp[i][fi] + 1
D. dp[i][la] + 1
*
41. ⑤处应填（）
A. ans * 2
B.ans + 1
C. n - ans
D. ans - 1
问卷星提供技术支持
举报