資料處理概要考古題｜歷屆國考試題彙整

給定以下有向加權圖（7 個節點A~G，15 條有向邊） 執行Dijkstra 演算法，逐步計算節點A 到每個節點的最短距離與路 徑。請以此例說明Dijkstra 演算法的運作方式，寫出每一步目前的「A 到每個節點的最短距離」與「前接節點（predecessor）」。（15 分） 請寫出A 到各節點的最短路徑與路徑長度。（5 分） 舉出兩個Dijkstra 演算法實際上的應用。（10 分）

某一公司的採購資料如下所述： 每一位客戶包含有屬性客戶編號、姓名、電話、地址。在客戶中，客戶 編號具有唯一性。 每一張訂單包含有屬性訂單編號、購貨日期。在訂單中，訂單編號具有 唯一性。每一張訂單裡的每一項產品都有其訂購數量之屬性。 每一項產品包含有屬性產品編號、產品名稱、單價。而在產品中，產品 編號具有唯一性。 每一位客戶可能都沒下過訂單，也可能下過多張訂單。 每一張訂單必定為某一位客戶且也僅能為一位客戶所下訂的。 每一張訂單包含有至少一項以上產品；每項產品可能被多張不同訂單所 訂購過，也可能未被任何訂單所訂購過。（每小題10 分，共40 分） 試依上述說明，為該公司畫出一實體關聯圖（Entity Relationship Diagram, ER Diagram）。該實體關聯圖需標出每一實體的名稱、屬性、 主鍵屬性（Key attribute）、每一關係（Relationship）及其基數性 （cardinality）。 試為該實體關聯圖（ER Diagram），決定出最簡化之各關聯表格。需描 述出每一表格的名稱、屬性（attribute）、主要鍵（primary key）及外來 鍵（foreign key）。 試寫出一SQL 程式片段，為每一張訂單所採購之每一項產品，列印出 該訂單編號、產品名稱及採購金額。 試寫出一SQL 程式片段，為每一張訂單列印出該訂單編號及該訂單所 採購總金額。

L1 為一由小而大排序之資料串列，L2 為一由大而小排序之資料串列，其 分別含有N1 與N2 筆資料，且N1, N2≫0：（每小題10 分，共20 分） 請設計出一最佳演算法，以能最快速查詢一資料D 是否存在於資料串 列L1 或L2 內。 並求出該演算法之時間複雜度（請越精確估算越佳）。

QuickSort 和MergeSort 是常見的排序演算法，各自有優點與缺點。 假設你負責設計一個「線上圖書目錄系統」，需要對50 萬筆已經按照 「出版年份」由大到小排序的書籍資料，重新依照「作者名稱」排序， 讓使用者能快速找到作者撰寫的書，但同時需要保持同一作者撰寫的 書籍能依據原本出版年份順序排列。根據QuickSort 和MergeSort 兩 種演算法的特性，你會選擇那一種演算法？為什麼？（10 分） 有一個數列[39, 18, 61, 46, 11, 2, 24, 33]，利用QuickSort（以第一個元 素為基準）進行由小到大的排序，請寫出並說明每一次循環的結果。 （10 分） 與上面問題同一個數列，利用MergeSort 進行由小到大的排序，請寫 出並說明每一次循環的結果。（10 分）

請撰寫一演算法，透過堆疊（stack）以計算出一後序式數學運算式（Postfix Expression）（例如"E=23*5+"）之結果。假設運算式中只含加、減、乘、 除（+, -, *, /）四種運算子（operator），及0, 1, …, 9 十種運算元（operant）。 （10 分）

資料庫中有一個資料表Books，包含以下欄位BookID（書籍編號）、Title （書名）、Author（作者）、Publisher（出版社）、PubYear（出版年份）、 ISBN（國際標準書號），其中BookID 為資料表的主鍵。 請寫一個SQL 查詢，尋找張曼娟於2020 年出版的書籍名稱與出版社。 （10 分） 請說明下列SQL 語法之查詢過濾條件與輸出欄位為何？（10 分） 請以JOIN 指令，利用自我關連的概念，改寫上面的查詢。（20 分） SELECT Title, Author, Publisher FROM Books WHERE PubYear IN (SELECT PubYear FROM Books WHERE Author = '村上春樹' AND Publisher = '時報出版公司');

