#I. 乔斯2024 CSP-J 初赛模拟赛（三）

A B C D E F G H I J

客观题

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

在 IEEE 754 标准中，一个规格化的 32 位浮点数 x 的真值表示为

若一浮点数 x 的 754 标准储存格式为(41360000）16,则其十进制数值为（）

314.625
63.125
11.375
303.125

在计算机系统中，采用总线结构便于实现系统的积木化构造，同时可以（）。

提高数据传输速度
提高数据传输量
减少信息传输线的数量
减少指令系统的复杂性

如果某系统 15*4=112 成立，则该系统采用的是（）进制。

4.将多项式 $2 ^7 + 2^5 + 2^2 + 2^0$ 表示为十六进制数，其值为（）。

5.一张分辨率为 4K 的 32 位真彩色照片，在不压缩的情况下，其存储容量为（）。 {{ select(5) }}

16KB
128KB
33.75MB
270MB

6.下列问题中不可用贪心算法求得最优解的是（）。 {{ select(6) }}

哈夫曼编码
活动安排问题
0-1 背包问题
单源最短路径

7.线性表采用链式存储时，节点的存储地址（）。

必须是不连续的
连续与否均可
必须是连续的
和头结点的存储地址相连续

8.树是一种非线性数据结构，其最适合用来表示（）。 {{ select(8) }}

有序数据元素
无序数据元素
元素之间具有分支层次关系的数据
元素之间无联系的数据

9.二叉树是一种特殊的树，一颗二叉树的第 k 层的节点数最多为（）。 {{ select(9) }}

2k-1
2k+1
$2^k-1$

10.设连通图 G 中的边集 E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点 a出发可以得到的一种深度优先遍历的顶点序列为（）。

abedfc
acfebd
abcedf
abcdef

11.随着世界各国互联网应用的发展，越来越多的 IP 地址被不断分配给最终用户，这样一来，IP 地址近乎枯竭，在这样的情况下，IPv6 应运而生，IPv6 采用（）位二进制表示网络地址。

12.有 7 个一模一样的苹果，放到 3 个不同的盘子中，每个盘子中至少有 1 个苹果的放法一

共有（）种。

13.在博士学位的授予仪式上，执行主席看到一脸稚气的维纳，颇为惊讶，于是就当面询问他的年龄，维纳不愧为数学申通，他的回答十分巧妙：“我今年岁数的立方是一个四位数，岁数的四次方是一个六位数，这两个数，刚好把十个数字 0、1、2、3、4、5、6、7、8、9全都用上了，不重不漏。这意味着全体数字都向我俯首称臣，预祝我将来在数学领域里一定能干出一番惊天动地的大事业”维纳此言一出，四座皆惊，大家都被他的这道妙题深深地吸引住了，整个会场上的人，都在议论他的问题。请问当年维纳的年龄是（）。

14.新上任的宿舍管理员拿到 10 把钥匙去开 10 个房间的们，他知道没把钥匙只能开其中的一个门，但不知道每把钥匙是开那一个门的钥匙，现在要打开所有关闭着的 10 个房间，他最多要试开（）次。

15.通过（）技术，人类实现了世界范围的信息资源共享，世界变成了“地球村”。

现代交通
现代通信
计算机网络
现代基因工程

二.阅读程序（判断题1.5分，选择题3分，共计40分）

判断题

1).第 03 行和 04 行的功能相似，都是定义变量，交换定义，即

const int maxn=50;

#define y 2021

程序运行结果不变()

2).将第 15 行移动到第 12 行行末，程序运行结果不变()

3)输入的 n 的范围为[1,50],若超过这个范，则程序运行结果会出错（）

4).根据第 14 行程序可知，对于 1<=i,j<=n,c[i][j]的值肯定比 c[i-1][j-1]的值大（）

单选题

5).当输入 n=7 时，输出结果为 ( ）

6).当输入 n=17 时，输出结果为（）

1728
1435
65536
131072

判断题

1).将第 15 行 tmp=rand()%(right-left)+left 换成 tmp=(right+left)/2，程序运行结果不变 (） {{ select(22) }}

2).第 28 行和第 29 行的递归调用，每次只能调用其中一个。（） {{ select(23) }}

3).第 22 行和第 24 行的 while 循环，程序每次运行都会至少执行 1 次循环

（） {{ select(24) }}

单选题

4).此程序的时间复杂度是（）。 {{ select(25) }}

O(log n)
O( $n^2$ )
O(nlog n)
O(n)

5).若输入数据为

4 7 5

则程序的运行结果是（）。 {{ select(26) }}

0.(375)
1.(375)
0.375
1.375

6)若输入数据为

80 90 40 50 20 30 10 60 70 100

则程序的运行结果是（）。 {{ select(27) }}

判断题

1).程序的输出结果有可能是0 () {{ select(28) }}

2).数组a中的值要么是0，要么是1，没有其他值（） {{ select(29) }}

3).第25行的while循环每次执行至少执行1次 {{ select(30) }}

单选题

4).此程序的时间复杂度是（）

O(n)
O(nlog n)
O( $n^2$ )
O( $n^3$ )

5).若n=3,则输出结果为（）

6).若输入n=7，则输出结果为（）。

16384
57344
65536
131072

三、完善程序

（1）（过河问题）在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一做独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n(2<=n<100)和这n个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

例如，有三个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，则总共最少需要的时间为7，具体方法是：甲、乙一起过桥到达河的左岸，甲单独回到河的右岸并将灯带回，然后甲、丙在一起过桥到河的左岸，总时间为2+1+4=7。

1).①处应填（）。

num<=0
num<=1
num<=2
num<=3

2).②处应填（）。 {{ select(35) }}

go(LEFT_TO_RIGHT)
go(RIGHT_TO_LEFT)
go(LEFT)
go(RIGHT)

3).③处应填（）。 {{ select(36) }}

pos[i]==LEFT && pos[i+1]==LEFT
pos[i]==LEFT || pos[i+1]==LEFT
pos[i]==LEFT
pos[i]!=LEFT

4).④处应填（）。 {{ select(37) }}

go(RIGHT_TO_LEFT)+hour[i]
go(LEFT_TO_RIGHT)+hour[i]
min(hour[i],hou[i+1])+hour[i]
hour[i]

5).⑤处应填（）。 {{ select(38) }}

pos[i]=LEFT_TO_RIGHT
pos[i]=RIGHT_TO_LEFT
pos[i]=LEFT
pos[i]=RIGHT

2.（黑白棋）在一个4x4的棋盘上摆放了14颗棋子，其中由7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，称为棋子的一步，黑白双方交替走棋，任意一方可以先走，如果在某个时刻使得任意一种颜色的棋子形成四个一条线（包括斜线），则这样的状态称为目标棋局，棋盘的初始状态如下。