各大IT公司笔试面试题目.doc

《各大IT公司笔试面试题目.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2011各大IT公司笔试面试题目分类： C++语法知识2012-02-1211:05 563人阅读 评论(1) 收藏 举报2011.10.17百度面试题1、进程切换需要注意哪些问题？保存处理器PC寄存器的值到被中止进程的私有堆栈；     保存处理器PSW寄存器的值到被中止进程的私有堆栈；   保存处理器SP寄存器的值到被中止进程的进程控制块；保存处理器其他寄存器的值到被中止进程的私有堆栈；    自侍运行进程的进程控制块取SP值并存入处理器的寄存器SP；   自侍运行进程的私有堆栈恢复处理器各寄存器的值；自侍运行

2、进程的私有堆栈中弹出PSW值并送入处理器的PSW；    自侍运行进程的私有堆栈中弹出PC值并送入处理器的PC。2、输入一个升序数组，然后在数组中快速寻找两个数字，其和等于一个给定的值。这个编程之美上面有这个题目的，很简单的，用两个指针一个指向数组前面，一个指向数组的后面，遍历一遍就可以了。3、有一个名人和很多平民在一块，平民都认识这个名人，但是这个名人不认识任何一个平民，任意两个平民之间是否认识是未知的，请设计一个算法，快速找出这些人中的那个名人。 已知已经实现了一个函数 boolknow(inta,intb)这

3、个函数返回true的时候，表明a认识b，返回false的时候表明a不认识b。思路：首先将n个人分为n/2组，每一组有2个人，然后每个组的两个人调用这个know函数，假设为know（a，b），返回true的时候说明a认识b，则a肯定不是名人，a可以排除掉了，依次类推，每个组都调用这个函数依次，那么n个人中就有n/2个人被排除掉了，数据规模将为n/2。同理在剩下的n/2个人中在使用这个方法，那么规模就会将为n/4，这样所有的遍历次数为n/2+n/4+n/8+........这个一个等比数列，时间复杂度为o（n）。4、判

4、断一个自然数是否是某个数的平方。当然不能使用开方运算。方法1：遍历从1到N的数字，求取平方并和N进行比较。如果平方小于N，则继续遍历；如果等于N，则成功退出；如果大于N，则失败退出。复杂度为O(n^0.5)。方法2：使用二分查找法，对1到N之间的数字进行判断。复杂度为O(logn)。方法3：由于(n+1)^2=n^2+2n+1，=...=1+(2*1+1)+(2*2+1)+...+(2*n+1)注意到这些项构成了等差数列（每项之间相差2）。所以我们可以比较N-1，N-1-3，N-1-3-5...和0的关系。如果大于

5、0，则继续减；如果等于0，则成功退出；如果小于0，则失败退出。复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法，所以速度会更快些。例如：3^2=9=1+2*1+1+2*2+1=1+3+54^2=16=1+2*1+1+2*2+1 + 2*3+1viewplain1.int square(int n)  2.{  3.    int i = 1;  4.    n = n - i;  5.    while( n > 0 )  6.    {  7.        i += 2;  8.     

6、   n -= i;  9.    }  10.    if( n == 0 )        //是某个数的平方  11.        return 1;  12.    else                //不是某个数的平方  13.        return 0;  14.}   百度2011.10.16校园招聘会笔试题一、算法设计1、设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。思路：这个使用数学中的极坐标来解决，先调用[s1，

7、t1]随机产生一个数r，归一化后乘以半径，得到R*（r-s1）/（t1-s1），然后在调用[s2，t2]随机产生一个数a，归一化后得到角度：360*（a-s2）/（t2-s2）2、为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设计一个算法，对用户请求的query进行随机选择m个，请给一个方案，使得每个query被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。思路：如果用户查询的数量小于m，那么直接就存起来。如果用户查询的

8、数量大于m，假设为m+i，那么在1-----m+i之间随机产生一个数，如果选择的是前面m条查询进行存取，那么概率为m/（m+i），如果选择的是后面i条记录中的查询，那么用这个记录来替换前面m条查询记录的概率为m/（m+i）*（1-1/m）=(m-1)/(m+i)，当查询记录量很大的时候，m/（m+i）==(m-1)/(m+i)，所以每个query被抽中的概率