應用適當的密碼學機制，可確保資料的機密性（confidentiality）、完整性 （integrity）、鑑別性（authenticity）、不可否認性（non-repudiation）之安 全目標。 試解釋何謂機密性、完整性、鑑別性、不可否認性。（8 分） 若A 欲將機密資料D，透過網路傳送給B。請透過雜湊（Hash）函式 及RSA 加密法，設計一資料加密機制，以確保機密資料之機密性、完 整性、鑑別性。（10 分） 若A 欲將一電子合約D，透過網路傳送給B 簽章。請透過雜湊（Hash） 函式及RSA 加密法，設計一數位簽章機制，以確保電子合約之機密 性、完整性、鑑別性、不可否認性。（12 分）

在關聯式資料庫中建立一個名為「圖書」資料表，其欄位結構與資料表 內容如下表所示： 圖書編號 圖書名稱 出版社 作者 售價 數量 B01 Visual Basic 6手冊 A公司 Mary 350 5 B02 Excel 2023 A公司 David 499 1 B03 Access 2023 B公司 Mary 600

現今資料庫管理系統都支援交易（Transaction）功能。 請說明何謂交易排程（Transaction Schedule）。（5 分） 說明Recoverable Schedule、Cascadeless Schedule 與Strict Schedule 的 交易排程特性。（15 分）

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

B04 Python訓練手冊 C公司 Kathy 355

B05 手把手Word 2023 A公司 Mary 400 2 B06 E世代網頁設計 B公司 Kim 555 5 B07 T-SQL 2023程式設計 A公司 Helen 699 2 寫出SQL 語法查詢圖書名稱包含字串”手”的圖書名稱、出版社、作者 的查詢結果，如下表所示：（10 分） 圖書名稱 出版社 作者 Visual Basic 6手冊 A公司 Mary Python訓練手冊 C公司 Kathy 手把手Word 2023 A公司 Mary 寫出SQL 語法查詢作者為”Mary”且數量小於3 的圖書名稱、作者、數 量，且圖書名稱為遞減排序的查詢結果，如下表所示：（15 分） 圖書名稱 作者 數量 手把手Word 2023 Mary 2 Access 2023 Mary 2 寫出SQL 語法查詢新增一個欄位進價（內容為售價*數量），其數值介 於1000 至2000 的圖書名稱、售價、數量、進價的查詢結果，如下表 所示：（15 分） 圖書名稱 售價 數量 進價 Visual Basic 6手冊 350 5 1750 Access 2023 600 2 1200 Python訓練手冊 355 3 1065 T-SQL 2023程式設計 699 2 1398 二、資料結構中的佇列（Queue）是一個有序串列（List），請說明佇列在加入 （Insertion）和擷取（Retrieve）資料的原則；分別寫下以佇列方式加入和 擷取｛6,23,11,27,58｝數字串列的順序情形。（20 分） 三、請描述電子通勤（E-commuting）對於員工、公司、社會的好處。（20 分）

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

網路詐騙的方式中，社交工程（Social Engineering）與網路釣魚（Phishing） 的操作手法為何？（20 分）

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

網際網路包含TCP、ARP、SNMP、ICMP 與DNS 等協定。（每小題15 分， 共30 分） 說明上述協定用途。 說明上述協定位於TCP/IP 協定堆疊中的那一分層。

在資料庫中，建有資料表「Company」，其為一家水果行的資訊，如下圖 所示，欄位分別代表ID、販售水果名稱、價格與產地。請回答下列問題： ID Product Price Origin 1 banana 10 Tainan

apple 50 Taichung

papaya 45 Tainan

grape 120 Taichung

lemon 20 Taipei

orange 30 Taichung

pineapple 40 Kaohsiung

