1、2.4對于下面的每一步，畫出棧元素與棧頂指針的示意圖：（ 1）棧空（ 2）在棧中插入一個元素 A；（ 3）在棧中插入一個元素 X；（ 4）刪除棧頂元素；（ 5）在棧中插入一個元素 T；（ 6）在棧中插入一個元素 G；（ 7）棧初始化 。解：如圖 2.1 所示。圖 2-1棧元素與棧頂指針的示意圖2.5設循環隊列的容量為70（序號為170），現經過一系列的入隊與退隊運算后，有：（ 1） front=14 ，rear=21（ 2） front=23 ，rear=12問在這兩種情況下，循環隊列中各有多少個元素？解：設循環隊列的容量為m 。如果 rear front，則循環隊列中的元素個數為rear f

2、ront；如果 rear front，則循環隊列中的元素個數為m（ rear front ）。由此可以得到：（ 1）循環隊列中的元素個數為rear front 21 14=7 。（ 2）循環隊列中的元素個數為m（ rear front ） =70（ 1223） =59 。2.6試圖示在表達式A* （B-D） /T+C * * (E * F )執行過程中運算符棧和操作數棧的變化情況。解：（ 1）建立操作數棧OVS（棧頂指針為topv ）與運算符棧OPS（棧頂指針為topp ），其中操作數棧的初始狀態為空，在運算符棧中已壓入一個表達結束符“； ”，如圖 2.2（ a）所示。（ 2）讀出操作數 A

3、進 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.

4、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棧彈出運算符“/ ” ，然后

5、作運算 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，并將運算結果T

6、4 壓入 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棧站頂運

7、算符“ +”的優先級，因此從 OVS 棧依次彈出操作數 T5 與 T3，從 OPS棧彈出運算符“ +”，然后作運算 T6=T3+T5，并將運算結果 T6 壓入 OVS棧，如圖 2.2（1）所示。在這種情況下，運算符“； ”下次將重新考慮。（ 13）運算符“； ”與 OPS棧棧頂的運算符“； ”（它們都是表達式結束符）相遇，彈出OVS棧中的 T8 即為表達式的計算結果，計算過程結束。2.15用三列二維數組表示下列稀疏矩陣（假設數組下標從1 開始）：（1）（ 1）00000500000000001500000-800000-6000A=00000000000130-2000170000000000

8、0004（2）003500000023170000A=000000210-12000000-900015解：對應的3 列二維數組分別為88875716513353115252337-83117（1） B= 45-6（2）B= 5221 641354-1266-271-9721775158842.16下列各三列二維數組分別表示一個稀疏矩陣，試分別寫出與它們對應的稀疏矩陣（假設數組下標從1 開始）：64612446513-613-6(1) 213 (2)1 5 -131522433-8318549449解：對應的稀疏矩陣分別為04-6 000-60-103000040000（1） A= 50-80

9、 (2)A=8 0 0 0 000000000900000900002.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）表達式樹如

10、圖2.4（ a）所示，波蘭表示式為ab-cd*s+/eg*xyz*+wvf/htq+*-+(2)將表達式化成 a*b+c/(d+t)-g*h/r+f(x,y/z,s)（b ）所示，波蘭表示式為。表達式樹如圖2.5（ a）所示，二叉樹如圖2.5ab*cdt+/+gh*r/xyz/sf+-(3)表達式樹如圖（a）所示，二叉樹如圖（b）表達式，波蘭表達式為abcd/+*xy/st-wv*f（ 1）（a b） / （c * d s） e * g / f （ xy * z ， w ， v） h * （1 q）（ 2） a * b c / （ d t） g * h / r f（ x ， y / z ， s

11、）（ 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 中，各節點射出的總數為：4122134115樹 T 中的總結點樹為：15（各結點射出的分支總數）+1（根結點） =16非葉子結點總數為：4+2+1+1=8葉子結點樹為：16（總結點數） -8（非葉子結點總數）2.21已知某二叉樹的前序序列為DBACFEG ，中序序列為=8ABCDEFG 。請畫出該二叉樹，并寫出該二叉樹的后序序列。（D）為

12、分界線，前面的子序列（ABC）一定在左子樹中，后面的子序列（EFG）一定在右子樹中。 同樣的道理， 對于已經劃分出的每一個子序列的左右節點中，位于前序列序列最前面的一個結點為子樹的根節點，而在中序序列中位于該根節點前面的結點構成左子樹上的結點子序列， 位于該根節點后面的結點構成右子樹上的結點子序列。這個處理過程直到所有子序列為空為止。根據上述道理，該二叉樹恢復的過程如圖所示。后序序列為ACBEGFD。2.26 用圖形表示下列數據結構，并指出它們是屬于線性數據結構還是非線性數據結構：(1)B(D , R)111D1 a, b, c, d, e, f R1( a, e),( b, c),( c, a),( e, f ),( f , d )(2) B2( D2, R2)D2 d i |1 i 5R2=( d i ,d j ) | i<j(3) B3(D 3, R3)D3 d i |1 i 5R3=( d i ,d i+1 ) | i=4,3,2,1(4) B4( D4, R4)D4 a,b, c, d, e, f ,gR4( a, b), (c, d ),( b, f ),( d, e),(5) B5( D5, R5)D5 a,b,c, d, e,R5( b, a),( a, c),( c, e),( e, d ),( d , a)解：（ 1）該數據結構為線