初赛知识点总结
1.计算机常识:
IPv4:32位(2^32-1),IPv6:128位(2^128-1);
C语言不属于面向对象程序设计语言;
ROM:只读存储器,断电信息不会丢失;
RAM:内存,断电信息会丢失。
2.原码反码补码:
正数的原码反码补码一样;
负数的反码是原码(除符号位)各位字符做取反运算;
负数的补码等于反码加一;
零的原码反码有两种,但补码只有一种;
3.算法常识:
(1) 算法的特征: 有穷性,可行性,确定性
(2) 排序算法:
稳定:冒泡排序,插入排序,归并排序,基数排序
不稳定:选择排序,希尔排序,快速排序,堆排序
插入排序:最好 O(n) 最坏 O(n^2)
选择排序:最好 O(n^2) 最坏 O(n^2)
基数排序:最好 O(nk) 最坏 O(nk)
冒泡排序:最好 O(n log n) 最坏 O(n^2)
快速排序:最好 O(n log n) 最坏 O(n^2)
归并排序:最好 O(n log n) 最坏 O(n log n)
希尔排序:最好 O(n log^2 n) 最坏 O(n log^2 n)
(3) 其他算法:
分治算法: 将一个问题拆分成多个子问题进行处理,再将答案进行合并,从而提高效率,加快速度;
贪心算法: 首先,找到可选子问题,求出最优解,达到局部最优,再将其合并,从而获得全局最优;
动态规划: 通过把原问题分解为相对简单的子问题的方式求解复杂问题(背包问题,区间DP,线性DP等);
4.哈夫曼编码:
构造一棵哈夫曼树，算法步骤如下：
初始化 :由给定的个权值构造棵只有一个根节点的二叉树,得到一个二叉树集合。
选取与合并 :从二叉树集合中选取根节点权值 最小的两棵 二叉树分别作为左右子树构造一棵新的二叉树,这棵新二叉树的根节点的权值为其左,右子树根结点的权值和。
删除与加入 :从中删除作为左,右子树的两棵二叉树，并将新建立的二叉树加入到中。
重复2,3步,当集合中只剩下一棵二叉树时，这棵二叉树就是哈夫曼树。
哈夫曼编码**,**其构造步骤如下：
设需要编码的字符集为:d1,d2,…dn,他们在字符串中出现的频率为:w1,w2,…wn。
以d1,d2,…dn作为叶结点,w1,w2,…wn作为叶结点的权值,构造一棵哈夫曼树。
规定哈夫曼编码树的左分支代表0,右分支代表1,则从根结点到每个叶结点所经过的路径组成的0.1,序列即为该叶结点对应字符的编码。
5.数据结构:
栈(stack): 先进后出
队列(queue): 先进先出
双向队列(deque): 栈与队列的结合体
集合(set): 自动排序,并去重
映射(map): 自动排序,不去重
动态数组(vector): 从下标0开始储存数据
树(tree):
根结点: 树最顶端的结点被称为根结点。
叶子结点: 度为0的结点被称为叶子结点
父结点: 度大于0的结点被称为父结点。
子结点 :除根结点以外的所有结点都是子结点
兄弟结点: 同一个父亲的多个子结点互为兄弟。
树的高度: 从根结点到各个叶子结点的最长距离。
树的宽度: 树每一层的结点数量的最大值。
二叉树: 所有结点的度均为0,1,2
完全二叉树: 只有最下面两层结点的度数小于2,且最下面一层的结点都集中在该层最左边的连续位置上。
满二叉树: 所有叶结点的深度均相同,且所有非叶结点的子结点数量均为2的二叉树称为满二叉树。
图(graph):
有向图: 相邻的结点之间的边是单向的;
强连通图: 各个结点之间能够互相到达;
强连通子图: 有向图中包含的较小的强连通图;
强连通分量: 有向图中包含的强连通图的数量;
有向图的入度: 通向这个结点的结点数量;
有向图的出度: 这个结点通向的结点数量;
无向图: 相邻的结点之间的边是双向的;
无向图的度: 与这个结点相连的结点数量;
连通图: 各个结点之间是互相连接的;
连通子图: 无向图中包含的较小的连通图;
连通分量: 无向图中包含的连通图的数量;
5. 格雷码:
构造格雷码:
1.翻转最低位得到下一个格雷码;
2.把最右边的1的左边的位翻转得到下一个格雷码;
3.交替按照上述策略生成2^k-1次,可得到k位的格雷码序列。
6. 运算符优先级:
++( 后自增)
–( 后自减)
()( 括号)
++( 前自增)
–( 前自减)
+( 正号)
- 负号
!( 逻辑取反)
~( 按位取反)
*( 乘法)
/( 除法)
%( 取余)
<( 小于)
<=( 小于等于)
>( 大于)
>=( 大于等于)
==( 等于)
!=( 不等于)
&( 按位与)
^( 按位异或)
|( 按位或)
&&( 逻辑与)
||( 逻辑或)
?：( 条件运算符)
=( 各种赋值运算)