關務三等資料結構：103

鐵路特考高員三級資料結構：103

高考三級資料結構：103

檢察事務官三等資料結構：無

專利商標審查人員三等資料結構：無

關務人員升官等薦任資料結構：無

資訊技師高等資料結構：103

地方特考三等資料結構：103

 

[一○三年關務三等資料結構]

103年公務人員特種考試關務人員考試、103年公務人員特種考試身心障礙人員考試及103年國軍上校以上軍官轉任公務人員考試試題

代號：10560 全一頁

考 試 別：關務人員考試

等    別：三等考試

類    科：資訊處理

科    目：資料結構

考試時間：2小時                                座號：_____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

 

一、有一整數數列 f(n) = 2*f(n-1)-f(n-2)+f(n-3), 3≤n, f(0) = 0, f(1) = 1, f(2) = 2。

(一)請使用 C 或 Java 語言，寫一非遞迴 (non-recursive) 副程式，此副程式輸入為一整數參數 3≤i，回傳此數列 f(i) 的數值。（12分）

(二)請計算 f(10) 的數值。（8分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

二、一個圖形 (graph) 包含五個頂點 (vertex)，V1, V2, …, V5，其鄰接矩陣

103年資料結構分年題庫

(一)請使用Floyd的方法，計算此圖形的最短路徑長度矩陣 (shortest path length matrix)，來表示任兩頂點間最短路徑長度。（10分）

(二)請使用Prim 的方法，繪出此圖形的最小成本擴張樹 (minimum cost spanning tree)。（5分）

(三)在任一圖形中，兩頂點在此圖形的最小成本擴張樹上的路徑，是否為這兩個頂點在此圖形上的最短路徑，請舉例說明。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

三、(一)請繪出一二元樹來表示運算式 (expression)-a+b/(c-d)-a*b/c+d。（8分）

(二)請列出此二元樹的後序走訪 (postorder traversal)、深度優先走訪(depth-first search traversal)及廣度優先走訪 (breadth-first search traversal)。（12分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

四、請使用 C 或 Java 語言寫一副程式 void FindMinMax(int [] A, int Min, int Max)，此副程式對一個長度為10的整數陣列 A[0:9]，最多花費15次的數值比較運算，尋找陣列中的最小值及最大值，並分別存入 Min 及 Max。（20分）（注意：請加註解說明程式碼作法）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

五、(一)陣列 (array)、鏈結串列 (linked list) 是常見的線性資料結構 (linear data structure)。請列舉兩種非線性的資料結構 (non-linear data structure)。（8分）

(二)在巨量資料 (big data) 分析中，何謂結構化資料 (structured data)？請舉例說明（6分）；何謂非結構化資料 (unstructured data)？請舉例說明（

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

[一○三年鐵路特考高員三級資料結構]

103年公務人員特種考試警察人員考試

103年公務人員特種考試一般警察人員考試             代號：71070  全一張

103年特種考試交通事業鐵路人員考試試題

等    別：高員三級鐵路人員考試

類    科：資訊處理

科    目：資料結構

考試時間：2小時                                    座號：_____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

 

一、有一個 N×N 的上三角矩陣，每個元素占一個 Byte。

(一)試以最少的記憶體儲存之，請說明應用何種資料結構？（5分）

(二)總共用多少記憶體空間？（5分）

(三)若矩陣第一個元素 (0,0) 在位址 S，請分別以 Row-Major 及Column-Major Ordering 寫出矩陣任意元素 (i, j) 所在位址的表示式。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

二、請將下列運算式由中序 (Infix) 改為後序 (Postfix) 及前序 (Prefix) 表示法，(A-B) ^ (X+D) ^ (Y-4%H) * G-6 / (F+2) + C。

其中 ^為指數運算符號、%為取餘數運算符號。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

三、已知有一個二元樹的前序搜尋 (Preorder) 結果為 “ABDGHCE”，且其後序搜尋 (Postorder) 結果為 “GHDBECA”。(一)請問由前述二個結果，是否可以得到唯一的二元樹（4分）？(二)前小題若為是，請畫出此唯一的二元樹；否者，請畫出二個二元樹，可得出具有前述前序搜尋與後序搜尋之結果（6分）。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

