第一章 資料結構基礎

一、演算法

[演算法(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.填魔術方陣的方法：

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

undefined

 

99年地特三等資料結構

五、考慮設計中式象棋 (如圖) 電腦程式系統：（每小題5分，共10分）

(一)請設計一資料結構使能隨時表示出棋盤現狀 (current state)，包含所有棋子的位置、有那些棋子在棋盤上。

(二)寫出一演算法能產生「象」或「相」在任意位置之下一步可前往且合規則的所有位置 (next feasible positions)，注意，務必考慮其他棋子阻礙的因素。「象」或「相」的移動規則：(1)田字形的對角移動；(2)田字正中央有棋子時，不能移動前往。

undefined

答：

(一)

1.棋盤：

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

2.棋子代碼：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

將

士

士

象

象

車

車

馬

馬

包

包

卒

卒

卒

卒

卒

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

帥

仕

仕

相

相

俥

俥

傌

傌

炮

炮

兵

兵

兵

兵

兵

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

空

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

(二)

1.田字形的對角移動：

undefined

2.演算法：

void move(int i, int j, int direction) { // i, j 棋子座標，direction 移動方向

int temp = board[i][j]; // 舊棋子位置

if(board[i][j]==4 || board[i][j]==5 || board[i][j]==20 || board[i][j]==21) { // 如果是象或相

if(board[i-2][j-1] != NULL && direction = 0) { // 不是邊界，並且往左上角移動

board[ i-2][j-1] = temp; // 新棋子位置

board[i][j] = 0; // 舊棋子位置清空

}

else if (board[i-2][j+1] != NULL && direction = 1) { // 不是邊界，並且往右上角移動

board[ i-2][j-1] = temp;

board[i][j] = 0;

}

else if (board[i+2][j+1] != NULL && direction = 2) { // 不是邊界，並且往右下角移動

board[i+2][j+1] = temp;

board[i][j] = 0;

}

else if (board[i+2][j-1] != NULL && direction = 3) { // 不是邊界，並且往左下角移動

board[ i+2][j-1] = temp;

board[i][j] = 0;

}

}

}

 

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

四、迴文 (palindrome) 乃是一個字串不論從左到右或從右到左看結果一模一樣，例如 “油麻地遍地麻油”、“人人為我、我為人人”、“Fall leaves as soon as leaves fall” 等。

(二)請寫出演算法以測試輸入的字串 (字串的長度不超過100個字) 是否為迴文。（10分）

答：

(二)

CreateStack( );

while(input not end) {

x←read next character; // 從左自右逐一讀取字元

push(x);

}

scan string again;

while(input not end) {

x←read next character; // 從左自右逐一讀取字元

y = pop( ); // 取出堆疊的字元

if(x≠y) {

print “not palindrome”;

exit;

}

}

print “is palindrome”;

 

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

一、請參考圖1：

(一)由 a 點出發，做 depth-first traversal (深度優先拜訪)，請問那些節點(node) 不會被訪問到？（3分）

(二)由a 點出發，做 breadth-first traversal (寬度優先拜訪)，請問那些節點(node) 不會被訪問到？（2分）

(三)假設圖1代表 heap 上各個節點 (node) 及其相互指向的關係。p、q、r 三節點代表全域變數 (global variables)，其他的節點代表 heap 上的記憶體區塊。如果 p→a 的指標被消除，那些節點會變成無用的垃圾節點？你必須詳細描述尋找垃圾節點的方法及所需之資料結構。你的演算法只能從 a 節點出發，它必須指出所有的垃圾節點，並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演算法必須在每一個節點儲存那些資料？（15分）

undefined

答：

(一)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≦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分）

答：

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

undefined

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年地方特考三等資料結構

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

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

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

答：

(一)

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

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

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

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

init.

StackA, StackB is empty;

while(scan expression left to right And not EOF) {

x←read( );

if(x is 左括號)

push StackA(x);

}

while(scan expression right to left And not EOF) {

y←read( );

if(y is 右括號)

    push StackB(y);

}

}

while(StackA And StackB not EOF) {

x←pop(StackA);

y←pop(StackB);

if(x 與 y 是同一類型的左右括號)

    output “Match”;

else {

    output “Not Match”;

}

}

if(StackA and StackB empty)

output “Match”;

else

output “Not Match”;

(二)

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 的右括號 )，配對失敗。不用繼續比對。

 

