CSP-J/S初赛知识点总复习
人物
1.阿兰·麦席森·图灵：英国数学家，计算机之父，人工智能之父，计算机逻辑的奠基者，提出“图灵机”概念，1966 年美国计算机协会 ACM 设“图灵奖”，有“计算机界的诺贝尔奖”之称，目前获得该奖项的华人学者仅有 2000 年图灵奖得主姚期智教授。

2.王选：中国人，汉字激光照排系统的创始人，它被誉为“汉字印刷术的第二次发明”。中国计算机学会王选奖原名“中国计算机学会创新奖”，于 2005 年创立，2006 年，为了纪念王选院士为中国计算机事业做出的非凡贡献，中国计算机学会将中国计算机学会创新奖更名为中国计算机学会王选奖。

3.冯·诺依曼：美籍匈牙利数学家，现代电子计算机之父，世界上第一台现代意义的通用计算机 EDVAC（离散变量自动电子计算机，二进制）的发明者，提出①存储程序思想 ②计算机硬件设备由存储器、中央处理器、控制器、输入设备和输出设备五部分组成。

4.布莱士·帕斯卡：法国科学家，制造出机械计算机的第一人。

5.戈特弗里德·威廉·莱布尼茨：德国数学家，发明了“乘法器”，即能够连续重复地做加法减法。

6.查尔斯·巴贝奇：英国科学家，设计的“分析机”有齿轮式“存贮仓库”和“运算室”、“控制器”、输入输出部件，首次提出了类似于现代计算机五大部件的逻辑结构。

7.阿达·奥古斯塔：英国数学家，拜伦的女儿，第一个写软件的人，穿孔机程序创始人，建立了循环和子程序概念，为计算程序拟定“算法”。

8.克劳德·艾尔伍德·香农：美国数学家，引入信息熵，信息论创始人，创立了开关电路理论，把二进制与运用以脉冲方式处理信息的继电器开关相对应，从理论到技术改变了数字电路的设计方向。

9.艾达洛夫莱斯:世界上第一位程序员

10.戈登摩尔:英特尔公司创始人，提出了“摩尔定律”。

11.香农：美国数学家，创立了开关电路理论，把二进制与运用以脉冲方式处理信息的继电器开关相对应，从理论到技术改变了数字电路的设计方向。

12.eniac:世界上第一台通用电子计算机，1946年

CCF 相关
1.NOI：1984 年，*提出计算机要从娃娃抓起。
2.NOIP：1995 年。从 2005 年开始，NOIP 不再支持Basic；从 2022 年开始，不再支持 Pascal。
3.CCSP：2016 年，大学生竞赛。
4.CSP：2014 年。
5.CCF NOI系列活动考场纪律：
1.带入考场物品规定：参加者仅可以携带笔、饮用水和食品进入赛场，不得把手机、优盘等电 子设备、书包、书籍等带入赛场，如发现违规，不管是否使用，均按作弊处理。
2.考试前后：在考试正式开始前，参加者不得操作机器、使用鼠标键盘等设备。考试结束铃声 响后，参加者立即停止答题，不关闭计算机，按照监考员的要求离开考场。
3.考试期间：考试结束前30分钟，参加者不得擅自离开赛场。如需去洗手间、身体不适或其他 帮助，参加者须举手示意
4.作弊及处罚：凡在考试期间有抄袭、主动被抄袭、暗示、传递纸条、通信、夹带、替考等行 为者，均按作弊处理。如被抄袭者知情但不报告，也同样以作弊处理。作弊者被禁赛三年，并 全国通报。
5.监督和举报：如发现有违规行为，现场可向监考员举报，赛后可向CCF实名投诉 （noi@ccf.org.cn）。
6.突发情况：考试期间如遇到特殊情况或突发事件，务必听从监考员指挥。

计算机相关
1.电子技术发展史:
1.1946 至 1958：电子管；
2.1959 至 1964：晶体管；
3.1965 至 1970：集成电路；
4.1971 至今：超大规模集成电路。

2.计算机组成：存储器、中央处理器 CPU、控制器、输入设备、输出设备。

3.存储器：中央处理器能直接访问的存储器称为内部存储器，它包括快速缓冲存储器 cache 和主存储器（内存，包含只读存储器 ROM 和随机存储器 RAM（如内存条））。中央处理器不能直接访问的存储器称为外部存储器。（也称为辅助存储器，包含硬盘，软盘，光盘存储器）

