CSP-J/S 初赛

一、人物

• 艾伦（阿兰）·麦席森·图灵：英国数学家，计算机之父，人工智能之父，计算机逻辑的奠基者，提出“图灵机”概念，1966年由美国计算机协会ACM设“图灵奖”，是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称，每年评选出一名计算机科学家，目前获得该奖项的华人学者仅有2000年图灵奖得主姚期智教授。现代计算机的基础是抽象的图灵机。（NOIP2017，2018提高组）
• 王选：汉字激光照排系统的创始人，为新闻、出版全过程的计算机化奠定了基础，被誉为“汉字印刷术的第二次发明”。中国计算机学会王选奖原名“中国计算机学会创新奖”，于2005年创立，每年评选一次，属于社会力量设立的科学技术奖。2006年，为了纪念王选院士为中国计算机事业做出的非凡贡献，学中国计算机学会将中国计算机学会创新奖更名为中国计算机学会王选奖。（NOIP2017提高组）
• 冯·诺依曼：美籍匈牙利数学家，现代电子计算机之父，世界上第一台现代意义的通用计算机EDVAC（离散变量自动电子计算机，二进制）的发明者，提出①存储程序思想 ②计算机硬件设备由存储器、中央处理器、控制器、输入设备和输出设备五部分组成
• 世界上第一台电子计算机：ENIAC（电子数值积分计算机，十进制），由宾夕法尼亚大学的莫奇莱教授和埃克特博士等为计算弹道轨迹而研制。
• 布莱士·帕斯卡：法国科学家，制造出机械计算机的第一人。
• 莱布尼茨：德国数学家，发明了“乘法器”，即能够连续重复地做加法减法。
• 巴贝奇：英国剑桥大学科学家，设计的“分析机”有齿轮式“存贮仓库”和“运算室”、“控制器”、输入输出部件，首次提出了类似于现代计算机五大部件的逻辑结构。
• 阿达·奥古斯塔：英国数学家，拜伦的女儿，第一个写软件的人，穿孔机程序创始人，建立了循环和子程序概念，为计算程序拟定“算法”。
• 香农：美国数学家，创立了开关电路理论，把二进制与运用以脉冲方式处理信息的继电器开关相对应，从理论到技术改变了数字电路的设计方向。

二、计算机硬件

存储器、中央处理器、控制器、输入设备、输出设备

从理论上讲，CPU和主存组成主机。

• 中央处理器CPU：由运算器、控制器和一些寄存器组成；运算器进行各种算术运算和逻辑运算；控制器是计算机的指挥系统，控制机器各个部件协调工作。CPU的主要性能指标是主频和字长，主要任务是执行数据运算和程序控制。（NOIP2015提高组）
• 存储器：中央处理器能直接访问的存储器称为内部存储器，它包括快速缓冲存储器(位于CPU和内存之间，现在一般集成在CPU上)和主存储器，中央处理器不能直接访问的存储器称为外部存储器，外部存储器中的信息必须调入内存后才能为中央处理器处理。地址位数N与可寻址的存储单元的个数M的关系： ，单位：B。（NOIP2016提高组）
• 主存储器（内存）：主存储器按读写功能，可分只读存储器（ROM，断电数据还在，如BIOS（基本输入输出系统））和随机存储器（RAM，断电数据没有，如内存条）两种。
• 外存储器：也称为辅助存储器，一般容量较大，速度比主存较慢，包括软盘、硬盘、光盘、U盘等一系列移动存储设备。
  • 硬盘（Hard disk）：目前的硬盘大多采用了温彻斯特技术，所以又称为“温盘”；温氏技术的特点是：将盘片、读写磁头及驱动装置精密地组装在一个密封盒里；采用接触式起停，非接触式读写的方式（磁盘不工作时，磁头停在磁盘表面的起停区，一旦加电后，磁头随着盘片旋转的气流“飞”起来，悬浮在磁盘表面，进行读写）。
  • 软盘（Floppy Disk）：目前常见的是3.5英寸/1.44 MB的软盘。
  • 光盘存储器：CD-ROM（只读型光盘），容量大约是650 MB；EOD（可擦写光盘）；DVD容量在4.7GB~17GB；EVD，DVD的升级版；VCD，CD的一种，即Video CD。

