初赛知识点选讲

笔记
编辑文章
这是整理的讲课材料,有些知识点仅有思路。

基础常识

进制转化

  1. 十转其他:整数部分除2取余,逆序排列;小数部分乘2取整,顺序排列。
  2. 其他转十
  3. 其他转其他:用十进制做跳板、二转八和十六进制的特殊情况。

机器码

  1. 带符号数:最高位表示符号,0为正,1为负;其他表示数值。
  2. 原码:符号位为0或1(正或负),数值不变。注意+0和-0不同。
  3. 反码:正数与原码相同;负数符号位不变,其他按位取反。
  4. 补码:正数与原码相同;负数符号位不变,其他按位取反后+1。
  5. 补码的意义:$A-B=A+(-B)$,在有模数的情况下 $A-B\equiv A+(M-B) \pmod M$,二进制下即需要$+1$
  6. 机器使用补码,$[10000000]$ 表示 $-128=(-1)+(-127)$,只有 $[00000000]$ 表示 $0$
  7. 程序中的应用,如&,|,~(区分&&,||,!
for (int i=100;i;i--)
for (int i=100;~i;i--)

浮点数

$$N = 2^{E} \times S$$

$E$ 是阶码,为整数,表示小数点移动的位数(正数向右,负数向左)。

$S$ 是尾数,为二进制小数。

如 $101.011 = 2^{3} \times 0.101011 \ , \ 0.0101011 = 2^{-1} \times 0.101011$

ASCII码

7位二进制数,0~127共128个字符。

算法

排列组合

卡特兰数

$$\frac{C_{2n}^n}{n+1}$$

  1. 按 $1,2,\cdots,n$ 的顺序进栈,对应的出栈序列总数。
  2. $n$ 个点可以构成的二叉树种类数。
  3. (初赛无关)在$n\times n$个方格形成的地图中,只能向下向右走,不能越过对角线,从左上到右下格子的路线总数。
  4. (2016全国卷III数学 12)定义“规范01数列”$\{a_n\}$ 如下:$\{a_n\}$ 共有 $2m$ 项,其中 $m$ 项为 $0$,$m$ 项为 $1$,且对任意的 $k\le 2m$,$a_1,a_2,\cdots ,a_k$ 中 $0$ 的个数不少于 $1$ 的个数。若 $m=4$,则不同的“规范01数列共有”多少个?

二叉树

  1. 先序遍历:根左右;中序遍历:左根右;后序遍历:左右根
  2. 第 $i$ 层有最多 $2^{i-1}$ 个节点。
  3. 深度为 $k$ 的二叉树最多有 $2^k-1$ 个节点,最少有 $k$ 个。
  4. 满二叉树:深度为 $k$ 就有 $2^k-1$ 个节点。
  5. 完全二叉树:除了最下层外的其他层都满,满二叉树也是完全二叉树。

哈夫曼树

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

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

哈夫曼

例题:设某哈夫曼树中有199个结点,则该哈夫曼树中有()个叶子结点。

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

答案:B

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

二叉搜索树

若左子树不为空,则左子树所有节点均小于根节点;若右子树不为空,则右子树所有节点均大于根节点。

  • 性质:根节点大于其他节点。(左右子树无要求)
  • 插入:(大根堆)先将其接在最后,然后判断它与父节点大小关系,若大于父节点则交换,并重复这个步骤,直到小于父节点时停止。
  • 删除根节点:将最后一个元素替换根节点,并进行与插入操作类似,不过依次向下的修复。

排序

排序的稳定性

稳定的排序:若排序前数 $a_i=a_j$ 且 $a_i$ 在 $a_j$ 之前,排序后 $a_i$ 仍然在 $a_j$ 之前。

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

冒泡排序

平均最坏最好空间稳定性
$O(n^2)$$O(n^2)$$O(n)$$O(1)$稳定

比较相邻的元素,如果前比后大就交换。

需要注意最好时间复杂度是 $O(n)$ ,可以在代码中加上判断是否有交换。

选择排序

平均最坏最好空间稳定性
$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$不稳定

从未排序的部分中不断选最小的,放在已排序部分的后面。

复杂度表现稳定,但是不稳定排序。

插入排序

平均最坏最好空间稳定性
$O(n^2)$$O(n^2)$$O(n)$$O(1)$稳定

假设前 $i$ 个数已经有序,取第 $i+1$ 个数,然后向前扫描,直到某个数 $a_j\le a_{i+1}$ ,将 $a_{i+1}$ 插入到 $a_j$ 后面。初始 $i=1$ 。

希尔排序

平均最坏最好空间稳定性
$O(n^{1.3})$$O(n^2)$$O(n)$$O(1)$不稳定
作者: 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

桶排序

平均最坏最好空间稳定性
$O(n+k)$$O(n^2)$$O(n)$$O(n+k)$稳定

为何最坏为 $O(n^2)$ ?若所有数都一样,当前桶被占用,需要向后寻找直到空桶。

堆排序

平均最坏最好空间稳定性
$O(n\log n)$$O(n\log n)$$O(n\log n)$$O(1)$不稳定

顾名思义,每次用堆得到一个最大/最小值,$n$ 次操作即可得到有序数列。

归并排序

平均最坏最好空间稳定性
$O(n\log n)$$O(n\log n)$$O(n\log n)$$O(n)$稳定

不断将数列二分然后分治,排序后合并。

复杂度表现稳定,也是稳定排序。

快速排序

平均最坏最好空间稳定性
$O(n\log n)$$O(n^2)$$O(n\log n)$$O(n\log n)$不稳定

从数列中选出一个数作为基准,将比基准小的数放在基准前,比它大的放在后,此时基准的顺序一定是正确的。而后对前后两个部分分治。(类似于归并)

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 $

表达式

中缀表达式

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

前缀表达式

以下内容转载至: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 协议之条款下提供,附加条款亦可能应用

我们可以使用 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} $$

