加載中. ..
PDF
112年公務人員高等考試三級考試試題
類 科
：
資訊處理
科 目
：
資料結構
考試時間
：
2
小
時
座號
：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
37650
頁次：
2
－
1
一、某一公司有下圖所示的8個優先順序分別為高或低的待執行工作，且將依
順序自A至H每間隔一天的時間放入對應的高優先執行佇列（Queue）或低
優先執行佇列（Queue），例如A（低）表示A工作將於第一天放入低優先
執行佇列，而C（高）表示C工作將於第三天放入高優先執行佇列。此外，
執行每個工作所需完成的時間均於工作名稱下顯示，例如執行A工作需要
2天時間完成，而執行B工作需要1天時間完成。最後，各個工作的執行規
則為，當高優先執行佇列內有工作待完成時，須優先執行該佇列內的工作
（由第一個開始執行），直到高優先執行佇列內沒有任何待完成工作時，
方可執行低優先執行佇列內的工作（由第一個開始執行）。
自A至H每間隔一天的時間放入對應的高優先佇列或低優先佇列
H（低） G（高） F（高） E（低） D（高） C（高） B（低） A（低）
1 2 1 1 2 2 1 2
試計算執行此8個工作需要多少天方可完成。（10分）
試計算此8個工作自放入佇列至開始執行的平均等待時間。（15分）
二、某一物流公司有下圖所示的8個地點要運送，每條方向性連線及其數字代
表兩個地點的運送順序及運送成本。
試使用拓樸排序法，找出此8個地點的運送順序以及總共運送成本。（15分）
若將上圖的地點2與地點4之間以及地點6與地點7之間的連線方向顛
倒，則運用拓樸排序法後，此8個地點的運送順序以及總共運送成本
為何？（10分）
代號：
37650
頁次：
2
－
2
三、在電腦網路中，透過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裝置
0 0 1 1 1 1 0 0 A
0 0 1 1 0 0 1 1 B
1 1 0 0 0 0 1 1 C
1 1 0 0 1 1 0 0 D
1 1 0 1 1 1 0 0 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分）