排序

希尔排序

作者： dreamcatcher-cx 出处： https://www.cnblogs.com/chengxiao/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在页面明显位置给出原文链接。

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，n/2,(n/2)/2,...,1，称为增量序列。

希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

例题：设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。

• A、40，50，20，95
• B、15，40，60，20
• C、15，20，40，45
• D、45，40，15，20

答案：B

std:sort

std::sort 在数据量大时采用快排，分段递归排序；一旦分段后的数据小于某个值，就改用插入排序；如果递归层次过深，还会改用堆排序。

std::sort使用了快排，插入排序（希尔排序），堆排序。

例题：c++的std::sort实现中使用了以下哪些快速排序的算法（）

• A、快速排序
• B、堆排序
• C、基数排序
• D、插入排序(希尔排序)

答案：ABD

归并排序

运用递归将原数据不断二分，然后在回溯过程中使用归并算法将其一步步合并，最后合成一个有序数列。

时间效率：最好：$ O(log n) $ 最坏：$ O(n \times log n) $

其中归并就是将两个数组一个个比较即可，最多比较 $ 2n-1 $ 次。

例(NOIp2017 T11)：设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的 数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 （ ）次比较。

答案：$ 2n-1 $

排序的稳定性

• 稳定排序：插入排序、桶排序、基数排序
• 不稳定排序：快速排序、堆排序、希尔排序、归并排序、选择排序、冒泡排序

树

哈夫曼树

哈夫曼树是最优二叉树，即每个点的权值 $\times$ 它到根节点的路径和最小。

哈夫曼树的构建方法是先将每个点单独构建成一颗只有自己的树，然后每次选取路径和最小的两棵树合并到一起，所有树合并完即构建成功。

例题：设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

• A、 99
• B、 100
• C、 101
• D、 102

答案：B

解析：把 $ n $ 个节点构建成哈夫曼树，相当于把 $ n $ 个只有根节点的子树合并成一个树，其中将任意两个子树合并成一个棵树需要增加一个节点，则一共需要增加 $ n-1 $ 个节点，才能使其变成一棵哈夫曼树，即这棵哈夫曼树一种有 $ 2n-1 $ 个树。$ 2 \times n - 1 = 199 $ ，解得：$n = 100$

表达式

中缀表达式

就是一般人用的表达式，初赛肯定不会考。

前缀表达式

以下内容转载至：https://www.cnblogs.com/chensongxian/p/7059802.html

就是把运算符放到数字的前面。

前缀转中缀：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

中缀转前缀：

1. 初始化两个栈:运算符栈s1，储存中间结果的栈s2
2. 从右至左扫描中缀表达式
3. 遇到操作数时，将其压入s2
4. 遇到运算符时，比较其与s1栈顶运算符的优先级
   1. 如果s1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
   2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1
   3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
5. 遇到括号时
   1. 如果是右括号“)”，则直接压入s1
   2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
6. 重复步骤2至5，直到表达式的最左边
7. 将s1中剩余的运算符依次弹出并压入s2
8. 依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式

后缀表达式

就是把运算符放到数字的左边。

前缀转中缀：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

中缀转前缀：和中缀转后缀差不多，就是从左到右扫，最后逆序就行了。

例(NOIp2017 T7)：表达式 a (b + c) d 的后缀形式是（ ）。

• A. a b c d +
• B. a b c + d
• C. a b c + d
• D. b + c a d

答案：B

个人看法

中缀转前缀、后缀的方法其实根本用不上，只需要把选项转成中缀比对就行了。

当然，如果除了选择题的题考到了，那就另说吧。

图

相关定义

完全图：每对顶点都有边相连的图。
完全无向图有 $ \dfrac {n\times \left( n-1\right) }{2} $ 条边，完全有向图有 $ n\times \left( n-1\right) $条边。

连通图：每两个节点间都有路径相连的图。

例题

例1：(NOIp2017 T8) 由四个不同的点构成的简单无向连通图的个数是（ ）。

答案：38

解析：按照分类标准连1条、连2条、连3条、连4条、连5条、连6条分类讨论。其中连1条、连2条由于无法构成无向连通图而舍掉。再对剩下的情况进行组合（因为无向），即在6条可能的边中连上3、4、5或6条，并将可以构成无向连通图的情况进行计数。不能构成的情况其实应该只有连3条边时才出现。比如ABCD 4个点三条边分别连接A-B、B-C、C-A就不行，一共四种不行的。算出来一共是42-4=38种。

例2：(NOIp2016 T8) G 是一个非连通简单无向图，共有 28 条边，则该图至少有（ ）个顶点。

答案：9

解析：因为是非连通图，所以至少有一个点不能连通，那么建一个完全图再把顶点+1即可。

$ \dfrac {n\times \left( n-1\right) }{2} = 28 $ ，解得 $ n=8 $ ，答案为 $ n+1=9 $。

递推时间复杂度的计算

主定理(Master Theorem)

以下内容来自OI Wiki,全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

根据SATA协议的相关要求，我已给了Star，并在此推荐此网站及感谢 @lr1d 和 @yeguanghao 对此内容的贡献。

我们可以使用 Master Theorem 来快速的求得关于递归算法的复杂度。 假设我们有递推关系式

$$T(n) = AT\left(\frac{n}{b}\right)＋cn^k, \qquad \forall n > b$$

那么

$$T(n) = \begin{equation}\begin{cases}\Theta(n^{\log_b a}) & a > b^k \\ \Theta(n^k) & a< b^k \\ \Theta(n^k\log n ) & a = b^k \end{cases}\end{equation}$$

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/noip-pretest-summary.html