資訊處理 108 年程式語言概要考古題

下列為計算費波那契數列（Fibonacci numbers）的遞迴與非遞迴程式： 遞迴程式： def fib_r(n): if n == 0 or n == 1: return n else: return fib_r(n-1) + fib_r(n-2) 非遞迴程式： def fib_un(n): if n == 0 or n == 1: return n a = 0 b = 1 for i = 2 to n: temp = b b = a + b a = temp end return b ㈠ 試計算使用遞迴及非遞迴方式求費波那契數列的時間複雜度為何？ （9 分） ㈡試說明使用遞迴 及非遞迴方式對費波那契數列分別有何優點？（8 分） 又有何缺點？（8 分）

請說明在CPU、記憶體（memory）、快取記憶體（cache）之間資料傳遞 時發生寫入（write through）與寫回（write back）之下列問題： ㈠ 試述何謂寫入（write through）？（5 分） ㈡試述何謂寫回（ write back）？（5 分） ㈢試述寫入（ write through）與寫回（write back）分別有何優點、缺點？ （15 分）

有一程式碼如下，試問總共create 出幾個process？（25 分） for(i=0;i<3;i++) { if(fork()==0) { fork(); fork(); fork(); } }

請說明直譯式程式語言（Interpreted language）與編譯式程式語言（Compiled language）之下列問題： ㈠試說明何謂直譯式程式語言？ （10 分） ㈡試說明何謂編譯式程式語言？ 10 分） ㈢ Javascript、Python、C、Pascal、HTML、Java，上述六個程式語言，何 者為直譯式程式語言？（5 分）