關務三等資料結構：99
專利商標審查人員三等資料結構：99
身心障礙人員三等資料結構：99
鐵路特考高員三級資料結構：99
高考三級資料結構：99
檢察事務官三等資料結構：99
資訊技師高等資料結構：99
地方特考三等資料結構：99
|
99年公務人員特種考試海岸巡防人員考試、99年公務人員特種考試基層警察人員考試、99年公務人員特種考試關務人員考試、99年公務人員特種考試經濟部專利商標審查人員考試、99年第一次公務人員特種考試司法人員考試及99年國軍上校以上軍官轉任公務人員考試試題 |
代號：33560 全一張 |
等 別：三等關務人員考試
類(科)別：資訊處理
科 目：資料結構
考試時間：2小時 座號：_____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本試題各題作答內容均須詳列計算或推導過程，否則不予計分。
一、假設運算子 (operator) 的運算先後次序的規則 (Precedence and Associativity) 之優先順序如下：指標 (pointer, →)、乘除、加減、比大小；同等類的運算子按照運算子在 infix expression 出現的優先次序 (例如 +、 - 為同一等類)。請列出如何利用堆疊 (stack) 轉換 infix expression：a+b/c>(d->e * f+g)/h 成 prefix 表示法。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、依序輸入下列6筆資料：L，C，E，P，S，A (英文字母代表的是 key value，而字母 A 的值是小於字母 B 的值)
(一)排成最大二元堆 (max binary heap) 後的堆積為何？（10分）
(二)刪除 (delete) 根節點 (root) 後，再加入新的值 M 後的堆積為何？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、解釋名詞：
(一)軟體開發生命週期 (software development lifecycle) 至少包含五大重要階段 (phases)，請寫出這些階段以及該階段的主要任務為何？（10分）
(二)在軟體開發上，必須要注意所謂的「安全容錯」(Fail-Safe)，試述其意義（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、以下程式的時間複雜度 (time complexity) Big-O 為何？（20分）
int C(int N, int K)
{
if ((K == 0) || (K == N))
return 1;
else if (K > N)
return 0;
else
return C(N-1, K-1) + C(N-1, K);
}
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、拓樸排序 (topological sorting) 是一個在沒有迴圈的有向性圖形 (directed graph) 找出節點順序 (Linear order)。例如，如果有一條有向連結從節點 u指向節點 v，則我們說 u v 的順序為 u 在 v 的前面。拓樸排序的演算法如下：
topSort (input Graph, output List)
s = createStack();
for (all vertices v in the graph)
if (v has no predecessors) {
Push v into s;
Mark v as visited;}
while (s is not empty) {
if (all vertices adjacent to the vertex v on the top of the stack have been visited) {
Pop v out of s;
Output v;
} else {
Push each unvisited vertex u adjacent to vertex v into s and mark u as visited; // 注意：當有一個以上的選擇時，永遠優先選擇代號數字比較小的節點先放入堆疊
}
}
(一)以下為一個有向性圖形，請利用以上程式列出所找出的節點順序。（請列出執行過程堆疊 (stack) 內的內容）（10分）
(二)如果有向性圖 G = (V, E)，節點集合的大小為 N，請問此演算法的時間複雜度 (time complexity) Big-O 為何？（請說明如何得到答案）（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
|
99年公務人員特種考試海岸巡防人員考試、99年公務人員特種考試基層警察人員考試、99年公務人員特種考試關務人員考試、99年公務人員特種考試經濟部專利商標審查人員考試、99年第一次公務人員特種考試司法人員考試及99年國軍上校以上軍官轉任公務人員考試試題 |
代號：73460 全一張 |
等 別：三等專利商標審查人員考試
類(科)別：資訊工程
科 目：資料結構（包括資料庫）
考試時間：2小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本試題各題作答內容均須詳列計算或推導過程，否則不予計分。題目如要求程式設計，請用 C 或 C-like 語言作答。
一、下圖為一網路流量圖 (network flow diagram)，每一線段上面標示該線段所能承載最大流量，箭頭代表流向。
(一)請問由 S 到 T 的最大流量為多少？每個線段流量各為多少？（10分）
(二)如線段沒有流向限制，S 到 T 的最大流量為多少？每個線段流量與方向各為何？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、下圖為一個二元樹 (binary tree)，非葉 (non-leaf) 節點為運算子 (operator)，葉節點 (leaf) 為整數運算元 (operand)。假設X為運算子，T1 與 T2 為其左右部分樹 (subtree)，則 X 這個節點可以被 X (T1, T2) 取代。請寫一個程式，輸入該二元樹，輸出其計算結果。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、請計算以下反覆函數 (recurrence function) 的時間複雜度 (time complexity)Θ()：
(一) T(n) = 8T(n/2) + 且 T(1) = 1（10分）
(二) T(n) = 4T(n - 1) - 3T(n - 2) + 1且 T(1) = 1，T(0) = 1（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、考慮一個表格 (table) T(A, B, C, D, E)，其函數相關性 (functional dependencies) 如下：AB→E, CD→E, A→C, C→A.
(一)請找出 T 所有之候選鍵 (candidate keys)，並列出推導過程。（10分）
(二) T 是不是 BCNF (Boyce-Codd Normal Form)？如是，請解釋。如不是，請分解其為符合BCNF的多個表格。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、有一個程式使用二元樹 (binary tree) 資料結構來解決問題，為避免資料遺失，二元樹的資料儲存在資料庫。二元樹節點之定義如下：
struct node{
char Cname[20];
int Ccode;
float CGA;
struct node *left;
struct node *right;
};
(一)請設計關聯資料庫，包括表格、鍵 (key) 等必要元素，來儲存該二元樹。（10分）
(二)請寫一程式 ReadTreeFromDB() 從資料庫讀取一棵完整二元樹之資料。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
99年公務人員特種考試身心障礙人員考試試題 代號：30930 全一頁
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：________________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、關於雜湊 (hashing) 的問題：（每小題10分，共20分）
(一)何謂雜湊？有何特點？
(二)常用的雜湊函數 (hashing function) 有那些？請寫出三個。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、關於資料結構中佇列 (queue) 的問題：（每小題10分，共20分）
(一)繪圖說明佇列的意義？試寫出並說明三種佇列上之運算動作(operation)？
(二)舉一例說明佇列的應用。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、關於堆疊 (stack) 共用的問題：（每小題10分，共30分）
(一)兩個堆疊共用一個陣列 (array) 空間時，應該如何安排較佳？
(二)四個堆疊共用一個陣列時，應如何安排較佳？
(三)上題(二)中，遇到某一堆疊滿溢 (stack overflow) 時，要如何解決？
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、設有一多項式如下：（10分）
試設計二種資料結構來表示此多項式。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、參考下圖 (graph)：
(一)寫出以深度優先搜尋 (depth first search) 之順序。（5分）
(二)寫出以廣度優先搜尋 (breadth first search) 之順序。（5分）
(三)試說明如何以堆疊 (stack) 完成深度優先搜尋 (depth first search) 演算法之關鍵技術。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
99年公務人員特種考試警察人員考試及
99年特種考試交通事業鐵路人員考試試題 代號：51050 全一頁
等 別：高員三級
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、為什麼需要資料結構，它對於我們解決問題有什麼幫助？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、在電腦象棋中，最主要被使用的2種資料結構為何？請解釋其用途。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、在物件導向 (object-oriented) 中，何謂 “Class”？其中有那些成員 (member)？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、請敘述如何使用程式來將兩個長度為50位數的整數相加。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、適合用來解決遞迴 (recursion) 問題的資料結構為何？其如何運作？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
99年公務人員高等考試三級考試試題 代號：36150 全一張
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、本題是關於演算法效率分析 (Algorithm and performance analysis)
(一)請分別寫出下列程式第一行 (line 1) 到第五行 (line 5) 的執行次數(frequency count)，於試卷上請標明是第幾行，次數是多少。（10分）
|
void mult(int a[][n], int b[][n], int c[][n]) { int i, j, k; for(i = 0; i < n; i++) ........................................line 1 for(j = 0; j < n; j++) .......................................line 2 { c[i][j] = 0; ...................................................line 3 for(k = 0; k < n; k++) ..............................line 4 c[i][j] += a[i][k] * b[k][j]; .............line 5 } } |
(二)於下列程式，請計算指令 x++；一共會執行多少次？（5分）
|
for (i =0; i < n ; i ++) for (j = i +1; j < n; j++) x++; |
(三)請根據下列表格的數據，size 是問題量 (或問題大小)，count 是程式指令的總執行次數，來推測程式執行的時間複雜度 (time complexity)，請以 Big-Theta θ表示之 (例如：θ(3n))。（5分）
|
size |
1,000 |
2,000 |
3,000 |
4,000 |
5,000 |
6,000 |
7,000 |
8,000 |
|
count |
11,863 |
24,227 |
40,003 |
53,217 |
67,393 |
78,961 |
91,985 |
113,997 |
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、關於字串樣式比對 (string pattern matching)，最簡單的方法是使用窮舉樣式比對法 (exhaustive pattern matching)，此即將樣式 (pattern) 的字元逐一比較本文 (text) 的字元，若不對則移下一字元繼續比對，直到比對成功或本文剩下的字元數目少於樣式長度。
(一)假設本文是：THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED，欲找尋的樣式 (pattern) 為 GENTLE，問：
1.總共比較多少次？（5分）
2.一共比較多少個字元？（5分）
(二)假設本文是一千個 “0”，欲找尋的樣式 (pattern) 為01010，請問：
1.總共比較多少次？（5分）
2.一共比較多少個字元？（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、(一)說明樹 (tree) 與二元樹 (binary tree) 有那三項主要的不同？（5分）
(二)已知某一樹其分支度 (degree) 為1的節點 (node) 有5個，分支度為2的節點有4個，分支度為3的節點有3個，分支度為4的節點有2個，分支度為5的節點有1個，請問此樹一共有幾個節點？（5分）
(三)證明：於任意一個二元樹中，若 n0 代表分支度為0的節點數目，n1 代表分支度為1的節點數目，n2 代表分支度為2的節點數目，則 n0 = n2+1。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、一個有向圖形 (directed graph)，若圖形的任何路徑 (path) 沒有環路 (cycle)，則此圖形可找到拓樸排序 (topological sorting)，問：
(一)說明什麼是拓樸排序？（5分）
(二)舉出一種拓樸排序的應用。（3分）
(三)於下圖中找出一種拓樸排序，要寫出產生的過程，最後畫出拓樸排序圖。（12分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、假設有一個陣列 A[0..12]，儲存13個數字：4，14，25，31，37，42，56，70，73，83，86，90，94。今使用二元搜尋 (binary search)，問：
(一)寫出找尋70的比較過程 (沒寫過程不予計分)。（8分）
(二)列出比較次數最多的所有數字。（6分）
(三)假設現有100,000個數字已經依由小而大的次序排列好，請分別使用二元搜尋 (binary search) 與循序搜尋 (sequential search)，計算兩者成功找尋 (successful search) 的平均比較次數，並說明兩者大概相差多少倍？（6分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
99年第二次公務人員特種考試司法人員考試試題 代號：30860 全一頁
等 別：三等考試
類 科：檢察事務官電子資訊組
科 目：資料結構
考試時間：2小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、(一)請解釋 Hash function。其主要功能及設計考量點為何？（15分）
(二)我們可以用那一種資料結構來實現它？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、在圍棋程式中，最常用的三種資料結構為何？請說明其用途。（30分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、(一)請解釋 disjoint-set data structure。（10分）
(二)請舉出一個應用的例子。我們可以用那一種資料結構來實現它？（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、我們如何在一個沒有支援 pointer 的程式語言中，利用那一種資料結構來實現 pointer？請舉例說明。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
99年專門職業及技術人員高等考試建築師、技師
代號：01310 全一頁
考試暨普通考試不動產經紀人、記帳士考試試題
等 別：高等考試
類 科：資訊技師
科 目：資料結構（包括資料庫）
考試時間：2小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、用 Big-O 表示下面函數與程式的時間複雜度：（10分）
(一) f(n) = 2n + n2 + n
(二) for (i = 0; i < n; i++) {j = i; for (k = j+1; k < n; k++) x = x+1;}
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、依下面問題，畫出雙向鏈結串列 (Doubly-linked list) 的圖形：（20分）
(一)畫出空串列頭 (empty list header node)。
(二)承上，畫出插入 (insert) 張三後的情況。
(三)承上，畫出插入 (insert) 李四後的情況。
(四)承上，畫出刪除 (delete) 張三後的情況。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、一個圖 (graph) 的五個邊 (edge) 依序輸入如下：（20分）
A, B A, D A, E D, E E, F
(一)以 A 為起點，利用堆疊 (stack)，依字母序，做深度優先搜尋 (depth-first search)，寫出搜尋結果。
(二)以 A 為起點，利用佇列 (queue)，依字母序，做廣度優先搜尋(breadth-first search)，寫出搜尋結果。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、依序加入 (insert) 下列整數到一棵空的 AVL 樹：（20分）
1, 4, 5, 3, 9, 7
(一)請繪圖顯示最後結果。
(二)然後，依序刪除 (delete) 5, 3,亦請繪圖顯示最後結果。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、有下面學生及成績兩個關聯 (Relations)：（10分）
學生 成績
學號 姓名 生日 學號 分數
90084100 張廷瑄 70.1.10 90084100 90
90089900 凌宗廷 70.3.11 91201035 80
91201035 李威廷 71.4.5 91302072 60
91302072 商揚夏 71.7.8
請問下面查詢的結果是什麼？
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
六、在關聯式代數 (relational algebra) 中，何謂完整集合 (complete set)？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
七、何謂參考完整性限制 (referential integrity constraint)？請舉例說明之。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
99年特種考試地方政府公務人員考試試題 代號：34280 全一張
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：_______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、解釋下列名詞並舉例說明：（每小題5分，共25分）
(一)演算法 (algorithm)
(二)時間複雜度 (time complexity)
(三)遞迴式的解決問題方法 (recursive solution)
(四)雙向佇列 (Deque)
(五)最小成本生成樹 (minimum cost spanning tree)
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
二、請用二元樹 (binary tree) 針對10筆資料：「陳、劉、王、蘇、高、胡、蔡、何、簡、莊」設計出以鏈結 (link) 表示的二元樹資料結構，10筆資料的排序方式可自行決定 (例如，依據筆劃數、注音符號、拼音或其他)。（每小題5分，共25分）
(一)請用任意程式語言寫出插入 (insert) 一個節點的演算法。
(二)請用任意程式語言寫出刪除 (delete) 一個節點的演算法。
(三)請用任意程式語言寫出中序 (inorder) 尋訪的演算法。
(四)請將「陳、劉、王、蘇、高、胡、蔡、何、簡、莊」及你決定並明確寫出的排序方式，用插入演算法逐一插入二元樹，請畫出最後的二元樹。
(五)請分析二元樹搜尋 (searching) 的 O( ) 時間複雜度。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、考慮某地區的地圖，地圖上有 n 個城市，城市之間共有 m 條相通的公路，每條公路有一個長度 (例如，10公里)。某人經常需從城市 S 出發，開車前往另一城市 T 送貨，請你設計一個軟體系統的資料結構與演算法，幫忙找出路程最短的建議路徑與該路徑的總長度。（每小題5分，共15分）
(一)請設計一資料結構表示出地圖之 n 個城市、m 條公路及公路長度。
(二)依據你設計的資料結構，寫出 Dijkstra 演算法，找出路程最短的建議路徑與該路徑的總長度，並舉例說明。
(三)分析 Dijkstra 的時間複雜度。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、給予資料：3, 1, 5, 7, 15, 13, 9, 11，
(一)請寫出 Shell 排序演算法。（15分）
(二)並用 Shell 排序法，將資料排成由大到小排列，請務必將每一步驟詳細畫出並詳細說明。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
五、考慮設計中式象棋 (如圖) 電腦程式系統：（每小題5分，共10分）
(一)請設計一資料結構使能隨時表示出棋盤現狀 (current state)，包含所有棋子的位置、有那些棋子在棋盤上。
(二)寫出一演算法能產生「象」或「相」在任意位置之下一步可前往且合規則的所有位置 (next feasible positions)，注意，務必考慮其他棋子阻礙的因素。「象」或「相」的移動規則：(1)田字形的對角移動；(2)田字正中央有棋子時，不能移動前往。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
留言列表
國考資訊處理解答 (7)
