google選擇題摘選

發信人: pengjun (這個世界規則太多), 信區: CPlusPlus
標 題: google選擇題摘選
發信站: 天大求實BBS (Wed Oct 25 13:28:20 2006), 本站()

1.6
下列哪個排序演算法的最差時間代價不是O(n^2)?[ ]
A 插入排序
B 歸併排序
C 快速排序
D 氣泡排序

1.8
以下語法制導的翻譯器可以將一種以a，b，c，d為終結符的語言翻譯為另一種以
1，2，3，4，5，6為終結符的語言。翻譯器使用的自底想上的移進（shift）/歸約
（reduce）分析器在發生歸約後會執行下列文法規則後的大括號中的動作。
S->AS{print"1"}
A->AB{print"2"}
A->a {print"3"}
B->bC{print"4"}
B->dB{print"5"}
C->c {print"6"}
那麼輸入串"aaaddbc"會被翻譯成為[]
A 333552
B 3336455211
C 3645552
D 3334555211
E 3336455521