【站僕】摩檸Morning>试卷(2015/04/21)

公職◆資料結構題庫 下載題庫

104 年 - 關務特考三等考試#20775 

选择:0题,非选:16题
立即測驗 
我要補題 回報試卷錯誤 試卷下載

【非選題】

一、 ,兩項式係數的組合遞迴演算法公式如左。

【題組】 請用你熟悉的程式語言,撰寫此遞迴函式。(5 分)

#19145
編輯私有筆記
1F
Zhe Zhen Hong (2015/05/17 23:48):
int c(int r,int n) {if(r>n) return 0; else if(n==r || r==0) return 1; else return c(n-1,r)+c(n-1,r-1); }
2F
frank9732 (2015/06/26 10:56):
int C(int r, int n){ if(r > n){ return 0; } else if(r == n || r == 0){ return 1;} else return C(n-1, r) + C(n-1, r -1) }

【非選題】【題組】若 n=5, r=3,請用二元樹畫出其遞迴呼叫的情形。(5 分)

#19146
編輯私有筆記
1F
frank9732 (2015/06/26 10:56):
5,3 -> 4,2 -> 3,2 -> 3,1 -> 4,1 ->

【非選題】【題組】最後的傳回值是多少?(5 分)

#19147
編輯私有筆記

【非選題】【題組】共遞迴呼叫幾次?(5 分)

#19148
編輯私有筆記

【非選題】

二、在計算學生成績的程式中,按成績的高低分為五級,且用 IF 指令,其程式如下:  若學生在五個等級中的分布是不平均的,分布機率如下表:
分數(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 分)

#19149
編輯私有筆記

【非選題】【題組】若用最佳化二元樹修正 IF 指令,請畫出該二元樹,並分析 IF 指令可能的比較次 數。(10 分)

#19150
編輯私有筆記

【非選題】【題組】可使用什麼資料結構,使程式指令更為精簡,並請說明。(5 分)

#19151
編輯私有筆記

【非選題】

三、佇列(Queue)結構的插入(Insert)和刪除(Delete)演算法如下:

【題組】 請問上述演算法的佇列結構,會有什麼問題存在?(5 分)

#19152
編輯私有筆記

【非選題】【題組】可用什麼資料結構解決?(5 分)

#19153
編輯私有筆記

【非選題】【題組】承上之資料結構,請寫出插入(Insert)和刪除(Delete)演算法。(10 分)

#19154
編輯私有筆記

【非選題】

四、圖形的理論是起源於西元十八世紀,有一位數學家尤拉(Eular)為了解決「肯尼茲 堡橋樑」問題,而想出的一種圖形結構理論。所謂的「肯尼茲堡橋樑」問題是:某 一個人由某地點出發,最後再回到原點,必須要經過每一座橋,並且只能經過一 次。如下圖所示:

【題組】 請問肯尼茲堡的人有無可能走過所有的橋樑 1 次,到過每個地方,而後又回到肯 尼茲堡?(5 分)

#19155
編輯私有筆記

【非選題】【題組】土地代表頂點 A,B,C,D,橋樑代表邊 1~7,請畫出此圖形結構。(5 分)

#19156
編輯私有筆記

【非選題】【題組】數學家尤拉(Eular)對「肯尼茲堡橋樑」問題所找出的規則是什麼?(5 分)

#19157
編輯私有筆記

【非選題】【題組】請舉一個具有尤拉循環(Eulerian Cycle)的例子,並寫出其路徑。(5 分)

#19158
編輯私有筆記

【非選題】

五、學生的學號格式是(N1N2N3N4N5N6N7),假設儲存空間為 99,請用數字分析法 (Digital Analysis),分別以學號為鍵值(Key)雜湊(Hashing)出其資料儲存的 位址。數字的分布曲度(Skewness)設為 sk,則,其aij表示Ni出現的個數。

【題組】請依下列五位學生的學號算出其ski值。(10 分)
Student 1 ID: 0392018
Student 2 ID: 0392124
Student 3 ID: 0392238
Student 4 ID: 0252714
Student 5 ID: 0392468

#19159
編輯私有筆記

【非選題】【題組】請寫出此五位學生儲存的位址。(5 分)

#19160
編輯私有筆記