stl,,面试重点.docx

stl,,面试重点篇一:有点难度的C++面试题篇二:各大IT公司笔试面试题目 20XX各大IT公司笔试面试题目分类:C++语法知识20XX-02-1211:05563人阅读评论收藏举报百度面试题 1、进程切换需要注意哪些问题? 保存处理器PC寄存器的值到被中止进程的私有堆栈;保存处理器PSW寄存器的值到被中止进程的私有堆栈;保存处理器SP寄存器的值到被中止进程的进程控制块; 保存处理器其他寄存器的值到被中止进程的私有堆栈;自侍运行进程的进程控制块取SP值并存入处理器的寄存器SP;自侍运行进程的私有堆栈恢复处理器各寄存器的值; 自侍运行进程的私有堆栈中弹出PSW值并送入处理器的PSW;自侍运行进程的私有堆栈中弹出PC值并送入处理器的PC。 2、输入一个升序数组,然后在数组中快速寻找两个数字,其和等于一个给定的值。这个编程之美上面有这个题目的,很简单的,用两个指针一个指向数组前面,一个指向数组的后面,遍历一遍就可以了。 3、有一个名人和很多平民在一块,平民都认识这个名人,但是这个名人不认识任何一个平民,任意两个平民之间是否认识是未知的,请设计一个算法,快速找出这些人中的那个名人。已知已经实现了一个函数boolknow这个函数返回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: 遍历从1到N的数字,求取平方并和N进行比较。如果平方小于N,则继续遍历;如果等于N,则成功退出;如果大于N,则失败退出。复杂度为O。方法2: 使用二分查找法,对1到N之间的数字进行判断。复杂度为O。方法3: 由于^2 =n^2+2n+1。=... =1+++...+ 注意到这些项构成了等差数列(每项之间相差2)。所以我们可以比较N-1,N-1-3,N-1-3-5...和0的关系。如果大于0,则继续减;如果等于0,则成功退出;如果小于0,则失败退出。复杂度为O。不过方法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 viewplain 1. 2. 3. 4. 5. 6. 7. 8. {inti=1;n=n-i;while{i+=2;n-=i;} //是某个数的平方 1; //不是某个数的平方 0; 14.} 百度校园招聘会笔试题一、算法设计 1、设rand(s,t)返回[s,t]之间的随机小数,利用该函数在一个半径为R的圆内找随机n个点,并给出时间复杂度分析。思路:这个使用数学中的极坐标来解决,先调用[s1,t1]随机产生一个数r,归一化后乘以半径,得到R*(r-s1)/(t1-s1),然后在调用[s2,t2]随机产生一个数a,归一化后得到角度:360*(a-s2)/(t2-s2) 2、为分析用户行为,系统常需存储用户的一些query,但因query非常多,故系统不能全存,设系统每天只存m个query,现设计一个算法,对用户请求的query进行随机选择m个,请给一个方案,使得每个query被抽中的概率相等,并分析之,注意:不到最后一刻,并不知用户的总请求量。思路:如果用户查询的数量小于m,那么直接就存起来。如果用户查询的数量大于m,假设为m+i,那么在1-----m+i之间随机产生一个数,如果选择的是前面m条查询进行存取,那么概率为m/(m+i),如果选择的是后面i条记录中的查询,那么用这个记录来替换前面m条查询记录的概率为m/(m+i)*(1-1/m)=/,当查询记录量很大的时候,m/(m+i)==/,所以每个query被抽中的概率是相等的。 3、C++STL中vector的相关问题: (1)、调用push_back时,其内部的内存分配是如何进行的? (2)、调用clear时,内部是如何具体实现的?若想将其内存释放,该如何操作? vector的工作原理是系统预先分配一块CAPACITY大小的空间,当插入的数据超过这个空间的时候,这块空间会让某种方式扩展,但是你删除数据的时候,它却不会缩小。 vector为了防止大量分配连续内存的开销,保持一块默认的尺寸的内存,clear只是清数据