主定理、NP 问题

2021 CCF 非专业级别软件能力认证第一轮（模拟二）

1. CPU、存储器、I/O 设备是通过 总线 连接起来的。

2. Linux 不是 通过扩展名来区分文件类型的。（第二次错了！！！）

3. dll 是 windows 的扩展名。

4. 启动计算机引导 DOS 是将操作系统从 系统盘 调入 存储器。

《一本通》CSP-S 第一套初赛模拟试题

1. 标准 ASCII 编码是一种 $7$ 位二进制编码，剩下一位是 $0$，用于奇偶校验。（从最多表示 $2^7=128$ 种字符也可以看出来）

2. puchar() 中可以加字符也可以加数字（$0\sim 127$），表示字符的 ASCII 码值。

3. A 类 IP 段：$0.0.0.0\sim 127.255.255.255$（$0、127$ 段不能用）

   B 类 IP 段：$128.0.0.0 \sim 191.255.255.255$

   C 类 IP 段：$192.0.0.0\sim 223.255.255.255$

2021 CCF 非专业级别软件能力认证第一轮（模拟三）

1. .hk 不是 国家顶级域名。

2. 图片文件格式：jpg、bmp、avif。

   不是图片文件格式：cdf。

3. 范内瓦·布什 在 1945 年发表的论文《诚如所思》中提出了微缩摄影技术和麦克斯储存器的概念，开创了数字计算机和搜索引擎时代。

4. 如有参加者提前离开考点，除身体特别原因外，须在 考试进行2小时后 方可准予离开。

绍兴一中 CCF-CSP-S1 模拟试题一

1. 应用层 协议有 FTP、HTTP、SMTP。

绍一中 2021 CCF 非专业级别软件能力认证第一轮（模拟）

1. 内存的技术指标有 容量、频率、存取时间、延迟。

2. 矩阵乘法目前最优时间复杂度是 $O(n^{2.3728596})$。

3. van Emde Boas tree 支持值域 $0\sim n-1$，单次 $O(\log\log n)$ 内支持插入删除以及求前驱后继出现次数。

4. 无法在 $O(\log n)$ 内判断素数。

5. 闰年：四年一闰，百年不闰，四百年再闰。

6. ASCII 码：

空格	$32$
”0“	$48$
”A“	$65$
”a“	$97$

7. PHP 属于弱类型语言，对变量的类型要求并不那么严格。

绍兴一中 NOIP 2018 初赛模拟卷

1. 浮点数在计算机内的表示顺序是 符号位 $+$ 阶码 $+$ 尾码。

2. 在物理线路上提供可靠的数据传输的是 ISO/OSI 参考模型的 数据链路层。

3. 万维网（WWW）的采用 URL 定位信息所在的位置。

4. 汇编程序：将 汇编语言源程序 翻译成 机器语言程序 的系统软件。

5. “信息论之父”是 香农，他提出了熵。

6. TCP/IP 共有 $4$ 层：应用层、传输层、网络层、数据链路层。

7. 浮点数在计算机内的表示除了符号位外还是用了 原码、移码。

8. Solaris 是操作系统软件。

9. 黎曼猜想、P=NP 都没有被证明是正确的。背包问题是一个 NPC 问题、基于比较的排序算法的时间复杂度下限是 O(nlogn)。

10. “光纤之父”是 高锟。

11. ENIAC 没有 采用冯诺依曼的程序存储结构。

12. 最大团问题（最大独立集问题） 是 NPC 问题。

NOIP 2013 提高组初赛试题

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

2. 满二叉树：出最后一层无任何叶子节点外，每一层上的所有节点都有两个子节点。

   完全二叉树：一棵深度为 $k$ 的有 $n$ 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 $i（1≤i≤n）$的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

   完全二叉树不一定是满二叉树，满二叉树一定是完全二叉树。

3. 不同形态的二叉树个数就是卡特兰数。

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

5. 所有的非确定性多项式时间可解的判定问题构成 NP 类问题。存在 $/$ 任何一个 P 类问题都是 NP 类问题。不属于 P 类的 $/$ 在指数时间内能解决的问题都不一定是 NP 问题。

NOIP 2015 提高组初赛试题

1. 数组储存单元地址要连续，链表储存单元地址连续或不连续都可以。

2. $n$ 个点 $m$ 条边的图用邻接表存储结构进行深度优先遍历或广度优先遍历的时间复杂度均为 $O(n+m)$。

3. Unix、Windows XP、Linux、Mac OS 都是操作系统。

NOIP 2011 提高组初赛试题

1. 寄存器是 CPU 的重要组成部分。

