CSP 初赛篇 第 1 章 计算机与网络基础知识 1.1计算机发展及应用 1、第一台电子计算机的诞生： ENIAC

2、第一台具有存储程序功能的计算机： EDVAC 。

关于图灵我们要知道的知识：图灵机、图灵实验、图灵奖。

【NOIP2019 普及组】15. 以下哪个奖项是计算机科学领域的最高奖？（ ） A.图灵奖 B.鲁班奖 C.诺贝尔奖 D.普利策奖 答案：A 解析：计算机基础-常识-重要人/事，图灵奖由美国计算机协会于 1966 年设立，其名称取自 计算机科学之父图灵，专门奖励对计算机事业做出重要贡献的个人，被誉为“计算机界的 诺贝尔奖”。

【NOIP2018 提高组】【不定项选择】5. 下列关于图灵奖的说法中，正确的有（ ）。 A.图灵奖是由电气和电子工程师协会（IEEE）设立的。 B.目前获得该奖项的华人学者只有姚期智教授一人。 C.其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。 答案：BCD 解析：计算机基础-常识-重要人/事。

4、世界上第一位软件工程师 英国著名诗人拜伦的女儿 Ada Lovelace(爱达)。由于她在程序设计上的开创性工作， Ada Lovelace 被称为世界上“第一位程序员”，“世界上第一位软件工程师”。

5、计算机发展的四个阶段 第一代：电子管计算机（1946~1956） 第二代：晶体管计算机（1956~1963） 第三代：中小规模集成电路计算机（1964~1971） 第四代：大规模集成电路计算机（1971 年以后）

6、微型计算机的问世 第四代 1971——至今 超大规模集成电路的微型计算机个人 PC 应用到了各个领域。 7、计算机的应用

1.1计算机系统的基本结构 计算机系统由硬件和软件两部分组成。

1.2硬件系统组成 1、冯·诺伊曼体系 五个基本部分组成：（1）运算器，（2）控制器，（3）存储器，（4）输入设备，（5）输出设备。

（1）中央处理器（CPU，Central Processing Unit） 由运算器、控制器和寄存器组成； 运算器：负责算术运算和逻辑运算； 控制器：负责计算机系统控制； CPU 主要性能指标： 主频和字长 。 CPU 的品牌： Intel、AMD、IBM（服务器CPU） 。 （2）存储器 用于保存各类程序的数据信息。存储器分为：主存储器和辅助存储器。 A、主存储器： 也称内存储器 ，属于主机的一部分。用于存放系统当前正在执行的数 据和程序，属于临时存储器。 主存储器的信息（内存）可以被 CPU 直接访问，内存由半导体存储器组成，存取速度快， 容量一般较小。内存中含有很多存储单元，每个存储单元可以存放 1 个 8 位二进制数（1 个字节），内存中每个字节有一个固定的编号，这个编号称为地址，CPU 在存取存储器中的数据是按地址进行的。 内存可分为： 只读存储器（ROM）、随机存储器（RAM）和高速缓冲存储器 Cache 。 ROM：只读存储器，信息只能被读入，不能写入新信息，计算机断电后，ROM 中的信息不 会丢失，用于检查系统配置及提供基本的输入输出控制程序。 RAM：读写存储器，可读、可写， 断电后RAM 中的信息全部丢失 。

高速缓冲存储器 Cache：由于 CPU 的速度不断提高，RAM 的读写速度很难满足 CPU 的要求，因此在读写内存时会加入等待时间，对于高速 CPU 而言是一种浪费，Cache 主要用于 CPU 与内存之间设置高速小容量存储器，固化于主板，用于提升 CPU 的读写效率。 B、外存储器：又称为辅助存储器，容量一般较大，大部分可移动，用于计算机之间的交流，外存一般有硬盘、闪存（优盘）、光盘、软盘，现在用得比较多的是 闪存和硬盘 。

2、计算机的三总线结构 总线是一组导线、是公共通路，微型计算机中各个组成部件之间的信息传输都是通过它们来实现的。

3、计算机主要的性能指标 （1）字长：通常 PC 机的字长为 16 位（早期），32 位，64 位。字长越长、表示的数据范围就越大、计算出结果的有效位数就越多、能表示的信息也就越多、机器处理功能就更强。 （2）运算速度：指的是计算机每秒钟能够执行的指令条数，一般用 MIPS（Million of Instruction Per Second，每秒百万条指令）为单位。 （3）主频：计算机 CPU 的时钟频率，一般主频越高，运算速度就越快（一个时钟周期内完成的指令越多）。 （4）内存容量：内存储器能够存储信息的总字节数，目前计算机的内存储容量一般是2GB、4GB、8GB 等。 注意： 区分字节和字长， 1 个字节（byte）= 8 位（bit） ，而字长是与芯片型号有关系的。 是 CPU 的寻址空间不同（ 【NOIP2018 普及组】1.以下哪一种设备属于输出设备：（ ） A.扫描仪 B. 键盘 C. 鼠标 D. 打印机

答案：D 解析：除了选项 D，其余的都是输入设备。

【NOIP2017 普及组】5.计算机应用的最早领域是（ ）。 A. 数值计算 B. 人工智能 C. 机器人 D. 过程控制答案：A

【NOIP2016 普及组】4.以下不是 CPU 生产厂商的是（ ）。A.Intel B. AMD C. Microsoft D. IBM 答案：C 解析：Microsoft 最著名的产品是家用操作系统以及Office 系列的软件。Intel 和 Amd 是家用 CPU 的生产厂商，IBM 是服务器 CPU 的生产厂商。

【NOIP2016 普及组】5.以下不是存储设备的是（ ）。 A. 光盘 B. 磁盘 C. 固态硬盘 D. 鼠标 答案：D 解析：鼠标是输入设备，不是存储设备

【NOIP2016 普及组】9.以下是 32 位机器和 64 位机器的区别的是（ ）。 A. 显示器不同 B. 硬盘大小不同 C. 寻址空间不同 D. 输入法不同答案：C

【NOIP2016 提高组】2.可以将单个计算机接入到计算机网络中的网络接入通讯设备有（ ）。 【不定项选择题】 A. 网卡 B. 光驱 C. 鼠标 D. 显卡答案：A

1.3软件系统组成

1、系统软件 （1）家用PC 操作系统 Windows 系列,苹果：Mac OS X。 （2）服务器操作系统 Windows 系列：Windows NT Server、Windows Server200x 等； Linux 系列： Red Hat Linux、CentOS、UbuntuServer、Debian 等； Unix 系列：Sun Solaris、IBM AIX 等； （3）手机操作系统 IOS（苹果），Android（安卓）

2、应用软件 后缀名： 可执行文件：bat、com、exe…… 文档文件：doc（docx）、xls（xlsx）、txt、ppt（pptx）……图片文件：gif、jpg、png…… 压缩文件：rar、zip 视频文件：avi、wav、mpg、mov、swf（flash）、mp4、rmvb

3、计算机语言 编程语言分类：机器语言，汇编语言，高级语言。

（1）机器语言：最早出现的使用二进制代码编写的计算机能直接识别的语言。 （2）汇编语言：用一些符号代替机器指令所产生的语言。虽然汇编语言比机器语言简单，但仍属于低级语言，汇编语言与计算机体系结构有关，在编写程序前需要花大量时间熟悉机器结构。 （3）高级语言：程序员容易理解的编程语言。比如： c, c++,VB等 。 高级语言中有一类叫做面向对象的语言，比如：Java、C++、C#、Python、请注意C语言不是面向对象的 。

