數(shù)據(jù)結構第三章習題課(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡介】 1 ② n ③ n+1 ④ n/2D： ① 長度 ②深度 ③ 棧頂 ④ 棧底E：①兩個棧的棧頂同時到達?？臻g的中心點 ②其中一個棧的棧頂?shù)竭_?？臻g的中心點 ③兩個棧的棧頂在棧空間的某一位置相遇 ④兩個棧均不空，且一個棧的棧頂?shù)竭_另一個棧的棧底答案：ABCDE＝2, 1, 2, 4, 34. 【統(tǒng)考書P60 413】順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：① 設置一個布爾變量以區(qū)別隊滿還是隊空；② 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。③ 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法②，即隊頭指針、隊尾指針中有一個指向實元素，而另一個指向空閑元素。判斷循環(huán)隊列隊空標志是： f=rear 隊滿標志是：f=(r+1)%N5. 【統(tǒng)考書P60 414】設循環(huán)隊列的容量為40（序號從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=321. 【②】寫出下列程序段的輸出結果（棧的元素類型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”。2. 【②】寫出下列程序段的輸出結果（隊列中的元素類型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”。3. 【②】簡述以下算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue amp。Q){Stack S。 int d。InitStack(S)。while(!QueueEmpty(Q)){ DeQueue (Q,d)。 Push(S,d)。}。while(!StackEmpty(S)){ Pop(S,d)。 EnQueue (Q,d)。 }}答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進行逆置。4. 【①】按照四則運算加、減、乘、除和冪運算（↑）優(yōu)先關系的慣例，并仿照教材例32的格式，畫出對下列算術表達式求值時操作數(shù)棧和運算符棧的變化過程：A－BC/D+E↑F答：1設整數(shù)序列a1,a2,…,an，給出求解最大值的遞歸程序。答：int MaxValue (int a[],int n) //設整數(shù)序列存于數(shù)組a中，共有n個，本算法求解其最大值 { if (n==1) max=a[1]。 else if a[n]MaxValue(a,n1) max=a[n]。 else max=MaxValue(a,n1)。 return(max)。 }//算法結束1假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針，請寫出相應的入隊列和出隊列算法。答：（1）void EnQueue (LinkedList rear, ElemType x)// rear是帶頭結點的循環(huán)鏈隊列的尾指針，本算法將元素x插入到隊尾{ s= (LinkedList) malloc (sizeof(LNode))。 //申請結點空間 sdata=x。 snext=rearnext。 //將s結點鏈入隊尾 rearnext=s。 rear=s。 //rear指向新隊尾}（2）void DeQueue (LinkedList rear) // rear是帶頭結點的循環(huán)鏈隊列的尾指針，本算
教學教案相關推薦
鄂ICP備17016276號-1