普及组 CSP-J2024 初赛模拟卷7

一、单项选择题(共15题，每题2分，共计 30 分;每题有且仅有一个正确选项)

1.在标准 ASCI 码表中，字符4的 ASCI码值用二进制表示是( )

{{ select(1) }}

• A.00000100
• B.00110100
• C.00110101
• D.00110011

2.关于树这种数据结构的下述说法，正确的是()。

{{ select(2) }}

• A.一个有m个顶点和 m-1条边的图就是树
• B.树中的任意两个顶点之间有且只有一条简单路径
• C.树中有的结点可能构成环
• D.若树根层次为1，则对应高度为n的二叉树最多有2”个结点

3.以下哪个不是输人设备?( )

{{ select(3) }}

• A.绘图仪
• B.触摸屏
• C.扫描仪
• D.麦克风

4.当a=3，b=2，c=1时，执行以下程序段后c=( )

if(a>b)
a=b;
if(b>c)
  b=c;
else
  c=b;
c=a--;

{{ select(4) }}

• A.0
• B.1
• C.2
• D.3

5.学生在大学选修某些课程时需要先上其他的前置课程，所有课程和课程间的先系构成一个有向图G，有向边<M,N>表示课程 M 是课程 N的先修课，则要找门课程L的全部先修课，下面哪种算法不可行?( )

{{ select(5) }}

• A. Dijkstra
• B.BFS
• C.DFS
• D. BFS+DFS

6.下列对语句 freopen("function.in"，"r"，stdin);的分析中正确的是( )

{{ select(6) }}

• A.freopen是文件名
• B.function.in 是重定向函数名
• C.r代表重定向为“写”方式
• D,语句将 cin 重定向到文件 function.in

7.Windows下可执行文件的扩展名是()

{{ select(7) }}

• A.com
• B. exe
• C. cpp
• D. dl1

8.[x]补码=10011000，其原码为()。

{{ select(8) }}

• A.011001111
• B.11101000
• C.11100110
• D.01100101

9.下面有关布尔类型的函数的说法，正确的是()。

{{ select(9) }}

• A.布尔类型函数只能返回0和1两个值
• B.布尔类型函数可以返回负数
• C.布尔类型函数必须有参数传递
• D.布尔类型函数可以返回NULL

10.下面有关格雷码的说法，错误的是()。

{{ select(10) }}

• A.在格雷码中，任意两个相邻的代码只有一位二进制数不同
• B.格雷码是一种可靠性编码
• C.在格雷码中，最大数和最小数只有一位二进制数不同
• D.格雷码是一种唯一性编码

11.现在有5个整数-2,-1,0,1,2,从中任意挑选两个整数,它们的和为0的概率是多少?

{{ select(11) }}

• A.1/6
• B.1/4
• C.1/5
• D.1/10

12.小明走楼梯，每次上台阶能跨1或2级。下面是走到第N步台阶的C++实现代码。

该段代码采用的是()算法。

int UpStairs(int N)
{
  if(N==1)
  return 1;
  else if(N==2)
  return 2;
  else
    return UpStairs(N-2)+ UpStairs(N-1);
  }

{{ select(12) }}

• A.递推
• B.贪心
• C.递归
• D.分治

13.某内容中仅会出现A,B,C,D,E,F,G，对应的出现概率分别为0.40,0.30,0.15,0.05,0.04,0.03,0.03，如下图所示。按照哈夫曼编码规则，假设B的编码为11，则D的编码为（ ）。

{{ select(13) }}

• A.10010
• B.10011
• C.10111
• D.10001

14.某学习小组有5名男生和3名女生,从中选3名男生和1名女生参加3项竞赛活每项活动至少有1人参加，则参赛方法有( )种。

{{ select(14) }}

• A.960
• B.1080
• C.2160
• D.540

15.简单无向连通图G有18条边,且每个顶点的度数为2,则图G有()个顶点

{{ select(15) }}

• A.81
• B.17
• C.18
• D.64

二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填√，错误除特殊说明外，判断题每题 1.5分，选择题每题3分，共计 40分)

（1）

判断题

16.将第8行中的 i=2改为i，程序的运行结果不会改变。（ ）

{{ select(16) }}

• A.正确
• B.错误

17.如果输入都是正整数、那么将第 10 行中的 a[1]替换成 a[0],将第 13 行中的 i-2替换成 i=1，程序的运行结果不会改变。（ ）

{{ select(17) }}

• A.正确
• B.错误

18。将第15行中的long long sum=0;替换成long long sum;，程序的运行结果不会改变。（ ）

{{ select(18) }}

• A.正确
• B.错误

19.将第18行中的 if(sum > maxx)替换成 if(sum >= maxx)，程序的运行结果不会改变。( )

{{ select(19) }}

• A.正确
• B.错误

选择题

20.若输入为7 1 6 5 4 3 2 1,则输出为( ).

{{ select(20) }}

• A.11
• B.2
• C.10
• D.3

21.若输入为15 9 4 5 3 3 2 1 2 1 1 1 1 1 1 1，则输出为（ ）

{{ select(21) }}

• A.4
• B.3
• C.2
• D.1

（2）

判断题

22.将judge函数和 main 函数的位置调换一下，程序的运行不受影响。( )

{{ select(22) }}

• A.正确
• B.错误

23.将第3行中的 bool改为 int，程序的运行结果不会改变。( )

{{ select(23) }}

• A.正确
• B.错误

24.该程序运行的时间复杂度是 O(nlogn)。

{{ select(24) }}

• A.正确
• B.错误

25.将第20行中的j=i+1改为j=1，程序的运行结果不会改变。( )

