加載中. ..
PDF
105年特種考試地方政府公務人員考試試題 代號：34080 全一頁
等別： 三等考試
類科： 資訊處理
科目： 資料結構
考試時間 ： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、請回答下列問題：
畫出 AVL 平衡二元樹，其中序（inorder）拜訪為 1、2、3、4、5任三種。（24 分）
請問共有多少種 AVL 平衡二元樹，其中序拜訪為 1、2、3、4、5？（6分）
二、分別給定矩陣 A、B、C與D的大小為 2×4、4×3、3×5和5×1：（每小題 5分，共 15 分）
共有幾種加括號的方法？
例如(AB)(CD)，共需多少次乘法？
求出三者乘積之最有效的方式為何？
三、試針對下列無向網路圖形（Undirected Network Graph）
N(V,E,C),V={1,2,3,4,5,6},N={(1,2,6),(1,5,19),(1,6,21),(2,3,5),(2,4,16),(2,5,11),
(3,4,10),(4,5,8),(4,6,9),(5,6,7)}，成本 C(1,2)=6, C(1,5)=19…等，
求最小成本擴張樹（minimal cost spanning tree）的最小成本。（10 分）
四、有一浮點數三維陣列（three dimensional array）float A [6] [7] [10]；假設 sizeof(float)＝4：
請問此陣列共佔多少位元組？（10 分）
若A[0][0][0] 在記憶體中的位址為 03C416
，則元素 A[5] [2] [9] 的位址為何？（15 分）
五、二項式係數（Binomial Coefficient）的計算公式如下：
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
−
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛−
=
−
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
1
11
)!(! !m
n
m
n
mnm n
m
n
⎩
⎨
⎧
−−+−
==
=otherwise;)1,1(Bino),1(Bino
or0if,1
),(Bino mnmn
nmm
mn
求Bino(5,3)的值？（5分）
求Bino(5,3)時，共呼叫 Bino 此函數多少次？（5分）
當n, m
N
∈且n≥m≥0求Bino(n, m)時，共呼叫 Bino 函數 T(n, m)次，求 T(n, m) =？
（10 分）