CSP-J初赛备考指南

· · 算法·理论

CSP-J初赛备考指南

（更新中）

最近更新：2025/09/19。

前言

本指南可在手机上查看，需要在微信里给文件传输助手发送网址https://www.luogu.com.cn/article/4iso5uyb ，点进去即可查看。

别看着字多，实际上内容并不多，如果你学过编程，那么里面学过的东西就可以跳过了。每个内容前都有重要程度，请选择性地使用本指南。

初赛会的就做，不会就蒙。备考可以多做历年真题。下面的不一定全面，但最起码能拿到一半分。

本指南以第一大题为主（15个单项选择题，30分）。

第一大题主要考察：计算机基础知识、进制与位运算、简单数据结构（线性表、树、图）、数论基础（排列与组合等）、简单算法等。

剩下的第二、三大题是阅读程序和完善程序，就看平时算法的积累了！（递归（重要！）、贪心、二分、图论、搜索、动态规划dp……）。这些算法可以在洛谷题单（点这里）中训练，后面也会有所提及。

历年真题（洛谷上）：点这里训练。

CSP-J大纲：点这里。

网上也有视频：网上的视频

通过初赛后，推荐复赛的教材：《深入浅出程序设计算法竞赛（基础篇）》（来找我借就行）。

第一章   单项选择题

（15题，30分）

单项选择题纯粹就是对基础知识的考察，主要包括：计算机基础知识、进制与位运算、数据结构（线性表、树、图）、排列与组合等。

做题技巧：认真计算，仔细审题，不会就蒙。

第一节   计算机基础知识

一、计算机基本内容

了解即可，稍加记忆【2】

（一）基础

另外需要了解NOI系列赛事(来自noi官网)：

计算机网络：连接分散计算机设备及通信设备（通过通信线路）以实现信息传递的系统。
分类：局域网（LAN）、城域网（MAN）、广域网（WAN）和互联网。

…………………………………………………………

（二）工作原理

推荐一篇文章： 点这里详细了解

计算机是一种根据指令操作数据的机器，主要由处理器与存储器两部分组成。

Windows、Linux、iOS，这些都是计算机操作系统。如果让你直接操作硬件，你肯定不会操作，但是操作系统把操作指令都封装好了，你就可以直接通过操作系统来使用电脑。

（1）计算机及工作原理

1、（2020）在内存储器中每个存储单元都被赋予一个唯一的序号，称为（ ）。
A.地址 B.序号 C.下标 D.编号

2、（2020）编译器的主要功能是（ ）。
A.将源程序翻译成机器指令代码
B.将源程序重新组合
C.将低级语言翻译成高级语言
D.将一种高级语言翻译成另一种高级语言

3、（2018）以下哪一种设备属于输出设备（ ）。
A. 扫描仪
B. 键盘
C. 鼠标
D. 打印机

4、（2018）广域网的英文缩写是（ ）
A. LAN—— B. WAN—— C. MAN—— D. LNA

5、下面的哪一个不是操作系统名字？（ ）
A. Notepad—— B. Linux—— C. Windows—— D. macOS

答案（点击查看）

二、计算机的存储

重要内容【3】

计算机里的数据都是通过二进制串存储的。计算机里面的电路，只能表示高电压（1）和低电压（0），因此用只含0和1的二进制来表示。

KB：1KB=1024B

MB：1MB=1024KB

GB：1GB=1024MB

再比如常见的数据类型，它们的存储长度有长有短：

（2）计算机存储

1、（2019）一个32 位整型变量占用（）个字节。
A.32
B.128
C.4
D.8

2、（2021）目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。
A. 二进制
B. 十进制
C. 八进制
D. 十六进制

3、（2020）现有一张分辨率为2048×1024 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）。
A. 16MB
B. 4MB
C. 8MB
D. 2MB

4、（2024） 1KB 为 1024 字节（byte），1MB 为 1024KB，那么 1MB 是多少二进制位（bit）？（ ）
A. 1000000
B. 1048576
C. 8000000
D. 8388608

5、（2018）1MB等于（）
A、1000字节
B、1024字节
C、1000×1000字节
D、1024×1024字节

6、（2017）分辨率为 800×600、16 位色的位图，存储图像信息所需的空间为（ ）。
A.937.5 KB
B.4218.75 KB
C.4320 KB
D.2880 KB

答案（点击查看）

三、计算机语言

了解即可，应该不考，记住语言的类型【1】。

