第三章棧和佇列
一、選擇題
二、判斷題
部分答案解釋如下。
1、尾遞迴的消除就不需用棧
2、這個數是前序序列為1,2,3,…,n，所能得到的不相似的二叉樹的數目。
三、填空題
1、操作受限（或限定僅在表尾進行插入和刪除操作）後進先出
2、棧3、3 1 24、23100ch5、0n+1top[1]+1=top[2]
6、兩棧頂指標值相減的絕對值為1（或兩棧頂指標相鄰）。
7、(1)滿(2)空(3)n(4)棧底(5)兩棧頂指標相鄰（即值之差的絕對值為1）
8、鏈式儲存結構9、s×ss×s××10、data[++top]=x；
11、23.12.3*2-4/34.5*7/++108.9/+（注：表示式中的點(.)表示將數隔開，如23.12.3是三個數）
12、假溢位時大量移動資料元素。
13、(m+1) mod n(m+1)% n；14、佇列15、先進先出16、先進先出
17、s=(linkedlist)malloc(sizeof(lnode))；s->data=x;s->next=r->next；r->next=s；r=s；
18、犧牲乙個儲存單元設標記
19、（tail+1）mod m=front (陣列下標0到m-1，若一定使用1到m，則取模為0者，值改取m
20、21、棧22、（rear-front+m）% m；23、（r-p+n）% n；
24、（1）a[i]或a[1]（2）a[i]（3）pop（s）或s[1]；
25、（1）push（optr，w）（2）pop（optr）（3）push（opnd，operate（a，theta，b））
26、（1）t>0（2）i0（4）top四、應用題
1、棧是只准在一端進行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最後插入的元素最先刪除，故棧也稱後進先出（lifo）表。
2、佇列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許刪除的一端叫隊頭。最先插入隊的元素最先離開（刪除），故佇列也常稱先進先出（fifo）表。
3、用常規意義下順序儲存結構的一維陣列表示佇列，由於佇列的性質（隊尾插入和隊頭刪除），容易造成「假溢位」現象，即隊尾已到達一維陣列的高下標，不能再插入，然而隊中元素個數小於佇列的長度（容量）。迴圈佇列是解決「假溢位」的一種方法。通常把一維陣列看成首尾相接。
在迴圈佇列下，通常採用「犧牲乙個儲存單元」或「作標記」的方法解決「隊滿」和「隊空」的判定問題。
4、（1）通常有兩條規則。第一是給定序列中s的個數和x的個數相等；第二是從給定序列的開始，到給定序列中的任一位置，s的個數要大於或等於x的個數。
（2）可以得到相同的輸出元素序列。例如，輸入元素為a，b，c，則兩個輸入的合法序列abc和bac均可得到輸出元素序列abc。對於合法序列abc，我們使用本題約定的s×s×s×操作序列；對於合法序列bac，我們使用ss××s×操作序列。
5、三個：cdeba，cdbea，cdbae
6、輸入序列為123456，不能得出435612，其理由是，輸出序列最後兩元素是12，前面4個元素（4356）得到後，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。
得到135426的過程如下：1入棧並出棧，得到部分輸出序列1；然後2和3入棧，3出棧，部分輸出序列變為：13；接著4和5入棧，5，4和2依次出棧，部分輸出序列變為13542；最後6入棧並退棧，得最終結果135426。
7、能得到出棧序列b、c、a、e、d，不能得到出棧序列d、b、a、c、e。其理由為：若出棧序列以d開頭，說明在d之前的入棧元素是a、b和c，三個元素中c是棧頂元素，b和a不可能早於c出棧，故不可能得到d、b、a、c、e出棧序列。
8、借助棧結構，n個入棧元素可得到1/(n+1)((2n）！/（n!*n!
）)種出棧序列。本題4個元素，可有14種出棧序列，abcd和dcba就是其中兩種。但dabc和adbc是不可能得到的兩種。
9、不能得到序列2，5，3，4，6。棧可以用單鏈表實現，這就是鏈棧。由於棧只在棧頂操作，所以鏈棧通常不設頭結點。
10、如果ipj的情況，則說明要將pj壓到pi之上，也就是在pj出棧之後pi才能出棧。這就說明，對於i11、（1）能得到325641。在123依次進棧後，3和2出棧，得部分輸出序列32；然後4，5入棧，5出棧，得部分出棧序列325；6入棧並出棧，得部分輸出序列3256；最後退棧，直到棧空。
得輸出序列325641。其操作序列為aaaddaadaddd。
（2）不能得到輸出順序為154623的序列。部分合法操作序列為adaaaaddad，得到部分輸出序列1546後，棧中元素為23，3在棧頂，故不可能2先出棧，得不到輸出序列154623。
12、（1）乙個函式在結束本函式之前，直接或間接呼叫函式自身，稱為遞迴。例如，函式f在執行中，又呼叫函式f自身，這稱為直接遞迴；若函式f在執行中，呼叫函式g，而g在執行中，又呼叫函式f，這稱為間接遞迴。在實際應用中，多為直接遞迴，也常簡稱為遞迴。
（2）遞迴程式的優點是程式結構簡單、清晰，易證明其正確性。缺點是執行中佔記憶體空間較多，執行效率低。
（3）遞迴程式執行中需借助棧這種資料結構來實現。
（4）遞迴程式的入口語句和出口語句一般用條件判斷語句來實現。遞迴程式由基本項和歸納項組成。基本項是遞迴程式出口，即不再遞迴即可求出結果的部分；歸納項是將原來問題化成簡單的且與原來形式一樣的問題，即向著「基本項」發展，最終「到達」基本項。
13、函式呼叫結束時vol=14。執行過程圖示如下：
vol（4）vol(4)=vol(3)+5
14=vol(2)+3+5
=vol(1)+4+3+5
vol（3）+5=vol(0)+2+4+3+5
9=0+2+4+3+5
=14vol（2）+3
6vol（1）+4
2vol（0）+2
014、過程p遞迴呼叫自身時，過程p由內部定義的區域性變數在p的2次呼叫期間，不佔同一資料區。每次呼叫都保留其資料區，這是遞迴定義所決定，用「遞迴工作棧」來實現。
15、設hn為n個盤子的hanoi塔的移動次數。(假定n個盤子從鋼針x移到鋼針z，可借助鋼針y)
則hn=2hn-1+1//先將n-1個盤子從x移到y，第n個盤子移到z，再將那n-1個移到z
=2（2hn-2+1）+1
=22hn-2+2+1
=22（2hn-3+1）+2+1
=23hn-3+22+2+1··
·= 2khn-k+2k-1+2k-2+…+21+20
=2n-1h1+2n-2+2n-3+…+21+20
因為h1=1，所以原式hn=2n-1+2n-2+…+21+20=2n-1
故總盤數為n的hanoi塔的移動次數是2n-1。
16、執行結果為：1213121（注：執行結果是每行乙個數，為節省篇幅，放到一行。）
17、兩棧共享一向量空間（一維陣列），棧底設在陣列的兩端，兩棧頂相鄰時為棧滿。設共享陣列為s[max]，則乙個棧頂指標為-1，另乙個棧頂指標為max時，棧為空。
用c寫的入棧操作push（i，x）如下：
constmax=共享棧可能達到的最大容量
typedefstructnode
anode；
anode ds;
intpush(inti,elemtype x)
//ds為容量有max個型別為elemtype的元素的一維陣列，由兩個棧共享其空間。i的值為0或1，x為型別為elemtype的元素。本演算法將x壓入棧中。
如壓棧成功，返回1；否則，返回0。
switch（i）
//入棧成功。
資料結構1800試題 第3章棧和佇列答案
第三章棧和佇列 一 選擇題 二 判斷題 部分答案解釋如下。1 尾遞迴的消除就不需用棧 2 這個數是前序序列為1,2,3,n，所能得到的不相似的二叉樹的數目。三 填空題 1 操作受限 或限定僅在表尾進行插入和刪除操作 後進先出 2 棧 3 3 1 2 4 23 100ch 5 0 n 1 top 1 ...
資料結構1800題 第4章串答案
第四章串 一 選擇題 注 子串的定義是 串中任意個連續的字元組成的子串行，並規定空串是任意串的子串，任意串是其自身的子串。若字串長度為n n 0 長為n的子串有1個，長為n 1的子串有2個，長為n 2的子串有3個，長為1的子串有n個。由於空串是任何串的子串，所以本題的答案為 8 8 1 2 1 37...
資料結構試題及答案
資料結構試卷 一 一 單選題 每題 2 分，共20分 1.棧和佇列的共同特點是 a a.只允許在端點處插入和刪除元素 b.都是先進後出 c.都是先進先出 d.沒有共同點 2.用鏈結方式儲存的佇列，在進行插入運算時 d a.僅修改頭指標b.頭 尾指標都要修改 c.僅修改尾指標d.頭 尾指標可能都要修改...