数据读写速度：寄存器 > 高速缓存>内存 >硬盘＞U盘＞光盘＞其他辅助存储器

键盘（输入设备）：（NOIP2016提高组）

标准Windows-PC键盘

标准Apple-Mac键盘

快捷键

在使用操作系统和软件的过程中，时常会用到复制、粘贴、剪切等功能。这时候如果使用快捷键来操作，往往能达到事半功倍的效果。以下是一些常用的功能及其在 Windows 键盘和 Mac 键盘上对应的快捷键方法。

鼠标（输入设备）

三、NOIP / CSP等的历史、大事件、参赛要求（每年都考）

• NOI：中国计算机学会于1984年（当年，邓小平提出计算机要从娃娃抓起）创办全国青少年计算机程序设计竞赛，即全国青少年信息学奥林匹克竞赛，是国内包括港澳在内的省级代表队最高水平的大赛。

• NOIP：中国计算机学会于1995年创办全国青少年信息学奥林匹克联赛。NOIP在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷，初、高中或其他中等专业学校的学生可报名参加。联赛分初赛和复赛，初赛考察通用和实用的计算机科学知识，以笔试为主。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。

• 从2005年开始，NOIP不再支持Basic；从2022年开始，不再支持Pascal。

• 选手进入考场时，只许携带笔、橡皮等非电子文具入场。禁止携带任何电子产品或机器设备入场，无存储功能的手表除外；手机（关机）、U盘或移动硬盘、键盘、鼠标、闹钟、计算器、书籍、草稿纸及背包等物品必须存放在考场外。如有违规带入的，一经发现，NOI各省特派员可直接取消违规选手的参赛资格。

• CCSP：大学生计算机系统与程序设计竞赛，由中国计算机学会(CCF)于2016年发起的一个面向大学生的竞赛，每年举办一次，考察的是算法、编程以及计算机系统设计能力，旨在进一步提高计算机教育质量，使学生通过竞赛进一步学习和掌握计算机系统知识，同时对高校计算机教育产生引领作用。

• CSP：中国计算机学会于2014年推出CCF计算机软件能力认证，该项认证重点考察软件开发者实际编程能力，由中国计算机学会统一命题、统一评测，委托各地设立的考试机构进行认证考试。该项认证每年大约3、9、12月各举办一次。认证者不限年龄，不限学历，不限报考次数，不限国籍 ，在报名官网注册账户后均可报名参加认证。语言：C/C++(Dev-CPP 5.4.0 (Min GW 4.7.2))，Java(Eclipse (Java SDK 1.7.0_15))，Python(3.6.5) 浏览器：Chrome

  CSP认证考试可以带纸质资料进入考场，不过只能是常用语言的程序设计基础书、数据结构的相关书籍。不允许U盘、手机等电子设备进入考场。

  CSP-S/J：认证开始15分钟后，认证者不能再进入认证点。如有认证者提前离开认证点，除身体特别原因外，须在认证进行2小时后方可准予离开。在第一轮认证期间，任何人不得将试卷携带出考场。认证者进入考场时，监考检查认证者携带物品。认证者只许携带笔、橡皮等非电子文具入场。禁止携带任何电子产品或机器设备入场，无存储功能的手表除外；手机（关机）、U盘或移动硬盘、键盘、鼠标、闹钟、计算器、书籍、草稿纸及背包等物品必须存放在考场外。如有违规带入的，一经发现，CSP-J/S认证总负责人可直接取消违规认证者的参加资格。

  CSP-S/J：认证开始15分钟后，认证者不能再进入认证点。如有认证者提前离开认证点，除身体特别原因外，须在认证进行2小时后方可准予离开。在第一轮认证期间，任何人不得将试卷携带出考场。认证者进入考场时，监考检查认证者携带物品。认证者只许携带笔、橡皮等非电子文具入场。禁止携带任何电子产品或机器设备入场，无存储功能的手表除外；手机（关机）、U盘或移动硬盘、键盘、鼠标、闹钟、计算器、书籍、草稿纸及背包等物品必须存放在考场外。如有违规带入的，一经发现，CSP-J/S认证总负责人可直接取消违规认证者的参加资格。

