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

第一章 資料結構基礎

一、演算法

[演算法(algorithm)] 14 | 91,93,94(4),97,99(2),101,102,104,105

91關薦、93檢三、94交員晉高、94身三、94檢三(2)、97關三、99地三(2)、101地三、102地三、103高三、104地三、105地三

(一)演算法特性：輸入+輸出+明確+有限+有效

1.輸入(Input)：可以輸入或不輸入 (亂數產生)。

2.輸出(Output)：需有結果產生。

3.明確性(Definiteness)：

每一行指令都必須明確，不可模稜兩可。例如成績優秀的學生才能領獎學金就不具有明確性，因為每個人對成績優秀的定義可能不相同，如果改為成績90分以上的學生才能領獎學金，則具有明確性，因為90分是比較客觀的定義。

註：y = x/0違反明確性。

參考資料：李春雄-計算機概論第六章演算法.ppt

4.有限性(Finiteness)：

不能有無窮迴路，必須能終止執行，就是必須在有限步驟內完成。

註：迴圈違反有限性。

5.有效性(Effectiveness)或正確性(Correctness)：可以正確執行。

(二)演算法工具：步驟條列、流程圖、虛擬碼、程式。

(三)其他議題

1.演算法與程式最大的不同：演算法具有「有限性」，程式不一定具有「有限性」。

2.填魔術方陣的方法：

以奇數最為簡單，第一個數字放在第一行第一列的正中央，然後向右 (左) 上填，如果右 (左) 上已有數字，則向下填，如下圖所示：

99年地特三等資料結構

答：

(一)

1.棋盤：

int board[10][9]; // 10*9 二維陣列棋盤，二維陣列的索引記錄目前棋盤上棋子的所在座標位置，二維陣列的值記錄目前棋盤是那顆棋子及是否沒棋子。

2.棋子代碼：

例如 board[0][0] = 6 (車)，座標位置 (0, 0)；board[0][1] = 8 (馬)，座標位置 (0, 1)；board[2][1] = 4 (砲)，座標位置 (2, 1)。

(二)

1.田字形的對角移動：

2.演算法：

101年地方特考三等資料結構

答：

(二)

102年地方特考三等資料結構

答：

(一)g, j, q, r。

(二)g, j, q, r。

(三)

1.如果 p→a 的指標被消除，則 a, b, c, d, x 會變成圾垃節點，因為剩下2個全域變數指標 q→k 及 r→j 仍然可以拜訪其他節點。

2.尋找垃圾節點的演算法：

先將全部的節點都作記號;

For 每一個存在的節點 do 進行追蹤 // 從 q, r 二節點追蹤，p 無法追蹤

使用 DFS 或 BFS，將追蹤到的節點記號消除;

最後記號未消除的節點都是圾垃節點;

3.必須在每一個節點儲存布林值型態的旗標作記號，以便判斷是否為圾垃節點。

103年高考三級資料結構

答：

處理的資料為1到100之間的整數或小數。先判斷 K 位於那個範圍 (1≦K≦99)，然後建立99個首節點陣列存放 K 值，每個首節點陣列指向一個集合 Lx。此 Lx 為一棵 AVL-tree，存放帶有小數的正整數集合。

1.Insert(X)：

由首節點陣列找到 Lx 的 AVL-tree root，再將資料 X 插入樹中，時間複雜度為 O(log|Lx|)。

2.Detete(X)：

由首節點陣列找到 Lx 的 AVL-tree root，再將 X 由 AVL-tree 刪除，時間複雜度為 O(log|Lx|)。

3.List(X)：

由首節點陣列找到 Lx 的 AVL-tree root，再對 AVL-tree 進行中序走訪，時間複雜度為 O(|Lx|)。

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

答：

(一)

1.設計二個堆疊A、B 存放運算子。左括號存放到堆疊 A，右括號存放到堆疊 B。

2.由左至右掃瞄運算式，遇到左括號放入堆疊 A。

3.由右至左掃瞄運算式，遇到右括號放入堆疊 B。

4.從堆疊 A 取出左括號，再從堆疊 B 取出右括號，如果括號能正確配對，則正確，反之錯誤。逐一配對直到堆疊 A、B 為空。

(二)

1.{A*[B-(C+D)+8]-16}

