笔记：
- 对数log：
如果 a 的 x 次方等于 N（ a>0，且 a≠1 ），那么数 x 叫做以 a 为底 N 的对数，记作 x=log_a N。其中，a 叫做对数的底数，N 叫做真数， \log_xn = y 就说明 x^y=n (x就是底数，在信奥中如果不写默认为2，数学中默认10) \log_2 n = y , 那么 2^y = n ，当 n/2 后，2 ^{( y - 1 )} = n /2 了 -
线性结构与非线性结构
线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。
非线性结构，其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。 -
主定理
主定理解释待填坑
分割线
错题：
题目：
由四个不同的点构成的简单无向连通图的个数是（ ）。
A. 32
B. 35
C. 38
D. 41
做法：
- 第一步： 可以把4个点看做正方形的四个顶点，正方形各个顶点见最多6条线，分别是四周的线和对角线
- 第二步： 因为是一个连通图，所以至少要3条边，故排除1，2两条边的可能
-
第三步： 因为只有三条边的话可能出现三个边形成一个三角形从而孤立一个点的可能，所以要排除这些可能（共四种）
-
第四步： 用组合数计算，C^3_6+C^4_6+C^5_6+C^6_6-4=38
题目：
将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有（ ）种不同的分配方案。
A. 60
B. 84
C. 96
D. 120
做法：
- 用插板法，因为插板法的前提是每个班至少要有一个人，而本题却允许没人，所以我们要进行一些操作
-
先自己添加4个点，分到每个班，所以现在一共有11个点，4个班，满足了插板法的条件，然后就用插板法解决
-
因为要把名额分成4分，也就是要3个板，而且这三个板要在10个空位中（11个名额间的间隔）组合，所以答案就是 C^3_{10}=120
有关：https://blog.csdn.net/sdz20172133/article/details/81431066
题目：
若 f_0 = 0, f_1 = 1, f_{n + 1} =\frac{ (f_n + f_{n-1})}2，则随着 i 的增大，f_i 将接近于( )。
A. \frac12
B. \frac23
C. \frac{\sqrt 5 − 1}2
D. 11
解法：
- 规律题，从 n=1 开始模拟， f_2=\frac12 ，f_3=\frac34 ， f_4=\frac58 ， f_5=\frac{11}{16} ， f_6=\frac{21}{32}
题目：
若某算法的计算时间表示为递推关系式：T(N) = 2 × T(\frac N2) + N × \log N ， T(1) = 1 则该算法的时间复杂度为（ ）。
A. O(N)
B. O(N \log N)
C. O(N \log^2 N)
D. O(N^2)
做法:
- 先把原式子递归找规律，得到
2 × (2 × T(\frac N4) + \frac N2 × \log \frac N2) + N × \log N
- 化简
4 × T(\frac N4) + N × \log \frac N2 + N × \log N
4 × T(\frac N4) + N × (\log \frac N2 + \log N)
- 上面的式子一直往下推会得到
2^{\log_{_2} N}×T(1)+N × (\log \frac N{16}+\log \frac N8+\log \frac N4+\log \frac N2 + \log N)
≈2^{\log_{_2}N}×T(1)+ N \log^2 N
＝N+N \log^2 N
为什么可以这样推导？
原因：
2^{\log_{_2} n}=n 推导：
因为 \log_xn = y 可以得到 x^y=n ，所以 \log_{2} n 就相当于求出了 y ，又因为 x=2 所以 2^{\log_{2} n}=n
n \log^2 n 推导：
先要明确，从 2 × (2 × T(\frac N4) + \frac N2 × \log \frac N2) + N × \log N 化简到 4 × T(\frac N4) + N × \log \frac N2 + N × \log N 时，\log 里面的不能除以2 ，我们可以把它看成一个整体。因为 \log N 只比 \log \frac N2 多一（原理见笔记），所以加到最后就约等于 2^{\log_{_2}N}×T(1)+ N \log^2 N
题目：
2017 年 10 月 1 日是星期日，1949 年 10 月 1 日是（ ）。
A. 星期三
B. 星期日
C. 星期六
D. 星期二
做法：
-
一年365天，365%17=1 也就是说每个平年会对星期造成1天的影响，那么每个闰年就是2天的影响
-
每个世纪100年中，有25个闰年，前半年13个，后半年12个，所以在1949-2017年一共有17个，17*2+(68-17)=85，85%7=1，又因为我们是从2017年去推1949年，所以我们要减1，因此就是星期六。
文章评论
暂时咕了