第2章习题答案
2.4对于下面的每一步，画出栈元素与栈顶指针的示意图：
（1）栈空
（2）在栈中插入一个元素A；
（3）在栈中插入一个元素X；
（4）删除栈顶元素；
（5）在栈中插入一个元素T；
（6）在栈中插入一个元素G；
（7）栈初始化。
解：如图2.1所示。
图2-1 栈元素与栈顶指针的示意图
2.5设循环队列的容量为70（序号为1~70），现经过一系列的入队与退队运算后，有：
（1）front=14，rear=21
（2）front=23，rear=12
问在这两种情况下，循环队列中各有多少个元素？
解：设循环队列的容量为m 。
如果rear＞front ，则循环队列中的元素个数为rear－front ；
如果rear＜front ，则循环队列中的元素个数为m＋（rear－front）。
由此可以得到：
（1）循环队列中的元素个数为rear－front＝21－14=7 。
（2）循环队列中的元素个数为m＋（rear－front）=70＋（12－23）=59 。
2.6试图示在表达式A*（B-D）/T+C * * (E * F ) 执行过程中运算符栈和操作数栈的变化情况。
解：（1）建立操作数栈OVS（栈顶指针为topv）与运算符栈OPS（栈顶指针为topp），其中操作数栈的初始状态为空，在运算符栈中已压入一个表达结束符“；”，如图2.2（a）所示。
（2）读出操作数A进OVS栈，读出运算符“*”进OPS栈，读出左括号“（”进OPS 栈，读出操作数B进OVS栈，读出运算符“－”进OPS栈，读出操作数D进OVS栈，如图2.2（b）所示。
（3）读出右括号“）”，由于右括号“）”的优先级不大于OPS栈栈顶运算符“－”的优先级，因此从OVS栈依次弹出操作数D与B，从OPS栈弹出运算符“－”，然后作运算T1＝B－D，并将运算结果T1压入OVS栈，如图2.2（e）所示。在这种情况下，刚读出的右括号“）”下次将重新考虑。
（4）右括号“）”遇到OPS栈中的左括号“（”，从OPS栈中退出左括号“（”，如图2.2（d）所示。
（5）读出运算符“/ ”，由于运算符“/ ”的优先级不大于OPS栈栈顶运算符“* ”的优先级，因此从OVS栈依次弹出操作数T1与A，从OPS栈弹出运算符“* ”，然后作运算T2=A*T1，，并将运算结果T2压入OVS栈，如图2.2（e）所示。在这种情况下，刚读出的运算符“/ ”下次将重新考虑。
（6）运算符“/ ”进OPS栈，读出操作数T进OVS栈，如图2.2（f）所示。
（7）读出运算符“＋”，由于运算符“＋”的优先级不大于OPS栈栈顶运算符“/ ”的优先级，因此从OVS栈依次弹出操作数T与T2，从OPS栈弹出运算符“/ ”，然后作运算T3=T2/T，并将运算结果T3压入OVS栈，如图2.2（g）所示。在这种情况下，刚读出的运算符“＋”下次将重新考虑。
（8）运算符“+”进OPS栈，读出操作数C进OVS栈，读出运算符“* *”进OPS栈，读出左括号“（”进OPS栈，读出操作数E进OVS栈，读出运算符“*”进OPS栈，读出操作数F进OVS栈，如图2.2（h）所示。
（9）读出右括号“）”，由于右括号“）”的优先级不大于OPS栈栈顶运算符“*”的优先级，因此从OVS栈依次弹出操作数F与E，从OPS栈弹出运算符“*”，然后作运算T4=E*F，并将运算结果T4压入OVS栈，如图2.2（i）所示。在这种情况下，刚读出的右括号“）”下次将重新考虑。
（10）右括号“）”遇到OPS栈中的左括号“（”，从OPS栈中退出左括号“（”，如图2.2（j）所示。
（11）读出运算符“；”，由于运算符“；”的优先级不大于OPS栈栈顶运算符“* *”的优先级，因此从OVS栈依次弹出操作数T4与C，从OPS栈弹出运算符“* *”，然后作运算T5=C* *T4，并将运算结果T5压入OVS栈，如图2.2（k）所示。在这种情况下，刚读出的运算符“；”下次将重新考虑。
（12）运算符“；”的优先级不大于OPS栈站顶运算符“+”的优先级，因此从OVS栈依次弹出操作数T5与T3，从OPS栈弹出运算符“+”，然后作运算T6=T3+T5，并将运算结果T6压入OVS栈，如图2.2（1）所示。在这种情况下，运算符“；”下次将重新考虑。
（13）运算符“；”与OPS栈栈顶的运算符“；”（它们都是表达式结束符）相遇，弹出OVS栈中的T8即为表达式的计算结果，计算过程结束。
2.15 用三列二维数组表示下列稀疏矩阵（假设数组下标从1开始）：
（1）（1）0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
15 0 0 0 0 0 -8 0
0 0 0 0 -6 0 0 0
A=[ 0 0 0 0 0 0 0 0 ]
0 0 0 13 0 -2 0 0
0 17 0 0 0 0 0 0
0 0 0 0 0 0 0 4
（2）0 0 35 0 0
0 0 0 0 23
17 0 0 0 0
A=[ 0 0 0 0 0 ]
0 21 0 -12 0
0 0 0 0 0
-9 0 0 0 15
解：对应的3列二维数组分别为
8 8 8 7 5 7
1 6 5 1 3 35
3 1 15 2 5 23
3 7 -8 3 1 17
（1）B= [ 4 5 -6 ] （2）B=[ 5 2 21 ]
6 4 13 5 4 -12
6 6 -2
7 1 -9
7 2 17 7 5 15
8 8 4
2.16 下列各三列二维数组分别表示一个稀疏矩阵，试分别写出与它们对应的稀疏矩阵（假设数组下标从1开始）：
6 4 6
1 2 4 4 6 5
1 3 -6 1 3 -6
(1) [ 2 1 3 ］ (2)[1 5 -1 ］
3 1 5 2 2 4
3 3 -8 3 1 8
5 4 9 4 4 9
解：对应的稀疏矩阵分别为
0 4 -6 0 0 0 -6 0 -1 0
3 0 0 0 0
4 0 0 0 0
（1）A=[5 0 -8 0 ］ (2) A=[ 8 0 0 0 0 0 ］
0 0 0 0 0 0 0 9 0 0
0 0 0 9
0 0 0 0
2.17 试写出题2.15中两个稀疏矩阵的POS与NUM向量。
解：对应的POS与NUM向量分别为
(2)
2.19 将下列表达式用表达式树表示，再分别转化成二叉树，最后分别写出其波兰表示式：
(1)(a-b)/(c*d+s)+e*g/f(x+y*z,w,v)-h*(t+q)
(2)a*b+c/(d+t)-g*h/r-f(x,y/z,s)
(3)f(a*(b+c/d),x/y,s-t,w*v)
解：（1）表达式树如图2.4（a）所示，波兰表示式为
ab-cd*s+/eg*xyz*+wvf/htq+*-+
(2)将表达式化成[a*b+c/(d+t)]-[g*h/r+f(x,y/z,s)]。表达式树如图2.5（a）所示，二叉树如图2.5（b）所示，波兰表示式为
ab*cdt+/+gh*r/xyz/sf+-
(3)表达式树如图（a）所示，二叉树如图（b）表达式，波兰表达式为
abcd/+*xy/st-wv*f
（1）（a－b）/ （c * d＋s）＋e * g / f（x＋y * z ，w ，v）－h *（1＋q）
（2）a * b＋c / （d＋t）－g * h / r－f（x ，y / z ，s）
（3）f（a *（b＋c / d），x / y ，s－t ，w * v）
2.20 设树T的度为4 ，其中度为1 ，2 ，3 ，4的结点个数分别为4 ，2 ，1 ，1 。问T中有多少个叶子结点？
解：根据给定的条件，在树T中，各节点射出的总数为：
+
+
?
?
4=
+
?
?
4
1
1
15
3
1
2
2
树T中的总结点树为：
15（各结点射出的分支总数）+1（根结点）=16
非叶子结点总数为：
4+2+1+1=8
叶子结点树为：
16（总结点数）-8（非叶子结点总数）=8
2.21 已知某二叉树的前序序列为DBACFEG ，中序序列为ABCDEFG 。请画出该二叉树，并写出该二叉树的后序序列。
（D）为分界线，前面的子序列（ABC）一定在左子树中，后面的子序列（EFG）一定在右子树中。同样的道理，对于已经划分出的每一个子序列的左右节点中，位于前序列序列最前面的一个结点为子树的根节点，而在中序序列中位于该根节点前面的结点构成左子树上的结点
子序列，位于该根节点后面的结点构成右子树上的结点子序列。这个处理过程直到所有子序
列为空为止。
根据上述道理，该二叉树恢复的过程如图所示。 后序序列为ACBEGFD 。
2.26 用图形表示下列数据结构，并指出它们是属于线性数据结构还是非线性数据结构：
11111
2
2
2
2
2
3
3
3
3
3
i+14
4
4
44
(1)(,)
{,,,,,}
{(,),(,),(,),(,),(,)}(2)(,){|15}={(,) | i ={(,) | i=4,3,2,1}(4)(,){,,,,,,} {(,),i i j i i a b c d e f a e b c c a e f f d i i a b c d e f g a b B D R D R B D R d D d d R B D R d D d d R B D R D R =====≤≤==≤≤===5 5 5 55 (,),(,),(,),}(5)(,){,,,,,} {(,),(,),(,),(,),(,)}c d b f d e a b c d e b a a c c e e d d a B D R D R === 解：（1） 该数据结构为线性结构 （2） 该数据结构为非线性。 （3） 该数据结构为线性结构。 （4） 该数据结构为非线性结构。 （5） 该数据结构为非线性结构。 2.27 写出下列各算术表达式的波兰表示式： (1)A (B C)+T/(D+E)F/(S H)(2)A/(B (E+F))T (3)()/()()()K A B C D E F T R *--**-**+-+-*- (1)////(2)/(3)/ABC TDE FSH ABC TDE FSH ABEF TK AB CD EF TR -*++*--*+*-++***-+---*+ 解：或