4、高级语言的执行过程 编译型、解释型。 编译型程序有：C/C++、Pascal等。 解释型程序有：Asp、PHP、Python等。

【NOIP2017 普及组】6.下列不属于面向对象程序设计语言的是（ ）。 A. C B. C++ C. Java D. C# 答案：A 【NOIP2016 普及组】1.以下不是微软公司出品的软件是（ ）。

A. Powerpoint B. Word

C. Excel D. Acrobat Reader

答案：D 解析： 选项 D 是 Adobe 公司的产品， Microsoft 公司最著名的产品有 Microsoft Office(Word/Excel/PPT)、Microsoft Windows（操作系统）。

1.4计算机网络的基本概念 1、 计算机网络分类 计算机网络的分类方式有很多种,可以按地理范围、拓扑结构、传输速率和传输介质等分类。 A、地理范围分类 ①局域网 LAN（Local Area Network），②城域网 MAN（Metropolitan Area Network）， ③广域网 WAN（Wide Area Network）， 2、Internet 网络地址 (IP 地址) IPv4 地址共有 32 位，分为 4 段，每段 8 位（也即 1 个字节） 。它的表示方法如下：xxx.xxx.xxx.xxx，其中每段的取值范围为 0～255 。 3、计算机网络的基本概念 A、域名 IP 地址和域名是一一对应的，这份域名地址的信息存放在一个叫域名服务器(DNS) 顶级域名有三类： 国家顶级域名：如 cn（中国）、us（美国）、uk（英国）。 通用顶级域名：com（商业组织）、net（网络组织）、edu（教育机构）、org（非盈利性组织）、gov（政府部门）。

B、常见的网络服务与协议小结 在计算机网络中一系列的通信规则和约定的集合，称为网络协议 常见网络协议与缩写总结如下：

TCP Transmission Control Protocol 传输控制协议 IP Internet Protocol 网际互连协议 DNS Domain name server 域名服务器 HTTP Hyper Text Transmission Protocol 超文本传输协议 HTML Hyper Text Markup Language 超文本标记协议 FTP File Transfer Protocol 文件传输协议 SMTP/POP3/IMAP Simple Mail Transfer Protocol/ Post Office Protocol/ Internet Mail Access Protocol 简单邮件传输协议/ 邮局协议/ Internet 邮件访问协议 WWW World Wide Web 万维网 URL Uniform Resource Locator 统一资源定位符 ARP Address Resolution Protocol 地址解析协议

5、计算机安全知识 计算机安全中最重要的是存储数据的安全，主要面临的威胁有：计算机病毒、非法访问、计算机电磁辐射、硬件损坏等。 计算机病毒的特性： A、 隐蔽性； B、 潜伏性； C、 传播性； D、 激发性：在一定的条件刺激下，病毒程序迅速活跃起来； E、 破坏性和危害性；

【NOIP2019 普及组】1、中国的国家顶级域名是( )。 A. .cn B. .ch C. .chn D. .china 答案：A

【NOIP2018 普及组】4. 广域网的英文缩写是（ ）。

A.LAN B.WAN C.MAN D.LNA 答案：B 解析：WAN：Wide area network，广域网LAN：local area network，局域网MAN：Metropolitan Area Network，城域网

【NOIP2017 普及组】3.下列协议中与电子邮件无关的是（ ）。 A. POP3 B. SMTP C. WTO D. IMAP 答案：C

【NOIP2016 普及组】3. 以下不属于无线通信技术的是（ ）。 A. 蓝牙 B. WiFi C. GPRS D. 以太网答案：D

1.5进制转换 数值信息在计算机内的表示方法就是用二进制数来表示。 一般说来，如果数制只采用 R 个基本符号（0~R-1），则称为基 R 数值，R 称为数制的基数，而数制中每一固定位置对应的单位值称为权。

进制 基数R 基本符号 二进制 2 0,1 八进制 8 0,1,2,3,4,5,6,7 十进制 10 0,1,2,3,4,5,6,7,8,9 十六进制 16 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F（对应十进制的0~15） 进位计数制的编码符合“逢 R 进位”的规则，各位的权是以 R 为底的幂，一个数可按权展开成为多项式。 例如，一个十进制数 256.47 可按权展开为 256.47=2×102＋5×101＋6×100 十 4×10-1＋ 7×10-2 1、R 进制转换为十进制 按权展开！ 基数为 R 的数字，只要将各位数字与它的权相乘，其积相加求出的和数就是十进制数。例: 3506.28 =6×80+0×81+5×82+3×83+2×8-1 =1862.25 例: 0.2A16 =2×16-1+10×16-2 =0.1640625

2、十进制转换为 R 进制 十进制整数转换成R 进制的整数: 除 R 取余法。例 ： （10）10 ＝（1010）2

十进制小数转换成R 进制时: 乘 R 取整. 例： (0．625)10= (0．101)2 0．625 X 2 1．25 1 X 2 0．5 0 X 2 1．0 1

3、二、八、十六进制的相互转换 每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时， 位组划分是以小数点为中心向左右两边延伸，中间的 0 不能省略，两头不够时可以补 0。尤其是小数后末尾的 0。 例如：将 1011010.12 转换成八进制和十六进制数 001 011 010. 100 1011010.12＝132.48 1 3 2. 4 0101 1010. 1000 1011010.12=5A.816 5 A . 8 例如：将十六进制数 F7.28 变为二进制数 F 7 . 2 8 F7.2816=11110111.001012 1111 0111.0010 1000

【NOIP2019 普及组】2、二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑与运算的结果是( )。

A. 01 0010 1000 1011 B. 01 0010 1001 0011 C. 01 0010 1000 0001 D. 01 0010 1000 0011 答案：D 解析：逐位进行与运算，1 与 1 得 1，其余都为 0。

【NOIP2018 普及组】1.下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。A. (269)16 B. (617)10 C. (1151)8 D. (1001101011)2 答案：D 解析：可以将每一项都转为 10 进制进行比较，选项 D 转换为 10 进制后值为 619，因此选D。

1.6计算机编码 计算机只能识别两个数字：0 和 1。因此计算机中所有的信息：数值、字符、图形、视频、声音等都需要转换为 0 和 1 表示的代码，这个过程就是编码。 1、信息存储的单位 位（bit，缩写为 b）：度量数据的最小单位，表示一位二进制信息。 字节(byte，缩写为 B)：一个字节由八位二进制数字组成（l byte＝8bit）。 字节是信息存储的最小存储单位。 计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。常用的单位有：

KB 1K=1024Byte MB 1M=1024KB GB 1G=1024M TB 1T=1024G 机器字（word）：字是位的组合，并作为一个独立的信息单位处理。字又称为计算机字，它取决于机器的类型、字长以及使用者的要求。常用的固定字长有 8 位、16 位、32位、64 位等。 机器字长是指计算机进行一次整数运算所能处理的二进制数据的位数，机器字长反映了计算机的运算精度，即字长越长，数的表示范围也越大，精度也越高。

2、ASCII 码 ASCII 码是 7 位的二进制编码，能表示 27=128 种常见的西文字符。 常见的 ASCII 码对应的值：字符'0'的编码是 48、'A'的编码是 65、'a'的编码是 97。

3、汉字编码 A、汉字交换码 GB2312-80 标准包含 6763 个汉字 B、字形存储码 字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常， 采用的是数字化点阵字模。（如下图）

一般的点阵规模有 16×16，24×24，32×32，64×64 等，每一个点在存储器中用一个二进制位（bit）存储。例如，在 16×16 的点阵中，需 16×16bit=16×16/8byte=32 byte 的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。 为了节省存储空间，普遍采用了字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息。