把 {, [, ( 存放到堆疊 A。

把 }, ], ) 存放到堆疊 B。

 取出堆疊 A 的左括號 (，與堆疊 B 的右括號 )，配對成功。

 再取出堆疊 A 的左括號 [，與堆疊 B 的右括號 ]，配對成功。

 再取出堆疊 A 的左括號 {，與堆疊 B 的右括號 }，配對成功。

 堆疊 A、B 為空，配對成功。

2.{A+[B-(C+5])}

把 {, [, ( 存放到堆疊 A。

把 }, ), ] 存放到堆疊 B。

 取出堆疊 A 的左括號 (，與堆疊 B 的右括號 )，配對失敗。不用繼續比對。

二、演算法的分類

(一)貪婪法(Greedy Method)

[Greedy演算法] 1 | 102

102專三

1.定義：

設定一個特定的選擇程序，稱為貪婪準則，以便在每一個步驟中做出目前最有利的選擇，即局部最佳解。主要是採用按部就班地方式來產生最佳解。在每個階段都產生一個看似最佳的選擇 (使用貪婪準則得到局部最佳解)。一旦做出選擇，就不可再更改，並希望這樣的選擇可以得到全域的最佳解。在一般情況下，其結果大多是非常接近最佳解。

2.步驟：

從某一起點開始，不斷的改進該解答 (尋找周圍的更佳解，然後移到該更佳解上)，直到無法改進為止。

3.特性：

並不保證永遠可以得到最佳解，但是它仍是一個有效率的演算法，而且在很多時候也可以得到最佳解，或者得到跟最佳解相去不遠的解。

4.實例：

(1)霍夫曼演算法。

(2)找零錢：用數目最少的硬幣找錢

a.選擇程序(selection procedure)：

售貨員開始找尋收銀機中最大幣值的硬幣，且此時在他腦中用來選擇的準則是究竟哪一枚硬幣的幣值是目前最佳的選擇 (局部最佳解)。

b.可行性檢查(feasibility check)：

售貨員必須判斷他剛剛選擇出那一枚硬幣的幣值加上「目前顧客方已經收到的幣值總數」是否超過「應找給顧客的最後總數」。

c.解答檢查(solution check)：

售貨員必須檢查目前「已找給顧客方的零錢總數」是否等於「應找給顧客的最後總數」。如果兩者不相等，則售貨員必須繼續利用他的選擇硬幣機制拿出硬幣，並重複上述的過程直到「已找給顧客方的零錢總數」等於「應找給顧客的最後總數」或是收銀機裡的硬幣全部用盡為止。

5.適用時機：

若遇最佳化問題，先思考可否用 Greedy Approach 解，若不行再考慮用 Dynamic Programming。如果所要處理的最佳化問題無法找到一個選擇程序，則需要考慮所有的可能情況，就是屬於 Dynamic Programming。

※參考資料：

1.Sartaj Sahni-資料結構、演算法與應用使用C++ p.618~p.619

2.郭育倫-演算法導論-第12章貪婪演算法.ppt

3.(PTT)陳士杰-Course07_1 貪婪法則.ppt

4.http://ccckmit.wikidot.com/so:greedyalgorithm

(二)各個擊破法(Divide-and-Conquer)：切割征服

[切割征服(Divide and conquer)] 2 | 82,90

82地三、90地三

1.定義：

可將大問題切割成較小的問題 (切割)，使用相同的解決程序加以處理 (征服)。所有小問題的解可以成為大問題的最後解 (如階乘問題、費氏數)；若有必要，則再將每個小問題的處理結果加以合併，就可以得到最後的答案 (如合併排序)。由於使用相同的解決程序處理每個小問題，這一個程序就會被遞迴呼叫，因此一個遞迴演算法通常以一個副程式的型式出現，內部包含一個解決程序與遞迴呼叫。

2.演算法：

(1)把大問題切割成兩個或多個更小的問題。

(2)分別解決每個小問題。

(3)把各小問題的解答組合起來，即可得到原問題的解答。

小問題通常與原問題相似，可以遞迴地使用分而治之策略來解決。

3.特性：解決程序使用遞迴呼叫。

4.優點：簡潔易懂。

5.缺點：因為採用遞迴，效率較差。

6.適用時機：

(1)問題本身具有遞迴關係：

大問題可被切割成較小的相同問題。例如階乘、費氏數、河內塔等問題。

