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

1、第三章第三章棧和隊(duì)列棧和隊(duì)列一、選擇題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、這個(gè)數(shù)是前序序列為123…n，所能得到的不相似的二叉樹的數(shù)目。三、填空題1、操作受限（或限定僅在表尾進(jìn)行插入和刪除操作）后進(jìn)先出2、棧3、3124、23100CH5、0n1top[1]1=top[2]6、兩棧頂指針值相減的絕對(duì)值為1（或兩棧頂指針相鄰）。7、(1)滿(2)空(3)n(4)棧底(5

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

4、rnext=s；r=s；18、犧牲一個(gè)存儲(chǔ)單元設(shè)標(biāo)記19、（TAIL1）MODM=FRONT(數(shù)組下標(biāo)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四、應(yīng)用題1、棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進(jìn)先出（LIFO）表。2、隊(duì)列是

6、允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊(duì)尾，允許刪除的一端叫隊(duì)頭。最先插入隊(duì)的元素最先離開（刪除），故隊(duì)列也常稱先進(jìn)先出（FIFO）表。3、用常規(guī)意義下順序存儲(chǔ)結(jié)構(gòu)的一維數(shù)組表示隊(duì)列，由于隊(duì)列的性質(zhì)（隊(duì)尾插入和隊(duì)頭刪除），容易造成“假溢出”現(xiàn)象，即隊(duì)尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而13、函數(shù)調(diào)用結(jié)束時(shí)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)用自身時(shí)，過程p由內(nèi)部定義的局部變量在p的2次調(diào)用期間，不占同一數(shù)據(jù)區(qū)。每次調(diào)用都保留其數(shù)據(jù)區(qū)，這是遞歸定義所決定，用“遞歸工作棧”來實(shí)現(xiàn)。15、設(shè)Hn為n個(gè)盤子的Hanoi塔的移動(dòng)次數(shù)。(假定n個(gè)盤子從鋼針X移到鋼針Z，可借助鋼針Y)則Hn=2Hn11先將n1個(gè)盤子從X移到Y(jié)，第n個(gè)盤子移到Z，再將那n1個(gè)移到Z

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