计算机的语言有高级、低级之分。我们学习C++的是高级语言，是面向任务的；还有一些低级语言，如汇编语言，直接面向机器。而高级语言大体分为两类：

1、面向过程（C语言）

就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。

2、面向对象（C++,Java） 是把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描述某个事物在整个解决问题的步骤中的行为。

面向对象程序设计中的概念主要包括：对象、类、数据抽象、继承、动态绑定、数据封装、多态性、消息传递。

（3）编程语言

1、（2021）以下不属于面向对象程序设计语言的是（   ）。
A.C++     B.Python     C.Java     D.C

2、（2022）以下哪种功能没有涉及C++语言的面向对象特性支持：（   ）。
A、C++中调用printf函数
B、C++中调用用户定义的类成员函数
C、C++中构造一个class或struct
D、C++中构造来源于同一基类的多个派生类

答案（点击查看）

四、C++基础

这些只要你学过几天C++基本上就会做了。因此直接给一组题，也不再讲解了。

（4）C++基础

1、（2024）以下哪个不是 C++ 中的基本数据类型？（ ）
A. int—— B. float—— C. struct—— D. char

2、以下哪个不是 C++ 中的循环语句？（ ）
A. for—— B. while—— C. do-while—— D. repeat-until

3、在 C/C++ 中，(char)('a' + 13) 与下面的哪一个值相等？（ ）
A. 'm'—— B. 'n'—— C. 'z'—— D. 'l'

4、（2023）在 C++ 中，下面哪个关键字用于声明一个变量， 其值不能被修改?
A. unsigned—— B. const—— C. static—— D. mutable

5、(2019)若有如下程序段，其中 s、a、b、c 均已定义为整型变量,且 a、c 均已赋值（c 大于 0）

s = a;
for （b = 1; b <= c; b++） s = s - 1;

则与上述程序段功能等价的赋值语句是（）
A.s = a - c;
B. s = a - b;
C.s = s - c;
D. s = b - c;

答案：点击查看

第二节 进制与位运算

这一部分主要研究二进制的原理、性质，属于数论范畴。

一、二进制位运算

重中之重！！ 【4】

二进制就是逢2进1，每一位上只有0或1，比如 0000 0001 就是一个二进制串，一个二进制串通常写作8位，即一个字节。计算机常用二进制，是因为在计算机电路中，高电压可以表示1，低电压可以表示0，因此二进制便于计算机进行表示。在二进制串中，0表示false（假），1表示true（真）。

位运算，就是对于二进制串的运算，可以是一个二进制串（取反），也可以是两个（与、或、非）。

1、两个二进制串进行位运算：

就像列竖式一样，两个二进制串进行位运算（与、或、异或）时，两个二进制串右端对齐，每一位上分别进行运算。 运算规则如下：

2、一个二进制串进行位运算：

位运算举例：

1101 \& 1011=1001 1101$ | $1000=1101 1101$ ^ $1011=0110 !1001=0110 0010<<2=1000 0100>>2=0001

注意区分逻辑运算与位运算。它们运算方式类似，含义不同。
比如：&&是逻辑与，针对两个逻辑表达式，两个表达式同真为真，有假为假，例如(1>0)&&(2>1)为真，(1<0)&&(2>1)为假。&是按位与，针对二进制，两个二进制位同1为1，否则为0。

二、进制

重中之重！！！【5】

（一）定义

N进制就是逢N进1，显然每一位上的数最大为(N-1)。
目前人类常用的是十进制，计算机常用二进制。此外常见的还有八进制、十六进制。

N进制的表示：(a)_N，比如十进制的12345表示为(12345)_{10}。
另外，如果当前数位上的数字超过10而不进位（比如十六进制可能出现），那么10表示为A，11表示为B，12表示为C，以此类推。比如(10)_{10}就是(A)_{16}。

在计算机中，我们的二进制串常写成八位，即一个字节。一个字节的数值表示范围是-128到127，下面会讲到。
比如表示5，5的二进制数是101，那么就补足空位，表示为0000 0101。

其他进制的加减乘除运算与十进制是相似的。点这里了解更多。

比如要求 0000 1001 + 0001 0011 ：

…………………………………………………………

（二）进制的转换与表示

由于我们常用十进制，因此我们一般的转换基本都是把N进制转为十进制、十进制转为N进制。如果两种别的进制进行转化，比如二进制转八进制，那么可以先把二进制转为十进制，再把十进制转为八进制（网上也有直接转换的方法，可以自行查询）。

