经验：CSP-J/S初赛核心知识点整理

下周六就是CSP-J/S第一轮认证了，今天小编盘点了一下往年NOIP初赛知识点，给各位学员参考巩固一下知识点...

信息学史及基本知识

01

一、信息学及计算机史

• 计算机的顶级奖项：图灵奖

• 对信息科学做出突出贡献的大神：图灵，冯 · 诺伊曼

• 中国获图灵奖的大神：姚期智

• 世界第一台电子计算机：埃尼阿克（𝐸𝑁𝐼𝐴𝐶），于1946年2月14日在美国宾夕法尼亚大学诞生。又被叫做电子管计算机。

02

二、关于编程

01

编程语言：

分两类：面向对象和面向过程。

02

高级语言和低级语言的区别：

高级语言需要编译运行，常数较大，运行速度慢。而低级语言常数极小，运行速度快。此外，高级语言更容易移植。

03

常见低级语言：

汇编

04

面向对象的高级语言：

C++，Java，EIFFEL，Simula 67等。

05

面向过程的高级语言：

C，Fortran语言。

06

递归编程：

递归是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题。简单来讲，就是“自身调用自身”（在函数中）。

07

P类/NP类/NPC类问题：

1、P类问题：如果一个问题能找到一个在多项式时间内解决它的算法，那么这个问题就是P问题。

2、NP类问题：注意：NP问题不是非P类问题，而是在多项式时间内验证一个解的问题。或者，我们可以将其理解为在多项式时间内猜出一个解的问题。

3、NPC类问题：定义如下：如果一个问题是NP问题，而且所有的NP问题都可以约化到它。那么它就是NPC类问题。再来介绍一下关于约化的定义：如果一个问题A可以约化为问题B，含义就是这个问题A可以用问题B的解法来解决。

03

三、关于计算机

先上张大图：

01

重要设备：

硬件：

• 控制器：是整个计算机的中枢神经，其功能是对程序规定的控制信息进行解释，根据其要求进行控制，调度程序、数据、地址，协调计算机各部分工作及内存与外设的访问等。

• 运算器：运算器的功能是对数据进行各种算术运算和逻辑运算，即对数据进行加工处理。

• 存储器：存储器的功能是存储程序、数据和各种信号、命令等信息，并在需要时提供这些信息。

• 输入设备：顾名思义，输入设备的作用是将控制命令或现场采集的数据等信息输入到计算机。常见的输入设备有键盘、鼠标器、光电输入机、磁带机、磁盘机、光盘机等。

• 输出设备：输出设备顾名思义，就是输出计算结果及计算机内容的设备。常用的输出设备有显示终端CRT、打印机、激光印字机、绘图仪及磁带、光盘机等。输出设备和输入设备简称外设。

02

CPU及存储：

CPU（中央处理器）=运算器+控制器+寄存器

存储器=内存储器+外存储器

BIOS是英文'Basic Input Output System'的缩略语，直译过来后中文名称就是'基本输入输出系统'。其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。

随机存储器RAM的“随机”指“随时访问”

所以，我们记下来以下知识点：

断电后可以保存数据：硬盘，ROM

断电后不可以保存数据：显存（显卡内存），RAM，CPU

03

计算机各存储单位及进位关系：

计算机的存储单位有以下几种：

𝑇𝐵/𝐺𝐵/𝑀𝐵/𝐾𝐵/𝐵

他们之间的进位关系为1024（这应该是常识）

特殊地，1𝐵=8(𝑏𝑖𝑡)，这里的𝑏𝑖𝑡是二进制下的一位内存。

进制及进制转化

01

十进制转任意进制

将十进制转换成𝑁进制，只需把十进制数每次除𝑁求余数，然后把余数逆序写出来。

看不懂就看图：

这是二进制的图，其他进制就类比推一下就可以了。

02

任意进制转十进制

简单说就是：按位转，第𝑖位的数字乘以要转换的进制的𝑛−1次幂即可。

还是上图：

03

任意进制互相转化

这里考虑用十进制做中转，先把𝐴进制转十进制，再把十进制转𝐵进制。

04

关于小数的进制转换

十进制转任意进制的小数不进行除法运算，而进行乘法运算后取整，取整后从前向后排列。

任意进制转十进制的小数只需要乘上负指数，最后算出来即可。

05

各进制的字母表达

𝐻(𝐻𝑒𝑥𝑎𝑑𝑒𝑐𝑖𝑚𝑎𝑙)——16进制

𝐷(𝐷𝑒𝑐𝑖𝑚𝑎𝑙)——10进制

𝑂(𝑂𝑐𝑡𝑜𝑛𝑎𝑟𝑦)——8进制

𝐵(𝐵𝑖𝑛𝑎𝑟𝑦)——2进制

05

二进制的相关知识

二进制是计算机进行计算所使用的工具，自然也是非常常考的要点。二进制的相关知识有许多，甚至算法中的位运算也是二进制的相关内容，但为了过第一轮初赛，我们只介绍一些理论知识。关于位运算的相关知识请有兴趣的同学自己学习。

01

原码

顾名思义，原码就是十进制数直接转换成二进制之后直接形成的二进制编码。

02

补码

正数的补码是本身，负数的补码是其反码加一。

03

反码

顾名思义：正数的反码是本身，负数的反码是其除符号位之外的所有位按位取反的结果。