4.地址位数 n 与可寻址的存储单元的个数 m 的关系：m=2^n。（单位是 B）

5.CPU：由运算器、控制器和寄存器组成。运算器进行各种算术运算和逻辑运算（包含算术逻辑运算单元 ALU 和浮点运算单元 FPU）；控制器是计算机的指挥系统。(把 CPU 比做大脑 寄存器就像你正在思考的问题,而 cache 就是你的临时记忆。)

6.数据读写速度：寄存器>cache>内存>硬盘>U 盘>光盘>其他辅助存储器。

7.断电后可以保存数据：硬盘，ROM；断电后不可以保存数据：显存（显卡内存），RAM，CPU。

8.ASCII 码：空格=0，回车=13，‘0’=48，’A’=56，’a’=97。

9.原码：某个二进制码。（符号位为 0 代表非负整数，反之为负整数）
补码：正数的补码是它本身，负数的补码是反码+1。
反码：正数的反码是它本身，负数的反码是除符号位所有位取反的结果。

10.计算机的主要作用:1.计算2.信息管理3.过程控制4.辅助工程5.人工智能6.网络应用

11.计算机辅助设计CAD,计算机辅助教学CAI

12.总线:计算机内部信息传递通信
1.数据总线:传递数据（32位cpu一次可以传递32个二进制位的数据地址）
2.地址总线:确定位置（宽度决定了能够访问的内存的大小）
3.控制总线:控制状态

13.计算机软件系统:
1.硬件:运算器，控制器，存储器，总线和输入输出设备
2.软件:系统软件（控制和协调计算机和外部设备，支持应用软件的开发和运行）和应用软件

14.系统软件分类:
1.操作系统（负责处理器管理，存储器管理，文件管理，设备管理，作业管理）:Windows(微软 microsoft)，安卓（谷歌），ios(苹果),dos (microsoft),unix,linux,macox(苹果)（安装软件前提）
2.语言处理程序:机器语言，汇编语言和高级语言（编译器）
3.数据库系统（建立使用和维护数据库）:mysql,oracle和sqlsever
4.辅助系统（帮助开发）

15.应用软件分类:
1.文字处理软件:word,wps
2.电子制表软件:excel
3.计算机辅助设计软件:cad（建筑）,c4d（影视）
4.图形软件:photoshop,美图秀秀
5.教育软件
6.电子游戏软件

16.计算机网络的主要作用:
1.数据通信
2.资源共享
3.集中管理
4.分布式管理
5.复合均衡

互联网
1.计算机病毒具有隐蔽性、潜伏性、传播性、激发性、破坏性、危害性。

2.计算机网络是指互联起来的自主计算机的集合。

3.网卡：可以将单个计算机接入到计算机网络中的网络接入通讯设备。

4.网络拓扑结构：总线拓扑、星型拓扑和环形拓扑。
总线拓扑结构是一种共享通路的物理结构。这种结构中总线具有信息的双向传输功能，普遍用于局域网的连接
星形拓扑结构是一种以中央节点为中心，把若干外围节点连接起来的辐射式互联结构。这种结构适用于局域网
环形拓扑结构是将网络节点连接成闭合结构。信号顺着一个方向从一台设备传到另一台设备，每一台设备都配有一个收发器，信息在每台设备上的延时时间是固定的。这种结构特别适用于实时控制的局域网系统。

5.网络可划分成资源子网和通信子网两部分。

6.局域网 LAN：几米到几十千米，覆盖一个房间、一幢大楼或一个校园，如以太网、令牌环网、令牌总线网等。
城域网 MAN：介于 LAN 与 WAN 之间，覆盖一群办公室或一个城市。
广域网 WAN：几十到几千千米，覆盖一个国家或一个洲。

7.IP 地址：
1.全球范围唯一。
2.IPv4 地址用 32 位二进数码表示，为了方便每 8 个一段用 . 隔开，每一段化成十进制数。 （值域为 [0,255]）
3.IPv4 地址分类： ABCDE 五类。目前大量使用的是 ABC 三类（A 类最高位 [1,126]，B 类最 高位 [128,191]，C 类最高位 [192,223]）而 D 类为 Internet 体系结构委员会 IAB 专用，E 类保留在今后使用。
4.由于 IPv4 地址不够分，将被 IPv6 协议取代，由 128 位二进制码表示。

