noip初赛

运算符

			联结词名称
异或 ⊕
非¬（-）			否定
与∧（·）	对应集合∩交集	对应按位与符号&	合取
或∨（+）	对应集合∪并集	对应按位或符号\|	析取
条件→	X→Y，X为true时只有Y为true才能返回true，X为false一定返回true		蕴涵
双条件↔	X↔Y，对应同或		等价
优先级	¬高于∧，∧高于∨，∨高于→

http://blog.csdn.net/wizardforcel/article/details/76551820（逻辑讲解）
http://www.wlxt.uestc.edu.cn/wlxt/ncourse/lsxx/web/lssx/end/imgs/5/5.1.2.htm

运算规则

非(P 且 Q) = (非 P) 或 (非 Q)
非(P 或 Q) = (非 P) 且 (非 Q)

P 或 (非P) = 1
P 且 (非P) = 0

A + (B + C) = (A + B) + C
A · (B · C) = (A · B) · C
A · (B + C) = A · B + A · C
A + (B · C) = (A + B) · (A + C)

（交换律、结合律、分配律）

原命题为：若a，则b。逆否命题为：若非b，则非a。原命题和逆否命题为等价命题。
对于这个原命题，逆命题为：若b，则a，否命题为：若非a，则非b，逆命题和否命题等价
如果提到“XXXX,反之亦然”，一般理解为原命题成立，且原命题的逆命题也成立（根据http://blog.sina.com.cn/s/blog_4fc8afbf0102vjld.html；但是在日常生活中有其他用法，也可能是误用），或者说原命题的条件和结论是等价的

ASCII

48-->0 57-->9 64-->A 90-->Z 97-->a 122-->z

树

1、结点拥有的子树数称为结点的度
2、度为0的结点称为叶子结点
3、树的度是树内各结点的度的最大值
4、结点的层次/深度从根开始定义起，根为第1/0层（1还是0看定义，一般是1）
5、树中结点的最大层次/深度称为树的深度或高度
(引自考研大纲解析38页：树的深度是从根节点开始（其深度为1）自顶向下逐层累加的，而高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。我的理解是：非根非叶结点的深度是从根节点数到它的，高度是从叶节点数到它的。)

（以下定义根节点层次/深度为1)

6、在二叉树的第i层上至多有2^(i-1)个结点
7、深度为k的二叉树至多有2^k-1个结点
8、深度为k的完全二叉树至少有2^(k-1)（=2^(k-1)-1+1）个节点
9、对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1

理解：二叉树当中的结点只有度为0、1、2三种情况,度为0就是终端结点.构造二叉树的过程就是从原始结点开始“生长”结点的过程,初始状态下,原始结点就是终端结点,n0=1,n1=0,n2=0,每当一个原来的终端结点变成“1度结点”的时候只是把终端的位置向下移动了一点,n1++,不影响n0和n2,而每当一个原来的终端结点变成“2度结点”的时候,原来的终端消失,增加两个终端,总效果就是n0++,n2++,所以二叉树当中的n0和n2总是同步增加,即总是满足n0=n2+1

10、具有n个结点的完全二叉树的深度为log2n+1

11、完全二叉树中度为1的结点数只有两种可能0或1

12、给定节点数量的二叉树，在完全二叉树的情况下可以得到最多的叶子节点，叶子节点最多的个数与节点总数的奇偶有关，奇数个则有(n-1)/2+1个，偶数个则有n/2个

理解：二叉树有一个性质，即叶子节点 = 度为2的节点数+1。所以二叉树叶子节点最多的时，即度为2的节点数也最多，这种情况出现在完全二叉树中。

计算机知识

数据库

关系型数据库：

简单来说，关系模型指的就是二维表格模型，而一个关系型数据库就是由二维表及其之间的联系所组成的一个数据组织。

数据库系统的数据结构可以认为是多张二维表，二维表中的列称为字段，行存放数据。

Oracle、DB2、PostgreSQL、Microsoft SQL Server、Microsoft Access、MySQL、浪潮K-DB、Sybase、FoxPro、FoxBase

非关系型的数据库：

非关系型数据库的实质：是传统关系型数据库的功能阉割版本，通过减少用不到或很少用的功能，来大幅度提高产品性能。可能有面向高性能并发读写的key-value数据库（Redis,Tokyo Cabinet,Flare）、面向海量数据访问的面向文档数据库（MongoDB以及CouchDB）、面向可扩展性的分布式数据库。

硬件

计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备5部分组成。

存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。

