資料處理概要（統計組）　申論題歷屆試題與參考架構

給定以下有向加權圖（7 個節點 A~G，15 條有向邊）A→B: 2 A→C: 4 A→D: 5 B→C: 1 B→D: 6 B→E: 3 C→D: 5 C→E: 2 C→F: 3 D→F: 2 D→G: 5 E→F: 2 E→G: 4 F→E: 2 F→G: 1

（一）執行 Dijkstra 演算法，逐步計算節點 A 到每個節點的最短距離與路徑。請以此例說明 Dijkstra 演算法的運作方式，寫出每一步目前的「A到每個節點的最短距離」與「前接節點（predecessor）」。（15 分）

（二）請寫出 A 到各節點的最短路徑與路徑長度。（5 分）

（三）舉出兩個 Dijkstra 演算法實際上的應用。（10 分）

（30 分）

QuickSort 和 MergeSort 是常見的排序演算法，各自有優點與缺點。

（一）假設你負責設計一個「線上圖書目錄系統」 ，需要對 50 萬筆已經按照「出版年份」由大到小排序的書籍資料，重新依照「作者名稱」排序，讓使用者能快速找到作者撰寫的書，但同時需要保持同一作者撰寫的書籍能依據原本出版年份順序排列。根據 QuickSort 和 MergeSort 兩種演算法的特性，你會選擇那一種演算法？為什麼？（10 分）

（二）有一個數列[39, 18, 61, 46, 11, 2, 24, 33]，利用 QuickSort（以第一個元素為基準）進行由小到大的排序，請寫出並說明每一次循環的結果。（10 分）

（三）與上面問題同一個數列，利用 MergeSort 進行由小到大的排序，請寫出並說明每一次循環的結果。（10 分）

（30 分）

資料庫中有一個資料表 Books，包含以下欄位 BookID（書籍編號） 、Title（書名） 、Author（作者）、Publisher（出版社）、PubYear（出版年份）、ISBN（國際標準書號），其中 BookID 為資料表的主鍵。

（一）請寫一個 SQL 查詢，尋找張曼娟於 2020 年出版的書籍名稱與出版社。（10 分）

（二）請說明下列 SQL 語法之查詢過濾條件與輸出欄位為何？（10 分）SELECT Title, Author, Publisher FROM Books WHERE PubYear IN (SELECT PubYear FROM Books WHERE Author = '村上春樹' AND Publisher = '時報出版公司');

（三）請以 JOIN 指令，利用自我關連的概念，改寫上面的查詢。（20 分）

（40 分）

現今資料庫管理系統都支援交易（Transaction）功能。

（一）請說明何謂交易排程（Transaction Schedule）。 （5 分）

（二）說明 Recoverable Schedule、Cascadeless Schedule 與 Strict Schedule 的交易排程特性。（15 分）

（20 分）

設計資料庫程式必須滿足那些交易執行（Transaction）性質，以確保交易結果不會產生非預期狀況。（20 分）

（20 分）

資料庫系統中有一個名為 student 資料表，請說明執行下列 SQL 指令對資料庫會有的影響。 （每小題 10 分，共 20 分）

（一）DROP TABLE student CASCADE;

（二）DROP TABLE student RESTRICT;

（20 分）

將中序運算式 A *（B – C）-（D + E）/ F *（G – H）轉換成後序運算式。（10 分）

（10 分）

網際網路包含 TCP、ARP、SNMP、ICMP 與 DNS 等協定。（每小題 15 分，共 30 分）

（一）說明上述協定用途。

（二）說明上述協定位於 TCP/IP 協定堆疊中的那一分層。

（30 分）

設 M 與 N 分別含有 m 及 n 個元素之兩個數列陣列。

（一）試設計一演算法 Sort（M, N, P, m, n），將 M 與 N 內之元素，合併成一個新陣列 P。合併後 P 內之元素需依小而大排序；該演算法的執行時間需最佳。（15 分）

（二）試計算所設計出之演算法 Sort（M, N, P, m, n）的執行時間複雜度。（10 分）

（25 分）

設 PFExp 為一字串，描述著一個以後置運算式（postfix expression）表示之 數 學 運 算 式 ， 例 如 PFExp = “ 62/3-42*+ ” 。 當 中 每 一 個 運 算 元（operand）皆僅為一個位數整數，且只有‘+’、‘-’、‘*’、‘/’四種可能運算子（operator）。

（一）寫出一演算法(int)postfix_math(string PFExp)，利用堆疊（Stack）計算該後置運算式，並傳回該運算結果。（15 分）