{{ select(25) }}

• A.正确
• B.错误

选择题

26.若输入n=24，则程序的输出为( )。

{{ select(26) }}

• A.15
• B.16
• C.14
• D.13

27.若程序的输出为20，则程序的输入可能为( )。

{{ select(27) }}

• A.38
• B.41
• C.40
• D.42

（3）

判断题

28.若将第8行中的while(left<right)替换为while(left<= right)，程序的运行结果不会改变。( )

{{ select(28) }}

• A.正确
• B.错误

29.若将第10行中的(left+right+1)/2替换为left+right+1>>1,程序的运行结果不会改变。( )

{{ select(29) }}

• A.正确
• B.错误

30.若将第23行中的(left+right)/2替换为left+(right-left)/2,程序的运行结果不会改变。( )

{{ select(30) }}

• A.正确
• B.错误

31.若将第48行中的 small(n,a,key)替换为(lower bound(a+1,a+n+1,b[i])-a)-程序的运行结果不会改变。( )

{{ select(31) }}

• A.正确
• B.错误

选择题

32.本程序运行的时间复杂度是( )

{{ select(32) }}

• A.O(1)
• B.O(n)
• C.O(n)
• D.O(nlogn)

33.若输入3 1 1 1 2 2 2 3 3 3,那么输出结果是( )

{{ select(33) }}

• A.27
• B.23
• C.18
• D.15

34(4分)若输入3 1 2 3 3 4 5 5 6 7,那么输出结果是( )。

{{ select(34) }}

• A.27
• B.21
• C.18
• D.15

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

(1) 一个nxn的正方形的黑白瓦片的图案要被转换成新的正方形图案。写一个程序来找出将原始图案按照下列转换方法转换成新图案所采用的最小序号的方式。 ①转 90°:图案顺时针旋转 90° ②转180°:图案顺时针旋转180°。 ③转 270°:图案顺时针旋转 270°。 ④反射:图案在水平方向翻转(以中央铅垂线为中心形成原图案的镜像) ⑤组合:图案在水平方向翻转，然后再按照①~③中的一种再次转换。 ⑥不改变:原图案不改变。 ⑦无效转换:无法用以上方法得到新图案。 如果有多种可用的转换方法，请选择序号最小的那个。 只使用上述7种步骤中的一个来完成这次转换。

输入格式:

第1行一个正整数 n。然后是n行，每行n个字符，全部为@或-，表示初始的正方形。接下来的n行，每行n个字符，全部为@或-，表示最终的正方形。

输出格式:

单独的一行包括1~7中的一个数字(在上文已描述)，表明需要将转换前的正方形变为转换后的正方形的转换方法。

输入样例:

3
@-@
---
@@-
@-@
@--
--@

输出样例:

1

数据范围:

对于 100%的数据，1≤n≤10。

35.①处应填( )

{{ select(35) }}

• A. b[j][n-i+1]=a[j][i]
• B. b[j][n-i]=a[j][i]
• C. b[j][n-i+1]=a[i][]
• D. b[j][n-i]=a[i][j]

36.②处应填( )

{{ select(36) }}

• A. b[n-i][n-j]=a[i][j]
• B. b[n-i+1][n-j+1]=a[i][j
• C. b[n-i][n-j]=a[j][i]]
• D. b[n-j+1][n-i+1]=a[i][j]

37.③处应填( )

{{ select(37) }}

• A. b[n-j+1][i]=a[i][j]
• B. b[n-j][i]=a[i][j]
• C. b[n-j+1][i]=a[j][i]
• D. b[n-j][i]=a[j][i]

38.④处应填()。

{{ select(38) }}

• A.b[n-j+1][i]=a[i][j]
• B.b[i][n-j]=a[i][j]
• C.b[i][n-j+1]=a[i][j]
• D.b[i][n-j]=a[j][i]

39.⑤处应填()。

{{ select(39) }}

• A. work1( )
• B. work2( )
• C. work3( )
• D. work4( )

(2) 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D₁、汽车油箱的容量C(以升为单位)、每升汽油能行驶的距离 D₂、出发点每升汽油的价格P、沿途加油站数N(N可以为零)、加油站i离出发点的距离D、每升汽油的价格P_i(1,2…N)。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出NoSolution。

输入格式:

第1行，D,C,D,P,N。接下来有N行。 第i+1行，两个数字，即加油站i离出发点的距离 D;和每升汽油的价格 P。

输出格式:

所需的最少费用，计算结果四舍五人至小数点后两位。如果无法到达目的地则输出 No Solution。

输入样例:

275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2

输出样例:

26.95

说明/提示:

N≤6，其余数字≤500。

40.①处应填（ ）

{{ select(49) }}

• A.D[N]= D1
• B.D[N+1]= D1
• C.D[1]= D1
• D.D[N-1]= D1

41.②处应填( )。

{{ select(41) }}

• A.req = D[i]- D[i-1]
• B.reg = D[i+1]- D[i]
• C.req = D[ni]+ D[i]
• D.req = D[ni]- D[i]

42.③处应填( )

{{ select(42) }}

• A.req = C
• B.req -= C
• C.req += C
• D.req %= C

43.④处应填()。

{{ select(43) }}

• A.cur += D[i+1]- D[i]
• B.cur -= D[i+1]- D[i]
• C.cur += D[ni]- D[i]
• D.cur -= D[ni]- D[i]

44.⑤处应填()。

{{ select(44) }}

• A. printf("%.2d\n",ans)
• B.printf("%2lf\n",ans)
• C.cout<<fixed<<setprecision(2)<<ans<<endl
• D.cout<<fixed<<setprecision(3)<<ans<<endl