四、有一組原始的整數序列為 56, 18, 79, 7, 42, 96, 35, 66，請分別以 Insertion sort 及 Quick sort 的方法寫出將此一數列由小到大的排序過程。注意：是寫出排序的過程，不只是排序結果。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

五、請寫出下列圖形結構的相鄰串列 (Adjacent List)（串列順序應依節點編號由小至大表示）（6分）。並請依此相鄰串列畫出以 S5 為起點之 DFS 展開樹(DFS Spanning Tree) 及 BFS 展開樹 (BFS Spanning Tree)（14分）。

103年資料結構分年題庫

 

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

六、請推算下圖中，由節點 S 到其他各點的最短路徑長度以及路徑所需經過的節點。（10分）

    

103年資料結構分年題庫

 

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

七、已知使用 Linked List 為 Stack 的類別 (Class) 宣告如下，請寫出其 Delete (Pop) 的函式 (Functions)。（10分）

template <class T>

class Node {

friend LinkedStack<T>;

private:

T data;

Node<T> *link;

};

template <class T>

class LinkedStack {

public:

LinkedStack() {top = 0;}

~LinkedStack();

bool IsEmpty() const {return top == 0;}

bool IsFull() const ;

T Top() const ;

LinkedStack<T>& Add(const T& x);

LinkedStack<T>& Delete(T& x);

private:

Node<T> *top; // pointer to top node

};

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

[一○三年高考三級資料結構]

103年公務人員高等考試三級考試試題                 代號：26850  全一張

類    科：資訊處理

科    目：資料結構

考試時間：2小時                                座號：_____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

 

一、給一個排序好的陣列 (Sorted Array) A[low...high]，當我們要搜尋一個元素X是否在此陣列A中，二元搜尋法 (Binary Search) 是檢查陣列的中間位置的元素 A[next], next =，和 X 做比較，並依比較結果作下列更新。

Case：

A[next]=X：return

A[next]>X：high←next-1

A[next]<X：low←next+1

重複上述步驟搜尋更新的陣列 A[low...high] 直到找到 X 或確認 X 不是在此陣列 A 中。若我們設計一個新的搜尋法來修改二元搜尋法，每次都是以下列方式選取 A[next]。

next←low+(high-low) * (X-A[low]) / (A[high]-A[low])

其他步驟都和二元搜尋相同。請回答下列問題：（每小題5分，共15分）

(一)新的搜尋法特色為何？請說明之。

(二)新的搜尋法在何種情形下，會比二元搜尋的搜尋速度為佳？請說明之。

(三)新的搜尋法，在最差的情況下，它的執行時間複雜度為多少？原因為何？假設陣列 A 中有 n 個元素。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

二、L為一鏈結串列 (Linked List)，函數 Reverse(L) 是要求把在原來 L 的每個節點 (Node) 的地址指標 (Pointer)，更改為指向它在鏈結串列 L 中的前面一個節點。請設計一個以疊代 (Iterative) 方式的程式來執行函數 Reverse(L) 的功能，程式限制只能使用常數個 (constant) 額外空間 (External Memory)，可用程式語言 C、C++、Java 或 Pseudocode，寫出你的答案。請先說明你的作法，再寫出程式。（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

三、若只能使用下列6種方式排序 (Sorting)：(a)Insertion Sort (b)Radix Sort (c)Merge Sort (d)Counting Sort (e)Heap Sort (f)Quick Sort。在下列各情形下，應選擇上述何種排序方法為最佳？請說明原因。（每小題5分，共15分）

(一)只要將全部資料中的前20名最大值排序好，並且主記憶體空間足夠。

(二)只有少數資料在被已排序好的資料修改過，需要重排序，並且主記憶體空間足夠。

(三)資料無明顯特性，需要做第一次的排序，並且主記憶體空間足夠。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

四、如右的權重圖 (weighted graph) 共有9個節點 (vertices) 19條邊 (edges)，回答下列問題：

(一)請列出在運用 Kruskal’s 演算法產生最小連結樹 (Minimum Spanning Tree) 中把邊納入最小連結樹的順序。（3分）