watermelon 100 Kaohsiung 9 guava 60 Tainan 10 tomato 70 Kaohsiung 寫一個SQL指令查詢該水果行所販售的水果名稱中有包含字串“apple” 的水果之名稱與售價，查詢結果如下圖所示。（10分） 水果 價格 apple 50 pineapple 40 寫一個SQL指令查詢該水果行所販售的水果來自不同產地的種類數量， 查詢結果請按產地名稱排序，查詢結果如下圖所示。（10分） 產地 數量 Kaohsiung 3 Taichung 3 Tainan 3 Taipei 1 寫一個SQL指令查詢該水果行所販售的水果來自不同產地且種類數量 大於2的水果平均價格，查詢結果請按平均價格由低到高排序，查詢結 果如下圖所示。（15分） 產地 均價 Tainan 38.33 Taichung 66.67 Kaohsiung 70 二、有一筆資料為12，10，7，23，13，6，15，17，46，3。 請依序建置最小堆積（Min heap）樹（由上而下Top Down建置）。（10分） 請依序建置最大堆積（Max heap）樹（由上而下Top Down建置）。（10分） 把上題所產生的最大堆積樹刪除最大元素，其更新完的結果為何？ （15分） 三、有一手機透過無線路由器連上網際網路時的網路設定如下圖所示，請回 答下列問題： 何謂MAC位址？（5分）其規範於OSI七層網路架構中的那一層？（5分） 該層的主要功能為何？（5分） IP位址屬於OSI七層網路架構中的那一層？（5分） 請說明何謂DNS？（5分）其屬於OSI七層網路架構中的那一層？（5分）

設M 與N 分別含有m 及n 個元素之兩個數列陣列。 試設計一演算法Sort（M, N, P, m, n），將M 與N 內之元素，合併成一 個新陣列P。合併後P 內之元素需依小而大排序；該演算法的執行時 間需最佳。（15 分） 試計算所設計出之演算法Sort（M, N, P, m, n）的執行時間複雜度。 （10 分）

一個m × n 的二維矩陣Am × n，其中列數m = 5，行數n = 4，A 矩陣大部 分的元素值為0，屬於稀疏矩陣，請試述： 稀疏矩陣的缺點？（10 分） 使用一個二維密集矩陣B 表現稀疏矩陣A。A 矩陣的非零元素分別為 A(0,0) = 1, A(1,1) = 2, A(2,2) = 3, A(3,0) = 4, A(4,3) = 5，如圖，請畫出B 矩陣。（20 分） 1 0 0 0 0

設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(StringPFExp)：移除PFExp 中最前面的字元，並傳回該字元。 (Boolean)EMPTY(String PFExp)：如PFExp 為一空字串時，傳回TRUE， 否則傳回FALSE。 44440

0 0 0 0

假設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 分） （※需寫出推導過程）

0

0 0 0 0 0 0

以下為某種程式語言的pseudocodes，其中main()為主程式，p(int x,int y, int z) 為被呼叫的副程式。 若副程式是以傳名呼叫（passed byname）法，則主程式印出的結果為何？ （3 分） 若副程式是以傳址呼叫（passed by reference）法，則主程式印出的結 果為何？（3 分） 若副程式是以傳值呼叫（passed by value）法，則主程式印出的結果為何？ （3 分）

二、有一資料表R，以R(A, B, C, D, E, F)表示，A～F 為資料表R 的欄位名 稱，功能相依以X→Y 表示，表欄位Y 依賴欄位X。資料表R 存在下列 功能相依： A→(E, F) B→C (A, D)→(B, C, E, F) 請問： R 資料表的主鍵為何？（10 分） 將資料表R 正規化為符合三階正規資料表，其中必須將三階正規化後 的所有資料表，標出主鍵(P)和外部鍵(F)。（20 分） 三、容錯式磁碟陣列（Redundant Array of Independent Disks; RAID）的使用 對於資料的儲存策略影響深遠，請試述何謂RAID 0、RAID 1？假設共 有n 顆硬碟，每顆硬碟規格皆相同，請就組成RAID 0、RAID 1 最少 硬碟數、最大容錯硬碟數、可用容量硬碟數三方面，比較它們的差異。 （10 分） 44630 四、網際網路上的應用，如全球資訊網（World Wide Web）的應用已蓬勃發 展，有所謂的WEB1.0、WEB2.0、WEB3.0 世代的演進，其中WEB3.0 有學者認為是語意網的發展，另一派學者認為是去中心化的發展，目前 尚無定論。請以資訊提供者、資訊品質、資訊互動性，試述比較WEB1.0 和WEB2.0 的差異。（30 分）

