資訊處理 98 年程式語言考古題

請回答下列的問題： 解釋什麼是強勢型態程式語言（strongly-typed programming language）和弱勢 型態程式語言（weakly-typed programming language）。（10 分） 列舉三個理由並舉例說明為何C 程式語言不是一個強勢型態程式語言。（10 分）

我們有下面的BNF 文法。（15 分） S ::= NP AS NP ::= NOUN PHRASES NOUN ::= “a man” | “a lady” | “a dog” | “a cat” PHRASES ::= | PROP NOUN PHRASES PROP ::= “with” | “for” | “by” AS ::= VERB NP | AS CONC AS VERB ::= “likes” | “owns” | “catches” CONC ::= “and” 請依據上述文法，畫出下面句子的derivation tree。 “a man with a cat likes a lady by a dog and owns a dog for a lady”

假設一個整數佔用四個位元組（4 bytes），考慮一個C 程式語言的整數陣列（integer array）int A[4][8][16]，此陣列的起始位址（starting address）為0X22F760，以十六 進位（hexadecimal）寫出下列四個printf 敘述句（statements）的輸出值（請寫出計 算過程）：（每小題5 分共20 分） printf("%X\n", &A[0][1][2]); printf("%X\n", &A[0][1][2]+1); printf("%X\n", &A[0][1]+2); printf("%X\n", &A[0]+3);

請問在第一題的BNF 文法，是不是ambiguous？（7 分） 請證明你的答案。（8 分）

下圖是一個執行時堆疊（run-time stack）中之啟動紀錄（activation record）的示意圖： Returned value Local variables Function parameters Dynamic link Static link Return address 說明如何使用啟動紀錄中的function parameters 實作下列兩種副程式的參數傳遞 （parameter passing）方法：call-by-value（或稱pass-by-value）和call-by-address （或稱pass-by-address, call-by-reference）。（10 分） 考慮下列的C 程式語言的程式片段，說明當主程式main 呼叫副程式foo 之後， 副程式foo 的啟動紀錄之function parameters 內容為何？並寫出主程式main 的輸 出值。（10 分） int c=5; void foo(int x, int* y) { int a=1, b=2; *y = a + b * x ; c = a + b + c; } int main (void) { int a=10, b=20; foo(b, &a); printf("%d, %d, %d\n", a, b, c); } 98 年公務人員高等考試三級考試試題 類 科： 資訊處理 全一張 （背面）

我們有下列C/C++語言程序。 int f(int n) { if (n = = 1 || n = = 2) return(1); else return(f(n 1)+f(n 2)); ­ ­ } 請描述這個程序在算什麼？（5 分） 請把這個程序的計算目的的遞迴方程式寫出來，並且把對任意引數n 的解，寫出來。 （5 分） 請問這個程序的計算時間複雜度是多少？（5 分） 請問根據你的描述，這個程序有什麼錯誤？（5 分）

考慮下列的BNF 法則： 〈conditional statement〉 ::= if 〈condition〉 then 〈statement〉 | if 〈condition〉 then 〈statement〉 else 〈statement〉 〈statement〉 ::= 〈assignment statement〉 | 〈conditional statement〉 假設C1 和C2 是由〈condition〉展開的程式碼，S1 和S2 是由〈statement〉展開 的程式碼，畫出〈conditional statement〉： if C1 then if C2 then S1 else S2 的語法樹（或稱剖析樹，parse tree），並解釋何謂「搖擺else 問題」（dangling else problem）。（10 分） 舉出兩個方法，解釋程式語言如何在設計、實作、或使用時解決「搖擺else 問 題」。（10 分）

假設我們可以在程式中宣告semaphore 變數，而且我們有下列兩個系統程序。 sem_wait(semaphore s) sem_signal(semaphore s) 請問什麼是semaphore 變數？（8 分） 請問這兩個程序的功能為何？（8 分） 請用spinlock 的技術，寫出上述兩個程序的內容。（9 分） 98 年公務人員、關務人員升官等考試試題 類 科： 資訊處理 全一張 （背面）

考慮C 程式語言的位元運算（bitwise operation），變數m 和陣列（array）n 的宣告 如下： unsigned int m; unsigned char n[4]; 假設m 的二進位值（binary value）為： b32b31b30b29b28b27b26b25b24b23b22b21b20b19b18b17b16b15b14b13b12b11b10b9b8b7b6b5b4b3b2b1 寫一個C 語言的程式將陣列n 的元素（element）設定為： n[0]: b31b32b29b30b27b28b25b26 n[1]: b23b24b21b22b19b20b17b18 n[2]: b15b16b13b14b11b12b9b10 n[3]: b7b8b5b6b3b4b1b2 即是將m 的二進位值，以每兩個位元一組，作位元調換（bit swap），再切割成四個 位元組。除了迴圈控制變數（loop control variable）外，程式中不可使用+, -, *, /, %的 算術運算（arithmetic operations）（可以宣告和使用其他變數）。（20 分）

假設我們有下列程式片段，有六個指令，有a, b, c, d, e, k 等六個變數。 1: b = a; // LSU 5 µs 2: b = b + 3; // ALU 10 µs 3: k = d; // LSU 5 µs 4: c = d + 5; // ALU 10 µs 5: e = c; // LSU 5 µs 6: a = b / k; // ALU 20 µs 假設這個程式，現在經過了compiler 的分析，要在一個single CPU 上執行。在指令 的左邊，我們寫上了指令的行號。指令的右邊，我們寫上了執行指令所需使用的硬 體元件與時間（以微秒µs 為單位）。ALU 代表所用的硬體元件是CPU 中唯一的算 術邏輯單元。LSU 代表所用的硬體元件是CPU 中唯一的存取單元。我們假設這個 CPU，可以容許LSU 與ALU 同時執行不同的指令。 請問這個程式片段，在in-order execution 時，需要花多少時間？（7 分） 請畫出上述程式片段的data-dependency graph。（6 分） 依照上述data-dependency graph，這個程式片段，在我們的single CPU 假設下， 做out-of-order execution 時，請問最短可以用多少時間完成？（6 分） 在的答案下，所需的out-of-order execution 是什麼？（6 分）