NOIP 提高组 2012 第一轮试卷

目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。

（ ）是主要用于显示网页服务器或者文件系统的 HTML 文件内容，并让用户与这些文件交互的一种软件。

目前个人电脑的( )市场占有率最靠前的厂商包括 Intel、AMD 等公司。

无论是 TCP/IP 模型还是 OSI 模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。

如果不在快速排序中引入随机化，有可能导致的后果是（ ）。

1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于（）计算机。

在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

8.地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 16 位，其最大的可寻址空间为 64KB。如果地址总线是 32 位，则理论上最大可寻址的内存空间为（ ）。

以下不属于目前 3G（第三代移动通信技术）标准的是（）。

10.仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述，错误的是（ )。

如果对于所有规模为 $n$ 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为 $O(2^n)$。

从顶点 $A_0$ 出发，对有向图（ ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是 $A_0,A_1,A_2,A_3,A_4$。

如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 $a,b,c$（如下图所示），另有元素 $d$ 已经出栈，则可能的入栈顺序有（ ）。

在计算机显示器所使用的 RGB 颜色模型中，（）属于三原色之一。

一棵二叉树一共有 $19$ 个节点，其叶子节点可能有（ ）个。

已知带权有向图 $G$ 上的所有权值均为正整数，记顶点 $u$ 到顶点 $v$ 的最短路径的权值为 $d(u, v)$。若 $v_1, v_2, v_3, v_4, v_5$ 是图 $G$ 上的顶点，且它们之间两两都存在路径可达，则以下说法正确的有（ ）。

逻辑异或（$\oplus$）是一种二元运算，其真值表如下所示。 以下关于逻辑异或的性质，正确的有（ ）。

十进制下的无限循环小数（不包括循环节内的数字均为 $0$ 或均为 $9$ 的平凡情况），在二进制下有可能是（ ）。

以下（ ）属于互联网上的 E-mail 服务协议。

以下关于计算复杂度的说法中，正确的有（ ）。

本题中，我们约定布尔表达式只能包含 $p, q, r$ 三个布尔变量，以及“与”（$\land$）、“或”（$\lor$）、“非”（$\neg$）三种布尔运算。如果无论 $p, q, r$ 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，$(p\land q)\lor r$ 和 $p\lor (q\lor r)$ 等价，$p\lor \neg p$ 和 $q\lor \neg q$ 也等价；而 $p\lor q$ 和 …

对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 $5$ 个不同的独立集（$1$ 个双点集合、$3$ 个单点集合、$1$ 个空集），图 2 有 $14$ 个不同的独立集。那么，图 3 有_________个不同的独立集。