NOIP 提高组 2013 第一轮试卷

一个 $32$ 位整型变量占用（ ）个字节。

二进制数 $11.01$ 在十进制下是（ ）。

下面的故事与（ ）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”

1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

已知一棵二叉树有 $2013$ 个节点，则其中至多有（ ）个节点有 $2$ 个子节点。

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有 $5$ 个顶点、$8$ 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。

斐波那契数列的定义如下：$F_1 = 1, F_2 = 1, F_n = F_{n - 1} + F_{n - 2} (n \geq 3)$。如果用下面的函数计算斐波那契数列的第 $n$ 项，则其时间复杂度为（ ）。

二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子 树上所有节点的值。那么，二叉查找树的（ ）是一个有序序列。

将 $(2, 6, 10, 17)$ 分别存储到某个地址区间为 $0\sim 10$ 的哈希表中，如果哈希函数 $h(x) =$ （ ），将不会产生冲突，其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被 使用（ ）位地址的 IPv6 协议所取代。

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。 那么，$12$ 个顶点的二分图至多有（ ）条边。

（ ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。

把 $64$ 位非零浮点数强制转换成 $32$ 位浮点数后，不可能（ ）。

对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

$T(n)$ 表示某个算法输入规模为 $n$ 时的运算次数。如果 $T(1)$ 为常数，且有递归式 $T(n) = 2\times T(\dfrac{n}{2}) + 2n$，那么 $T(n) =$ （ ）。

下列程序中，正确计算 $1, 2,\dots, 100$ 这 $100$ 个自然数之和 $sum$（初始值为 $0$）的是（ ）。

（ ）的平均时间复杂度为 $O(n \log n)$，其中 $n$ 是待排序的元素个数。

以 $A_0$ 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（ ）。

（ ）属于 NP 类问题。

CCF NOIP 复赛考试结束后，因（ ）提出的申诉将不会被受理。

某系统自称使用了一种防窃听的方式验证用户密码。密码是 $n$ 个数 $s_1, s_2,\dots , s_n$，均为 $0$ 或 $1$。该系统每次随机生成 $n$ 个数 $a_1, a_2, \dots , a_n$，均为 $0$ 或 $1$，请用户回答 $(s_1a_1 + s_2a_2 + \dots + s_na_n)$ 除以 $2$ 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于…

现有一只青蛙，初始时在 $n$ 号荷叶上。当它某一时刻在 $k$ 号荷叶上时，下一时刻将等概 率地随机跳到 $1, 2, \dots, k$ 号荷叶之一上，直至跳到 $1$ 号荷叶为止。当 $n = 2$ 时，平均一共跳 $2$ 次；当 $n = 3$ 时，平均一共跳 $2.5$ 次。则当 $n = 5$ 时，平均一共跳_________次。