第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）00000500000000001500000-800000-6000A=[00000000]000130-20001700000000000004（2）003500000023170000A=[00000]0210-12000000-900015解：对应的3列二维数组分别为88875716513353115252337-83117（1）B=[45-6]（2）B=[5221]641354-1266-271-9721775158842.16下列各三列二维数组分别表示一个稀疏矩阵，试分别写出与它们对应的稀疏矩阵（假设数组下标从1开始）：64612446513-613-6(1)[213］(2)[15-1］31522433-8318549449解：对应的稀疏矩阵分别为04-6000-60-103000040000（1）A=[50-80］(2)A=[800000］0000000900000900002.17试写出题2.15中两个稀疏矩阵的POS与NUM向量。解：对应的POS与NUM向量分别为（1）k123456POS(k)134667NUM(k)212010(2)K1234POS(k)1345NUM(k)21112.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中，各节点射出的总数为：1514312214树T中的总结点树为：15（各结点射出的分支总数）+1（根结点）=16非叶子结点总数为：4+2+1+1=8叶子结点树为：16（总结点数）-8（非叶子结点总数）=82.21已知某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG。请画出该二叉树，并写出该二叉树的后序序列。（D）为分界线，前面的子序列（ABC）一定在左子树中，后面的子序列（EFG）一定在右子树中。同样的道理，对于已经划分出的每一个子序列的左右节点中，位于前序列序列最前面的一个结点为子树的根节点，而在中序序列中位于该根节点前面的结点构成左子树上的结点子序列，位于该根节点后面的结点构成右子树上的结点子序列。这个处理过程直到所有子序列为空为止。根据上述道理，该二叉树恢复的过程如图所示。后序序列为ACBEGFD。2.26用图形表示下列数据结构，并指出它们是属于线性数据结构还是非线性数据结构：111112222233333i+144444(1)(,){,,,,,}{(,),(,),(,),(,),(,)}(2)(,){|15}={(,)|ij}(3)(,){|15}={(,)|i=4,3,2,1}(4)(,){,,,,,,}{(,),iijiiabcdefaebccaeffdiiabcdefgabBDRDRBDRdDddRBDRdDddRBDRDR55555(,),(,),(,),}(5)(,){,,,,,}{(,),(,),(,),(,),(,)}cdbfdeabcdebaacceeddaBDRDR解：（1）该数据结构为线性结构（2）该数据结构为非线性。（3）该数据结构为线性结构。（4）该数据结构为非线性结构。（5）该数据结构为非线性结构。2.27写出下列各算术表达式的波兰表示式：(1)A(BC)+T/(D+E)F/(SH)(2)A/(B(E+F))T(3)()/()()()KABCDEFTR(1)////(2)/(3)/ABCTDEFSHABCTDEFSHABEFTKABCDEFTR解：或