初赛知识点复习

access_time    bookmark 笔记    comment 0 条评论   

排序

希尔排序

作者: 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( \dfrac {n}{b}\right) +cn^{k} \qquad \forall n > b $$

那么

$$ T(n) = \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} $$


新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交或含有敏感词汇的评论将在审核后显示。