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

很多電腦的應用程式都需要亂數產生器(random number generator)，例如打牌程式在 發牌時就需要使用到亂數。（20 分） 其中有一種方法，稱為假亂數產生器(pseudo-random number generator)，試解釋其 做法為何？ 另有一種稱為線性同餘產生器(linear congruential generator)，試解釋其做法為何？ 在解決一些計算問題上，我們常用蒙地卡羅法(Monte Carlo method)，試解釋此做 法為何？ 亂數也常被用在電腦模擬(computer simulation)上，試解釋此做法為何？

假設有一個具有n 個整數元素的陣列A[1..n], 這些整數元素的值均為1、2、3 或4， 一開始時並未排序。現在請你撰寫一段程式碼將所有n 個元素由小到大排序，並將 排序後的結果存回A 陣列中。注意：你的程式的執行時間必須為O(n)，但可利用額 外的陣列來協助處理。（20 分）

試解釋下列名詞：(20 分) 摩爾定律(Moore's Law) GPS(Global Positioning System) Intranet SET(Secure Electronic Transaction)

我們常用雜湊表(Hash table)或AVL 樹(AVL-tree) 來記錄大量的資料，這兩種資料結 構都可動態地增加資料。(20 分) 請你就這兩種資料結構，比較一下那一種較浪費空間。 請你就這兩種資料結構，比較一下那一種增加資料的動作其速度較快。 請你就這兩種資料結構，比較一下那一種它的程式比較容易撰寫。 如果要循序處理每一筆資料，請你就這兩種資料結構，比較一下那一種其循序處 理的速度比較快。

有關SRAM 和DRAM：(20 分) 請分別寫出兩者的英文全名。 請問那一種需要定期更新(refresh)？ 需要定期更新(refresh)的性質是否比較好？為什麼？ 請問那一種是屬於揮發性記憶體(volatile memory)？