2021CCF非专业级别软件能力认证第--轮(CSP-S1)

考生注意事项：
•试题纸共有12页，答题纸共有1页，满分100分。请在答题纸上作答，写在试题纸上的 一律无效。
♦不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15题，每题2分，共计30分；每題有且仅有一个正确选项）

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

1.

假设输入的所有数的绝对值都不超过 1000，完成下面的判断题和单选题：
判断题：

单选题

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


假设输入的所有数的绝对值都不超过 1000，完成下面的判断题和单选题：
l 判断题

单选题

阅读程序三（程序输入不超过数组或字符串定义的范围；判断题正确填√错误填X除特殊说明外， 判断题1.5分，选择题3分，共计40分）
3
.

假设输入总是合法的（一个整数和一个不含空白字符的字符串，用空格隔开），完成下面
的判断题和单选题：
l 判断题

单选题

三、完善程序（单选题，每小题3分，共计30分）
(1)（魔法数字）小 H 的魔法数字是 4。给定 n，他希望用若干个 4 进行若干次加法、减法和整除运算得到 n。但由于小 H 计算能力有限，计算过程中只能出现不超过M= 10000 的正整数。求至少可能用到多少个 4。
例如，当 n= 2 时，有 2 = (4 + 4)/4，用到了 3 个 4，是最优方案.
试补全程序。

三、完善程序（单选题，每小题3分，共计30分）
(2) （RMQ 区间最值问题）给定序列a0,......，an，和m次询问，每次询问给定 l, r，求max {al，......，ar}，为了解决该问题，有一个算法叫 the Method of Four Russians，其时间复杂度为O(n + m)，步骤如下：
建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。
• 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根
的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。
• 注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1。
下面解决这个 ±1 RMQ 问题，“序列”指 Euler 序列：
设 t为 Euler 序列长度。取 b=|long2t/2|。将序列每 b 个分为一大块， 使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度O（n）。
• （重点）对于一个块内的 RMQ 问题，也需要O(1) 的算法。由于差分数组 2b-1种，可以预处理出所有情况下的最值位置，预处理复杂度 O(b2b,)，不超过 O(n)。
• 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ问题。
试补全程序。