關(guān)于棧和隊列習(xí)題ppt課件

1、關(guān)于棧和隊列的習(xí)題一、選擇題1.用單循環(huán)鏈表表示隊列，正確的說法是：B A. 可設(shè)一個頭指針使入隊、出隊都方便B. 可設(shè)一個尾指針使入隊、出隊都方便C. 必需設(shè)頭尾指針才干使入隊、出隊都方便D. 無論如何,只能夠使入隊方便2.輸入序列為A，B，C，D，不能夠得到的輸出序列有 D 。AA，B，C，D BD，C，B，A CA，C，D，B DC，A，B，D3.用順序表實現(xiàn)棧構(gòu)造時，順序表地址的 B 作為棧頂操作比較方便。A. 低端 B. 高端4.用單鏈表實現(xiàn)棧構(gòu)造構(gòu)時，把鏈表的 A 作為棧頂操作比較方便。A. 第一個元素 B.最后一個元素二、判別題1.棧和隊列邏輯上都是線性表。 ( )2.消除遞歸不

2、一定需求運用棧。 三、填空題1.用循環(huán)鏈表表示的隊列長度為n，假設(shè)只設(shè)頭指針，那么出隊和入隊的時間復(fù)雜度分別是 O1 和 On ；假設(shè)只設(shè)尾指針，那么出隊和入隊的時間復(fù)雜度分別是 O1 和 O1 。2.棧的特點是 后進先出 。3.隊列的特點是先進先出 。四、問答題內(nèi)存中一片延續(xù)空間無妨假設(shè)地址從1到m，提供應(yīng)兩個棧S1和S2運用，怎樣分配這部分存儲空間，使得對任一個棧，僅當(dāng)這部分空間全滿時才發(fā)生上溢。 兩個棧公用一片順序空間s1s2p2p1兩個棧公用一片順序空間10s1s2p2p1兩個棧公用一片順序空間1011s1s2p2p1兩個棧公用一片順序空間101112s1s2p2p1兩個棧公用一片順序

3、空間10111220s1s2p2p1兩個棧公用一片順序空間1011122120s1s2p2p1兩個棧公用一片順序空間101112222120s1s2p2p1兩個棧公用一片順序空間10111223222120s1s2p2p1兩個棧公用一片順序空間1011122423222120s1s2p2p1兩個棧公用一片順序空間101112132423222120s1s2p2p1兩個棧公用一片順序空間10111213142423222120s1s2p2p1此時指針交錯，空間曾經(jīng)滿了，不能再壓入元素五、程序設(shè)計題1.設(shè)A是一個棧，棧中共有N個元素，依次為A1，A2，,AN，棧頂元素為AN，B是一個循環(huán)隊列，隊列

4、中N個元素依次為B1，B2，BN，隊頭元素為B1，A，B均采用順序存儲構(gòu)造且存儲空間足夠大，現(xiàn)要將棧中元素全部移到隊列中，使得隊列中元素與棧中元素交替陳列，即B中元素為B1，A1，B2，A2，B3，A3，,BN，AN，問至少需求多少次根本操作才干完成上述任務(wù)，請寫出詳細步驟要求除A，B外所用的其他附加存儲量為1，每次出棧、入棧、出隊列可均看作一次根本操作。 int main(int argc, char* argv)queue q;q.push(1);q.push(2);q.push(3);stack s;s.push(4);s.push(5);s.push(6); int len;while

5、(s.empty()!=true)q.push(s();/棧頂元素放入隊列尾部s.pop();/刪除棧頂元素len=q.size();/此時隊列的長度為lenwhile(len2)/隊列的前l(fā)en-2個元素放入隊尾q.push(q.front();q.pop();len-;while(q.empty()!=true)coutq.front();q.pop();return 0;我無法證明這是不是最少次數(shù)。大家可以思索一下有沒有更好的方法。2.知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的ADT函數(shù)和少量任務(wù)變量，運用C言語編寫一個算法，將隊列Q中的一切元素逆置。 int main(int argc, char* argv)queue q;q.push(1);q.push(2);q.push(3);stack s;while(q.empty()!=true)/隊列中元素入棧s.push(q.front();q.pop();while(s.emp