2013年小米公司校园招聘笔试题及答案.doc

发布时间：2022-09-12 发布人：admin 分类：说明书资料大小：0.05M 资料格式：doc 举报版权申诉

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

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、6 3、运算（93&-8）的结果为：88 4、将一个无序整数数组构造成一个最大堆，最差时间复杂度为： 5、int *p = &n; 那么*p 的值是（） A、p 的值 D、n 的地址 B、p 的地址 C、n 的值 6、一个完全二叉树有 770 个节点，那么其叶子的个数为：385 7、有一个二维数组 a[1...100 , 1...65]有 100 行，65 列，我们以行序为主序，如果该数组的基地址是 10000，且每个元素占 2 个存储单元，请问 a[56 , 22]的存储地址是：17194 8、以下代码输出结果是： [cpp] view plaincopyprint? 1. class B 2. { 3. public: 4. 5. 6. 7. 8. 9. B() { } cout<<"B constructor\n"; s = "B"; void f() 10. {

cout<f(); ((D*)b)->f(); delete b; return 0; 输出结果是 B constructor D constructor BD

二、编程题 1、数组乘积（15 分）输入：一个长度为 n 的整数数组 input 输出：一个长度为 n 的整数数组 result，满足 result[i] = input 数组中除了 input[i]之外所有数的乘积（假设不会溢出）。比如输入：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 , int n) 2. { 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. } int i ; int *result = new int[n]; result[0] = 1; for(i = 1 ; i < n ; ++i) result[i] = result[i-1]*input[i-1]; result[0] = input[n-1]; for(i = n-2 ; i > 0 ; --i) { } result[i] *= result[0]; result[0] *= input[i]; return result; 2、异形数（25 分）在一个长度为 n 的整形数组 a 里，除了三个数字只出现一次外，其他的数字都出现了 2 次。请写程序输出任意一个只出现一次的数字，程序时间和空间复杂度越小越好。例如： a = {1,3,7,9,5,9,4,3,6,1,7}，输出 4 或 5 或 6 C/C++： void find(int* a , int n);

Java: void find(int[] a); [cpp] view plaincopyprint? 1. // lowbit 表示的是某个数从右往左扫描第一次出现 1 的位置 2. int lowbit(int x) return x&~(x-1); 3. { 4. 5. } 6. 7. void find(int* a , int n) 8. { int i , xors; xors = 0; for(i = 0 ; i < n ; ++i) xors ^= a[i]; // 三个数两两的异或后 lowbit 有两个相同，一个不同，可以分为两组 int fips = 0; for(i = 0 ; i < n ; ++i) fips ^= lowbit(xors ^ a[i]); // 表示的是：flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c) int b; // 假设三个只出现一次的其中一个数为 b b = 0; for(i = 0 ; i < n ; ++i) { } if(lowbit(xors ^ a[i]) == fips) b ^= a[i]; // 成功找到三个数中一个数 cout<

的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这 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); [cpp] view plaincopyprint? 1. // 简单的并查集应用 2. int set[10001]; 3. 4. inline int find(int x) //带路径优化的并查集查找算法 5. { 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. } int i , j , r; r = x; while(set[r] != r) r = set[r]; i = x; while(i != r) { } j = set[i]; set[i] = r; i = j; return r; 19. inline void merge(int x , int y) //优化的并查集归并算法 20. { 21. 22. 23. int t = find(x); int h = find(y); if(t < h)

set[h] = t; else set[t] = h; 24. 25. 26. 27. } 28. 29. int friends(int n , int m , int* r[]) 30. { 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. } int i , count; for(i = 1 ; i <= n ; ++i) //初始化并查集，各点为孤立点，分支数为 n set[i] = i; for(i = 0 ; i < m ; ++i) merge(r[i][0] , r[i][1]); count = 0; for(i = 1 ; i <= n ; ++i) { } if(set[i] == i) ++count; return count;

分享到：

赞收藏

资料库

2013年小米公司校园招聘笔试题及答案.doc

相关推荐

求职招聘

热门标签

最新资料