數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列自測(cè)卷答案

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

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

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

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

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

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

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

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

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

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

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