以下顯示一Ethernet 2000 網路架構： 當剛打開網路系統後，PC1 向PC3 傳遞資料，描述Switches 傳送該資 料的過程及資料內容的變化。（10 分） 隨後PC5 向PC1 傳遞資料，描述Switches 傳送該資料的過程及資料 內容的變化。（10 分） PC3 00-F1-EE-50-DC-92 Switch 1 PC6 09-54-11-2d-c5-22 PC1 00-13-46-9A-63-74 PC4 00-E0-4C-39-00-1F PC2 80-C1-6E-F3-E7-6A PC5 00-03-FF-C0-CD-98 fa0/1 fa0/3 fa0/2 fa0/4 p(int y, int x, int z) { x = x+z; z = x+1; x = y+z; y = z;} main( ) { x = 2; y = 5; p(x, y, 3); print x, y}

在Microsoft Access 中，建有「老師資料表」與「課程資料表」，兩個表 格皆有四個欄位，內容如下圖： 老師資料表 課程資料表 老師ID 姓名 電話 年紀 課程ID 課程名稱 老師ID 人數 1 張三 123 30 1 國文 1 58

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

王武 456 56 2 英文 2 63

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

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

劉丹 897 42 3 數學 1 42

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

陳河 658 39 4 物理 2 89

某機器共有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 分）

高樂 756 60

假如某公司的關聯式資料庫包含以下三個表格，其內之欄位如括號內所示。 客戶（客戶編號，姓名，電話，地址，年齡） 產品（產品編號，產品名稱，價格，庫存數量） 訂單（訂單編號，購貨日期，客戶編號，產品編號，購買數量） 請寫出SQL 敘述（statement）以列出地址在臺北市的客戶姓名與電話。 （5 分） 請寫出SQL 敘述以列出各個產品名稱及其平均購買數量。（7 分） 針對不同客戶，請寫出SQL 敘述以計算各個客戶所購買之各產品的購 買數量。（8 分）

化學 3 67

微積分 4 75

音樂 5 30 9 美術 5 36 10 電子學 4 69 其資料庫關聯圖如下圖所示， 在「課程資料表」中，PK 與FK 的欄位名稱為何？（5 分） 請說明上圖1↔∞關聯的特色與優點。（8 分） 寫一個SQL 指令查詢來得到下表，其中欄位「人數總和」為該老師所 開所有課程的人數總和。（10 分） 姓名 人數總和 王武 152 高樂 66 張三 100 陳河 144 劉丹 67 寫一個SQL 指令查詢來得到課程老師的年紀小於55 歲，且人數大於 50 人的課程資訊表，如下表所示，且該資料需以人數遞減排序。（12 分） 課程ID 課程名稱 姓名 電話 人數 7 微積分 陳河 658 75 10 電子學 陳河 658 69 6 化學 劉丹 897 67 1 國文 張三 123 58 1 ∞ 老師資料表 老師ID 姓名 電話 年紀 課程資料表 課程ID 課程名稱 老師ID 人數 45130 二、有一筆資料的鍵值依序為32，17，85，16，51，60。使用除法雜湊函數 ( ) mod 7 h k k  來建立7 個桶（buckets）且每個桶只有一個槽（slot）的 雜湊表（hash table）。當發生碰撞（collision）與溢位問題時， 如果使用開放定址（open addressing）中的線性探測法（linear probing）， 請寫出產生的雜湊表格。（5 分）而此方法的主要缺點為何？（5 分） 如果使用開放定址（open addressing）中的平方探測法（quadratic probing），新的雜湊函數為：    2 , mod 7 H k i h k i       ，其中i 為目前 進行的探測次數。請寫出產生的雜湊表格。（10 分） 請說明何謂連結串列法（chaining）。（8 分） 請寫出使用連結串列法而產生的雜湊表格。（7 分） 三、電腦無線網路的標準為IEEE802.11 系列，常見的包含有802.11ac 802.11b 802.11n 802.11g 802.11ax， 請問WiFi 5 與WiFi 6 各指的是那一個標準？（10 分） 請問何謂MIMO？（10 分） 上述標準中，支援MIMO 的標準有那幾個？（5 分） 上述標準中，工作頻率可為2.4 kHz 或5 kHz 標準有那幾個？（5 分）

