小米筆試題目+答案詳解

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

2、、n的地址6、一個完全二叉樹有770個節(jié)點，那么其葉子的個數為：3857、有一個二維數組a1.100 , 1.65有100行，65列，我們以行序為主序，如果該數組的基地址是10000，且每個元素占2個存儲單元，請問a56 , 22的存儲地址是：173248、以下代碼輸出結果是：cppview plaincopyclassBpublic:B()coutBconstructorn;s=B;voidf()couts;private:strings;classD:publicBpublic:D():B()coutDconstructorn;s=D;voidf()coutf();(D*)b)-f();d

3、eleteb;return0;輸出結果是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 plaincopyint*cal(int*input,

4、intn)inti;int*result=newintn;result0=1;for(i=1;i0;-i)resulti*=result0;result0*=inputi;returnresult;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 plaincopy/lowbit表示的

5、是某個數從右往左掃描第一次出現1的位置intlowbit(intx)returnx&(x-1);voidfind(int*a,intn)inti,xors;xors=0;for(i=0;in;+i)xors=ai;/三個數兩兩的異或后lowbit有兩個相同，一個不同，可以分為兩組intfips=0;for(i=0;in;+i)fips=lowbit(xorsai);/表示的是：flips=lowbit(ab)lowbit(ac)lowbit(bc)intb;/假設三個只出現一次的其中一個數為bb=0;for(i=0;in;+i)if(lowbit(xorsai)=fips)b=ai;/成功找到

6、三個數中一個數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個朋友圈。最后請分析所寫代碼的時間、空間復雜度。評分會參考代碼的正確性和效率。C/C+：int friends(int n , int m , int* r);Java:i

7、nt friends(int n , int m , int r);cppview plaincopy/簡單的并查集應用intset10001;inlineintfind(intx)/帶路徑優(yōu)化的并查集查找算法inti,j,r;r=x;while(setr!=r)r=setr;i=x;while(i!=r)j=seti;seti=r;i=j;returnr;inlinevoidmerge(intx,inty)/優(yōu)化的并查集歸并算法intt=find(x);inth=find(y);if(th)seth=t;elsesett=h;intfriends(intn,intm,int*r)inti,count;for(i=1;i=n;