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

關務三等資料結構：104

身心障礙人員三等資料結構：104

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

高考三級資料結構：104

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

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

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

資訊技師高等資料結構與資料庫及資料探勘：104

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

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

104年公務人員特種考試關務人員考試、

104年公務人員特種考試身心障礙人員考試及            代號：10460 全一張

104年國軍上校以上軍官轉任公務人員考試試題

考 試 別：關務人員考試

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

一、，兩項式係數的組合遞迴演算法公式如左。

(一)請用你熟悉的程式語言，撰寫此遞迴函式。（5分）

(二)若 n = 5, r = 3，請用二元樹畫出其遞迴呼叫的情形。（5分）

(三)最後的傳回值是多少？（5分）

(四)共遞迴呼叫幾次？（5分）

答：

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

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

二、在計算學生成績的程式中，按成績的高低分為五級，且用 IF 指令，其程式如下：

if S<60

then G = ‘F’

else if S<70

then G = ‘D’

else if S<80

then G = ‘C’

else if S<90

then G = ‘B’

Else G = ‘A’

若學生在五個等級中的分布是不平均的，分布機率如下表：

假設學生人數為5000人，請回答下列問題：

(一)請畫出 IF 指令的二元樹分析圖並分析此 IF 指令可能的比較次數。（10 分）

(二)若用最佳化二元樹修正IF 指令，請畫出該二元樹，並分析 IF 指令可能的比較次數。（10分）

(三)可使用什麼資料結構，使程式指令更為精簡，並請說明。（5分）

答：

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

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

三、佇列 (Queue) 結構的插入 (Insert) 和刪除 (Delete) 演算法如下：

(一)請問上述演算法的佇列結構，會有什麼問題存在？（5分）

(二)可用什麼資料結構解決？（5分）

(三)承上之資料結構，請寫出插入 (Insert) 和刪除 (Delete) 演算法。（10分）

答：

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

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

四、圖形的理論是起源於西元十八世紀，有一位數學家尤拉 (Eular) 為了解決「肯尼茲堡橋樑」問題，而想出的一種圖形結構理論。所謂的「肯尼茲堡橋樑」問題是：某一個人由某地點出發，最後再回到原點，必須要經過每一座橋，並且只能經過一次。如下圖所示：

(一)請問肯尼茲堡的人有無可能走過所有的橋樑1次，到過每個地方，而後又回到肯尼茲堡？（5分）

(二)土地代表頂點 A, B, C, D，橋樑代表邊1~7，請畫出此圖形結構。（5分）

(三)數學家尤拉 (Eular) 對「肯尼茲堡橋樑」問題所找出的規則是什麼？（5分）

(四)請舉一個具有尤拉循環 (Eulerian Cycle) 的例子，並寫出其路徑。（5分）

答：

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

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

五、學生的學號格式是 (N₁N₂N₃N₄N₅N₆N₇)，假設儲存空間為99，請用數字分析法 (Digital Analysis)，分別以學號為鍵值 (Key) 雜湊 (Hashing) 出其資料儲存的位址。數字的分布曲度 (Skewness) 設為 sk，則，其 a_ij 表示 N_i 出現的個數。

(一)請依下列五位學生的學號算出其 sk_i 值。（10分）

Student 1 ID: 0392018

Student 2 ID: 0392124

Student 3 ID: 0392238

Student 4 ID: 0252714

Student 5 ID: 0392468

(二)請寫出此五位學生儲存的位址。（5分）

答：

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

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

[一○四年身心障礙人員三等資料結構]

104年公務人員特種考試關務人員考試、

104年公務人員特種考試身心障礙人員考試及            代號：30860 全一張

104年國軍上校以上軍官轉任公務人員考試試題

考 試 別：身心障礙人員考試

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

一、請計算且說明下列片斷程式中 x = x+1 的執行次數。（每小題5分，共10分）

(一) k = 100000;

while (k != 10){

k /= 10;

x = x+1;

}

(二) for (i = 1; i <= n; i++) {

k = i+1;

do {

x = x+1;

} while (k++ <= n);

}

答：

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

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

二、二維陣列 A(0:m-1, 0:n-1)，假設 A(3, 2) 在1110，而 A(2, 3) 在1115，若每個元素占一個空間，請推導 A(1, 4) 所在的位址。（10分）

答：

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

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

三、若堆疊以陣列 st 儲存，請完成堆疊的插入演算法。（10分）

其中相關宣告為

