Midterm exam. 2010/11/08 13:35 - 15:15 共100分鐘 P.1/3 請注意指可以攜帶一張手寫 A4 memo, 不可互相借! 請依序作答寫於答案本! (I)0% 本題一定要寫, 否則扣 20分! 請用第一頁的上半頁作答! 最多只能寫半頁, 所以第(II)題請從第一頁的下半頁開始寫! (a)先用3分鐘大略看完考題, 預估這次你可以考幾分? (b)到昨天為止, 八週演習課你做完多少? 用百分比表示, 例如95%。 (c)用200字+/-80字寫出這門課從開學到現在的學習心得(學到哪些)? (II) 13% Regarding variables (本題請寫第一頁的下半頁) 　　 　4%(a)Consider the following C program: int x; static int y; int main( ) { int a=38; static int b; b = x + y + a; return b; } 請指出哪些變數是 Global 變數? x, y 哪些是 Local 變數? a, b 哪些是Auto變數? a 哪些是 static Local變數? b 　3%(b)Auto variables 會被安排在記憶體的何處? ==> 在堆疊區 　　　何以 Auto variable 若是 array 則它的 size 不可以太大? ====> 因為一般安排給堆疊區的記憶體很小, 幾 k 到幾十 k, 所以 auto 變數 array 若太大會爆掉! 　3%(c)What is the purpose of static Global variable? Explain it with example. ===> static Global 變數只有在同檔案 (file)內的 functions 才可以使用它! 具有類似 information hiding 的概念! 　3%(d)已知 x, y, k 都是 short 變數, 令 y = -x; 結果 y 與 x 相等, 　　　已知 x 不是 0, 請問 x 是多少? ==> x 是 -32768 若令 k = x+x; 則 k 是多少? ==> 0 因為就是 -32768 + (-32768) = (100...000)bin + (100...000)bin = 0 ==>說明: -32768 是除了 sign bit 是 1, 其他 bit 都是 0 　　　　(*考慮電腦使用二的補數表示法 2's complement) (III)12% Basic Computer Concept. (任選 4子題, 每子題 3分。 多選沒有分!) 　(a) What is Y2k38 problem? Explain why we might have Y2k38 problem. 　(b) Explain Overflow and Floating undeflow with examples. 　(c) Compare auto variable vs. static local variable. 　(d) What are the differences between compiler and interpreter? 　(e) List, in the order of being used, all the system programs you used 　　to generate an executable program.(從寫出程式到生出執行檔會用到的程式) 　(f) Explain "Big Endian" and "Little Endian" with an example of short int. 　(g) What is the strategy to win the BATNUM game? (寫出贏的策略) (IV) 10% Briefly answer the following questions. 　2%(a)類似 ROC, ECFA 這種都是頭字語, 寫出"頭字語"這單字的英文。 　3%(b)寫出三個與電腦有關的頭字語, 並寫出其意義與英文全稱。 　5%(c)變異數的定義是把每個data減去平均後的差值平方, 加起來後再除以 data總數 n, 　　可是這樣須先算出平均, 如果想要只記住 n, 平方和 以及 和(sum), 就可算出變異數, 　　那就要把公式轉換成不含有平均這項目, 以便用一個 Loop的程式就可同時算出平均值 　　與變異數。請逐步推導出這個公式。 (V) 20% Regarding the rand( ) and srand( ) 　6%(a)為何說電腦語言提供的亂數是亂假的?(2%) 如何做可以做出真的亂?(2%) 　　　　關於亂數的 PRNG 也是個頭字語, 寫出其英文全稱。(2%) 　3%(b)寫出一個 C 的 assignment statement 使變數 ans 可得到 5 到 31 之間 　　　　的一個整數(含 5 和 31)。當然啦, 你可以使用 rand( ) 這函數。 　3%(c)利用 rand( ), 寫一個 double drand( ); 可以傳回 [0, 1) 　　　　的 double 實數, 就是最小 0 (含), 最大不超過 1 (不會等於 1) 　3%(d)rand( )是uniform distribution,請寫出一個 double stdNormalRand( ); 　　　　可以傳回符合標準常態分配 N(0, 1) 的亂數。 　3%(e)利用stdNormalRand()寫一個 double myNRand(double avg, double std); 　　　可以傳回符合平均為 avg, 標準差 std 的常態分配之亂數。 　2%(f)假設考試分數是常態分配平均75, 標準差 7, 請問大約多少百分比落在[61,89]? 　　　又大約有多少百分比的人落在[54,96] ? 　 Midterm exam. 2010/11/08 13:35 - 15:15 共100分鐘 P.2/3 (VI) 13% Regarding the homework of ID Checker / Generator 　3%(a)寫出身份證驗證程式中把字母轉為 10 到 35 的整數之函數int a2nn(int a), 　　　　程式越短越好, 請注意傳入的 a可以是大寫也可以是小寫, 若非字母則回傳 0. 　　　　注意 A 是 10, I 是 34, O 是 35, 以及VWXYZ分別對應到29,32,30,31,33. 　5%(b)利用 (a) 的 a2nn(int), 寫出可以計算 checksum 的 int findCheckSum(char*); 　　　以便 ans = findCheckSum("a123456789"); 可以得到 9; 以及 ans = findCheckSum("A12345679"); 可以得到 8; (注意 ans 是 int) 　　　為了簡單, 程式可使用 strlen(char*), 且不必考慮傳入字串長度是否合理! 　5%(c)若用 fgets 讀入字串到 char buf[999] 則 buf 的尾巴可能會有 '\n', 　　　請寫一個函數 void chop(char s[ ]) 可把字串 s 尾巴的 '\n' 去掉(若有)。 　　　(Hint: 可以不使用指標, 也可以使用指標; 先找到字串結束處, 倒回一個char, 　　　　　然後 check 看是否為 '\n', 若是則把它改為字串結束符號) 　 (VII)15% Briefly answer and explain the following questions. 注意, 必須解釋你的答案, 否則分數減半 !!! 　4%(a) Give the output of the following program and explain your answer. #include #define NLOOP 8000 double x = 1234567.2, delta= 0.0001; int main(){ float y = x; int i; printf("Before add, x=%13.4f, y=%13.4f\n", x, y); for(i=1; i<= NLOOP; i++) x += delta; for(i=1; i<= NLOOP; i++) y += delta; printf(" After add, x=%13.4f, y=%13.4f\n", x, y); } 　4%(b) Give the output of the following program and discuss your answer. 　　(注意此題必須討論在不同 compiler 之下何以可能會有不同答案!) #include int y=0; /* global variable*/ int haha(){ int x = 0; ++y; return (x++); } int hehe(){ static int x = 0; y++; return (++x); } int main(){ printf("a=%d %d %d\n", haha() , haha() , haha() ); printf("b=%d %d %d\n", hehe() , hehe() , hehe() ); printf("y=%d\n", y); } 　4%(c) Give the output of the following program. (不必解釋) #include int main( ) { short i, k = 32765; printf(" Size of a short k = %d\n", sizeof k); for( i=1; i <=5; ++i) { ++k; printf("k = %hd = %hu = %d\n", k, k, k); } k = 3; /// for( i=1; i <=5; ++i) { --k; printf("k = %hd = %hu = %d\n", k, k, k); } return 0; } 　3%(d) Give the output of the following program. (不必解釋) #include int main( ) { short a=4938, b =258; printf("a=%hd, b=%hd\n", a, b); a = a ^ b; b = a ^ b; a = a ^ b; printf("a=%hd, b=%hd\n", a, b); return 0; } Midterm exam. 2010/11/08 13:35 - 15:15 共100分鐘 P.3/3 (VIII)13% Regarding the homework of Calendar 　(a)2% 中華民國01/01/01是西元 1912/01/01, 請問前一天在中國的西元是哪一天? 　(b)3% 說明何以在 Unix 系統的月曆程式 cal 印出的 1752年九月只有19天? 寫出原因並寫出少掉哪 11 天。 　(c)3% 考慮英美的西元萬年曆, 寫出可判斷閏年的函數 int isLeap(year); 若 year 是閏年則回傳 1, 否則回傳 0. 　(d)5% 程式庫有個字串串接函數 char* strcat(char t[ ], char s[ ]); 它會把 字串 s 接到 字串 t 的尾巴, 並回傳原先 t 的起始位址。 不可使用到指標變數, 寫出此函數 char* strcat(char t[ ], char s[ ]); (IX)16% 簡易程式題, 任選 4子題, 每子題 4 分, 注意多選不給分! 　(a) 可用任何運算, 寫一個recursive function(函數) long gcd(long m, long n); 　　　可以算出 m 和 n 的 GCD (最大公約數), 不要寫主程式。 　(b) 同 (a), 但不可使用 recursive 的 function, 就是用 Loop 寫法! 　(c) 這子題不必寫程式, 請寫出八階魔方陣的前三列與最後三列。 　(d) 算四的倍數階之魔方陣時要判斷是否在所謂的對角線上, 寫出該判斷函數 　　　int isOnDiag(int row, int col); 假設 row和 col 都是由 0 算起。 　(e) 寫出不會當掉的函數 double getDouble( ); 可從鍵盤讀入一個實數, 　　　只考慮一列只輸入一個實數, 此函數不可使用 scanf 與 sscanf 函數。 　　　注意使用時是這樣用: double ans; printf("Give me a 實數: "); ans = getDouble( ); 　(f) 畫圖說明程式在跑時, 呼叫 function 以及返回時, 記憶體之分佈和變化情形。 包括 Stack 區, Heap 區, 參數之推入與移出, (假設函數需要兩個參數x, y)。 (X) 13% 關於 Fibonacci 的 Rabbit problem. 　(a)3% 寫出原來問題的 Recursive 公式. 　(b)4% 假設原來問題改為: 第 0 個月有 1 對小兔子, 小兔子隔一個月會長大為成兔, 　　　每對成兔則要到下下個月才會生出一對(即懷孕期從一個月改為兩個月); 　　　請推導出算某月兔子有幾對的 recursive 公式 (要推導, 直接寫出則分數減半) 　(c)3% 寫出 recursive 函數 long fibNew(int n); 可以依據(b)傳回第 n 個月的 　　　兔子有幾對的答案。 　(d)3% 同 (c), 但使用 Loop, 不可以使用 recursion, 也不可用 array. ~ ~ ~ END ~ ~ ~