聊些初赛
ccjjxx
·
·
个人记录
今天是9月16号，两天之后就要初赛了.今天在这里来聊聊些教练有可能没有讲到的，但是，却是考点的东西吧
本文使用了些\KaTeX，可能导致加载过慢！
1.编程语言类型
编译型编程语言:
#### 解释型编程语言:
$\mathtt{Python}$、$\mathtt{Ruby}$与$\mathtt{Shell}$等
#### 面向对象程序设计语言：
$\mathtt{Smalltalk}$、$\mathtt{Eiffel}$、$\mathtt{C}$++、$\mathtt{Java}
2.前、中、后缀表达式
例：$\text{1-(2+3)}$ $\to$ $\text{-1+23}
\text{(a+b)*(c+d)}$ $\to$ $\text{*+ab+cd}
（2） 中缀表达式最简单，就是我们日常用的那一种了
（3） 后缀表达式（逆波兰式）：将运算符写在操作数之后
例：\text{(a+b)*c-(a+b)/e} \ \ \ \to \ \ \ \text{ab+c*ab+e/-}
一个例题:
表达式 \texttt{a*(b+c)*d}的后缀表达式为( )，其中 \texttt{*} 和 \texttt{ + }是运算符。
A. \texttt{**a+bcd}
B. \texttt{abc+*d*}
C. \texttt{abc+d**}
D. \texttt{*a*+bcd}
答案：
\colorbox{white}{\large\color{white}B}
3.各种排序算法的时间复杂度及稳定性
选择排序\large\mathcal{O} \verb!(x^2)! 不稳定
桶排序 \large\mathcal{O} \verb!(n+k)! 稳定
冒泡排序\large\mathcal{O} \verb!(x^2)! 稳定
插入排序\large\mathcal{O} \verb!(x^2)! 稳定
归并排序\large\mathcal{O} \verb!(n log n)! 稳定
快速排序\large\mathcal{O} \verb!(n log n)! 不稳定
4.位运算
1.与：\land 或者 \And
0\land0=0 \ \ 1\land0=0\ \ 1\land1=1
2.或：\lor 或者 |
0\lor0=0 \ \ 1\lor1=1 \ \ 0\lor1=1
5.排列组合
排列：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数。
\LARGE A^m_n\large=n(n-1)(n-2)\dotsi(n-m+1)=\frac{\large n!}{(\large n-m)!}
例子：1,2,3\to取2个的排列：
\to1,2
\to1.3
\to2.1
\to2.3
\to3.1
\to3.2
一共有6种， A^2_3=\frac{3!}{(3-2)!}=3\times2\times1\div1=6，显然正确。
组合：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。
\LARGE C^m_n\large=\frac{\large A^m_n}{\large m!}=\frac{\large n!}{\large m!(n-m)!} \ \ , C^m_n=C^{n-m}_n
例子：1,2,3\to取2个的组合：
\to1,2
\to1.3
\to2.3
一共有3种， c^2_3=\frac{3!}{2!(3-2)!}=3\times2\times1\div2=3，显然正确。
5.反码与补码
反码：
对于正数，反码与原码相同
对于负数，除符号位仍为1，其余各位1换成0，0换成1；
例如-11101001->10010110
补码：
正数：本身
负数：两头1不变，中间取反
视频空间
存储空间大小 = 视频时长 × 帧率 × 每帧图像大小 × 压缩率
深度优先遍历是一种图的遍历算法，用于遍历图中的所有节点。对于一个具有 n 个顶点和 m 条边的连通图，如果采用邻接矩阵存储结构，进行深度优先遍历的时间复杂度为 O(n^2)，即平方级别的时间复杂度。
6.一些杂项（常识）
1946年 美国宾夕法尼亚大学
- 第一台具有存储功能的计算机：\text {ECVAC \ ecvac}
冯诺依曼（匈牙利人）依据存储程序的工作原理设计
-
-
董铁宝：中国第一个程序员，王选的老师
-
计算机发展：
$\ \ \ \ \ \ \ \ \ \ \ \ $第二代：$\tt {1958~1964}$ 晶体管
$\ \ \ \ \ \ \ \ \ \ \ \ $第三代：$\tt {1964~1975}$ 中小规模集成电路
$\ \ \ \ \ \ \ \ \ \ \ \ $第四代：$\tt{1975}$至今 大规模、超大规模集成电路
* 存储器：
$\ \ \ \ \ \ \ \ \ \ \ \ $外存：
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 硬盘、光盘、软盘、U盘
$\ \ \ \ \ \ \ \ \ \ \ \ $内存：
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \tt {ROM}$：只读存储器
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \tt {RAM}$：随机存取存储器
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $高速缓存器：$\tt {cache}
$\ \ \ \ \ \ \ \ \ \ \ \ $寄存器$(\text {register})>cache>RAM>$硬盘
* 计算机三总线：
$\ \ \ \ \ \ \ \ \ \ \ \ $地址总线
$\ \ \ \ \ \ \ \ \ \ \ \ $数据总线
$\ \ \ \ \ \ \ \ \ \ \ \ $控制总线
* 计算机语言：
$\ \ \ \ \ \ \ \ \ \ \ \ $机器语言
$\ \ \ \ \ \ \ \ \ \ \ \ $汇编语言
$\ \ \ \ \ \ \ \ \ \ \ \ $高级语言$\text {c,c++,c--,vb}
\frak{set}$ $\frak{up}$ $\frak{on}$ $\frak{22.9.16}
未完待续……