關務三等資料結構：108
身心障礙人員三等資料結構：無
鐵路特考高員三級資料結構：無
高考三級資料結構：108
專利商標審查人員三等資料結構：無
關務人員升官等薦任資料結構：108
資訊技師高等資料結構與資料庫及資料探勘：108
地方特考三等資料結構：108
|
代號：10460 頁次：3-1 |
108年公務人員特種考試關務人員、身心障礙人員考試及 108年國軍上校以上軍官轉任公務人員考試試題 |
考 試 別：關務人員考試
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、下列程式函式 doit( ) 以C 語言語法呈現，用以對雙向鏈結串列 (doubly linked list) 進行處理。請依據該函式回答問題。
void doit(struct node **head) {
struct node *temp = NULL;
struct node *current = *head;
while(current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if(temp != NULL)
*head = temp->prev;
}
(一)若 X 指向一個雙向鏈結串列如下，其中 X->prev 指向 NULL，X->next指向資料為21的節點。請顯示並說明 doit(&X) 執行過後該串列變化結果。（10分）
(二)若 X 指向一個雙向鏈結串列如下，其中 X->prev 指向資料為17的節點，X->next 指向資料為35的節點。請顯示並說明 doit (&X) 執行過後該串列的變化結果。（5分）
(三)若 X 指向一個環狀雙向鏈結串列 (circular doubly linked list)，請說明doit(&X) 是否仍能順利執行。（5分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、給定 T 為一個以陣列表示的二元搜尋樹 (binary search tree)。
(一)若有一些介於1及1,000的正整數被儲存於 T，且要搜尋數字364，請說明搜尋過程是否有可能為3, 400, 388, 220, 267, 383, 382, 279, 364？（5分）
(二)若有一些介於1及1,000的正整數被儲存於 T，且要搜尋數字364，請說明搜尋過程是否有可能為926, 203, 912, 241, 913, 246, 364？（5分）
(三)若對 T 進行前序遍歷 (pre-order traversal) 的結果為30, 20, 10, 15, 25, 23, 39, 35, 42。請說明若以後序遍歷 (post-order traversal)，結果為何。（5分）
(四)若對 T 進行後序遍歷 (post-order traversal) 的結果為25, 20, 34, 37, 31, 49, 46, 57, 60, 52, 41。請說明若以中序遍歷 (in-order traversal)，結果為何。（5分）
(五)請說明可將二元搜尋樹 T 轉換為最小堆積 (min heap) 的程序為何？（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、給定以相鄰矩陣 (adjacency matrix) 表示的圖 G，矩陣中的數字為相鄰兩節點間的距離，若空白則代表兩節點不相鄰。
(一)請說明若以 Kruskal’s 演算法建立最小生成樹 (minimum spanning tree)的過程中，依序被加入生成樹的邊。（5分）
(二)請說明若以 Prim’s 演算法建立最小生成樹 (minimum spanning tree) 的過程中，依序被加入生成樹的邊。（5分）
(三)請說明 Dijkstra’s 演算法的用途，並說明該演算法應用上的限制。（10分）
(四)請說明將圖 G 從 f 節點開始執行 Dijkstra’s 演算法的過程並顯示節點加入的順序。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、請將所給定數字藉由所指定雜湊函數依序置入雜湊表
(一)若雜湊函數為 H(k) = k mod 11，並以線性探測 (linear probing) 解決溢位 (overflow) 問題，請顯示將15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12, 0, 21依序置入11桶 (buckets)×2槽 (slots) 雜湊表的最終結果。（10分）
(二)若雜湊函數為 H(k) = k mod 7，並以平方探測 (quadratic probing) 解決溢位 (overflow) 問題，請顯示將15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12依序置入7桶 (buckets)×2槽 (slots) 雜湊表的最終結果。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
|
代號：26950 頁次：2-1 |
108年公務人員高等考試三級考試試題 |
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：___________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、給予如下二元樹節點的宣告，分別寫出 C 的遞迴程式計算二元樹節點個數及計算二元樹葉節點 (leaves) 個數 (Count the number of nodes in a binary tree and count the number of leaf nodes in a binary tree, respectively)。（25分）
|
struct node { int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void countTree(NODEPTR tree) { } void countLeaves(NODEPTR tree) { } |
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、給予如下二元樹節點的宣告，寫一 C 的遞迴程式 swapTree(NODEPTR tree)將每一節點的左、右節點互換 (Swap the left and right children of every node of a binary tree)。（25分）
|
struct node { int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void swapTree(NODEPTR tree) { } |
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、給予如下程式，假設 x[ ] = [30, 75, 53, 47, 21, 94, 88, 39]，lb = 0，ub = 7，請問執行完下列程式後，x[ ] 的內容為何？（25分）
|
void divide&conquer(int x[ ], int lb, int ub, int *pj) { int a, down, temp, up; a = x[lb]; up = ub; down = lb; while(down < up) { while(x[down] <= a && down < ub) down++; while(x[up] > a) up--; if(down < up) { temp = x[down]; x[down] = x[up]; x[up] = temp; } } x[lb] = x[up]; x[up] = a; *pj = up; } |
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、用 G = (V, E) 表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點(Vertices) 形成一個邊及對應權重 (Weights) 所組成的集合，例如：
(0, 1, 28) 表示節點0至節點1有一個邊，而且權重為28。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5, 6}，E = {(0, 1, 27), (1, 2, 15), (2, 3, 11), (0, 5, 9), 1, 6, 13), (4, 5, 24), (4, 6, 23), (3, 4, 21), (3, 6, 17)}。請利用 Kruskal 演算法計算最小擴張樹 (Minimum spanning tree) 之最低權重或成本值。（25分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
|
代號：26260 頁次：2-1 |
108年公務、關務人員升官等考試、108年交通事業郵政、公路、港務人員升資考試試題 |
等 級：薦任
類 科（別）：資訊處理
科 目：資料結構
考試時間：2小時 座號：____________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、一般常用的算術運算式 (Arithmetic Expression) 有：中序運算式 (Infix Expression)、前序運算式 (Prefix Expression)、後序運算式 (Postfix Expression) 三種表示法，請回答下列問題：
(一)考慮中序運算式 (6-2)×(5+9/3)+4×7，請說明其前序與後序運算式分別為何？（8分）
(二)請說明為何中序運算式需要使用括號來輔助界定運算元的優先順序而前序與後序運算式則無需括號？（7分）
(三)請說明如何利用一個堆疊 (Stack) 結構計算出一個後序運算式的值，並以後序運算式 a b × c + d c / - 為例，其中 a = 3, b = 5, c = 2, d = 6，請逐步列出運算過程中堆疊的內容。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、以下是關於二元搜尋樹 (Binary Search Tree) 的問題：
(一)請說明二元搜尋樹的定義？（5分）
(二)是否可以使用一個二元搜尋樹對鍵值 (Key) 來進行排序 (Sorting)？如果不行，請解釋其原因。若可以，請描述作法及執行時間。（5分）
(三) AVL 樹是一個基於二元搜尋樹的資料結構，請敘述 AVL 樹的定義並說明為何一個有 n 個節點 (鍵值) 的 AVL 樹其高度是 O(log n)。（5分）
(四)若將鍵值36、25、14、27、55、30 以依序加入的方式建構一個 AVL樹，請繪出每次加入後的 AVL 樹。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、優先佇列 (Priority Queue) 用來管理具有優先權順序的資料物件，主要提供的功能有：加入 (Insert) 任意資料物件，以及移除 (Remove) 具有最高優先權的資料物件。我們在此假設鍵值 (Key) 越低的資料物件有越高的優先權，加入與移除功能分別命名為 insert( ) 及 remove_Min( )。
(一)請說明如何利用優先佇列將資料物件以鍵值進行排序。（5分）
(二)二元堆積 (Binary Heap) 是一個實現優先佇列的資料結構，請敘述其定義。（6分）
(三)若我們分別使用排序串列 (Sorted List)、未排序串列 (Unsorted List)、二元堆積三種資料結構來實現有 n 個資料物件的優先佇列，請比較這三種方式在加入 insert( ) 與移除 remove_Min( ) 功能上所需的時間複雜度。（6分）
(四)在考慮鍵值低的資料物件有高的優先權的情況下，所使用的二元堆積稱為最小堆積 (Minimum Heap)。若給定一個最小堆積與一個鍵值 k，請說明如何輸出所有鍵值小於或等於 k 的資料物件，而所花的時間 (或運算量) 與鍵值小於或等於 k 的資料物件之數量成線性比例。（8分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、一個圖形結構 (Graph) 中，若所有的邊都具有方向，則此圖形結構為一個有向圖 (Directed Graph)。
(一)一個有向圖不具有迴圈 (Cycle) 則稱為一個有向非循環圖 (Directed Acyclic Graph, DAG)，考慮下方的有向非循環圖 G，請說明 G 共有幾種不同的拓樸排序 (Topological Sort)？（7分）
(二)若在圖 G 上由節點 c 開始進行拓樸排序，並考慮字母順序進行排列，請列出此一拓樸排序並說明方法與所需要的時間複雜度。（8分）
(三)一個有向圖若具有強連通性 (Strong Connectivity)，則其中任意兩節點 u 與 v 彼此可藉由不同路徑相互連通。請提供一個驗證一有向圖是否具強連通性的方法，並說明其正確性與時間複雜度。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
108年專門職業及技術人員高等考試建築師、
25類科技師（含第二次食品技師）考試暨 代號：01310 全一頁
普通考試不動產經紀人、記帳士考試試題 座號：_____________
等 別：高等考試
類 科：資訊技師
科 目：資料結構與資料庫及資料探勘
考試時間：2小時
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、如果資料庫設計階段決定採用關聯式資料庫模型 (Relational Database Model)，在進行關聯綱要 (Relation Schema) 設計時，常需要進行正規化程序，何謂正規化 (Normalization)？為何要正規化？請寫出二項 “好” 的關聯式資料庫設計的關聯綱要設計原則 (Principles)，並請說明之。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、關聯代數 (Relational Algebra) 由那八個運算子所組成？其中那些運算子構成基本運算子 (Primitive Operators)？關聯代數運算子與資料庫結構化查詢語言 SQL 的關係為何？如何用 SQL 求一個欄位 (假設是 int 資料型態) 的平均值 (average) 或最大值 (maximum)？（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、給予一串資料：45, 30, 40, 65, 68, 60, 70, 50，請畫出將此串資料建成order 3 的 B-tree。接著請畫出從此 B-tree 刪除 (Delete) 資料50後 order 3 的B-tree。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、給予如下 C 語言的一個節點的宣告：
struct node {
int info;
struct node *next;
}
typedef struct node *NODEPTR;
請完成下列 C 程式，使它能在節點 p 後面加入一資料為 x 的節點 q。（20分）
void insafter(NODEPTR p, int x)
{
NODEPTR q;
}
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
五、資料倉儲 (DataWarehouse) 及 OLAP 是資料探勘 (Data Mining) 會用到的技術，請畫出一常用的三層資料倉儲架構 (Three-tier Data Warehousing Architecture)，並請說明每一層的工作。（20分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
|
代號：34280 頁次：2-1 |
108年特種考試地方政府公務人員考試試題 |
等 別：三等考試
類 科：資訊處理
科 目：資料結構
考試時間：2小時 座號：___________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
(三)本科目除專門名詞或數理公式外，應使用本國文字作答。
一、對下列三個程式片段，請使用 Big-O 符號，分別估計其最長執行時間 (worst time)。程式片段中，S 代表一段沒有與 n 相關的迴圈 (no n-dependent loops)。
(一) for(int i = 0; i*i < n; i++)（5分）
S
(二) for(int i = 0; Math.sqrt(i) < n; i++)（5分）
S
(三) int k = 1;（10分）
for(int i = 0; i < n; i++)
k *= 2;
for(int i = 0; i < k; i++)
S
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
二、有下列資料元素 (data elements)，其數值越小則優先權 (priority) 越高，請分別依序將各元素加入 (add) 優先佇列 (priority queue) 中，且分別以下列三種資料結構實作之。
90, 10, 80, 20, 70, 50, 40, 30
(一)用雙向鏈接串列 (doubly-linked list) 來實作此優先佇列，請畫出其資料結構圖。（6分）
(二)用紅黑樹 (red-black tree) 來實作此優先佇列，請畫出其資料結構圖。注意：紅節點請標示 R，例如 20R 表示其值為20的紅 (Red) 節點；黑節點則請標示 B，例如 50B 表示其值為50的黑 (Black) 節點。（7分）
(三)用最小堆積 (min heap) 來實作此優先佇列，請畫出其資料儲存的陣列(array) 圖。注意: 陣列索引 (array index) 由左向右遞增。（7分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
三、下圖為一棵2-3-4樹。
(一)請畫出對應的紅黑樹 (red-black tree)。請參閱上題紅黑樹節點的標示說明。（6分）
(二)首先，插入 (insert) 33；接著，刪去 (delete) 78。請分別畫出對應的2-3-4樹與紅黑樹。（14分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
四、下面的無向圖 (undirected graph) 表示四個人的關係，如張三與李四有關係， 這二人之間有邊 (edge) 相連，則可走訪。括弧內為人名縮寫，如張三 (Chang San) 的縮寫為 CS。若同時有兩個以上的人可處理，則先處理人名縮寫的字母順序較小者。
(一)由張三 (CS) 出發，用佇列 (queue) 做廣度優先搜尋 (breadth-first search) 走訪所有人，請寫出走訪順序的中文人名。（10分）
(二)由張三 (CS) 出發，用堆疊 (stack) 做深度優先搜尋 (depth-first search) 走訪所有人，請寫出走訪順序的中文人名。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
五、將下列六個鍵值：
33, 72, 71, 55, 112, 109
存入大小為19的雜湊表 (a hash table of size 19)
雜湊函數 h 為：h(key) = key mod 19
分別用下面兩種衝突處理方式 (collision handler)：
(一)間隔為1 (offset of 1)（12分）
(二)間隔為商 (quotient-offset)（8分）
請分別寫出兩個雜湊表；並在間隔為1的雜湊表上，標示出一次聚集 (primary clustering)。
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。
http://goods.ruten.com.tw/item/show?21512692236852
留言列表
國考資訊處理解答 (7)
