清华严蔚敏老师－－数据结构疑难问题讨论

    严老师：双端队列确是好像两个栈底靠在一起的栈，但这两个栈底又是互通的。它确是很灵活，因此不可能出现的出队的序列只可能是四个车厢都已经入队的情况，因为如果队列中只有1个或2个或3个都是能调度过来的，但当4个都进去之后就受一定限制了，对于输入受限的双端队列此时队列中车厢的排列必定是1234,因此尽管两头都能出去，也不可能出现是42**这样的出队序列，而对于输出受限的双端队列，无论怎么进去，在队列中也形不成4132和4231这样的序列。

    学生：您能帮我详细分析一下你习题集上的航空订票的完整的思路吗？我刚学了前两章，感到无从下手，谢了！题目：假设某机场共有m次航班，每次航班有n个座位，且每次航班达到一个目的机场。设计一个满足该机场需要的用户定票、退票程序。

    严老师：一、关于"航空订票"的题，我觉得在该题的实现提示上已经讲得很清楚了，该作业基本上是线性表的查询、插入和删除的练习，只是其中还用到了排队所需的队列及其操作。我不知道你是否已经学了第三章。另外，按你所说"你刚学了前两章",那么你是否以前没有做过类似实习题，如果是这样，我想你最好先作一个实习一的题，如果无从下手，也可以先仿照实习报告示例，自己调通1.3题。

    二、答案就是根据存储密度的定义而得，分子为串本身所占存储量，分母为存储结构所占存储量，结点大小见书78页的定义，"4k"为结点中字符数，"4"为指针占存储量，因此"4(k+1)"是每个结点所占存储量，乘号后面是结点个数。题目中给出的串长分布函数是多余的条件，和存储密度无关。

    学生：严老师，您好！我想请问您，在我们这现在的几个月里，作为复习数据结构，平时我是不是应该多找些题上机多练一下。如果有必要的话，可以针对哪一方面的题练习呢？ 

     严老师：一、是否作练习，作多少，根据你自己的情况而定，你可以请教已经考过的同学的经验之谈;

    二、"前缀表示式"的求值规律是，从左向右判别字符，若是运算符，则入栈，直至连续出现的两个操作数，应和栈顶的运算符构成一个最小表达式即进行运算，"中缀"丢失了原表达式中的括弧信息，无法求值，"后缀表示式"的求值规律最简单，遇操作数则入栈，遇运算符即从栈中连续出栈两个运算符进行运算，当然先出栈的为第二操作数， 表达式树求值即进行后序遍历，清华大学出版社出版的《数据结构及应用算法教程》中有详细算法例子。

    三、关于"清华大学计算机系考研"的问题请查阅相关网站或向该系的业务办公室询问;

    四、也可能这个题从数学上讲不是很严格的，因为当初出这个题的目的是为了复习课本中讲的时间复杂度的概念，因此只能说是h(n)不是O(n4),而是式(4)所表达的，因此从这个角度讲，(2)是错的。

Tag: