第2章習(xí)題答案

2.4對于下面的每一步，畫出棧元素與棧頂指針的示意圖：（1）?？眨?）在棧中插入一個元素A；（3）在棧中插入一個元素X；（4）刪除棧頂元素；（5）在棧中插入一個元素T；（6）在棧中插入一個元素G；（7）棧初始化。解：如圖2.1所示。圖2-1棧元素與棧頂指針的示意圖2.5設(shè)循環(huán)隊列的容量為70（序號為1~70），現(xiàn)經(jīng)過一系列的入隊與退隊運算后，有：（1）front=14，rear=21（2）front=23，rear=12問在這兩種情況下，循環(huán)隊列中各有多少個元素？解：設(shè)循環(huán)隊列的容量為m。如果rear＞front，則循環(huán)隊列中的元素個數(shù)為rear－front；如果rear＜front，則循環(huán)隊列中的元素個數(shù)為m＋（rear－front）。由此可以得到：（1）循環(huán)隊列中的元素個數(shù)為rear－front＝21－14=7。（2）循環(huán)隊列中的元素個數(shù)為m＋（rear－front）=70＋（12－23）=59。2.6試圖示在表達式A*（B-D）/T+C**(E*F)執(zhí)行過程中運算符棧和操作數(shù)棧的變化情況。解：（1）建立操作數(shù)棧OVS（棧頂指針為topv）與運算符棧OPS（棧頂指針為topp），其中操作數(shù)棧的初始狀態(tài)為空，在運算符棧中已壓入一個表達結(jié)束符“；”，如圖2.2（a）所示。(2)K1234POS(k)1345NUM(k)21112.19將下列表達式用表達式樹表示，再分別轉(zhuǎn)化成二叉樹，最后分別寫出其波蘭表示式：(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(huán)*（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設(shè)樹T的度為4，其中度為1，2，3，4的結(jié)點個數(shù)分別為4，2，1，1。問T中有多少個葉子結(jié)點？解：根據(jù)給定的條件，在樹T中，各節(jié)點射出的總數(shù)為：樹T中的總結(jié)點樹為：15（各結(jié)點射出的分支總數(shù)）+1（根結(jié)點）=16非葉子結(jié)點總數(shù)為：4+2+1+1=8葉子結(jié)點樹為：16（總結(jié)點數(shù)）-8（非葉子結(jié)點總數(shù)）=82.21已知某二叉樹的前序序列為DBACFEG，中序序列為ABCDEFG。請畫出該二叉樹，并寫出該二叉樹的后序序列。（D）為分界線，前面的子序列（ABC）一定在左子樹中，后面的子序列（EFG）一定在右子樹中。同樣的道理，對于已經(jīng)劃分出的每一個子序列的左右節(jié)點中，位于前序列序列最前面的一個結(jié)點為子樹的根節(jié)點，而在中序序列中位于該根節(jié)點前面的結(jié)點構(gòu)成左子樹上的結(jié)點子序列，位于該根節(jié)點后面的結(jié)點構(gòu)成右子樹上的結(jié)點子序列。這個處理過程直到所有子序列為空為止。根據(jù)上述道理，該二叉樹恢復(fù)的過程如圖所示。后序序列為ACBEGFD。2.26用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性數(shù)據(jù)結(jié)構(gòu)還是非線性數(shù)據(jù)結(jié)構(gòu)：解：（1）該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)（2）該數(shù)據(jù)結(jié)構(gòu)為非線性。（3）該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。（4）