四、语言（NOIP2017、2018提高组）

程序设计语言一般分为机器语言、汇编语言和高级语言三大类，机器语言和汇编语言都是低级语言，高级语言又称算法语言。

• 机器语言：由0和1的不同组合所形成的可为计算机直接识别和执行的二进制指令代码的集合，是面向机器的程序设计语言。机器语言程序占用内存少、执行效率高，但编程工作量大，容易出错；依赖具体的计算机体系，因而程序的通用性、移植性都很差。 速度最快
• 汇编语言：使用助记符和有关符合编写的程序称为汇编语言程序，比机器语言更加直观，每一条用符号来表示的汇编指令都与一条计算机机器指令对应，是面向机器的程序设计语言。汇编语言的出现大大降低了记忆难度，占用内存较少，运行效率较高，不仅便于检查和修改程序错误，而且指令、数据的存放位置可以由计算机自动分配，但对于计算机CPU及其外围硬件设备具有很大的依赖性，程序员需要十分熟悉计算机系统的硬件结构。用汇编语言编写的程序称为源程序，计算机不能直接识别和处理源程序，必须通过某种方法将它翻译成为计算机能够理解并执行的机器语言，执行这个翻译工作的程序称为汇编程序。 速度快
• 高级语言：人工设计的语言，对具体的算法进行描述，所以又称为算法语言。高级语言独立于计算机的硬件（即与具体的硬件无关），相对于低级语言更容易实现跨平台的移植。 速度慢

• 结构化语言：代码和数据分离，专门描述一个功能单元逻辑要求。它不同于自然语言，也区别于任何特定的程序语言(如VB、VC 等)，是一种介于两者之间的语言。结构化描述语言一般采用英语，既有自然语言灵活性强、表达丰富的特点，又清晰易读和逻辑严密，还是一种用于数据库查询和编程的语言，已经成为关系型数据库普遍使用的标准，对程序设计和数据库的维护都带来了极大的方便，广泛地应用于各种数据查询。
• Pascal：语法严谨，层次分明，程序易写，可读性强，是第一个结构化编程语言。它基于ALGOL编程语言，是面向过程的编译型语言程序语言。
• C：结构化编译型编程语言，具有变量作用域以及递归功能的过程式语言，是面向过程、抽象化的通用程序设计语言，广泛应用于底层开发。C语言具有高效、灵活、功能丰富、表达力强和较高的可移植性等特点，在程序设计中备受青睐。C语言的设计影响了众多后来的编程语言，例如C++、Java、C#等。
• 面向对象语言：以对象作为基本程序结构单位，用于描述的设计是以对象为核心，而对象是程序运行时刻的基本成分。语言中提供了类、继承等成分，类、对象的思想实现程序共享，适合大型程序。Simula是第一个面向对象语言。
• VB(Visual Basic)：Microsoft开发的一种通用的结构化的、模块化的、面向对象的、包含协助开发环境的事件驱动为机制的可视化混合型（侧重于解释）程序设计语言，是一种可用于微软自家产品开发的语言。
• C++：面向对象的编译型程序设计语言，最初它被称作“C with Classes”（包含类的C语言），是C语言的继承，进一步扩充和完善了C语言。它是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言，支持过程化程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。
• Java：跨平台、分布式、多线索、面向对象的混合型（侧重于解释）程序设计语言，是一种先编译后解释的语言，所以它不如全编译性语言快。许多的Android应用都是Java程序员开发者开发，Java还广泛应用于企业级Web应用开发和移动应用开发。
• 解释语言：应用程序源代码一边由相应语言的解释器“翻译”成目标代码(机器语言)，一边执行，每条语言只有在执行才被翻译，每执行一次就翻译一次，因此效率比较低，而且不能生成可独立执行的可执行文件 。解释程序的优点是当语句出现语法错误时，可以立即引起程序员注意，而程序员在程序开发期间就能进行校正。一般地来说，如果你听别人说到动态语言，大多都是指解释型语言。eg.Python
• 编译语言：编译是指在应用源程序执行之前，就将程序源代码“翻译”成目标代码 (机器语言)，因此其目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高 。Java 程序需要编译，但是没有直接编译成为机器语言，而是编译成为字节码，然后在 Java 虚拟机上用解释方式执行字节码。这种运行方式带来了一些优势，但同时直接导致了复杂的环境、不算很高的效率和很多的争议。

