1、进程切换需要注意哪些问题?
保存处理器PC寄存器的值到被中止进程的私有堆栈; 保存处理器PSW寄存器的值到被中止进程的私有堆栈; 保存处理器SP寄存器的值到被中止进程的进程控制块;
保存处理器其他寄存器的值到被中止进程的私有堆栈; 自待运行进程的进程控制块取SP值并存入处理器的寄存器SP; 自待运行进程的私有堆栈恢复处理器各寄存器的值;
自待运行进程的私有堆栈中弹出PSW值并送入处理器的PSW; 自待运行进程的私有堆栈中弹出PC值并送入处理器的PC。
2、输入一个升序数组,然后在数组中快速寻找两个数字,其和等于一个给定的值。
这个编程之美上面有这个题目的,很简单的,用两个指针一个指向数组前面,一个指向数组的后面,遍历一遍就可以了。
3、有一个名人和很多平民在一块,平民都认识这个名人,但是这个名人不认识任何一个平民,任意两个平民之间是否认识是未知的,请设计一个算法,快速找个这个人中的那个名人。 已知已经实现了一个函数 bool know(int a,int b) 这个函数返回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、有一类数组,例如书序[1,2,3,4,6,8,9,4,8,11,18,19,100] 前半部分是是一个递增数组,后面一个还是递增数组,但整个数组不是递增数组,那么怎么最快的找出其中一个数?
-
#include<iostream>
-
usingnamespacestd;
-
-
intbinary_search(int*a,intlow,inthigh,intgoal)
-
{
-
while(low<=high)
-
{
-
intmiddle=(low+high)>>1;
-
if(a[middle]==goal)
-
returnmiddle;
-
-
elseif(a[middle]<goal)
-
low=middle+1;
-
-
else
-
high=middle-1;
-
}
-
return-1;
-
}
-
voidgetNum(int*a,intlen,intgoal)
-
{
-
inti,index;
-
for(i=0;i<len-1;i++)
-
{
-
if(a[i]>a[i+1])
-
break;
-
}
-
if(a[i]>=goal)
-
{
-
index=binary_search(a,0,i,goal);
-
printf("%d\n",index);
-
}
-
if(a[i+1]<=goal)
-
{
-
index=binary_search(a+i+1,0,len-i-2,goal);
-
if(index!=-1)
-
index+=(i+1);
-
printf("%d\n",index);
-
}
-
}
-
-
intmain(void)
-
{
-
inta[]={1,2,3,4,6,8,9,4,8,11,18,19,100};
-
intlen=13,goal=4;
-
getNum(a,len,goal);
-
return0;
-
}
5、判断一个自然数是否是某个数的平方。当然不能使用开方运算。
方法1:
遍历从1到N的数字,求取平方并和N进行比较。
如果平方小于N,则继续遍历;如果等于N,则成功退出;如果大于N,则失败退出。
复杂度为O(n^0.5)。
方法2:
使用二分查找法,对1到N之间的数字进行判断。
复杂度为O(log n)。
方法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的关系。
如果大于0,则继续减;如果等于0,则成功退出;如果小于 0,则失败退出。
复杂度为O(n^0.5)。不过方法3中利用加减法替换掉了方法1中的乘法,所以速度会更快些。
例如:3^2 = 9 = 1 + 2*1+1 + 2*2+1 = 1 + 3 + 5
4^2 = 16 = 1 + 2*1 + 1 + 2*2+1 +2*3+1
-
intsquare(intn)
-
{
-
inti=1;
-
n=n-i;
-
while(n>0)
-
{
-
i+=2;
-
n-=i;
-
}
-
if(n==0)
-
return1;
-
else
-
return0;
-
}
分享到:
相关推荐
c++面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试...
java面试题10年汇总2011年1月12日更新.rarjava面试题10年汇总2011年1月12日更新.rarjava面试题10年汇总2011年1月12日更新.rarjava面试题10年汇总2011年1月12日更新.rarjava面试题10年汇总2011年1月12日更新.rarjava...
2010年百度面试题 2011年毕业的同学有用
百度2013年移动开发岗位面试题(南京)
百度质量部软件测试面试题,包括所有测试的东西,供大家下载
flahas3.0面试题 flash as3.0面试题 as3.0面试题 as3.0面试题最新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新面试题新...
百度 面试 笔试 互联网 bat,讲述了一些面试技巧以及往年的笔试题目,是2011年前的,参考性较大。
2011年最全Java面试题,2011年最全Java面试题,2011年最全Java面试题,2011年最全Java面试题,2011年最全Java面试题,2011年最全Java面试题,2011年最全Java面试题,2011年最全Java面试题,2011年最全Java面试题,...
面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题...
百度_新浪_盛大2011年面试笔试算法题收集(含答案)_java
百度面试题大收集百度面试题大收集百度面试题大收集
百度android开发面试题,android面试试题
找工作的面试题,很全面,2011年最新java面试题大全
2011年最新.net面试题 最新的噢~
java面试题! java面试题! java面试题! java面试题! java面试题! java面试题!
2011 百度面试题总结
比较全面的.net面试题汇总,面试前看一看,还是很有必要的。做好准备工作么。
【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】...
现在五块钱的付出,将来收获的可能是一份心仪的offer,干货满满,建议下载。...友情提示:本套面试题包括面试题900题+公司实战面试题400问,面试题已经整理好答案,公司题由于新收录没有答案,但非常有参考价值。
百度持续交付组面试题很好的资料,直接大家学习,非常好!