2. 用快速排序的思想实现求第 $k$ 大数的程序，不考虑最坏情况，理论最低时间复杂度为 $O(n)$。因为它的做法是：每次选一个基准点，用快速排序的方法把基准点放到一个合适的地方，使得它左边的都是小于它的，它右边都是大于它的，然后根据它的位置递归处理，时间复杂度为 $O(n)+O(n/2)+O(n/4)+\cdots = O(2n)=O(n)$。

3. 为解决 web 应用中的不兼容问题，保障信息的顺利流通，万维网联盟（W3C） 制定了一系列标准，涉及 HTML、XML、CSS 等，并建议开发者遵循。

4. 一个十六位数可以写成四位二进制位数。因此 $100$ 位十六进制数，考虑前导零，在二进制下有 $397\sim 400$ 位。

5. 汇编语言是一种与具体硬件 有关 的程序设计语言；在编写复杂程序时，相对于高级语言而言代码量大，且不易调试；可以直接访问寄存器、内存单元、I/O端口。

6. 计算机中的数值信息分为整数和实数（浮点数）。实数之所以能够表示很大或者很小的数，是由于使用了 阶码。

NOIP 2010 提高组初赛试题

1. Linux 不依靠扩展名来区分文件类别。

2. 在 $12$ 进制下，$12\times 12=144$。注意！十二进制下 $12=2+1\times 12=14$，原式等于 $14\times 14=(196)_{10}=(144)_{12}$。

3. 为了提高系统整体的执行效率，在 CPU 中引入了 高速缓存。

4. 现在大多数语言（C、C++、Pascal）都是 高级语言，低级语言已经很少了。编译语言是指编译时候直接编译成可以直接运行的程序，如 exe、dll 等，典型的有 C++、C、Pascal 等；解释语言需要有一个解释器去翻译，典型的有 Java、Python 等。

5. 原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关的排序算法，除了归并、计数、基数等之外都是原地排序。

6. 补码：只有负整数的编码最高位为 $1$；整数 $0$ 只有一个唯一的编码。

NOIP 2009 提高组初赛试题

1. BIOS 是 基本输入输出系统 的缩写。

拓展：BIOS 是一组固化到计算机内 主板 上一个 ROM 芯片上的程序。

2. 正数的补码就是真值本身负数的补码是符号位为 $1$，数值各位取反，最低位加 $1$。

3. CPU 全称为 中央处理器，能直接运行 机器语言，不是有 Intel 公司发明的（?）。

4. 一般的个人计算机在同一时刻只能存/取 一个 特定的内存单元。

2021年绍兴市中小学生编程比赛初赛试题 小学组

1. 下列计算机网络相关名词中文含义错误的是（ ）。
   A. VPN：虚拟专用网络 B. URL：统一资源定位系统
   C. HTTP：超文本传输协议 D. IP：因特网地址

答案：D。

错因：知识点。

分析：百度百科。IP 是 网络互连协议 的缩写。

---

7. 十进制算术表达式:5×128+3×64+7，运算结果用二进制表示为（ ）。
   A. 1101000111 B. 1101001111 C. 11001000111 D. 1111101101

答案：A。

错因：方法。

分析：不用死算，直接用二进制表示。原始可转化为：$4\times 2^7+2^7+2\times 2^7+2^6+2^2+2^1+2^0$，然后合并后发现只有 $9,8,6,2,1,0$ 这几位为 $1$，其他都是 $0$。

---

9. 在C++编程中定义一个数组：bool a[8][10],程序运行时占用（ ）内存空间。
   A．80字节 B．63字节 C．80位 D．160字节

答案：A。

错因：知识点。

分析：bool 型只有 一个 字节。

---

11．一个高度为h 的二叉树最小节点数目是（ ）。
A. 2h+1 B. h C. 2h-1 D. 2h

答案：B。

错因：知识点。

分析：维基百科。二叉树是每个节点 最多只有两个分叉 的树结构，而不是一定有两个分叉（那是满二叉树），那么高度为 $h$ 的二叉树节点最小的情况就是每一层只有一个节点的时候。

---

12. 由2个a，3个b和4个c构成的所有字符串中，包含子串“abc”的共有（ ）个。
    A. 420 B. 5040 C. 7 D. 390

答案：D。

错因：方法。

分析：用到 捆绑法 和 容斥 的思想。考虑将 $abc$ 看成一个元素 $d$，那么就是 $1$ 个 $a$，$2$ 个 $b$，$3$ 个 $c$，$1$ 个 $d$ 的排列，就是 $7!$，因为含有相同元素，还要除以 $1! \times 2! \times 3!$（因为相同元素内部排列一下还是一样的，$a_1a_2b$ 和 $a_2a_1b$ 是一样的）。计算一个 $abc$ 的情况算了两个 $abc$,还要算出两个 $abc$ 的再减去。

