1、1L=head頭結(jié)點R=headhead第3章棧和隊列棧和隊列自測卷答案自測卷答案姓名姓名班級班級題號題號一二三四五六總分總分題分題分151020202015100得分得分一、填空題（每空一、填空題（每空1分，共分，共15分）分）1.向量、棧和隊列都是向量、棧和隊列都是線性線性結(jié)構(gòu)，可以在向量的結(jié)構(gòu)，可以在向量的任何任何位置插入和刪除元素；對于棧只能在位置插入和刪除元素；對于棧只能在棧頂棧頂插入和刪除元素；對于隊列只能在插入和刪除元素；

2、對于隊列只能在隊尾隊尾插入和插入和隊首隊首刪除元素。刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂棧頂。不允許插入和刪除運算的一端稱為棧底棧底。3.隊列隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。4.在一個循環(huán)隊列中，隊首指針指向隊首元素的前一個前一個位置。5.在具有n個單元的循環(huán)隊列中，隊滿時共有n1個元素。6.向棧中壓入元素的操作是先移動棧頂指針移動棧頂指針，后，后存入元素存入元

3、素。7.從循環(huán)隊列中刪除一個元素時，其操作是先移動隊首指針移動隊首指針，后，后取出元素取出元素。8.帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于0。解：解：二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（每小題（每小題1分，共分，共10分）分）（）1.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈式存儲，與元素數(shù)據(jù)

4、類型無關(guān)。（）2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊列。（√）3.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構(gòu)。（√）4.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（）5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表

5、，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。（）6.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（√）7.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（√）8.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。（）9.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。錯，后半句不對。（）10.

6、一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯，有可能。三、單項選擇題三、單項選擇題（每小題（每小題1分，共分，共20分）分）（B）1.棧中元素的進出原則是Ａ先進先出Ｂ后進先出Ｃ?？談t進Ｄ棧滿則出3答案：ABCDE=22164注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8.從供選擇的答案中，選出應填入下面敘述？內(nèi)的最確切的解答，把相應

7、編號寫在答卷的對應欄內(nèi)。在做進棧運算時，應先判別棧是否A；在做退棧運算時，應先判別棧是否B。當棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為C。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應將兩棧的D分別設在這片內(nèi)存空間的兩端，這樣，只有當E時，才產(chǎn)生上溢。供選擇的答案：A，B：①空②滿③上溢④下溢C：①n1②n③n1④n2D：①長度②深度③棧頂④棧底E：①兩個棧的棧頂同時到達棧空間的中心

8、點②其中一個棧的棧頂?shù)竭_棧空間的中心點③兩個棧的棧頂在達?？臻g的某一位置相遇④兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底答案：ABCDE＝21243四、簡答題（每小題四、簡答題（每小題4分，共分，共20分）分）1.說明線性表、棧與隊的異同點。劉答：相同點：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：不同點：①運算規(guī)則不同，線性

9、表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。②用途不同，堆棧用于子程調(diào)用和保護現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2.設有編號為1，2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。①全進之后再出情況，只有1種：4，3，2，1②進3個之后再出的情況，有

10、3種，342132413214③進2個之后再出的情況，有5種，24312341213421432134④進1個之后再出的情況，有5種，143213241342123412433.假設正讀和反讀都相同的字符序列為假設正讀和反讀都相同的字符序列為“回文回文”，例如，，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。假設一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出則不是回文。假

11、設一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？其回文的可能性？答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j）從表尾開始打印輸出；堆棧是后進先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實現(xiàn)。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