解析

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

（1）以下哪一种设备属于输出设备

• 扫描仪、键盘、鼠标均属于输入设备
• 打印机属于输出设备

（2）下列四个不同进制的数中，与其它三项数值上不相等的是

• 269(16) = 0010 0110 1001(2)
• 617(10) = xxx
• 1151(8) = 0010 0110 1001(2)
• 1001101011(2) = 0010 0110 1011(2)

（3）1 MB 等于（ ）

1 GB = 1024 KB，1 KB = 1024 B

（4）广域网的英文缩写是（ ）

LAN 局域网，MAN 城域网，WAN 广域网

（5）中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。

1984年邓小平指出：“计算机的普及要从娃娃做起。”中国计算机学会于1984年创办全国青少年计算机程序设计竞赛（简 称：NOI）

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

81 /4 = 20 ... 1， 已经当前是第奇数轮，大写第一个 A。

（7）根节点深度为 0，一棵深度为 h 的满 k(k>1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（ ）个结点。

$s_h = k^0 + k^1 +k^2+...k^h = \dfrac{k^{h+1}-1}{k-1}$

（8）以下排序算法中，不需要进行关键字比较操作的算法是（ ）。

• 基数排序，计数排序不需要进行关键字比较
• 冒泡排序、堆排序、直接插入排序都需要进行关键字比较。

（9）给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的 数，至少需要 N - 1次比较操作。则最坏情况下，在该数组中同时找最大与 最小的数至少需要（ ）次比较操作。（ $\lceil \rceil$ 表示向上取整，$\lfloor \rfloor$ 表示向下取整）

奇数最大和最小的初始值设为第一个元素； 偶数前两个元素比较，最大初始值为大的元素，最小初始值为小的元素； 两个数枚举一次，那么次数分别是：

• 奇数：(3n+1)/2-2
• 偶数：3n/2-2

$\lceil \dfrac{3N}{2} \rceil - 2$

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

枚举是列举所有情况。 递归是自己调用自己，具有相同子问题。 贪心是每次选择当前的最优解，考虑局部最优。 分治可以将问题划分为几个小问题解决。

（11）由四个没有区别的点构成的简单无向连通图的个数是（ ）。

• 无向图：边没有方向
• 连通图：图中任意两点都是连通的
• 简单图：不含重边与自环的图
• C(4,2) = 6 在4个点中任意选2个点不相连。