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

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

請解釋下列名詞：（20 分） Time-sharing Deadlock Handshaking Direct Memory Access

考慮下面的虛擬程式（pseudocode）： if (A < B) and (A < 0) then C := 1 else if B > 2 then C := 2 else if A > 3 then C := 3 else C := 4 A 與B 的數值要滿足什麼條件，才會使C 的值為4？請用兩個不同形式（forms） 來表示此條件，第一個用到邏輯的否定“not＂，第二個則不用“not＂。（20 分）

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

請用任一高階語言設計一個程式計算一串數字的中間值。（10 分）

有人將快閃記憶體（flash memory）做成的儲存裝置稱為隨身碟、大姆哥，請就製 造技術、儲存資料原理等方面比較它與硬碟機不同之處。（20 分）

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

請簡要說明OSI 七層網路架構 (seven layers of OSI reference model)。（10 分）

在一個完全二元樹（complete binary tree）中，若任一個節點（node）上的值都不比 其父節點（parent node）上的值小，則稱該二元樹為堆積（heap）。你要將數值以 堆積的結構儲存，且每輸入一個新數值後，都要能儘快形成堆積。要循序輸入七個 數值6,8,3,2,9,4,5。請畫出每輸入一個數值後，所形成的堆積。你的答案為七個堆 積。（20 分）

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

請設計一個適用於8 位元資料組(8-bit data word) 的SEC 碼(single error correction code)。 若假設有一8 位元資料組為00111001，請證明此一SEC 碼可更正第3 個資 料位元(0)所發生的錯誤。（20 分）

針對含有n 個元素（elements）且已排序（sorted）的陣列（array），做n 次二元搜 尋（binary search）的時間複雜度是多少？做n 次線性搜尋（linear search）的時間 複雜度是多少？請分別簡略說明搜尋過程及如何得到時間複雜度。在什麼情況，你 會使用上述兩種搜尋方式中時間複雜度較差者而捨棄時間複雜度較佳者？（20 分）

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

請分別以選擇式排序法(selection sort)及插入式排序法(insertion sort)，對下列資料進行 由小到大的排序，請詳細列出運算過程及最後結果。（20 分） 14, 8, 32, 10, 15, 6, 7,25 六、請將下列各式轉成相對應的前置表示法(prefix notation)及後置表示法(postfix notation)。其中^表指數運算。（20 分） (A+B)*(C-D)^E*F A+(((B-C)*(D-E)+F)/G)^(H-J)

有5000 個節點（nodes）的完全二元樹（complete binary tree）用陣列A 的5000 個 元素（elements）A[1], A[2],…, A[5000]來儲存，且以A[1]代表根（root），則 A[3001]之父節點（parent node）為何？A[3001]有無子節點（child node）？若有， 是那一個？（20 分）