加載中. ..
PDF
104年公務人員特種考試關務人員考試、
104年公務人員特種考試身心障礙人員考試及
104年國軍上校以上軍官轉任公務人員考試試題 代號：10460 全一張
（正面）
考 試 別： 關務人員考試
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
考試時間： 2小時 座號：
※注意： 禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、Cn
r=
0,
1, 若r>n
若 n==r
1, 若 r==0
Cr
n-1+Cr-1
n-1,其他
，兩項式係數的組合遞迴演算法公式如左。
請用你熟悉的程式語言，撰寫此遞迴函式。（5分）
若n=5, r=3，請用二元樹畫出其遞迴呼叫的情形。（5分）
最後的傳回值是多少？（5分）
共遞迴呼叫幾次？（5分）
二、在計算學生成績的程式中，按成績的高低分為五級，且用 IF 指令，其程式如下：
if S<60
then G = ‘F’
else if S<70
then G = ‘D’
else if S<80
then G = ‘C’
else if S<90
then G = ‘B’
Else G = ‘A’
若學生在五個等級中的分布是不平均的，分布機率如下表：
分數（Score）90-100 80-89 70-79 60-69 0-59
等第（Grade）A B C D F
機率 0.05 0.30 0.50 0.1 0.05
假設學生人數為 5000 人，請回答下列問題：
請畫出 IF 指令的二元樹分析圖並分析此 IF 指令可能的比較次數。（10 分）
若用最佳化二元樹修正 IF 指令，請畫出該二元樹，並分析 IF 指令可能的比較次
數。（10 分）
可使用什麼資料結構，使程式指令更為精簡，並請說明。（5分）
104年公務人員特種考試關務人員考試、
104年公務人員特種考試身心障礙人員考試及
104年國軍上校以上軍官轉任公務人員考試試題 代號：10460 全一張
（背面）
考 試 別： 關務人員考試
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
三、佇列（Queue）結構的插入（Insert）和刪除（Delete）演算法如下：
const int N=10; int Rear=0, Front=0;
void Insert(char item, char Queue[]) void Delete(char item, char Queue[])
{ if (Rear==N-1) { if (Front==Rear)
cout<<“Queue Is Full”; cout<<“Queue Is Empty”;
else else
{ Rear=Rear+1; { Front =Front + 1;
Queue[Rear]=item; item = Queue[Front];
} }
} }
請問上述演算法的佇列結構，會有什麼問題存在？（5分）
可用什麼資料結構解決？（5分）
承上之資料結構，請寫出插入（Insert）和刪除（Delete）演算法。（10 分）
四、圖形的理論是起源於西元十八世紀，有一位數學家尤拉（Eular）為了解決「肯尼茲
堡橋樑」問題，而想出的一種圖形結構理論。所謂的「肯尼茲堡橋樑」問題是：某
一個人由某地點出發，最後再回到原點，必須要經過每一座橋，並且只能經過一
次。如下圖所示：
請問肯尼茲堡的人有無可能走過所有的橋樑 1次，到過每個地方，而後又回到肯
尼茲堡？（5分）
土地代表頂點 A,B,C,D，橋樑代表邊 1~7，請畫出此圖形結構。（5分）
數學家尤拉（Eular）對「肯尼茲堡橋樑」問題所找出的規則是什麼？（5分）
請舉一個具有尤拉循環（Eulerian Cy cle）的例子，並寫出其路徑。（5分）
五、學生的學號格式是（N1N2N3N4N5N6N7），假設儲存空間為 99，請用數字分析法
（Digital Analysis），分別以學號為鍵值（Key）雜湊（Hashing）出其資料儲存的
位址。數字的分布曲度（Skewness）設為 sk，則ski=∑
=9~0 1-
j
ij |a| ，其aij表示Ni出現的個數。
請依下列五位學生的學號算出其ski值。（10 分）
Student 1 ID: 0392018
Student 2 ID: 0392124
Student 3 ID: 0392238
Student 4 ID: 0252714
Student 5 ID: 0392468
請寫出此五位學生儲存的位址。（5分）
肯尼茲堡