3.數據結構作業(yè)答案第3章-第3章 棧和隊列 自測卷答案作業(yè)答案

3.數據結構作業(yè)答案第3章--第3章棧和隊列自測卷答案作業(yè)答案3.數據結構作業(yè)答案第3章--第3章棧和隊列自測卷答案作業(yè)答案3.數據結構作業(yè)答案第3章--第3章棧和隊列自測卷答案作業(yè)答案3.數據結構作業(yè)答案第3章--第3章棧和隊列自測卷答案作業(yè)答案編制僅供參考審核批準生效日期地址：電話：傳真:郵編:第3章棧和隊列自測卷答案姓名班級題號一二三四五六總分題分151020202015100得分一、填空題（每空1分，共15分）1.【李春葆】向量、棧和隊列都是線性結構，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為棧底。3.隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。4.在一個循環(huán)隊列中，隊首指針指向隊首元素的前一個位置。(注：不一定，這是一種約定，在殷教材中是隊首指針指向隊列的首元素位置)5.在具有n個單元的循環(huán)隊列中，隊滿時共有n-1個元素。6.向棧中壓入元素的操作是先移動棧頂指針，后存入元素。7.從循環(huán)隊列中刪除一個元素時，其操作是先移動隊首指針，后取出元素。(注：不一定，這是一種約定，在殷教材中是先取出元素，后移動隊首指針)8.〖00年統(tǒng)考題〗帶表頭結點的空循環(huán)雙向鏈表的長度等于0。L=head頭結點RL=head頭結點R=headhead二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）（×）1.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，線性表是邏輯結構概念，可以順序存儲或鏈式存儲，與元素數據類型無關。（×）2.在表結構中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調用子程序或函數常用，CPU中也用隊列。（√）3.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（√）4.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（×）5.棧和鏈表是兩種不同的數據結構。錯，棧是邏輯結構的概念，是特殊殊線性表，而鏈表是存儲結構概念，二者不是同類項。（×）6.棧和隊列是一種非線性數據結構。錯，他們都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（√）7.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（√）8.兩個棧共享一片連續(xù)內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。（×）9.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。 錯，后半句不對。（×）10.一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯，有可能。（注：不可能是53421等）三、單項選擇題（每小題1分，共20分）（B）1.〖00年元月統(tǒng)考題〗棧中元素的進出原則是Ａ．先進先出Ｂ．后進先出Ｃ．?？談t進Ｄ．棧滿則出（C）2.〖李春葆〗若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定解釋：當p1=n，即n是最先出棧的，根據棧的原理，n必定是最后入棧的（事實上題目已經表明了），那么輸入順序必定是1，2，3，…，n，則出棧的序列是n，…，3，2，1。（若不要求順序出棧，則輸出序列不確定）（B）3.〖李春葆〗判定一個棧ST（最多元素為m0）為空的條件是（注：在殷教材中是top=-1）Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0（A）4.〖李春葆〗判定一個隊列QU（最多元素為m0）為滿隊列的條件是（注：在殷教材在采用循環(huán)隊列隊滿是front==(rear+1)%m0）Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1解：隊滿條件是元素個數為m0。由于約定滿隊時隊首指針與隊尾指針相差1，所以不必再減1了，應當選A。當然，更正確的答案應該取模，即：QU->front==(QU->rear+1)%m0（D）5．數組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數小于ｎ，計算隊列中元素的公式為（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n殷教材（D）5．數組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的位置，ｒ為隊尾元素的后一位置，假定隊列中元素的個數小于ｎ，計算隊列中元素的公式為（Ａ）r－f;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n6.【98初程P71】從供選擇的答案中，選出應填入下面敘述

內的最確切的解答，把相應編號寫在答卷的對應欄內。設有4個數據元素a1、a2、a3和a4，對他們分別進行棧操作或隊操作。在進棧或進隊操作時，按a1、a2、a3、a4次序每次進入一個元素。假設棧或隊的初始狀態(tài)都是空?，F要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是A，第二次出棧得到的元素是B是；類似地，考慮對這四個數據元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是C，第二次出隊得到的元素是D。經操作后，最后在棧中或隊中的元素還有E個。供選擇的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：ABCDE＝2,4,1,2,27.【94初程P75】從供選擇的答案中，選出應填入下面敘述

