電子工程 94 年計算機概論考古題

計算機中的記憶體系統往往被設計成階層式的。（20 分） 如此設計的目的為何？ 該設計利用到的原理為何？試詳述之。 一般而言包含哪些階層？各階層所要達到的效果及特色為何？

二的補數法（2’s complement）中，12bits 所能表示的數值範圍在哪裡？二的補數法 （2’s complement）中，十進位的整數-1 與1 之12bits 的表示值為何？請詳細說明得 到答案的計算過程。（20 分）

證明下列式子：（⊕ 代表 Exclusive-OR，+ 代表 OR。每小題5 分，共15 分）  x' ⊕ y = x ⊕ y' = (x ⊕ y) ' = xy + x'y'  x ⊕ 1 = x' 與 x ⊕ 0 = x  if xy = 0 then x ⊕ y = x + y

試解釋以下程式的功用，並指出其輸出的結果：（10 分） Void main(void){ int fun(int n); printf(“%d\n\n”,fun(10)); } int fun(int n){ if(n <= 1) return (n); else return n * fun(n-1); } 一陣列A[n,m]儲存了五列*六行個32 位元的元素。假設記憶體為byte addressable ，且A[1,1]位於位址1000H, 請問元素A[4, 5]的位址為何？（假設該系統使用 row-major 的陣列儲存方式。）（10 分）

追蹤（traverse）樹上的節點，就是拜訪每個節點一次，其追蹤的結果就是拜訪節點 的順序。以A＊B＋C 為例，圖示說明此式子如何儲存在二元樹？並列出其前序追 蹤（Preorder traversal）與後序追蹤（Postorder traversal）的結果。（20 分）

說明電腦網路通訊協定的OSI 七層架構，並以寫信寄信的例子說明這七層的作用。 （20 分）

試將下列數字依序建立一binary search tree：（10 分） 6, 5, 9, 0, 8, 3, 2, 7, 1, 4。 在一n 個節點的binary search tree 中，搜尋一個元素的時間複雜度，其最糟情況 為何？並說明該情況發生的條件。（5 分） 同上(二)，其平均情況為何？（5 分）

作業系統中程序管理的主要管理任務有哪些？請具體說明至少三種功能任務。程序（process） 與引線（thread）皆為CPU 的控制單元，請問其差別在哪裡？（20 分）

將 ((A + B) * C – (D – E)) $ (F + G) 轉換成前序與後序。（20 分）

試將以下中序表示式轉換為後序表示式以及前序表示式：（8 分） A*(B+C－D/E)+F 請問中序、前序、後序三種表示法，何者最適於電腦系統之運算？並說明其原因。 （6 分） 該三種表示法何者次適於電腦系統之運算？並說明其原因。（6 分）

請問一張1280 × 1024 的256 色圖檔，在不壓縮及不包含額外資訊的情況下，需要 多少Bytes 的儲存空間？若欲擷取取樣頻率為96 赫次，取樣大小為16 位元的1 分 鐘音樂CD，需要多少Bytes 的儲存空間？（20 分）

現在個人電腦至少配備有兩層的快取記憶體（Cache Memory），分別是Level 1 快 取記憶體與Level 2 快取記憶體兩種，說明此兩快取記憶體的功能。（15 分）

在計算機系統中，有所謂的” stored-program”的概念。（20 分） 試述此觀念的內容為何？ 試述此觀念的主要原因、目的、以及優點為何？

說明下列名詞之功能與特色：（20 分，每小題4 分） Random Access Memory Degree of Multiprogramming B-to-C E-Commerce 802.11b Interrupt driven

舉出下列函數的遞迴定義：（10 分） N! Fibonacci Sequence 六、有下列整數：（20 分） 45, 83, 7, 61, 12, 99, 44,77, 14, 29 找出對應的二元樹（binary tree） 找出這二元樹的錐形樹（heap tree）