一、⑴請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩 者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的 差異（13 分）。

⑵若有 n 個鍵值，以下列甲和乙兩種資料結構策略儲存：  策略甲：由小到大依序儲存在一陣列中  策略乙：以 AVL tree 架構儲存  請以 Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或 兩者效能相近：1.尋找特定鍵值 k；2.尋找排序為 j 的鍵值；3.刪除特定鍵值 k； 4..刪除排序為 j 的鍵值；5.插入新鍵值；6.依序輸出所有鍵值。 （12 分）

二、一非空的二元樹（binary tree） ，如果有 n0 個葉節點（leaf node）且 n2 個節點之分支 度（degree）為 2，請證明 n0 = n2+1。（25 分）

三、一無向圖 G 之節點集合為 G(V)={0,1,2,3,4,5,6,7,8,9}，邊集合為 G(E)={(0,1), (1,2), (1,3), (2,4), (3,4), (3,5), (5,6), (5,7), (6,7), (7,8), (7,9)}；請列出 G 之接合點（articulation point）和畫出 G 的所有雙連通元件（biconnected component），雙連通元件須以節點 和邊構成之子圖方式表示。 （20 分）

⑴請說明 SMMH 特性並說明以 SMMH 建構之優先佇列與以一般的堆積（heap）建 構 之 優 先 佇 列 功 能 有 何 不 同 ？ 並 從 一 個 空 的 SMMH 開 始 ， 依 序 插 入 30,20,50,5,4,9,70,2,80。請畫出最後 SMMH 的樹狀結構圖。（10 分）

⑵請畫出第⑴小題建構的 SMMH，刪除數字 2 後 SMMH 的樹狀結構圖。 （5 分）

⑶請以一維陣列設計一資料結構儲存 SMMH，該資料結構可以使節點透過其對應之 陣列索引值 x 構成的數學式計算出其祖父節點 g、父節點 p、左子節點 l、右子節 點 r 與兄弟節點 s 等在陣列中的索引值。假設一維陣列之起始索引值為 0，請列出 由 x 構成之計算 g、p、l、r、s 的數學式。並請畫出以此一維陣列儲存第⑴小題建 構完成的 SMMH 的結果。（15 分）

一、請為如下的醫療院所設計符合 BCNF 且考量 OO 的 EER data model，model 中請註明 合適的 primary/foreign/candidate keys，資料表間的關聯亦請適當地說明彼此間的 maximum/minimum cardinality。註：不需要用到的資料不必列入。 （30 分） • 假設一位醫師或護理人員只會屬於一個科別，但可以支援其它科別的門診 • 假設某一診間同一看診時段，只會安排一位醫師跟護理人員 • 醫師跟護理人員同屬於醫療單位的工作人員，除了工作人員的基本資料外，醫師 會記錄「主治項目」 、「學歷」 、「經歷」、 「現職」，護理人員會記錄「專長」 • 系統可依科系（如「內科系」 ）、科別（如「消化內科」）查詢科別的醫療項目 • 系統可依醫師查詢醫師的主治項目、學歷、經歷、現職、性別、門診時刻表（包 括：日期、時段、醫師姓名、診間代號及掛號現況） • 系統可依科系、科別查詢門診時刻表 • 系統可依病患查詢該病患的預約掛號資料，包括：病患身分代號/病歷號碼/病患、 科系、科別、醫師代號/姓名、日期、時段、掛號號碼 • 系統可列印各日期時段的診間掛號資料，包括：科系、科別、日期、時段、醫師 代號/姓名、護理人員代號/姓名、病患身分代號/姓名/性別/年齡（可藉由出生年月 日計算）

⑴定義資料表 MedicalRecord（定義中應適當表示 primary and foreign key）（10 分）

⑵請依推拿師代號（nID）為分群依據，找出日期為"2018-06-06"，且該日期相對應 推拿師所經手的醫療次數大於零時，個別推拿師在該日期所經手的相關醫療總收 費金額及醫療次數（結果資料表應包含推拿師的名字、別名為"收費總金額"的醫療 總收費金額、及別名為"醫療次數"的醫療次數，結果並依醫療次數作降冪排列顯 示）。 （10 分）

四、假設現有如圖三個 transactions 同步存取資料 A, B, C，請使用 conflict equivalent 說明圖中同步執行的非序列排程 （ non-serial schedule ），是否具有排程循序性（serializability）；如果具備排程循序性，執行結果可以等同於三個 Transactions 的那種序列排程；如果不具排程循序性，衝突的 cycle 為何？（15 分）

115年 - 115 關務特種考試_三等_資訊處理（選試英文）：資料結構#138980

115年 - 115 身心障礙特種考試_三等_資訊處理：資料結構#138979

114年 - 114 地方政府公務特種考試_三等_資訊處理：資料結構#134706

114年 - 114 公務升官等考試_薦任_資訊處理：資料結構#133251

114年 - 114 高等考試_三級_資訊處理：資料結構#128753

114年 - 114 關務特種考試_三等_資訊處理（選試英文）：資料結構#126563

114年 - 114 身心障礙特種考試_三等_資訊處理：資料結構#126562

113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理：資料結構#124511

113年 - 113 高等考試_三級_資訊處理：資料結構#121217

113年 - 113 關務特種考試_三等_資訊處理（選試英文）：資料結構#119489