《2013年小米公司校园招聘笔试题及答案.doc》由会员分享，可在线阅读，更多相关《2013年小米公司校园招聘笔试题及答案.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2013年小米公司校园招聘笔试题及答案一、填空题（5分每题，一共8题）1、两个人A（速度为a）、B（速度为b）在一直路上相向而行。在A、B距离为s的时候，A放出一个鸽子C（速度为c），C飞到B后，立即掉头飞向A，遇到A在掉头飞向B.就这样在AB之间飞来飞去，直到A、B相遇，这期间鸽子共飞行路程为？答案是：s*c/(a+b)2、（he）的平方=she。h、e、s代表的数字？答案是：分别代表2、5、63、运算（93&-8）的结果为：884、将一个无序整数数组构造成一个最大堆，最差时间复杂度为：5、int *p = &n;那么*p的值是（）A、p的值 B、p的地址 C、n的值 D、n的地址6、一个完
2、全二叉树有770个节点，那么其叶子的个数为：3857、有一个二维数组a1.100 , 1.65有100行，65列，我们以行序为主序，如果该数组的基地址是10000，且每个元素占2个存储单元，请问a56 , 22的存储地址是：171948、以下代码输出结果是：cpp view plaincopyprint?1. classB2. 3. public:4. B()5. 6. coutBconstructorn;7. s=B;8. 9. voidf()10. 11. couts;12. 13. private:14. strings;15. ;16. 17. classD:publicB18. 19
3、. public:20. D():B()21. 22. coutDconstructorn;23. s=D;24. 25. voidf()26. 27. coutf();37. (D*)b)-f();38. deleteb;39. return0;40. class Bpublic:B()coutB constructorn;s = B;void f()couts;private:string s;class D : public Bpublic:D() : B()coutD constructorn;s = D;void f()coutf();(D*)b)-f();delete b;retu
4、rn 0;输出结果是B constructorD constructorBD二、编程题1、数组乘积（15分）输入：一个长度为n的整数数组input输出：一个长度为n的整数数组result，满足resulti = input数组中除了inputi之外所有数的乘积（假设不会溢出）。比如输入：input = 2,3,4,5，输出result = 60,40,30,24程序时间和空间复杂度越小越好。C/C+：int *cal(int* input , int n);Java:int cal(int input);cpp view plaincopyprint?1. int*cal(int*input,
5、intn)2. 3. inti;4. int*result=newintn;5. result0=1;6. for(i=1;i0;-i)10. 11. resulti*=result0;12. result0*=inputi;13. 14. returnresult;15. int *cal(int* input , int n)int i ;int *result = new intn;result0 = 1;for(i = 1 ; i 0 ; -i)resulti *= result0;result0 *= inputi;return result;2、异形数（25分）在一个长度为n的整形
6、数组a里，除了三个数字只出现一次外，其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字，程序时间和空间复杂度越小越好。例如： a = 1,3,7,9,5,9,4,3,6,1,7，输出4或5或6C/C+：void find(int* a , int n);Java:void find(int a);cpp view plaincopyprint?1. /lowbit表示的是某个数从右往左扫描第一次出现1的位置2. intlowbit(intx)3. 4. returnx&(x-1);5. 6. 7. voidfind(int*a,intn)8. 9. inti,xors;10. xor
7、s=0;11. for(i=0;in;+i)12. xors=ai;13. /三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组14. intfips=0;15. for(i=0;in;+i)16. fips=lowbit(xorsai);17. /表示的是：flips=lowbit(ab)lowbit(ac)lowbit(bc)18. intb;/假设三个只出现一次的其中一个数为b19. b=0;20. for(i=0;in;+i)21. 22. if(lowbit(xorsai)=fips)23. b=ai;24. 25. /成功找到三个数中一个数26. coutbendl;
8、27. / lowbit表示的是某个数从右往左扫描第一次出现1的位置int lowbit(int x)return x&(x-1);void find(int* a , int n)int i , xors;xors = 0;for(i = 0 ; i n ; +i)xors = ai;/ 三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组int fips = 0;for(i = 0 ; i n ; +i)fips = lowbit(xors ai);/ 表示的是：flips=lowbit(ab)lowbit(ac)lowbit(bc) int b; / 假设三个只出现一次的其中
9、一个数为bb = 0;for(i = 0 ; i n ; +i)if(lowbit(xors ai) = fips)b = ai;/ 成功找到三个数中一个数coutbendl;3、朋友圈（25分）假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友.），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。假如：n = 5 ， m = 3 ， r = 1 , 2 , 2 , 3 , 4 , 5，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。最后请分析所写代码的
10、时间、空间复杂度。评分会参考代码的正确性和效率。C/C+：int friends(int n , int m , int* r);Java:int friends(int n , int m , int r);cpp view plaincopyprint?1. /简单的并查集应用2. intset10001;3. 4. inlineintfind(intx)/带路径优化的并查集查找算法5. 6. inti,j,r;7. r=x;8. while(setr!=r)9. r=setr;10. i=x;11. while(i!=r)12. 13. j=seti;14. seti=r;15. i=j
11、;16. 17. returnr;18. 19. inlinevoidmerge(intx,inty)/优化的并查集归并算法20. 21. intt=find(x);22. inth=find(y);23. if(th)24. seth=t;25. else26. sett=h;27. 28. 29. intfriends(intn,intm,int*r)30. 31. inti,count;32. for(i=1;i=n;+i)/初始化并查集，各点为孤立点，分支数为n33. seti=i;34. for(i=0;im;+i)35. merge(ri0,ri1);36. count=0;37.
12、 for(i=1;i=n;+i)38. 39. if(seti=i)40. +count;41. 42. returncount;43. / 简单的并查集应用int set10001;inline int find(int x) /带路径优化的并查集查找算法 int i , j , r; r = x; while(setr != r) r = setr; i = x; while(i != r) j = seti; seti = r; i = j; return r;inline void merge(int x , int y) /优化的并查集归并算法 int t = find(x); int h = find(y); if(t h) seth = t; else sett = h;int friends(int n , int m , int* r)int i , count;for(i = 1 ; i = n ; +i) /初始化并查集，各点为孤立点，分支数为n seti = i;for(i = 0 ; i m ; +i)merge(ri0 , ri1);count = 0;for(i = 1 ; i = n ; +i)if(seti = i)+count;return count;