閱讀513 返回首頁    go 阿裏雲 go 技術社區[雲棲]

零零總總的麵試題（3）

1）下列代碼編譯時會產生錯誤的是（）

  1. #include <iostream>     
  2. using namespace std;    
  3. struct Foo    
  4. {    
  5.     Foo() {  }    
  6.     Foo(int) {  }    
  7.     void fun()   {  }    
  8. };    
  9. int main(void)    
  10. {    
  11.     Foo a(10);    //語句1     
  12.     a.fun();      //語句2     
  13.     Foo b();      //語句3     
  14.     b.fun();      //語句4     
  15.     return 0;    
  16. }    


A、語句1             B、語句2           C、語句3             D、語句4   

說明：詐一看，是語句3報錯，因為調用缺省構造函數是不需要寫括號的，但事實上語句4報錯。語句3其實是編譯通過的，隻不過被編譯器理解為一個沒有參數返回一個FOO 類型對象的函數.

（2）在排序方法中，元素比較次數與元素的初始排列無關的是（）
A、Shell 排序         B、歸並排序              C、直接插入排序                D、選擇排序
說明：A、C肯定不選的，歸並排序的在merge中是跟序列有關，如果有序，比較次數最少n/2，最糟是元素錯落n-1。而選擇排序比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1)+(n-2)+...+1=n*(n-1)/2。所以 應該是選擇排序！

（3）給你1、2、3 這三個數字 可以使用C的各種運算符 你能表示的最大的整數是（） 

A、2*3*sizeof(1)             B、3<<(2<<sizeof(1))                    C、sizeof(3)<<(sizeof(2)<<(sizeof(1)))                    D、(unsigned long)(2-3)*1

（4）判斷一個單向鏈表中是否存在環的最佳方法是（）
A、兩重遍曆      B、快慢指針      C、路徑記錄       D、哈希表輔助

（5）下麵代碼的輸出是多少？

  1. class A    
  2. {    
  3. public:    
  4.     A()  {    cout<<"A"<<endl;    }    
  5.     ~A() {    cout<<"~A"<<endl;   }    
  6. };    
  7.     
  8. class B:public A    
  9. {    
  10. public:    
  11.     B(A &a):_a(a)    
  12.     {    
  13.         cout<<"B"<<endl;    
  14.     }    
  15.     ~B()    
  16.     {    
  17.         cout<<"~B"<<endl;    
  18.     }    
  19. private:    
  20.     A _a;    
  21. };    
  22.     
  23. int main(void)    
  24. {    
  25.     A a;       //很簡單，定義a的時候調用了一次構造函數     
  26.     B b(a);    //這裏b裏麵的_a是通過成員初始化列表構造起來的     
  27.     //而且是通過copy constructor構造的是b的成員對象_a的，這裏是編譯器默認的，因此在構造好_a前，先調用基類構造函數     
  28.     //然後才是構造自身,順序就是A()->_a->B()（局部）     
  29.     //因此這裏有兩個A,一個B     
  30.     
  31.         
  32.     //在return之前進行析構     
  33.     /************************************************************************/    
  34.     /*析構是按照定義對象的反順序來的，而且同一個對象按照構造的反順序來的，因此這裏先  
  35.     析構b然後才是a，那麼b的構造順序是上麵的A()->_a->B()（局部），反過來，就是B()（局部）->_a->A()  
  36.     因此得到的就是~B->~A->~A  
  37.     在b之後就是析構a  
  38.     最後結果就是  
  39.     ~B->~A->~A->~A*/    
  40.     return 0;    
  41. }    


 （6）判斷一包含n個整數a[]中是否存在i、j、k滿足a[i] +>

       A.O(n^3)        B. O(n^2*logn)       C. O(n^3)    D. O(nlogn)

（7）下列序排算法中最壞情況下的時間複雜度不是n(n-1)/2的是

       A.快速排序     B.冒泡排序   C.直接插入排序   D.堆排序