【NOIP2019 普及组】3、一个 32 位整型变量占用( )个字节。A.32 B.128 C.4 D. 8 答案：C 解析：1byte=8bit，因此 32 位占用 32/8=4 个字节。

【NOIP2018 普及组】3、1MB 等于（ ）。A.1000 字节 B. 1024 字节 C. 1000 X 1000 字节 D. 1024 X 1024 字节 答案：D

【NOIP2017 普及组】2. 计算机存储数据的基本单位是（ ）。 A. bit B. Byte C. GB D. KB 答案：B

【NOIP2017 提高组】3.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。 A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 答案：A 解析：所需空间 = (1600 * 900 * 16) / (1024 * 8) = 2812.5KB

【NOIP2016 提高组】9. 某计算机的 CPU 和内存之间的地址总线宽度是 32 位（bit），这台计算机最多可以使用（ ）的内存。

A.2GB B. 4GB C. 8GB D. 16GB 答案：B 解析：32bit 计算机最多的寻址单元有有 232，1GB=230（210210210）, 4GB=22*230=232

1.7计算机中带符号数的表示法 1、原码 在用二进制原码表示的数中，符号位为 0 表示正数，符号位为 1 表示负数，其余各位表示数值部分。 如：10000010，00000010。

2、反码 （原因是计算机实际上只能做加法） 反码的定义如下： （1）对于正数，它的反码表示与原码相同。即[x]反=[x]原 （2）对于负数，则除符号位仍为“1”外，其余各位“1”换成”0”，”0”换成 1”，即得到反码[X]反。 例如[-1101001] 反=10010110。 （3）对于 0，它的反码有两种表示:[+0] 反=00…0 [-0] 反=11…1 3、补码 正数的补码就是该正数本身。[01100100]补 ＝01100100 对于负数：两头的 1 不变，中间取反。（负数取反加一） [10100100]补 ＝11011100 [+0]补＝[-0]补＝00…0。 总结：正数的原码、反码、补码相同，负数反码符号位不变其余取反，负数的补码=反码+1（补码的作用主要方便计算机运算） 原码 反码 补码 2 00000010 00000010 00000010 -2 10000010 11111101 11111110 0 00000000 00000000 11111111 00000000

4、BCD 码（8421 码） BCD 码就是用二进制代码表示的十进制数，也称 BCD 数。它是用 4 位二进制代码 0000— 1001 来表示十进制数 0---9。如：39 的 BCD 码为 00111001。

5、整数和浮点数的表示及在 C++中的运算 A、整数 整型值可以用十进制，十六进制或八进制符号指定，前面可以加上可选的符号（-或者 +）。 B、浮点数 浮点数，在计算机中用以近似表示任意某个实数。具体来说，这个实数由一个整数或定点数（即尾数）乘以某个基数（计算机中通常是 2）的整数次幂得到，这种表示方法类似于基数为 10 的科学记数法。用 E(e)来表示指数部分。如 123.456 或 123e-2。 C、在 C++中表示进制数及位运算例子： //以 0 开头表示 8 进制 int a = 010; //打印时以 10 进制打印cout<<a<<endl;

//以 0x 开头表示 16 进制int b = 0x1A; //26 cout<<b<<endl;

//科学计数法，表示 1 * 10^2 int c = 1e2; cout<<c<<endl;

double d = 1e-2; cout<<d<<endl;

例子：整数的& | << >>运算 /* &：二进制与，将两个数换算为二进制，然后做&运算1100 101 0100 */ int a = 5 & 12; //打印以 10 进制打印cout<<a<<endl;

int b = 5 | 12; cout<<b<<endl;

/* 左移运算：将整数换算为二进制，然后左移 1 位 101 -> 左移 1 位 -> 1010 -> 对应十进制 10 左移：相当于将整数乘 2 */ int c = 5 << 1; cout<<c<<endl;

/* 右移运算：将整数换算为二进制，然后右移 1 位 101 -> 右移 1 位 -> 10 -> 对应十进制 2

右移：相当于将整数除 2 */ int d = 5 >> 1; cout<<d<<endl;

注意：本质上来说，计算机判断两个小数是否相等，不能用==

【NOIP2017 提高组】2.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。A. 43 B. -85 C. -43 D.-84 答案：B 解析：10101011 对应反码是：10101010，对应原码是：11010101，对应的整数是：-85。

第 2 章 算法知识、栈、队列

2.1算法知识 算法是对特定问题求解步骤的描述，算法有 5 个重要特征。 （1）有穷性：对于任意一组合法的输入，算法能在有限的时间内完成。 （2）确定性：算法的每一步有明确的定义，没有歧义。 （3）输入：算法应有 0 个或多个输入。（一般 0 个输入指的是有些算法的输入是嵌入到算法之中的） （4）输出：算法应有 1 个或者多个输出。 （5）可行性：算法必须遵循特定条件下的解题规则，算法描述的操作都应该是特定规则中允许使用的、可执行的，并通过执行有限次来实现。 常见的算法有：穷举、高精度计算、排序、递推、递归、贪心、分治、搜索、动态规划等。 1、算法复杂度 一个算法的评价一般从时间复杂度和空间复杂度来考虑。 时间复杂度：指算法所需要的计算工作量，用算法所执行的基本运算次数来度量。常见的时间复杂度有：常数阶O(1)，对数阶 O(log2n)，线性阶 O(n)，线性对数阶O(n* log2n)， 平方阶O(n2)，立方阶 O(n3)，指数阶 O(2n)等，上述时间复杂度随着问题规模n 的增加，时间复杂度不断增加，算法效率降低。 时间复杂度的计算步骤： 求解算法的时间复杂度的具体步骤是： 1、找出算法中的基本语句： 算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。2、计算基本语句的执行次数的数量级： （1）只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。 3、用大Ο记号表示算法的时间性能： （1）本例如： for(i=1;i<=n;i++) x++; for(i=1;i<=n;i++){ for(j=1;j<=n;j++) x++; } 第一个 for 循环的时间复杂度为Ο(n)，第二个 for 循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。 下面按从快到慢的顺序列出了你经常会遇到的 5 种大 O 运行时间。（时间复杂度只需要

计算到对应的数量级，不需要计算到具体的值） （1）O(log n)，也叫对数时间，这样的算法包括二分查找。 （2）O(n)，也叫线性时间，这样的算法包括简单查找。 （3）O(n * log n)，这样的算法包括快速排序——一种速度较快的排序算法。 （4）O(n2)，这样的算法包括选择排序、冒泡排序——一种速度较慢的排序算法。 （5）O(n!)，这种情况很少见，n 越大，所消耗的时间就越慢。 大 O 表示法是一种特殊的表示法，指出了算法的速度有多快。例如，假设列表包含 n 个元素。简单查找需要检查每个元素，因此需要执行n 次操作，这个运行时间为 O(n)。 一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何其他情况更长。

图 四种算法效率对比 空间复杂度：指执行这个算法所需要的内存空间。 2、常见算法的算法复杂度 （1）查找算法

查找策略 时间复杂度 备注

顺序查找 O(n) 二分查找 O(log2n) 要求数列有序 插值查找 O(log2n) 要求数列有序且相对均匀 https://www.bilibili.com/video/BV14K4y1t71j/?spm_id_from=333.788&vd_source=3506c5d97c8e0fc57f665b8427340cab 顺序查找、二分查找、冒泡排序、选择排序、排序算法、快速排序算法、归并排序锦标赛排序 数据结构：图和树、认识二叉树、树的遍历算法、树的遍历（2）

（2）排序算法