较复杂的排列组合(见pdf)

例1(2008,22)书架上有21本书,编号从1到21,从其中选4本,其中每两本的编号都不相邻的选法一共有(3060)种。(等价放了17本书,插入4本,$C_{18}^4=3060$)

运算符优先级(部分)

优先级运算符
1后缀++ --,括号
2前缀++ --! ~
3* / %
4+ -
5<< >>
6== !=
7&
8^
9|
10&&
11||

例题:(2017,5)在C语言中,表达式 23|2^5 的值是( ) 23

欧拉图

  • 定义:通过图中所有边且每边仅通过一次的通路称为欧拉回路,具有欧拉回路的图称为欧拉图。
  • 具有欧拉通路而无回路的称为半欧拉图。
  • 无向连通图是欧拉图:图中不含奇数度节点
  • 无向连通图含欧拉通路:有0个或2个奇数度的节点
  • 有向连通图是欧拉图:所有节点入度=出度
  • 有向连通图含欧拉通路:所有节点入度=出度 或 除了两个节点(起点终点),其他节点满足入度=出度,且这两点中起点入度=出度-1,终点出度=入度-1。
  • 欧拉环游,欧拉闭迹

例题:(2007,9)欧拉图G 是指可以构成一个闭回路的图,且图G 的每一条边恰好在这个闭回路上出现一次(即一笔 画成)。在以下各个描述中,不一定是欧拉图的是(D)。

  • A.图G中没有度为奇数的顶点
  • B.包含欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)
  • C.包含欧拉闭迹的图(欧拉迹是指通过图中每边恰好一次的路径)
  • D.存在一条回路,通过每个顶点恰好一次
  • E.本身为闭迹的图

数学中逻辑符号

  • ¬ = !
  • = &
  • = |

例1:(2007,11)设A=B=true,C=D=false,以下逻辑运算表达式值为真的有(ABC)。

  • A. (¬ A∧B)∨(C∧D∨A)
  • B. ¬ (((A∧B)∨C)∧D)
  • C. A∧(B∨C∨D)∨D
  • D. (A∧(D∨C)) ∧B

例2:(2008,13)设A=true,B=false,C=true,D=false,以下逻辑运算表达式值为真的有(AC)。

  • A. (A∧B)∨(C∧D∨A)
  • B. ((A∧B)∨C)∧D
  • C. (B∨C∨D)∨D∧A
  • D. A∧(D∨C)∧B

字符串

  • 子串:串中任意个连续的字符组成的子序列称为该串的子串。
  • $n$ 个字符的串的子串个数:$\frac{n(n+1)}{2}+1$ (注意空串)

例题:(2008,3)设字符串S=”Olympic”,S的非空子串的数目是(28)。

补充:哈夫曼编码

将字符按照出现的频率建立哈夫曼树,从根节点开始,左子树为0,右子树为1,走到该字符得到该字符的编码。

例题:(2009,7)最优前缀编码,也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。(B)

  • A.(00,01,10,11)
  • B.(0,1,00,11)
  • C.(0,10,110,111)
  • D.(1,01,000,001)

立体几何

例题:(2010,18)一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、(0,3,0)、(2,0,0)的平面的法线是(D)。(3,2,1)

  • A.过点(1,1,1)、(2,3,3)的直线
  • B.过点(1,1,1)、(3,2,1)的直线
  • C.过点(0,3,0)、(-3,1,1)的直线
  • D.过点(2,0,0)、(5,2,1)的直线

其他题选讲

  1. (2008,10)对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找,等概率的情况下查找成功的平均查找长度(平均比较次数)是(3)。(56查1次,19和88查2次,剩下的数4个查3次,4个查4次(写法不同))
  2. (2010,17)关于拓扑排序,下列说法正确的是(D)。
  • A.所有连通的有向图都可以实现拓扑排序
  • B.对同一个图而言,拓扑排序的结构是唯一的
  • C.拓扑排序中入度为0的结点总会排在入度大于0的结点的前面
  • D.拓扑排序结果序列中的第一个结点一定是入度等于0的点

新评论

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