105-1 Data Structure Exam 1 2016/12/27

成績計算 Design a maze (15x15) Find the path to exit Use stack Random Print the original array (10%) Print the result array with the path (60%) Replace the value on the path to 3 (30%) Replace remained element to * (30%) If it is the shortest path (30%) Show the shortest path length Use stack Do not use recursive function

Mazing problem 0 : though path 2 : though path 1 : blocked path N、W、S、E、NW、SW、SE、NE 2 : though path N、W、S、E 1 : blocked path You can’t walk this road

Mazing problem (10%) 0 1 0 2 0 1 1 0 1 0 1 0 0 2 1 2 1 0 2 1 0 1 0 1 1 2 0 2 1 0 1 0 2 1 0 1 2 0 2 0 0 2 2 0 2 1 1 0 1 0 0 1 1 0 2 0 2 1 2 2 1 2 0 1 0 1 0 1 0 0 0 2 0 1 1 2 1 0 1 2 1 0 1 0 1 2 2 0 1 2 2 1 2 0 2 0 1 1 2 0

Result array with the path (30%) If it is the shortest path (30%) 3 1 0 2 0 1 1 0 1 0 1 3 0 2 1 2 1 0 2 1 3 1 0 1 1 2 0 2 1 0 1 3 2 1 0 1 2 0 2 0 0 2 3 3 2 1 1 0 1 0 0 1 1 0 3 0 2 1 2 2 1 2 0 1 3 1 0 1 0 0 0 2 0 1 1 3 1 0 1 2 1 0 1 0 1 2 3 3 1 2 2 1 2 0 2 0 1 1 3 3

Replace remained element to * (30%) 3 * * * * * * * * * * 3 * * * * * * * * * * 3 3 * * * * * * * * * * 3 * * * * * * * * * * 3 * * * * * * * * * * 3 3 * * * * * * * * * * 3 3

Example

105-1 Data Structure Exam 2 2016/12/27

成績計算 統計字數：10% 進行霍夫曼樹編碼：15% 壓縮成功：45% 解壓縮回來也正確：30%

Huffman Codes 霍夫曼在1952年所提出的一種無失真壓縮技術，它的原理是將要壓縮之字串，先讀一遍，再將字串中的每一個相異單字元的出現頻率，做成統計，依此來建構霍夫曼樹。 每一相異的字元，用0與1給他編碼，出現次數最多者，給較少的位元編碼，最後將這些位元串組合起來，並加上霍夫曼樹，就成為壓縮檔案。

Huffman Codes 步驟一：計算每一個符號出現的機率，然後把所有符號跟機率放入要處理符號集合R中，準備由(下往上)建立一棵編碼二元樹。 步驟二：從要處理的集合中找出機率最小的兩個符號做為二元樹的兩個子節點，並為這兩個節點建立一個父節點，此父節點機率為兩個子節點的機率和。再將這兩個子節點從R中移除，且把其父節點(含機率)加入R中。 步驟三： 重複步驟二直到待處理集合只剩下一個符號。 步驟四：將建立完成的二元樹中任何兩兄弟節點的左邊線標上0右邊線標上1。樹中每個符號被指定之0與1的位元集合即是代表該符號的字碼。 步驟五： 使用在步驟四決定的符號字碼，一一編碼所有待壓縮符號。 霍夫曼編碼法在許多標準中被採用，最著名的就是應用於失真影像壓縮標準的JPEG中。在JPEG標準中，影像被切割為8x8的區塊，每一區塊各自進行轉換編碼，轉換後的64個係數就是使用霍夫曼編碼法加以編碼、壓縮。

Example Use Huffman coding to encode the fallowing symbols with the frequencies listed: A:0.08, B:0.10, C:0.12, D:0.15, E:0.20, F:0.35. What is the average number of bits used to encode a character ?

Example 於題目中找尋最小兩點→A:0.08和B:0.10(A於右下B於左下∵B>A) 接著把A+B視為新的一點0.18，再找最小兩點→C:0.12和D:0.15如同AB方法接起來 C+D也視為新的一點0.27再比大小，之後依此方法作完全部的點 而全圖於右下角的支線都為1,左下角都之線都為0 因此A by 111,B by 110,C by 011,D by 010, E by 10, F by 00. So the average number of bits used to encode a symbol using this encoding is 3×0.08+3×0.10+3×0.12+3×0.15+2×0.20+2×0.35=2.45