CPU功能：处理指令/执行操作/控制时间/处理数据

1.CPU的主频，即CPU内核工作的时钟频率。通常所说的某某CPU是多少兆赫的，而这个多少兆赫就是CPU的主频;

2.CPU的主频与CPU实际的运算能力是没有直接关系的;

3.CPU的运算速度还要看CPU的流水线、总线等等各方面的性能指标,只能说主频仅仅是CPU性能表现的一个方面，而不代表CPU的整体性能。

缓存大小也是CPU的重要指标之一，而且缓存的结构和大小对CPU速度的影响非常大，CPU内缓存的运行频率极高，一般是和处理器同频运作，工作效率远远大于系统内存和硬盘。实际工作时，CPU往往需要重复读取同样的数据块，而缓存容量的增大，可以大幅度提升CPU内部读取数据的命中率，而不用再到内存或者硬盘上寻找，以此提高系统性能。

L1　Cache(一级缓存）是CPU第一层高速缓存，分为数据缓存和指令缓存。

L2　Cache（二级缓存）是CPU的第二层高速缓存，分内部和外部两种芯片。内部的芯片二级缓存运行速度与主频相同，而外部的二级缓存则只有主频的一半。

L3　Cache(三级缓存）

寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和地址。在中央处理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序计数器(PC)。在中央处理器的算术及逻辑部件中，存器有累加器(ACC)。

指令寄存器（IR，Instruction Register），是临时放置从内存里面取得的程序指令的寄存器，用于存放当前从主存储器读出的正在执行的一条指令。

程序计数器是用于存放下一条指令所在单元的地址的地方。

运算器由算术逻辑单元（ALU）、累加器、状态寄存器、通用寄存器组等组成。算术逻辑运算单元（ALU）的基本功能为加、减、乘、除四则运算，与、或、非、异或等逻辑操作，以及移位、求补等操作。计算机运行时，运算器的操作和操作种类由控制器决定。运算器处理的数据来自存储器；处理后的结果数据通常送回存储器，或暂时寄存在运算器中。与Control Unit共同组成了CPU的核心部分。

算术逻辑单元(arithmetic and logic unit) 是能实现多组算术运算和逻辑运算的组合逻辑电路，简称ALU。 FPU：(Float Point Unit，浮点运算单元)FPU是专用于浮点运算的处理器，以前的FPU是一种单独芯片，在486之后，英特尔把FPU集成在CPU之内。

总线（Bus）是计算机各种功能部件之间传送信息的公共通信干线，它是由导线组成的传输线束，按照计算机所传输的信息种类，计算机的总线可以划分为数据总线、地址总线和控制总线，分别用来传输数据、数据地址和控制信号。

数据总线（Data Bus）：在CPU与RAM之间来回传送需要处理或是需要储存的数据。
地址总线（Address Bus）：用来指定在RAM（Random Access Memory）之中储存的数据的地址。
控制总线（Control Bus）：将微处理器控制单元（Control Unit）的信号，传送到周边设备，一般常见的为 USB Bus和1394 Bus。
扩展总线（Expansion Bus）：可连接扩展槽和电脑。
局部总线（Local Bus）：取代更高速数据传输的扩展总线。

主机是指计算机除去输入输出设备以外的主要机体部分。也是用于放置主板及其他主要部件的控制箱体（容器Mainframe）。通常包括 CPU、内存、硬盘、光驱、电源、以及其他输入输出控制器和接口。

IP地址

分A、B、C、D、E五类，目前大量使用的是A、B、C三类，D类为Internet体系结构委员会IAB专用，E类保留在今后使用。

分类

各个进制的字母代表

二进制B 八进制O 十进制D 十六进制H

题目

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

(http://tieba.baidu.com/p/2620672640)

两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有有唯一的一个元素y与它对应，就这种对应为从A到B的映射，记作f：A→B。
利用p∨¬ p和p∧¬ p可以构造出常数true和false
直观地，题目中含p,q,r的全体本质不同的表达式应当是{0,1}^3到{0,1}的全部映射的一个子集。
注意到我们利用形同((p∧1)∧(q∧0)(r∧1))∨((p∧1)∧(q∧1)(r∧1))∨...这样的式子可以构造出{0,1}^3到{0,1}的任意一个映射，所以只要统计这样的映射的数目就行了，是2^8
再解释一下：
将p与q与r的值用一个二进制数表示，那么三个数的不同取值有{000,001,010,011,100,101,110,111}这8种。对于任何一个表达式，将这8组值分别代入都可以得到8个结果(都为0/1)。
首先，可以确定，对于任意给定的8个结果(0/1)，都能够构造一个表达式，使得8组值代入这个表达式得到的结果分别为这8个结果。（如果不明白的话要相信...直觉?实际上类似((只将取值a1代入后为真的表达式)∨(只将取值a2代入后为真的表达式)∨...∨(只将取值ap代入后为真的表达式))这样的表达式能达到这个效果）
如果两个表达式等价，那么显然这8个结果分别相同。如果两个表达式不等价，那么只需要有至少一个数据代入它们计算得到的结果不同。要找出两两不等价的表达式最多有多少种（注意，不是两两不等价的表达式对数），也就是要找出这8个结果(0/1)组成的集合最多可能有多少种不同的。（也可以叫做集合{000,001,010,011,100,101,110,111}到集合{0,1}的映射个数）答案：2^8=256

2、书架上有21本书,编号从1 到 21 从中选4 本,其中每两本的编号都不相邻的选法一共有多少种?
看成把4本书插到17本书中,4本不能有相邻的,17本书有18个空,所以是C(18,4).结果是3060.

3、求（二叉）树的独立集个数：树形dp

注意：空集也是独立集

f[i]表示以i为根的子树选i的方案数,而g[i]则是不选i的方案数
f[i]=g[左子树]*g[右子树], g[i]=(f[左子树]+g[左子树])*(f[右子树]+g[右子树])

答案就是f[根]+g[根]=5536

（多叉树类似，就是把所有子树的g或者f+g乘起来）http://www.cnblogs.com/logic-yzf/p/7642963.html

其含义为：如果选i，那么i的子节点都不能选，每一种不选i的左儿子的独立集与不选右儿子的独立集合起来得到的也一定是一个独立集，这样产生独立集的个数就是g[左子]*g[右子]。不选i时同理。

手算方法：在每个节点的旁边标两个数字分别表示f和g（容易搞混）

4、同时查找2n个数中的最大值和最小值，最少比较次数为（）

A. 3(n-2)/2 B. 4n-2 C. 3n-2 D. 2n-2 E. n-2
答案：C，不是D

解释：https://zhidao.baidu.com/question/426499895347085212.html

前两个数比较,大的为最大值, 小的为最小值, 用掉一次比较
后面2*(n-1)个数, 每两个比较, 大的同最大值比较, 小的同最小值比较, 3*(n-1)次比较,
共3*(n - 1) + 1 = 3n - 2次比较

应该说...这题目本来就不是很对来着...桶排...

5.关于CPU下面哪些说法是正确的：
A)CPU全称为中央处理器（或中央处理单元）。
B)CPU能直接运行机器语言。
C)CPU最早是由Intel公司发明的。
D)同样主频下，32位的CPU比16位的CPU运行速度快一倍。