8.协议：
1.ISO/OSI 协议：一种理想的概念模型，分七层，应用层、表示层、会话层、传输层、网络层 、数据链路层、物理层。功能层之间，上一层对下一层提出服务要求，下一层完成上一层提出 的要求。
2.TCP/IP 协议：由FTP、SMTP、TCP、UDP、IP等协议构成的协议簇，诞生于 1974 年 12 月。
3.应用层：OSI 的应用层、表示层、会话层。协议有 http、ftp、smtp 等。
4.传输层：OSI 的传输层。协议有 udp、tcp 等。
5.网际层：OSI 的网络层。协议有 ip、arp、路由等。
6.网络接口层（链路层）：OSI的数据链路层、物理层。

9.常见协议：1.WWW(World Wide Web)：万维网
2.URL（Uinform Resource Locator）：统一资源定位器
3.HTTP（Hypertext Transfer Protocol）：超文本传输协议
4.FTP (File Transfer Protocol)：文本传输协议
5.SMTP（Simple Mail Transfer Protocol ）简单邮件传输协议

10.无线通信技术：蓝牙，Wifi，GPRS（通用分组无线服务技术，GSM移动电话用户可用的一种移动数据业务，属于第二代移动通信中的数据传输技术）

11.域名&网址
网址：即IP地址，由于难于记忆故用到域名。
域名：就是一半常常说到得网址。
两者关系：域名和网址通过DNS（域名系统）互相转化。

12.因特网的发展历史
（1）Internet最早起源于60年代末美国的ARPANET(阿帕网).
（2）我国与1994年正式介入因特网。
（3）我国建立的4个公用网络：
1.中国公用计算机互联网（CHINANET）
2.中国金桥信息网（CHINAGBN）
3.中国教育和科研网（CERNET）
4.中国科学技术网（CSTNET）

13.通用顶级域是供一些特定组织使用的顶级域:无赞助：.biz .com .edu .gov .info .int .mil .name .net .org .pro .xyz赞助：.aero .cat .coop .jobs .museum .travel .mobi .asia .tel .xxx

14.常用文件扩展名:txt(文本).jpg,jpeg,png,bmp,jif.（图片）avi,mov,rmvp,mp4.(视频)

15.一些易错考点
（1）IPV6是IPV4的补充升级，不是IPV5.
（2）TCP/IP是互联网的基础协议组，包含TCP和IP等网络与传输层的通讯协议，
（3）互联网上每一台入网主机通常需要一个唯一的IP地址。且必须要有IP地址，不能仅仅注册一个域名而没有IP地址。
（4）HTML没有实现文本、图形、声音和视屏信息的统一编码，
（5）HTML不但包含网页内容信息的描述，同时也包含对网页格式信息的定义。
（6）网页上的超链接既能够指向外部资源，也可以指向本网站的超链接。
（7）为解决Web应用中不兼容的问题，万维网（W3C）制定了一些列的标准，设计HTML,XML,CSS等并建议开发者遵循。

语言
1.低级语言：不需要编译直接运行，运行速度快。（如汇编语言）

2.高级语言：需要编译运行，更容易移植。

1.面向对象语言：Simula67（纯面向对象语言），EIFFEL（纯面向对象语言），C++，Java，C#
2.面向过程语言：C，Fortran，Pascal。
3.解释型语言：Python，JavaScript，Perl，Shell。
4.编译型语言：C，C++，Pascal，Object Pascal。
图像
1.三基色：红绿蓝。（RGB）

2.饱和度：颜色的纯度，饱和度越大越鲜艳。纯光谱色是完全饱和的，加入白光会稀释饱和度。

3.位图：点阵图，由像素排列组合而成，容量较大，放大或缩小及旋转时容易失真。工具：Photoshop、画图。格式：BMP、TIFF、GIF、JPEG（压缩率最高）、PSD、PNG。

4.矢量图：以数学向量方式记录图像内容，文件小，不会失真，不宜制作色彩变化太多的图像。工具：Flash、CorelDRAW。 格式：WMF

5.位图的大小：a×b 像素，2^c 色（或 c 位色彩）的图像大小为 abc/8B。

P/NP/NPC
1.P 类问题：存在多项式时间解法。
2.NP 类问题：存在多项式时间验证方法。
3.NPC 类问题：所有 NP 类问题都可以规约到的一个 NP 问题。

进制转换
1.整数：
1.10 转 n：不断除以 n，倒序取余数。
2.n 转 10：直接算幂次。
2.小数：
1.10 转 n：不断乘 n，正序取个位数。
2.n 转 10：直接算负幂次。

算法
1.特征：有穷性，确切性，至少一个输出，可行性。

