資訊處理 104 年資料結構考古題

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年國軍上校以上軍官轉任公務人員考試試題 考 試 別： 關務人員考試

佇列（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 Cycle）的例子，並寫出其路徑。（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 分） 肯尼茲堡

請寫出圖(2)所示二元樹的前序、中序和後序走訪。（6 分）

資料20、30、10、50、60、40、45、5 ㈠請建立成一棵AVL 樹，（6 分）㈡請依序 刪除60 及30，在推導過程需註明旋轉的類別。（6 分）

若採雜湊搜尋法中的移位折疊相加法，且m=1000，請推導鍵值x=123456789 的儲 存位址在那裡？（5 分） 九、請推導圖(3)之拓撲排序。（10 分） 十、有一二維陣列A(-1:5, -4:2)之啟始位址A(-3,-4) = 100，以列為主排列，請問A(1,1)所 在位址？（6 分）若以行為主排列，請問A(1,1)所在位址又如何？（6 分）（假設陣 列內元素長度都為1） 圖(2) 圖(3)