（8）下列說法錯誤的是：

A.SATA硬盤的速度大約為500Mbps/s

B.讀取18XDVD光盤數據的速度為1Gbps

C.千兆以太網的數據讀取速度為1Gpbs

D.讀取DDR3內存數據的速度為100Gbps

分析：A和B相比，怎麼光盤的速度比硬盤還快？B必錯無疑啊。千兆以太網的速度是1000Mbps，也可以寫成1Gbps。DDR3-1600的極限傳輸速度是12.8GBp/s

 

（9）設在內存中有P1,P2,P3三道程序，並按照P1,P2,P3的優先級次序運行，其中內部計算和IO操作時間由下表給出（CPU計算和IO資源都隻能同時由一個程序占用）：

P1:計算60ms---》IO 80ms---》計算20ms

P2:計算120ms---》IO 40ms---》計算40ms

P3:計算40ms---》IO 80ms---》計算40ms

完成三道程序比單道運行節省的時間是（）

A.80ms

B.120ms

C.160ms

D.200ms

（10）長為n的字符串中匹配長度為m的子串的複雜度為（）

         A.O(N)

         B.O(M+N)

         C.O(N+logM)

         D.O(M+logN)

 

（11）發射三次炮彈，射中目標的概率是0.95，請問發射一次能擊中目標的概率是多少？

      A.0.63

      B.0.50

      C.0.32

       D.0.86

 

（12）在c++程序中，如果一個整型變量頻繁使用，最好將他定義為（）

      A.auto

      B.extern

      C.static

      D.register

 

（13）兩個等價線程並發的執行下列程序，a為全局變量，初始為0，假設printf、++、--操作都是原子性的，則輸出不可能是（）

  1. void foo() {    
  2.     if(a <= 0) {    
  3.         a++;    
  4.     }    
  5.     else{    
  6.         a--;    
  7.     }    
  8.     printf("%d", a);    
  9. }    

         A.01

         B.10

         C.12

         D.22

注：這道題怎麼做的

（13）有N個人，其中一個明星和n-1個群眾，群眾都認識明星，明星不認識任何群眾，群眾和群眾之間的認識關係不知道，現在如果你是機器人R2T2，你每次問一個人是否認識另外一個人的代價為O(1)，試設計一種算法找出明星，並給出時間複雜度（沒有複雜度不得分）。

     遍曆 1~n 這n個人；
     首先取出 1號 和 2號，
     如果 1 認識 2， 那麼把 1 去掉；
     如果1不認識2，就可以把2去掉了。
     每次比較都去掉一個，如此循環；n-1次之後隻有一個人了
     時間複雜度： O（n-1）

（14）下列程序輸出的結果：

  1. #include<stdio.h>  
  2.   
  3. int main(void)  
  4. {  
  5.       int a=10,b=20,c=30;  
  6.       printf("\n%d..%d..%d",a+b+c,b *=2, c*=2);  
  7.       return 0;  
  8. }  

答案：110..40..60

思路：因為C語言中函數參數默認是從右往左處理，而輸出是從左往右

 （15）循環移位的構造

  1. b=a<<(16-n);  
  2. c=a>>n;  
  3. c=c|b;  