下面将以二进制转十进制（简称“二转十”）、十进制转二进制（简称“十转二”）为例，来介绍具体方法。

1、二进制转十进制
先来回忆一下十进制数的构成。比如十进制下123，可以分成1个百(10^2)、2个十(10^1)、3个一(10^0)，也就是 1*10^2+2*10^1+3*10^0=100+20+3=123。
二进制也是如此。比如(1001101)_2，就可以表示为下图：

因此，(01001101)_2就是

0*2^7+1*2^6+0*2^5+0*2^4+1*2^3+1*2^2+0*2^1+1*2^0 = 0+64+0+0+8+4+0+1 另外，可以引入一个定义：“权”： 指当前位是从右往左第几位（从0开始）。比如 100 1101 每一位对应的权值分别是6,5,4,3,2,1,0。二转十就是 每一位的数字 乘以2的权值次方 再求和。 如果是N进制转十进制，只需要改成N的权值次方就可以。

…………………………………………………………

2、十进制转二进制
结合下面的计算过程来理解：

计算过程是：最开始数字为给定的数。每次把当前数除以2，余数写在一边，除得的商成为当前数，继续重复这个过程，直到得到当前数为0时停止。此时，把得到的余数倒着写出来，得到的01串就是二进制数。

如果是十进制转N进制，把除数改为N即可。

如果我们从下面往上看我们刚写出的式子，发现了吗？整个过程就是把二转十的过程倒过来。（对这个过程的更深理解 点这里）

程序练习：B3619（10转x）、B3620（x转10），参考代码 点这里。

…………………………………………………………

3、小数的二进制

小数的二进制转化与整数十分相似。

（1）小数的二转十
还是以小数的构成来介绍。比如十进制的 12.1234，其实就是 整数部分的12，加上小数部分的0.1234=1*0.1+2*0.01+3*0.001+40.0001 =$110^{-1}+210^{-2}+310^{-3}+410^{-4}。 二进制也同理，以二进制的101.101为例，整数部分的101就是十进制2^2+2^0=5，小数部分的101就是十进制的12^{-1}+02^{-2}+12^{-3}=\frac{1}{2^1}+\frac{1}{2^3}=\frac{1}{2}+\frac{1}{8}=0.5+0.125=0.625，整体就是5+0.625=5.625$。

（2）小数的十转二

小数部分的计算方法是：把小数部分的数每次乘2，得到的数舍去整数部分，小数部分继续乘2。最终的结果就是每次乘2之后的整数部分。

（其实也是用短除法，只不过是除以\frac{1}{2}，就相当于乘2。）

…………………………………………………………

4、负数的二进制

二进制表示负数有三种方式：

简化一下，负数补码就是：首位变为1，其余位取反，再加1。

注意：在取反码时：①符号位（首位）千万不要取反。正数首位一定为0，负数首位一定为1。②注意是取反，每一位1变0、0变1，不是前后颠倒。

计算机的负数是用补码表示的，原码和反码无法计算正确结果。

另外，正数和0的原码、反码、补码都是二进制串本身，不发生变化。

举例：-5表示方法：十进制的5是二进制的101，补全得 0000 0101，符号位为1，原码就是 1000 0101。取反后，反码是 1111 1010。加一，得补码 1111 1011。所以-5的二进制就是 1111 1011。
反过来也要会，比如补码 1111 1011，先转成反码（减去1），1111 1010，再转成原码（除了首位都取反），1000 0101 ，就是负的101即十进制的-5。

_

初赛会用就行，也不用理解原理。原理1：（点击蓝字查看原理）。也有一种理解方法：在钟表上，往前拨3小时和往后拨9个小时是一样的。（原理2 点击蓝字查看。）

在计算机的CPU中只有加法器，因此要想计算a-b，就转化成a+(-b)。

拓展问题：（点击查看） 。

（5）（二进制和位运算）

1、（2019）二进制数 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

2、（2020）二进制数 1011 转换成十进制数是（ ）。
A. 11 —— B. 10 —— C. 13 —— D. 12

3、（2021）二进制数 101.11 对应的十进制数是（ ）。
A. 6.5 —— B. 5.5 —— C. 5.75 —— D. 5.25

4、（2022）八进制数 32.1 对应的十进制数是（ ）。
A. 24.125—— B. 24.250—— C. 26.125—— D. 26.250