答案：AB，没有C

它的意思应该是指cpu理论的提出者？

英国人Charles Babbage设计了差分机和分析机，其设计理论非常超前，它设计的利用卡片输入程序和数据的概念被后人发明CPU时所采用。1834年:他设想制造一台通用分析机，在只读存储器(穿孔卡片)中存储程序和数据。1840年将操作位数提高到了40 位，并基本建立了控制中心(CPU)和存储程序的设想理论，而且程序可以根据条件进行跳转，能在几秒内做出一般的加法，几分钟内做出乘、除法。不过由于当时的硬件工业水平无法制造出芯片实件，因此只能停留在理论基础上。但他已经迈出了人类研究微芯片技术的第一步，可以说是打开了人类开启微芯片技术的第一把钥匙。

1971年。世界上第一块微处理器4004在Intel公司诞生了。它出现的意义是划时代的，比起现在的CPU，4004显得很可怜，它只有2300个晶体管，功能相当有限，而且速度还很慢。

6. 下列说法中，哪个（些）是错误的（）。
A）程序是指令的序列，它有三种结构：顺序、分支和循环。
B）数据总线决定了中央处理器CPU所能访问的最大内存空间的大小。
C）中央处理器CPU内部有寄存器组，用来储存数据。
D）不同厂家生产的CPU所能处理的指令集是相同的。
E）数据传输过程中可能会出错，奇偶校验法可以检测出数据中那一为在传输中出了差错。
答案：BDE，少了E
奇偶校验只能判断数据在传输中是否出错，不能精确到某一位，另外同时有奇数（偶数校验法时）/偶数（奇数校验法时）个bit出错了也校验不出来。

