雲南大學資訊學院電腦科學與工程系《資料結構》課後作業
一．選擇題
1. 若已知乙個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pn,若pn是n，則pi是( )。
a. ib. n-i c. n-i+1 d. 不確定
2. 設乙個棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（ ）。
a. 5 1 2 3 4 b. 4 5 1 3 2 c. 4 3 1 2 5 d. 3 2 1 5 4
3. 某堆疊的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ ）。
a. a，c，b，d b. b, c，d，a c. c, d，b, a d. d, c，a，b
4. 最大容量為n的迴圈佇列，隊尾指標是rear，隊頭是front，則隊空的條件是 （ ）。
a. (rear+1) mod n=frontb. rear=front
c．rear+1=frontd. (rear-l) mod n=front
5. 用不帶頭結點的單鏈表儲存佇列時,其隊頭指標指向隊頭結點,其隊尾指標指向隊尾結點，則在進行刪除操作時( )。
a．僅修改隊頭指標b. 僅修改隊尾指標
c. 隊頭、隊尾指標都要修改 d. 隊頭,隊尾指標都可能要修改
6. 遞迴過程或函式呼叫時，處理引數及返回位址，要用一種稱為（ ）的資料結構。
a．佇列b．多維陣列c．棧d. 線性表
7. 設棧s和佇列q的初始狀態為空，元素e1，e2，e3，e4,e5和e6依次通過棧s，乙個元素出棧後即進佇列q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧s的容量至少應該是( )。
a． 6b. 4c. 3d. 2
8. 若用乙個大小為6的陣列來實現迴圈佇列，且當前rear和front的值分別為0和3，當從佇列中刪除乙個元素，再加入兩個元素後，rear和front的值分別為多少？( )
a. 1和 5 b. 2和4c. 4和2 d. 5和1
9. 若以1234作為雙端佇列的輸入序列，則既不能由輸入受限的雙端佇列得到，也不能由輸出受限的雙端佇列得到的輸出序列是( )。
a. 1234 b. 4132c. 4231 d. 4213
二．判斷題
1. 兩個棧共用靜態儲存空間，對頭使用也存在空間溢位問題。（ ）
2. 即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ ）
3. 棧和佇列都是限制訪問點的線性結構。（ ）
4. 佇列和棧都是運算受限的線性表，只允許在表的兩端進行運算。（ ）
5. 通常使用佇列來處理函式或過程的呼叫。（ ）
三．填空題
1．棧是的線性表，其運算遵循的原則。
2是限定僅在表尾進行插入或刪除操作的線性表。
3. 當兩個棧共享一儲存區時，棧利用一維陣列stack(1,n)表示，兩棧頂指標為top[1]與top[2]，則當棧1空時，top[1]為_______，棧2空時 ，top[2]為_______，棧滿時為_______。
4. 順序棧用data[1..n]儲存資料，棧頂指標是top,則值為x的元素入棧的操作是_______。
5．佇列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是_______。
6．表示式求值是_______應用的乙個典型例子。
四．應用題
1. 假設以s和x分別表示入棧和出棧操作，則對初態和終態均為空的棧操作可由s和x組成的序列表示（如sxsx）。
（1）試指出判別給定序列是否合法的一般規則。
（2）入棧系列包含n個元素（每個元素均不同），兩個不同入棧序列能否得到相同的輸出元素序列？如能得到，請舉列說明。
2. 簡要敘述迴圈佇列的資料結構，並寫出其初始狀態、佇列空、佇列滿時的隊首指標與隊尾指標的值。
五．演算法設計題
1．設有兩個棧s1,s2都採用順序棧方式，並且共享乙個儲存區[o..maxsize-1],為了盡量利用空間，減少溢位的可能，可採用棧頂相向，迎面增長的儲存方式。試設計s1,s2有關入棧和出棧的操作演算法。
2.已知q是乙個非空佇列，s是乙個空棧。僅用佇列和棧的adt函式和少量工作變數，使編寫乙個演算法，將佇列q中的所有元素逆置。
棧的adt函式有：
makeempty; 置空棧
push新元素進棧
pop出棧，返回棧頂值
isempty; 判棧空否
佇列的 adt函式有：
enqueue; 元素value進隊
dequeue; 出佇列，返回隊頭值
isempty; 判佇列空否
第3章棧和佇列
一 填空題 1.棧 2.線性，棧頂，隊尾，隊頭 3.棧頂，棧底 4.佇列 5.先存入元素，後移動棧頂指標 6.不可能的 7.2 3 5 4 1 100ch 8.s x s s x s x x 9.陣列 10.hs null 11.前乙個位置 12.先移動隊首指標，後取出元素 13.n 1 14.m ...
資料結構1800試題 第3章棧和佇列答案
第三章棧和佇列 一 選擇題 二 判斷題 部分答案解釋如下。1 尾遞迴的消除就不需用棧 2 這個數是前序序列為1,2,3,n，所能得到的不相似的二叉樹的數目。三 填空題 1 操作受限 或限定僅在表尾進行插入和刪除操作 後進先出 2 棧 3 3 1 2 4 23 100ch 5 0 n 1 top 1 ...
資料結構第3章棧與佇列習題
9 設n個元素進棧序列是p1,p2,pn，其輸出序列是1，2，3，n，若p3 1,則p1的值 a 可能是2 b 一定是1 c 不可能是2 d 不可能是3 10 設n個元素進棧序列是p1,p2,pn，其輸出序列是1，2，3，n，若p3 3,則p1的值 a 可能是2 b 一定是2 c 不可能是1 d 一...