初赛—错题集

计算机基础知识

LAN：局域网，WAN：广域网，MAN：城域网
汇编语言是(依赖于具体计算机)的低级程序设计语言
计算机操作的最小时间单位是(时钟周期)。
注意所需空间需要 \(\div 8\) ！！！
\(256\) 色的彩色视频 \(\rightarrow\) \(8\) 位！！！只用 \(\times 8\) 而不是 \(256\) ！！！
Java、Python 解释执行
编译命令: g++ text.cpp -o exec -Ofast -std=c++14 -g
- 先有 g++ text.cpp -o exec 命令表示编译的代码与用 exec 运行，再有其他编译选项
关于 IPv4 与 IPv6 :
- IPv4 是 \(32\) 位的，十进制，不提供身份加密
- IPv6 是 \(128\) 位的，十六进制，提供身份加密
关于补码：补码 \(=\) 反码 \(+1\) ！！！(不是最后一位取反)
面向对象的语言有 Smalltalk、Eiffel、C++、Java、PHP 等

图论

有根树的 节点度数 是孩子节点的个数。
邻接表是 \(\text{vector}\) ，而邻接矩阵再是 \(n^2\) ！！！！！！！

数据结构

线段树的 \(\text{build}\) 是 \(O(n)\) 的！！
- \[T(n)=2\times T\left(\frac{n}{2}\right)+1=O(n) \]

数学

二阶常系数齐次线性递推数列
一个圆形水池中等概率随机分布着四只鸭子，那么存在一条直径，使得鸭子全在直径一侧的概率是( \(\dfrac{1}{2}\) )
- 假设第一只鸭子所在位置与圆心的连线与存在的直径垂直，那么后面每一只鸭子都有 \(\dfrac{1}{2}\) 的概率在这一侧。
- 考虑到每一只鸭子都可以当第一只鸭子，所以最终概率为：
- \[n\times\dfrac{1}{2^{n-1}} \]
在 xxy 的面前摆了 \(4\) 包不同品牌的薯条(用 \(a\) 代替)和 \(5\) 包不同品牌的蕃茄酱(用 \(b\) 代替)，其中有 \(4\) 个 \(b\) 的品牌与 \(4\) 个 \(a\) 一一对应，另一个 \(b\) 的品牌则无法对应。每次操作， xxy 从剩下的 \(a\) 中随机选择一个，从剩下的 \(b\) 中随机选择一个，一起吃掉。这样 \(4\) 次以后， \(a\) 已经没有了， \(b\) 还有一包， xxy 就会把这包 \(b\) 送给小 \(y\) 。问 xxy 恰好只吃到一组同品牌的 \(a\) 和 \(b\) 的概率约为( A )？
A.\(37\%\) B.\(36\%\) C.\(33\%\) D.\(31\%\)
- 总情况数为 \(A_5^4=5!=120\) ，分两种清况。
- 第一种，抛弃的 \(b\) 刚好是多余品牌。那么选一对 \(a,b\) 对应正确，其余错排即可( \(4\times2=8\) )。
- 第二种，选一对 \(a,b\) 对应正确，再选一个 \(a\) 对应多余 \(b\) ( \(4\times3\times3=36\) )。
- \[\dfrac{4\times2+4\times3\times3}{A_5^4}\approx37\% \]
现在工厂里有三根铁棒，分别长为 \(3,4,5\) 现在你可以对其中一些铁棒进行加长，但总的加长长度不能超过 \(10\) ，有(187)种加长的方案使得加长后的铁棒可以构成三角形。
- 考虑容斥，首先用隔板法求出加长的总方案数为 \(\dbinom{10+4-1}{3}=286\) ，再考虑算出不合法的加长方案数。
- 构不成三角形则 \(a+x+b+y\le c+z\) ，且 \(x+y+z\le L\)
- 则 \(x+y\le \min(c+z−a−b,L−z)\)
- 于是枚举 \(z\) ,则知道 \(x+y\) 最大是多少，再用隔板法求出这种条件下 \(x,y\) 的方案数
采用任何基于排序码比较的算法，对 5 个互异的整数进行排序，至少需要(C)次比较。
A. 5 B. 6 C. 7 D. 8
- \(\log_2(5!)\) 向上取整
公共汽车起点站于每小时的 \(10\) 分，\(30\) 分，\(55\) 分发车,该顾客不知发车时间,在每小时内的任
一时刻随机到达车站,求乘客候车时间的数学期望(准确到秒).(C)
A.8 分 40 秒 B.13 分 20 秒 C.10 分 25 秒 D.15 分 30 秒
- 画图，(以下默认以分的位单位，最终结果除外)，期望为：
- \[\dfrac{\dfrac{20^2}{2}+\dfrac{25^2}{2}+\dfrac{15^2}{2}}{60}=625s \]
随机抛硬币，在连续三次得到的结果是正反正时停止。那么期望抛的次数是(D)
A.7 B.8 C.9 D.10
- 设 \(f[i]\) 为现在状态到达最终状态的期望步数。
- \[\begin{cases}f[3]=0\\f[2]=\dfrac{1}{2}(f[3]+1)+\dfrac{1}{2}(f[0]+1)\\f[1]=\dfrac{1}{2}(f[2]+1)+\dfrac{1}{2}(f[1]+1)\\f[0]=\dfrac{1}{2}(f[1]+1)+\dfrac{1}{2}(f[0]+1)\end{cases} \]
- 解得：\(f[0]=10\)
对于集合 \(S\) ，设 \(|S|\) 表示 \(S\) 中的元素个数，而令 \(n(S)\) 表示包括空集和 \(S\) 自身在内的 \(S\) 的子集个数。如果 \(A,B,C\) 三个集合满足 \(n(A)+n(B)+n(C)=n(A\cup B\cup C)\) ，\(|A|=|B|=100\) ，那么 \(|A\cap B\cap C|\) 最小可能值是(B)。
A. 96 B. 97 C. 98 D. 100