2022CSP初赛普及组比赛详情
重点复习
栈
*缀表达式
图的遍历
语言
逻辑表达式
二叉树
排序
队列（queue）
2022CSP（原名NOIP）普及组初赛详情
比赛时间：未定
重点复习：
一，栈
1.定义：栈（stack）又名堆栈，是一种运算受限的线性表。
2.栈的主要操作：
（1）s.push(a) //将a压入栈顶(纯动作)
（2）s.pop() //删除栈顶的元素，但不会返回（纯动作）
（3）s.top() //返回栈顶的元素，但不会删除
（4）s.size() //返回栈中元素的个数
（5）s.empty() //检查栈是否为空，如果为空返回true，否则返回false
*二，缀表达式
1.中缀表达式（中缀记法）
中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。
2.前缀表达式（前缀记法、波兰式）
前缀表达式的运算符位于操作数之前。
前缀表达式的计算机求值：
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如前缀表达式“- × + 3 4 5 6”：
(1) 从右至左扫描，将6、5、4、3压入堆栈；
(2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；
(3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；
(4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
可以看出，用计算机计算前缀表达式的值是很容易的。
将中缀表达式转换为前缀表达式：
遵循以下步骤：
(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
(2) 从右至左扫描中缀表达式；
(3) 遇到操作数时，将其压入S2；
(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
(4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
(4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
(5) 遇到括号时：
(5-1) 如果是右括号“)”，则直接压入S1；
(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
(6) 重复步骤(2)至(5)，直到表达式的最左边；
(7) 将S1中剩余的运算符依次弹出并压入S2；
(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
例如，将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的结果为：- + 1 × + 2 3 4 5。
3.后缀表达式（后缀记法、逆波兰式）
后缀表达式与前缀表达式类似，只是运算符位于操作数之后。
后缀表达式的计算机求值：
与前缀表达式类似，只是顺序是从左至右：
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如后缀表达式“3 4 + 5 × 6 -”：
(1) 从左至右扫描，将3和4压入堆栈；
(2) 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
(3) 将5入栈；
(4) 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
(5) 将6入栈；
(6) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。
4.将中缀表达式转换为后缀表达式：
与转换为前缀表达式相似，遵循以下步骤：
(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
(2) 从左至右扫描中缀表达式；
(3) 遇到操作数时，将其压入S2；
(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
(4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
(4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；
(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
(5) 遇到括号时：
(5-1) 如果是左括号“(”，则直接压入S1；
(5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；
(6) 重复步骤(2)至(5)，直到表达式的最右边；
(7) 将S1中剩余的运算符依次弹出并压入S2；
(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。
三，图的遍历
1.深度优先遍历和广度优先遍历( DFS && BFS )
【深度优先】 0->3->1->2->4
1.从0开始，首先找到0的关联顶点3。
2.由3出发，找到1；由1出发，没有关联的顶点。
3.回到3，从3出发，找到2；由2出发，没有关联的顶点。
4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。
【广度优先】A->B->F->C->G->I->E->D->H
2.欧拉回路(一笔画问题)
由众所周知的“哥尼斯堡城‘七桥问题’”，大数学家欧拉开创了数学新分支-----图论。也就是“一笔画”。一笔画图形的必要条件是：奇点数目是0或者2。“七桥问题”的A,B,C,D都是奇节点，数目是4，所以不能够“一笔画”。 我们把节点转换回来，成为“节面”（区域），来考虑“一笔画”。
数学家欧拉找到一笔画的规律是：
⒈凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。
⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。
⒊其他情况的图都不能一笔画出（有偶数个奇点除以二便可算出此图需几笔画成）。
相关名词：【奇点】从某点发出奇数条边。
3.哈密尔顿环
哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。
1、背景
（1）哈密尔顿图的概念
1857年， 哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市 ，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示。
哈密尔顿(1805—1865),爱尔兰数学家。个人生活很不幸，但兴趣广泛：诗歌、光学、天文学和数学无所不能。他的主要贡献是在代数领域，发现了四元数(第一个非交换代数)，他认为数学是最美丽的花朵。
哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备而著名) ，1859年获得专利权。但商业运作失败了。
该游戏促使人们思考点线连接的图的结构特征。这就是图论历史上著名的哈密尔顿问题。
2、哈密尔顿图与哈密尔顿路
定义：如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈，称为G的哈密尔顿圈。
四，语言
面向过程：Pascal 、C 、QBASIC、Fortran
面向对象(对象Object)：Objective-C、C++ 、Java、Python、Ruby、EIFFEL、Simula67(第一种)、SmallTalk(第二种)
面向对象的三个基本特征是:封装、继承、多态
机器语言(二进制的01串，平台有关，可直接运行)->汇编语言(使用助记符的机器语言，平台有关，要汇编才能运行)->高级语言(平台无关，不能直接执行，需要解释或编译才能运行)
五，逻辑表达式
1.运算：
（1）与：and ∧
（2）或：or ∨
（3）非：not ¬
（4）异或：xor
2.优先级：
非>与>或
六，二叉树
1.3种遍历次序：
（1）前序遍历
（2）中序遍历
（3）后序遍历
2.相关计算：
（1）二叉树的深度和层数其实是一样的。
（2）任意一棵树的总结点数等于总分支数+1。
（3）叶子结点也称叶子，度为0的结点。
（4）一个深度为n的满二叉树的总结点数为 2^n-1。
（5）深度为h的完全二叉树至少有2(h-1）个结点，最多有2h-1个结点。
3.结点：
（1）分支结点
（2）叶子结点
4.公式：
（对于完全二叉树）
（1）（总结点数为偶数）叶子结点=分支结点
（2）（总结点数为奇数）叶子结点=分支结点+1
5.相关题目：
【例1】一棵二叉树第六层（根结点为第一层）的结点数最多为？
解：其实这道题很简单，就是2^5=32。
【例2】某二叉树中度为2的结点有18个，则该二叉树中有多少个叶子结点？
解：根据总结点数=总分支数+1，设叶子有n个，则有18 + n = 18*2 + 1，解得n = 19。
【例3】设一棵完全二叉树共有199个结点，那么该二叉树共有个分支结点？
解：思路就是先求出这个完全二叉树的叶子数，然后用总结点数减去叶子数就是分支结点的数目了。因为有 (2^7) - 1<199<=(28)-1，所以得深度为8，前7层为满二叉树，所以前7层的总结点数为(27) - 1 = 127 ,第7层的结点数为 2^6 = 64，则最后一层的叶子为 199 - 127 = 72 ，所以第7层的叶子数为 64 - 72/2 = 28，所以总叶子数为 72+28 = 100，分支数为 199 -100 = 99。
【例4】在深度为7的二叉树中，最多有多少个叶结点？（注意这里问的是叶结点，而不是结点数，如果是结点数的话答案是（2^6）-1 ）
解：这种题目和例1差不多，为 2^6。
【例5】设一棵完全二叉树共有127个结点，那么该二叉树是满二叉树吗？
解：因为 一个深度为n的满二叉树的总结点数为 2^（n-1）-1，则设 2^（n-1）-1 = 127，解得n = 8 ，所以这是满二叉树。
【例6】具有53个结点的完全二叉树的深度为？
解：因为一个二叉树的结点数必然不会超过深度一样的满二叉树的结点数，所以有(25)-1<53<=(26)-1，所以答案为6。
【例7】设一棵完全二叉树共有700个结点，则在该二叉树中有多少个叶子结点？
解：从例5延伸出来的题目，由例6的思路可得， (29)-1<700<=(210) - 1，所以得出这棵二叉树前面9层是满二叉树，则得前9层的总结点数为 (2^9)-1 = 512 -1 =511。则剩下来的结点数就是最后一层的结点数，为 700 - 511 = 189 ，把他凑成偶数为190，则也就是说，最后一层是从第九层中 190/2= 95个结点延伸出来的，所以第九层失去了95个叶子，又因为第九层的结点数为 2^8 = 256，则第九层的叶子数为 256 - 95，则所有的结点数为256-95 +189 =350。
七，排序
1.插入排序
（1）直接排序
（2）shell排序
2.选择排序
（1）直接选择
（2）堆排序
3.交换排序
（1）冒泡排序
（2）快速排序
4.归并排序
5.基数排序
关于基数排序，请参考网站：(https://www.cnblogs.com/qilinart/articles/11653452.html)
6.原地排序
7.拓扑排序
关于拓扑排序，请参考网站：
(https://www.cnblogs.com/qilinart2/articles/3872376.html)
八，队列（queue）
只能访问queue容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。FIFO（先进先出）
1.初始化
需要头文件：queueque;
2.成员函数
C++队列queue类成员函数如下:
（1）back() //返回最后一个元素
（2）empty() //如果队列空则返回真
（3）front() //返回第一个元素
（4）pop() //删除第一个元素
（5）push() //在末尾加入一个元素
（6）size() //返回队列中元素的个数
3.基本操作
queue的基本操作举例如下：
（1）queue入队，如例：q.push(x) //将x 接到队列的末端
（2）queue出队，如例：q.pop() //弹出队列的第一个元素（注意：并不会返回被弹出元素的值）
（3）访问queue队首元素，如例：q.front() //即最早被压入队列的元素
（4）访问queue队尾元素，如例：q.back() //即最后被压入队列的元素
（5）判断queue队列空，如例：q.empty() //当队列空时，返回true
（6）访问队列中的元素个数，如例：q.size()
资料来源：qilinart-博客园 & codeisking-博客园