104年 - 104 專技高考_電子工程技師：電子計算機原理#41860

科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論) | 年份：104年 | 選擇題數：0 | 申論題數：12

試卷資訊

所屬科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)

選擇題 (0)

申論題 (12)

⑴任何使用比較運算（comparison）的排序演算法，當其輸入的資料項目的數目為 n 時，最少需要多少個比較運算方能完成？請使用時間複雜度表示之，並說明其理由。（10 分）

⑵就您所知，有無現存的排序演算法，其最壞情況之時間複雜度可以達到上述之下限（lower bound）？若有，請舉一例說明之；若無，請說明理由。（10 分）

⑴定義二元搜尋樹（binary search tree，BST）。（5 分）

⑵使用下列八個資料，建構一棵二元搜尋樹：（5 分） 56，30，25，42，78，89，63，12

⑶可否使用建構 BST 的方法完成資料的排序？若可，請說明其方法，並估計其計算複雜度（computational complexity）；若否，請說明其理由。（10 分）

⑴何謂獨立程序（independent process）與協力程序（cooperating process）？（5 分）

⑵何謂 IPC（interprocess communication）？（5 分）

⑶ IPC 有那兩種基本模型（model）？請說明之。（10 分）

⑴何謂多層次包含（multilevel inclusion）與子集性質（subset property）？（10 分）

⑵假設 L2 的區段大小（block size）為 L1 的四倍。說明當一個快取失誤（miss）造成的 L1 與 L2 置換（replacement）時，可能導致多層次包含性質不成立的理由。（10 分）

⑴何謂程序的關鍵部分（critical section）？（5 分）

⑵解決程序的關鍵部分之問題時，必須滿足那三個重要條件？（15 分）