二、演算法的分類

undefined

(一)貪婪法(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)

n

0

1

2

3

4

5

6

7

8

Fn

0

1

1

2

3

5

8

13

21

  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.相異處：

Greedy Approach

Dynamic Programming

1.是一種階段性 (Stage) 的方法

2.具有一選擇程序 (Selection Procedure)，自某起始點 (值) 開始，在每一個階段逐一檢查每一個輸入是否適合加入答案中，重複經過多個階段後，即可順利獲得最佳解

3.較為簡單 (若遇最佳化問題，先思考可否用Greedy Approach 解，若不行再考慮用Dynamic Programming)

4.如果所要處理的最佳化問題無法找到一個選擇程序，則需要考慮所有的可能情況，就是屬於 Dynamic Programming

1.先把所有的情況都看過一遍，才去挑出最佳的結果

2.考慮問題所有可能的情況，將最佳化問題的目標函數表示成一個遞迴關係式，結合 Table 的使用以找出最佳解

3.每採用一次貪婪準則便做出一個不可撤回的決策；而在動態程式規劃中，還要檢視每個最佳決策序列中是否包含一個最佳的子序列

※參考資料：

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

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

 

※子問題重覆(Overlapping Subproblem)：

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

undefined

※參考資料：

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

 

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

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

2.不同處：

 

各個擊破法

動態規劃

計算方式

可能會對相同子問題進行重覆計算

使用表格將子問題的計算結果加以儲存，在後面階段如果需要這個計算結果，再直接由表格中取出使用。可以避免許多重覆的計算，以提高效率

記憶體空間

不需要額外記憶體空間來儲存計算結果

需要額外記憶體空間來儲存計算結果

解題方式

Top-Down↓

Bottom-Up↑

適用

非重疊(non-overlap)子問題

重疊(overlap)子問題

※參考資料：(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，都相同才可以相乘。

undefined

※參考資料：

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

2.Am×n×Bn×p = Cm×p

3.

4.演算法：

for i←1 to m do

for j←1 to p do

begin

cij←0; // 初始化陣列 C，C[i][j] = 0

for k←1 to n do

    // c[i][j] = c[i][j]+a[i][k]×b[k][j] // 陣列 a 乘上陣列 b，然後存入陣列 c

cij←cij+aik×bkj; // k 迴圈跑完一輪才能算出一個 cij

end

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

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

undefined

(a11×b11+a12×b21)，(a11×b12+a12×b22)，(a11×b13+a12×b23)，(a11×b14+a12×b24)

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：

如何由一陣列中找到最大與最小的值？

答：

[方法一]

undefined

[方法二]

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

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

3.比較次數：undefined。

undefined

 

※範例：

103關三

寫一副程式對一個長度為10的整數陣列 A[0:9]，最多花費15次的數值比較運算，尋找陣列中的最小值及最大值。

答：

#include <iostream>

using namespace std;

#define INF 100;

/* 測試用 */

void printData(int data[ ], int n) {

for(int i = 0; i < n; i++) {

cout << data[i] << ",";

}

cout << endl;

}

void FindMinMax(int A[ ], int size, int &min, int &max) {

int arr1[10] = {0};

int arr2[10] = {0};

int j = 0;

int k = 0;

/* 陣列相鄰值兩個為一組互相比較，分別找出最大值及最小值*/

for(int i = 0; i < size; i = i+2) {

if(A[i] < A[i+1]) {

min = A[i];

            max = A[i+1];

}

else {

min = A[i+1];

            max = A[i];

}

arr1[j++] = min;

        arr2[k++] = max;

}

/* 上述陣列值大的分為一組，小的為另一組 */

min = arr1[0];

max = arr2[0];

/* 陣列值大的一組找出最大值，陣列值小的一組找出最小值 */

for(i = 1; i < size/2; i++) {

if(arr1[i] < min)

min = arr1[i];

if(arr2[i] > max)

max = arr2[i];

}

printData(arr2, 10); // 測試用

}

int main(void) {

int data[ ] = {5, 6, 12, -5, 7, 22, 4, 80, 3, 45};

int min;

int max;

FindMinMax(data, 10, min, max);

    cout << "min=" << min << ",max=" << max << endl;

    return 0;

}

 

※範例2：

將 n 個 boolean 所有可能的變數結果輸出。例如 n = 2，則有 true, false；false, true；true, true；false, false 四種可能。

答：

undefined

 

※範例3：

求出2到1000之間的所有質數。

答：

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)。

