參加2012人人網校園招聘的人真多。今年找工作的人好多啊。
C++筆試題目。
1.算法的幾個概念：時間復雜度，空間復雜度等等。
2.采用鏈地址法處理長度的時候，哈希表查找成功的平均長度與哪些因素有關？
哈希表的裝填因子有關。
裝填因子= 表中填入的記錄數/哈希表的長度。
3.二叉樹節點的計算：
二叉樹中度為1的節點有8個，度為0的節點有3個，問這顆二叉樹總共有多少節點？
對於任意一棵二叉樹BT，如果度為0的結點個數為n0，度為2的結點個數為n2，則n0=n2+1。
所以度為2的節點個數為3-1 = 2，那麼總共的結點個數就是3+2+8 = 13。
順便復習一下完全二叉樹的計算。
完全二叉樹有一個特點，就是度為1的節點數要麼為1，要麼為0。可以自己畫出圖來看看。
問題：如果設一棵完全二叉樹共有500個結點，則在該二叉樹中有多少個葉子結點？
設葉子節點數為n0,度為2的節點數為n0 - 1,又因為是完全二叉樹，所以n1 = 1或者0
n0 + n1 + n2 = 500，帶入 2n0 - 1 + n1 = 500,故n1 = 1,n0 = 250, n2 = 249。
5.最小生成樹的問題，節點個數計算問題。
6.在序列有序的情況下，快速排序的時間復雜度是多少？
O(n^2)。
7.網卡完成那一層的功能？
網卡工作在物理層和數據鏈路層的MAC子層。
http://www.linuxidc.com/Linux/2012-12/77132.htm 。
8.模板函數的使用。
template <typename T>
T add(T x, T y){
return x + y;
}
A.add(5,2)
B.add(5.2,2.2)
C.add<float>(5.2,2)
D.add(5.2,2)
D是錯誤的，因為編譯器知道要特化哪一個了。
8.構造函數可以重載麼？析構函數可以重載麼？
構造不重載，怎麼實現多樣化？
析構怎麼重載，沒有參數。
10.C++靜態成員和非靜態成員有什麼區別？
1)靜態變量是屬於類的,只能用classname::來調用.而非靜態是屬於對象的,必須通過對象
來調用.
2)如果在函數中聲明一個靜態變量的話,它存儲在非函數的活動區.就是它不隨函數調用的
結束而釋放內存空間,所以它也具有全局變量的特點.但是和全局變量相比不同在於它只能在本
文件中使用
11.空類的大小？一個含有虛函數的類大小？為什麼？
分別是1和4。
因為，對於空類，C++編譯器會制定一個char來占據位置。
含有虛函數的類，裡面會存放一個虛函數指針vptr，指向一個虛函數表。指針在32位平台上
的大小為4個字節。
12 OSI七層模型和TCP/IP 五層模型。
應用層
表示層
會話層 應用層
傳輸層 傳輸層
網絡層 互聯網絡層
數據鏈路層 互聯接口層
物理層 物理層
12.編程求解走樓梯問題：
一個人一次可以上1步，2步，3步。現在有n個階梯（1<= n <= 100W，問有方法可以上去？
）
f(1) = 1;
f(2) = 2;
f(3) = 4;
n > 3,f(n) = f(n - 1) + f(n - 2) + f(n -3)
13.人人網的朋友概念：A和B是朋友，B和C是朋友，那麼A和C是二度朋友。
找出每一個人的10度朋友。要求O(n)的算法
14.推薦系統的設計