2012百度实习生招聘面试题

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; 
• }