加載中. ..
PDF
100
年公務人員升官等考試、
100
年關務人員升官等考試試題
代號：
36160
等 別： 薦任
類 科： 資訊處理
科 目： 資料結構
考試時間： 2小時
座號：
※注意：
可以使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
全一張
（
正面
）
一、複雜度big-Oh O的定義為：f(n) = O(g(n)) 若且唯若存在一實數c＞0和一整數n0＞0，使
得對所有整數n≧n0，f(n) ≦ cg(n)皆成立。假設有如下的程式：
1. Procedure Sum(A, n)
2. sum = 0;
3. i = 0;
4. while(i< n) {
5. sum Å sum + A[i];
6. i = i+1; }
7. return sum;
設敘述 2執行一次需 1個單位時間，敘述 3執行一次需 1個單位時間，敘述 4執行
一次需 2個單位時間，敘述 5執行一次需 3個單位時間，敘述 6執行一次需 2個單
位時間，敘述 7執行一次需 1個單位時間。
對一個含 n個元素的陣列 A，執行呼叫 Sum(A, n)需要花多少個單位時間？（註：
只需計算敘述 2-7 所花的時間即可。）（5分）
此程式之時間複雜度（time complexity）為何？以 big-Oh 表示之，並請用上述的
定義證明答案的正確性。（註：無證明者此小題不給分。）（10 分）
若A含有八個整數 60, 5, 25, 20, 35, 10, 15, 85，請問呼叫 Sum(A, 8)的回傳值為何？
（5分）
二、假設有一個雙鏈結串列（doubly-linked list）L，如圖 1所示。此串列中的每一個節
點（node）有三個欄位：前指指標、存放的資料、後指指標。此外，有一個 header
存放指到第一個節點的指標（pointer），有一個 trailer 存放指到最後一個節點的指
標。節點中的前指指標指到上一個節點或 header，後指指標指到下一個節點或
trailer。如圖 1所示，header 的位址是 800，trailer 的位址是 150，存放 BMI 資料的
節點的位址是 600，存放 PVD 資料的節點的位址是 300，存放 JFK 資料的節點的位
址是 700，存放 SFO 資料的節點的位址是 1100。
將資料 NYU 插入在存放 JFK 資料的節點
之前，且此新節點的位址是 850。請畫出
插入後的 L。（5分）
圖1
續前，將存放 JFK 資料的節點刪除。請畫
出刪除後的 L。（5分）
續前，將資料 KAH 插入並成為第一個節點，
且此新節點的位址是 400。請畫出插入後
的L。（5分）
續前，將 L的最後一個節點刪除。請畫出
刪除後的 L。（5分）
100
年公務人員升官等考試、
100
年關務人員升官等考試試題
代號：
36160
等 別： 薦任
類 科： 資訊處理
科 目： 資料結構
全一張
（
背面
）
三、假設有 10 個整數 42, 22, 32, 74, 47, 52, 94, 29, 40, 58，請利用雜湊（hash）函數
h(k) = k%11 及線性探測（linear probing）碰撞解決法，建立一個 11 個元素的雜湊表
（hash table）。（註：a%b 是表示 a除以 b的餘數。）
請畫出此雜湊表。（10 分）
將22 刪除，請畫出刪除後的雜湊表。（10 分）
四、圖 2為一個圖型（graph）。
請利用廣度優先搜尋法（breadth-first search, BFS），從節點 c開始，列出此圖型
的所有節點。請將字元較小的節點優先列出。（10 分）
請利用深度優先搜尋法（depth-first search, DFS），從節點 c開始，列出此圖型的
所有節點。請將字元較小的節點優先列出。（10 分）
圖2
五、假設有一個二元樹（binary tree）如圖 3所示，定義一個自創追蹤法如下：對於任一
個節點（node），其右子節點先印出，這個節點印出，然後其左子節點才印出。
請問圖 3的自創追蹤為何？（10 分）
若圖 3為一個二元搜尋樹（binary search tree），請問其自創追蹤有何特性？
（10 分）
圖3