五、计算机基础

1.ASCII码

ASCII（American Standard Code for Information Interchange，美国标准信息交流码）码是目前微型计算机中使用最广泛的一种字符编码，用7位二进制数来编码（占一个字节），可表示128个字符，最高位为0或作奇偶校验用。

常用编码：空格->0，回车->13，字符0->48，A->65，a->97

2.汉字编码

以ASCII码中的94个字符为基础，由任意两个ASCII码组成一个汉字编码（即一个汉字由两个字节组成），第一个字节称为“区”，第二个字节称为“位”，则国标码最多可表示 个汉字符号。在国标码中，实际收录汉字6763个，其中一级汉字3755个，按拼音排序；二级汉字3008个，按部首排序。为了避免国标码和ASCII码的双重定义，在计算机内部存储时，汉字的各个字节的最高位都置为1，这时的汉字编码称为机内码。

区位码：优点是无重码或重码率低，缺点是难于记忆。

音码：典型代表有全拼码和双拼码，优点是大多数人都易于掌握，但同音字多，重码率高，影响输入的速度。

形码：典型代表有五笔字型、表形码，根据汉字的字型进行编码，编码的规则较多，难于记忆，必须经过训练才能较好地掌握；重码率低。

音形码：典型代表有自然码、首尾拼音码，将音码和形码结合起来，输入汉字，减少重码率，提高汉字输入速度。

字形存储码：供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。

3.机内代码及其运算

原码：设X，若为非负数，则符号位为0，其余各位取值不变，否则符号位为1。如：

X=+1110001，则[X]原=01110001；X=-1110001，则[X]原=11110001。

反码：设X，若为非负数，则与原码相同，否则符号位为1，其余各位取值求反。如：

X=+1110001，则[X]反=01110001；X=-1110001，则[X]反=10001110。

补码：设X，若为非负数，则与原码相同，若为负数，则为反码加1。如：

X=+1110001，则[X]补=01110001；X=-1110001，则[X]补=10001111。

负补：对补码（包括符号位）的每一位求反，且最低位加1。如：

X=+1110001，[-X]补=10001111。

[X+Y]补=[X]补+[Y]补，[X-Y]补=[X]补-[Y]补=[X]补+[-Y]补（最高位产生的进位要丢掉）

4.进制（每年都考）

十进制->R进制：整数：短除法，倒序取余数

小数：连续乘以R，顺序取整数，直到小数部分为0

如：

∴

∴

R进制->十进制：小数点向左，第n位数字乘以 ；小数点向右，第n为数字乘以 ，

相加得到对应的十进制数。

5.逻辑运算

0：假 1：真

逻辑加法（或运算）：“+”或“ ”， ，

逻辑乘法（与运算）：“*”或“·”或“ ”， ，

逻辑非运算：“ ”，

同或：相同为真，不同为假 异或（Xor）：相同为假，不同为真

6.图形和图像

三基色：RGB，红绿蓝

三原色：红黄蓝

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

位图：点阵图，由许多点（像素）排列组合而成，容量较大，只要有足够多的不同色彩的像素就可以制作出色彩丰富的位图图像，放大或缩小及旋转时容易失真，清晰度受显示或打印设备的分辨率和图像文件自身的分辨率影响。

常见制作工具：Photoshop、画图等。

常见格式：BMP、TIFF、GIF、JPEG（压缩率最高）、PSD、PNG等。

