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

計算機中的記憶體系統往往被設計成階層式的。（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 分）

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

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

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

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

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

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

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