7.一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、（0,3,0）、(2,0,0)的平面的法线是（）。
A．过点（1，1，1）、（2，3，3）的直线 B．过点（1，1，1）、（3，2，1）的直线
C．过点（0，3，0）、（-3，1，1）的直线 D．过点（2，0，0）、（5，2，1）的直线
答案：D

法向量（法线方向的向量）与平面上的向量的乘积为0。

平面：向量是(-1,2,-1)

A、向量是(1,2,2)，乘积是(-1)*1+2*2+(-1)*2=1

B、向量是(2,1,0)，乘积是-1

C、向量是(-3,-2,1)，乘积是-2

D、向量是(3,2,1)，乘积是0

8.现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（）。
A．1 B．2 C．3 D．4

答案：BC

9.一棵二叉树一共有19个节点，其叶子节点可能有（）个。
A.1 B.9 C.10 D.11

答案：ABC（其实1-10都可以）

根据n0=n2+1公式计算即可

10、若某二进制数x的真值为–0.1010，则其反码表示是（）。
A.1.0101 B.10.0101 C.1.0110 D.10.0100
A

11、有一种互连设备工作于网络层，它既可以用于相同（或相似）网络间的互连，也可以用于异构网络间的互连,这种设备是（）。
A．集线器 B．交换机 C．路由器 D．网关
C

12、下面那个操作系统不属于多用户操作系统（）？
A.Windows ME B.Windows 10 C.Unix D.Linux
A

13、以下属于人工智能的是（）
A.机器学习 B.云计算 C.文字识别 D.3D打印
AC

该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

14、2017年8月23日，intel新推出的第八代酷睿处理器采用4核心8线程设计，比上代的2核心4线程的规格整整翻了一倍。下列说法正确的是（）
A.由于技术上由2核心4线程变成了4核心8线程，八代酷睿处理器比七代运行速度提升了一倍。
B.处理器在运行过程中同一时间可以同时运行4个核心。
C.4核处理器可以被多个程序交替占用。
D.在运行某些大型程序时，相同CPU规格多个单核CPU要比一个多核CPU工作效率更高。
答案：CD

A？达不到提升一倍

B？玄学，可能是答案错了

处理器实际性能是处理器在每个时钟周期内所能处理指令数的总量，因此增加一个内核，处理器每个时钟周期内可执行的单元数将增加一倍。而双核处理器中每个核心拥有独立的指令集、执行单元，可以同时执行多项任务，能让处理器资源真正实现并行处理模式。

C？肯定对的嘛

D？这个要看实际应用领域。https://www.zhihu.com/question/20998226

15. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是
3 2 5 6 4 1，则该二叉树的可能的中根遍历是（）
A. 3 2 1 4 6 5 B. 3 2 1 5 4 6
C. 2 3 1 5 4 6 D. 2 3 1 4 6 5

答案：BC

16. 使序列有序的最小交换次数（任意两数交换）：总个数-循环节个数

循环节：如果原数列为2,3,1,4，那么原数列中位置->新数列中位置的变化有1->2,2->3,3->1,4->4，1,2,3还有4分别就是一个循环节。

简单解释：将每个循环节归位需要循环节中元素个数-1，将所有的归位就是所有的元素个数-1*循环节个数

证明：

http://blog.csdn.net/wangxugangzy05/article/details/42454111

http://blog.csdn.net/sunmenggmail/article/details/8151793

17. 得到序列顺序的最小比较次数（特解）：

将 5 个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。
A. 6 B. 7 C. 8 D. 9 E. 10
答案：B

快照：

5 个数最快的排序, H.B.Demuth 于 1956 年在他的博士论文中提出了以下方法:

开始时,就像用合并对4个元素排序一样,首先比较a:b,接着 c:d,然后把每对的较大者拿来比较,这就产生了a<b<d和 c<d, 进行 3 次比较, 可以找到如下有序关系 (以下图中所有连线均表示左下元素比右上元素小)
b--d
/ /
a c e

这时,我们把第5个元素e,插入到{a,b,d}当中的适当位置,只需比较两次,首先同b进行比较,而后同a或d进行比较,就有如图所示的四种情况
    b-d   e-b-d    b-e-d    b-d-e
    / /        / /      /    /      / /
e-a c     a c     a   c     a c
对以上任意一种情况, 总可以通过两次比较将 c 调整入由 abde 构成的有序队中 (用二分的思想)
这样处理后总共需要比较 3 + 2 + 2 = 7 次, 能选出答案 7 并且解答过程无误的可以给双倍的分
资料来源: [Ph.D.thesis, Standford University(1956), 41~43]
同时在 D.E.Knuth 的著作 <计算机程序设计艺术> (The Art of Computer Progamming) 第三卷(排序和查找) 173 页至 174 页对这个问题有一个详细的解释.

