25
積累(一)
積累(一)
C++的多態——編譯時多態與運行時多態。前者指重載（同名函數對應不同的函數體定義）；後者指虛函數（動態綁定）。
struct的成員默認是public，class的成員默認是private。
對於派生類的構造函數，在定義對象時構造函數的執行順序為？
答：1.基類的構造函數 2.成員對象所在類的構造函數 3.派生類自己的構造函數。
定義一個函數指針，指向的函數有兩個int形參並且返回一個函數指針，返回的指針指向一個有一個int形參且返回int的函數。這個函數指針的定義是：int (*(*F)(int, int))(int)；
問：有n個人，其中一個明星和n-1個群眾，群眾都認識明星，明星不認識任何群眾，群眾和群眾之間的認識關係不知道，現在如果你是機器人R2T2，你每次問一個人是否認識另外一個人的代價為O(1)，試設計一種算法找出明星，並給出時間複雜度（沒有複雜度不得分）。
答：把A認識B的關係轉化為A>B，那麼此題可以轉化為求一個集合中最小的數字。
People a[n];//n個人
{...}//重載小於號，若A認識B，則A<B為真
int fun(int a[],int n){
int tmp=0;
for(int i=1;i<n;i++)
if(a[i]<a[tmp])
tmp=i;
return tmp;
}// time complexity =O(n)
字節對齊
數論-糖果傳遞問：A和B晚上無聊就開始數星星。每次隻能數K個（20<=k<=30）A和B輪流數。最後誰把星星數完誰就獲勝，那麼當星星數量為多少時候A必勝？
問：不定項選擇：假定函數rand_k會生成一個[1,k]之間的隨機整數，並且每個結果的出現都是等概率的。現有rand_7函數，請問利用這個函數和其他運算與邏輯操作，能實現以下的哪些函數？(a b c d)
a.rand_3 b.rand_21 c.rand_23 d.rand_47
答：首先，可以生成rand_x();//x<=7
也就是說，若有rand_x,可以實現任意的rand_i; // i<=x
然後我們分析rand_49的實現。所以，可得答案。
int rand_7();//已有
int rand_x(){//x<=7
while(1){
int t=rand_7();
if(t<=x) return t;
}
}
int rand_49(){
return 7*(rand_7()-1)+rand_7();
}
/*
給出表達式: x=7*a+b (a屬於[0,6],b屬於 [1,7]
[1,49]的任意一個數x都可以唯一的對應於a,b兩個參數，所以 rand_49可實現。
*/
問：若一棵二叉樹的前序遍曆序列與後續遍曆序列分別是1,2,3,4 和 4,3,2,1，則該二叉樹的中序遍曆不會是(C)
A.1234 B.2341 C.3241 D.4321
答：先序遍曆：根、左、右；後序：左、右、根。兩次遍曆序列完全相反，說明每一個結點都不會同時有左右子樹。所以中序遍曆中‘1’隻能在頭或末，四個選項都滿足。接下來，234,2隻能在頭或末，所以C不滿足。
先序遍曆與後序不能唯一確定一棵二叉樹，但可以確定各結點的父子關係。
問：已知一棵有2011個結點的樹，其葉結點個數為116，該樹對應的二叉樹中無左右孩子的結點個數是（選項略）
答：此題為選擇題，可以舉特例，易得解。
問：若平衡二叉樹的高度為6，且所有非葉結點的平衡因子為1，則該平衡二叉樹的結點總數為(20).
答：有函數f(x)=高度為x時葉結點總數。f(2)=2,f(3)=4,配合圖形可得規律，f(x)=1+f(x-1)+f(x-2)。則f(4)=7,f(5)=12,f(6)=20。
將兩個遞增有序的鏈表合並成一個遞減有序鏈表，仍使用原節點.
最後更新：2017-04-03 12:55:46