(二)請列出運用 Prim’s 演算法從 A

  點開始產生最小連結樹，把邊納

入最小連結樹的順序。（4分）

103年資料結構分年題庫

 

(三)設計一個 O(V) 的演算法，判定在新增加一個 (x, y) 的邊到原圖形後，是否要更新已經產生的最小連結樹。（8分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

五、若處理的資料，其數值均不同且已知均為1到100之間的整數或小數。若K ≦X＜K+1，集合 Lx 代表數值在 [K,K-1] 間全部資料，1≦K≦99, K為整數，資料結構支援下列功能。

1.Insert(X)：增加 X，若 X 不存在 Lx 中。

2.Delete(X)：移除 X，若 X 存在 Lx 中。

3.List(X)：將 Lx 中的資料全部依序印出。

設計一資料結構滿足在最差情況的條件分析 (Worst Case Analysis)，每個功能的執行時間要求為：Insert(X) and Delete(X) 須在 O(log|Lx|) 時間內完成，List(X) 則須在 O(|Lx|) 時間內完成。請說明設計的資料結構為何？並解釋其執行時間為何滿足需求？（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

六、若 G = (U, E) 為一權重圖 (weighted graph)，每條邊的權重均不為負數，則單源最短路徑問題 (Single Source Shortest Path Problem) 可以用著名的Dijkstra 演算法求得，回答下列問題：（每小題5分，共15分）

(一)說明 Dijkstra 演算法的主要觀念。

(二)Dijkstra演算法在最差情況下 (Worst Case Analysis)，下列三個功能Insert、Delete、Decrease_Key 各自需要執行的次數，可用 Big-Oh 符號表示。

(三)若是要在O(|E|+|V|log|V|) 最差情況分析下的時間內執行Dijkstra演算法，請問該選擇使用那種資料結構，並說明其原因。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

七、下面二小題各有一段程式，其執行的時間是以執行 sum++ 的次數計算，請用 Θ-notation 表示其執行時間，並說明其理由。（每小題5分，共10分）

(一)sum=0

for(i=0; i<2*n; i++)

for(j=0; j<i; j++)

sum++;

(二)sum=0

for(i=1; i<2*n; i++)

for(j=1; j<i*i; j++)

for(k=1; k<j; k++)

if(j%i==1)

sum++;

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

[一○三年資訊技師高等資料結構]

103年專門職業及技術人員高等考試建築師、技師、第二次

食品技師考試暨普通考試不動產經紀人、記帳士考試試題  代號：01310 全一頁

等    別：高等考試

類    科：資訊技師

科    目：資料結構（包括資料庫）

考試時間：2小時                                 座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

 

一、試使用下列三種資料結構各設計一個優權工作佇列 (priority job queue)，針對插入 (insert)、擷取 (extract) 操作，比較時間複雜度。

(一)線性結構 (linear structure)。（5分）

(二)二元搜尋樹 (binary search tree)。（5分）

(三)最大堆積 (max heap)。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

二、(一)試述靜態雜湊 (static hashing) 設計時所需考量的課題、優缺點、使用上的限制。（10分）

(二)試述動態雜湊 (dynamic hashing) 之設計及結構，並申論是否能解決上述(一)之缺點及使用上的限制。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

三、當有巨量資料需要排序 (sort) 而記憶體工作區 (RAM buffer) 卻有限，必須使用外部排序 (external sort) 或多線會合排序 (multi-way merge sort)。資料以頁 (disk page) 的方式存放在磁碟機。

(一)試以磁碟讀取寫入 (disk I/O access) 的次數評論排序效能與資料量 N 頁、記憶體工作區大小 B 頁的關聯。（10分）

(二)以資料量 N = 136 pages，記憶體工作區 B = 5 pages 為例說明。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

四、一個大型資料庫系統資料庫有 N 筆紀錄 (data records)，B+-tree 是一個常用的索引結構，而整個B+-tree 也存放在磁碟機中。B+-tree 的一個節點(node) 占一個區塊 (disk block) 大小 b bytes，資料鍵值 (key value) 需 k bytes，區塊位址指標 (block address pointer) p bytes，每筆紀錄位址指標 (data record pointer) r bytes。

