數(shù)據(jù)結(jié)構(gòu)第3章棧和隊列自測卷答案(編輯修改稿)
2025-07-19 17:06 本頁面
【文章內(nèi)容簡介】 2，3，4的四輛列車，順序進入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。① 全進之后再出情況，只有1種：4，3，2，1② 進3個之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4③ 進2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4④ 進1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’ 和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j）從表尾開始打印輸出；堆棧是后進先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實現(xiàn)。（但堆棧是先減后壓還是……）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈首開始入棧，全部壓入后再依次輸出。“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：① 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空；② 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。③ 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法②，即隊頭指針、隊尾指針中有一個指向?qū)嵲兀硪粋€指向空閑元素。判斷循環(huán)隊列隊空標志是： f=rear 隊滿標志是：f=(r+1)%N（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有① 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分。至少要寫出思路）1. 按照四則運算加、減、乘、除和冪運算（↑）優(yōu)先關(guān)系的慣例，并仿照教材例32的格式，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：A－BC/D+E↑F答：2. 寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。void main( ){Stack S。Char x,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”。3. 寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElem Type為char）。void main( ){Queue Q。 Init Queue (Q)。Char x=’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,y)。printf(y)。 }。Printf(x)。}答：輸出為“char”。4. 簡述以下算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue amp。Q){Stack S。 int d。InitStack(S)。while(!QueueEmpty(Q)){ DeQueue (Q,d)。 Push(S,d)。}。while(!StackEmpty(S))
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1