发布于

初赛复习：前缀表达式和后缀表达式

前缀表达式和后缀表达式——有时也被成为波兰表达式和逆波兰表达式——是对仅包含二元关系运算符和括号的表达式的变形。

事实上，前缀表达式和后缀表达式没有本质区别，因此只要会了前缀表达式，就会了后缀表达式——记住，前缀表达式是把运算符提到最前面的表达式，而后缀表达式反之。

对于一个这样的式子：
a+b/c
我们按照运算符优先级依次操作：
a+/bc
+a/bc
这样就将所有符号提到了整个式子的最前面。
对于包含括号的表达式，例如：
2+3(4-(5+6))/7 操作流程依然是按照运算符优先级的。 2+3(4-+5 6)/7
2+3(-4+5 6)/7 2+3(-4+5 6)/7
2+/3-4+5 6 7 +2/3-4+5 6 7

而如果要求后缀表达式，那操作就反之——从优先级最低的操作符开始，把操作符提到最右边。
还是一样的例子：
2 3(4-(5+6))/7+ 2 3(4-(5+6))7/+
2 3(4-(5+6))7/+ 2 3(4(5+6)-)7/+
2 3 4 5 6+-*7/+

发布于

初赛复习：OSI七层网络协议

ISO网络协议标准包括七层。

最底层的被称为物理层。这一层主要包括：
光纤、同轴电缆、双绞线、网卡、中继器、集线器
等硬件。它传输的是比特（bit）

物理层之上被称为数据链路层。数据链路层的主要硬件是网桥和交换机，这一层把数据封装成一种被称为帧（frame）的结构。

网络层是第三层。IP地址是这一层的内容。路由器也在这一层。

传输层是网络层之上的第四层。这一层主要管的是数据包的运输。TCP协议和UDP协议都是传输层协议。

会话层是第五层，没看到什么考点。

表示层主要负责数据转换，没看到什么考点。

应用层是最顶层，应用层协议包括Telnet（Windows的远程桌面）、FTP、SNMP（这两个都是远程文件管理系统）、HTTP、DNS（IP地址解析服务）等协议。它是直接展现给用户的一层。

发布于

初赛复习：主定理

对于形如：
$$T(n)=aT(\frac{n}{b})+f(n)$$
那么，我们可以用下述三个公式来刻画\(T(n)\)的渐近上下界。
$$f(n)=\Theta(n^{log_ba-\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(n^{log_ba})$$
$$f(n)=\Theta(n^{log_ba+\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(f(n))$$
$$f(n)=\Theta(n^{log_ba})\Rightarrow T(n)=\Theta(n^{log_ba}logn)$$
换而言之，就是，比较\(f(n)\)和\(\Theta(n^{log_ba})\)的级别。如果两者同级，就乘上一个log，否则就取较大的。