5、（2023）八进制数 12345670_8 和 07654321_8 的和为 （ ）
A. 22222221_8
B. 21111111_8
C. 22111111_8
D. 22222211_8

6、（2023）数 1010102_2 与 166_8 的和为（ ）
A、(10110000)_2
B、(236)_8
C、(158)_{10}
D、(A0)_{16}

7、设 x=true,y=true,z=false，以下逻辑运算表达式值为真的是（ ）。
A. (y∨z)∧x∧z
B. x∧(z∨y) ∧z
C. (x∧y) ∧z
D. (x∧y)∨(z∨x)

8、（2018）下列四个不同进制的数中，与其它三项数值上不相等的是
A.(269)_{16}—— B. (617)_{10}
C. (1151)_8——D. (1001101011)_2

9、（2024）以下哪个序列对应数字0至8的四位格雷码？
A.0000,0001,0011,0010,0110,0111,0101,1000
B.0000,0001,0011,0010,0110,0111,0100,0101
C.0000,0001,0011,0010,0100,0101,0111,0110
D.0000,0001,0011,0010,0110,0111,0101,0100
注：在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。

10.（2024）计算(14_8-1010_2)*D_{16}-1101_2的结果，并选择答案的十进制值
A.13——B.14——C.15——D.16

答案（点击查看）

第三节 简单数据结构

数组存储数据的特点是存储、修改、查询方便，但插入困难；链表则是查询困难、插入方便……不同的数据结构具有不同的特点，在特定的题里要合适地选用。
初赛里对数据结构的考察很浅，只是考了一下各种数据结构的性质；而复赛就要考写法、用法。

一、数据的存储与指针的使用（选读）

选读部分，仅帮助读者理解。初赛复赛都不会考得太详细。

（一）数据的存储

每一个数据，要存储在内存里，就要开辟一定的空间。内存的空间很多，我们将其分开，每8位为一个字节（1B，即1Byte），每一个字节都对应一个内存地址。就好比说，你是一个char型数据（长1字节），住在酒店的房间里，你这个房间的大小是一字节，对应一个门牌号码（就是地址）。

在一个32位计算机中，内存地址（“门牌号”）是一个32位的二进制数，可以缩写为一个8位16进制数。十六进制数前常会加上“0x”作为提示。比如，“0x0000107F”就可以是一个地址。

定义一个变量，就会为这个变量准备一块内存空间，并记录它的起始地址。当再次需要访问时，就可以根据地址找到这个变量的值。

我们定义一个int型变量a，那么&a就可以返回它的地址。对于一个int型变量，它的长度是四字节，返回的是第一个字节的地址。

对于数组，一个数组会有多个元素，这些元素的地址是连续的。

（二）指针

指针变量是一种专门用来存储内存地址的变量，其值为另一个变量的地址（一个十六进制串）。
声明一个指针数组：int *p；声明了一个指针p，它指向一个int型变量。
p=&a; 指针p指向int型变量a。
此时输出p，得到的就是a的地址。
*p返回的是指针p指向的那个变量的值。

数组名其实也是指针，它指向数组的首位。如，int arr[5]; arr=&arr[0]。

指针也可以进行运算。p+n表示指针p从当前位置向后移动n*sizeof(数据类型)个字节。比如int型下，p++就是向后移动四个字节。

了解到这即可。

二、线性表（链表、队列、栈等等）

重中之重！！【4】

（一）数组

首先回顾一下数组的知识：数组的每一个空间都用下标来标记。下标从0开始，因此一个长度为n的数组，最末项的下标是n-1，不要出错。
这一部分属于是基础了，因此接下来我们讨论一种不一样的数组：这个数组没有固定的长度，可以自动改变其长度，叫做可变长度数组（vector）。具体用法如下：

（1）vector<int> v; 定义一个目前长度为0的int型可变长度数组v，你可以改变类型和数组名。也可以用vector<int> v(n,i);表示这个数组初始长度为n，每个元素初始化为i。
（2）v.push_back(a);将元素a插入到数组v的末尾并增加数组长度。
（3）v.size() 返回v的长度 。
（4）v.resize(n,m);重新调整数组长度为n，如果n比原来小，删除多余信息，如果n比原来大，那么新增部分初始化为m。
（5）v[i]访问第i个元素，类似于数组。
（6）二维可变长度数组：vector<int> v[10] 或 vector< vector<int> > v。