統計字數：10% 統計10

進行霍夫曼樹編碼：15% 進行編碼15

壓縮成功：45% 壓縮45

解壓縮回來也正確：30% 解壓縮30

105-1 Data Structure Exam 3 2016/12/27

成績計算 隨機數 + print出來，如圖，1~5點都要 (30%) 深度最短路徑 (30%) 負載平衡 (40%)

Map部分說明 定義<5,5>為原點: o 最短路徑由原點北邊到達原點定為:0 最短路徑由原點東邊到達原點定為:1 最短路徑由原點南邊到達原點定為:2 最短路徑由原點西邊到達原點定為:3 若點無法通過活點到達原點o則定為獨立點: iso

探討深度的影響以點<6,7>為例 深度最短路徑 (30%) 北方群組0的<5,7>的depth=4 東方群組尚未被定義(因為在比較外層) 南方為死點不考慮 西方群組2的<6,6>的depth=2 因西方群組depth較少 所以選西方群組2

探討深度的影響以點<6,7>為例 深度最短路徑 (30%)

探討深度相同時，node數的影響 深度最短路徑 (30%) 以點<3,3>為例: 北方群組尚未被定義(因為在比較外層) 東方群組0的<3,4>的depth=3,node=8 南方群組3的<4,3>的depth=3, node=3 西方群組尚未被定義(因為在比較外層) 雖然東方和南方depth數一樣，但node數南方群組較少 所以選南方群組3

探討深度相同時，node數的影響 深度最短路徑 (30%)

證明load balance:將全部點都設為活點(99) 並附上Depth 深度紀錄 (40%)

105-1 Data Structure Exam 4 2016/12/27

題目及配分 給一個2015年全國空氣指數資料集 請算算看2015全國哪個測站，紫爆天數最多？ 成績計算 假設當日PM2.5的平均值大於60，則算該日該地區紫爆 成績計算 篩選出各地區只有PM2.5的資料 (30%) 資料中有符號的要變成沒有符號 輸出成txt檔 算出各地區每日PM2.5的平均值並排序 (60%) 用三種不同的排序(Quick、Merge、Bubble) 比較使用這三者的不同(time complexity) 紫爆天數排序 (10%)

各種不同的資料 日期,測站,測項,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23 2015/01/02,龍潭,PM10,40,40,40,47,49,45,49,47,55,50,54,56,59,54,53,47,52,46,44,32,26,28,31,37 不是PM2.5 2015/01/02,龍潭,PM2.5,15,12,9,14,17,20,18,22,21,23,18,25,24,27,18,23,18,19,18,21,23,18,19,19 2015/11/28,龍潭,PM2.5,16,18,15,20,13,18,8,16,11,23,19,21,22,15,16,10,21,24,21,10,7,10,9,9 有同地區不同天的PM2.5 2015/10/10,林口,PM2.5,17,19,17,12,17,17,17,17,16,20,20,23,18,19,23,19,21,19,21,24,26,30,32,31 不同地區的PM2.5 2015/09/04,新竹,PM2.5,32,28,27,25,25,26,25,24,25,17,18,29,19,16,17,11,12,17*,17,13,14,16,17,17 可能出現符號 2015/03/13,斗六,PM2.5,39,26,27,20,30,33,42,47,45,48,50,73,88,92,87,78,74,74,69,76,87,95,99,95 真正需要的紫爆資料

結果 第一個txt檔 (30%) 不同的排序方法所耗費時間 將不同排序方法排序後的資料存進txt (3個) 各地區每天的PM2.5資料 Quick sort : x秒 (20%) Merge sort : y秒 (20%) Bubble sort : z秒 (20%) 將不同排序方法排序後的資料存進txt (3個)

結果 算出各地區紫爆總天數後，將這些資料排序 (10%) 範例 紫爆天數最多的第一個，以此類推 (0次的不用) 斗六 50 新竹 44 雲林 42 新店 30 … 宜蘭 1

Random Ascii Ctime String