学堂在线数据结构上4

第4章 栈与队列
a.栈接口与实现
1.栈S初始为空，进行以下操作后从栈顶到栈底的元素依次为：
S.push(5);S.push(4);S.pop();S.push(2);S.pop();S.pop();S.push(1)
答案：1
解析：先输入5，后输入4，然后弹出4，然后输入2，然后弹出2，然后弹出5，然后输入1，最终只有1

c1.栈应用：进制转换
1.16进制数AF的二进制为：10101111

c2.栈应用：括号匹配
1.当扫描到一个左括号时：进栈

c3.栈应用：栈混洗
1.{3,1,2,4}是否是{1,2,3,4}的栈混洗？不是

2.长度为4的序列共有多少个不同的栈混洗？14

c4.栈应用：中缀表达式求值
1.什么时候进行实际的运算？当前的操作符比栈顶的操作符优先级低

c5.栈应用：逆波兰表达式
1.逆波兰表达式的求值算法中，什么时候进行一次实际的运算？
答案：每遇到一个新的操作符

2.逆波兰表达式 1 5 +6

本章测试
1.栈初始为空，依次经过以下操作：
push(5);push(8);pop();push(5);top();push(1);push(3);pop();
pop();push(2);
此时从栈顶到栈底依次为：2,5，5

2.:面是队列的一种基于向量的实现(向量的接口和实现可参考第2章)：对于规模为n的该队列，enqueue()和dequeue()的最坏时间复杂度分别为：

O(n),O(1)
解析：如此实现的队列enqueue()需要移动后继中的n个元素。

3.下面是某种数据结构，它用2个栈实现，支持添加、删除元素的操作：

当T为整数时，对初始为空的以上数据结构依次执行以下操作：

此时XXX中唯一剩下的元素是：11
解析：enqueue()的复杂度为O(1)，单次dequeue()的最坏时间复杂度为Ω(n)，但分摊复杂度为O(1)

4.下面是某种数据结构，它用2个队列实现，支持添加、删除元素的操作

当T为整数时，对初始为空的以上数据结构依次执行以下操作：

此时XXX中唯一剩下的元素是：2
解析：该数据结构即为栈，只不过规模为n时，其pop()的时间复杂度高达Ω(n)

5.阅读下面函数(其中1≤x, y≤16)，指出其功能：

打印十进制整数x的y进制表示
解析：该函数是进制转换的递归版。

6.对序列{2, 3, 5, 7, 11}进行栈混洗得到{3, 5, 2, 11, 7}的过程中用于中转的栈S进行的操作是:
push, push, pop, push, pop, pop, push, push pop, pop

7.下列哪一个序列一定不是{1,2,3… i…j…k…n}的栈混洗：
答案：{… k…i…j…}
解析：若要通过栈混洗产生{… k…i…j…}，则k进入目标栈时i,j必然在中间栈且j相对于i在栈的上方。由“先进后出”，j必定先于i进入目标栈，故不可能产生{… k…i…j…}。（也可以考虑i,j,k相邻的特殊情形来解答）

8.以下几个量中相等的是:
① 不同的n位二进制数个数
② 对小括号所能构成的合法括号匹配个数
③ {1, 2 … n}的不同栈混洗个数
④ 含n个运算符的中缀表达式求值过程中运算符栈push操作的次数
答案：②③
解析：栈混洗中的push和pop分别对应于括号匹配中的”( ”和”) ”,故它们数量相等.(①为2^n,②为 Catalan(n),③ 为Catalan(n),④≤n)

9.在中缀表达式求值中，某时刻运算数栈从栈顶到栈底依次为:6，2，1
运算符栈从栈顶到栈底依次为:×,+,(剩下的待处理表达式为 ????/(4×5−7)
在接下来的过程中运算符的入栈顺序以及最终的计算结果分别为：
答案：最终结果为1
解析：最初的表达式是(1+2×6)/(4×5-7)。

10.(1+2×3!)/(4×5−7)的逆波兰表达式为(表达式中的整数都是一位数)
答案：123!×+45×7−/
解析：AB+A+B的逆波兰表达式为AB+