(2)資料結構屬於遞迴定義：

  資料結構切割後仍然具相同性質。例如二元樹、鏈結串列等。

※參考資料：

1.(PTT)陳士杰-演算法課程-Course05 切割與征服.ppt

2.Sartaj Sahni-資料結構、演算法與應用使用C++ p.662

(三)動態規劃(Dynamic Programming)

1.定義：

是一種表格式的演算法設計原則。若要解一個問題，需要解其子問題，再合併子問題的解以得出原問題的解。一旦某個給定子問題的解已經算出，則將其記憶儲存，以便下次需要同一個子問題解時直接查表。通常許多子問題非常相似，因此只需要解決每個子問題一次，從而減少計算量，

2.實例：

(1)斐波那契數列(Fibonacci polynomial)：費氏數(Fibonacci Number)

  F8 = F(7)+F(6) = 13+8 = 21，F(7) = F(6)+F(5) = 8+5 = 13，計算 F8 和 F7 時，F(6) 會被用到2次，使用表格記錄已算過的部份，減少計算量。

(2)最短路徑：

假設要尋找一條從來源節點 s 到目的節點 d 的最短路徑，如果在第一次決策時到達了某個節點 v，那麼不管 v 是如何決定的，之後選擇從 v 到 d 的最短路徑時，都必須採用最佳策略。

※參考資料：

1.http://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92

2.(PTT)陳士杰-演算法課程-Course06 動態規劃.ppt

3.Sartaj Sahni-資料結構、演算法與應用使用C++ p.712

※Dynamic Programming與Greedy Approach的比較：

1.相同處：

對於具有限制的最佳化問題，可以採用貪婪法則或動態規劃來設計演算法則。

2.相異處：

※參考資料：

1.(PTT)陳士杰-演算法課程Course06 動態規劃.ppt

2.Sartaj Sahni-資料結構、演算法與應用使用C++ p.712

※子問題重覆(Overlapping Subproblem)：

可能會對相同子問題進行重覆計算，是 Divided-and-Conquer 主要的問題所在。

※參考資料：

(PTT)陳士杰-演算法課程-Course06 動態規劃.ppt

※各個擊破法與動態規劃的比較：

1.相同處：都是將問題切割再採用遞迴方式處理子問題。

2.不同處：

※參考資料：(PTT)陳士杰-演算法課程Course06 動態規劃.ppt

(四)回溯法(Backtracking)

1.定義：

是暴力搜尋法中的一種。採用嘗試錯誤的方式，嘗試逐步的去解決一個問題。在逐步解決問題的過程中，通過嘗試發現現有的逐步答案不能得到有效的正確解答時，將取消上一步甚至是上幾步的計算，再通過其它的可能的逐步解答再次嘗試尋找問題的答案。通常用最簡單的遞迴方法來實現，在反覆重複上述的步驟後可能出現兩種情況：

(1)找到一個可能存在的正確的答案。

(2)在嘗試了所有可能的分步方法後宣告該問題沒有答案。

在最壞的情況下，會導致複雜度為指數時間。

2.實例：八皇后問題、迷宮。

※參考資料：

http://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95

(五)分支設限(Branch and Bound)

1.定義：把問題的可行解展開如樹的分枝，再經由各個分枝中尋找最佳解。

2.實例：修剪過的狀態空間樹 (Pruned State Space Tree)。

※參考資料：

1.http://wiki.mbalib.com/zh-tw/%E5%88%86%E6%9E%9D%E7%95%8C%E9%99%90%E6%B3%95

2.http://episte.math.ntu.edu.tw/articles/mm/mm_11_3_02/page2.html

3.(PTT)陳士杰-演算法課程Course08 回溯、分枝與限制.ppt

※矩陣相乘：

1.定義：

只有第一個矩陣的列數 (column) 和第二個矩陣的行數 (row) 相同才可以相乘。例如矩陣 A 的列數為 n，矩陣 B 的行數為 n，都相同才可以相乘。

※參考資料：

https://zh.wikipedia.org/wiki/%E7%9F%A9%E9%99%A3%E4%B9%98%E6%B3%95

2.A_m×n×B_n×p = C_m×p

3.

4.演算法：

※參考資料：http://programming.im.ncnu.edu.tw/expamle_for_c/19.htm

