403
積累(二)
阿裏2014實習生招聘
問：某國家非常重男輕女，若一戶人家生了一個女孩，便要繼續生，直到得到男孩為止。假設生男生女概率相等，請問平均每戶人家有（1）個女孩。
答：此題即高數中的級數。
引申：
int f(int x){
int s=0;
while(x--) s+=f(x);
return max(x,1);
}
//若調用f(35),此程序運行時間（）
若調用f(35),主流PC上此程序運行時間（D）
A.幾毫秒 B.幾秒 C.幾分鍾 D.幾小時
答：函數調用--複雜度
f(1)-1;f(2)-1;f(3)-2;f(4)-4;f(5)-8;f(6)-16;...;f(n)=pow(2,n-2);
f(35)=pow(2,33)=O(pow(10,9)),主流計算機一秒執行語句數O(pow(10,6)),一小時=O(pow(10,3)秒,相除得1,所以在小時級別。
問：將n條長度均為m的有序鏈表進行合並，合並以後的鏈表也保持有序。時間複雜度為多少？
答：
思路一：對長度為a和b的有序表進行歸並，複雜度是Ｏ（ａ＋ｂ）。構造n個權重均為m的葉結點，對其構造最優二叉樹。則樹中所有非葉結點的權值和即為所求。答案為O(n*m*log(下標：2)(真數：n)).
引申：
對長度為n的無序數組（鏈表同樣適用）進行二路歸並排序，複雜度為n*log(n).
分析：對長度為a和b的有序表進行歸並，複雜度是Ｏ（ａ＋ｂ）。
每趟歸並將有序表的數目減少一半，初始可視為n個長度為1的有序表，所以共
lg(n)/lg(2)趟歸並。
每趟歸並，調用n/(2*length)次歸並函數將n/length個長度為length的有序表進行兩兩歸並。每次歸並複雜度是Ｏ（2*length）。所以每趟歸並複雜度是O(n)。
總的複雜度為O（n*log(n)）。
思路二：等價於n*m個元素，初始狀態無序，歸並到log(下：2)(真：m)趟時，後續的複雜度。
問：ABCD四人夜裏要過一座橋，每次最多過兩人，過橋必須有手電筒。他們隻有一隻手電筒，四人過橋時間分別是1、2、5、10。問：安排最優方案，使過橋時間最短。
答：時間長的一塊過，相當於並行處理，效率高。所以：AB-A-CD-B-AB=2+1+10+2+2=17min.
有兩個鏈表A和B，試求其首個公共結點的地址。
問：判斷一棵樹是否是完全二叉樹的算法：
答：完全二叉樹具有性質——如果一個結點沒有左子樹，那麼它一定沒有右子樹。利用此性質，在廣度優先搜索中對遍曆結點逐一判斷。
問：八個人的單打比賽，選手編號由強至弱為1~8，當實力相差兩個等級內（含）才有爆冷門的可能。也就是說8號存在打敗6號的可能。這八個人進行1/4決賽、半決賽和決賽。問所有可能奪冠的選手中，編號最大的是幾號？（6）
答：尚沒發現通用解法。
問：2的100次方mod 7等於（2）。
答：公約數隻有1的兩個數，叫做互質數。
mod,取餘數運算符，7 mod 5=2;c++中為‘%’運算符。
費馬小定理：a是整數，p是質數，且a,p互質，則[a的(p-1)次方mod p]恒等於1。
此題有pow(2,6)%7=1。pow(2,100)=(2的6次方)的16次方*2的4次方，故答案為16 mod 7=2。
所謂兩棵二叉樹T1與T2相似，是指
1.都是空樹；
2.都隻有根結點；
3.T1左子樹和右子樹與T2左子樹和右子樹均相似。
驗證算法:
bool is_similar(node*t1,node*t2){//判斷兩棵樹是否相似
if(!t1&&!t2) return true;
if(!t1||!t2) return false;
if (is_similar(t1->lchild,t2->lchild)&&\
is_similar(t1->rchild,t2->rchild))
return true;
return false;
}
問：【2012研招真題】在內部排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結束都至少能夠確定一個元素最終位置的方法是（A）
a.簡單選擇排序 b.希爾排序c.快速排序d.堆排序e.二路歸並排序
A.acd B.ace C.bcd D.cde
答：簡單選擇排序每次都選擇未排序列中最小的元素放入最終位置。
希爾排序每次是對等步長的序列進行排序，得到的是局部有序。
堆排序，每趟堆頂的元素就是待排序列中最大或最小的（大根堆或小根堆)。
快速排序每趟後都將基準元素放入到最終位置。
歸並排序會得到若幹局部有序結果。
跳躍鏈表是一種隨機化數據結構，基於並聯的鏈表，其效率可比擬於二叉查找樹(對於大多數操作需要O(log n)平均時間)，並且對並發算法友好。
跳躍列表是按層建造的。底層是一個普通的有序鏈表。每個更高層都充當下麵列表的"快速跑道"，這裏在層 i 中的元素按某個固定的概率 p 出現在層 i+1 中。平均起來，每個元素都在 1/(1-p) 個列表中出現，而最高層的元素(通常是在跳躍列表前端的一個特殊的頭元素)在 O(log1/pn) 個列表中出現。
查找的總體代價是 O(log1/p n/p).
如果某係統15*4=112成立，則係統采用的是（6）進製。
答：設為x進製。由題得(x+5)*4=x*x+x+2,解得x=6.
設有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},請寫出按二路歸並方法對該序列進行一趟掃描後的結果，為？
答：D，Q，F，X，A，P，B，N，M，Y，C，W；
共12個元素，第一趟實現兩兩有序，共12/2=6對。
關鍵碼序列{Q,H,C,Y,Q,A,M,S,R,D,F,X}，要求遞增排序，若采用初始步長為4 的希爾排序，則一趟掃描的結果是？
若采用以第一個元素為基準的快速排序，則一趟排序的結果為？
答：Q,A,C,S,Q,D,F,X,R,H,M,Y;(1,5,10有序，2,6,11有序，...)
F,H,C,D,Q,A,M,Q,R,S,Y,X。(要細心)
最後更新：2017-04-03 12:56:00