---

19. 小明收到了100枚1元硬币，其中有一枚是假币，其重量稍轻，如果使用不带砝码的天平称重，最少需要称（ ）次，确保一定可以找出假币。
    A．99 B. 4 C. 5 D.50

答案：C。

错因：方法。

分析：用三分法，每次把硬币分成三份，然后称两份，平衡的话一定在第三份，不平衡的话在轻的那份，继续三分。

选择题练习（三）

1. 集合 $A-$ 集合 $B$，相当于在 $A$ 除去 $B$ 中含有的元素。

2. 光驱是用来 读取光盘 的设备，显然不是必须的。而主板是计算机最重要的部分之一，上面安装了计算机的主要电路系统。

3. 用静电吸附墨粉后转移到纸张上，这是 激光打印机 的工作方式。

4. $1280\times 1024$ 的分辨率最清晰。

5. 十进制小数转化为二进制小数采用“乘 $2$ 取整，顺序排列”的方法。

6. CPU 所能访问的最大内存空间大小取决于 CPU 地址总线 的位宽

7. 访问速度 寄存器 $>$ 高速缓存 $>$ 访问 CPU。

2021年绍兴市中小学生编程比赛初赛试题 初中组

1. IP 地址有三种表示方法，其中最常见的是点分 $10$ 进制表示格式：其实 IP 地址是由一个 $32$ 位的二进制数所构成，不过这样比较难记，因此我们把 $32$ 位分成 $4$ 组，每组 $8$ 位，并将其用十进制表示，中间用点隔开。

   比如说 $61.256.72.4$ 就不是一个合法的 IP 地址，因为 $61$ 的二进制是 $111101$ 只有 $6$ 位，不满 $8$ 位。

2. 新一代互联网使用的 IPv6 标准是 IPv4 标准的补充和升级。IPv6 与 IPv5 一点关系没有，它是 IPv4 的替代版本。

3. 计算字串时候需要算上空串，最后要加上 $1$。计算公式：$n\times(n+1)/2+1-\text{重复子串的个数}$。

4. 插空法：要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物品插入空中，进行计数。

5. 冒泡排序：依次比较两个相邻的元素。
   选择排序：每次选出最大或最小的放在最前面。

选择题练习（四）

1. 图灵 提出理想计算机数学模型，成为计算机科学理论基础。

2. 冯诺依曼 提出存储程序工作原理；设计出第一台具有存储程序功能的计算机 EDVAC。

NOIP 2012 提高组初赛试题

1. 1949 年诞生于美国宾夕法尼亚大学的 ENIAC 属于电子管 （比晶体管拉）计算机。

拓展：ENIAC 是 第二台 电子计算机（第一台是 ABC）和第一台通用计算机。

2. 地址总线的位数决定了 CPU 可直接寻址的内存空间大小，若地址总线位数为 $n$，则 CPU 可直接寻址的内存空间大小为 $2^n$ 个字节。例如地址总线为 16 位，其最大的可寻址空间为 $2^{16} B =2^9 B\times 2^6 = 1024 KB \times 64 = 64 KB$；地址总线为 $32$ 为，最大可寻址空间为 $4294967296 = 4 GB$。

3. 因特网不是根据蜘蛛网发明的；伏特电池是根据电鱼发明的。

4. 三原色是指红、绿、蓝。

5. 异或满足 交换律 和 结合律，不满足关于与和或的分配律。

6. E-mail 服务协议有 POP3 和 SMTP。

7. 如果一个问题不存在多项式时间的算法，那它不一定是 NP 类问题；如果一个问题不存在多项式时间的算法，那它一定不是 P 类问题；如果一个问题不存在多项式空间的算法，那它一定不是 P 类问题。

8. 一棵任意形态的 $n$ 个节点的二叉树的叶子节点范围是 $1\sim \frac{n+1}{2}(\text{向下取整})$。

9. 问题：本题中，我们约定布尔表达式只能包含 p, q, r 三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。如果无论 p, q, r 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r 和 p∨(q∨r)等价，p∨¬p 和 q∨¬q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有_________个。

   答案：$256$。

   解析：三个变量的取值选择最多只有 $2^3=8$ 中可能，因为代入表达式中最后只有两种取值，那么不同的表达式有 $2^8=256$ 个。

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

    答案：$5536$。

    解析：手动树形 dp！设 $f_{i,0/1}$ 表示以 $i$ 为根的子树中，选/不选 $i$的独立集个数，有转移 $f_{i,0}=f_{lson_i,1}\times f_{rson_i,1}$，$f_{i,1}=(f_{lson_i,0}+f_{lson,1})\times(f_{rson_i,0}+f_{rson,1})$。