給定一個有權重的圖形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分）

CSMA/CD（Carrier Sense Multiple Access/ Collision Detection）與CSMA/CA （Carrier Sense Multiple Access/ Collision Avoidance）是兩項現今普及的網 路通訊協定，請比較兩者之間的差異以及各自的運作過程。（25分）

在資料處理語言（DML），JOIN 是用來合併兩個或多個表格中的資料。 請分別以Inner Join、Left Outer Join、Right Outer Join 和Full Join 運算查 詢來合併員工（Employee）與部門（Department）資料表，並將SQL 的查 詢語法及各個JOIN 合併後的資料表內容，完整列出。（20 分） Employee 資料表： Emp_No Emp_Name Dep_No ManagerID E01 張三 D101 E08 E02 李四 D102 E09 E03 王五 E04 趙六 D103 E05 鄭七 E08 Department 資料表： Dep_No Dep_Name D101 行銷部 D102 人力資源部 D103 研發部 D104 財務部 D105 MIS 部

關聯式代數（Relational Algebra）是針對關聯式模型的一組基本運算集合， 關聯式資料庫的SQL 語法是以「關聯式代數」作為它的理論基礎，根據 E.F.Codd 所提出的「關聯式代數」有八種基本運算子，除了合併（Join）、 交集（Intersection）及除法（Division）三種非原始運算子外，另有五種運 算子所成的集合稱為「完整集合」（Complete Set），又稱為原始運算子 （Primitive Operators），是不能由其他運算子導出的運算子，請說明此五 種原始運算子的定義與用法。（20 分）

雲端運算（Cloud Computing）是繼1980 年代大型電腦到客戶端-伺服器 （Client-Server）的行動計算資料處理架構，請詳細說明：（每小題10 分， 共20 分） 雲端運算之部署模型。 雲端運算之服務模型。

何謂AVL 樹？（5 分） 給定一個數列「47, 24, 31, 53, 18, 65, 13」，將此數列的每個數字依序加 入AVL 樹，顯示數字加入後的AVL 樹，過程中如果需要旋轉，請逐一 將AVL 樹調整前與調整後的狀態畫出並註明旋轉方式。（15 分）

當進行資料傳輸，為了確保資料的正確性，通常會在所傳送的資料中，加 入一些錯誤檢測技術，漢明碼（Hamming Code）就是一種錯誤檢查碼。請 回答下列問題，並列出每個步驟： 若資料為1101101011，使用偶同位漢明碼予以編碼，編碼後Hamming code 為何？（10 分） 若接收到偶同位元的Hamming code 為1001000，試問此訊息正確編碼 為何？原資料為何？（10 分）

在資料庫中，建有資料表「Company」，其為一家水果行的資訊，如下圖 所示，欄位分別代表ID、販售水果名稱、價格與產地。請回答下列問題： ID Product Price Origin 1 banana 10 Tainan

使用結構化查詢語言（Structured Query Language, SQL），對SalesData 的 資料表進行查詢，計算出每個部門的平均業績。最後顯示出部門ID （DepartmentID）以及各部門的平均業績（AverageSales），並依平均業績 遞減排列。（25 分） 資料表名稱：SalesData EmployeeID DepartmentID SalesAmount 101 1 1000 102 1 1500 103

apple 50 Taichung

800 104 2 1200 105

900 二、請解釋乙太網路（Ethernet）和WiFi 分別使用的媒體存取控制（Media Access Control, MAC）協議，並敘述兩者的傳輸方式。（25 分） 三、依序輸入數值為：39, 18, 61, 46, 11, 2, 24, 33，請使用這些數值，劃出刪 除節點11 後的二元搜尋樹。（25 分）

papaya 45 Tainan

雜湊函數（Hash Function）作為一種常見的資料加密演算法，請詳細說 明雜湊函數之特性。（25 分）

