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分析你的
演算法的時間複雜度,解釋演算法即可,不必寫程式碼。
-
管理培訓生招商銀行總行筆試
本來不是非常想去參加這個筆試,但是老爸專門打來電話教育良久說進去就是進了保險箱……云云,朋友們也說單位好,職位好,值得一試,於是早上一大早爬起來去人大考試。最近參加了若干筆試,有一些小結:1、題量很大,基本做不完;2、題目故意不按難易程度排列,這樣如...
-
金地集團筆試題(精華)
1.你為什麼選擇現在的專業?請列舉出你這個專業的三個特點?你最喜歡的一門課程是什麼?你從中的最大收穫是什麼?你最不喜歡的課程有哪些?為什麼?列舉出你記憶中最輕鬆的一件事情,最費勁的一件事情2.A公司:高速發展、制度不完善、?B公司:穩健發展、制度完善、??如果你是畢業...
-
凱德筆試及一面(杭州)
昨天晚上筆試,夜裡十一點半通知第二天上午十點半面試。投了這麼多簡歷,終於有了迴音。其實筆試後並沒有報太大的希望,因為做完題後感覺不太好。筆試分為兩部分,第一部分20題,類似於公務員考試的行政能力測試,20分鐘完成,感覺時間挺緊,沒做完,好幾道題只能靠蒙,算是為公務...
-
阿里巴巴的筆試
阿里巴巴的筆試全英文寫作,狂暈1、說出一個你印象很深的人,同時寫出讓你印象深的原因2、說出從中國出口到USA的大致流程3、兩份商務回函4、公司背景翻譯5、你認為對B2B站點來說,什麼是為商業人士服務的關鍵...