int st[0:MAX-1];

int top = -1;

答：

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

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

四、有一個 n*n 的矩陣 A 如圖(1)所示。其中在 i<j 時存有不同的資料，但 i≧j 時 a_ij = 0，試問：(一)以最小化儲存空間為目標，宜採用何種方式儲存？（5分）(二)承上，需要多少空間？（5分）(三)承上，若以行為主儲存，則在 i<j 時，請推導 a_ij 儲存的位置。（5分）

A= 圖(1)

答：

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

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

五、在一單向鏈結串列中，若節點的定義為：

class Node{

public int data;

public Node next;

}

請寫出刪除指定節點 p 的演算法。（10分）

註：假設第一個節點為開頭節點 (head)，不存放任何資料。

答：

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

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

六、請寫出圖(2)所示二元樹的前序、中序和後序走訪。（6分）

答：

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

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

七、資料 20、30、10、50、60、40、45、5 (一)請建立成一棵 AVL 樹，（6分）(二)請依序刪除60及30，在推導過程需註明旋轉的類別。（6分）

答：

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

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

八、若採雜湊搜尋法中的移位折疊相加法，且 m = 1000，請推導鍵值 x = 123456789 的儲存位址在那裡？（5分）

答：

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

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

九、請推導圖(3)之拓撲排序。（10分）

答：

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

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

十、有一二維陣列 A(-1:5, -4:2) 之啟始位址 A(-3, -4) = 100，以列為主排列，請問 A(1, 1) 所在位址？（6分）若以行為主排列，請問 A(1, 1) 所在位址又如何？（6分）（假設陣列內元素長度都為1）

答：

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

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

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

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

類 科 別：資訊處理

科    目：資料結構

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

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

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

一、對於很多項係數為0的多項式加法，譬如 A(x) = 12x¹⁰⁰⁰+6x¹⁵+5 與 B(x) = 8x⁵⁰⁰-56x¹²⁵+10x¹⁵+1 相加。

(一)請問你會使用陣列 (array) 或鏈結串列 (linked list) 來表示此種多項式？為什麼？該資料結構會包含那幾部分？（10分）

(二)以 A(x) 與 B(x) 為例，畫出 AB 兩多項式的資料結構、說明加法演算法運作的過程、與最終的資料結構結果。（15分）

答：

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

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

二、(一)有一陣列 A = (179, 208, 306, 93, 859, 984, 55, 9, 271, 33) 要由小排到大。使用堆積排序法 (heap sort) 需要先將 A  陣列整理成 max heap，然後再經過9個回合 (pass) 的 reheap 才能將資料由小排到大，請寫出整理成 max heap 後與第一個回合 reheap 結束時 A 陣列的內容。（10分）

(二)有6個已排序過的檔案，長度分別為7，9，2，3，6，13。這6個檔案經過5次的兩兩合併，成為一個完整排序過的檔案。已知合併時間複雜度與兩個合併檔案的長度和成正比，請用 merge tree 寫出他們的合併順序與結果，且 merge tree 的 left subtree 長度小於 right subtree。（10分）

(三)有 n 筆資料，請說明如果任意選最左邊的資料當成比較基準資料(pivot)，則快速排序法 (quick sort) 在最糟的情況下時間複雜度為多少？（5分）

答：

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

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

三、(一)令 “i” 代表插入 (insert) 一筆資料，“d” 代表刪除 (delete) 一筆資料。畫出在空的 binary search tree 做 i4, i2, i6, i5, i1, i9, d4, i3, i8, d6, i10, i7, d5 動作之後最終的 binary search tree，而刪除資料時用比刪除資料大的資料取代它並調整成 binary search tree。（10分）

(二)請填入下列 C 程式中三個空格以完成 ptr 指向樹根的 binary search tree 上搜尋 key 的程式。（15分）

typedef struct node {

struct node *left;

int data;

struct node *right;} NODE;

NODE *search(NODE *ptr, int key)

{   while(ptr != NULL ) {

If (key == ptr->data) return       (1)      ;

If (key < ptr->data)       (2)      ;

else       (3)      ;

}

return NULL

}

答：

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

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

四、(一)分別說明在什麼情況下會用鄰接矩陣 (adjacency matrix) 或鄰接串列(adjacency list) 表示一個圖形 (graph)？為什麼？（10分）

(二)分別說明在圖形的廣度優先搜尋 (breadth first search) 與深度優先搜尋(depth first search) 時會使用何種資料結構？為什麼？（10分）