grape 120 Taichung

lemon 20 Taipei

orange 30 Taichung

pineapple 40 Kaohsiung

watermelon 100 Kaohsiung 9 guava 60 Tainan 10 tomato 70 Kaohsiung 寫一個SQL指令查詢該水果行所販售的水果名稱中有包含字串“apple” 的水果之名稱與售價，查詢結果如下圖所示。（10分） 水果 價格 apple 50 pineapple 40 寫一個SQL指令查詢該水果行所販售的水果來自不同產地的種類數量， 查詢結果請按產地名稱排序，查詢結果如下圖所示。（10分） 產地 數量 Kaohsiung 3 Taichung 3 Tainan 3 Taipei 1 寫一個SQL指令查詢該水果行所販售的水果來自不同產地且種類數量 大於2的水果平均價格，查詢結果請按平均價格由低到高排序，查詢結 果如下圖所示。（15分） 產地 均價 Tainan 38.33 Taichung 66.67 Kaohsiung 70 二、有一筆資料為12，10，7，23，13，6，15，17，46，3。 請依序建置最小堆積（Min heap）樹（由上而下Top Down建置）。（10分） 請依序建置最大堆積（Max heap）樹（由上而下Top Down建置）。（10分） 把上題所產生的最大堆積樹刪除最大元素，其更新完的結果為何？ （15分） 三、有一手機透過無線路由器連上網際網路時的網路設定如下圖所示，請回 答下列問題： 何謂MAC位址？（5分）其規範於OSI七層網路架構中的那一層？（5分） 該層的主要功能為何？（5分） IP位址屬於OSI七層網路架構中的那一層？（5分） 請說明何謂DNS？（5分）其屬於OSI七層網路架構中的那一層？（5分）

一個m × n 的二維矩陣Am × n，其中列數m = 5，行數n = 4，A 矩陣大部 分的元素值為0，屬於稀疏矩陣，請試述： 稀疏矩陣的缺點？（10 分） 使用一個二維密集矩陣B 表現稀疏矩陣A。A 矩陣的非零元素分別為 A(0,0) = 1, A(1,1) = 2, A(2,2) = 3, A(3,0) = 4, A(4,3) = 5，如圖，請畫出B 矩陣。（20 分） 1 0 0 0 0

設M 與N 分別含有m 及n 個元素之兩個數列陣列。 試設計一演算法Sort（M, N, P, m, n），將M 與N 內之元素，合併成一 個新陣列P。合併後P 內之元素需依小而大排序；該演算法的執行時 間需最佳。（15 分） 試計算所設計出之演算法Sort（M, N, P, m, n）的執行時間複雜度。 （10 分）

設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(StringPFExp)：移除PFExp 中最前面的字元，並傳回該字元。 (Boolean)EMPTY(String PFExp)：如PFExp 為一空字串時，傳回TRUE， 否則傳回FALSE。 44440

0 0 0 0

假設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 分） （※需寫出推導過程）

0

以下為某種程式語言的pseudocodes，其中main()為主程式，p(int x,int y, int z) 為被呼叫的副程式。 若副程式是以傳名呼叫（passed byname）法，則主程式印出的結果為何？ （3 分） 若副程式是以傳址呼叫（passed by reference）法，則主程式印出的結 果為何？（3 分） 若副程式是以傳值呼叫（passed by value）法，則主程式印出的結果為何？ （3 分）

0 0 0 0 0 0

以下顯示一Ethernet 2000 網路架構： 當剛打開網路系統後，PC1 向PC3 傳遞資料，描述Switches 傳送該資 料的過程及資料內容的變化。（10 分） 隨後PC5 向PC1 傳遞資料，描述Switches 傳送該資料的過程及資料 內容的變化。（10 分） PC3 00-F1-EE-50-DC-92 Switch 1 PC6 09-54-11-2d-c5-22 PC1 00-13-46-9A-63-74 PC4 00-E0-4C-39-00-1F PC2 80-C1-6E-F3-E7-6A PC5 00-03-FF-C0-CD-98 fa0/1 fa0/3 fa0/2 fa0/4 p(int y, int x, int z) { x = x+z; z = x+1; x = y+z; y = z;} main( ) { x = 2; y = 5; p(x, y, 3); print x, y}