（二）以您所設計之演算法，來計算數學運算式 PFExp =“62/3-42*+”。寫出在執行過程中每一步驟 Stack 及 PFExp 的內容。（10 分）以下是您可能會用到的副程式：(int)POPStack(Stack)：移除 Stack 中最前面的整數，並傳回被移除的整數。PUSHStack(Stack, V)：將整數 V 放入 Stack 的最前面。(int)DECV(char C)：將一字元 C 轉成一整數，並傳回該整數。(char)First_Char(String PFExp)：移除 PFExp 中最前面的字元，並傳回該字元。(Boolean)EMPTY(String PFExp)：如 PFExp 為一空字串時，傳回 TRUE，否則傳回 FALSE。

（25 分）

假設 T 為一個符合第一正規化要求之關聯表格，且 T 包含有屬性為{A, B, C, D, E, F, G, H}，以下描述其屬性間之功能相依的關係性：BC → GH, AD → E, A → H, E → BCF, G → H

（一）決定出表格 T 之最合適的主要鍵（primary key）。（5 分）

（二）將 T 轉化成符合第二正規化要求的關聯表格，並指出關聯表格的主要鍵。（8 分）

（三）將（二）轉化後的關聯表格，轉成符合第三正規化要求之表格，並標出表格的主要鍵。（8 分）（※需寫出推導過程）

（21 分）

以下為某種程式語言的 pseudo codes，其中 main( )為主程式，p(int x, int y, int z)為被呼叫的副程式。main( ) p(int y, int x, int z) { x = 2; y = 5; p(x, y, 3); print x, y} { x = x+z; z = x+1; x = y+z; y = z;}

（一）若副程式是以傳名呼叫（passed by name）法，則主程式印出的結果為何？（3 分）

（二）若副程式是以傳址呼叫（passed by reference）法，則主程式印出的結果為何？（3 分）

（三）若副程式是以傳值呼叫（passed by value）法，則主程式印出的結果為何？（3 分）

（9 分）

以下顯示一 Ethernet 2000 網路架構：PC1 PC4 00-13-46-9A-63-74 00-E0-4C-39-00-1F fa0/1 PC2 fa0/2 fa0/4 PC5 Switch 1 80-C1-6E-F3-E7-6A 00-03-FF-C0-CD-98 fa0/3 PC3 PC6 00-F1-EE-50-DC-92 09-54-11-2d-c5-22

（一）當剛打開網路系統後，PC1 向 PC3 傳遞資料，描述 Switches 傳送該資料的過程及資料內容的變化。（10 分）

（二）隨後 PC5 向 PC1 傳遞資料，描述 Switches 傳送該資料的過程及資料內容的變化。（10 分）

（20 分）

請說明必須同時具備那四個條件才可能使資料處理程序（process）產生死結（deadlock）？（16 分）

（16 分）

請說明設計關聯式資料庫時，實體關係模型（Entity-Relationship Model） 、資料庫綱目（Database Schema）與資料正規化（Data Normalization）等三項技術的功能？（21 分）

（21 分）

某個二維陣列由 a(1, 1)開始，若 a(2, 3)的位址為 56，a(3, 2)的位址為 76，a(4, 5)的位址為 112，則 a(6, 2)的位址為何？（10 分）

（10 分）

請說明堆疊（Stack）、佇列（Queue）與鏈結串列（Linked List）資料結構之資料儲存方式以及在其上可採行的操作特性。（21 分）

（21 分）

某機器共有 7 個指令，分別為 A~G。假設其出現的機率分別如下：A：0.25 B：0.20 C：0.15 D：0.13 E：0.12 F：0.10 G：0.05若以哈夫曼編碼（Huffman coding）方式將指令編碼，且左子樹編碼為 0，右子樹編碼為 1，則指令 A~G 的編碼分別為何？（12 分）

（12 分）

假如某公司的關聯式資料庫包含以下三個表格，其內之欄位如括號內所示。客戶（客戶編號，姓名，電話，地址，年齡）產品（產品編號，產品名稱，價格，庫存數量）訂單（訂單編號，購貨日期，客戶編號，產品編號，購買數量）

（一）請寫出 SQL 敘述（statement）以列出地址在臺北市的客戶姓名與電話。（5 分）

（二）請寫出 SQL 敘述以列出各個產品名稱及其平均購買數量。 （7 分）

（三）針對不同客戶，請寫出 SQL 敘述以計算各個客戶所購買之各產品的購買數量。（8 分）

（20 分）

給定一個有權重的圖形 G=(V, W)，V 為頂點集合，W 為邊以及該邊上權重的集合。假設 V={A,B,C,D,E,F}，W={{A,B,2},{A,C,6},{B,D,7},{C,D,4},{C,E,5},{D,F,10},{E,F,9}}，請找出 G 的最小生成樹（Minimum Spanning Tree），並詳細說明執行的步驟。（25分）

