NOIP 提高组 2017 第一轮试卷

从（ ）年开始，NOIP 竞赛将不再支持 Pascal 语言。

在 $8$ 位二进制补码中，$10101011$ 表示的数是十进制下的（ ）。

分辨率为 $1600\times 900$、$16$ 位色的位图，存储图像信息所需的空间为（ ）。

2017 年 10 月 1 日是星期日，1949 年 10 月 1 日是（ ）。

设 $G$ 是有 $n$ 个结点、$m$ 条边 $(n \leq m)$ 的连通图，必须删去 $G$ 的（ ）条边， 才能使得 $G$ 变成一棵树。

若某算法的计算时间表示为递推关系式：

表达式 $\texttt{a * (b + c) * d}$ 的后缀形式是（ ）。

由四个不同的点构成的简单无向连通图的个数是（ ）。

将 $7$ 个名额分给 $4$ 个不同的班级，允许有的班级没有名额，有（ ）种不 同的分配方案。

若 $f_0 = 0, f_1 = 1, f_{n + 1} = \dfrac{f_n + f_{n - 1}}{2}$，则随着 $i$ 的增大，$f_i$ 将接近于( )。

设 $A$ 和 $B$ 是两个长为 $n$ 的有序数组，现在需要将 $A$ 和 $B$ 合并成一个排好序的 数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 （ ）次比较。

在 $n(n \geq 3)$ 枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重）,如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c 三行代码补全到算法中。 a. A ← X ∪ Y b. A ← Z c. n ← |A| 算法 Coin(A, n)

有正实数构成的数字三角形排列形式如图所示。第一行的数为 $a_{1,1}$；第二行的数从左到右依次为 $a_{2,1}$，$a_{2,2}$；… 第 $n$ 行的数为 $a_{n,1}, a_{n,2},\dots, a_{n,n}$。从 $a_{1,1}$ 开始，每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i+1,j}$ 和 $a_{i+1,j+1}$。用动态规划算法找出一条从 $a_{1,1}$ 向…

小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第 $1$ 个航班准点的概率是 $0.9$，第 $2$ 个航班准点的概率为 $0.8$，第 $3$ 个航班准点的概率为 $0.9$。如果存在第 $i$ 个（$i=1,2$）航班晚点，第 $i+1$ 个航班准点，则小明将赶不上第 $i+1$ 个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是（ ）。

欢乐喷球：儿童游乐场有个游戏叫“欢乐喷球”，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有一 圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。

以下排序算法在最坏情况下时间复杂度最优的有（ ）。

对于入栈顺序为 $a, b, c, d, e, f, g$ 的序列，下列（ ）不可能是合法的出栈序列。

下列算法中，（ ）是稳定的排序算法。

以下是面向对象的高级语言的有（ ）。

以下和计算机领域密切相关的奖项有（ ）。

如右图所示，共有 $13$ 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 $1$ 变 $0$，或由 $0$ 变 $1$）。现在要使得所有的格子中的数字都变为 $0$，至少需要_________次操作。

如下图所示，$A$ 到 $B$ 是连通的。假设删除一条细的边的代价是 $1$，删除一条粗的边的代价是 $2$，要让 $A,B$ 不连通，最小代价是（________）（2 分），最小代价的不同方案数是（_______）（3 分）。（只要有一条删除的边不同，就是不同的方案）