內的最確切的解答，把相應編號寫在答卷的對應欄內。棧是一種線性表，它的特點是A。設用一維數組A[1,…,n]來表示一個棧，A[n]為棧底，用整型變量T指示當前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值B；從棧中彈出（POP）一個元素時，變量T的值C。設?？諘r，有輸入序列a，b，c，經過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是D，變量T的值是E。供選擇的答案：A：①先進先出②后進先出 ③進優(yōu)于出 ④出優(yōu)于進 ⑤隨機進出B，C： ①加1②減1③不變 ④清0⑤加2⑥減2D：①a,b②b,c ③c,a ④b,a⑤c,b⑥a,cE：①n+1②n+2③n ④n-1⑤n-2答案：ABCDE=2,2,1,6,4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8.【91初程P77】從供選擇的答案中，選出應填入下面敘述

內的最確切的解答，把相應編號寫在答卷的對應欄內。在做進棧運算時，應先判別棧是否A；在做退棧運算時，應先判別棧是否B。當棧中元素為n個，做進棧運算時發(fā)生上溢，則說明該棧的最大容量為C。為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內存空間時，應將兩棧的D分別設在這片內存空間的兩端，這樣，只有當E時，才產生上溢。供選擇的答案：A，B：①空②滿③上溢④下溢C： ①n-1②n③n+1④n/2D：①長度②深度③棧頂④棧底E：①兩個棧的棧頂同時到達棧空間的中心點②其中一個棧的棧頂到達?？臻g的中心點③兩個棧的棧頂在達棧空間的某一位置相遇④兩個棧均不空，且一個棧的棧頂到達另一個棧的棧底答案：ABCDE＝2,1,2,4,3四、簡答題（每小題4分，共20分）1.【嚴題集①和①】說明線性表、棧與隊的異同點。劉答：相同點：都是線性結構，都是邏輯結構的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：①運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。②用途不同，堆棧用于子程調用和保護現場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2.【統(tǒng)考書P604-11，難于嚴題集①】設有編號為1，2，3，4的四輛列車，順序進入一個棧式結構的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。①全進之后再出情況，只有1種：4，3，2，1②進3個之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進2個之后再出的情況，有5種，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進1個之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,33.【劉自編】假設正讀和反讀都相同的字符序列為“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’則不是回文。假設一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？

答：線性表是隨機存儲，可以實現，靠循環(huán)變量（j--）從表尾開始打印輸出；堆棧是后進先出，也可以實現，靠正序入棧、逆序出棧即可；隊列是先進先出，不易實現。哪種方式最好，要具體情況具體分析。若正文在機內已是順序存儲，則直接用線性表從后往前讀取即可，或將堆棧棧頂開到數組末尾，然后直接用POP動作實現。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈首開始入棧，全部壓入后再依次輸出。4.【統(tǒng)考書P604-13】順序隊的“假溢出”是怎樣產生的如何知道循環(huán)隊列是空還是滿答：一般的一維數組隊列的尾指針已經到了數組的上界，不能再有入隊操作，但其實數組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：設置一個布爾變量以區(qū)別隊滿還是隊空；浪費一個元素的空間，用于區(qū)別隊滿還是隊空。使用一個計數器記錄隊列中元素個數（即隊列長度）。我們常采用法②，即隊頭指針、隊尾指針中有一個指向實元素，而另一個指向空閑元素。判斷循環(huán)隊列隊空標志是：f=rear隊滿標志是：f=(r+1)%N5.【統(tǒng)考書P604-14】設循環(huán)隊列的容量為40（序號從0到39），現經過一系列的入隊和出隊運算后，有①front=11，rear=19;②front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？

答：用隊列長度計算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32五、閱讀理解（每小題5分，共20分。至少要寫出思路）【嚴題集①】按照四則運算加、減、乘、除和冪運算（↑）優(yōu)先關系的慣例，并仿照教材例3-2的格式，畫出對下列算術表達式求值時操作數棧和運算符棧的變化過程：A－B×C/D+E↑FA－B×C/D+E↑F答：【嚴題集②】寫出下列C程序段的輸出結果（棧的元素類型SElemType為char）。并將其改寫成C++編寫voidmain(){StackS;Charx,y;InitStack(S);X=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};Printf(x);}答：輸出為“stack”。【嚴題集②】寫出下列程序段的輸出結果（隊列中的元素類型QElemType為char）。并將其改寫成C++編寫voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q