CSIE 1A + 1B Midterm examination Open Books (但不可以互相借任何東東) 請依題號順序作答, 否則扣分 10% I. Convert the following decimal numbers into binary, octal, and hexadecimal: (a) 515 (b) 1030.75 (c) 1543.625 (d) 0.1 (e) 43.3 10% II.A certain computer represents floating point numbers by means of a signed magnitude fractional mantissa and an excess 16 base 4 exponent.(not base 2) The floationg point format is illustrated below. (12 bits) Exponent Mantissa 1 1 0 0 1 0 1 0 1 0 1 0 ^ --------- =========== | Sign (a) Assume there is no hidden bit. What is the decimal value of the number shown above? List your calculations. (b) Assume there is a hidden bit at the left of the decimal point of the mantissa. What is the decimal value of the number shown above? List your calculations. 10% III. What is the output of each of the following programs? (a) #include int love, hate; int fp ( int x){ int life=1; love++; hate= x+1; life += love+hate; x++; return life; } int f2 ( int x){ static int life=1; love++; hate= x+1; life += love+hate; x++; return life; } int main() { int life; love = hate = 1; life = fp(love); printf("%3d %3d %3d\n", life, love, hate); life = fp(hate); printf("%3d %3d %3d\n", life, love, hate); love = hate = 1; life = f2(love); printf("%3d %3d %3d\n", life, love, hate); life = f2(hate); printf("%3d %3d %3d\n", life, love, hate); return 0; } (b) /*** C program ***/ #include #define begin { #define end } #define call void myfun(void){ int m=1; static int n=1; printf(" %3d=m, n=%d\n",m,n); m++; n++; } int main() begin call myfun(); call myfun(); call myfun(); end 10% IV.Suppose that IEEE floating standard(IEEE 754/854) is used to represent single precision floating number. (Note that Exponent is excess 127) (a) What does "IEEE" stand for? (2%) (b) Convert the decimal number 12.3 into binary format. (3%) (c) Dipict the 32-bit patten for the decimal number 12.3 In addition to the binary representation, also give your answer in hexadecimal format. (5%) (就是寫出12.3在電腦內的 bit pattern, 用32個1跟0, 再用八位的16進位數) 20% V. Briefly answer the following questions: a) 正負整數用binary儲存可有sign-magnitude, one's complement, two's complement 以及 excess method等, 為什麼現代電腦大多採用 two's complement? b) 說明overflow 和 underflow, 並指出各發生於何種情況? c) 舉例說明parity 和 checksum 之觀念。 d) 仔細說明如何在tin 中一次同時將文章post於兩般計概討論群。 e) 如果 Error Correcting Code 要能在錯掉2bit時仍能自動更正, 則該 code 的 雌Hamming distance 須為多少? f) 課本上有關 truncation error 和 rounding error 之說明並不正確, 請說明 這兩種 error 之不同。 g) 法國數學家 Blaise Pascal 雖只活了39歲, 但因對以後發明電腦很有貢獻, 所以 電腦語言 Pascal 就是以他為名, 說出至少兩件他的貢獻。 h) IDF 是個戰機, 也是個頭字語(Acronym), 阿扁以前說它代表 I Don't Fly, 後來說是 I Don't Fight, 當上總統後改說是 I Do Fight ! 至少寫出頭字語 IBM 的三種意思。 i) 雖有爭議, 大多數人仍認為史上第一部電腦是1946/02/14發表於賓州大學的ENIAC, 寫出這頭字語的英文全名, 並說出帶領該計劃的兩位教授之英文名字。 j) 寫出以下與記憶體相關頭字語的英文全名: RAM, ROM, PROM, EPROM, EEPROM 10% VI. a) Given the following ECC(Error Correcting Code): Symbol Code Symbol Code A 000001 E 100111 B 001110 F 101000 C 010010 G 110100 D 011101 H 111011 Decode the following messages: (a) 001110 000010 110010 (2%) (b) 101110 000011 011101 110111 110101 111100 (3%) b) 現代電腦大多採用von Neumann 架構, 畫圖說明 von Neumann 架構。 (要說明電腦如何執行記憶體中的program) 。 10% VII. 用 C 語言寫出以下兩個函數, 各函數中都只能寫一個 statement。 a) 寫出函數 int and(int a, int b) 可傳回 a & b 之值, 但只能用 | 和 ~ 運算。 b) 寫出函數 int or(int a, int b) 可傳回 a | b 之值, 但只能用 & 和 ~ 運算。 (注意 &, |, 和 ~ 都是 bitwise 的運算) 10% VIII. 用 C 語言寫一函數 double mysin(double x) 傳回 sin(x)之值, 程式須用泰勒 展開式求解到誤差在 0.0000001 之內, 注意 x 是弳度量, 為讓其較快收斂, 程式中須先將 x 調整到 0 到 PI (3.14159265)之間。 10%IX. 使用上課教過的簡單組合語言寫一程式可將記憶體 66 中的值減去記憶體 67中的值 然後存入記憶體 68之中然後停掉。 (數值都是十六進位, 程式程式中也使用十六進位) (a) 先寫成組合語言 (b) 再手譯成機器碼 12% X. a) Consider the magic square we discussed in class meeting. If we are now on the cell of Row r and Column c, 用C語言的statement 表示要如何移到所謂的"左上角那一格", 要注意 wrap around 的問題(3%) b) Consider the game of Bull and Cow. Suppose that x an y are arrays of character consisting of 5 elements. (因字串結束有一 NULL char) Write a C function int ishit(char x[], char y[], int *na, int*nb) which will return 1 if na equales to 4, and return 0 otherwise. The values of na and nb are calculated in your function according to the following rules: na --- number of elements in x and y which have the same data and on the same position. (NULL 不算) nb --- number of elements in x and y which have the same data but on different position. (NULL 不算) For example, if x="1234" and y="1237" then na is 3 and nb is 0. If x="1734" and y="1237" then na is 2 and nb is 1. If x="8734" and y="8347" then na is 1 and nb is 3. Note: 寫出函數 ishit 即可, 不用寫主程式。 (9%) 12%XI. 假設 Fibonacci 的兔子問題中長成期改為需要2個月, 也就是說小兔子要兩個月才 長為成兔, 仍是每個月會生出一對兔子。 a) 假設一開始(第0個月)有一對剛出生的小兔子, 寫出其recursive公式,列出討論過程。 b) 用 C 語言寫出non-recursive function long myfib(int n); 注意n小於0時須傳回0 (寫成 recursive 沒有分數!) c) 寫一主程式可問user取得 n 值然後叫用myfib(n)算出再印出答案, 程式要能一直 讓 user 輸入一直到輸入 q 或 Q 或 quit 或 QUIT 才結束。 (10%)I. Conver the following decimal numbers into binary, octal, and hexadecimal: (a) 513 (b) 1234.5 (c) 1234.625 (d) 0.2 (e) 8.3 (10%)II.A certain computer represents floating point numbers by means of a signed magnitude fractional mantissa and an excess 16 base 4 exponent.(not base 2) The floationg point format is illustrated below. (12 bits) Exponent Mantissa 1 1 0 0 1 0 1 1 1 0 0 0 ^ --------- =========== | Sign (a) Assume there is no hidden bit. What is the decimal value of the number shown above? List your calculations. (b) Assume there is a hidden bit at the left of the decimal point of the mantissa. What is the decimal value of the number shown above? List your calculations. 10% III. What is the output of each of the following programs? (a) Program xx3a(Output); var K,L: integer; function P ( X : integer ) : integer; var L: integer; begin K := K+1; L := X+1; P := X + L; X := X+1 end; function Q (var X : integer ) : integer; begin (*note that "var X" means X uses same address as it's argument*) K := K+1; L := L+1; Q := X + L; X := X+1 end; Begin (*main*) K := 1; L := 1; writeln(P(K):3,K:3,L:3); writeln(P(L):3,K:3,L:3); writeln(Q(K):3,K:3,L:3); writeln(Q(L):3,K:3,L:3); End. (b) program xx3b; var k:integer; var x:string[10]; (* 這只有 Turbo Pascal 認得 *) begin x := 'Dcf Iktn'; for k:=1 to 8 do if(x[k]<> ' ')then x[k]:= chr( ord(x[k]) - 2 ); writeln('=',x,'='); end. 10% IV.Suppose that IEEE floating standard(IEEE 754/854) is used to represent single precision floating number. (Note that Exponent is excess 127) (a) What does "IEEE" stand for? (2%) (b) Convert the decimal number 12.3 into binary format. (3%) (c) Dipict the 32-bit patten for the decimal number 12.3 In addition to the binary representation, also give your answer in hexadecimal format. (5%) 10% V. Write a Pascal function toupper(x:char):char; which will return the upper case character of x. (若 x 不是小寫字母則傳回 x) Hint: 參考 III(b) 中使用 chr() 和 ord() ord('A') 是 65, ord('a') 是 97 5% VI. Given the following ECC(Error Correcting Code): Symbol Code Symbol Code A 000001 E 100111 B 001110 F 101000 C 010010 G 110100 D 011101 H 111011 Decode the following messages: (a) 000011 000110 000010 (2%) (b) 001110 000000 011111 111111 100111 100001 111101 (3%) (10%)VII.Suppose that X an Y are arrays of character consisting of 4 elements. (type myarray = array [1..4] of char; ) Write a Pascal function ishit(X,Y:myarray; var NA,NB:integer) which will return 1 if NA equales to 4, and return 0 otherwise. The values of NA and NB are calculated in your function according to the following rules: NA --- number of elements in X and Y which have the same data and on the same position. NB --- number of elements in X and Y which have the same data but on different position. For example, if X="1234" and Y="1237" then NA is 3 and NB is 0. If X="1734" and Y="1237" then NA is 2 and NB is 1. If X="8734" and Y="8347" then NA is 1 and NB is 3. Note: 寫出函數 ishit 即可, 不用寫主程式。 (10%)VIII.The function GCD(M,N) will return the greatest common divisor of any two integers(can be positive, 0, or negative) M and N. Write a nonrecursive Pascal function GCD(M,N:integer) using the method of "輾轉相減法"(不可使用乘法和減法) (15%)IX. 使用上課教過的 magic 語言寫一程式可讀入兩個正整數(不用考慮負數和0), 然後印出該二數的 GCD。 (15%)X. Consider the magic square of order N. (a) 3% Draw a magic square of order 9. (b) 4% If we are now on the cell of Row r and Column c, 用Pascal 的statement 表示要如何移到所謂的"左上角那一格", 要討論跟array 的宣告方式有何關係? 先假設宣告為 array [1..N] of integer, 再討論宣告為 array [0..N-1] of integer (c) 3% Draw a magic square of order 8. (d) 5% Draw a magic square of order 12. (20%)XI. Briefly answer the following questions or explain the term: (a) Von Neumann model (3%) (b) bit rate and baud rate (3%) (c) ADSL (3%) (d) critical region (3%) (e) deadlock (3%) 要寫出在哪些條件都成立才會發生deadlock (f) 寫出OS kernel 通常有的component 並略述其功能 (5%) 學號 ： ______________ 姓名： _____________ (10%)VIII.The function GCD(M,N) will return the greatest common divisor of any two integers(can be positive, 0, or negative) M and N. Write a nonrecursive Pascal function GCD(M,N:integer) using the method of "輾轉相減法"(不可使用乘法和除法) ( %)IX. 使用上課教過的 magic 語言寫一程式可讀入兩個正整數(不用考慮負數和0), 然後印出該二數的 GCD。 (這題原沒寫或寫錯的才寫, 這次寫對算10分)