（二）链表

我们在排队时，如果每一个人都记住自己前一个人、后一个人是谁，那么解散后很容易再次排好序。我们脑中存储的是自己、前一个人、后一个人。这样的，每个元素存储数值、前驱（即上一个元素）、后继（即下一个元素）的数据结构，我们叫它链表。

链表分为单链表与双链表，除数据外，单链表只存放当前节点的后继或前驱中的一个，而双链表两者都存放。一般来说，链表最后一个节点（tail）的后继（nex）、第一个节点的前驱(pre)指向空（NULL）；而如果tail.nex->head，head.pre->tail，那么这个链表称为循环链表。
一般链表具有头指针head、尾指针tail，指向首和尾，因此如果要把第一项踢出链表，head后移即可（head=a[head].nex）。

下图是3条简单的链表。

链表常考的是插入与删除。

（1）插入：如果我们要在点[a]后插入一点[b]，那么怎么操作呢？因为[a].nex会变化，因此可以先弄pre。以下[a]表示结点a
首先开辟[b]的空间。

然后，改变pre。[b].pre=a , [a.nex].pre=b。

随后，改变nex。[b].nex=[a].nex , [a].nex=[b]

归纳一下：[b].pre=[a] , [a.nex].pre=[b]，[b].nex=[a].nex , [a].nex=[b]。

（2）删除：也同理。要删除结点[a]，做法就是: [a.pre].nex=[a].nex , [a.nex].pre=[a].pre。自己画图理解。

（3）如果是添加/删除首或尾：只需要改变首/尾指针的指向。画图理解。

这样的话，链表的复杂度：插入删除O(1) 、查找 O(n)。

……………………………………………………………………

（三）栈（先进后出）和队列（先进先出）

在此我们也是只了解它们的性质，写法到复赛再考。

1、栈（stack）：
就像我们洗盘子一样，先摞在下面的最后洗，最后摞在上面的会第一个洗。
栈就是这样的数据结构，它的特点是先进后出（LIFO）。它是一种特殊的线性表，其中只允许在固定的一端进行插入（入栈）和删除（出栈）元素的操作。栈的最顶端叫做栈顶，栈的操作有入栈(push)、出栈(pop)等。
栈有STL模板stack，操作有：
1、生成：stack<int> s;建立一个int型的栈s。
2、s.size() 返回栈的元素个数；s.empty()判断栈是否为空。
3、栈顶：s.top()返回栈顶数值； s.pop()将栈顶弹出。

当然，也可以自己写一个栈，定义一个数组stack，以及一个“指针”top，存储当前的栈顶。一开始top=0，随后加入一个元素a，操作为 stack[++top]=a。

………………………………

2、队列（queue）：
很好理解，就像排队付款，你越站在队列前面，就越早付款。因此，队列是一种先进先出（FIFO）的数据结构。队列只能在两端进行操作，如：弹出或访问队首、压入元素到队尾。
队列有个STL模板queue，操作有： 1、建立：queue<int> q;
2、q.size()队列长度， q.empty()是否为空
3、队首：q.front()查询队首，返回队首的值； q.pop();弹出队首。
4、队尾：q.push(a);入队（将元素a压入到队尾）。 q.back()返回队尾元素。

图中操作对应代码：

queue<int> q;
int a,b,c,d;

q.push(a);
q.push(b);
q.push(c);

q.pop();

q.push(d);

q.pop();q.pop();q.pop();

（6）

1、（2023）假设有一个链表的节点定义如下： 

struct Node { int data; Node* next; }

现在有一个指向链表头部的指针：Node* head 。如果想要在链表中插入一个新节点，其成员 data 的值为 42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;
（注：该题中用到了指针。类型名* 指针名 = new 类型名可理解为声明一个该类型的指针，->表示指向结构体成员。）

2、（2022）以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。
A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C.s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

3、（2022）对假设栈 S 和队列 Q的初始状态为空。存在e_1∼e_6六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e_1,e_2,e_3,e_4,e_5,e_6 进栈，队列 Q 依次有数据e_2,e_4,e_3,e_6,e_5,e_1出队列。则栈 S的容量至少是（ ）个数据。
A、2 —— B、3 —— C、4 —— D、6

4、（2021）对于入栈顺序为a,b,c,d,e的序列，下列（ ）不是合法的出栈序列。
A. a,b,c,d,e
B. e,d,c,b,a
C. b,a,c,d,e
D. c,d,a,e,b

