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

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

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

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

4、中N個元素依次為B1，B2，BN，隊(duì)頭元素為B1，A，B均采用順序存儲構(gòu)造且存儲空間足夠大，現(xiàn)要將棧中元素全部移到隊(duì)列中，使得隊(duì)列中元素與棧中元素交替陳列，即B中元素為B1，A1，B2，A2，B3，A3，,BN，AN，問至少需求多少次根本操作才干完成上述任務(wù)，請寫出詳細(xì)步驟要求除A，B外所用的其他附加存儲量為1，每次出棧、入棧、出隊(duì)列可均看作一次根本操作。 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();/棧頂元素放入隊(duì)列尾部s.pop();/刪除棧頂元素len=q.size();/此時隊(duì)列的長度為lenwhile(len2)/隊(duì)列的前l(fā)en-2個元素放入隊(duì)尾q.push(q.front();q.pop();len-;while(q.empty()!=true)coutq.front();q.pop();return 0;我無法證明這是不是最少次數(shù)。大家可以思索一下有沒有更好的方法。2.知Q是一個非空隊(duì)列，S是一個空棧。僅用隊(duì)列和棧的ADT函數(shù)和少量任務(wù)變量，運(yùn)用C言語編寫一個算法，將隊(duì)列Q中的一切元素逆置。 int main(int argc, char* argv)queue q;q.push(1);q.push(2);q.push(3);stack s;while(q.empty()!=true)/隊(duì)列中元素入棧s.push(q.front();q.pop();while(s.emp