5.矩陣相乘範例：i = m = 3, j = p = 4, k = n = 2

(a₁₁×b₁₁+a₁₂×b₂₁)，(a₁₁×b₁₂+a₁₂×b₂₂)，(a₁₁×b₁₃+a₁₂×b₂₃)，(a₁₁×b₁₄+a₁₂×b₂₄)

1×0+2×4 = 8，1×1+2×0 = 1，1×1+2×-1 = -1，1×2+2×3 = 8

3×0+4×4 = 16，3×1+4×0 = 3，3×1+4×-1 = -1，3×2+4×3 = 18

5×0+6×4 = 24，5×1+6×0 =5，5×1+6×-1 = -1，5×2+6×3 = 28

※範例1：

答：

[方法一]

[方法二]

1.每兩項資料為一組，比較其最大與最小值，然後小的分一組，大的分一組。

2.從較大的那一組資料找最大值；從較小的那一組資料找最小值。

3.比較次數：。

※範例：

103關三

答：

※範例2：

答：

※範例3：

答：

1.質數是一個數字，除了１和自己之外，沒有其他正因數。例如 2 (=1×2)、3、5、7、11 ...均為質數，而4、6、8不為質數 (因為有因數2)。

2.假設 i = 2~1000，a[i] = 1可能為質數；a[i] = 0為非質數。陣列初值設定 a[i] = 1。標示 2~i 的倍數 a[i] = 0。時間複雜度為 O(nlogn)。

※範例4：

答：

[方法一]

[方法二]

p←1;

while y > 0 do begin

if y is odd then p = p*x; // y 是奇數 (odd)

x←x*x;

y←[y/2];

end;

103年關務三等資料結構

答：

略

103年關務三等資料結構

答：

略

105年地方特考三等資料結構

答：

(一)共有幾種加括號的方法？

共有 (((AB)C)D)、((AB)(CD))、((A(BC))D)、(A((BC)D))、(A(B(CD))) 5種加括號的方法。

(二)例如 (AB)(CD)，共需多少次乘法？

A_2×4×B_4×3×C_3×5×D_5×1

(AB)_2×3：2×4×3 = 24。

(CD)_3×1：3×5×1 = 15。

(AB)_2×3(CD)_3×1：2×3×1 = 6。

總共24+15+6 = 45次。

(三)求出三者乘積之最有效的方式為何？

(A×(B×(C×D)))_2×1

(CD)_3×1：3×5×1 = 15。

(B×(C×D))_4×1：4×3×1= 12。

A_2×4×(B×(C×D))_4×1：2×4×1= 8。

總共15+12+8 = 35次。綜合上圖的計算，可知 (A(B(CD))) 是5種加括號的方法之中，其乘積次數為最少。

三、資料結構

82,90,91,92(5),93(2),94,95(2),97(3),99(9),100(2),101(7),103(2),104,105

82地三、90地三、91技高、92身三、92公薦、92省八(2)、92檢三、93檢三、93技高、94身三、95關三、95技高、97關三、97身三、97地三、99鐵高(4)、99檢三(3)、99地三(2)、100檢三、100技高、101關三(3)、101檢三(2)、101技高、101地三、102關薦、103關三、103高三、103技高、104關三、105關三

(一)定義

探討如何將資料更有組織地存放到電腦記憶體中，對於節省儲存空間、增加資料的安全性與處理速度將有很大幫助。

(二)常用結構

※各種資料結構關係：

※線性結構(linear structure)：

1.定義：

是一個有序資料元素的集合，資料元素之間在邏輯上有先後關係，例如陣列 (array)、串列 (list)、堆疊 (stack)、佇列 (queue) 等。資料元素之間存在「一對一」的關係 (如 a[1] = x, a[2] = y, a[3] = z, ...)，例如 (a₁, a₂, a₃,.....,a_n)，a₁ 為第一個資料元素，a_n 為最後一個資料元素。

2.特性：

(1)集合中必存在「第一個資料元素」，而且是唯一的。

(2)集合中必存在「最後一個資料元素」，而且是唯一的。

(3)除了「第一個資料元素」之外，其它資料元素均有唯一的前行者。

(4)除了「最後一個資料元素」之外，其它資料元素均有唯一的後繼者。

※參考資料：

