民國112年 高考三級 資訊處理 資料結構收錄考選部官方試題，共 4 題可線上瀏覽，考選部未公告本科目答案。
某一公司有下圖所示的8個優先順序分別為高或低的待執行工作，且將依 順序自A至H每間隔一天的時間放入對應的高優先執行佇列（Queue）或低 優先執行佇列（Queue），例如A（低）表示A工作將於第一天放入低優先 執行佇列，而C（高）表示C工作將於第三天放入高優先執行佇列。此外， 執行每個工作所需完成的時間均於工作名稱下顯示，例如執行A工作需要 2天時間完成，而執行B工作需要1天時間完成。最後，各個工作的執行規 則為，當高優先執行佇列內有工作待完成時，須優先執行該佇列內的工作 （由第一個開始執行），直到高優先執行佇列內沒有任何待完成工作時， 方可執行低優先執行佇列內的工作（由第一個開始執行）。 自A至H每間隔一天的時間放入對應的高優先佇列或低優先佇列 H（低） G（高） F（高） E（低） D（高） C（高） B（低） A（低） 試計算執行此8個工作需要多少天方可完成。（10分） 試計算此8個工作自放入佇列至開始執行的平均等待時間。（15分）
某一物流公司有下圖所示的8個地點要運送，每條方向性連線及其數字代 表兩個地點的運送順序及運送成本。 試使用拓樸排序法，找出此8個地點的運送順序以及總共運送成本。（15分） 若將上圖的地點2與地點4之間以及地點6與地點7之間的連線方向顛 倒，則運用拓樸排序法後，此8個地點的運送順序以及總共運送成本 為何？（10分）
在電腦網路中，透過IP位址以查詢對應的裝置是常見的動作。今某電腦網 路有以下表格所示的IP位址以及對應裝置（假設每個IP位址有8個位元）， 當輸入某一IP位址以查詢對應的裝置時，最壞情況為此表格中的每個IP位 址的每個位元皆需要搜尋一次，以確認此輸入的IP位址是否有對應的裝 置。由於這樣的IP位址儲存方式，將造成查詢時的高複雜度（例如，若表 內有m個IP時，查詢的複雜度為m*8），因此運用適當的資料結構以減低查 詢複雜度，已成為電腦網路的重要課題。 IP位元0 IP位元1 IP位元2 IP位元3 IP位元4 IP位元5 IP位元6 IP位元7 裝置 A B C D E … … … … … … … … … 試建立並驗證一個樹狀資料結構，不僅可以儲存以上表格方式的IP位址以 及對應裝置資訊，並可使得查詢IP位址所對應的裝置的最壞情況複雜度維 持在常數8（也就是IP位址位元數）。（25分）
某一系統有下表所示的使用者帳號與密碼資料，今為了保密需要欲將使 用者密碼透過雜湊函數加以加密，並將雜湊後的密碼連同使用者帳號儲 存於一個2-3樹（2-3 tree）（依使用者帳號英文字母順序儲存），而雜湊函 數h(x) =密碼之英文及數字加總，其中英文a-z相當於1-26。 使用者帳號 使用者密碼 AA 234abc BB 123bcd CD aa012 AC 555be BD 45fdd CA 712ccc 試計算出雜湊後的密碼資料。（10分） 試建立此2-3樹，以儲存系統的使用者帳號與（雜湊後）密碼資料。（15分）