一般练习

1. 复习下面概念：容器，元素，容器数据结构，栈（堆栈），队列（队），缓冲存储（缓存），后进先出（LIFO，后进先出表），先进先出（FIFO），实现结构，入栈（压入）操作，出栈（弹出）操作，栈顶，栈底，括号匹配问题，表达式的中缀表示（前缀表示，后缀表示），波兰表达式，逆波兰表达式，表达式求值，表达式形式转换，运算符栈，数据栈，函数的递归定义，递归结构，递归调用，运行栈，函数帧（栈帧），入队，出队，循环顺序表，数据不变式，消息，消息驱动的系统，消息队列，离散事件系统和模拟，迷宫问题，当前位置，探查，回溯法，搜索，状态空间搜索，路径搜索，通用问题求解方法，深度优先搜索，宽度优先搜索，最优解，双端队列（deque）。

2. 考虑符号a, b, c, d按顺序进栈，允许在进栈过程中任意插入弹出操作。请列出这样做可能产生的所有出栈元素序列。

3. 如果栈的压入序列为1, 2, 3, 4, 5，则下面哪个（哪些）不可能是栈的弹出序列：

a) 2, 3, 4, 1, 5 b) 5, 4, 1, 3, 2 c) 2, 3, 1, 4, 5 d) 1, 5, 4, 3, 2

4. 设顺序将整数1, 2, 3, …, n压入栈中，并全部弹出形成的输出序列是 。如果是整数k，那么可能是什么？如果是整数k，那么可能是什么？

5. 在前一题目的假设下，产生的输出序列中不可能出现，使得。请设法证明这个结论。

6. 把下面中缀表达式翻译为与之等价的前缀形式：

(a + b) * (c - d)

2 * (a + b) / c / d

7. 把下面后缀表达式翻译为与之等价的中缀形式：

a b c / f d - * 3 r / + -

2 a + b / c d - e f - * /

8. 写出下面数学表达式的前缀形式和后缀形式：

1 ＋ (2 － 3 ×5) / 4

(7 ＋ 4) × (2 － 6 / 3) ＋ 4

9. 假设火车调度场有一个Y形调度线，其一条支线上有一列客车车厢，其中任意交错出现硬座车厢和卧铺车厢，现需要将它们重新排列为硬座在前卧铺在后的一列客车，从另一支线推出。这里只有一个车头在Y形铁路顶端，请为其设计一个调度算法。

10. 将1, 2, 3, 4作为双端队列输入数据（可在加入任一端），存在多少种可能的输出序列？如果输入数据是1, 2, 3, 4, 5，情况怎么样？

编程练习

1. 改造5.3节的括号匹配检查函数，让它从指定文件读入数据，在发现不匹配时，不仅输出不匹配的括号，还输出该括号在原文件里的行号和字符位置。

2. 请修改前一题完成的函数，使之可以检查实际Python程序里的三种括号匹配。

3. 考察Python语言标准，改进中缀表达式到后缀表达式里的tokens生成器，使之能更好地处理所有符合Python语法的算术表达式。

4. 请定义一个函数，它组合使用正文讨论的中缀表达式到后缀表达式的转换函数和后缀表达式的求值函数，实现对中缀表达式的求值功能。

5. 请定义一个独立的中缀表达式求值函数，不经过后缀表达式转换。注意，一种技术如本章5.3.2节中讨论的，使用两个栈，一个存储运算对象和计算的中间结果，另一个存储尚未处理的运算符。也可以考虑只用一个栈的方法。

6. 请定义一个函数，它的输入是一个后缀表达式，输出是一个加了所有括号的中缀表达式。这里不考虑括号的必要性，加进所有括号可保证计算顺序正确。请分析算法的时间和空间复杂度。

7. 设法实现一个不用递归的背包求解函数。实现该算法的关键在需要考虑两种递归情况时，必须把一种可能保存起来，然后按另一可能继续走下去。如果按一种可能做下去能得到结论，保留的信息都可以丢掉；否则就需要找到最近的另一种可能安排，检查能否从这里找到解。这里还有一个难点是如何输出合格的物品配置。

8. 有一个非常著名的函数称为Ackerman函数，其特点是函数值增长的特别快。该函数的定义如下：

a) 请定义一个递归函数实现Ackerman函数；

b) 请定义一个非递归函数实现Ackerman函数；

c) 请画出用非递归函数计算Ack(2, 1) 的过程中栈的变化情况。

9. 请详尽描述第5.4.3节说明的队列实现的数据不变式，请基于这组不变式实现一个队列，并逐一验证每个操作都满足有关不变式的要求。

10. 请基于顺序表技术实现一种双端队列结构，保证其两端插入和删除均为常量时间操作。

11. 双端队列的一种显然实现方法是采用双链表技术，请做出这种实现。

12. 八皇后问题（参考右边图示）：国际象棋的棋盘为8行8列64个格子，棋子置于格中。皇后是国际象棋里威力最强大的棋子，可以在直、横和两个斜线方向上攻击其他棋子。八皇后问题要求在棋盘上为八个皇后安排位置，使之不能相互攻击。例如，右图（上）给出的是问题的一个解。请为求解这个问题设计一套适当的数据表示，并实现一个求解该问题的非递归程序。进而：

a) 修改上面定义的函数，使之可以产生出所有满足条件的皇后布局。

b) 修改上面工作使之能处理一般的n皇后问题。

13. 骑士周游问题：国际象棋中的骑士，行棋方式与中国象棋中的马类似，走“日”字。现在的问题是在国际象棋棋盘上为骑士找到一条路径，使之可以经过棋盘的每个格子恰好一次。右图（下）是这个问题的一个解。请定义一个非递归函数求解这个问题，函数的参数是骑士的初始位置，程序求出路径，返回途经位置的表。

14. 请设法统计在骑士周游过程中程序回溯的步数及其随着已走路径长度的变化而变化的趋势：

a) 你可能发现，随着剩余结点越来越少，回溯的情况会越来越多，连续回溯的步数也会越来越长。请分析这里的原因，设法提出缓解方法

b) 请修改所用搜索方法，加入适当的分支选择策略，提高求解程序的效率。