（16）談談如下兩式的含義以及區別（C陷阱與缺陷15~19頁）：

          float *g();//因為()的結合優先級比*高，所以該表達式相當於float *(g())，即g是一個函數，函數的返回值為float類型的指針，這是一個函數的聲明。

          float  (*h)();//h先和*結合，表示h是一個指針，再和（）結合表示一個函數。即表示h是一個函數指針，該函數返回值為浮點類型。

          (float (*)());//表示一個“指向返回值為浮點類型的函數的指針”的類型轉換符。

          (void (*)())0;//表示將0轉換為“返回值為void類型的函數的指針”類型。

          (*(void (*)())0)();//調用上麵這個指針的函數。

          typedef  void(*funcptr)();//funcptr就可以用了定義變量，定義變量類型為返回值為void類型的函數指針。

          (*(funcptr)0)();//首先將0轉換為funcptr類型的函數指針，然後調用相應的函數。

          void (*signal(int,void(*)(int)))(int);//首先看塗黑的地方，這是一個函數，其返回類型為一個指針。函數參數為int和一個指向“參數為int，返回類型為void”的指針。再拚起來，該語句聲明了一個函數signal，其返回類型函數指針看紅色的地方，即返回值為void（*）int。可以通過如下的方式來簡化操作：

                         typedef  void(*HANDLER)(int);

                         HANDLER signal(int,HANDLER);

          int(*(*F)(int,int))(int)：根據上麵的分析，我們就可以輕而易舉的得到(*F)(int,int)為函數指針，而返回類型為int(*)(int)的函數指針。

注：一個函數返回一個函數指針時這麼寫的： void (*signal(int,void(*)(int)))(int);

注：若fp是一個函數指針，則調用函數有兩種方式：(*fp)()以及簡寫的fp()。


（17）下列的語句錯在哪，並改正。（C陷阱與缺陷）

                       while(c=getc(in)!=EOF){

                                  putc(c,out);

                        }

       問題出現在優先級上，我將優先級從高到低總結為括號->取地址->單目運算->乘除加減移位比較->位與短路選擇賦值->逗號。按照這個順序賦值運算符比比較運算的優先級低，所以上式等價於這樣c=(getc(in)!=EOF)，這顯然是不對的，與設計者的本意不符，改為：

                       while((c=getc(in))!=EOF){//加一個括號

                                  putc(c,out);

                        }


（18）下列程序會出現在哪一行崩潰？（程序員麵試寶典P71）

  1. struct S{  
  2.     int i;  
  3.     int *p;  
  4. };  
  5. int main()  
  6. {   
  7.     S s;  
  8.     int *p=&s.i;  
  9.     p[0]=4;  
  10.     p[1]=3;  
  11.     s.p=p;  
  12.     s.p[1]=1;  
  13.     s.p[0]=2;  
  14. }  


       我覺得指針變化是上麵這樣一個過程，最終s.p[1]和s.p其實是同一個地方，s.p[1]=1 表示讓S.p指向地址為1的地方，s.p[0]=2，就是將地址為1的地方賦值為2，即*((int*)1)=2，出現程序崩潰。

注：(1)int *p，則p+1=p+sizeof(int)*1；

           char *p，則p+1=p+sizeof(char)*1；

           int *p，int p1 = (char*)p，則p+1=p+sizeof(char)*1

       (2)struct 存儲為連續存儲（不談對界問題）。


（19）指出下麵程序使用錯誤的地方改正（程序員麵試寶典P72）

  1. int max(int x,int y)  
  2. {return x>y?x:y;}  
  3. int main()  
  4. {  
  5.     int *p=&max;    
  6.     ...  
  7. }  
     p根本不是一個指向函數的指針，修改為int (*p)(int,int)=&max，函數指針類型跟函數的形參和返回類型對應的。

注：這個地方用int (*p)(int,int)=max也是可以的，因為函數名被使用時總是由編譯器把他轉換為函數指針。


（20） 某計算機有64位虛地址空間，頁大小是2048B.每個頁表項長為4B。因為所有頁表都必須包含在一頁中，故使用多級頁表，問一共需要多少級？

           2048B=2^11  
           64-11=53（地址中扣除頁內地址位數） 共有2^53頁
          一頁中可以裝2048/4=2^9個頁表項
          9*6>53  至少需要6級頁表




//csdn博客目前暫時不再更新了，有興趣請訪問我的技術博客-曉的博客：zhangxiaolong.org 

最後更新：2017-04-03 18:52:08

  上一篇：go 排序算法係列之堆排序
  下一篇：go 第九章 關係映射 組件關聯映射