第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=[00000900015解：对应的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+-体现式树如图（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中，各节点射出的总数为：树T中的总结点树为：15（各结点射出的分支总数）+1（根结点）=16非叶子结点总数为：4+2+1+1=8叶子结点树为：16（总结点数）-8（非叶子结点总数）=82.21已知某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG。请画出该二叉树，并写出该二叉树的后序序列。（D）为分界线，前面的子序列（ABC）一定在左子树中，背面的子序列（EFG）一定在右子树中。同样的道理，对于已经划分出的每一种子序列的左右节点中，位于前序列序列最前面的一种结点为子树的根节点，而在中序序列中位于该根节点前面的结点构成左子树上的结点子序列，位于该根节点背面的结点构成右子树上的结点子序列。这个处理过程直到所有子序列为空为止。根据上述道理，该二叉树恢复的过程如图所示。后序序列为ACBEGFD。2.26用图形表达下列数据