2013小米笔试题目答案详解

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、一个完全二叉树有770个节点，那么其叶子的个数为：3857、有一个二维数组a1.100 , 1.65有100行，65列，我们以行序为主序，如果该数组的基地址是10000，且每个元素占2个存储单元，请问a56 , 22的存储地址是：173248、以下代码输出结果是：cppview plaincopy1. 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. 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. 输出结果是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);cppview plaincopy1. int*cal(int*input,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. 2、异形数（25分）在一个长度为n的整形数组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);cppview plaincopy1. /lowbit表示的是某个数从右往左扫描第一次出现1的位置2. intlowbit(intx)3. 4. returnx&(x-1);5. 6. 7. voidfind(int*a,intn)8. 9. inti,xors;10. xors=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;27. 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个朋友圈。最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。C/C+：int friends(int n , int m , int* r);Java:int friends(int n , int m , int r);cppview plaincopy1. /简单的并查集应用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;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. for(i=1;i=n;+i)38. 39. if(seti=i)40. +count;41. 42. returncount;43.