二、有一資料表R，以R(A, B, C, D, E, F)表示，A～F 為資料表R 的欄位名 稱，功能相依以X→Y 表示，表欄位Y 依賴欄位X。資料表R 存在下列 功能相依： A→(E, F) B→C (A, D)→(B, C, E, F) 請問： R 資料表的主鍵為何？（10 分） 將資料表R 正規化為符合三階正規資料表，其中必須將三階正規化後 的所有資料表，標出主鍵(P)和外部鍵(F)。（20 分） 三、容錯式磁碟陣列（Redundant Array of Independent Disks; RAID）的使用 對於資料的儲存策略影響深遠，請試述何謂RAID 0、RAID 1？假設共 有n 顆硬碟，每顆硬碟規格皆相同，請就組成RAID 0、RAID 1 最少 硬碟數、最大容錯硬碟數、可用容量硬碟數三方面，比較它們的差異。 （10 分） 44630 四、網際網路上的應用，如全球資訊網（World Wide Web）的應用已蓬勃發 展，有所謂的WEB1.0、WEB2.0、WEB3.0 世代的演進，其中WEB3.0 有學者認為是語意網的發展，另一派學者認為是去中心化的發展，目前 尚無定論。請以資訊提供者、資訊品質、資訊互動性，試述比較WEB1.0 和WEB2.0 的差異。（30 分）

在Microsoft Access 中，建有「老師資料表」與「課程資料表」，兩個表 格皆有四個欄位，內容如下圖： 老師資料表 課程資料表 老師ID 姓名 電話 年紀 課程ID 課程名稱 老師ID 人數 1 張三 123 30 1 國文 1 58

已知110002，1103，1024，1025，556，447，518，係用不同進位表達的數 字，例如518 是一個用8 進位表達的數字51。（每小題10 分，共20 分） 請將它們全部轉換為10 進位的數字。 請用快速排序法（quick sort）來將這些表達成10 進位的數字作排序， 並說明過程。

同步控制（concurrency control）是資料庫管理系統（DBMS）裡的必要功 能之一。請說明下列有關問題：（每小題10 分，共20 分） 如果資料庫管理系統沒有做好同步控制，則有可能在多筆交易 （transactions）同時執行時，發生資料更新後有錯誤的情形，請說明這 是指什麼問題。 二階段鎖定協定（two-phase locking protocol）可以保證有衝突的交易在 更新資料時仍保持資料的正確性。請說明什麼是二階段鎖定協定，並解 釋為什麼二階段鎖定能使有衝突的交易仍能被正確的執行。

王武 456 56 2 英文 2 63

劉丹 897 42 3 數學 1 42

某資料庫有下列關連，請用SQL 語法回答下列查詢。 （每小題10 分，共20 分） 學生（學號，姓名，電話） 成績（學號，科目名稱，分數） 針對一查詢是「列出所有在科目名稱是“資料處理”這門課裡分數不及 格（< 60 分）的學生的姓名和電話」，某同學想要用巢狀查詢（nested query）的寫法來回答此查詢。可是只完成了上半部，請幫他完成此查詢 餘下的部分。亦即，請填入下列括號裡“？”部分應填入的指令。 SELECT 姓名，電話 FROM 學生 WHERE 學號IN（？）； 請列出各個科目的科目名稱，和所有學生在該科目成績的平均分數。

已知一個二元樹如下圖。（每小題10 分，共20 分） 說明用廣度優先的順序來走訪這棵樹，其順序為何？ 說明用深度優先的順序來走訪這棵樹，其順序為何？

陳河 658 39 4 物理 2 89

在關聯式資料庫（Relational Database）裡，針對關聯有一些限制條件 （Constraints）。（每小題10 分，共20 分） 請說明什麼是鍵值限制（Key Constraint）。 請說明什麼是參考完整限制（Referential Integrity Constraint）。

高樂 756 60