排序 算法复杂度 冒泡排序 O(n2) 直接插入 O(n2) 快速排序、堆排序、归并排序 O(nlog2n) 选择排序 O(n2) 桶排序 O(n)

【NOIP2018 普及组】8.以下排序算法中，不需要进行关键字比较操作的算法是（ ）。 A. 基数排序 B. 冒泡排序 C. 堆排序 D. 直接插入排序答案：A 解析：基数排序，根据键值的每位数字来分配桶； 冒泡排序、堆排序和插入排序都是基于两两元素关键字比较的排序。基数排序是直接将元素通过某些规则放到数组的相应位置，不是基于两两元素关键字比较的排序。

2.2什么是数据结构？ 1、数据结构的定义 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。如：数组。

2、数组有什么特点？ （1）数组(array)的元素(element)或项(item) 的类型是相同的 （2）数组对某元素的存取是 O(1)时间 （3）数组的插入、删除操作是 O(n)时间 由于数组通常的插入、删除操作是 O(n)时间的，在某些特定的条件下就显得低效了。因此我们通过对数组元素操作的限制，来达到操作的高效---算法优化的突破点。 常见的“订制”数组有：栈、队列、堆等，它们操作的时候效率都很高。

2.3栈（Stack）

1、栈的特点 （1）栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的 （2）栈有三个基础操作压入(push),弹出(pop),取数(getTop)操作都为 O(1)时间 （3）栈有一个计数器 counter 或栈顶指针

2、栈的基本操作 （1）建栈（init）：在使用栈之前，首先需要建立一个空栈，称建栈； （2）压栈（push）：往栈顶加入一个新元素，称进栈（压栈）； （3）出栈（pop）：删除栈顶元素，称出栈（退栈、弹出）； （4）取栈顶（gettop）：查看当前的栈顶元素，称读栈； （5）测试栈（empty）在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈； （6）显示栈（display）：输出栈的所有元素； （7）释放栈（setnull）：清空栈；

3、栈的练习题 【noip2015 普及组】15. 今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈，进栈，出栈，进栈，进 栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为

（ ） A. f B. c C. a D. b 答案：B 解析：画一个栈，按照题目所描述的操作模拟一遍。

【noip2017 提高组】2. 对于入栈顺序为 a, b, c, d, e, f, g 的序列，下列( )不可能是合法的出栈序列。【不定项选择题】 A. a,b,c,d,e,f,g B. a,d,c,b,e,g,f C. a,d,b,c,g,f,e D.g,f,e,d,c,b,a 答案：C 解析：画一个栈，逐个选项判断模拟是否可行。

【noip2012 普及组】18．在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。 A．系统分配的栈空间溢出 B．系统分配的堆空间溢出 C．系统分配的队列空间溢出 D．系统分配的链表空间溢出答案：A 解析：递归是用栈这种数据结构来实现的。 执行时，外层的函数先进栈，内层的函数后进栈。内层的函数把结果返回给外层的函数并出栈。

【noip2010 普及组】15．元素 R1、R2、R3、R4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如果第一个出栈的是 R3，那么第五个出栈的不可能是（ ）。 A．R1 B．R2 C．R4 D．R5 答案：B答案：C 解析：画一个栈，逐个选项判断模拟是否可行。

2.4队列 1、什么是队列？ 队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾， 通常用一个队尾指针 r 指向队尾元素，即 r 总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针 f 指向排头元素的前面。初始时 f=r=0。

举例 1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例 2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。 结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO）的线性表。

2、队列的基本操作 （1）新建队列 （2）入队 （3）出队 （4）判断队列是否为空 （5）判断队列是否为满 （6）显示队列元素

3、队列练习题 【noip2018 普及组】15.下图中所使用的数据结构是（ ）。

A.哈希表 B. 栈 C. 队列 D. 二叉树答案：B

【noip2012 普及组】2．（ ）是一种先进先出的线性表。 A．栈 B．队列 C．哈希表（散列表） D．二叉树答案：B

【noip2011 普及组】11．广度优先搜索时，需要用到的数据结构是（ ）。A．链表 B．队列 C．栈 D．散列表 答案：B

第 3 章 链表及链式栈、链式队列

3.1指针（Pointer） 1、什么是指针？ 指针（Pointer）：变量的地址，通过它能找到以它为地址的内存单元。 例子：理解指针的概念，区分什么是地址（指针），什么是地址指向的值！理解如何通过指针修改变量的值！ #include <bits/stdc++.h> using namespace std;

int main(){ int x = 10; //定义指针，指向 x 的地址 int p = &x; //p 是 int类型的指针（整数的地址） cout<<p<<endl; //*p 不是地址，是 p 这个地址指向的值 cout<<*p<<endl;

*p = *p + 2;//修改指针指向的变量的值cout<<p<<" "<<*p<<endl; cout<<x<<endl;

//数组的本质是数组中下标为 0 的元素的地址 int arr[5] = {0}; cout<<&arr<<" "<<&arr[0]<<" "<<arr<<endl;

//采用 scanf 读入int a,b; scanf("%d%d",&a,&b); printf("a=%d\n",a); printf("b=%d\n",b); printf("%d+%d=%d\n",a,b,a+b);

return 0; } 问题：对比如下代码输出的结果，理解指针和普通变量的不同； #include <bits/stdc++.h> using namespace std;

int main(){ int x = 10; int y = x; y = y + 2; cout<<y<<endl<<x<<endl;

int *p = &x; *p = *p + 2; cout<<*p<<endl<<x<<endl;

int a = 10; int *p2 = &a; cout<<p2<<" "<<a<<endl; (p2)++;//注意++的优先级高于 cout<<p2<<" "<<a<<endl;

return 0; }

例子：*p++和(*p)++的区别 int x = 10; int *p = &x; cout<<p<<endl<<x<<endl; *p++; cout<<p<<endl<<x<<endl; 注意：上述代码并不能通过指针修改 x 的值，*p++相当于 p++是在对指针的值自增（相当于地址值自增）。

3.2链表 1、链表介绍 （1）线性表的优点 A、无需为表示结点间的逻辑关系而增加额外的存储空间； B、可方便地随机存取表中的任一元素。 （2）线性表的缺点 A、插入或删除平均需要移动一半的结点； B、顺序表要求占用连续的存储空间；

问题：存储一个班同学的成绩（人数不确定），如何存储？解决方法 1：定义尽可能长的数组来存储！ 99 100 98 90 88 97 100 92 … 98

解决方法 2：利用链表来存储！

注意：链表结构并不一定占用连续的内存空间，其占用的内存空间可以不连续！

（3）链表的基本概念A.结点(Node)组成

A.数据域：存储数据元素本身 B.指针域：存储邻接元素的存储地址(位置) C.链接方式： 单链表：每个结点只有一个指针域。双向链表：每个结点有两个指针域。循环链表：是一个首尾相接的链表。E.头指针 ：指向链表头结点的指针。

第 4 章 树和二叉树

4.1树 1、常见的数据结构？ （1）集合 集合的定义是由一组无序且唯一（即不能重复）的项组成的。不包含任何元素的集合就叫做空集。

（3）树形结构 n 个有限节点组成一个具有层次关系的集合。

（2）线性结构 线性结构是一个有序数据元素的集合。 常用的线性结构有：线性表，栈，队列，双队列，数组，串。 元素 1 元素 2 元素 3 元素 4 元素 5 0 1 2 3 4

（4）图形结构 图形结构——多个对多个，如图。

