这又是一篇没有代码的题解

这个题解不会根据一年年的来，而是根据题型来的。大家收好啊…orz

题型1——数学题

1.1集合计算

1、（NOIP2004–T1-单选）设全集 $I=$ { $a, b, c, d, e, f, g$ }，集合 $A =$ { $a, b, c$ }， $B =$ { $b, d, e$ }， $C=$ { $e, f, g$ }，那么集合 $(A-B)\cup($ ~ $C\cap B)$ 为（ A）。
A. { $a, b, c, d$ } B. { $a, b, d, e$ } C. { $b, d, e$ } D. { $b, c, d, e$ } E. { $d, f, g$ }

画韦恩图！

2、（NOIP2015–T2-单选）设全集 $I =$ { $a, b, c, d, e, f, g, h$ }，集合 $A\cup B =$ { $a, b, c, d, e, f$ }， $A\cap C =$ { $c, d, e$ }， $A\cap$ ~ $B =$ { $a, d$ }，那么集合 $A\cap B\cap C$ 为（）。
A. { $c, e$ } B. { $d, e$ } C. { $e$ } D. { $c, d, e$ } E. { $d, f$ }

这道题画个韦恩图就出来了

这个题型好像只有很久之前有考到过…算是在数学上的中等难度的题了，OIer需要好好学习掌握数学知识啊！

1.2组合数学

1、（NOIP2004–T2-单选）由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（D ）个。
A. 40320 B. 39600 C. 840 D. 780 E. 60

有一定难度的组合数学题，由于要出现“abc”，所以把 1 个 a，1 个 b，1 个 c 捆绑起来，这样相当于现在有 1 个“abc”，2 个“a”，4 个“b”，1 个“c”进行排列，根据我以前给出的“不尽相异元素的全排列”的公式知道，总的情况是8!/(2!*4!)=840，但是 2 个“a”，4 个“b”，1 个“c”也有可能组成“abc”，840里有重复的情况，比如（abc）abcabbb 和 abc(abc)abbb 其实是一种情况，所以要减去 2 个“a”，4 个“b”，1 个“c”也组成 abc 的情况（其实就是只有两个元素的容斥原理），那么这就相当于 2 个“abc”，一个“a”，3 个“b”的全排列数＝6!/(2!*3!)=60，所以总的情况数是 840-60=780。

这个一直在考，以前放选择现在放填空，但和数学竞赛比还是差了一点的

1.3拓扑排序

1、（NOIP-2004–T20-多选）某大学计算机专业的必修课及其先修课程如下表所示：
历年NOIP提高组初赛选择解析（未完结）

这个好像也比较简单…图一画就可以了。

题型2——算法基础

2.1栈

1、（NOIP2004–T3-单选）某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（E）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7

手动模拟=答案

这个其实还好，每年都会考一道的，只要注意模拟就好了，然后有些会告诉你栈的上限所以要注意一下

2.2树

2.2.1二叉树的节点个数计算

1、（NOIP-2004–T4-单选）满二叉树的叶结点个数为 $N$ ，则它的结点总数为（C ）。
A. $N$ B. $2 * N$ C. $2 * N – 1$ D. $2 * N + 1$ E. $2N – 1$

基本知识：
- 满二叉树的节点个数=2*子节点个数-1
- 满二叉树的节点个数=2^树的深度-1

2、（NOIP-2005–T4-单选）完全二叉树的结点个数为 $4 * N + 3$ ，则它的叶结点个数为（E ）。
A. $2 * N$ B. $2 * N - 1$ C. $2 * N + 1$ D. $2 * N - 2$ E. $2 * N + 2$
这个也基本年年考，一般都是满二叉树的计算，但基本都是送分的

2.2.2先序-中序-后序遍历

1、（NOIP-2004–T5-单选）二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ B）。
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1

常规题，根据前序确定子树的根再到中序当中划分子树建树