(三)一個無向圖 (undirected graph) 所有點 (vertex) 的分支度 (degree) 總和與邊 (edge) 的個數有何關係？為什麼？（5分）

答：

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

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

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

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

類    科：資訊處理

科    目：資料結構

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

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

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

一、有位程式設計師在撰寫程式時遇到了一個難解的問題，後來發現有兩個演算法可以解這個難題：演算法 A 的時間複雜度為 O(n²log(n!))，演算法 B 的時間複雜度為 O(n²((log n)!))。假設輸入資料的個數 n 通常都很大，他應該選擇那個演算法比較好，原因何在？（20分）

答：

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

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

二、樹 (tree) 是一個很常用的資料結構。一個樹是指一個沒有迴圈 (cycle) 的聯通圖 (connected graph)。（每小題10分，共20分）

(一)證明：每個具有 n 個節點 (node) 的樹，n > 1，至少有2個分支度 (degree)為1的節點。（分支度就是指有多少邊以此節點為端點。）

(二)用前項結果證明：每個具有 n 個節點的樹，n > 1，恰好有 n-1個邊 (edge)。

答：

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

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

三、給定一個權重圖 (weighted graph)，G = (V, E, w)，其中每個邊 (edge) e 的權重 w(e) 都是正整數，為了簡單，假設 V = {1, 2, ..., n}。任意點 v 與起始點 s 的距離可以用一個矩陣 d[1..n] 來表示。（每小題10分，共20分）

(一)設計一個只需 O(n) 空間的方法來記錄從 s 出發，到達每個點的最短路徑。

(二)說明計算與印出從起始點 s 到任意點 tV 的最短路徑的演算法。（解此小題時可參考 Dijkstra 或其他演算法來設計，且不須將 Dijkstra 或別的演算法做詳細的描述。）

答：

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

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

四、有個矩陣 A[1..n]，n 的值很大。在矩陣A中存有 n 個正整數，且從小到大排列。給定某個整數 x，二分搜尋法 (binary search) 可以在 O(log n) 的時間內找出 x 在矩陣 A[1..n] 的位置，或宣告在 A[1..n] 中沒有 x。在某個應用中，已知絕大部分的 x 都會出現在矩陣 a[1..n] 的前面 m 個元素，且 m 的值遠小於 n，但是無法預知 m 的範圍。設計一個演算法，可以在O(log m) 的時間內完成搜尋。（20分）

答：

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

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

五、假設有個矩陣 A[1..n] 儲存 n 個整數。Quick sort 是一個排序演算法。假設有個副程式 partition(A, l, r) 其輸入參數 A 是一個矩陣，l, r, l < r < n，是兩個指標。其回傳的值 m 也是一個指標。這個副程式可將矩陣中從 l 到 r 的這一段資料 A[l..r] 區分成兩段：

A[l..m] 和 A[m+1..r]，使得在 A[l..m] 中的元素都小於或等於 x，而在 A[m +1..r] 中的元素都大於或等於 x，其中 x 是從 A[l..r] 中隨機選擇的一個整數。接下來要在此兩段資料遞迴執行 partition。避免這些遞迴計算可以用一個堆疊 (stack) 來處理。假設

partition(A, l, r) 回傳 m，則執行：

if (l<m) push (l, m) into stack

if (m+1<r) push (m+1, r) into stack

一開始，堆疊中只有一組資料，(1, n) 表示 A[1..n] 需要排序。如此反覆將堆疊最上面的資料 (l, r) 移出，執行 partition(A, l, r)，直到堆疊沒有資料為止。

（每小題10分，共20分）

(一)證明在最糟情況下，堆疊的高度可以達到 n/2。

(二)設計一個好的演算法以降低 stack 的高度，並證明堆疊的高度最多只需要 log n+1。

答：

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

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

[一○四年關務人員升官等薦任資料結構]

104年公務人員升官等考試、104年關務人員升官等考試

104年交通事業公路、港務人員升資考試試題           代號：26260  全一張

等    級：薦任

類科 (別)：資訊處理

科    目：資料結構

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

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

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

一、給定如下圖所示之環狀雙向鏈結串列 (circular doubly linked list)，並以 A  指向其中一個節點。請用類 C 之虛擬語言 (C-like pseudo code) 完成下列動作。

(一)在 A 所指向節點之右鏈結 (rlink) 插入由 B 所指向的一個新節點。（6分）

