NOIP 提高组 2016 第一轮试卷

以下不是微软公司出品的软件是（ ）。

如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、字母键 A、字母键 S 和字母键 D 的顺序来回按键，即 CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、……，屏幕上输出的第 81 个字符是字母（ ）。

二进制数 $00101100$ 和 $01010101$ 异或的结果是（ ）。

与二进制小数 $0.1$ 相等的八进制数是（ ）。

以比较作为基本运算，在 $N$ 个数中找最小数的最少运算次数为（ ）。

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

一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）。

$G$ 是一个非连通简单无向图，共有 $28$ 条边，则该图至少有（ ）个顶点。

某计算机的 CPU 和内存之间的地址总线宽度是 $32$ 位（bit），这台计算机最多可以使用（ ）的内存。

有以下程序：

有 $7$ 个一模一样的苹果，放到 $3$ 个一样的盘子中，一共有（ ）种放法。

Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人 A 向他（她）的朋友 B 分享了某张照片，那么 B 就可以对该照片进行评论；如果 B 评论了该照片，那么他 （她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非 A 也向他（她）分享了该照…

周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜 $10$ 分钟，然后切菜 $10$ 分钟，最后炒菜 $10$ 分钟。那么做一道菜需要 $30$ 分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（ ）分钟。

假设某算法的计算时间表示为递推关系式

给定含有 $n$ 个不同的数的数组 $L=\text{<}x_1,x_2,\dots,x_n\text{>}$。如果 $L$ 中存在 $x_i(1<i<n)$ 使得 $x_1<x_2<\dots<x_{i-1}< x_i>x_{i+1}>\dots>x_n$， 则称 $L$ 是单峰的，并称 $x_i$ 是 $L$ 的 “峰顶”。现在已知 $L$ 是单峰的，请把 a-c 三行代码补全到算法中使得算法 正确找到 $L$ 的峰顶。 a.Search(…

以下属于无线通信技术的有（ ）。

可以将单个计算机接入到计算机网络中的网络接入通讯设备有（ ）。

下列算法中运用分治思想的有（ ）。

下图表示一个果园灌溉系统，有 A、B、C、D 四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的有（ ）。

参加 NOI 比赛，以下能带入考场的有（ ）。

一个 $1\times 8$ 的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有_________种填涂方案。

某中学在安排期末考试时发现，有 $7$ 个学生要参加 $7$ 门课程的考试，下表列 出了哪些学生参加哪些考试（用√表示要参加相应的考试）。 最少要安排_________个不同的考试时间段才能避免冲突？