天天看點

《計算機系統:核心概念及軟硬體實作(原書第4版)》——2.7 練習

本節書摘來自華章計算機《計算機系統:核心概念及軟硬體實作(原書第4版)》一書中的第2章,第2.7節,作者:[美] j. 斯坦利·沃法德(j. stanley warford)著, 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

2.4節

1.主程式第一次調用圖2-25中的函數sum,從第二次開始它就自己調用自己。*(a)該函數總共被調用了多少次?(b)畫出函數第三次被調用後,主程式變量和運作時棧的情況。應該有3個棧幀。(c)畫出從(b)調用傳回前,主程式變量和運作時棧的情況。應該有3個棧幀,不過内容和(b)的不同。

2.給出圖2-28中函數bincoeff的調用樹,調用樹的畫法如圖2-30所示,主程式中的調用語句如下:

*(a)bincoeff(4,1) (b)bincoeff(5,1)

(c)bincoeff(3,2) (d)bincoeff(4,4)

(e)bincoeff(4,2)

該函數被調用了多少次?程式執行期間,運作時棧上棧幀的最大數量是多少?程式是按照什麼順序進行調用和傳回的?

3.對練習2中的情況,畫出從下列函數調用傳回前的運作時棧,運作時棧的畫法如圖2-29所示。

*(a)bincoeff(2,1) (b)bincoeff(3,1)

(c)bincoeff(1,0) (d)bincoeff(4,4)

(e)bincoeff(2,1)

在(e)中,bincoeff(2,1)被調用兩次,畫出從第二次對該函數進行調用傳回前的運作時棧。

4.給出圖2-32中逆轉字元串數組字母順序的程式的調用樹,調用樹的畫法如圖2-30所示。函數reverse被調用了多少次?在運作時棧上配置設定的棧幀最大數量是多少?畫出第三次調用函數reverse後的運作時棧。

5.斐波那契數列是

《計算機系統:核心概念及軟硬體實作(原書第4版)》——2.7 練習

每個斐波那契數列中的數是數列中它前面兩個數之和。數列最開始有兩個數,遞歸地定義為

fib(0)=0

fib(1)=1

fib(n)=fib(n - 1) + fib(n - 2)n > 1

畫出下列斐波那契數的調用樹:

(a)fib(3)    (b)fib(4)    (c)fib(5)

對上述每個調用,fib被調用了多少次?在運作時棧上被配置設定的棧幀最大數量是多少?

6.對于問題2.15中漢諾塔問題的解決方案,畫出4個盤子情況的調用樹。程式被調用了多少次?運作時棧上棧幀的最大數量是多少?

7.神秘數字遞歸地定義為

myst(0)=2

myst(1)=1

myst(n)=2*myst(n - 1) + myst(n - 2)n > 1

(a)畫出myst(4)的調用序列。(b)myst(4)的值是什麼?

8.檢查下面的c++程式。(a)畫出過程最後一次被調用後的運作時棧。(b)程式的輸出是什麼?

《計算機系統:核心概念及軟硬體實作(原書第4版)》——2.7 練習

繼續閱讀