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

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

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

对于一个这样的式子:
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的远程桌面)、FTPSNMP(这两个都是远程文件管理系统)、HTTPDNS(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,否则就取较大的。