111年高考三級資料結構
|
四、用 G = (V, E) 表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點(Vertices) 形成邊及對應權重 (Weights) 所組成的集合。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5}，圖形的邊與權重值以如下的定義儲存對應連接矩陣 (Adjacency matrix) 表示中的值 #define MAX_EDGES 100 typedef struct { int col; int row; int weight; } edge; |
111年高考三級資料結構
|
三、一個二元搜尋樹 (Binary search tree) 的前序追蹤 (Preorder traversal) 結果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20 請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式 sortTree (NODEPTR tree)，輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25分）
|
111年高考三級資料結構
|
二、利用鏈結串列 (Linked list) 實做佇列 (Queues)，給予如下鏈結串列節點及 佇列定義，front 指標指在串列第一個節點，rear 指標指在串列最後一個節點，請使用 C 語言完成 insert(pq, x) 程序，將整數值 x 加入 (Insert) 到佇列，程式需檢查佇列加入前是否為空的鏈結串列，可使用函數 getnode( ) 配置 (Allocate) 一新節點。（25分）
|
111年身心障礙人員三等資料結構
|
二、以下7個數字 [21, 1, 16, 11, 25, 9, 35]，要儲存到 Hash Table 中，Hash Table的儲存空間是一個索引從0開始的一維陣列 (Array)。假設 Hash 函數為 H(Key) = (Key*3) mod 7，裝填因子 (Load Factor) 為0.7。 (一)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的線性探測法 (Linear Probing)：增量函數 F(i) = i (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分） (二)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的平方探測法 (Quadratic Probing)：增量函數 F(i) = i2 (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分） |
答：
[21, 1, 16, 11, 25, 9, 35]
裝填因子 = 資料個數/總容量 = 0.7，表示有7筆資料，總容量10個。
(一)
111年關務三等資料結構
|
四、以文本 (text) X = “AGTCATTCGATTC”，樣式 (pattern) Y = “ATTC” 兩字串為例，請問使用暴力比較/窮舉法 (exhaustive search) 中的樣式前向法(forward) 及後向法 (backward) 各需比較幾次？（10分） |
答：
暴力比較法實作：
|
#include <iostream> #include <string> using namespace std; int Find(char Text[ ], char Pattern[ ]) { |
關務三等資通網路：110
身心障礙人員三等資通網路：110
鐵路特考高員三級資通網路：無
警察人員特種考試刑事警察人員數位鑑識組二等電腦通訊：110
警察人員特種考試刑事警察人員電子監察組二等網路工程：無
高考三級資通網路：110
檢察事務官三等計算機網路：110
法務部調查局調查人員四等電腦網路概要：無
關務三等資訊管理：110
身心障礙人員四等資訊管理概要：110
身心障礙人員三等資訊管理：110
鐵路特考員級資訊管理概要：無
鐵路特考高員三級資訊管理：無
警察人員特種考試刑事警察人員數位鑑識組二等網路與資訊安全：110
警察人員特種考試資訊管理人員三等資訊管理：110
警察人員特種考試資訊管理人員三等網路安全與資訊倫理：110
關務三等資料結構：110
身心障礙人員三等資料結構：110
鐵路特考高員三級資料結構：無
高考三級資料結構：110
專利商標審查人員三等資料結構：無
關務人員升官等薦任資料結構：110
資訊技師高等資料結構與資料庫及資料探勘：110
地方特考三等資料結構：110
關務三等資料庫應用：110
鐵路特考高員三級資料庫應用：無
警察人員特種考試刑事警察人員數位鑑識組二等資料庫管理與運用：110
警察人員特種考試刑事警察人員電子監察組二等資料庫管理與運用：無
警察人員特種考試資訊管理人員三等資料庫應用：110
國家安全情報人員三等資料庫應用：110
高考三級資料庫應用：110
法務部調查局調查人員三等資料庫應用：110
身心障礙人員三等程式語言：110
鐵路特考高員三級程式語言：無
警察人員特種考試資訊管理人員三等物件導向程式設計：110
高考三級程式語言：110
檢察事務官三等程式語言：110
關務人員升官等薦任程式語言：110
資訊技師高等程式設計：110
地方特考三等程式設計：110
身心障礙人員三等資訊系統與分析：110
國軍上校以上軍官轉任上校轉任系統分析：無
鐵路特考高員三級資訊系統與分析：無
高考二級系統分析與設計研究：110
高考二級軟體專案管理研究：110
高考三級系統專案管理：110
檢察事務官三等系統分析：110
法務部調查局調查人員三等系統分析與設計：110
關務三等資通網路：109
身心障礙人員三等資通網路：109
鐵路特考高員三級資通網路：無
警察人員特種考試刑事警察人員數位鑑識組二等電腦通訊：109
警察人員特種考試刑事警察人員電子監察組二等網路工程：無
高考三級資通網路：109
檢察事務官三等計算機網路：109
法務部調查局調查人員四等電腦網路概要：無
關務三等資訊管理：109
身心障礙人員四等資訊管理概要：無
身心障礙人員三等資訊管理：109
鐵路特考員級資訊管理概要：無
鐵路特考高員三級資訊管理：無
警察人員特種考試刑事警察人員數位鑑識組二等網路與資訊安全：109
警察人員特種考試資訊管理人員三等資訊管理：109
警察人員特種考試資訊管理人員三等網路安全與資訊倫理：109
關務三等資料結構：109
身心障礙人員三等資料結構：109
鐵路特考高員三級資料結構：無
高考三級資料結構：109
專利商標審查人員三等資料結構：無
關務人員升官等薦任資料結構：無
資訊技師高等資料結構與資料庫及資料探勘：109
地方特考三等資料結構：109
關務三等資料庫應用：109
鐵路特考高員三級資料庫應用：無
警察人員特種考試刑事警察人員數位鑑識組二等資料庫管理與運用：109
警察人員特種考試刑事警察人員電子監察組二等資料庫管理與運用：無
警察人員特種考試資訊管理人員三等資料庫應用：109
高考三級資料庫應用：109
法務部調查局調查人員三等資料庫應用：109
國家安全情報人員三等資料庫應用：同上
身心障礙人員三等程式語言：109
鐵路特考高員三級程式語言：無
警察人員特種考試資訊管理人員三等物件導向程式設計：109
高考三級程式語言：109
檢察事務官三等程式語言：109
關務人員升官等薦任程式語言：無
資訊技師高等程式設計：109
地方特考三等程式設計：109
身心障礙人員三等資訊系統與分析：109
國軍上校以上軍官轉任上校轉任系統分析：無
鐵路特考高員三級資訊系統與分析：無
高考三級系統專案管理：109
檢察事務官三等系統分析：109
法務部調查局調查人員三等系統分析與設計：109
法務部調查局調查人員四等系統分析與設計概要：無
外交行政人員四等資訊組系統分析及設計與資料庫應用概要：109
關務三等資通網路：108
身心障礙人員三等資料通訊：無
鐵路特考高員三級資通網路：無
警察人員特種考試刑事警察人員數位鑑識組二等電腦通訊：108
警察人員特種考試刑事警察人員電子監察組二等網路工程：無
高考三級資通網路：108
檢察事務官三等計算機網路：108
法務部調查局調查人員四等電腦網路概要：無
關務三等資訊管理：108
身心障礙人員四等資訊管理概要：無
身心障礙人員三等資訊管理：無
鐵路特考員級資訊管理概要：無
鐵路特考高員三級資訊管理：無
警察人員特種考試刑事警察人員數位鑑識組二等網路與資訊安全：108
警察人員特種考試資訊管理人員三等資訊管理：108
警察人員特種考試資訊管理人員三等網路安全與資訊倫理：108
關務三等資料結構：108
身心障礙人員三等資料結構：無
鐵路特考高員三級資料結構：無
高考三級資料結構：108
專利商標審查人員三等資料結構：無
關務人員升官等薦任資料結構：108
資訊技師高等資料結構與資料庫及資料探勘：108
地方特考三等資料結構：108
國考資訊處理解答 (7)
