2012百度實習生招聘面試題

一面：
第一題、任意給一個數，試證明這個數的某個倍數的十進制表示是01串，比如3的倍數111是二進制表示，5的倍數10是二進制表示，等等。
假設序列1,11,111,1111…用A1~AN標識，下腳標N即為1的個數，如：A1=1,A2=11,A3=111…
其中沒有一個是N的倍數，即AK mod N不等於0（K屬於1~N），並且AK mod N的余數各不相同，設它們為a1,a2,a3,…,aN，但AK mod N的余數最多只有N-1個不同，則由鴿巢原理可知，a1,a2,a3,…,aN中必有兩個相同，即ai=aj(j>i)，則Aj-Ai=0(mod N)，Aj-Ai即為所求的0和1組成的十進制數M，得證。
第二題、證明素數有無窮多個。
假若素數只有有限多個，設最大的一個是P，從2到P的全體素數是：
　　2，3，5，7，11……，P。
　　所有的素數都在這裡，此外再沒有別的素數了。
　　現在，我們來考察上面從2到P的全體素數相乘、再加上1這個數，設它是A，即
　　A=2×3×5×7×11×……×P+1。
　　A是一個大於1的正整數，它不是素數，就是合數。
　　如果A是素數，那麼，就得到了一個比素數P還要大的素數，這與素數P是最大素數的假設矛盾。
　　如果A是合數，那麼，它一定能夠被某個素數整除，設它能被g整除。
　　因為A被從2到P的任何一個素數除，余數都是1，就是都不能整除，而素數g是能整除A的，所以素數g不在從2到P的全體素數之中。這說明素數g是一個比素數P更大的素數，這又與P是最大的素數的假設矛盾。
　　上面的證明否定了素數只有有限多個的假定，這就證明了素數是無窮多個。
第三題、給一個很大的數組，裡面有兩個數只出現過一次，其他數都出現過兩次，把這兩個數找出來。
很簡單，根據所有數的異或結果，將數字分為兩組，然後找出這兩個數。前面我的blog裡有這個題的介紹的。
第四題、把一個鏈表逆過來，要求空間復雜度O(1)，這個算簡單的。

1. /*
2. ==========================
3. 功能：鏈表逆序
4. (鏈表的頭變成鏈表的尾，鏈表的尾變成頭)
5. 返回：指向鏈表表頭的指針
6. ==========================
7. */
8. struct node *Reverse (struct node *head)

• {
• struct node *p; //臨時存儲
• struct node *p1; //存儲返回結果
• struct node *p2; //源結果節點一個一個取
• p1 = NULL; //開始顛倒時，已顛倒的部分為空
• p2 = head; //p2指向鏈表的頭節點
• while(p2 != NULL)
• {
• p = p2->next;
• p2->next = p1;
• p1 = p2;
• p2 = p;
• }
• head = p1;
• return head;
• }