（25 分）

假設關聯式資料庫資料表命名為“員工”，內容記錄以下欄位：編號、姓名、性別、薪資、部門別，若欲查詢各部門的員工平均薪資，應該下達之 SQL 指令為何？又欲查詢各部門的男性員工人數，應該下達之 SQL指令為何？（25分）

（25 分）

假設關聯式資料庫中有員工資料表，其綱要（Schema）定義如下：員工（員工編號、姓名、性別、薪資、專長）專案（專案編號、起始日期、專案金額、專案類別）專案管理（專案編號、員工編號、工作角色）若欲查詢參與專案類別為‘大數據分析’的專案編號、員工編號、姓名、專長及擔任該專案裏的工作角色，應該下達之 SQL 指令為何？（25分）

（25 分）

給定某二元樹 T=(V, X)，V 為頂點的集合，且 V={A,B,C,D,E,F,G,H,I}，X為邊的集合，且 X={{A,B},{A,C},{B,D},{B,E},{E,F},{E,G},{G,H},{G,I}}，請以節點 A 為樹根，並以中序（In-order）拜訪法依序列出拜訪的節點。（25分）

（25 分）

試寫出此 99 / 9 + 46 * 36 / 6 – 12 * 42 運算式的前序表示法與後序表示法。（25 分）

（25 分）

請 利 用 SQL 語 法 列 出 員 工 資 料 表 （ Employee ） 內 之 員 工 編 號（Employee_no），姓名（Employee_name）以及訂單資料表（Order）內之 訂 單 編 號 （ Order_no ）， 送 貨 日 期 （ Delivery_date ）， 交 貨 日 期（Order_date），並將結果使用員工編號遞增排序，其中：（25 分）員工資料表中包含員工編號，姓名，職稱，性別訂單資料表中包含訂單編號，員工編號，送貨日期，交貨日期

（25 分）

分別說明可搶先排班演算法（Preemptive Scheduling）與不可搶先排班演算法（Nonpreemptive Scheduling）二者的優缺點。（25 分）

（25 分）

封 包 傳 送 當 中 的 錯 誤 控 制 方 式 技 術 有 兩 種 ， 分 別 為 回 退 N 重 傳（Go-back-N, GBN）和選擇性重複（Selective Repeat, SR），請比較兩種方式的差異以及各自的優點。（25 分）

（25 分）

佇列（queue）和堆疊（stack）是二種常用的資料結構。請回答下列問題。

（一）若要用深度優先的方式（depth-first search）走訪一樹狀結構（tree structure）的所有節點（node），請問佇列和堆疊，何者較適合？並說明原因。（10 分）

（二）若要用廣度優先的方式（breadth-first search）走訪一樹狀結構（tree structure）的所有節點（node），請問佇列和堆疊，何者較適合？並說明原因。（10 分）

（20 分）

有一資料表如下圖，共有八筆資料，第一欄是鍵值（key value）的二進位表示法（Binary representation），第二欄是姓氏資料。今要用雜湊（hash）的方式來將資料分成若干籃子（bucket），請回答下列有關雜湊的問題。鍵值（二進位表示法） 姓1000 Lee 0000 Chen 0010 Wang 1001 Hwang 1011 Lu 0100 Chao 1110 Liao 0111 Chang

（一）假設雜湊函數（hashing function）是 key mod 4，亦即將 key 的值除以4 之餘數值，即為雜湊函數值。假設每個籃子的容量最多可存三筆資料，請以上表之資料為例，將鍵值之二進位值轉換為十進位值，並將這些資料按所給的雜湊函數，區分為應有的籃子，並以此例說明什麼是靜態雜湊（static hashing）。（10 分）

（二）假設每個籃子的容量最多可存二筆資料，請以上表鍵值之二進位表示法為例，用動態雜湊（dynamic hashing）的方法，將這八筆資料做 hash。（10 分）

（20 分）

請說明物聯網（Internet of Things）、網際網路（Internet）、全球資訊網（World Wide Web）這三者不同之處。 （10 分）

（10 分）

有一資料庫其中一個關連（relation）裡有 A, B, C, D, E 這些欄位（attribute），且他們之間存在一些功能相依（functional dependency）的關係：{CE→ABD, A→D, E→B }。此關連已滿足第一正規化。

（一）請將此關連作第二正規化處理，說明理由，並指出何者為關鍵欄位（key attribute）。（10 分）

（二）請將此關連作第三正規化處理，說明理由，並指出何者為關鍵欄位。（10 分）

（20 分）

