關務三等資料結構：無
身心障礙人員三等資料結構：無
鐵路特考高員三級資料結構：107
高考三級資料結構：107
專利商標審查人員三等資料結構：無
關務人員升官等薦任資料結構：無
資訊技師高等資料結構與資料庫及資料探勘：107
地方特考三等資料結構：107
107年公務人員特種考試警察人員、一般警察人員考試及
107年特種考試交通事業鐵路人員考試試題 代號：70670 全一頁
考 試 別：鐵路人員考試
等 別：高員三級考試
類 科 別：資訊處理
科 目：資料結構
考試時間：2小時 座號：____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、若已知一個二元樹 (binary tree) 的節點數 (node) 總共有305個，且有104個樹葉節點 (leaf node)，試求出分支度 (degree of branch) 為1的節點數有多少個？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、已知一個二元樹 (binary tree) 的後序追蹤 (postorder traversal) 為FEACGHBD，而中序追蹤 (inorder traversal) 為 EFADCBGH，其中字母 A 到 H 分別代表一個節點的名稱。
(一)請畫出此二元樹。（10分）
(二)請寫出此二元樹的前序追蹤 (preorder traversal)。（5分）
(三)請寫出此二元樹的廣度優先走訪順序 (breadth-first traversal)。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、給定一權重圖 (weighted graph) 如下：
(一)試寫出下圖的相鄰矩陣 (adjacency matrix) 及相鄰串列 (adjacency list)。（10分）
(二)請使用Kruskal 演算法找出下圖的其一種最小生成樹 (minimum spanning tree)，並寫出最小生成樹的邊之建構順序。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、今有八個數字：6、12、7、9、15、10、4、11儲存於陣列中，由不同演算法進行遞增排序。
(一)請按照合併排序法 (merge sort) 步驟，列出此八個數字的順序變化過程。（10分）
(二)請按照快速排序法 (quick sort) 步驟，列出此八個數字的順序變化過程。（10分）
(三)如果輸入 n 筆資料時，請寫出這二種排序法之時間複雜度以及空間複雜度。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
五、請使用虛擬碼 (pseudocode) 或 C 語言或 C++ 語言撰寫(一)程式片段。
(一)以遞迴的呼叫方式寫出二元搜尋法 (binary search)。（10分）
(二)根據所寫的虛擬碼或程式碼，寫出二元搜尋法之時間複雜度。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
107年公務人員高等考試三級考試試題 代號：36350 全一頁
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、(一)請說明並比較二分搜尋 (binary search) 與一般二元搜尋樹 (binary search tree) 兩者在儲存鍵值並應用來進行搜尋鍵值功能時，在 ‘建置’ 與 ‘搜尋’ 程序上作法與效能的差異（13分）。
(二)若有 n 個鍵值，以下列甲和乙兩種資料結構策略儲存：
策略甲：由小到大依序儲存在一陣列中
策略乙：以 AVL tree 架構儲存
請以 Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或兩者效能相近：1.尋找特定鍵值 k；2.尋找排序為 j 的鍵值；3.刪除特定鍵值 k；4.刪除排序為 j 的鍵值；5.插入新鍵值；6.依序輸出所有鍵值。（12分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、一非空的二元樹 (binary tree)，如果有 n0 個葉節點 (leaf node) 且 n2 個節點之分支度 (degree) 為2，請證明 n0 = n2+1。（25分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、一無向圖 G 之節點集合為 G(V) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，邊集合為 G(E) = {(0, 1), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (5, 6), (5, 7), (6, 7), (7, 8), (7, 9)}；請列出 G 之接合點 (articulation point) 和畫出 G 的所有雙連通元件(biconnected component)，雙連通元件須以節點和邊構成之子圖方式表示。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、對稱式最小-最大堆積 (Symmetric Min-Max Heap，簡稱 SMMH) 是一種優先佇列 (priority queue)，請回答下列與 SMMH 相關的問題。
(一)請說明 SMMH 特性並說明以 SMMH 建構之優先佇列與以一般的堆積 (heap) 建構之優先佇列功能有何不同？並從一個空的 SMMH 開始，依序插入30, 20, 50, 5, 4, 9, 70, 2, 80。請畫出最後 SMMH 的樹狀結構圖。（10分）
(二)請畫出第(一)小題建構的 SMMH，刪除數字2後 SMMH 的樹狀結構圖。（5分）
(三)請以一維陣列設計一資料結構儲存 SMMH，該資料結構可以使節點透過其對應之陣列索引值 x 構成的數學式計算出其祖父節點 g、父節點p、左子節點 l、右子節點 r 與兄弟節點 s 等在陣列中的索引值。假設一維陣列之起始索引值為0，請列出由 x 構成之計算 g、p、l、r、s的數學式。並請畫出以此一維陣列儲存第(一)小題建構完成的 SMMH的結果。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
|
代號：01310 頁次：3-1 |
107年專門職業及技術人員高等考試建築師、技師、第二次食品技師考試暨普通考試不動產經紀人、記帳士考試試題 |
等 別：高等考試
類 科：資訊技師
科 目：資料結構與資料庫及資料探勘
考試時間：2小時 座號：____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、某個以列為主 (row-major) 儲存的二維陣列 A[0..7][0..5]，若 A[2, 3] 的位址為108410，A[5, 1] 的位址為114810，則 A[3, 4] 的位址為多少？若改以行為主 (column-major)，則 A[3, 4] 的位址又為多少？請寫出計算式並說明。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、下列為一棵高度平衡二元樹 (AVL tree)，若依序加入資料：65、55，該如何調整此 AVL 樹？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、給予一中序追蹤 (inorder traversal) ABCDEGHF 和前序追蹤 (preorder traversal) DBACEFGH，請畫出其對應的二元樹，並詳繪左右節點。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、請對下列無方向圖形進行廣向優先走訪 (breadth first search)，從頂點1開始。
(一)請寫出演算法及其走訪過程所需資料結構之使用方式，搜尋時請依照頂點編號由小而大放入該結構，如：若需放入1、4、6 三個頂點則先放入1再放入4再放入6。（5分）
(二)請由左而右依序寫出對該圖形進行搜尋的拜訪順序，例如：1, 2, 3, ......
表示先拜訪1再拜訪2再拜訪3 ......。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
五、下列兩題為有關資料庫關聯代數的運算：
(一)下面為兩個關聯資料表 T1 和 T2 的內容，若對 T1 和 T2 進行除法運算 (DIVIDE)後得到一個關聯資料表 T3，請寫出 T3 的內容。（5分）
(二)下面為兩個關聯資料表 R1 和 R2 的內容，其中 X 為其共同屬性(common attribute)，若對 R1 和 R2 進行 LEFT OUTER JOIN 後得到一個關聯資料表 R3，請寫出 R3 的內容。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
六、有一關聯資料表 S 之關聯綱要 (relation schema) 如下，其中除了主鍵之相依性外，若以 → 表示相依性 (functional dependency)，該表還存在著右列的相依性，A→B; A→C; D→E; D→F
請將該關聯資料表修改成符合第二正規化之 (second normal form) 格式，並寫出其關聯綱要。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
七、下列關聯資料表 EMP 為員工的紀錄，其中 DEPT_ID 為員工所屬部門代碼，請以 SQL 敘述寫出下列查詢：
(一)列出薪資最高的員工姓名。（5分）
(二)列出每個部門的平均薪資和部門的代碼。（5分）
(三)列出員工姓名以「M」開頭的員工姓名和薪水。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
八、請說明下列工作是否為資料探勘 (data mining) 的工作：（每小題2分，共10分）
(一)根據客戶的年齡將客戶分類
(二)根據客戶按時繳交帳款的機率將客戶分類
(三)根據居民的居住地區將居民分類
(四)根據居民的糖尿病罹患機率將居民分類
(五)根據歷史的價格預測股票的未來價格
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
九、何謂巨量資料 (big data)？（5分）它有 4V 的特性，其中一個 V 代表 Veracity，意指資料真實性。請說明另外三個 V 是指什麼？（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
|
代號：33780 頁次：2-1 |
107年特種考試地方政府公務人員考試試題 |
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目得以本國文字或英文作答。
一、計算正整數 a 和 b 的最大公因數 gcd(a, b) 的演算法，以類似 C 語言表示如下：
1 integer gcd(a, b) {
2 x = a; y = b;
3 while(y > 0) { r = x%y; x = y; y = r; }
4 return x;
5 }
其中資料型態 integer 表示整數，x%y 表示 x 除以 y 的餘數。請回答下列問題：（每小題10分，共20分）
(一)請證明：輸入任意兩個正整數，此程式執行一定時間後就會停止，不會造成無窮迴圈。
(二)假設 a > b，請證明此程式之 while 迴圈 (第3行) 至多只會被執行2 log2b+1次。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、給定一個權重圖 (weighted graph)，G = (V, E, w)，假設 V = {1, 2, ..., n}，且每個邊 (edge) e 的權重 w(e) 都是正整數。令 l(v) 為以 v 為端點的所有邊中權重最小的邊。將這些邊集合起來稱作 L，也就是 L =<圖8>pic8。
（每小題5分，共20分）
(一)假設每個邊的權重都不相同。請證明由 L 中這些邊所構成的子圖 (edge induced subgraph) G[L] 沒有迴圈。
(二)G[L] 是否一定是 G 的擴張樹 (spanning tree)？若是請證明之，若不一定是請給一個反例。
(三)用以上之結論，設計一個計算 G 的最小權重擴張樹 (minimum spanning tree) 的演算法。
(四)在一般的應用中，邊的權重可能會相同，請修正上述之演算法，使修正後之演算法可以正確找出答案。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、假設陣列 A[1..n] 儲存 n 個正整數 x1, x2, ..., xn。（每小題10分，共20分）
(一)已知所有的正整數 xi ≦ M。請設計一個 O(n+M) 時間的演算法將這些整數由小到大排列。
(二)已知所有的正整數 xi ≦ n2。請設計一個 O(n) 時間的演算法將這些整數由小到大排列，或證明這是不可行的。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、假設有個陣列 A[1..n] 儲存著 n 個整數。可將 A[1..n] 看成二元樹，其中A[1] 是樹根。A[i] 的左右子節點分別為 A[2i] 和 A[2i+1], i = 1, 2, ..., n/2。若 2i > n 或 2i+1 > n，則這些子節點是不存在的。若 A 滿足 A[i] ≧max{A[2i], A[2i+1]},1 ≦ i ≦ n/2，則稱陣列 A[1..n] 是一個堆疊 (heap)。假設有個副程式 sift(A, r, n) 其輸入參數 A 是一個陣列，n 是 A 的大小，r ≦ n 是一個指標，指向此子樹的樹根。副程式 sift(A, r, n) 的功能是將 A[r] 為樹根的子樹變成 heap。在呼叫 sift(A, r, n) 之前，它的左右子樹都已經是 heap。副程式 sift(A, r, n) 所需的計算時間是 O(h(r))，其中 h(r) 是以 A[r] 為樹根的子樹的高度，也就是從樹根到任一樹葉的最長距離。
（每小題10分，共20分）
(一)用 sift(A, r, n) 設計一個線性時間的演算法，將陣列 A[1..n] 變成 heap。
(二)分析以上所設計演算法的計算複雜度為 O(n)。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
五、斐波納契數 (Fibonacci number) Fn 的定義是 F0 = 0, F1 = 1, Fn = Fn-1+Fn2, n > 1。計算 Fibonacci number Fn 的演算法，以類似 C 語言表示如下：
1 integer f[N]; // array of N integers
2 integer F(n) {
3 if (f[n] < 0)
4 f[n] = F(n-1)+F(n-2);
5 return f[n];
6 }
7 integer Fib(n) {
8 f[0] = 0; f[1] = 1;
9 for (i = 2; i ≦ n; i = i+1)
10 f[i] = -1;
11 return F(n);
12 }
其中資料型態 integer 表示整數。假設輸入的整數 n > 1。主程式執行 Fib(n)，則副程式 F(n) 第4行之指令：
f[n] = F(n-1)+F(n-2) 會被執行幾次？請說明理由。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
留言列表
國考資訊處理解答 (7)
