1表达式3*2^（4+2*2—6*3）-5求值过程中当扫描到6时，对象栈和算符栈为（）。
2.已知输入序列为abcd经过输出双限的双向队列后能得到的输出队列（）。
解:
此题用两个栈,栈opnd存放操作数,栈optr存放运算符,并利用书P53的运算符间的优先关系,运算符"^"<运算符"*"（“^”异或运算符)
操作思想:
每次从表达式中取一个字符ch,ch是数字则入栈到opnd,ch是运算符时,则
当optr栈顶的运算符<ch,ch入栈optr,
当optr栈顶的运算符>ch,opnd出栈两个数,optr出栈一个运算符,且做运算,然后将结果入栈opnd
......
对象栈: 6 8
运算符栈: #^(-
2已知输入序列为abcd经过输出双限的双向队列后能得到的输出队列（）。
解:
输出受限的双端队列,即删除限制在一端进行,而插入仍允许在两端进行.
输入受限的双端队列,即插入限制在一端进行,而删除仍允许在两端进行.
参考答案:
由于队列输出受限，故只能在一端进行输出：
分析答案A：A的输入序列为abcd，输出结果为dacb ，由输出受限性质可知da开头的结果只有dabc；A项为错误答案；
分析答案B：B的输出结果为：cadb ；其输入输出顺序为(可以画图帮助理解)：先输入a，然后在非输出端输入b，这时队列的序列为ba（假设左端为限制端，下同),接着在输入端输入c，这时队列的序列为bac,输出c，再输出a，在输出端输入d，这时队列的序列为bd,
输出d，输出b；得到输出序列为cadb；
分析答案D：先输入a，接着在输出端输入b，然后再另一端输入c，最后在输出端输入d，这时队列的序列为cabd；其输出结果为dbac；
分析答案C：由db开头的输出结果只有dbac；故错误；
3.设栈s和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,d6依次通过栈s,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈s的容量至少是（）。
解:
此题考的是栈和队列操作特点.栈是先进后出,队列是先进先出
所以,从6个元素出队的序列是e2,e4,e3,e6,e5,e1,可以知道出栈的顺序应该是e2,e4,e3,e6,e5,e1,当栈中存放的元素为e1,e3,e5,e6时占的空间是最大，所以容量至少是4。
4 解:若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除一个元素
最节省时间的结构：带头结点的双循环链表
这种结构很容易建立当前结点之间的关系，不用再通过遍历来寻找合适的位置。
5模式串T=‘abcaabbcabcaabdab’,计算该模式串的next值。
解：abcaabbcabcaabdab 01
ab|caabbcabcaabdab 011
abc|aabbcabcaabdab 0111
a bc a|abbcabcaabda
b 01112
a bca a|bbcabcaabda
b 011122
ab ca ab|bcabcaabdab 0111223
abcaabb|cabcaabdab 01112231
abcaabbc|abcaabdab 011122311
a bcaabbc a|bcaabda
b 0111223112
ab caabbc ab|caabdab 01112231123
abc aabbc abc|aabdab 011122311234
abca abbc abca|abdab 0111223112345
abcaa bbc abcaa|bdab 01112231123456
abcaab bc abcaab|dab 011122311234567
abcaabbcabcaabd|ab 0111223112345671
a bcaabbcabcaabd a|
b 01112231123456712
6. 23+（（12*3-2)/4+34*5/7）+108/9的后缀表达式是（）。
解：比较简单的方式就是用二叉树将其画出来（从下往上画，参考书P129），再通过后序遍历得到遍历的序列就是此表达式的后缀式。
7用一维数组存放的一棵完全二叉树为ABCDEFGHIGKL.请写出后续遍历该二叉树的访问结点序列。
解：先按照层次把完全二叉树画出来（与满二叉树类似编号一一对应），然后对此二叉树进行后序遍历得到序列。
得到的序列：HIDGKEBLFGCA
8
解：中序遍历：先遍历左子树，再遍历根，然后遍历右子树。
后序遍历：先遍历左子树，再遍历右子树，然后遍历根。
9
解：对序列（15,9,7,8,20，-1,7,4）进行希尔排序的过程：
选用的增量向量：4，2，1（一个希尔排序算法的一个实现，初次取序列的一半为增量，以后每次减半，直到增量为1）注:也可以选用其他的增量向量
算法思想:
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。
如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。
D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。
当增量减到1时,整个要排序的数被分成一组，排序完成。
过程：
15 9 7 8 20 -1 7 4
15 -1 7 4 20 9 7 8
7 -1 7 4 15 8 20 9
-1 4 7 7 8 9 15 20。