这个也是常规题，而且有套路

2.3字符串

2.3.1最长公共子串

1、（NOIP-2005–T1-单选）字符串“ababacbab”和字符串“abcba”的最长公共子串是（B ）。
A. abcba B. cba C. abc D. ab E. bcba

这个很简单，暴力或者KMP匹配下？

2.4图论

2.4.1最小生成树

1、（NOIP-2005–T5-单选）平面上有五个点 A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图 G 的顶点，每两点之间的直线距离是图 G 中对应边的权值。图 G 的最小生成树中的所有边的权值综合为（ D ）。
A. $8$ B. $7+ \sqrt5$ C. $9$ D. $6+ \sqrt5$ E. $4+2\sqrt2 + \sqrt5$

这个最快的做法应该是prim吧…手动跑一把就可以了

题型3——编码计算机理论基础

3.1进制转换

1、（NOIP-2004–T6-单选）十进制数100.625等值于二进制数（B ）。
A. 1001100.101 B. 1100100.101 C. 1100100.011 D. 1001100.11 E. 1001100.01

2、（NOIP-2004–T13-多选） $(2004)_{10} + (32)_{16}$ 的结果是（BCD ）。
A. $(2036)_{16}$ B. $(2054)_{10}$ C. $(4006)_8$ D. $(100000000110)_2$ E. $(2036)_{10}$

3、（NOIP-2005–T3-单选）以下二进制数的值与十进制数23.456 的值最接近的是（ D）。
A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111

又是一个基础，高进制和低进制的转换包括小数位建议大家都去百度一下，不详细讲

3.2硬件基础

1、（NOIP-2004–T7-单选）下面哪个部件对于个人桌面电脑的正常运行不是必需的（C ）。
A. CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存

ABDE你家里电脑拆开来都可以马上看得到，光驱是用来放光盘的所以你不用光盘就可以不需要装了（我就没有装，还改了个固态硬盘233）

2、（NOIP-2004–T12-多选）下列哪个（些）是 64 位处理器（ ACDE ）。
A. Intel Itanium B. Intel Pentium III C. AMD Athlon64
D. AMD Opteron E. IBM Power 5

说实话这个题我真的没什么办法…都是十多年前的古董…上古时代的神器吧…

3、（NOIP-2004–T12-多选）下列哪个（些）不是计算机的存储设备（AC ）。
A. 文件管理器 B. 内存 C. 显卡 D. 硬盘 E. U盘

这个是真的常识orz，文件管理器就是你电脑上的资源管理器…内存其实可以存储（临时）

4、（NOIP-2004–T17-多选）下列说法中正确的有（ ADE ）。
A. CPU 的基本功能就是执行指令。
B. CPU 的主频是指 CPU 在 1 秒内完成的指令周期数，主频越快的 CPU 速度一定越快。
C. 内部构造不同的 CPU 运行相同的机器语言程序，一定会产生不同的结果。
D. 在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。
E. 数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。

B的话主频的定义对的，但是CPU速度还跟其他东西有关；C大部分情况下都是对的但不排除特殊的情况…

5、（NOIP-2004–T18-多选）彩色显示器所显示的五彩斑斓的色彩，是由哪三色混合而成的（ ACD ）。
A. 红 B. 白 C. 蓝 D. 绿 E. 橙

这个常识，不讲

6、（NOIP-2005–T6-单选）下列设备中没有计算功能的是（ E ）。
A. 笔记本电脑 B. 掌上电脑 C. 智能手机 D. 电子计算器 E. 液晶显示器

常识，不讲

7、（NOIP-2005–T7-单选）Intel 的首颗 64 位处理器是（ E ）。
A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium

这个也是古董了…但由于比较特殊还是记一笔吧…8086是首颗16位的，80386是第一颗32位

这种题真的是妖的不行，基本靠积累，还有就是你的日常常识了orz

3.3网络基础