2、什么是树？ 树：是一种数据结构，它是由 n（n>=0）个有限节点组成一个具有层次关系的集合。树是一类非线性结构。这种结构结点之间有分支，并具有层次关系。它非常类似于自然界中的树。 树的作用：表达家谱顺序、行政组织结构、计算机文件结构、书的教材章节结构等。 3、树的基本概念 （1）树是 n（n≥0）个结点的有限集。 （2）当 n=0 时称为空树； （3）当 n>0 时为非空树，在任意一棵非空树中，有且仅有一个称为根的结点，其余的结点可分为 m(m ≥0)个互不相交的有限集 T1,T2,…,Tm，其中每一个集合又称为一棵树，并且称为根的子树；同理，每一棵子树又可以分为若干个互不相交的有限集…… 总结树的特性： （1）空树是树的特例; （2）非空树中至少有一个结点，称为树的根，只有根结点的树称为最小树;

（3）在含有多个结点的树中，除根结点外，其余结点构成若干棵子树，且各子树间互不相交。 4、树的基本术语 （1）树的结点： 包含一个数据元素及若干个指向其子树的分支 ； （2）结点的度： 一个结点拥有的子树数目 ； （3）树的度： 一棵树上所有结点度的最大值 ； （4）叶子结点（终端结点）： 度为零的结点 ； （5）分支结点（非终端结点）： 度大于零的结点 ； （6）路径（从根到结点的）： 由从根到该结点所经分支和结点构成 ； （7）孩子结点： 结点的子树的根称为该结点的孩子结点 ； （8）双亲结点： 相应地，该结点称为孩子的双亲结点； （9）兄弟： 具有同一父结点的子结点互称兄弟 ； （10）堂兄弟： 其双亲在同一层的结点互为堂兄弟 ； （11）祖先结点： 从根到该结点所经分支上的所有结点 ； （12）子孙结点： 以某结点为根的子树中任一结点都称为该结点的子孙 ； （13）结点的层次： 从根结点到该结点所经过的路径长度加 1 ； （14）树的深度： 树中叶子结点具有的最大层次数 ； （15）树的宽度： 整棵树中某一层中最多的结点数称为树的宽度 ； （16）有序树： 如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，与之相对的是无序树 ； （17）第一个孩子： 在有序树中，最左边的子树的根称为第一个孩子 ； （18）最后一个孩子： 在有序树中，最右边的子树的根称为最后一个孩子 ； 练习：参照右图的树，回答下列问题 （1）该树有哪些结点 ABCDEFGHIJKLM ， 其中的叶子节点有 EKLGHIM ，分支节点有 ABCDFJ 。 （2）结点 A 的度为 3 ，结点 B 的度为 2 ，树的度为 3 。 （3）请写出A 节点到K 节点经过的路径 A->B->F->K 。 （4）H 结点的兄弟结点有 I、J ，堂兄弟结点有 E、F、G 。 （5）F 结点的祖先结点有 B、A ，子孙结点有 K、L 。 （6）该树的深度为 4 ，树的宽度为 6 。

5、树的表示方法 了解树的表示方法。

二叉链表（孩子-兄弟）表示法 在这种存储方式下，每个结点包括三部分的内容：结点值、指向该结点第一个孩子结点的指针和指向该结点下一个兄弟结点的指针。 firstchild data nextsiblings

4.2二叉树 1、什么是二叉树？ 二叉树是 n (n≥0) 个结点的有限集合，这个集合或是空集，或是由一个根结点以及两棵互不相交的、被称为根的左子树和右子树所组成；左子树和右子树分别又是一棵二叉树。 二叉树的特点：每个结点至多只有两棵子树，且二叉树的子树有左右之分，其次序不能任意颠倒。

问题：二叉树和树有哪些不同？ ① 树中结点的最大度数没有限制，而二叉树结点的最大度数为 2 。 ② 树的结点无左、右之分，而二叉树的结点有左右之分 。

问题：具有 3 个结点的二叉树可能有 5 种不同形态？普通树有 2 种不同的形态？ 请分别画出他们。

2、满二叉树和完全二叉树

满二叉树：一棵深度为 k 且有 2k -1 个结点 的二叉树。（特点：每一层上的结点数都是最大结点数）

完全二叉树：深度为 k 的，有 n 个结点的二 叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应 （特点： 至多只有最下面两层的结点的度可以小于 2，且倒二层如果只有一个孩子，那必是左孩子。）

注意：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1 层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。 一棵深度为 k 的完全二叉树，至少有 2k-1 个结点，最多有 2k-1 个结点。

3、二叉树的性质(可以自己了解，看自己安排) ① 性质 1：在二叉树的第i 层上至多有 2i-1 个结点（i≥1）。问题：在第 i 层上至少有 1 个结点。 ② 性质 2：深度为 h 的二叉树至多有 2h-1 个结点（h≥1）。 问题：一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。问题：一颗深度为 k 的二叉树，至少有 k 个结点。

③ 性质 3：对任何一棵二叉树，如果其叶结点数 n0，度为 2 的结点数为 n2，则一定满足：n0= n2+1 。 问题：一棵完全二叉树有 5000 个结点，可以计算出其叶结点的个数是 2500 。 ④ 性质 4：具有 n 个结点的完全二叉树的深度为 floor(log2n)+1 。

⑤ 性质 5：对于一棵 n 个结点的完全二叉树，对任一个结点（编号为 i） 如果 i=1，则结点 i 为根，无 父结点 ；如果 i>1，则其父结点编号为 floor(i/2) 。 如果 2i>n，则结点 i 无 子节点 ，即结点 i 为 叶结点 ；否则左孩子编号为
2i 。 如果 2i+1>n，则结点 i 无 右孩子 ，否则右孩子编号为 2i+1 。

4、二叉树的存储 （1）表示方法一：数组表示法 对于完全二叉树，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。 对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应位置中。

（2）表示方法二：字符串表示法；本质上来说，还是数组表示法。

用字符串表示为：string s = "LDPCFM###EH#N";

（3）表示方法三：链式存储； 采用：含有两个指针域的结点结构体及链表的结构进行存储。结点结构：

lchild data rchild

问题：在 n 个结点的二叉树链表中，有 n+1 个空指针域 5、遍历方案 一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作: （1）访问根结点（D）; （2）遍历该结点的左子树（L）; （3）遍历该结点的右子树（R）; 遍历方案： （三点关键：D，LR,递归） DLR：先序遍历（Preorder Traverse，亦称前序遍历） ———访问根结点、遍历左树、遍历右树。 LDR：中序遍历（Inorder Traverse） ———遍历左树、访问根结点、遍历右树。 LRD：后序遍历（Postorder Traverse） ———遍历左树、遍历右树、访问根结点。

先序遍历的结果为： A B C D E F G H K ； 中序遍历的结果为： B D C A E H G K F ； 后序遍历的结果为： D C B H K G F E A ；

表达式（a+b*(c-d)-e/f）的二叉树 构造二叉树过程 DLR：（前缀表达式、波兰式） 前缀：- + a * b - c d / e f LDR：（中缀表达式） 中缀：a + b * c - d - e / f LRD：（后缀表达式、逆波兰式） 后缀：a b c d - * + e f / -

先序遍历： ABDECFG ； 中序遍历： DBEAFCG ； 后续遍历： DEBFGCA ；

重要结论：若二叉树中各结点的值均不相同，则：由二叉树的 前序序列和中序序列 ， 或由其 其后序序列和中序序列 均能唯一地确定一棵二叉树，但由 前序序列和后序序列 却不一定能唯一地确定一棵二叉树。

问题：已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 解答： 中序，左根右：BDCEAFHG 后序，左右根：DECBHGFA

第 5 章 图

