電子工程 104 年電子計算機原理考古題

任何使用比較運算（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 cache）架構，以提升系 統之性能。請回答下列問題： 何謂多層次包含（multilevel inclusion）與子集性質（subset property）？（10 分） 假設L2 的區段大小（block size）為L1 的四倍。說明當一個快取失誤（miss）造 成的L1 與L2 置換（replacement）時，可能導致多層次包含性質不成立的理由。 （10 分）

何謂程序的關鍵部分（critical section）？（5 分） 解決程序的關鍵部分之問題時，必須滿足那三個重要條件？（15 分）