腾讯面试题(有复习资料).docx

1. 1-20的两个数把与告诉A,积告诉B，A说不知道是多少，B也说不知道，这时A说我知道了，B接着说我也知道了，问这两个数是多少？答案：2与32 爸爸,妈妈,妹妹,小强,至少两个人同一生肖的概率是多少?1-12*11*10*9/12*12*12*12 = 1-55/96 = 41/963, 计算 ab << 2答案：运算符优先级：括号，下标，->与.(成员)最高；单目的比双目的高；算术双目的比其他双目的高；位运算 高于 关系运算；关系运算 高于 按位运算（及，或，异或）；按位运算 高于 逻辑运算；三目的只有一个 条件运算，低于逻辑运算；赋值运算仅比 , （顺序运算）高。在此题中，位左移"<<" 优先级高于按位异或"",所以b先左移两位（相当于乘以4），再及a异或。例如： 当 a = 6； b = 4 时； 则 ab<<2 = 224 如何输出源文件的标题与目前执行行的行数？答案： printf("The : %dn", _FILE_);printf("The current line No:%dn", _LINE_);ANSI C标准预定义宏:_LINE_FILE_DATE_TIME_STDC_ 当要求程序严格遵循ANSI C标准时该标识符被赋值为1_cplusplus_ 当编写C+程序时该标识符被定义5 a34哪个不能表示 a11: *(&a00+5) *(*(a+1)+1) *(&a1+1) *(&a00+4)答案: *(&a1+1)a是数组的首地址，a1就表示a10地址了，不用再取地址了。6 fun(exp1,exp2),(exp3,exp4,exp5)有几个实参？答案：两个。形式参数：在声明与定义函数时，写在函数名后的括号中的参数。实参是调用参数中的变量，行参是被调用函数中的变量。7. 希尔 冒泡 快速 插入 哪个平均速度最快？答案：快速排序快速排序、归并排序与基数排序在不同情况下都是最快最有用的。8. enum的声明方式答案：enum 枚举类型名 枚举常量1，枚举常量2，.枚举常量n;For example:enum weekday sunday, monday, tuesday, wednesday, thursday, friday, saturday;enum weekday week_day;/week_day 就是一个枚举类型变量9. 频繁的插入删除操作使用什么结构比较合适，链表还是数组？答案：链表10. *p=NULL *p=new char100 sizeof(p)各为多少？答案：都为4。因为都是指针类型，所占存储空间必然为4。11. 顺序查找的平均时间答案：(1+2+3+.+n)/n = (n+1)/212. for(i=0,sum=0; i<10; +i,sum+=i);的运行结果答案：sum = 5513. 不能做switch()的参数类型是：答案：switch的参数不能为浮点型。14.不使用其他变量，交换两个整型a，b的值答案：x = x+y; y = x-y; x = x-y15. 写出float x 及“零值”比较的if语句。if(x>=0.000001 && x<=-0.000001)（x不为0的比较）float: 6位精度double: 16位精度16.两个数相乘，小数点后位数没有限制，请写一个高精度算法*数据库*1. 有个表tableQQ，有整型的ID项与字符类型的Nickname项，这两个项都不允许为空(1)写出建立该表的SQL语句(2)找出Nickname为QQ的用户，按ID降序排列的SQL语句(3)写出删除ID为1234用户记录的SQL语句(4)写出添加ID为5555，Nickname为'1234'的SQL语句答案：(1) CREATE TABLE tableQQ(ID NUMBER(12) NOT NULL,Nickname Varchar2(30) NOT NULL);(2) select * from tableQQ where Nickname = 'QQ' order by ID desc;(3) delete from tableQQ where >(4) insert into tableQQ values(5555,'1234');/删除表(5)drop table tableQQ;2. 有关系 s(sno,sname) c(cno,cname) sc(sno,cno,grade)1 问上课程 "db"的学生2 成绩最高的学生号3 每科大于90分的人数答案：(1)select s.sno, ame from s, c, sc where s.sno = sc.sno and o = o and ame = 'db'(2)select sno, max(grade)from sc group by sno;(3)select cno, count(sno) from sc where grade > 90 group by cno;*=操作系统 网络=1. 描述实时系统的基本特性答案：在特定时间内完成特定的任务，实时性及可靠性。2. Internet采用哪种网络协议？该协议的主要层次结构？答案：TCP/IP协议。应用层、传输层、网络层、数据链路层与物理层。3. Internet物理地址与IP地址转换采用什么协议？答案：地址解析协议ARP address resolution protocol4. IP地址的编码分为哪俩部分？答案：网络号与主机号。不过是要与“子网掩码”按位及上之后才能区分哪些是网络位哪些是主机位。10 二分查找是 顺序存储 链存储 按value有序中的哪些 大题： 1 把字符串转换为小写，不成功返回NULL,成功返回新串 char* toLower(char* sSrcStr) char* sDest= NULL; if( _1_) int j; sLen = strlen(sSrcStr); sDest = new _2_; if(*sDest = NULL) return NULL; sDestsLen = '0' while(_3_) sDestsLen = toLowerChar(sSrcStrsLen); return sDest; 2 把字符串转换为整数 例如："-123" -> -123 main() . if( *string = '-' ) n = _1_; else n = num(string); . int num(char* string) for(;!(*string=0);string+) int k; k = _2_; j = -sLen; while( _3_) k = k * 10; num = num + k; return num; 附加题： 1 linux下调试core的命令，察看堆栈状态命令 2 写出socks套接字 服务端 客户端 通讯程序 3 填空补全程序，按照我的理解是添入：win32调入dll的函数名 查找函数入口的函数名 找到函数的调用形式 把formView加到singledoc的声明 将singledoc加到app的声明 #define Max(a,b) ( a/b)?a:b写一个病毒 while (1)                      int *p = new int10000000;        不使用额外空间,将 A,B两链表的元素交叉归并 将树序列化 转存在数组或 链表中struct stint i;short s;char c;sizeof(struct st); 答案：8     char * p1;    void * p2;    int *p3;    char p410;    sizeof(p1.p4) =? 答案：4，4，4，10二分查找快速排序双向链表的删除结点有12个小球,外形相同,其中一个小球的质量及其他11个不同 给一个天平,问如何用3次把这个小球找出来 并且求出这个小球是比其他的轻还是重解答: 哈哈，据说这是微软前几年的一个面试题。很经典滴啊！三次一定能求出来，而且能确定是重还是轻。 数据结构的知识还没怎么学透，不过这个题我到是自己研究过，可以分析下。 将12个球分别编号为a1,a2,a3.a10,a11,a12. 第一步：将12球分开3拨，每拨4个，a1a4第一拨，记为b1， a5a6第2拨，记为b2，其余第3拨，记为b3； 第二步：将b1与b2放到天平两盘上，记左盘为c1，右为c2；这时候分两中情况： 1.c1与c2平衡，此时可以确定从a1到a8都是常球；然后把c2拿空，并从c1上拿下a4，从a9到a12四球里随便取三球，假设为a9到a11，放到c2上。此时c1上是a1到a3，c2上是a9到a11。从这里又分三种情况：       A：天平平衡，很简单，说明没有放上去的a12就是异球，而到此步一共称了两次，所以将a12随便跟11个常球再称一次，也就是第三次，马上就可以确定a12是重还是轻；       B： 若c1上升，则这次称说明异球为a9到a11三球中的一个，而且是比常球重。取下c1所有的球，并将a8放到c1上，将a9取下，比较a8与a11（第三 次称），如果平衡则说明从c2上取下的a9是偏重异球，如果不平衡，则偏向哪盘则哪盘里放的就是偏重异球；       C：若c1下降，说明a9到a11里有一个是偏轻异球。次种情况与B类似，所以接下来的步骤照搬B就是； 2.c1与c2不平衡，这时候又分两种情况，c1上升与c1下降，但是不管哪种情况都能说明a9到a12是常球。这步是解题的关键。也是这个题最妙的地方。       A：c1上升，此时不能判断异球在哪盘也不能判断是轻还是重。取下c1中的a2到a4三球放一边，将c2中的a5与a6放到c1上，然后将常球a9放到c2上。至此，c1上是a1，a5与a6，c2上是a7，a8与a9。此时又分三中情况：           1） 如果平衡，说明天平上所有的球都是常球，异球在从c1上取下a2到a4中。而且可以断定异球轻重。因为a5到a8都是常球，而第2次称的时候c1是上升 的，所以a2到a4里必然有一个轻球。那么第三次称就用来从a2到a4中找到轻球。这很简单，随便拿两球放到c1与c2，平衡则剩余的为要找球，不平衡则 哪边低则哪个为要找球；           2）c1仍然保持上升，则说明要么a1是要找的轻球， 要么a7与a8两球中有一个是重球（这步懂吧？好好想想，很简单的。因为a9是常球，而取下的a2到a4肯定也是常球，还可以推出换盘放置的a5与a6也 是常球。所以要么a1轻，要么a7或a8重）。至此，还剩一次称的机会。只需把a7与a8放上两盘，平衡则说明a1是要找的偏轻异球，如果不平衡，则哪边 高说明哪个是偏重异球；           3）如果换球称第2次后天平平衡打破，并且c1降低了，这说明异球肯定在换过来的a5与a6两求中，并且异球偏重，否则天平要么平衡要么保持c1上升。确定要找球是偏重之后，将a5与a6放到两盘上称第3次根据哪边高可以判定a5与a6哪个是重球；       B： 第1次称后c1是下降的，此时可以将c1看成c2，其实以后的步骤都同A，所以就不必要再重复叙述了。至此，不管情况如何，用且只用三次就能称出12个外 观手感一模一样的小球中有质量不同于其他11球的偏常的球。而且在称的过程中可以判定其是偏轻还是偏重。 给一个奇数阶N幻方，填入数字1，2，3.N*N,使得横竖斜方向上的与都相同答案:#include<iostream>#include<iomanip>#include<cmath>usingnamespace std;int main() int n; cin>>n; int i; int *Matr=new int*n;/动态分配二维数组 for(i=0;i<n;+i)      Matr i =newintn;/动态分配二维数组 /j=n/2代表首行中间数作为起点，即1所在位置 int j=n/2,num=1;/初始值 i=0; while(num!=n*n+1) /往右上角延升，若超出则用%转移到左下角      Matr(i%n+n)%n(j%n+n)%n=num;    /斜行的长度与n是相等的，超出则转至下一斜行    if(num%n=0)          i+;   else                i-;          j+;           num+; for(i=0;i<n;i+)       for(j=0;j<n;+j)         cout<<setw(int)log10(n*n)+4)<<Matr i j ;/格式控制      cout<<endl<<endl;/格式控制 for(i=0;i<n;+i)      delete Matr i ;return1;腾讯的一道面试题:(及百度相似,可惜昨天百度死在这方面了)/在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。答案:1， 把整数分成256M段，每段可以用64位整数保存该段数据个数，256M*8 = 2G内存，先清0 2，读10G整数，把整数映射到256M段中，增加相应段的记数 3，扫描256M段的记数，找到中位数的段与中位数的段前面所有段的记数，可以把其他段的内存释放 4，因中位数段的可能整数取值已经比较小（如果是32bit整数，当然如果是64bit整数的话，可以再次分段），对每个整数做一个记数，再读一次10G整数，只读取中位数段对应的整数，并设置记数。 5，对新的记数扫描一次，即可找到中位数。 如果是32bit整数，读10G整数2次，扫描256M记数一次，后一次记数因数量很小，可以忽略不记(设是32bit整数，按无符号整数处理 整数分成256M段？ 整数范围是0 - 232 - 1 一共有4G种取值，4G/256M = 16，每16个数算一段 0-15是1段，16-31是一段，. 整数映射到256M段中？ 如果整数是0-15，则增加第一段记数，如果整数是16-31，则增加第二段记数，. 其实可以不用分256M段，可以分的段数少一写，这样在扫描记数段时会快一些，还能节省一些内存)腾讯题二:一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数答:方法一: 4个字节表示的整数，总共只有232约等于4G个可能。 为了简单起见，可以假设都是无符号整数。 分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。 算法流程： ）分配内存buf，初始化为 ）unsigned int x=0x1;     for each int j in file     buf=buf ¦x < <j;     end (3) for(unsigned int i=0; i <= 0xffffffff; i+)         if (!(buf & x < <i)                     output(i);             break;         以上只是针对无符号的，有符号的整数可以依此类推。方法二:文件可以分段读啊，这个是O（2n）算法，应该是很快的了，而且空间也允许的。 不过还可以构造更快的方法的，更快的方法主要是针对定位输出的整数优化算法。 思路大概是这样的，把值空间等分成若干个值段，比如值为无符号数，则 00000000H-00000FFFH 00001000H-00001FFFH . 0000F000H-0000FFFFH . FFFFF000H-FFFFFFFFH 这样可以订立一个规则，在一个值段范围内的数第一次出现时，对应值段指示值Xn=Xn+1，如果该值段的所有整数都出现过，则Xn=1000H，这样后面输出定位时就可以直接跳过这个值段了，因为题目仅仅要求输出一个，这样可以大大减少后面对标志数值的遍历步骤。 理论上值段的划分有一定的算法可以快速的实现，比如利用位运算直接定位值段对应值进行计算。腾讯面试题:有1到10w这10w个数，去除2个并打乱次序，如何找出那两个数。（不准用位图！）位图解决:位图的方法如下 假设待处理数组为A10w-2 定义一个数组B10w,这里假设B中每个元素占用1比特,并初始化为全0 for(i=0;i <10w-2;i+) B Ai =1 那么B中不为零的元素即为缺少的数据 这种方法的效率非常高，是计算机中最常用的算法之一其它方法:    求与以及平方与可以得到结果，不过可能求平方与运算量比较大（用64位int不会溢出）腾讯面试题:腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。解答: 第二题如果空间足够大,可以定义一个大的数组 aqq号,初始为零,然后这个qq号登陆了就aqq号+ 最后统计大于等于2的QQ号 这个用空间来代替时间第二个题目，有不成熟的想法。 2w x 300s 所以用 6,000,000 个桶。删除超时的算法后面说，所以平均桶的大小是 1 。 假设 qq 号码一共有 1010 个，所以每个桶装的 q 号码是 1010 / (6 * 106) 个，这个是插入时候的最坏效率（插入同一个桶的时候是顺序查找插入位置的）。 qq的节点结构与上面大家讨论的基本一样，增加一个指针指向输出列表，后面说。 struct QQstruct    num_type    qqnum;    timestamp   last_logon_time;    QQstruct    *pre;    QQstruct    *next;    OutPutList *out;     / 用于 free 节点的时候，顺便更新一下输出列表。 另外增加两个指针列表。 第一个大小 300 的循环链表，自带一个指向 QQStruct 的域，循环存 300 秒内的qq指针。时间一过 就 free 掉， 所以保证所有桶占用的空间在 2w X 300 以内。 第二个是 输出列表， 就是存放题目需要输出的节点。 如果登陆的用户，5分钟内完全没有重复的话，每秒 free 掉 2w 个节点。 不过在 free 的时候，要判断一下时间是不是真的超时，因为把节点入桶的时候，遇到重复的，会更 新一下最后登陆的时间。当然啦，这个时候，要把这个 qq 号码放到需要输出的列表里面。