for(i = 2; i <= 1000; i++) a[i] = 1;

for(i = 2; i< = 1000; i++) {

if(a[i] == 1) {

printf(“%i”, a[i]);

for(k = i+i; k <= 1000; k += i) // 找出所有 i 的倍數

a[k] = 0; // 當i = 2 時，a[4] = 0, a[6] = 0, a[8] = 0, a[10] = 0, ...

}

}

undefined

 

※範例4：

計算 x 的 y 次方。

答：

[方法一]

undefined

int pow1(int x, int y) {

int p = 1;

for(int i = 1; i <= y; i++) {

p = p*x;

}

return p;

}

[方法二]

p←1;

while y > 0 do begin

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

x←x*x;

y←[y/2];

end;

undefined

int pow2(int x, int y) {

           int p = 1;

           while(y > 0) {

                     if(y%2 == 1) { // y 是奇數

                                p = p*x;

                     }

                     x = x*x;

                     y = y/2;

           }

           return p;

}

 

103年關務三等資料結構

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

答：

略

 

103年關務三等資料結構

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

答：

略

 

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

二、分別給定矩陣 A、B、C 與 D 的大小為2×4、4×3、3×5 和5×1：（每小題5分，共15分）

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

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

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

答：

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

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

undefined

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

undefined

undefined

A2×4×B4×3×C3×5×D5×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。

A2×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關三

(一)定義

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

(二)常用結構

陣列結構

是一種結構性的資料儲存空間，同一陣列裡的資料性質呈一致性，元素與元素之間的記憶體位置是相鄰的

堆疊結構

先進後出的堆疊特性

佇列結構

先進先出的特性

串列結構

由許多節點所組成的，在加入和刪除功能上比陣列容易許多

樹狀結構

由一個或多個節點所組成的有限集合，是一種有層次的結構

圖形結構

是由節點和邊所組成的的集合。很像樹狀結構，不同的地方是節點之間沒有父子關係

 

※各種資料結構關係：

undefined

 

※線性結構(linear structure)：

1.定義：

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

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 為例，說明如下：

<customers>

<user>

<name>Squall</age>

<age>18</age>

</user>

<user>

<name>Mario</school>

<shoe_color>brown</shoe_color>

</user>

</customers>

如果以上方的 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年檢察事務官三等資料結構

二、在圍棋程式中，最常用的三種資料結構為何？請說明其用途。（30分）

答：

(一)圖形

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

(二)遊戲樹

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

(三)堆疊或佇列

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

 

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

三、一個大型社群網路 (network) 中可能包含多個興趣小社群 (interest group)，社群網路常使用圖形 (graph) 為模型 (modeling)。（15分）

(一)請說明圖形的資料結構及表示法 (representation)。

(二)請描述找出小社群 (graph connected components) 的方法。

答：

(一)

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

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

 

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

二、在大富翁的遊戲中，我們需要那些資料結構來幫助我們設計該遊戲？請詳述之。（25分）

說明：大富翁 (Monopoly) 是一種多人策略圖版遊戲。參賽者分得遊戲金錢，憑運氣 (擲骰子) 及交易策略，買地、建樓以賺取租金。

答：

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

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

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

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

 

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

四、在作業系統資源管理程式中，我們需要那些資料結構來幫助我們適當的分配 CPU 的執行時間？請詳述之。（25分）

答：

暫略

 

103年關務三等資料結構

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

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

答：

arrow
arrow
    文章標籤
    資料結構
    全站熱搜

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

    E-mail轉寄