大小：若为 像素、n位色彩/ 色的图像，则容量为(B)（NOIP2017提高组）

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

六、计算机网络和硬件

1.网络的发展

第一个远程计算机网络：1969年由美国国防部的高级研究计划局ARPA组织研制，称为ARPANET，是Internet的前身。

二十世纪六十年代中期之前：以单台计算机为中心的远程联机系统，也称为面向终端的计算机通信网络。

二十世纪六十年代中期至七十年代：计算机-计算机网络。

二十世纪七十年代末至九十年代：开放式标准化的网络。

二十世纪九十年代末至今L新一代的计算机网络，国际互联网与信息高速公路

2.网络的基本概念

计算机网络是利用通信线路和设备，把分布在不同地理位置上的、功能独立的多个计算机系统连接起来，以功能完善的网络软件（如网络通信协议、信息交换方式以及网络操作系统等）来实现网络中信息传递和资源共享的系统。功能独立的计算机系统一般指有CPU的计算机。

简单地说，计算机网络是指互联起来的自主计算机的集合。

自主：计算机之间没有主从关系。 集合：构成一个网络至少需要两台计算机。

最基本的网络拓扑结构：总线拓扑、星型拓扑和环形拓扑。

总线拓扑结构是一种共享通路的物理结构。这种结构中总线具有信息的双向传输功能，普遍用于局域网的连接，总线一般采用同轴电缆或双绞线。总线拓扑结构的优点是：安装容易，扩充或删除一个节点很容易，不需停止网络的正常工作，节点的故障不会殃及系统。由于各个节点共用一个总线作为数据通路，信道的利用率高。但总线结构也有其缺点：由于信道共享，连接的节点不宜过多，并且总线自身的故障可以导致系统的崩溃。如：以太网Ethernet

星形拓扑结构是一种以中央节点为中心，把若干外围节点连接起来的辐射式互联结构。这种结构适用于局域网，特别是近年来连接的局域网大都采用这种连接方式。这种连接方式以双绞线或同轴电缆作连接线路。星型拓扑结构的特点是：安装容易，结构简单，费用低，通常以集线器(Hub)作为中央节点，便于维护和管理。中央节点的正常运行对网络系统来说至关重要。

环形拓扑结构是将网络节点连接成闭合结构。信号顺着一个方向从一台设备传到另一台设备，每一台设备都配有一个收发器，信息在每台设备上的延时时间是固定的。这种结构特别适用于实时控制的局域网系统。环型拓扑结构的特点是：结构简单，适合使用光纤，传输距离远，传输延迟确定。有些网络系统为了提高通信效率和可靠性，采用了双环结构,即在原有的单环上再套一个环,使每个节点都具有两个接收通道。环型网络的弱点是，当节点发生故障时，整个网络就不能正常工作，且难以诊断故障。如：令牌环网Token Ring

网络的主要功能：资源共享、信息传输、分布处理、综合信息服务

3.网络的分类

• 局域网LAN：作用范围一般为几米到几十千米，大约是一个房间、一幢大楼或一个校园，用于连接个人电脑、工作站等各种类型的计算机和各种外围设备以实现资源共享和信息交换。如：以太网、令牌环网、令牌总线网等。
• 城域网MAN：介于LAN与WAN之间，可覆盖一群办公室或一个城市，既可能是私有的也可能是公用的。
• 广域网WAN：作用范围一般为几十到几千千米，覆盖一个国家或一个洲。
• 网络可划分成资源子网和通信子网两部分。

4.网络的标准和协议

**ISO/OSI协议模型：**各功能层之间，上一层对下一层提出服务要求，下一层完成上一层提出的要求。OSI参考模型将网络结构划分成七层：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层。这只是一种理想的概念模型。

**TCP/IP协议模型：**传输控制协议/互联网络协议，诞生于1974年12月。分为应用层（OSI的应用层、表示层、会话层）、传输层、网际层（OSI的网络层）、网络接口层（OSI的数据链路层、物理层），包含了TCP、IP、UDP（用户数据报协议）、ARP（地址解析协议）等。（NOIP2014提高组）

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

