98年 - 98 公務升官等考試_薦任_資訊處理：程式語言#34333

科目：程式語言 | 年份：98年 | 選擇題數：0 | 申論題數：14

試卷資訊

所屬科目：程式語言

選擇題 (0)

申論題 (14)

一、我們有下面的 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”
⑴請問在第一題的 BNF 文法，是不是 ambiguous？（7 分）
⑵請證明你的答案。（8 分）

⑴請描述這個程序在算什麼？（5 分）
⑵請把這個程序的計算目的的遞迴方程式寫出來，並且把對任意引數n 的解，寫出來。 （5 分）
⑶請問這個程序的計算時間複雜度是多少？（5 分）
⑷請問根據你的描述，這個程序有什麼錯誤？（5 分）
⑴請問什麼是 semaphore 變數？（8 分）
⑵請問這兩個程序的功能為何？（8 分）
⑶請用 spinlock 的技術，寫出上述兩個程序的內容。（9 分）

⑴請問這個程式片段，在 in-order execution 時，需要花多少時間？（7 分）
⑵請畫出上述程式片段的 data-dependency graph。（6 分）
⑶依照上述 data-dependency graph，這個程式片段，在我們的 single CPU 假設下， 做 out-of-order execution 時，請問最短可以用多少時間完成？（6 分）
⑷在⑶的答案下，所需的 out-of-order execution 是什麼？（6 分）