史上最全的CSP-JS第⼀轮知识点
CSP-J/S 第⼀轮知识点选讲
\(NOIP\)（全国青少年信息学奥林匹克竞赛）于2019年取消。取⽽代之的是由\(CCF\)推出的⾮专业级软件能⼒认证，也就是现在的\ (CSP-J/S\)。作为⼀名于2019年1⽉⼊\(OI\)的蒟蒻\(OIer\)，没能参加\(NOIP\)是我⼀⽣的遗憾。但在遗憾之余，我不得不备战\ (CSP\)的认证。⽽\(CSP\)⾮专业级认证的第⼀轮（也就是\(NOIP\)初赛）常常使某些⼤神\(OIer\)（就是对基础知识不太了解）⽆缘复赛...所以今天来盘⼀下初赛知识点，顺带着⾃⼰也学习⼀下......
信息学史及基本知识
⼀、信息学及计算机史
计算机的顶级奖项：图灵奖
对信息科学做出突出贡献的⼤神：图灵（所以才有个奖），冯 · 诺伊曼
中国获图灵奖的⼤神：姚期智（清华就有姚班，就是以他的名字命名的）
世界第⼀台电⼦计算机：埃尼阿克（\(ENIAC\)），于1946年2⽉14⽇（够虐狗的）在美国宾⼣法尼亚⼤学诞⽣。⼜被叫做电⼦管计算机。
⼆、关于编程
编程语⾔：分两类：⾯向对象和⾯向过程。
⾼级语⾔和低级语⾔的区别：⾼级语⾔需要编译运⾏，常数较⼤，运⾏速度慢。⽽低级语⾔常数极⼩，运⾏速度快。此外，⾼级语⾔更容易移植。
常见低级语⾔：汇编
⾯向对象的⾼级语⾔：C++，Java，EIFFEL，Simula 67等。
⾯向过程的⾼级语⾔：C，Fortran语⾔。
三、关于计算机
先上张⼤图：
重要设备：
硬件组成：
1. 控制器(Control)：是整个计算机的中枢神经，其功能是对程序规定的控制信息进⾏解释，根据其要求进⾏控制，调度程序、数
据、地址，协调计算机各部分⼯作及内存与外设的访问等。
2. 运算器(Datapath)：运算器的功能是对数据进⾏各种算术运算和逻辑运算，即对数据进⾏加⼯处理。
3. 存储器(Memory)：存储器的功能是存储程序、数据和各种信号、命令等信息，并在需要时提供这些信息。
4. 输⼊设备(Input system)：输⼊设备是计算机的重要组成部分，输⼊设备与输出设备合称为外部设备，简称外设，输⼊设备的
作⽤是将程序、原始数据、⽂字、字符、控制命令或现场采集的数据等信息输⼊到计算机。常见的输⼊设备有键盘、⿏标
器、光电输⼊机、磁带机、磁盘机、光盘机等。
5. 输出设备(Output system)：输出设备与输⼊设备同样是计算机的重要组成部分，它把外算机的中间结果或最后结果、机内的
各种数据符号及⽂字或各种控制信号等信息输出出来。微机常⽤的输出设备有显⽰终端CRT、打印机、激光印字机、绘图仪
及磁带、光盘机等。
CPU及存储：
CPU（中央处理器）=运算器+控制器+寄存器
存储器=内存储器+外存储器
BIOS是英⽂"Basic Input Output System"的缩略语，直译过来后中⽂名称就是"基本输⼊输出系统"。其实，它是⼀组固化到计算机内主板上⼀个ROM芯⽚上的程序，它保存着计算机最重要的基本输⼊输出的程序、系统设置信息、开机后⾃检程序和系统⾃启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。
随机存储器RAM的“随机”指“随时访问”
所以，我们记下来以下知识点：
断电后可以保存数据：硬盘，ROM
断电后不可以保存数据：显存（显卡内存），RAM，CPU
计算机各存储单位及进位关系：
计算机的存储单位有以下⼏种：
\(TB/GB/MB/KB/B\)
他们之间的进位关系为1024（这应该是常识，没打过⽐赛还没玩过⼿机么？）
特殊地，\(1B=8(bit)\)，这⾥的\(bit\)是⼆进制下的⼀位内存。
进制及进制转化
⼗进制转任意进制
将⼗进制转换成\(N\)进制，只需把⼗进制数每次除\(N\)求余数，然后把余数逆序写出来。
看不懂就看图：
这是⼆进制的图，其他进制就类⽐推⼀下就可以了。如果这个看不懂的话就不要参加初赛了，50块钱买点啥不好...
任意进制转⼗进制
简单说就是：按位转，第\(i\)位的数字乘以要转换的进制的\(n-1\)次幂即可。
还是上图：
任意进制互相转化
这⾥考虑⽤⼗进制做中转，先把\(A\)进制转⼗进制，再把⼗进制转\(B\)进制。
关于⼩数的进制转换
⼗进制转任意进制的⼩数不进⾏除法运算，⽽进⾏乘法运算后取整，取整后从前向后排列。
任意进制转⼗进制的⼩数只需要乘上负指数，最后算出来即可。
各进制的字母表达
\(H(Hexadecimal)\)——16进制
\(D(Decimal)\)——10进制
\(O(Octonary)\)——8进制
\(B(Binary)\)——2进制
⼆进制的相关知识
⼆进制是计算机进⾏计算所使⽤的⼯具，⾃然也是⾮常常考的要点。⼆进制的相关知识有许多，甚⾄算法中的位运算也是⼆进制的相关内容，但为了过第⼀轮初赛，我们只介绍⼀些理论知识。关于位运算的相关知识请有兴趣的同学⾃⼰学习。
1、原码
顾名思义，原码就是⼗进制数直接转换成⼆进制之后直接形成的⼆进制编码。
2、补码
正数的补码是本⾝，负数的补码是其反码加⼀。
3、反码
顾名思义：正数的反码是本⾝，负数的反码是其除符号位之外的所有位按位取反的结果。
逻辑运算
逻辑运算
逻辑运算⼀共有三种，每种都有两种写法：
逻辑⾮：！或 ┐
逻辑与：&& 或 ∧
逻辑或：|| 或 ∨
逻辑运算的优先级
⾮\(>\)与\(>\)或
位运算+逻辑运算的优先级
逻辑⾮（！，┐）=按位反（~）>位移运算（<<,>>）>不等号（>=,<=）>等号（==,!=）>按位与（&）>按位异或（^）>按位或（|）>逻辑与（&&，∧）>逻辑或（||，∨）
图论理论知识
基本概念
完全图：任意两点都有边相连，我们很容易推出来，⼀张完全图的边数为（\(n\)为节点个数）
\[ \frac{n\times (n-1)}{2} \]
连通图：顾名思义，连通图就是连通的图，即任意两点都能直接或间接到达，这就区别于完全图必须直接⽤边到达的定义。
进制数转换公式
树：直观来讲，就是⼀张长得像树的图。定义是任意两点之间的简单路径有且只有⼀条。树是⼀棵连通且⽆环的图。它的边数是\(n-1\)。
⼆叉树的遍历
先序遍历：遍历⽅式如下：根—左⼉⼦—右⼉⼦
中序遍历：遍历⽅式如下：左⼉⼦—根—右⼉⼦
后序遍历：遍历⽅式如下：左⼉⼦—右⼉⼦—根
我们⽤⼀张图来理解⼀下这⼏种遍历⽅式。
这张图的先序遍历：1245367
中序遍历：4251637
后序遍历：4526731
⼀个推论：
先序遍历+中序遍历=⼀棵确定的⼆叉树
后序遍历+中序遍历=⼀棵确定的⼆叉树
先序遍历+后序遍历=啥也不是
特殊⼆叉树及其性质
完全⼆叉树：只有最后⼀层不是满的，且最后⼀层的所有节点均集中在左侧。
图例如下：
满⼆叉树：节点个数已满。
图例如下：
特殊⼆叉树的性质：
1、对于⼀棵满⼆叉树来讲，它的叶⼦节点为\(n\)，则节点总数为\(2\times n-1\)。此结论可逆。
2、对于⼀棵满⼆叉树来讲，它的层数（深度）为\(k\)，则它的节点总数为\(2^k-1\)。此结论可逆。
简单数据结构基本理论
1、栈
想象⼀个桶，你从上⾯往⾥扔砖，然后你想把某⼀块砖拿出来，你需要先拿出来你后扔进去的砖。这就是栈。栈的基本原则是：后进先出来⼀发图⽰？

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。