(二)刪除 A 所指向的節點，並將A 指向其原節點之右鏈結 (rlink) 節點。只能使用 A 指標。（6分）

(三)刪除整個串列，完成後 A 應指向 NULL。只能使用 A 指標。（13分）

答：

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

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

二、假設有1000筆資料將以雜湊法 (hashing) 放入雜湊表 (hash table)。

(一)若該雜湊表有750桶 (buckets) × 4 槽 (slots)，不管採用何種雜湊函數，1000筆資料都放入雜湊表後，該表之載入密度 (load factor) 為何？（7分）

(二)若要做到完整雜湊 (perfect hashing)，雜湊函數應該要有何特性？（8分）

(三)假設建立雜湊表時若發生碰撞就採取線性探測法 (linear probing) 來放入資料，且在1000筆資料都放入該雜湊表後，搜尋每筆資料的平均所需查看 (access) 次數希望約為2，在盡量不浪費空間的前提下，該雜湊表應該如何設計？請以「桶」(buckets)、「槽」(slots)、「載入密度」(load factor) 等之數量加以敘述，並說明為何該設計符合平均查看次數之限制。（10分）

答：

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

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

三、給定下列以陣列所表示之16筆有序數列。

(一)請畫出該陣列以二元搜尋法搜尋資料之二元搜尋樹 (binary search tree)。（5分）

(二)假設陣列內的資料量共有1024筆資料，則二元搜尋樹共會有幾層 (最上層為第1層)？請說明。（5分）

(三)若是陣列中有兩個相鄰的數字對調位置 (也就是只有此兩個數字順序錯誤)，最多可能會有多少數字將無法以二元搜尋法成功找到？請說明。（15分）

答：

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

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

四、給定 m 個印表機共用一個印表佇列 (printer queue)。印表機 A₁, …, A_k 每次都從印表佇列選取優先權最高 (優先權數字最大) 的列印工作進行列印，印表機 A_k+1, …, A_m 每次都選取優先權最低 (優先權數字最小) 的列印工作進行列印。每天需要列印工作繁多，因此該印表佇列在選取優先權最高、最低及排入新印表需求的效率非常重要。假設該印表佇列以對稱最小最大堆積 (Symmetric min-max heap, SMMH) 加以實作。

(一)找到並移除最高優先權印表工作的時間複雜度為何？排入新印表需求的時間複雜度為何？請以 Big-O 方式敘述。（5分）

(二)若所有印表機都尚未開機，而送進印表佇列的順序如後 (數字代表該印表優先權)：

8, 18, 28, 38, 35, 25, 15, 5, 40, 1。請將該印表佇列以 SMMH 樹狀結構圖表示之。（15分）

(三)承上題(二)，若 A₁ 開機，並處理了優先權最高的印表工作。請將印表佇列變化結果以 SMMH 樹狀結構圖表示之。（5分）

答：

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

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

[一○四年資訊技師高等資料結構與資料庫及資料探勘]

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

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

等    別：高等考試

類    科：資訊技師

科    目：資料結構與資料庫及資料探勘

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

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

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

一、(一)下列圖形是一棵 B-tree of order 3，若陸續加入資料：99、20，會成為怎樣的 B-tree，請畫出最後的 B-tree。（5分）

(二)請問 B-tree of order 3 又稱為什麼樹？（5分）

答：

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

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

二、堆疊 (stack) 可應用於後序表示式 (postfix expression) 的運算處理，請利用下列的表示式，繪出堆疊內的變化來說明如何利用堆疊計算其結果，並請寫出演算法。後序表示式：4 8 -9 3 / * (該表示式中的數值均為個位數)。（10分）

答：

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

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

三、請將 18、25、6、33、9、12、55、14 依快速排序 (Quick sort) 由小排到大，若是以最左的資料18為支柱點 (pivot)，請繪出 first pass (即是指將資料18 放在正確的位置) 之排序過程。（5分）

答：

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

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

四、(一)請問什麼是最小成本擴展樹 (minimum cost spanning tree)？（5分）(二)依據下列的圖形，利用 Prim’s algorithm 求出最小成本擴展樹 T，假設 TV 為 T 的頂點集合，設定 TV 的初始值為 A，即 TV = {A}。請繪出最小成本擴展樹的形成過程。（10分）

答：

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

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

五、資料庫管理系統一個重要的工作即是進行交易 (transaction) 管理，在同作控制 (concurrency control) 處理中要確保交易的四項特性，簡稱為 ACID，請逐一說明這四項性質。（15分）