5.1图的基本概念 (1)无向图：每条边都是无方向的； (2)有向图：每条边都是有方向的；

(3)完全图：任意两个顶点上都存在一个边；

完全无向图 完全有向图 a、n 个顶点的完全无向图有 n(n-1)/2 条边； b、n 个顶点的完全有向图有 n(n-1) 条边； c、无向图 G 中顶点数为 n，则图 G 至少有 0 条边，至多有 n(n-1)/2 条边；若 G 为有向图， 则至少有 0 条边，至多有 n(n-1)/2 条边。 (5)带权图：边上带权的图；（权：具有某种含义的数值，如表示两点之间的距离）

(7)强连通图：有向图中，若任意两个顶点都存在路径可达；

(8)路径与回路 路径：顶点 A 到顶点B 的经过的所有的边； 简单路径：在一条路径中, 除起点和终点外,若其余顶点各不相同； 回路：起点和终点相同的路径； 简单回路：由简单路径组成的回路称为简单回路； (4) 子图：从图中取出的部分集合；

(6)连通图：无向图中任意两个点都存在路径可达；

(9)顶点的度：与顶点有关的边的数目； 有向图有分为出度和入度； 顶点 V 的出度=以 V 为起点有向边数； 顶点 V 的入度=以 V 为终点有向边数； 顶点 V 的度=V 的出度+V 的入度； 图的度=图中所有顶点度的和； 问题：一个图的顶点数为 n，边数为 e，则该图的度 = 2*e 。

例题：在右图所示的的无向图中； V0,V1,V2,V3 是不是简单路径? 是 V0,V1,V2,V4,V1 是不是简单路径? 不是 写出无向图的一条简单回路 V0,V1,V2,V3,V0 写出有向图的一条简单回路 V0,V2,V3,V0 (10)连通分量：在无向图中，如果从顶点 vi 到顶点 vj 有路径，则称 vi 和 vj 连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的较大连通子图称为连通分量。 在有向图中，如果对于每一对顶点 vi 和 vj，从 vi 到 vj 和从 vj 到 vi 都有路径，则称该图为强连通图； 否则，将其中的极大连通子图称为强连通分量。 5.2图的存储结构 1、邻接矩阵（数组）表示法 邻接数组表示法是以一个 n*n 的数组来表示一个具有 n 个顶点的图形。我们以数组的索引 （下标）值来表示顶点，以数组的内容之来表示顶点间边是否存在（1 表示存在， 0 表示不存在）。 例子：无向图的邻接矩阵

根据上述无向图得到邻接矩阵，可以得出如下结论： 结论 1： 无向图的邻接矩阵是对称的 ； 结论 2： 顶点 i 的度＝第 i 行 (列) 中 1 的个数 ； 注意：完全图的邻接矩阵中，对角元素为 0，其余全 1。

例子：有向图的邻接矩阵 根据上述有向图得到邻接矩阵，可以得出如下结论： 结论 1： 有向图的邻接矩阵可能是不对称的 ； 结论 2： 顶点的出度 = 第 i 行元素之和 ； 顶点的入度 = 第 i 列元素之和 ； 图的度 = 矩阵中 1 的个数 * 2 ； 结论 3： 图的存储空间占用量只与它的顶点数有关，与边数无关；适用于边稠密的图； ；

例子：带权图的邻接矩阵

邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）找顶点的邻接点等等。 邻接矩阵法缺点：n 个顶点需要 n*n 个单元存储边(弧)。 对稀疏图而言尤其浪费空间。

2、邻接（链式）表表示法 邻接链表法：以链表来记录个顶点的邻接顶点。例 1：无向图的邻接表 例 2：有向图的邻接表

例 3：网（带权图）的邻接链表表示

5.3图的遍历 从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。遍历方法： 深度优先遍历和广度优先遍历 。 1、深度优先搜索( DFS ) 基本思想：——仿树的先序遍历过程。

步骤： 1)访问起始点 v; 2)若 v 的第 1 个邻接点没访问过，深度遍历此邻接点； 3)若当前邻接点已访问过，再找 v 的第 2 个邻接点重新遍历； 例子：

DFS 搜索结果： v1,v2,v4,v8,v5,v3,v6,v7 DFS 搜索结果： v3,v2,v4,v9,v1,v6,v5,v8,v7

2、广度优先搜索( BFS ) 基本思想：——仿树的层次遍历过程。简单归纳： 1）在访问了起始点v 之后，依次访问 v 的邻接点； 2）然后再依次访问这些顶点中未被访问过的邻接点； 3）直到所有顶点都被访问过为止。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。

BFS 搜索结果： v1,v2,v3,v4,v5,v6,v7,v8 BFS 搜索结果：v3,v2,v1,v6,v4,v5,v9,v8,v7 5.4图的最小生成树 1、生成树问题 在一个含有 n 个顶点的连通图中，必能从中选出 n-1 条 边构成一个极小连通子图，它含有图中全部 n 个顶点，但只有足以构成一棵树的 n-1 条边，称这棵树为连通图的生成树。例如，对下图(a)进行深度优先搜索遍历过程中经过的边和全部顶点构成的极小连通子图(b)即

为(a)的一棵生成树。

2、最小生成树 在含有 n 个顶点的连通网中选择 n-1 条边，构成一棵极小连通子图，并使该连通子图中 n-1 条边上权值之和达到最小，则称其为连通网的最小生成树。例如，对于如图所示的连通网可以有多棵权值总和不相同的生成树。

应用： n 个城市建网，如何选择 n–1 条线路，使总费用最少？ 构造最小生成树的算法有许多，基本原则是： 尽可能选取权值最小的边，但不能构成回路； 选择 n-1 条边构成最小生成树。

（1）克鲁斯卡尔(Kruskal)算法 基本思想：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路。 具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。（归并边）

（2）普里姆(Prim)算法 普里姆算法构造最小生成树的过程是从一个顶点 U={u0}作初态，不断寻找与 U 中顶点相邻

且代价最小的边的另一个顶点，扩充到 U 集合直至U=V 为止。（归并顶点） 比较以上两种算法可见： A、Kurskal 算法主要对边进行操作，又称为“加边法”，其时间复杂度为 O(eloge)。这种方法比较适用于稀疏图。 B、Prim 算法主要对顶点进行操作，又称为“加点法”，其时间复杂度为 O(n2)。比较适用于稠密图。

5.6 图的课堂练习 【NOIP2019 提高组】8. G 是一个非连通无向图（没有重边和自环），共有 28 条边，则该图至少有（ ）个顶点 A.10 B.9 C.11 D.8 答案：B 解析：根据公式(8-1)*8/2 得到 28 条边，然后增加一个节点使其成为非连通图。

【NOIP2019 提高组】12.以下哪个结构可以用来存储图（ ） A.栈 B.二叉树 C.队列 D.邻接矩阵 答案：D 解析：邻接矩阵和邻接表可以存储图，其他三项都是数据结构，不是存储结构。

【NOIP2017 普及组】10. 设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边，才能使得 G 变成一棵树。 A. m – n + 1 B. m - n C. m + n + 1 D. n – m + 1 答案：A 解析：m-(n-1)=m-n+1

【NOIP2015 普及组】15.设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有 （ ）个顶点。 A. 10 B. 12 C. 8 D. 16 答案：D 解析： 抓住结点度数之和为边数的两倍来解题： 设顶点个数 x 个： 所以：2x=162，x=16，所以答案选：D

第 6 章 数学和逻辑

