109 高普考高考三級 資訊處理 程式語言 考古題詳解

核心觀念

原程式在遞迴呼叫返回後，還要執行加法：

return(x + recsum(x - 1));

因此它是非尾遞迴。尾遞迴的條件是：遞迴呼叫必須是函式最後一個動作，呼叫返回後不再有其他運算。

要把尚未完成的加法工作放進累積參數，讓每次遞迴呼叫都帶著目前的累計值前進。

解題方法

原函式計算的是：

$$x + (x-1) + \cdots + 2 + 1$$

新增累積參數 sum，用來保存已累加的部分。每次將目前的 x 加進 sum，再以 x - 1 繼續遞迴；當 x == 1 時，回傳最後的總和。

int recsum_tail(int x, int sum) {
 if (x == 1)
 return sum + x;
 return recsum_tail(x - 1, sum + x);
}

int recsum(int x) {
 return recsum_tail(x, 0);
}

以 x = 4 為例，呼叫參數依序為：

$$(4,0)\rightarrow(3,4)\rightarrow(2,7)\rightarrow(1,9)$$

最後回傳 $9+1=10$，與原程式的 $4+3+2+1=10$ 相同。遞迴呼叫 recsum_tail(x - 1, sum + x) 是最後一個動作，因此符合尾遞迴定義。

尾遞迴形式的優點

核心觀念

本題考查 C 語言的多維陣列、指標與陣列的型別，以及 sizeof 和指標相減的單位。

typedef int T1[10][9];

因此，T1 是含有 $10 \times 9$ 個 int 的二維陣列，大小為

$$\operatorname{sizeof}(T1)=10 \times 9 \times 4=360\text{ bytes}$$

結構中的 a 是由 10 個「指向 T1 的指標」組成的陣列；b 是指向含有 100 個 int 之陣列的指標。兩者都是指標，大小均為 4 bytes。

f 的型別是三維陣列，其每個元素都是該匿名結構。指標相減的結果則是兩個指標之間相隔的「元素個數」，不是位元組數。

解題方法

先由內而外判讀宣告，再逐一套用陣列大小與指標運算規則。

結構大小為

$$\operatorname{sizeof}(\text{struct}) =\operatorname{sizeof}(a)+\operatorname{sizeof}(b) =(10 \times 4)+4=44\text{ bytes}$$

本題假設 int 與指標各占 4 bytes，且結構成員的排列不需額外填補。

f 的維度為 [10][10][10]，所以：

• f[i] 是一個 [10][10] 的陣列。
• f[i][j] 是一個 [10] 的陣列。
• f[i][j][k] 是一個結構元素。

逐項計算

p1

sizeof(f[1][5])

f[1][5] 是長度 10 的結構陣列，因此

$$\operatorname{sizeof}(f[1][5]) =10 \times 44=440$$

所以 p1 = 440。

p2

sizeof(f[2][3][4].a)

.a 是含有 10 個指標的陣列，每個指標占 4 bytes：

核心觀念

本題考遞迴函式的呼叫順序與回傳值。計算時要先求出內層函式呼叫的回傳值，再將結果代入外層函式。

• foo2(p)：當 $p<91$ 時，遞迴呼叫 foo2(p + 11)；直到參數至少為 $91$，才回傳該參數。
• foo1(p)：當 $p\ge 90$ 時，先計算 foo1(p - 11)，再把該回傳值當作參數呼叫另一層 foo1；當 $p<90$ 時，回傳 $p+10$。
• foo(p)：先計算 foo2(p)，再把結果傳入 foo1，即 foo1(foo2(p))。

解題方法

先整理 foo2 的作用：它每次將小於 $91$ 的參數加 $11$，直到參數達到或超過 $91$，再回傳參數。因此：

輸入 $p$	foo2(p) 的遞迴參數	回傳值
65	$65\to76\to87\to98$	98
83	$83\to94$	94
95	$95$	95
100	$100$	100
142	$142$	142

接著計算 foo1。當輸入至少為 $90$，程式會先對 $p-11$ 呼叫 foo1，再以該次回傳值作為新的參數呼叫 foo1。

• foo1(98) $\texttt{foo1(98)}=\texttt{foo1(foo1(87))}$ $\texttt{foo1(87)}=87+10=97$ $\texttt{foo1(97)}=\texttt{foo1(foo1(86))}$ $\texttt{foo1(86)}=86+10=96,\qquad \texttt{foo1(96)}=\texttt{foo1(85)}=95$ 所以 foo1(98)=95。

• foo1(94) $\texttt{foo1(94)}=\texttt{foo1(foo1(83))}$ $\texttt{foo1(83)}=93,\qquad \texttt{foo1(93)}=\texttt{foo1(foo1(82))}$ $\texttt{foo1(82)}=92,\qquad \texttt{foo1(92)}=\texttt{foo1(foo1(81))}$

核心觀念

本題考查物件導向程式語言中的繼承：子類別（subclass）從父類別（superclass）取得資料欄位與方法，並可在此基礎上新增或覆寫功能。繼承能重用程式碼，也能表達類別間的「是一種」（is-a）關係。

解題方法

可從「一個子類別可直接繼承幾個父類別」切入，再比較類別關係與實作方式。

• 單一繼承（single inheritance）：每個子類別至多直接繼承一個父類別。繼承關係形成樹狀結構；子類別仍可透過父類別的父類別，間接取得更上層的功能。
• 多重繼承（multiple inheritance）：一個子類別可直接繼承兩個或以上的父類別。子類別可以同時重用多個類別的屬性與方法，類別關係較具彈性，但也會增加名稱衝突與繼承歧異的處理難度。

例如，Student 可單一繼承 Person；若語言支援多重繼承，也可讓 TeachingAssistant 同時繼承 Student 與 Employee，取得兩者的功能。

實作方法與差異

以類別宣告來看，單一繼承只指定一個父類別；多重繼承則指定多個父類別。以下以類似 C++ 的語法示意：