電子工程 104 年電子計算機原理考古題（共 5 題）
資料來源：考選部歷屆試題｜法律人 LawPlayer 整理
https://lawplayer.com/exam/electronic-engineering/104-%E9%9B%BB%E5%AD%90%E8%A8%88%E7%AE%97%E6%A9%9F%E5%8E%9F%E7%90%86

第 1 題
㈠任何使用比較運算（comparison）的排序演算法，當其輸入的資料項目的數目為n
時，最少需要多少個比較運算方能完成？請使用時間複雜度表示之，並說明其理
由。（10 分）
㈡就您所知，有無現存的排序演算法，其最壞情況之時間複雜度可以達到上述之下
限（lower bound）？若有，請舉一例說明之；若無，請說明理由。（10 分）

第 2 題
㈠定義二元搜尋樹（binary search tree，BST）。（5 分）
㈡使用下列八個資料，建構一棵二元搜尋樹：（5 分）
56，30，25，42，78，89，63，12
㈢可否使用建構BST 的方法完成資料的排序？若可，請說明其方法，並估計其計算
複雜度（computational complexity）；若否，請說明其理由。（10 分）

第 3 題
㈠何謂獨立程序（independent process）與協力程序（cooperating process）？（5 分）
㈡何謂IPC（interprocess communication）？（5 分）
㈢IPC 有那兩種基本模型（model）？請說明之。（10 分）

第 4 題
所有的多處理器系統均使用多層次快取記憶器（multilevel cache）架構，以提升系
統之性能。請回答下列問題：
㈠何謂多層次包含（multilevel inclusion）與子集性質（subset property）？（10 分）
㈡假設L2 的區段大小（block size）為L1 的四倍。說明當一個快取失誤（miss）造
成的L1 與L2 置換（replacement）時，可能導致多層次包含性質不成立的理由。
（10 分）

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

題目為考試當年公告版本，實務標準請以現行規範為準。