5、（2019）链表不具有的特点是（）。
A. 可随机访问任一元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比

6、（2020、2018）下图中所使用的数据结构是（ )。

A. 栈—— B. 队列—— C. 二叉树—— D. 哈希表

答案（点击查看）

三、树

树和图可以算是最难的部分了。

1、一般的树和树形结构

树这种数据结构就类似于一棵真的树。有几个必须掌握的概念，结合下图来理解：

这部分不是重点，作为下面二叉树的铺垫，了解即可。

…………………………………………………………………………………………

2、二叉树（BT）

这部分是重点。

（1）二叉树

二叉树是树形结构，但不是树，它允许空二叉树的存在。二叉树是指度为2的树，即每个节点最多有2个孩子。它的孩子分为左孩子、右孩子，孩子们构成左子树、右子树，左孩子（和左子树）、右孩子（和右子树）可以为空。

还是拿图举例，B的左孩子是D、右孩子是E，G左孩子是L、没有右孩子。

……………………………………………………………………

（2）二叉树的遍历

遍历就是按一定的顺序，把二叉树的所有结点枚举一遍。分以下三种：

视频讲解（先序和中序，自己理解后序）

……………………

给出中序+后序=唯一结构，给出中序＋先序=唯一结构。

一起来解下面的题目。
例题：已知先序为ABCDEFG，中序为CBEDAFG，求后序遍历？

逐步分解来求。

  1. 找出总的根节点。先序为A BCDE FG，中序为CBED A FG。
  2. 找出左子树的根节点。先序 B C DE，中序 C B ED，根节点是B。然后继续分解下去，左子树确定是C，得到图（2）。
    右子树：先序 D E，中序 E D，根节点D、左子树E、右子树空，得到图（3）。
  3. 找出右子树根节点。先序 F G ，中序 F G，根节点是F，左子树为空，右子树G，得到图（4）。
  4. 至此，后序遍历就显而易见：CEDBGFA。

下面的一道编程题可以帮你更好地理解这个过程：P1030 求先序排列。参考代码：参考代码

………………………………………………………………………………………

（3）二叉树的类型

二叉树分为下面几种类型：

拓展——深入理解二叉树的几个性质

1> 在二叉树的第 i 层上至多有 2^{i-1} 个结点。
很明显，第一行最多有1个结点（2^0），以后每一行最多是前一行的两倍。

2> 深度为k的二叉树至多有 2^k-1 个结点。
很明显，结点最多的就是满二叉树。

3> 具有n个结点的完全二叉树，深度为floor(log_2n)+1。
涉及对数的知识（我不会证），先不给出证明了。用到的知识是深度为k的完全二叉树最多有2^k-1个结点。

4> 对任意一棵二叉树，如果其叶节点数为n_0，度为2的结点数为n_2，则一定满足：n_2=n_0+1。
证明：结点数n=n_0+n_1+n_2 ①，

…………………………………………………………………………………………

3、树形结构的应用

必须要会哈夫曼编码和表达式树，必考，4分！

（1）二叉搜索树

挂个链接：二叉搜索树（来自网络）。

（2）哈夫曼编码

在此，我们不深究原理，只了解方法即可。

我们要表示一串字母，通常需要用多个字节。如果一篇文章只由字母A、B、C、D、E组成，我们能不能利用一种特别的方式来进行编码，减小它们的长度？这便是我们要介绍的哈夫曼编码。它是一种0/1编码。

方法：比如说，每个字母的出现次数如下：A:10 B:20 C:15 D:13 E:9。我们一定会让出现频率高的字母对应的编码长度尽可能短，从短到长依次为BCDAE，那么我们能不能就直接对应地编为0,1,00,01,10呢？显然是不行的，这样会出现歧义，比如001，到底是0/01还是00/1，我们无法确定。
我们的目的就是要让一个字母的编码不能是另一个编码的前缀，比如001就包含00，这是不可以的。现在我们来介绍一种方法：哈夫曼编码。

先把上面的字母按出现频率排一下序：BCDAE。
我们可以优先考虑BCD，把BCD放在同一层，然后才是AE。具体操作如下：再二分一下，BC分一个子树，D和判断(A/E)分一个子树。以此类推，下一层就是AE的子树。得到图片中的树。然后左边标号0，右边标号1，这样就得到所有编号。运用的思想是贪心的思想。

………………

