第2章习题答案

《第2章习题答案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、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，则循环队列中的元素个数为rea

2、r－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）读出操

3、作数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）所示。

4、（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，并将运算结

5、果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）所示。在这种情况下，刚读出

6、的右括号“）”下次将重新考虑。（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栈弹出运算符

7、“+”，然后作运算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]0

8、210-12000000-900015解：对应的3列二维数组分别为88875716513353115252337-83117（1）B=[45-6]（2