小米筆試題目+答案詳解

1、2013小米筆試題目+答案詳解收藏的一些筆試題目，僅供參考一、填空題（5分每題，一共8題）1、兩個(gè)人A（速度為a）、B（速度為b）在一直路上相向而行。在A、B距離為s的時(shí)候，A放出一個(gè)鴿子C（速度為c），C飛到B后，立即掉頭飛向A，遇到A在掉頭飛向B.就這樣在AB之間飛來飛去，直到A、B相遇，這期間鴿子共飛行路程為？答案是：s*c/(a+b)2、（he）的平方=she。h、e、s代表的數(shù)字？答案是：分別代表2、5、63、運(yùn)算（93&-8）的結(jié)果為：884、將一個(gè)無序整數(shù)數(shù)組構(gòu)造成一個(gè)最大堆，最差時(shí)間復(fù)雜度為：5、int *p = &n;那么*p的值是（）A、p的值 B、p的地址 C、n的值 D

2、、n的地址6、一個(gè)完全二叉樹有770個(gè)節(jié)點(diǎn)，那么其葉子的個(gè)數(shù)為：3857、有一個(gè)二維數(shù)組a1.100 , 1.65有100行，65列，我們以行序?yàn)橹餍?，如果該?shù)組的基地址是10000，且每個(gè)元素占2個(gè)存儲(chǔ)單元，請問a56 , 22的存儲(chǔ)地址是：173248、以下代碼輸出結(jié)果是：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;輸出結(jié)果是B constructorD constructorBD二、編程題1、數(shù)組乘積（15分）輸入：一個(gè)長度為n的整數(shù)數(shù)組input輸出：一個(gè)長度為n的整數(shù)數(shù)組result，滿足resulti = input數(shù)組中除了inputi之外所有數(shù)的乘積（假設(shè)不會(huì)溢出）。比如輸入：input = 2,3,4,5，輸出result = 60,40,30,24程序時(shí)間和空間復(fù)雜度越小越好。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、異形數(shù)（25分）在一個(gè)長度為n的整形數(shù)組a里，除了三個(gè)數(shù)字只出現(xiàn)一次外，其他的數(shù)字都出現(xiàn)了2次。請寫程序輸出任意一個(gè)只出現(xiàn)一次的數(shù)字，程序時(shí)間和空間復(fù)雜度越小越好。例如： 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、是某個(gè)數(shù)從右往左掃描第一次出現(xiàn)1的位置intlowbit(intx)returnx&(x-1);voidfind(int*a,intn)inti,xors;xors=0;for(i=0;in;+i)xors=ai;/三個(gè)數(shù)兩兩的異或后lowbit有兩個(gè)相同，一個(gè)不同，可以分為兩組intfips=0;for(i=0;in;+i)fips=lowbit(xorsai);/表示的是：flips=lowbit(ab)lowbit(ac)lowbit(bc)intb;/假設(shè)三個(gè)只出現(xiàn)一次的其中一個(gè)數(shù)為bb=0;for(i=0;in;+i)if(lowbit(xorsai)=fips)b=ai;/成功找到

6、三個(gè)數(shù)中一個(gè)數(shù)coutbendl;3、朋友圈（25分）假如已知有n個(gè)人和m對好友關(guān)系（存于數(shù)字r）。如果兩個(gè)人是直接或間接的好友（好友的好友的好友.），則認(rèn)為他們屬于同一個(gè)朋友圈，請寫程序求出這n個(gè)人里一共有多少個(gè)朋友圈。假如：n = 5 ， m = 3 ， r = 1 , 2 , 2 , 3 , 4 , 5，表示有5個(gè)人，1和2是好友，2和3是好友，4和5是好友，則1、2、3屬于一個(gè)朋友圈，4、5屬于另一個(gè)朋友圈，結(jié)果為2個(gè)朋友圈。最后請分析所寫代碼的時(shí)間、空間復(fù)雜度。評分會(huì)參考代碼的正確性和效率。C/C+：int friends(int n , int m , int* r);Java:i

7、nt friends(int n , int m , int r);cppview plaincopy/簡單的并查集應(yīng)用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;