中南大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法第3章棧和隊列課后作業(yè)答案匯總(已修改)
2025-07-06 06:54 本頁面
【正文】 . . . . .第3章棧和隊列習(xí)題練習(xí)答案 設(shè)將整數(shù)1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題： (1)若入、出棧次序為Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何(這里Push(i)表示i進棧，Pop( )表示出棧)? (2)能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到?！ ?3)請分析 1，2 ，3 ，4 的24種排列中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。答： (1)出棧序列為：1324 (2)不能得到1423序列。因為要得到14的出棧序列，則應(yīng)做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。這樣，3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24種排列中，可通過相應(yīng)入出棧操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 鏈棧中為何不設(shè)置頭結(jié)點?答： 鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進行操作的，如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進行操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。 循環(huán)隊列的優(yōu)點是什么? 如何判別它的空和滿?答： 循環(huán)隊列的優(yōu)點是：它可以克服順序隊列的假上溢現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用。判別循環(huán)隊列的空或滿不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊列的空和滿。二是少用一個元素的空間,每次入隊前測試入隊后頭尾指針是否會重合，如果會重合就認為隊列已滿。三是設(shè)置一計數(shù)器記錄隊列中元素總數(shù)，不僅可判別空或滿，還可以得到隊列中元素的個數(shù)。 設(shè)長度為n的鏈隊用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊出隊操作的時間為何? 若只設(shè)尾指針呢?答： 當(dāng)只設(shè)頭指針時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指針開始查找，找到最后一個元素時方可進行入隊操作。若只設(shè)尾指針，則出入隊時間均為1。因為是循環(huán)鏈表，尾指針?biāo)傅南乱粋€元素就是頭指針?biāo)冈?，所以出隊時不需要遍歷整個隊列。 指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S){ int i。 arr[64] 。 n=0 ?！ hile ( StackEmpty(S)) arr[n++]=Pop(S)?！ or (i=0, i n。 i++) Push(S, arr[i])?！ //Demo1(2) SeqStack S1, S2, tmp?！ ataType x?！ ?..//假設(shè)棧tmp和S2已做過初始化 while ( ! StackEmpty (amp。S1)) { x=Pop(amp。S1) ?！ ush(amp。tmp,x)。 } while ( ! StackEmpty (amp。tmp) ) { x=Pop( amp。tmp)。 Push( amp。S1,x)?！ ush( amp。S2, x)?！ (3) void Demo2( SeqStack *S, int m) { // 設(shè)DataType 為int 型 SeqStack T。 int i?！ nitStack (amp。T)?！ hile (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( amp。T,i)?！ hile (! StackEmpty( amp。T)) { i=Pop(amp。T
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1