（3）表达式树（利用树的遍历）

以下的表达式指的都是双目运算符（参与运算的数有两个）。

我们日常使用的表达式，名叫中缀表达式，意思是运算符号在中间，而参与运算的数在两边，比如1 + 2。而如果把符号提前，+ 1 2就叫前缀表达式。同理，1 2 +就叫后缀表达式。

观察下图，这是一个由1，2和+构成的二叉树。那么分别写出它的先序、中序、后序遍历，有什么发现？

这就是一棵表达式树。表达式树的先序遍历就是前缀表达式，中序遍历是中缀表达式，后序遍历就是后缀表达式。

来一个比较复杂的：

前缀：+ (* (- 11 4) 5 ) (/ 1 4)
中缀：((11 - 4) * 5) + (1 / 4)
后缀：((11 4 -) 5 *) (1 4 /) +

如果给你一个前/中/后缀表达式，你要能画出表达式树，并把它表示成别的表达式。

（7）

注意：做题的时候有个挺重要的公式：

\sum_{k=0}^nx^k=\frac{x^{n+1}-1}{x-1}

意思是：x^0+x^1+...+x^{n-1}+x^n=\frac{x^{n+1}-1}{x-1}。

1、（2018）根节点深度为 0，一棵深度为 h 的满k(k>1) 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（ ）个结点。
A.\frac{k^{h+1}-1}{k-1}

B.k^{h-1}

C.k^h

D.\frac{k^{h-1}}{k-1}

2、（2022）对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、 是运算符。
A. `+a-bcd B.+a-bcd C.abc-d+ D.abc-+d`

3、（2022）假设字母表 {a,b,c,d,e} 在字符串出现的频率分别为 10\%，15\%，30\%，16\%，29\%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度（ ）位。
A. 1
B. 2
C. 2 或 3
D. 3

4、（2022）一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
A. 8、18
B. 10、18
C. 8、19
D. 10、19

5、（2021）如果一棵二叉树只有根结点，那么这棵二叉树高度为 1。请问高度为 5 的完全二叉树有 （ ）种不同的形态？
A. 16
B. 15
C. 17
D. 32

6、（2019）一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为

$i$，则其左孩子位于下标 $2i$ 处、右孩子位于下标 $2i+1$ 处），则该数组的最大下标至少为（）。 ![](https://cdn.luogu.com.cn/upload/image_hosting/7d58dfs8.png?x-oss-process=image/resize,m_lfit,h_170,w_225) A. 6 —— B. 10 —— C. 15 —— D. 12 7、（2023）根节点的高度为 1，一棵拥有 2023个节点的三叉树高度至少为（）。 A. 6 —— B. 7 —— C. 8 —— D. 9 8、（2023）后缀表达式 `6 2 3 + - 3 8 2 / + * 2 ^ 3 +` 对应的中缀表达式是 A. `((6-(2+3))*(3+8/2))^2+3` B. `6-2+3*3+8/2^2+3` C. `(6-(2+3))*((3+8/2)^2)+3` D. `6-((2+3)*(3+8/2))^2+3` 9、（2023）给定一棵二叉树，其前序遍历结果为：`ABDECFG`,中序遍历结果为：`DEBACFG`。请问这棵树的正确后序遍历结果是什么? A. `EDBGFCA` B. `EDGBFCA` C. `DEBGFCA` D. `DBEGFCA` [答案（点击查看）](https://www.luogu.com.cn/paste/n78geblq)

四、图

图就好像是一幅地图，每个顶点表示一个建筑，建筑之间有路（边）将这些顶点连接起来。

（图片）

初赛我们只需了解图的大体定义、性质，到复赛才需了解图的储存和遍历。

（待更新）

第四节 数论基础

（待更新）

后记

本指南目前尚未编写完成，预计将于2026年完工。

编写历程：

2023/9/15晚 ： 初稿形成，共计28页word文档，作为考前复习。
2023/11 ： 开始在博客上将word文档转为博客文章，完成第一章编写。
2024暑假至2024/9 ： 完成了一、二、三节（图论除外）的编写。大部分工作都是在2024完成的。
2025/9 ： 对大量语言进行重构，添加“C++基础”“数据存储与指针使用”章节。

鸣谢：
老师@xtyz
同学@New_Node@const_int_N@Yand_JiaYi
我自己@qiaoluchen

祝各位RP++ 取得好成绩

早日AK IOI!!!