有一資料庫記載一些客戶資料，和他們下訂單訂購貨物的資訊如下：客戶（身分證字號，姓名，電話，地址，年齡）貨品（貨品編號，貨名，價格，庫存量）訂單（貨品編號，身分證字號，訂貨日期，訂購數量）請用 SQL 回答下列查詢。

（一）找出所有年齡大於 60 歲（年齡>60） ，所下訂單之訂貨日期為 20180101的客戶，列出他們的姓名和地址。 （10 分）

（二）找出年齡低於 20 歲（年齡<20）的客戶，列出他們的姓名，電話和在 2017年（20170101<=訂貨日期<=20171231）裡下訂單的次數。（10 分）

（20 分）

說明什麼是「區塊鏈」 （Block Chain）。列舉四個區塊鏈最重要的特色，並說明之。（10 分）

（10 分）

請透過下圖使用 Dijkstra’s Algorithm 找出頂點 a 至其他所有頂點的最短路徑，請詳細說明演算法選擇頂點的過程及結果：（20 分）2 b e 2 5 3 a 2 f 4 c d

（20 分）

資料之鍵值為 27, 12, 9, 60, 55, 39, 22，請以氣泡排序法排序：

（一）寫出排序的過程及其結果。（10 分）

（二）在最佳和最壞情況下之時間複雜度分別為何？（10 分）

（20 分）

學生資料表 STUDENT 當中有學號 Student_ID、姓名 NAME 兩個欄位，成績表 SCORE中有學號 Student_ID、課程代號 Course_ID 和成績 Student_SC 三個欄位，要列出成績大於 90 分的學生姓名、課程代號及成績，請寫出 SQL 指令語句。 （20 分）

（20 分）

資料鏈結層的功能包含了流量控制以及錯誤控制，請詳加說明流量控制以及錯誤控制。（20 分）

（20 分）

作業系統可依照處理資料方式區分成多種作業系統類型，請詳加說明批次處理作業系統（Batch processing OS） 、分時作業系統（Time-sharing OS）以及平行式作業系統（Parallel Operating System）三者之處理方式及特點。 （20 分）

（20 分）

何謂 SQL injection？要如何避免 SQL injection 的攻擊？（20 分）

（20 分）

考慮下列關聯式資料庫的三個 table：顧客（Customer）、產品（Product）和交易（Transaction）。他們的結構（schema）定義如下：Customer（cName, cID, address）、Product（pName, pID, price）、Transaction（cID, pID, amount）。（每小題 10 分，共 20 分）

（一）顧客「李大同」要買產品「H 牌手機」一支，請寫出 SQL 指令來更新 table。

（二）如果有同名同姓的顧客，依（一）的 SQL 指令其執行結果是否正確？要如何解決？

（20 分）

資料結構中的堆積（heap）是什麼？如何利用堆積來排序（sorting）？請分析堆積排序（heap sort）的時間複雜度。（30 分）

（30 分）

IP 位址（Internet Protocol Address）、MAC 位址（Media Access Control Address）和網頁地址（Uniform Resource Locator, URL）各是什麼？為何需要這麼多不同的地址？它們之間如何對應？（30 分）

（30 分）

請回答下面關於一般資訊應用概念上的問題：一般所謂 3C 產品的 3C 所指為何？電腦程式語言有世代的演進，請問從第一代到第三代的程式語言，各有何特性？目前流行之雲端運算環境，從終端使用者的角度來檢視，有何異於傳統電腦應用之處？請詳述之。（20 分）

（20 分）

在有線網路的連接技術上，集線器與交換器在作用上與功能上有何差異？而在無線網路的環境中，目前無線區域網路所遵循的通訊協定為何？如何運作？（20 分）

（20 分）

以 A[N, M]表示 X 軸從 0 到 N-1，Y 軸從 0 到 M-1 的二維陣列。假設陣列的起始位置是 1024（即 A[0, 0]的位址為 1024），每個陣列元素占用 4 個位元組（byte）的空間。請問，宣告陣列 A[100, 200]需要多少位元組的空間？在以行為主（column majored）的定址方式下，陣列元素 A[50, 100]的位址為何？（10 分）

（10 分）

在一個連通圖（connected graph）中，連線（edge）數跟節點（vertex）的分支度個數之間的關係為何？何謂連通平面圖（connected planar graph）？請問一個 4 個節點的完全圖（complete graph）K4 是否為一個連通平面圖？請說明理由。（20 分）

（20 分）

分別以陣列跟串列的資料結構來表示堆疊，在實作與應用上，請詳述兩種表示法有何差異？（20 分）六、一個 XML 的檔案包含那些部分？傳統的關聯式資料庫管理系統與 XML 檔案系統，在資料的表示上有何差異？請詳述之。（10 分）

（30 分）