騰訊2011.10.15校園招聘會筆試題 · IT公司筆試題集錦

轉載請標明出處，原文地址：[http://blog.csdn.net/hackbuteer1/article/details/6878287](http://blog.csdn.net/hackbuteer1/article/details/6878287) 1、下面的排序算法中，初始數據集的排列順序對算法的性能無影響的是（**B**） A、插入排序?????????????????????**B、堆排序**??????????????? C、冒泡排序???????????????????? D、快速排序 2、以下關于Cache的敘述中，正確的是（**B**） A、CPU中的Cache容量應大于CPU之外的Cache容量 **B、Cache的設計思想是在合理成本下提高命中率** C、Cache的設計目標是容量盡可能與主存容量相等 D、在容量確定的情況下，替換算法的時間復雜度是影響Cache命中率的關鍵因素 3、數據存儲在磁盤上的排列方式會影響I/O服務的性能，一個圓環的磁道上有10個物理塊，10個數據記錄R1------R10存放在這個磁道上，記錄的安排順序如下表所示： <table border="1" cellpadding="0" cellspacing="0" width="589"><tbody><tr><td>物理塊</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>邏輯記錄</td><td>R1</td><td>R2</td><td>R3</td><td>R4</td><td>R5</td><td>R6</td><td>R7</td><td>R8</td><td>R9</td><td>R10</td></tr></tbody></table> 假設磁盤的旋轉速度為20ms/周，磁盤當前處在R1的開頭處，若系統順序掃描后將數據放入單緩沖區內，處理數據的時間為4ms（然后再讀取下個記錄），則處理這10個記錄的最長時間為（**C**） A、180ms?????????????????????????? B、200ms????????????????????????? C、204ms???????????????????????????? D、220ms 2+4+（（2+4）+2*8）*9=204 4、隨著IP網絡的發展，為了節省可分配的注冊IP地址，有一些地址被拿出來用于私有IP地址，以下不屬于私有IP地址范圍的是（**C**） A、10.6.207.84????????????????????????????? B、172.23.30.28?????????????????????**C、172.32.50.80**????????????? D、192.168.1.100 私有IP地址共有三個范圍段： A：???? 10.0.0.0~10.255.255.255 /8 　　B：????? 172.16.0.0~172.31.255.255 /12 　　C：?? 192.168.0.0~192.168.255.255 /16 5、下列關于一個類的靜態成員的描述中，不正確的是（**D**） A、該類的對象共享其靜態成員變量的值????????????????????????????? B、靜態成員變量可被該類的所有方法訪問????????????????? C、該類的靜態方法只能訪問該類的靜態成員變量????????????????**D、該類的靜態數據成員變量的值不可修改** 6、已知一個線性表（38，25，74，63，52，48），假定采用散列函數h（key) = key%7計算散列地址，并散列存儲在散列表A【0....6】中，若采用線性探測方法解決沖突，則在該散列表上進行等概率成功查找的平均查找長度為（**C**） A、1.5????????????????? B、1.7???????????????????????????**C、2.0**????????????????????? D、2.3 依次進行取模運算求出哈希地址： <table border="1" cellpadding="0" cellspacing="0" width="591"><tbody><tr><td>A</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr><tr><td>記錄</td><td>63</td><td>48</td><td>?</td><td>38</td><td>25</td><td>74</td><td>52</td></tr><tr><td>查找次數</td><td>1</td><td>3</td><td>?</td><td>1</td><td>1</td><td>2</td><td>4</td></tr></tbody></table> 74應該放在下標為4的位置，由于25已經放在這個地方，所以74往后移動，放在了下標為5的位置上了。由于是等概率查找，所以結果為：1/6*（1+3+1+1+2+4）= 2.0 7、表達式“X=A+B*（C--D）/E”的后綴表示形式可以為（**C**） A、XAB+CDE/-*=???????????????????? B、XA+BC-DE/*=??????????????????????**C、XABCD-*E/+=**??????????????????????? D、XABCDE+*/= 8、（**B**）設計模式將抽象部分與它的實現部分相分離。 A、Singleton（單例）???????????????????????????????????? ?**B、?Bridge（橋接）**???????????????????? C、?Composite（組合）???????????????????????????????????D、 Facade（外觀） 9、下面程序的輸出結果為多少？ ~~~ void Func(char str_arg[100]) { printf("%d\n",sizeof(str_arg)); } int main(void) { char str[]="Hello"; printf("%d\n",sizeof(str)); printf("%d\n",strlen(str)); char *p = str; printf("%d\n",sizeof(p)); Func(str); } ~~~ 輸出結果為：6?? 5???? 4????? 4 對字符串進行sizeof操作的時候，會把字符串的結束符“\0”計算進去的，進行strlen操作求字符串的長度的時候，不計算\0的。數組作為函數參數傳遞的時候，已經退化為指針了，Func函數的參數str_arg只是表示一個指針，那個100不起任何作用的。 10、C++將父類的析構函數定義為虛函數，下列正確的是哪個？ A、釋放父類指針時能正確釋放子類對象 B、釋放子類指針時能正確釋放父類對象 C、這樣做是錯誤的 D、以上全錯 C++的多態肯定是使用父類的指針指向子類的對象，所以肯定是釋放子類的對象，如果不使用虛函數的話，父類的指針就只能夠釋放父類的對象。 11、下列哪一個不屬于關系數據庫的特點？ A、數據冗余度小 B、數據獨立性高 C、數據共享性好 D、多用戶訪問 12、下面程序的輸出結果為多少？ ~~~ void Func(char str_arg[2]) { int m = sizeof(str_arg); //指針的大小為4 int n = strlen(str_arg); //對數組求長度，str_arg后面的那個2沒有任何意義，數組已經退化為指針了 printf("%d\n",m); printf("%d\n",n); } int main(void) { char str[]="Hello"; Func(str); } ~~~ 輸出結果為：????? 4???????? 5 strlen只是對傳遞給Func函數的那個字符串求長度，跟str_arg中的那個2是沒有任何關系的，即使把2改為200也是不影響輸出結果的。。 13、typedef char *String_t; 和 #define String_d char * 這兩句在使用上有什么區別？答：typedef char *String_t 定義了一個新的類型別名，有類型檢查。而#define String_d char * 只是做了個簡單的替換，無類型檢查，前者在編譯的時候處理，后者在預編譯的時候處理。同時定義多個變量的時候有區別，主要區別在于這種使用方式String_t? a,b;? String_d? c,d;??? a,b ,c都是char*類型，而d為char類型由于typedef還要做類型檢查。。#define沒有。。所以typedef比#define安全。。 14、到商店里買200的商品返還100優惠券（可以在本商店代替現金）。請問實際上折扣是多少？ 15、題目：已知rand7() 可以產生 1~7 的7個數（均勻概率），利用rand7()? 產生rand10()?? 1~10（均勻概率）記住這道題重點是：均勻概率 ~~~ //rand7 產生的數概率是一樣的,即1~7出現概率一樣，由于我們對結果做了一定的篩選只能通過 1~5，而1~5出現的概率也是一樣的，又由于范圍為1~5 所以 temp1 出現 1~5的概率為1/5 ,同理后面的出現 temp2 的概率為 1/2 //首先temp1出現在1~5的概率為1/5，而temp2出現 1~2 的概率為1/2，也就是說 5*(temp2-1) 出現5或0的概率為1/2,所以假如你要得到1~5的數的話那么 5*（temp2-1）必須0，所以因為你要保證 5*（temp2-1）=0，這個概率只有1/2,再加上你前面指定1~5 的概率為1/5 ,所以結果為 1/5*1/2=1/10 int rand10() { int temp1; int temp2; do { temp1 = rand7(); }while(temp1>5); do { temp2 = rand7(); }while(temp2>2); return temp1+5*(temp2-1); } ~~~ 16、給定能隨機生成整數1到5的函數，寫出能隨機生成整數1到7的函數。 17、對一個正整數作如下操作：如果是偶數則除以2，如果是奇數則加1，如此進行直到1時操作停止，求經過9次操作變為1的數有多少個？第9次操作：結果1由2產生。1個被操作數 8：結果2只能由4產生。1個被操作數 7：結果4由8、3產生。2個 6：結果8由16、7產生；結果3由6產生。共3個 5：結果16由32、15產生；結果7由14產生；結果6由12、5產生。共5個… 每次操作，偶數（2除外）都由該數減1和該數的2倍得來，奇數只由該數的2倍得來各次操作的操作對象個數為：1，1，2，3，5，8，13，21，34，… 本題可以通過所給的變換規律，由易到難，確定操作可變為1的數組成斐波拉契數列，再根據所發現的規律求出經過9次操作變為1的數的個數。 18、OFFSETOF(s, m)的宏定義，s是結構類型，m是s的成員，求m在s中的偏移量。 ~~~ #define OFFSETOF(s,m) ((int)&(((s*)0)->m)) ~~~ 用地址零作為起始地址，強制轉換成結構體類型，然后取出成員的地址，轉換成int類型，就可以得到偏移量了。算法編程題： 1、給定一個字符串，求出其最長的重復子串。思路：使用后綴數組，對一個字符串生成相應的后綴數組后，然后再排序，排完序依次檢測相鄰的兩個字符串的開頭公共部分。這樣的時間復雜度為：生成后綴數組 O(N) 排序 O(NlogN*N) 最后面的 N 是因為字符串比較也是 O(N) 依次檢測相鄰的兩個字符串 O(N * N) 總的時間復雜度是 O(N^2*logN),? 轉載請標明出處，原文地址：[http://blog.csdn.net/hackbuteer1/article/details/6878287](http://blog.csdn.net/hackbuteer1/article/details/6878287)