**IP地址：**Internet中的每一台主机分配一个在全球范围唯一地址。IPv4地址是由32位二进数码表示。为方便记记忆，把这32位二进制数每8个一段用“.” 隔开，再把每一段的二进制数化成十进制数，也就得到我们现在所看到的IP地址形式，用“.”隔开的四个十进制整数，每个数字取值为0—255。（NOIP2015提高组）

IP地址分A、B、C、D、E五类，目前大量使用的是A、B、C三类，最高位1……126为A类，128……191是B类，192……223是C类。D类为Internet体系结构委员会IAB专用，E类保留在今后使用。IPv4地址不够分，将被IPv6协议取代，由128位二进制码表示。

**域名：**是由一串用点分隔的名字组成的Internet上某一台计算机或计算机组的名称，用于在数据传输时标识计算机的电子方位。

**通用顶级域：**无赞助：.biz .com .edu .gov .info .int .mil .name .net .org .pro .xyz赞助：.aero .cat .coop .jobs .museum .travel .mobi .asia .tel .xxx

5.操作系统（OS）（NOIP2015提高组）

Windows类（Microsoft）：1.0（1985），2.0（1987），3.0（1990，红心大战和扫雷），NT，95（出现“开始”菜单），98（原生支持USB接口），98 SE，2000（最后一个专为企业开发的Windows系统），Me（最后一个基于MS-DOS开发的操作系统），XP，Vista，7，8，10

**UNIX：**多用户，多任务的分时操作系统，大部分是由C语言编写的，这使得系统易读，易修改，易移植，1969年开发。

**LINUX：**自由和开放源码的类UNIX操作系统，较适用于小型网络，1991年10月5日发布

**MAC OS：**运行于苹果电脑上的操作系统，是首个在商用领域成功的图形用户界面操作系统。Mac系统是基于Unix内核的图形化操作系统，一般情况下在普通PC上无法安装的操作系统。由苹果公司自行开发。

**iOS：**原名为iPhone OS，是苹果公司为其移动设备所开发的专有移动操作系统，为其公司的许多移动设备提供操作界面，支持设备包括iPhone、iPad和iPod touch。iPhone OS自iOS 4起便改名为iOS，它是全球第二大最受欢迎的移动操作系统，仅次于Google开发的安卓系统。

6.其他

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

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

七、数据结构

1.存储结构

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

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

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

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

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

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

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

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

2.数据结构

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

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

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

3.树

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

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

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

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

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

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

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

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

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

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

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

③若叶节点数为 度为2的节点数为 ，则一定满足 。

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

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

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

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

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

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

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

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

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

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

4.图

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

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

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

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

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

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

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

八、算法

1.算法的基本概念

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

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

复杂度：时间复杂度，通常题目中给出的是时间递推关系式。

NOIP2015T11，2016T14，2017T6，2018T5（提高组）

2.排序

• 简单排序：选择排序：对待排序的记录序列进行n-1遍的处理。第一遍处理是将L[1..n]中最小
• 者与L[1]交换位置，第二遍处理是将L[2..n]中最小者与L[2]交换位置，以
• 此类推，时间复杂度为O( )。选择排序是稳定排序。
• 插入排序：经过i-1遍处理后，L[1..i-1]已排好序。第i遍处理仅将L[i]插入L[1..i-1]的
• 适当位置p，原来p后的元素一一向右移动一个位置，使得L[1..i]又是排
• 好序的序列，时间复杂度为O( )。插入排序是稳定排序。
• 冒泡排序：又称交换排序。对待排序的记录的关键字进行两两比较，如果发现是反
• 序的，则进行交换，时间复杂度为O( )。冒泡排序是稳定排序。
• 快速排序：先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放在它的一边，
• 再对左右两边分别用同样的方法处理，直到每一个待处理的序列长度为1，处理结
• 束。时间复杂度下限为O(nlogn)，上限为O( )。快速排序是不稳定排序，基于分治思想。
• 希尔排序：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。
• 堆排序
• 二叉树排序

以上收集整理自知乎高中竞赛学习笔记专栏。