114 高普考高考三級 資訊處理 資料結構 考古題詳解

一、 一棵空的階數為 3 的 B-Tree（B-Tree of order 3），由左而右依序插入下列鍵值（key value）：$10, 80, 2, 9, 45, 62$。

請問插入完畢後，根節點中的鍵值有哪些？請依序由小到大列出，用逗號分隔，並請說明樹節點的變化。（10 分）

二、 有一棵階數為 5 的 B-Tree（B-Tree of order 5），其高度（height）為 3，請問這棵樹中最多可以儲存多少個鍵值？（10 分）

一、 有一個三維整數陣列 $A[3][6][8]$，每個元素占用 4 個記憶體空間，每個記憶體空間均有位址。該陣列在儲存至記憶體時，會先被轉換為一維陣列的形式儲存。下列位址皆為十進位，已知 $A[0][1][2]$ 的記憶體位址為 $2040$，$A[1][4][5]$ 的位址為 $2340$。

請問陣列 $A$ 在記憶體中的儲存方式為何？是以列為主（row-major）還是以行為主（column-major）？（10 分）

二、 請計算 $A[1][5][3]$ 在記憶體中的位址為何？（10 分）

假設 $G$ 為一個無方向連通加權圖（Undirected connected weighted graph），包含五個節點：$A$、$B$、$C$、$D$、$E$。各節點間相連情形如下，邊權（邊的權重）為正整數，代表邊的成本。

• $A$ 與 $B$ 相連，邊權為 $16$。
• $A$ 與 $C$ 相連，邊權為 $18$。
• $A$ 與 $D$ 相連，邊權為 $14$。
• $B$ 與 $C$ 相連，邊權為 $15$。
• $C$ 與 $D$ 相連，邊權為 $13$。
• $D$ 與 $E$ 相連，邊權為 $12$。
• $C$ 與 $E$ 相連，邊權為 $17$。

請使用 Sollin’s 演算法，寫出最終形成的最小成本擴展樹的邊集合與總成本，請寫出每一步的演算法與該步驟形成的擴展樹。每一合併過程，列出選中的邊與合併的組成（component）。（20 分）

根據下列的虛擬碼，若 $n=21$，則傳回的答案為何？請說明。其中 $floor()$ 為數學上的地板函數（floor function）。

function splitSum(n: integer) returns integer     if $n \leq 1$ then<br>       return $1$<br>     $a \leftarrow floor(n/2)$<br>     $b \leftarrow floor(n/3)$<br>     return splitSum($a$) + splitSum($b$)<br>

（20 分）

下列虛擬碼是利用某演算法對陣列 $A$ 的元素進行處理，請說明該法是進行何種處理，並請寫出其名稱和在最壞情況下時間複雜度為何？（10 分）

若陣列 $A=[29, 10, 14, 37, 13]$，請寫出該虛擬碼的處理過程：請列出陣列在每一輪（每次外層迴圈執行完後）的內容變化情形。請特別標示出最終結果為何？（10 分）

doingSomething(A) begin     $n \leftarrow$ 陣列 $A$ 的元素個數<br>     for $i \leftarrow 0$ to $n-2$ do<br>       $theIndex \leftarrow i$<br>       for $j \leftarrow i+1$ to $n-1$ do<br>         if $A[j] < A[theIndex]$ then<br>           $theIndex \leftarrow j$<br>         end for<br>         if $theIndex \ne i$ then<br>           $temp=A[i]$<br>           $A[i]=A[theIndex]$<br>           $A[theIndex]=temp$<br>         end if<br>     end for end