附：ASCII码

ASCII码的正规名称是：美国信息交换标准代码，是基于拉丁字母的一套电脑编码系统。是最通用的信息交换标准。一共定义了128个字符。

这里不赋ASCII码的转换表。只给出几种比较常用的转换：

字符0→48

大写字母A→65

小写字母a→97

空格→32

换行→13

逻辑运算

01

逻辑运算

逻辑运算一共有三种，每种都有两种写法：

逻辑非：！或 ┐

逻辑与：&& 或 ∧

逻辑或：|| 或 ∨

逻辑运算的优先级

非>与>或

位运算+逻辑运算的优先级

逻辑非（！，┐）=按位反（~）>位移运算（<<,>>）>不等号（>=,<=）>等号（==,!=）>按位与（&）>按位异或（^）>按位或（|）>逻辑与（&&，∧）>逻辑或（||，∨）

逻辑表达式

由逻辑运算复合而成，只有两种结果：𝑡𝑟𝑢𝑒和𝑓𝑎𝑙𝑠𝑒，C/C++中，返回的值以0表示假，以1表示真。

条件表达式

条件表达式的基本形式如下：

<表达式1>？<表达式2>：<表达式3>

其表达意义是：如果表达式1成立，则执行表达式2，否则执行表达式3。其实也等价于𝑖𝑓−𝑒𝑙𝑠𝑒条件语句。例如下：

#define Min(a,b) a<b?a:b

注意：如果条件表达式有多个进行复合，那么在执行的时候需要从由往左依次判断最后得出一个结果。即：右结合性。

比如：

<表达式1>？<表达式2>：<表达式3>？<表达式4>：<表达式5>

那么，在执行的时候是从3开始判断是否为真，然后执行某一个表达式，依次向上回溯。

图论理论知识

01

基本概念

• 完全图：任意两点都有边相连，我们很容易推出来，一张完全图的边数为（𝑛为节点个数）

    𝑛×(𝑛−1）  

  2

• 连通图：顾名思义，连通图就是连通的图，即任意两点都能直接或间接到达，这就区别于完全图必须直接用边到达的定义。

• 树：直观来讲，就是一张长得像树的图。定义是任意两点之间的简单路径有且只有一条。树是一棵连通且无环的图。它的边数是𝑛−1。

02

二叉树的遍历

• 先序遍历：遍历方式如下：根—左儿子—右儿子

• 中序遍历：遍历方式如下：左儿子—根—右儿子

• 后序遍历：遍历方式如下：左儿子—右儿子—根

我们用一张图来理解一下这几种遍历方式。

这张图的先序遍历：1245367

中序遍历：4251637

后序遍历：4526731

• 一个推论：

先序遍历+中序遍历=一棵确定的二叉树

后序遍历+中序遍历=一棵确定的二叉树

先序遍历+后序遍历=啥也不是

03

特殊二叉树及其性质

• 完全二叉树：只有最后一层不是满的，且最后一层的所有节点均集中在左侧。

图例如下：

• 满二叉树：节点个数已满。
  

图例如下：

• 特殊二叉树的性质：
  

1、对于一棵满二叉树来讲，它的叶子节点为𝑛，则节点总数为2×𝑛−1。此结论可逆。

2、对于一棵满二叉树来讲，它的层数（深度）为𝑘，则它的节点总数为2^𝑘−1。此结论可逆。

简单数据结构基本理论

01

栈

想象一个桶，你从上面往里扔砖，然后你想把某一块砖拿出来，你需要先拿出来你后扔进去的砖。这就是栈。栈的基本原则是：后进先出。

图示：

02

队列

想象你在排队买票，这个队伍中的人都非常有素质，都自觉排队而且不会提前离开队伍。这样就只能从队首买完票再离开，从队尾进入队伍。队列的基本原则是：先进先出。

图示：

03

链表

链表分两种：单向链表和双向链表。

时空复杂度的计算

• 时间复杂度：渐进时间复杂度用符号O表示。一个程序的语句执行次数可以用一个代数式表示，那么我们取这个代数式的最高次项且忽略此项系数作为时间复杂度。如果一个程序的语句执行次数为 2𝑛³+3𝑛²+𝑛+7，那么这个程序的渐进时间复杂度为𝑂(𝑛³)。

• 计算非递归程序的时间复杂度：简单粗暴，数循环。

• 常数：常数即为我们忽略掉的𝑂中最高次项的系数与低次项所带来的时间消耗。

• 空间复杂度：类比时间复杂度。看开空间开了多大。

• 计算空间占用量：根据我们以上说过的计算机存储单位的知识：一个𝑖𝑛𝑡占用的内存是4𝐵，所以我们把开的𝑖𝑛𝑡乘上4，再除以1024就是𝐾𝐵，同理，再除1024就是𝑀𝐵。

公式：𝑛为元素个数，𝑀为最终答案（以𝑀𝐵为单位）

𝑀=4𝑛/1024×1024

PS:一般来讲，比赛中所给的256𝑀𝐵内存可以开6×10⁷个𝑖𝑛𝑡类型的变量。另外，大数组必须开全局变量。如果扔在主函数里极容易爆栈。

数学、逻辑学及运筹学知识

• 排列组合：排列组合是每年必考知识点。但是这是一个比较大的课题。