CSP初赛知识点复习 .pdfVIP

精品word完整版-行业资料分享

CSP-J/S第一轮（初赛）知识点精讲

NOIP（全国青少年信息学奥林匹克竞赛）于2019年取消。取而代之的是由CCF推出的非专业级软件能

力认证，也就是现在的CSP−J/S。CSP非专业级认证的第一轮（也就是NOIP初赛）常常使某些大神对

基础知识不太了解无缘复赛...所以今天学习下初赛知识点。

信息学史及基本知识

一、信息学及计算机史

•计算机的顶级奖项：图灵奖、冯诺依曼奖·

图灵奖：由ACM（美国计算机协会）设立于1966年。是计算机界的诺贝尔奖“”。

冯诺依曼奖：由·IEEE设立。

对信息科学做出突出贡献的大神：图灵（所以才有个奖），冯·诺伊曼

中国获图灵奖的大神：姚期智（清华就有姚班，就是以他的名字命名的）

世界第一台电子计算机：埃尼阿克（ENIACENIAC），于1946年2月14日在美国宾夕法尼亚大

学诞生。又被叫做电子管计算机。

二、关于编程

•编程语言：

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

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

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

更容易移植。

•常见低级语言：

汇编

•面向对象的高级语言：

C++，Java，EIFFEL，Simula67等。

•面向过程的高级语言：

C，Fortran语言。

•递归编程：

精品word完整版-行业资料分享

递归是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多

的计算机科学问题。简单来讲，就是“自身调用自身”（在函数中）。

•P类/NP类/NPC类问题：

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

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

可以将其理解为在多项式时间内猜出一个解的问题。

3、NPC类问题：定义如下：如果一个问题是NP问题，而且所有的NP问题都可以约化到它。那么它

就是NPC类问题。再来介绍一下关于约化的定义：如果一个问题A可以约化为问题B，含义就是这个

问题A可以用问题B的解法来解决。

三、关于计算机

先上张大图：

•

重要设备：

硬件组成：

控制器(Control):是整个计算机的中枢神经，其功能是对程序规定的控制信息进行解释，根据其要求

进行控制，调度程序、数据、地址，协调计算机各部分工作及内存与外设的访问等。

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

精品word完整版-行业资料分享

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

信息。

输入设备(Inputsystem):输入设备是计算机的重要组成部分，输入设备与输出设备合称为外部设备，

简称外设，输入设备的作用是将程序、原始数据、文字、字符、控制命令或现场采集的数据等信息

输入到计算机。常见的输入设备有键盘、鼠标器、光电输入机、磁带机、磁盘机、光盘机等。

输出设备(Outputsystem):输出设备与输入设备同样是计算机的重要组成部分，它把外算机的中间结

果或最后结果、机内的各种数据符号及文字或各种控制信号等信息输出出来。微机常用的输出设备

有显示终端CRT、打印机、激光印字机、绘图仪及磁带、光盘机等。

•

CPU及存储：

•

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

运算器=算术逻辑运算单元（ALU）及浮点运算单元（FPU）

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

BIOS是英文BasicInputOutputSystem的缩略语，直译过来后中文名称就是基本输入输出系统。其

实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计