假如某公司的關聯式資料庫包含以下三個表格，其內之欄位如括號內所示。 客戶（客戶編號，姓名，電話，地址，年齡） 產品（產品編號，產品名稱，價格，庫存數量） 訂單（訂單編號，購貨日期，客戶編號，產品編號，購買數量） 請寫出SQL 敘述（statement）以列出地址在臺北市的客戶姓名與電話。 （5 分） 請寫出SQL 敘述以列出各個產品名稱及其平均購買數量。（7 分） 針對不同客戶，請寫出SQL 敘述以計算各個客戶所購買之各產品的購 買數量。（8 分）

化學 3 67

微積分 4 75

音樂 5 30 9 美術 5 36 10 電子學 4 69 其資料庫關聯圖如下圖所示， 在「課程資料表」中，PK 與FK 的欄位名稱為何？（5 分） 請說明上圖1↔∞關聯的特色與優點。（8 分） 寫一個SQL 指令查詢來得到下表，其中欄位「人數總和」為該老師所 開所有課程的人數總和。（10 分） 姓名 人數總和 王武 152 高樂 66 張三 100 陳河 144 劉丹 67 寫一個SQL 指令查詢來得到課程老師的年紀小於55 歲，且人數大於 50 人的課程資訊表，如下表所示，且該資料需以人數遞減排序。（12 分） 課程ID 課程名稱 姓名 電話 人數 7 微積分 陳河 658 75 10 電子學 陳河 658 69 6 化學 劉丹 897 67 1 國文 張三 123 58 1 ∞ 老師資料表 老師ID 姓名 電話 年紀 課程資料表 課程ID 課程名稱 老師ID 人數 45130 二、有一筆資料的鍵值依序為32，17，85，16，51，60。使用除法雜湊函數 ( ) mod 7 h k k  來建立7 個桶（buckets）且每個桶只有一個槽（slot）的 雜湊表（hash table）。當發生碰撞（collision）與溢位問題時， 如果使用開放定址（open addressing）中的線性探測法（linear probing）， 請寫出產生的雜湊表格。（5 分）而此方法的主要缺點為何？（5 分） 如果使用開放定址（open addressing）中的平方探測法（quadratic probing），新的雜湊函數為：    2 , mod 7 H k i h k i       ，其中i 為目前 進行的探測次數。請寫出產生的雜湊表格。（10 分） 請說明何謂連結串列法（chaining）。（8 分） 請寫出使用連結串列法而產生的雜湊表格。（7 分） 三、電腦無線網路的標準為IEEE802.11 系列，常見的包含有802.11ac 802.11b 802.11n 802.11g 802.11ax， 請問WiFi 5 與WiFi 6 各指的是那一個標準？（10 分） 請問何謂MIMO？（10 分） 上述標準中，支援MIMO 的標準有那幾個？（5 分） 上述標準中，工作頻率可為2.4 kHz 或5 kHz 標準有那幾個？（5 分）

給定一個有權重的圖形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分）

CSMA/CD（Carrier Sense Multiple Access/ Collision Detection）與CSMA/CA （Carrier Sense Multiple Access/ Collision Avoidance）是兩項現今普及的網 路通訊協定，請比較兩者之間的差異以及各自的運作過程。（25分）

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

合併是指將兩個關聯表依合併條件合併成一個新的關聯表，當在進行合 併時不管紀錄是否符合條件，都會被列出其中一個資料表的所有紀錄，稱 為「外部合併」。下表分別為學生資料表以及課程資料表，若對兩個資料 表進行全外部合併，其結果為何？（學號為主鍵）（25分） 學生資料表 學號 姓名 課號 S0001 張三 C001 S0002 李四 C002 S0003 王五 C005 S0004 林六 NULL 課程資料表 課號 課名 學分數 C001 資料結構

C002 資訊管理 3 C003 系統分析 3 C004 程式設計

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

C005 資料庫系統 4 三、請利用SQL語法列出「產品資料表」之全部產品編號、銷售業績、產品售價、 產品名稱，並將銷售業績由低到高排序，但銷售業績為零的除外。（25分） 四、請問下列二元樹的中序、前序以及後序表示法為何？並繪出對應於該二 元樹之引線二元樹。（25分） 1 6 3 2

給定某二元樹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分）

4 7