電子工程 111 年計算機概論考古題
題目為考試當年公告版本，實務標準請以現行規範為準。
㈠你只能利用基本的三種邏輯閘AND、OR、NOT，設計出一個1-bit 的 比較器（comparator）線路，這個比較器有兩個1-bit 的輸入a 與b，一 個輸出c，當a>b 時，輸出c 的值為1，否則輸出c 的值為0。（10 分） ㈡在電腦的數字系統中，假設使用4-bit 的二補數（2’s complement）方 式來儲存整數，則計算1+7 之後的結果是多少？請詳述你的計算過程， 並解釋你的理由。（10 分）
Scheme 是一種函式程式語言（functional programming language），其中定 義了一個函式如下： (define (mystery input-list) (cond ((null？ input-list) 0) (else ( + 1 (mystery (cdr input-list)))))) ㈠執行下列函式的呼叫，結果為何？（5 分） (mystery (list 4 5 6)) ㈡解釋這個mystery 函式，在計算什麼？（5 分） ㈢用Scheme 語法，定義出一個函式factorial n，這個函式要算出n!。（10 分）
㈠電腦的作業系統使用虛擬記憶體來管理記憶體，假設每個分頁（page） 大小為4 KB，總共有邏輯位址（logical address）空間共256 分頁，而 此電腦的實體記憶體總共只有64 框（frame）。則此電腦的邏輯位址、 實體位址（physical address）分別是多少bits？（10 分） ㈡假設使用只有三個分頁框（frame）的需求分頁法（demand paging）機 制，且使用LRU（Least Recently Used）取代演算法，則下列分頁參考 （page reference）的順序7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1 會導致多少次的分頁錯誤（page fault），詳述說明整個過程。假設一開 始的分頁表（page table）內容是空的。（10 分）
㈠一個無階級（classless）IP 位址為167.188.170.83/27，它所屬的子網域 （subnet）範圍為多少？（10 分） ㈡在一個區域網路內，多個使用者共用同一個通道（channel），使用下列 那些媒介存取控制（Medium Access Control）協定，會讓當使用者站 台數目很多時，因為通道碰撞（collision）嚴重，而使得系統的吞吐量 驟降，甚至癱瘓掉？解釋原因。（10 分） ⑴ALOHA ⑵CSMA/CD ⑶CSMA/CA ⑷TDMA
㈠下列式子是用後序（postfix）表示式，計算出它的答案。（5 分） 2 3 4 + * 5 + ㈡假設一個二元樹的走訪（binary tree traversal），用後序走訪（postorder） 得到的是HGDBFECA，用中序走訪（inorder）的結果是HDGBACFE， 畫出這個二元樹。（15 分）