1、（NOIP-2004–T8-单选）下列哪个网络上常用的名字缩写是错误的（D ）。
A. WWW（World Wide Web）
B. URL（Uniform Resource Locator）
C. HTTP（Hypertext Transfer Protocol）
D. FTP（Fast Transfer Protocol）
E. TCP（Transfer Control Protocol）

这个错的比较明显，D的‘F’是值file，fast是什么鬼

2、（NOIP-2004–T10-单选）一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（A ）。
A. 调制解调器 B. 路由器 C. 网卡 D. 网关 E. 网桥

网卡网关和网桥是网络之间的协议转换器，调制解调器就是我们说的猫…现在估计都不用了orz，路由器就是我们现在使用的那种WiFi啥的…orz

3、（NOIP-2005–T8-单选）常见的邮件传输服务器使用（ B ）协议发送邮件。
A. HTTP B. SMTP C. TCP D. FTP E. POP3

这个信息课都会讲的，你不知道就是没有好好听！上课怎么又在睡觉！！！

还是要积累

3.4输入输出设备

1、（NOIP-2004–T9-单选）用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ C）。
A. 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪

这个考的比较偏了，即使是那个年代激光打印也很少普及…现在针式打印应该没怎么见到了orz

3.5软件常识

1、（NOIP-2004–T14-多选）下列哪个（些）不是数据库软件的名称（ D）。
A. MySQL B. SQL Server C. Oracle D. Outlook E. Foxpro

好像只要记SQL是数据库，然后记几个特殊的Oracle，FoxPro，Access…这种

2、（NOIP-2004–T16-多选）下列哪个（些）软件属于操作系统软件（BE）。
A. Microsoft Word B. Windows XP C. Foxmail D. 金山影霸 E. Red Hat Linux

这个也很简单好么…都是比较常见的…

3、（NOIP-2005–T9-单选）不能在 Linux 上使用的网页浏览器是（ A ）。
A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla

这个很明显嘛…笨笨的IE就只能在Windows上跑啊…

3.6语言基础

1、（NOIP-2004–T19-多选）下列哪个（些）程序设计语言支持面向对象程序设计方法（ ABDE ）。
A. C++ B. Object Pascal C. C D. Smalltalk E. Java

C++，object Pascal，VB，smalltalk，simula（第一个面向对象的语言），Java是面向对象的
free Pascal，C是面向过程的

3.7内存计算

1、（NOIP-2005–T10-单选）一位艺术史学家有 20000 幅 1024 * 768 的真彩色图像，如果将这些图像以位图形式保存在 CD 光盘上（一张 CD 光盘的容量按 600M 计算），大约需要（ C ）张 CD 光盘。
A. 1 B. 10 C. 100 D. 1000 E. 10000

这个上课的也会讲…虽然它没说拿24位还是32位来算，24位就是 $1024*768*3/1024/1024=2MB$ ，总共20000张图片就是 $20000*2MB$ ，大约要 $40000/600$ ，差不多就是100张

3.8逻辑运算

1、（NOIP-2005–T11-多选）
历年NOIP提高组初赛选择解析（未完结）

这个你一个个推过去就行，用短路算法可能会稍微快一点

题型4——计算机/OI的史/常识

1、（NOIP-2004–T11-多选）美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献包括（BC）。
A. 提出理想计算机的数学模型，成为计算机科学的理论基础。
B. 提出存储程序工作原理，对现代电子计算机的发展产生深远影响。
C. 设计出第一台具有存储程序功能的计算机EDVAC。
D. 采用集成电路作为计算机的主要功能部件。
E. 指出计算机性能将以每两年翻一番的速度向前发展。

A的数学模型是图灵，D的话冯诺依曼1957年去世1958年开始用集成电路orz，E是摩尔定律…

这个好像年年考，不是冯诺依曼就是图灵吧…大家多多了解就可以了

历年NOIP提高组初赛选择解析（未完结）