6.1组合数学基础 1、排列组合的基础知识 排列与元素的顺序有关，而组合则与元素的顺序无关 。 2、排列 Am = n! n (n − m)! 问题 1：分别从 3 个不同的乒乓球中选择 2 个乒乓球依次放在 2 个不同的盒子里，每个盒子各 1 个，求有多少种不同的选择方法？ 2  6

问题 2：分别从 6 个不同的乒乓球中选择 3 个乒乓球，依次放在 3 个不同的盒子里，每个盒子 1 个，请问有多少种放法？ 3 1 2 0

3、组合 从 n 个不同元素中取出 m（m≤n）个元素的所有组合的个数，叫做从n 个不同元素中取出 m 个元素的组合数，用符号Cm表示.

Cm = n! n m! (n − m)!

例子：计算如下算式的运算结果 （a）C4 （b）C7 （c）已知C3 = A2 ，求n 的值？ n n 答案：（a）35 （b）120 （c）8

例子：甲、乙、丙、丁 4 支足球队举行单循环赛； (1)各队要举办多少场比赛？列出所有各场比赛的双方； 答案： C2 = 6 甲乙、甲丙、甲丁、乙丙、乙丁、丙丁

(2)有多少种冠亚军的组合？列出所有冠亚军的可能情况； 答案： A2 = 12 甲乙、甲丙、甲丁、乙丙、乙丁、丙丁乙甲、丙甲、丁甲、丙乙、丁乙、丁丙

例子：一位教练的足球队共有 17 名初级学员，他们中以前没有一人参加过比赛。按照足球比赛规则，比赛时一个足球队的上场队员是 11 人； （1）这位教练从这 17 名学员中可以形成多少种学员上场方案？ 答案： C11 = 12376 （2）如果在选出 11 名上场队员时，还要确定其中的守门员，那么教练员有多少种方 式做这件事情？ 答案： C1 * C10 = 136136 17 16 C10 * C1 = 136136 17 7

例子：(1)平面内有 10 个点，以其中每 2 个点为端点的线段共有多少条？ 答案： C2 = 45

(2)平面内有 10 个点，以其中每 2 个点为端点的有向线段共有多少条？ 答案： A2 = 90

例子：(1)凸五边形有多少条对角线？ 答案： C2 - 5= 10 - 5 = 5

(2)凸 n（n>3）边形有多少条对角线？ 答案： C2 - n = (n2-3n)/2（n 点取 2 个点是所有的线 – n 条边，剩余的是对角线）

（2）解题技巧 技巧 1：相邻问题——整体捆绑法 。 例：7 名学生站成一排，甲、乙必须站在一起，有多少不同排法？ 解：两个元素排在一起的问题可用“捆绑”法解决，先将甲乙二人看作一个元素与其他五人进行排列，并考虑甲乙二人的顺序，所以共有 A(6/6) * A(2/2) =1440 种。

例：5 个男生 3 个女生排成一排，3 个女生要排在一起，有多少种不同的排法？ 解：因为女生要排在一起，所以可以将 3 个女生看成是一个人，与 5 个男生作全排列， 因此有 A(6/6) 种排法，其中女生内部也有 A(3/3) 种排法; 根据乘法原理，共有 A(3/3) * A(6/6) = 4320 种不同的排法。

技巧 2：不相邻问题——选空插入法 例：7 名学生站成一排，甲乙互不相邻，有多少不同排法？ 解：甲、乙二人不相邻的排法一般应用“插空”法，所以甲、乙二人不相邻的排法总数计算应为： A(5/5)*A(2/6) =3600 种。

例：学校组织老师学生一起看电影，同一排电影票 12 张，8 个学生，4 个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的坐法？（写出计算公式，不需要计算） 解：先排学生共有 A(8/8) 种排法，然后把老师插入学生之间的空档，共有 7 个空档可插，选其中的 4 个空档，共有 A(4/7) 种选法。根据乘法原理，共有的不同坐法 为 A(8/8) * A(4/7) = 33868800 。

技巧 3：复杂问题——总体排除法或排异法 例：正六边形的中心和顶点共7 个点，以其中3 个点为顶点的三角形共有 个。解：从 7 个点中取 3 个点的取法有 C(3/7) 种，但其中正六边形的对角线所含的中心 和顶点三点共线不能组成三角形，有 3 条，所以满足条件的三角形共有 C(3/7)-3=32 个。

例：从 43 人中任抽 5 人，正、副班长、团支部书记至少有一人在内的抽法有多少种？ 解：43 人中任抽 5 人的方法 C(5/43) 种，正副班长，团支部书记都不在内的抽法有C(5/40)种，所以正副班长，团支部书记至少有 1 人在内的抽法有 C(5/43)-C(5/40) 种。

技巧 4：特殊元素——优先考虑法 例：乒乓球队的 10 名队员中有 3 名主力队员，派 5 名队员参加比赛，3 名主力队员要安排在第一、三、五位置，其余 7 名队员选 2 名安排在第二、四位置，那么不同的出场安排共有 种。

解：由于第一、三、五位置特殊，只能安排主力队员，有 A3/3 种排法，而其余 7 名队员选出 2 名安排在第二、四位置，有 A2/7 种排法，所以不同的出场安排共有A3/3*A2/7=252 种。

技巧 5：多元问题——分类讨论法 例：某班新年联欢会原定的 5 个节目已排成节目单，开演前又增加了两个新节目；如果将这两个节目插入原节目单中，那么不同插法的种数为 。 解：增加的两个新节目，可分为相邻与不相邻两种情况 (1) 不相邻：共有 A2/6 种； (2) 相邻：共有 A2/2*A1/6 种。故不同插法的种数为： 30+12=42 ； 该题的另外一个解法为： (1)7 个节目的总排法为 A(7/7) ； (2)但其中 5 个节目是预先排好的，排法为 A(5/5) ； (3)那么剩余的 2 个节目的排法就要去掉这个重复的 5 个节目的排法，结果为 A(7/7) / A(5/5) = 7 * 6 = 42 ；

技巧 6：混合问题——先选后排法 例：从黄瓜、白菜、油菜、扁豆 4 种蔬菜品种中选出 3 种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有 种。 解：先选后排，分步实施。由题意，不同的选法有 C(2/3) 种，不同的排法有 A (3/3) 故不同的种植方法共有 C(2/3)*A(3/3)=18 。

技巧 7：相同元素分配——档板分隔法 例：把 10 本相同的书发给编号为 1，2，3 的三个学生阅览室，每个阅览室分得的书的本数不小于其编号数，试求不同分法的种数有 种。 解：先分别给 1、2、3 号阅览室分配 0、1、2 本书，然后把剩下的 7 本书分配给这 3 个阅览室，要求每个阅览室至少再分到 1 本。那么在 7 本书中有 6 个空，任意选取 2 个空，就可以把这 7 本书分成左、中、右 3 个部分，分别分给 3 个图书室，所以不同的分法共有 C2/6 ＝15 。

技巧 8：转化法 例： 高二年级 8 个班，组织一个 12 个人的年级学生分会，每班要求至少 1 人，名额分配方案有 种？ 转化法：对于某些较复杂的或较抽象的排列组合问题，可以利用转化思想，将其化归为简单的、具体的问题来求解。 解：此题若直接去考虑的话，就会比较复杂。但如果我们将其转化为等价的其他问题， 就会显得比较清楚，方法简单，结果容易理解。此题可以转化为：插板问题，结果为C7/11=330 。

5、关于排列组合问题的小结 一、分清排列（先取再排）和组合（只取不排）