答：

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

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

六、有一資料表 PRODUCT 之關聯綱要 (relation schema) 如下，其中產品代碼為主鍵 (primary key)， 除了主鍵之相依性外，若以→表示相依性 (functional dependency)，該表還存在著右列的相依性，供應商代碼→供應商名稱

請問該資料表符合第三正規化的格式 (third normal form) 嗎？若不符合，請問該如何修改使之符合第三正規化之格式。（10分）

答：

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

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

七、某大學進行全校的體能競賽，下列資料表 GAMERECORD 為參賽選手的分數紀錄範例，該表為關聯資料庫 (relational database) 的資料表 (relation)，一位學生只有一個分數，同一個科系會有多位學生參加，每個學生的學號均不同。請根據該資料表，回答下列第(一)到第(三)題：

(一)請問該資料表的主鍵 (primary key) 應設為該資料表的那些屬性(attribute)？請說明你的答案。（5分）

(二)寫出 “列出平均體能分數大於80 的科系代碼與該科系的平均體能分數” 的 SQL 指令。（5分）

(三)寫出 “列出每科系的最高體能分數與科系代碼” 的 SQL 指令。（5分）

答：

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

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

八、在資料探勘的分類方法 (cluster analysis) 中有一方法稱為 nearest-neighbor clustering algorithm，請說明該方法的運作原理？（10分）

答：

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

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

九、資料探勘中的關聯法則 (Association rule) 可用來尋找顧客購買產品的關聯規則，{麵包}→{牛奶} 表示購買麵包的顧客也會購買牛奶。有一交易紀錄如下表，請寫出關聯規則 {b, c}→{d} 的支持度 (support) 和信心度(confidence)，及其計算過程（5分），並說明這兩者是指什麼？（5分）

答：

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

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

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

104年特種考試地方政府公務人員考試試題              代號：34380 全一頁

等    別：三等考試

類    科：資訊處理

科    目：資料結構

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

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

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

一、二元搜尋法 (binary search) 使用 divide-and-conquer (分而治之) 演算法技巧，對一個已排序 (sorted) 且長度為 n 的陣列 A[0:n-1]，進行資料搜尋，其最差時間複雜度 (worst case time complexity) 可降到 θ(log n)。

(一)請使用 C 或 Java 語言，修改此二元搜尋法，使其能對未排序 (unsorted)且長度為 n 的陣列 A[0:n-1]，以 divide-and-conquer 技巧，進行二元化搜尋。（15分）

(二)請分析修改後的二元搜尋法其最差時間複雜度 (worst case time complexity) 以 order θ的方式表示。（5分）

（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法）

答：

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

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

二、請使用 C 或 Java 語言寫一副程式 void merge(int [ ] A, int [ ] B, int [ ] C, int n)，此副程式將對兩個長度為 n 且已依小到大排序的整數陣列 A 與 B，合併至長度為 2n 且依小到大排序的整數陣列 C，此副程式的時間複雜度需為 θ(n)。（20分）

（注意：請加註解說明程式碼作法）

答：

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

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

三、(一)請說明使用何種資料結構及其演算法，可有效判斷一運算式 (expression)中的巢狀 (nested) 括號是否正確配對 (matched)。（10分）

(二)請以兩個運算式實例 {A*[B-(C+D)+8]-16} 及 {A+[B-(C+5])}，分別說明此演算法判斷的過程及結果。（10分）

（注意：未說明判斷的過程，不予計分）

答：

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

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

四、(一)一運算式 (expression) 為：-a+(z+f)/y-b*a/c+d，請依運算元優先順序，繪出其二元樹 (binary tree)。（10分）

(二)請列出此二元樹的前序走訪 (preorder traversal)。（5分）

(三)請列出此二元樹的廣度優先走訪 (breadth-first search traversal)。（5分）

答：

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

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

五、一個圖形 (Graph) 包含五個頂點 (vertex)，V₁, V₂, ..., V₅，其相鄰矩陣(adjacency matrix) A =

(一)請使用 Floyd 的方法，計算此圖形的最短路徑長度矩陣 (shortest path length matrix)，表示任兩頂點間最短路徑長度。請依序列出最短路徑長度矩陣變化過程。（15分）

(二)請使用 Kruskal 的方法，依序繪出加入此圖形的最小成本擴張樹(minimum cost spanning tree) 每一邊的過程。（5分）

答：

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

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