http://blog.csdn.net/fisher_jiang/article/details/2442486

18.在编程时（使用任一种高级语言，不一定是 C++），如果需要从磁盘文件中输入一个很大的二维数组（例如 1000*1000 的 double 型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。

A. 没有区别 B. 有一些区别，但机器处理速度很快，可忽略不计
C. 按行读的方式要高一些 D. 按列读的方式要高一些 E. 取决于数组的存储方式。

答案：D（改20191018：好像抄错了，应该是E）

19.下列关于二分图的说法正确的是（）

A.最小点覆盖数等于最小边覆盖数
B.最小边覆盖数等于最大独立集
C.二分图最大独立集等于最大匹配数。
D.二分图的最大匹配数等于最小点覆盖数。

答案：BD

解释：http://blog.csdn.net/flynn_curry/article/details/52966283

20、有关固态硬盘的说法错误的是（）
A.固态硬盘速度较快，可以用来作为系统盘
B.固态硬盘与传统硬盘相比容量较大
C.固态硬盘与传统硬盘相比寿命更短
D.固态硬盘比传统硬盘更易损坏

答案：BD

21. 处理器 A 每秒处理的指令数是处理器 B 的 2 倍。某一特定程序 P 分别编译为处理器 A和处理器 B 的指令，编译结果处理器 A 的指令数是处理器 B 的 4 倍。已知程序 P 的算法时间复杂度为 O(n2)，如果处理器 A 执行程序 P 时能在一小时内完成的输入规模为 n，则处理器 B 执行程序 P 时能在一小时内完成的输入规模为（）。
A. 4 * n B. 2 * n C. n D. n / 2

22、常见的邮件传输服务器使用（）协议发送邮件。
A. HTTP B. SMTP C. TCP D. FTP E. POP3
答案：B

POP3允许用户从服务器上把邮件存储到本地主机（即自己的计算机）上,同时删除保存在邮件服务器上的邮件，而POP3服务器则是遵循POP3协议的接收邮件服务器，用来接收电子邮件的。

SMTP 协议属于 TCP/IP 协议簇，它帮助每台计算机在发送或中转信件时找到下一个目的地。SMTP 服务器就是遵循 SMTP 协议的发送邮件服务器。

IMAP全称是Internet Mail Access Protocol，即交互式邮件存取协议，它是跟POP3类似邮件访问标准协议之一。不同的是，开启了IMAP后，您在电子邮件客户端收取的邮件仍然保留在服务器上，同时在客户端上的操作都会反馈到服务器上，如：删除邮件，标记已读等，服务器上的邮件也会做相应的动作。

23、以下哪个（些）不是计算机的输出设备（）。
A. 鼠标 B. 显示器 C. 键盘 D. 扫描仪 E. 绘图仪
ACD，并没有E

绘图仪可将计算机的输出信息以图形的形式输出。

24.

 1 #include<iostream>
 2 using namespace std;
 3 long long g(long long k)
 4 {
 5     if (k <= 1) return k;
 6     return (2002 * g(k - 1) + 2003 * g(k - 2)) % 2005;
 7 }
 8 int main()
 9 {
10     long n;
11     cin>>n;
12     cout<<g(n)<<endl;
13     return 0;
14 }

费马小定理：
假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

25. 某计算机的 CPU 和内存之间的地址总线宽度是 32 位（bit），这台计算机最多可以使用（）的内存。
A. 2GB B. 4GB C. 8GB D. 16GB
答案：B

32位最大内存是2^32字节=4,294,967,296，也就是4G。

26.

答案：C

方法：主定理

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

答案：3

https://wenku.baidu.com/view/a3ede7dff01dc281e53af0c6.html?re=view

杂项

在C++中，setw(int n)用来控制输出间隔。
例如:cout<<'s'<<setw(8)<<'a'<<endl;
则在屏幕显示
s a
//s与a之间有7个空格，setw()只对其后面紧跟的输出产生作用，如上例中，表示'a'共占8个位置，不足的用空格填充。若输入的内容超过setw()设置的长度，则按实际长度输出。
setw()默认填充的内容为空格，可以setfill()配合使用设置其他字符填充。
如
cout<<setfill('*')<<setw(5)<<'a'<<endl;
则输出：
****a //4个*和字符a共占5个位置。