電力工程 97 年計算機概論考古題

將下列整數以二進位、8-bit 的方式表示，表示法包括：符號與大小 1 的補數 2 的補數 Excess 3 （24 分） ㈠10 ㈡-99 ㈢-100

CPU 執行放在記憶體內程式指令的一個循環稱為指令週期，請詳述一個指令週期有 那些步驟？（16 分）

依序加入下列整數資料到一棵空的二元搜尋樹（binary search tree）： 18,31,15,17,20,40,16,8 請畫出最後結果之二元搜尋樹。（20 分）

在虛擬記憶體管理中，分頁式記憶體管理（paged memory management）是作業系統 常用的技術。假設main memory 的存取時間是80ns，associated memory 的存取時間 是2ns。（20 分） ㈠為何page size 總是2 的冪次方？ ㈡假設沒有發生page fault，CPU 在下列情況下執行一次存取指令（或資料）的時 間分別是？ page table 是放在main memory。 page table 是放在associated memory，hit-rate 為80%。

電腦的軟、硬體架構在運作時，何謂時間局部性（temporal locality）與空間局部性 （spatial locality）？（20 分）

本題考慮常見的兩種搜尋法：循序搜尋法（Sequential Search）及二元搜尋法（Binary Search）。 ㈠請以虛擬碼（Pseudo Code）分別描述這兩種搜尋法的演算法。（20 分） ㈡比較兩搜尋法的優缺點。（5 分） ㈢以陣列（Array）或串列（Linked List）這兩種資料結構而言，何者較為適合二元 搜尋法？請說明之。（5 分）

請說明以下之名詞： ㈠網際網路（Internet）（5 分） ㈡全球資訊網路（World Wide Web）（5 分）