P2
211275022田昊东
2.2
- 顺序表：存储空间利用率高，访问速度快，支持随机访问，插入删除元素慢，大小变更麻烦，开销较大；链表：大小便于动态变化，插入删除元素方便，需要存储指针，空间占用较大，不支持随机访问，访问效率较低。
- 链表存储，因为顺序表使用的是一段固定长度的来纳许空间，如果表的长度动态变化，可能造成数组需要多次开辟空间，会产生高昂的复制开销，因此对于动态的情况更适合使用链表。
- 顺序表，链表由于无法随机访问每次存取都需要进行遍历开销很大。由于很少进行顺序表开销较大的插入、删除，因此使用顺序表效率更高更为适合。
2.3
- 插入：\(\frac1{n+1}\sum_{i=1}^{n+1}(n-i
+1)=\frac n2=63.5\)
- 删除：\(\frac1n\sum_{i=1}^n(n-i)=\frac{n-1}2=63\)
3.1
- 假设第 \(n\) 个数第 \(i\) 个出栈，可能的方案数为 \(f(i-1)*f(n-i)\)，因此总方案数为 \(f(n) = \sum_{i=1}^{i=n}{f(i-1)*f(n-i)}\) ，显然这是一个卡特兰数，通项为 \(f(n) = \frac{C_{2n}^{n}}{n+1}\) ,故 \(f(6)=\frac{924}{7}=132\) 种
-
- 435612：4>2且4先出了栈，这说明12均被压入栈中，因此后面出栈时一定2在1的前面；
- 325641：存在，push123;pop32;push45;pop5;push6;pop6;pop41;
- 154623：不存在，4>3且4先出了栈，这说明23均被压入栈中，因此后面出栈时一定3在2的前面；
- 135426：存在，push1;pop1;push2;push3;pop3;push45;pop542;push6;pop6;
3.2
- 假设这种情况存在，由于 \(p_j\) , \(p_k\) 都在 \(p_i\) 后面出栈，由于 \(p_i>p_k>p_j\) 也就是说在 \(p_i\) 出栈之时 \(p_j\) , \(p_k\) 都在栈中、\(p_k\) 入栈时 \(p_j\) 一定已经在栈中，因此一定 \(p_k\) 比 \(p_j\) 先出栈，这与 \(j<k\) 矛盾。
3.4
- (4):
AB+D\*EFAD\*+/+C+
- (5):
ABC\<CD\>||!&&!CE<||
3.6
- 使用栈st1存储操作符，st2存储结果，接下来从左到右，对字符串的每一位进行处理
- st1:
a
- st1:
+;st2:a
- st1:
+;st2:ab
- st1:
+*;st2:ab
- st1:
+*(;st2:ab
- st1:
+*(;st2:abc
- st1:
+*(-;st2:abc
- st1:
+*(-;st2:abcd
- st1:
+*;st2:abcd-
- st1:
-;st2:abcd-*+
- st1:
-;st2:abcd-*+e
- st1:
-^;st2:abcd-*+e
- st1:
-^;st2:abcd-*+ef
- st1:
-/;st2:abcd-*+ef^
- st1:
-/;st2:abcd-*+ef^g
- st1:
-/;st2:abcd-*+ef^g/-
- 得到后缀表达式
abcd-*+ef^g/-