Google公司預選筆試試題
面試筆試2.62W
發信人: whqnju (男兒何不帶吳鈎,收取關山五十州 ), 信區: Algorithm. 本篇人氣: 1401
標 題: Google公司預選筆試試題
發信站: 南京大學小百合站 (Sat May 12 18:00:07 2007)
大家有興趣看看吧,5/10 sjtu的考卷。
選擇題3、8我蒙的,大牛給解答一下。
1.單項選擇題
1. 下面一段代碼的輸出是[ ]
void fn( int* b){
(*b)++;
}
int main(){
int a=7;
fn(&a);
cout }
A.0 B.7 C.8 fined
2. 定義int i,j,*p=&i; 那麼下面哪條語句可以完成i=j的賦值[ ]
A.i=*p; B. *p=*&j; C.i=&j; D.I=**p;
3. 用二叉搜索樹和哈希表存儲相同的數據集,對於以下何種操作,二叉搜索樹比哈希表
速度更快?[ ]
A.檢索 B. 插入 C.刪除 D.更新 E.排序
4. 包含N個幾點和M條邊的有向帶權圖G, 邊的權為正, 以下操作中不可以在O(N+M)
的時間複雜度內完成的操作是:[ ]
A. 求結點s到結點t之間的最短距離
B. 求距離結點s最近的結點
C. 已知起始結點, 對圖G中的結點進行拓撲排序
D. 求圖G的最大強連通子圖
5. 有如下遞歸函數f(n),其時間複雜度為[ ]
int f(int n){
if(n==0)
return 0;
if(n==1)
return 1;
return ( 5*f(n-1) - 6*f(n-2));
}
A.O(n) B. O(n^2) C. O(n^3) D. O(2^n)
6. 下面所述步驟中,哪一個不是創建經常所必需有的[ ]
A.由調度程序為進程分配CPU B.建立一個進程控制塊
C.為進程分配內存 D.將進程控制塊鏈入就緒隊列
7. 在多進程的系統中,為了保證公區變量的完整性,各進程應互斥進入臨界區。所謂臨
界區是[ ]
A.一個緩衝區 B.一個數據區 C.一個同步機構 D.一段程序
8. 能產生滿足如下條件語言的正則表達式是:1.每一個a後至少緊跟兩個c; 2.每一個b
後至少緊跟一個c [ ]
A.(acc|bc|c)* B.(acc|bc)* C.(ac|bc)* D.不是正則語言
9. 以下哪項不是RPC(遠程過程調用)的特點[ ]
A.速度快 B.降低系統耦合度 C.可以實現異構系統間的協作
10. 有三個桶,容量分別是3升,5升,7升,你只能進行下面的操作:
把一個桶中所有的水倒掉;
把一個桶A中的水倒入桶B,直到桶A空了或者桶B滿了;
假設一開始容量為3升和5升的桶是滿的,7升的桶是空的,希望通過一系列操作使3個桶
中任意一箇中正好有4升水,那麼至少需要[ ]次操作。
A.3 B.5 C.7 D.不可能
2. 程序設計與算法
2.1 實現如下編碼算法,對於重複2-9次數的字符,用兩個數字表示,即NX(其中N為重
復的次數,X為重複的字符,下同),超過九個則先輸出9X,然後處理剩下的字符。對於
連續的不重複的字符,則兩邊加1來封字符串。如果被封的字符串其中有數字為1,則用1
來轉義。 示例: AAAAAABCCCC -> 6A1B14C, 12344 -> 11123124。。。(下面的框
架是用C++語言寫的。你可以用你熟悉的語言。)
void encode (const char* text, char* dest)
text 為需要編碼的字符串,dest表示編碼輸出的目標空間,而空間足夠大
2.2給定一顆有n個結點的二叉樹。求它的所有結點數為m的連通子圖數目。m<=n分析你的
算法的時間複雜度,解釋算法即可,不必寫代碼。
標 題: Google公司預選筆試試題
發信站: 南京大學小百合站 (Sat May 12 18:00:07 2007)
大家有興趣看看吧,5/10 sjtu的考卷。
選擇題3、8我蒙的,大牛給解答一下。
1.單項選擇題
1. 下面一段代碼的輸出是[ ]
void fn( int* b){
(*b)++;
}
int main(){
int a=7;
fn(&a);
cout
A.0 B.7 C.8 fined
2. 定義int i,j,*p=&i; 那麼下面哪條語句可以完成i=j的賦值[ ]
A.i=*p; B. *p=*&j; C.i=&j; D.I=**p;
3. 用二叉搜索樹和哈希表存儲相同的數據集,對於以下何種操作,二叉搜索樹比哈希表
速度更快?[ ]
A.檢索 B. 插入 C.刪除 D.更新 E.排序
4. 包含N個幾點和M條邊的有向帶權圖G, 邊的權為正, 以下操作中不可以在O(N+M)
的時間複雜度內完成的操作是:[ ]
A. 求結點s到結點t之間的最短距離
B. 求距離結點s最近的結點
C. 已知起始結點, 對圖G中的結點進行拓撲排序
D. 求圖G的最大強連通子圖
5. 有如下遞歸函數f(n),其時間複雜度為[ ]
int f(int n){
if(n==0)
return 0;
if(n==1)
return 1;
return ( 5*f(n-1) - 6*f(n-2));
}
A.O(n) B. O(n^2) C. O(n^3) D. O(2^n)
6. 下面所述步驟中,哪一個不是創建經常所必需有的[ ]
A.由調度程序為進程分配CPU B.建立一個進程控制塊
C.為進程分配內存 D.將進程控制塊鏈入就緒隊列
7. 在多進程的系統中,為了保證公區變量的完整性,各進程應互斥進入臨界區。所謂臨
界區是[ ]
A.一個緩衝區 B.一個數據區 C.一個同步機構 D.一段程序
8. 能產生滿足如下條件語言的正則表達式是:1.每一個a後至少緊跟兩個c; 2.每一個b
後至少緊跟一個c [ ]
A.(acc|bc|c)* B.(acc|bc)* C.(ac|bc)* D.不是正則語言
9. 以下哪項不是RPC(遠程過程調用)的特點[ ]
A.速度快 B.降低系統耦合度 C.可以實現異構系統間的協作
10. 有三個桶,容量分別是3升,5升,7升,你只能進行下面的操作:
把一個桶中所有的水倒掉;
把一個桶A中的水倒入桶B,直到桶A空了或者桶B滿了;
假設一開始容量為3升和5升的桶是滿的,7升的桶是空的,希望通過一系列操作使3個桶
中任意一箇中正好有4升水,那麼至少需要[ ]次操作。
A.3 B.5 C.7 D.不可能
2. 程序設計與算法
2.1 實現如下編碼算法,對於重複2-9次數的字符,用兩個數字表示,即NX(其中N為重
復的次數,X為重複的字符,下同),超過九個則先輸出9X,然後處理剩下的字符。對於
連續的不重複的字符,則兩邊加1來封字符串。如果被封的字符串其中有數字為1,則用1
來轉義。 示例: AAAAAABCCCC -> 6A1B14C, 12344 -> 11123124。。。(下面的框
架是用C++語言寫的。你可以用你熟悉的語言。)
void encode (const char* text, char* dest)
text 為需要編碼的字符串,dest表示編碼輸出的目標空間,而空間足夠大
2.2給定一顆有n個結點的二叉樹。求它的所有結點數為m的連通子圖數目。m<=n分析你的
算法的時間複雜度,解釋算法即可,不必寫代碼。
-
交通銀行筆經(北京大學)
數字部分:重點是做例題的時候,不要做完就完了,要對圖表進行進一步的分析。比如説今天的折線圖,一條線表示總產量,另一條表示其中一種產品的產量,那麼我們要做的就是在草稿紙上算出另外一種產品的產量。其他類似。因為例題中的圖表在後面會再次出現,這樣做能夠節省很多...
-
中國人民銀行直屬事業單位筆經
中國人民銀行直屬事業單位筆經我考的是經濟金融類,昨天考的,記性不太好今天已經忘得差不多了,歡迎補充!!上午考的英語,下午專業。英語的我看見人大的bbs上有筆經,就不寫了,順便轉過來就好了。就先説説經濟金融專業的考試吧。第一部分是填空。比如商業銀行的業務(吸收存...
-
沃爾瑪筆試分享
Wal-Mart筆試剛從沃爾瑪筆試回來立馬抱了電腦上牀了頭痛……上午是説明會和填表在我看來有點多餘主要就是在宣揚他家的企業文化下午分組筆試我是第一組1:30--2:30正是最瞌睡的時候做完出來只覺得頭痛欲裂噁心想吐題目倒也不難,中譯英,英譯中,25道英文...
-
招商銀行- 招商銀行的筆試
招商銀行-招商銀行的筆試居然遲到了幾十分鐘,佩服工作人員的時間觀念……筆試分為兩部分,兩個半小時,基礎知識類似於公務員題,但添加了專業的內容,注重,還包括主觀題;專業的部分就根據不同情況而定了,我們是營銷類的,一道案例題。一道可選題,關於宏觀經濟政策的論述。第...