http://translate.googleusercontent.com/translate_c?depth=1&hl=zh-TW&prev=search&rurl=translate.google.com.tw&sl=zh-CN&u=http://baike.baidu.com/view/390966.htm&usg=ALkJrhj4kQqSyB4R_Y_vBx3-TG1NFJFnig

※非線性結構(nonlinear structure)：

(一)定義

一個節點可能有多個直接前行者 (predecessor) 或多個直接後繼者 (successor)。

(二)兩種非線性的資料結構

1.圖(graph)：

包含頂點 (vertices) 及連結這些頂點的邊 (edges) 所形成結構。以 G = (V, E) 表示，其中 V 表示 G 中所有頂點的集合，而 E 是在 G 中所有邊的集合。

2.樹(tree)：

資料與資料之間藉由分支 (Branch) 組成階層式 (Hierarchical) 的關係。

(1)含有一個特別的節點，稱為樹根。

(2)是一個或多個以上的節點所形成的有限集合。

(3)其餘節點又分成 n 個互斥集合 (n≥0)，其中每個集合也都是一棵樹。

※參考資料：http://baike.baidu.com/view/597537.htm

※資料(Data)：

1.結構化資料(structured data)：

每筆資料都有固定的欄位、固定的格式、固定的順序甚至是固定的佔用大小。是很有條理的資料類型。違反規則的資料進不了這類資料庫裡面。譬如資料結構一開始就定義清楚，假設資料有三個欄位，第一個欄位是產品編號、第二個欄位是產品名稱，第三個欄位是型號，例如關聯式資料庫的表格。

2.非結構化資料(unstructured data)：

資料結構並非一開始就確定欄位格式及大小，必須另外再整理過。例如數位影像、多媒體影音、日誌檔、網頁及一般的共享檔案等。

3.半結構化的資料(Semi-structured data)：

介於結構化資料和非結構化資料之間，資料格式以文字為主，但每個欄位填入資料的內容和長度則不固定。例如電子郵件、網路社群討論文章、XML。以XML 為例，說明如下：

如果以上方的 XML 存放資料，確實可以準確地提取出 name 的值，但是可以隨時追加任何其他新的欄位，不受到任何限制。

※參考資料：

1.http://tomatokafka.pixnet.net/blog/post/108445171-%E6%B7%BA%E8%AB%87%E5%A4%A7%E6%95%B8%E6%93%9A%E6%88%96%E6%B5%B7%E9%87%8F%E8%B3%87%E6%96%99%28an-introduction-to-big-data%29-

2.http://www.sysage.com.tw/Guest/GoGoBuy/GoGoBuyOne.aspx?id=13

3.https://kevinwang.gitbooks.io/bigdata/content/general/structured-data.html

4.http://fredbigdata.blogspot.tw/2012/08/blog-post.html

99年檢察事務官三等資料結構

答：

(一)圖形

記錄已落子的棋子位置，通常用鄰接矩陣 (2-D 陣列) 記錄棋子位置即可，此一陣列用記錄盤面狀況，來檢查死活，計算佔領區域的大小，以判斷勝負。

(二)遊戲樹

在人工智慧部份用來找尋電腦的最佳落子位置，通常使用mini-max 演算法或Alpha-beta pruning 演算法，來找尋最佳落子位置。

(三)堆疊或佇列

使用回溯法 (backtracking) 搜尋遊戲樹時，需要用到堆疊；若使用廣度搜尋法時，需要用到佇列；若使用最佳優先搜尋法 (best-first search) 時，使用優先權佇列 (priority queue)。

100年資訊技師高等資料結構

答：

(一)

使用 disjoint set 表示。一群集合的交集為空集合。互斥集合可以用一般樹來表示，每一個互斥集合用一棵樹來代表。

(二)找出集合的元素個數最小的。

101年檢察事務官三等資料結構

答：

1.大富翁地圖使用環狀鏈結串列，玩家的棋子沿著鏈結串列循環前進。

2.機會與命運兩疊卡片可以用堆疊結構。每次翻卡片就由堆疊開頭位置取卡片。

3.骰子以亂數函數實作。

4.路名、玩家名稱、房屋資訊等，記錄在環狀鏈結串列的節點，每個串列節點有資料欄位記錄這些資料。

101年檢察事務官三等資料結構

答：

暫略

103年關務三等資料結構

答：