注：按指定的一种顺序排列的问题，实质是组合问题二、基本的解题方法 ⑴ 特优法：优先处理特殊元素（位置）法； ⑵ 捆绑法：某些元素要求必须相邻时，可以先将这些元素看作一个元素，与其他元素排列后，再考虑相邻元素的内部排列。 ⑶ 插空法：某些元素不相邻排列时，可以先排其他元素，再将这些不相邻元素插入空挡。 ⑷ 对于含“至多”、“至少”的问题，宜用排除法或分类解决； 涉及“多面手”的问题，一般分类解决。 C m C m  C m

(5) 不同元素的均匀分组：将mn 个不同元素均匀分成n 组，有种分法； ⑹ 挡板法：相同元素分配问题

mn

Cm1

( n -1) m m m m

将n 个相同元素分给m 个不同单位，每个单位至少一个元素，有 n1 种分法；

6.2常用的原理小结 1、容斥原理 容斥原理是在计数时，必须确保没有重复，没有遗漏，使重叠部分不被重复计算。基本思想是： 1、先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来； 2、然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复。 如果被计数的事物有 A、B、C 三类，那么，A 类和B 类和 C 类元素个数总和= A 类元素 个数+ B 类元素个数+C 类元素个数—既是 A 类又是 B 类的元素个数—既是 A 类又是 C 类的元素个数—既是 B 类又是C 类的元素个数+既是 A 类又是 B 类而且是 C 类的元素个数。 （A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C）。

例如：一次期末考试，某班有 15 人数学得满分，有 12 人语文得满分，并且有 4 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？ 答案：23。 解析：被计数的事物有语、数得满分两类，“数学得满分”称为“A 类元素”，“语文得满分”称为“B 类元素”，“语、数都是满分”称为“既是 A 类又是 B 类的元素”，“至少有一门得满分的同学”称为“A 类和B 类元素个数”的总和。为 15+12-4=23。

【NOIP2018 普及组】13. 10000 以内，与 10000 互质的正整数有（ ）个。A. 2000 B. 4000 C. 6000 D.8000 答案：B 互质的意思，与 10000 没有公约数，即不能被 10000 的质因子整除。10000 分解质因子：10000 =2222555*5

10000 以内被 2 整除的数有 5000 个 10000 以内被 5 整除的数有 2000 个 两者存在重复计算的数，即被 10 整除的数，有 1000 个。 被 2 或 5 整除的数有：5000 +2000 – 1000 =6000 互质的数有：10000 - 6000 ＝ 4000 个

2、鸽巢原理/抽屉原理 桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有 n+1 个元素放到 n 个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。 抽屉原理的另一个表达：如果有 n 个集合和 kn+1 个元素，将元素放入集合中之后，至少有 1 个集合中有 k+1 个元素。 运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。

例子：属相是有 12 个，那么任意 37 个人中，一个属相至少不少于多少个人。答案：4 人。 分析：这时将属相看成 12 个抽屉，则一个抽屉中有 37/12，即 3 余 1，余数不考虑，而向上考虑取整数，所以这里是 3+1=4 个人，但这里需要注意的是，前面的余数 1 和这里加上的1 是不一样的。（思考 38 个人的情况）

【NOIP2019 普及组】12.一副纸牌除掉大小王有 52 张牌，四种花色，每种花色 13 张。假设从这 52 张牌中随机抽取 13 张纸牌,则至少（ ）张牌的花色一致。 A.4 B.2 C.3 D.5 答案：A 解析：抽屉原理，最坏情况,13 张牌对应四种花色的牌数为 3、3、3、4。抽屉存储：黑桃黑桃黑桃，抽屉 2：红桃红桃红桃，抽屉 3：梅花梅花梅花，抽屉 4：方片方片方片 这时再抽一张，不管放在哪，都能满足要求。

6.3逻辑 1.今天是星期日，那么 100 天以后是星期几？ 解析： 本题是周期性问题求解，每周有 7 天； 那么 100 天除去完整的 7 天周期以外，剩余填数 = 100 % 7 = 2（14 个完整周期剩余2 天）； 因此 100 天以后是星期几，相当于 2 天之后是星期几，答案是星期二。

2、今天是星期日，那么 10100 天以后是星期几？

解析： 我们并不急于求出 10100,而是像 1,10,100,100,10000…这样,依次增加 0 的个数, 观察其规律。 0 的个数 0 1 天以后的星期数 1÷7=0 余 1 -> 一 1 10 天以后的星期数 10÷7=1 余 3 -> 三 2 100 天以后的星期数 100÷7=14 余 2 -> 二 3 1000 天以后的星期数 1000÷7=142 余 6 -> 六 4 10000 天以后的星期数 10000÷7=1428 余 4 -> 四 5 100000 天以后的星期数 100000÷7=14285 余 5 -> 五 6 1000000 天以后的星期数 1000000÷7=142857 余 1 -> 一 7 10000000 天以后的星期数 10000000÷7=1428571 余 3 -> 三 8 100000000 天以后的星期数 100000000÷7=14285714 余 2 -> 二 9 1000000000 天以后的星期数 1000000000÷7=142857142 余 6 -> 六 10 10000000000 天以后的星期数 10000000000÷7=1428571428 余 4 -> 四 11 100000000000 天以后的星期数 100000000000÷7=14285714285 余 5-> 五 12 1000000000000 天以后的星期数 1000000000000÷7=142857142857 余 1->一 因此 10100 以后的星期数，可以将天数中的 0 的个数（10100 有 100 个 0）除以 6，通过所得余数来判断。 100 ÷ 6 = 16 余 4 因此，10100 天以后是星期四。

3. 2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（ ）。 A. 星期三 B. 星期日 C. 星期五 D. 星期二解析： 闰年：一年 366 天，非闰年：一年 365 天。 判断标准：四年一闰,百年不闰,四百年再闰（n%4==0&&n%100!=0 ||n % 400 == 0） 意思是：不是整百的年份只要被 4 整除的就是闰年,整百的年份必须得被 400 整除才是 闰年 1999 年~2016 年中的闰年有：2000、2004、2008、2012、2016，5 个闰年。 也就是说 1999 年 10 月 1 日~2017 年 10 月 1 日总天数 = 18 年，总天数 = 18 * 365 + 5 = 6575 天。6575/7 结果为 939 周余 2 天。 说明：1999 年 10 月 1 日为周五。

4.一个人站在坐标（0, 0）处，面朝 x 轴正方向。第一轮，他向前走 1 单位距离，然后右转；第二轮，他向前走 2 单位距离，然后右转；第三轮，他向前走 3 单位距离，然后 右转……他一直这么走下去。请问第 2017 轮后，他的坐标是：（ ， ）。 （请在答题纸上用逗号隔开两空答案）

答：1009,1008 解析：找规律，每一个循环有 4 个动作，上、下、左、右！ 初始值为 0,0，不看坐标的值，看坐标的变化； 第 1 循环 第 2 循环

变化 变化

可以看出，每一循环的 x 和 y 的变化幅度一定是相同的，由此可以直接计算出第 1 循环结束，坐标为-2,2 第 2 循环结束，坐标为-4,4 2017 次走完时，经过了 2017/4=504 次循环，余数为 1，说明是 504 次循环+1 次。 504 次循环结束，坐标应当为：504*-2，5042，也就是-1008,1008 第 504 次循环结束值到了 5044=2016，下一个数是 2017，也就是下一步为+2017,0 坐标变化为 1009,1008。

10.周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责 切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜 10 分钟，然后切 菜 10 分钟，最后炒 菜 10 分钟。那么做一道菜需要 30 分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（ ）分钟。 A. 90 B. 60 C. 50 D. 40 答案：C 解析： 10 20 30 40 50 60 70 80 90

洗 1 2 3 切 1 2 3 炒 1 2 3