#4770. 2021年CSP-J 初赛试题
一、单选题(共15题,每题2分,共计30分;每题有且只有一个正确选项。)
- 以下不属于面向对象程序设计语言的是( )。
- 以下奖项与计算机领域最相关的是( )。
- 目前主流的计算机储存数据最终都是转换成( )数据进行储存。
- 以比较作为基本运算,在 个数中找出最大数,最坏情况下所需要的最少的比较次数为 ( )。
- 对于入栈顺序为 的序列,下列( )不是合法的出栈序列。
- 对于有 个顶点、 条边的无向连通图 ,需要删掉( )条边才能使其成为一棵树。
- 二进制数 对应的十进制数是( )。
- 如果一棵二叉树只有根结点,那么这棵二叉树高度为 。请问高度为 的完全二叉树有 ( )种不同的形态?
- 表达式 的后缀表达式为( ),其中 和 是运算符。
- 个人,两个人组一队,总共组成三队,不区分队伍的编号。不同的组队情况有( )种。
- 在数据压缩编码中的哈夫曼编码方法,在本质上是一种( )的策略。
- 由 1,1,2,2,3 这五个数字组成不同的三位数有( )种。
- 考虑如下递归算法
则调用 solve(7) 得到的返回结果为( )。
- 以 为起点,对下边的无向图进行深度优先遍历,则 四个点中有可能作为最后一个遍历到的点的个数为( )。
- 有四个人要从 A 点坐一条船过河到 B 点,船一开始在 A 点。该船一次最多可坐两个人。 已知这四个人中每个人独自坐船的过河时间分别为 ,且两个人坐船的过河时间为两人独自过河时间的较大者。则最短( )时间可以让四个人都过河到 B 点(包括从 B 点把船开回 A 点的时间)。
二、阅读程序(程序输入不超过数组或字符串定义的范围;判断题正确填 √ ,错误填 × ;除特殊说明外,判断题 1.5 分,选择题 3 分,共计 40 分)
·判断题
输入的 等于 时,程序不会发生下标越界。( )
输入的 必须全为正整数,否则程序将陷入死循环。( )
当输入为 5 2 11 9 16 10 时,输出为 3 4 3 17 5。( )
当输入为 1 511998 时,输出为 18。( )
将源代码中 g 函数的定义( 行)移到 main 函数的后面,程序可以正常编译运行。( )
·单选题
当输入为 2 -65536 2147483647 时,输出为( )。
判断题
输出的第二行一定是由小写字母、大写字母、数字和 构成的字符串。( )
可能存在输入不同,但输出的第二行相同的情形。( )
输出的第一行为 。( )
单选题 设输入字符串长度为 ,decode 函数的时间复杂度为( )
当输入为 时,输出的第二行为()。
(3.5 分)当输入为 时,输出的第二行为( )。
假设输入的 是不超过 的自然数,完成下面的判断题和单选题:
判断题
若输入不为 ,把第 13 行删去不会影响输出的结果。( )
(2 分) 第 25 行的 可能存在无法整除而向下取整的情况。 ( )
(2 分) 在执行完 init() 后,f 数组不是单调递增的,但 g 数组是单调递增的。 ( )
单选题
init 函数的时间复杂度为( )。
在执行完 init() 后, 中有()个等于 。
(4 分) 当输入为 时,输出为()。
三、完善程序(单选题,每小题 3 分,共计 30 分)
(Josephus 问题) 有 个人围成一个圈,依次标号 至 。从 号开始,依次 交替报数,报到 的人会离开,直至圈中只剩下一个人。求最后剩下人的编号。
试补全模拟程序。
①处应填( )
②处应填( )
③处应填( )
④处应填( )
⑤处应填( )
①处应填 ( )
②处应填 ( )
③处应填 ( )
④处应填 ( )
⑤处应填 ( )