數(shù)據(jù)結(jié)構(gòu) 習題 第三章 棧和隊列 答案

1、第三章第三章棧和隊列棧和隊列一、選擇題1.B2.1B2.2A2.3B2.4D2.5.C3.B4.D5.D6.C7.D8.B9.D10.D11.D12.C13.B14.C15.B16.D17.B18.B19.B20.D21.D22.D23.D24.C25.A26.A27.D28.B29.BD30.C31.B32.C33.1B33.2A33.3C33.4C33.5F34.C35.C36.A37.AD二、判斷題1.√2.√3.√4.√5.6.

2、√7.√8.√9.√10.11.√12.13.14.15.√16.17.√18.19.√20.√部分答案解釋如下。1、尾遞歸的消除就不需用棧2、這個數(shù)是前序序列為123…n，所能得到的不相似的二叉樹的數(shù)目。三、填空題1、操作受限（或限定僅在表尾進行插入和刪除操作）后進先出2、棧3、3124、23100CH5、0n1top[1]1=top[2]6、兩棧頂指針值相減的絕對值為1（或兩棧頂指針相鄰）。7、(1)滿(2)空(3)n(4)棧底(5

3、)兩棧頂指針相鄰（即值之差的絕對值為1）8、鏈式存儲結(jié)構(gòu)9、SSSS10、data[top]=x；11、23.12.32434.57108.9（注：表達式中的點(.)表示將數(shù)隔開，如23.12.3是三個數(shù)）12、假溢出時大量移動數(shù)據(jù)元素。13、(M1)MODN(M1)%N；14、隊列15、先進先出16、先進先出17、s=(LinkedList)malloc(sizeofsizeof(LNode))；sdata=xsnext=rnext；

4、rnext=s；r=s；18、犧牲一個存儲單元設(shè)標記19、（TAIL1）MODM=FRONT(數(shù)組下標0到M1，若一定使用1到M，則取模為0者，值改取M20、sq.front=(sq.front1)%(M1)；returnreturn(sq.data(sq.front))；(sq.rear1)%(M1)==sq.front；21、棧22、（rearfrontm）%m；23、（RPN）%N；24、（1）a[i]或a[1]（2）a[i]（3

5、）pop（s）或s[1]；25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b））26、（1）T0（2）i0（4）topn（5）top1（6）true（7）i1（8）top1（9）Tw[i]（10）false四、應用題1、棧是只準在一端進行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進先出（LIFO）表。2、隊列是

6、允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許刪除的一端叫隊頭。最先插入隊的元素最先離開（刪除），故隊列也常稱先進先出（FIFO）表。3、用常規(guī)意義下順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)（隊尾插入和隊頭刪除），容易造成“假溢出”現(xiàn)象，即隊尾已到達一維數(shù)組的高下標，不能再插入，然而13、函數(shù)調(diào)用結(jié)束時vol=14。執(zhí)行過程圖示如下：vol（4）vol(4)=vol(3)514=vol(2)35=vol(1)43

7、5vol（3）5=vol(0)24359=02435=14vol（2）36vol（1）42vol（0）2014、過程p遞歸調(diào)用自身時，過程p由內(nèi)部定義的局部變量在p的2次調(diào)用期間，不占同一數(shù)據(jù)區(qū)。每次調(diào)用都保留其數(shù)據(jù)區(qū)，這是遞歸定義所決定，用“遞歸工作?！眮韺崿F(xiàn)。15、設(shè)Hn為n個盤子的Hanoi塔的移動次數(shù)。(假定n個盤子從鋼針X移到鋼針Z，可借助鋼針Y)則Hn=2Hn11先將n1個盤子從X移到Y(jié)，第n個盤子移到Z，再將那n1個移到Z

8、=2（2Hn21）1=22Hn221=22（2Hn31）21=23Hn32221=2kHnk2k12k2…2120=2n1H12n22n3…2120因為H1=1，所以原式Hn=2n12n2…2120=2n1故總盤數(shù)為n的Hanoi塔的移動次數(shù)是2n1。16、運行結(jié)果為：1213121（注：運行結(jié)果是每行一個數(shù)，為節(jié)省篇幅，放到一行。）17、兩棧共享一向量空間（一維數(shù)組），棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設(shè)共享數(shù)組為S[MAX]，