關務三等資料結構: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,其鄰接矩陣
(一)請使用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分)。
答:
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
六、請推算下圖中,由節點 S 到其他各點的最短路徑長度以及路徑所需經過的節點。(10分)
答:
請到「露天拍賣」購買 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分)
(三)設計一個 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分)
答:
請到「露天拍賣」購買 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分)
答:
請到「露天拍賣」購買 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