2.表示方法：自然语言法，程序流程图法（顺序结构，选择结构，循环结构），程序法。

3.排序：
1.希尔排序：令步长 gap 从 ⌊n2⌋ 循环到 1，每次除以 2。将模 gap 同余的所有数分为一 类，每一类单独进行插入排序。
2.计数排序：类似后缀数组。

数据结构
1.存储结构
数组：具有相同类型的若干变量按有序的形式组织起来，因此占用的空间是连续的。数组可分为数值数组、字符数组、指针数组、结构数组等。

bool a[x] 数组占字节数：1xy

char/unsigned (short) a[x] [y]数组占字节数：2xy

int/unsigned long/float a[x] [y]数组占字节数：4xy

(unsigned) long long/double a[x] [y]数组占字节数：8xy

链表：物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。相比于线性表顺序结构，链表比较方便插入和删除。（NOIP2015提高组）

单链表：每个节点只有一个存储直接后继结点地址的链域。

双向链表：既有存储直接后继结点地址的链域，称为右链域。又有存储直接前驱节点地址的链域，称为左链域。（NOIP2015提高组T13：插入结点；NOIP2010T9：删除结点）

2.数据结构
散列表：又称哈希表，通过关键码映射到表中一个位置来访问记录，以加快查找的速度。

栈：后进先出，栈顶允许进行插入和删除操作，栈底固定。（NOIP2015提高组）

队列：先进先出，队头进行删除操作，队尾进行插入操作。

3.树
树上每个元素称为节点，有一个特定的节点称为根节点。树是递归定义的，因此树的操作和应用大都是采用递归思想来解决的。

节点的度：一个节点的子树个数。度为0的节点称为叶节点（or 树叶），度不为0的节点称为分支节点，根节点以外的分支节点称为内部节点。树中各节点的度的最大值称为这棵树的（宽）度。

深度：节点的层次等于其父节点的层次数加1，树中各点的层次的最大值称为这棵树的深度。

森林：m（m≥0）棵互不相交的树的集合。

性质：①树上任意两个节点之间有且只有一条路径

②一个拥有N个节点的树，必然存在N-1条边（NOIP2015、2017提高组）

③树中任意一条边的删除都会导致不连通

前序遍历：根左右 中序遍历：左根右 后序遍历：左右根 （NOIP2015提高组）

二叉树的性质：①在二叉树的第i层上至多有 2^(i-1) 个节点（i≥1）。

（NOIP2018）②深度为k的二叉树至多有2^k-1 个节点（k≥1）。特别地，一棵深度为k且有

2^k-1个节点的二叉树称为满二叉树。（根的深度为1）

③若叶节点数为n0 度为2的节点数为 n2 ，则一定满足n0=n2+1 。

完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。

完全二叉树的性质：①叶节点只可能出现在最下面两层。

②对任一节点，若其右子树深度为m，则其左子树的深度必为m或m+1.

③具有n个节点的完全二叉树的深度为log2n+1 （根的深度为1）。

（NOIP2015提高组，深度=高度）

④一棵n个节点的完全二叉树，对于任一编号为i节点，有：

i.如果i=1，则节点i为根，无父节点；否则，其父节点的编号为i/2

ii.如果2i>n，则节点i为叶节点，否则左孩子编号为2i。

iii.如果2i+1>n，则节点i无右孩子，否则右孩子编号为2i+1。

堆：完全二叉树，节点的值大于它两个儿子的值时称为大根堆，节点的值小于它两个儿子的值时称为小根堆。堆可以在log n的时间内完成插入节点的功能。

4.图
1.有向图：若有n个顶点，则最多有n(n-1)条弧，此时称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。任意两点之间有双向路径的有向图称为强连通图，否则，将其中的极大连通子图称为强连通分量。

2.无向图：若有n个顶点，则最多有n(n-1)/2条边，此时称作无向完全图。与顶点v相关的边的条数称作顶点v的度。任意两点之间都连通的无向图称为连通图，否则，将其中的极大连通图称为连通分量。

3.定理：①图G中所有顶点的度数之和等于边数的两倍。

②任意一个图一定有偶数个奇点。

4.路径长度：路径上边或弧的数目。若路径上顶点没有重复出现，则称这条路径为简单路径。

5.生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。

6.哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。运用了贪心思想。

其他
1.常见厂商:
1.微软公司:windows,dos,office系列:word,excel,powerpoint.
2.阿杜比公司（Adobe):photoshop,acoboatt reader
3.金山公司:wps