(一)試算內部節點的量級 m (branches 數 or order in internal node)、葉節點的量級 n (branches 數 or order in leaf node) 及 B+- tree 的高度 H。m，n 以b，k，p，r 等符號表示，H 以 N，m，n 等符號表示。（12分）

(二)請就單筆資料搜尋 (search)、插入 (insert)、刪除 (delete) 操作及範圍搜尋 (range query)，評述其操作成本及效能。（13分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

五、網際網路可視為一有方向性的圖 (directed graph)，網頁的 URL 是節點(node)，網頁到網頁的鍵接是邊 (edge)。穿越 (traversal) 網頁有各種不同的瀏覽次序，試提出二種穿越 (traversal) 方法可遍歷所有可瀏覽到的網頁而不重覆，並評論其時間複雜度。如有需要額外的輔助資料結構，請說明其使用方法。（20分）

答：

請到露天拍賣購買「103年資料結構分年題庫」詳解。

 

[一○三年地方特考三等資料結構]

103年特種考試地方政府公務人員考試試題              代號：34480 全一張

等    別：三等考試

類    科：資訊處理

科    目：資料結構

考試時間：2小時                                     座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

 

一、給定一個權重圖 (weighted graph) G(V, E) 如下圖所示。

(一)請用 Kruskal 演算法找出最小生成樹 MST(G) (minimum spanning tree)。請依序寫出加入此最小生成樹的每一個邊。（5分）

(二)請用 Prim 演算法找出最小生成樹 MST(G)。若以A 為起始點，請依序寫出加入此最小生成樹的每一個邊。（5分）

(三)假設最小生成樹 MST(G) 已知。若在原圖 G(V, E) 中加入一個新的邊 vi-vj 且其權重為 w。請設計一個 O(V) 的演算法，從已知的 MST(G) 中快速找出新圖的最小生成樹。請以文字敘述說明。（10分）

(四)請說明上一小題的演算法為 O(V)。（5分）

 103年資料結構分年題庫

 

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

二、給定一個二元樹 T。若 T 之後序巡行 (postorder traversal) 結果是 P D J M O A I H K G L N E B C，而中序巡行 (inorder traversal) 結果是 J D P I A M O C K H G B E L N：

(一)請畫出該二元樹 T。（10分）

(二)請寫出該二元樹之前序巡行 (preorder traversal) 結果。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

三、請用 Dijkstra 演算法找出下圖中從 S 到 T 的最短路徑長度：

(一)請依序寫出過程中逐一加入已被選擇的頂點 (vertex)，起始頂點為 S。（10分）

(二)請問以此演算法所找出的 S 到 T 最短路徑長度為何？（5分）

103年資料結構分年題庫

 

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

四、給定一個陣列 (array) A[0], A[1],…, A[99] 用以表示一個循環佇列 (circular queue)。另外再以兩個整數變數 front 及 back 記錄該循環佇列之前端 (front of the queue) 及尾端 (back of the queue)。一個尚未有任何資料的循環佇列之 front = back = -1：

(一)若要新增加一筆資料於此循環佇列，front 及 back 變數該如何改變？（5分）

(二)若要從循環佇列中取出並刪除一筆資料，front 及back 變數該如何改變？（5分）

(三)此循環佇列最多可以儲存幾筆資料？（5分）

(四)若此循環佇列已經全滿，在未刪除任何資料前已不能再儲存新資料，請問此時 front 及 back 的關連為何？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

 

五、給定下列尚未排序之數列：80, 24, 11, 47, 19, 91, 2, 32, 85, 7, 16, 36, 99, 52, 41，請以泡沫排序法 (bubble sort) 及快速排序法 (quick sort) 分別將該數列由小到大排序：

(一)請依序寫出泡沫排序法前五回合的排序結果。（10分）

(二)請依序寫出快速排序法前五回合的排序結果，每一回合用一個樞紐(pivot)，並把每一回合所用的樞紐圈起來。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

arrow
arrow
    文章標籤
    資料結構
    全站熱搜
    創作者介紹
    創作者 jacksaleok 的頭像
    jacksaleok

    國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

    jacksaleok 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