一些常考的基礎知識點個人總結，大神勿噴，歡迎指正。
1.廣義表的表尾是指除去表頭後剩下的元素組成的表，表頭可以為表或單元素值.表尾或為表，或為空表。
2.構造函數不能聲明為虛函數。
構造函數為什麼不能是虛函數？
1. 從存儲空間角度，虛函數對應一個指向vtable虛函數表的指針，這大家都知道，可是這個指向vtable的指針其實是存儲在對象的內存空間的。問題出來了，如果構造函數是虛的，就需要通過 vtable來調用，可是對象還沒有實例化，也就是內存空間還沒有，怎麼找vtable呢？所以構造函數不能是虛函數。
2. 從使用角度，虛函數主要用於在信息不全的情況下，能使重載的函數得到對應的調用。構造函數本身就是要初始化實例，那使用虛函數也沒有實際意義呀。所以構造函數沒有必要是虛函數。虛函數的作用在於通過父類的指針或者引用來調用它的時候能夠變成調用子類的那個成員函數。而構造函數是在創建對象時自動調用的，不可能通過父類的指針或者引用去調用，因此也就規定構造函數不能是虛函數。
3. 構造函數不需要是虛函數，也不允許是虛函數，因為創建一個對象時我們總是要明確指定對象的類型，盡管我們可能通過基類的指針或引用去訪問它但析構卻不一定，我們往往通過基類的指針來銷毀對象。這時候如果析構函數不是虛函數，就不能正確識別對象類型從而不能正確調用析構函數。
4. 從實現上看，vbtl在構造函數調用後才建立，因而構造函數不可能成為虛函數從實際含義上看，在調用構造函數時還不能確定對象的真實類型（因為子類會調父類的構造函數）；而且構造函數的作用是提供初始化，在對象生命期只執行一次，不是對象的動態行為，也沒有必要成為虛函數。
5. 當一個構造函數被調用時，它做的首要的事情之一是初始化它的VPTR。因此，它只能知道它是“當前”類的，而完全忽視這個對象後面是否還有繼承者。當編譯器為這個構造函數產生代碼時，它是為這個類的構造函數產生代碼——既不是為基類，也不是為它的派生類（因為類不知道誰繼承它）。所以它使用的VPTR必須是對於這個類的VTABLE。而且，只要它是最後的構造函數調用，那麼在這個對象的生命期內，VPTR將保持被初始化為指向這個VTABLE, 但如果接著還有一個更晚派生的構造函數被調用，這個構造函數又將設置VPTR指向它的 VTABLE，等.直到最後的構造函數結束。VPTR的狀態是由被最後調用的構造函數確定的。這就是為什麼構造函數調用是從基類到更加派生類順序的另一個理由。但是，當這一系列構造函數調用正發生時，每個構造函數都已經設置VPTR指向它自己的VTABLE。如果函數調用使用虛機制，它將只產生通過它自己的VTABLE的調用，而不是最後的VTABLE（所有構造函數被調用後才會有最後的VTABLE）。
3.二叉樹的相關概念：
深度：樹的層數；
度：（對節點來說是）一個節點的孩子數；（對整棵樹來說是）其節點的度的最大值。
完全二叉樹： 將滿二叉樹從右向左刪除節點所得的二叉樹為完全二叉樹。
如果一棵樹有 n 個 葉子節點，那麼 度為2的節點 就有 n -1個。如果我們知道一棵完全二叉樹有 n 個葉子節點，那麼它的節點數最多 2n 個。
任何二叉樹中度為0的結點比度為2的結點多一個。
4.堆的插入元素是在最後插入，然後進行調整堆；刪除元素是把最後的元素放到刪除元素的地方，然後進行調整堆。
5.由先序遍歷和中序遍歷可以唯一確定二叉樹，確定方法是：由先序序列確定根節點；按根節點把中序序列分為兩端，前面的是左子樹，後面的是右子樹；對左右子樹重復前面的步驟還原樹形結構。
6.printf是從右向左壓入棧，先運行右側項，再運行左側項。例如printf(“%d,%d”,a,++a);輸出的結果應該是兩個相等的值（都是a+1以後的值）。
7.在寫判斷語句時最好將一個右值放在= =左側，而把左值放在右側，因為這樣可以檢查出誤寫成賦值運算符的情況。
8.所有的ASCII碼都可以用“\”加數字（一般是8進制數字）來表示。因此看到\後跟三位數字的時候要明白這是一個字符。
9.在二叉樹結點的前序序列、中序序列和後序序列中,所有葉結點的先後順序完全相同。
10.一種類型a至少提供另外一種類型t的行為,那麼a類型就是b類型的子類型。公有繼承的派生類就是基類的子類型。類a是類b的子類型,意味著類a適應類b,即:類a對象可以使用的場合同樣適合類b的對象。
11.拓撲排序常用來確定一個依賴關系集中，事物發生的順序。拓撲排序得出的線性序列，只要能滿足排在前面的任務先完成即可，例如V1→V2，序列中只要V1在V2前面即可（所以得出的序列可能不唯一）。
12.一棵非空的二叉樹的先序遍歷序列與後序遍歷序列正好相反，則該二叉樹一定滿足只有一個葉子節點。
13.++ 是一目運算符，自增運算，它只能用於一個變量，即變量值自增1， 不能用於表達式。++運算符有個很有意思的特點，前置++返回的為左值對象，可以在一個運算式中多次使用例如++++i，但是後置++則返回右值，無法在一個運算式中多次使用後置++（對於- -是一樣的），由於無法對右值進行自增運算，因此一個對象一旦後置自增後就不能再被當前式中自增。（可以在下次自增）可以這樣理解：前置運算將對象返回了，該對象的值為自增以後的，而後置操作返回的是一個值，而不是一個對象，對象自身自增了，但是並沒有返回。
14.對任意一棵樹,設它有n個結點,這n個結點的度數之和為n-1.
15.多型數據類型是指包含的數據元素的類型並不確定。
16.一個char占用一個字節，一個short占用2個字節，一個int占用4個字節。
17.三種數據的存儲區：局部變量存儲在棧，全局變量及靜態變量存儲在靜態存儲區，動態分配對象存儲在堆區（動態存儲區）。
18.對一個數組使用取地址符號，返回的是一個指向整個數組（而不是首元素）的指針，對於指向數組首元素的指針，只需要直接將數組賦值給指針即可。例如int a[]={1,2,3,4};&a 返回的是int （*）[4]即數組指針類型。
19.字符類型占1字節， 可以從任何地址開始，short類型占2字節， 必須從2字節倍數地址開始，int類型占4字節，必須從4字節倍數地址開始。
20.結構體在內存組織上是順序式的，聯合體則是重疊式，各成員共享一段內存，所以整個聯合體的sizeof也就是每個成員sizeof的最大值。（需要考慮對齊）。
21.在無向圖中，如果從頂點vi到頂點vj有路徑，則稱vi和vj連通。如果圖中任意兩個頂點之間都連通，則稱該圖為連通圖，否則，稱該圖為非連通圖，則其中的極大連通子圖稱為連通分量，這裡所謂的極大是指子圖中包含的頂點個數極大。
22.純虛函數是在基類聲明的虛函數，它在基類中沒有定義，但是要求派生類都要定義自己的實現方法。在基類中實現純虛函數的方法是在函數原型後面添加“=0”
23.比如 virtual void f()=0;
24.而c++中包含純虛函數的類稱為抽象類，由於抽象類中包含了沒有定義的純虛函數，所以不能定義抽象類的對象。總結：1.抽象類只能用作其他類的基類，不能定義抽象類的對象。2.抽象類不能用於參數類型、函數返回值或顯示轉換的類型3.抽象類可以定義抽象類的指針和引用，此指針可以指向它的派生類，進而實現多態性。
25.堆內存和棧內存的區別：1.棧內存由操作系統分配，堆內存由程序員自己分配。2棧內存空間大小是固定的，堆的大小受限於系統中有效地虛擬內存。3棧的空間由系統決定合適釋放，堆內存需要自己決定何時釋放。4堆的使用容易產生碎片，但是使用方便。
26.宏定義問題：#define是宏定義，該定義只是做簡單轉換，不會執行高級數學運算包括運算律，例如#defineA 2；#define B A+1;#define C (B+1)*B/2將執行操作（2+1+1）*2+1/2=8，而不是按照正常的數學運算優先級。
27.不同的數據類型在32位和64位下所占字節的區別
32位編譯器：
char ：1個字節
char*（即指針變量）: 4個字節（32位的尋址空間是2^32, 即32個bit，也就是4個字節。同理64位編譯器）
short int : 2個字節
int： 4個字節
unsigned int : 4個字節
float: 4個字節
double: 8個字節
long: 4個字節
long long: 8個字節
unsigned long: 4個字節
64位編譯器：
char ：1個字節
char*(即指針變量): 8個字節
short int : 2個字節
int： 4個字節
unsigned int : 4個字節
float: 4個字節
double: 8個字節
long: 8個字節
long long: 8個字節
unsigned long: 8個字節
28.將樹T轉換成二叉樹B之後，那麼對於B中的某個節點N：
（1）如果存在左子樹，則該左子樹一定來自於N在樹T中的長子;
（2）如果存在右子樹，則該右子樹一定來自於N在樹T中鄰接右兄弟；
29.自動變量，只在定義它們的時候才創建，在定義它們的函數返回時系統回收變量所占存儲空間。對這些變量存儲空間的分配和回收是由系統自動完成的。一般情況下，不作專門說明的局部變量，均是自動變量。自動變量也可用關鍵字auto作出說明。
30.對於堆來講，生長方向是向上的，也就是向著內存地址增加的方向；對於棧來講，它的生長方向是向下的，是向著內存地址減小的方向增長。
31.線索化二叉樹利用了一個節點數為n的二叉樹種空指針域有n-1個的特點，將空指針域指向特定類型的前驅或後繼（先序、中序、後序）若一個節點左子樹為空，則將左子樹指向其前驅，若右子樹為空，則將右子樹指針指向其後繼（根據序的要求）。
若向平衡二叉樹中插入一個新結點後破壞了平衡二叉樹的平衡性。首先要找出插入新結點後失去平衡的最小子樹根結點的指針。然後再調整這個子樹中有關結點之間的鏈接關系，使之成為新的平衡子樹。當失去平衡的最小子樹被調整為平衡子樹後，原有其他所有不平衡子樹無需調整，整個二叉排序樹就又成為一棵平衡二叉樹。
失去平衡的最小子樹是指以離插入結點最近，且平衡因子絕對值大於1的結點作為根的子樹。假設用A表示失去平衡的最小子樹的根結點，則調整該子樹的操作可歸納為下列四種情況。
（1）LL型平衡旋轉法
由於在A的左孩子B的左子樹上插入結點F，使A的平衡因子由1增至2而失去平衡。故需進行一次順時針旋轉操作。即將A的左孩子B向右上旋轉代替A作為根結點，A向右下旋轉成為B的右子樹的根結點。而原來B的右子樹則變成A的左子樹。
（2）RR型平衡旋轉法
由於在A的右孩子C的右子樹上插入結點F，使A的平衡因子由-1減至-2而失去平衡。故需進行一次逆時針旋轉操作。即將A的右孩子C向左上旋轉代替A作為根結點，A向左下旋轉成為C的左子樹的根結點。而原來C的左子樹則變成A的右子樹。
（3）LR型平衡旋轉法
由於在A的左孩子B的右子數上插入結點F，使A的平衡因子由1增至2而失去平衡。故需進行兩次旋轉操作（先逆時針，後順時針）。即先將A結點的左孩子B的右子樹的根結點D向左上旋轉提升到B結點的位置，然後再把該D結點向右上旋轉提升到A結點的位置。即先使之成為LL型，再按LL型處理。
如圖中所示，即先將圓圈部分先調整為平衡樹，然後將其以根結點接到A的左子樹上，此時成為LL型，再按LL型處理成平衡型。
（4）RL型平衡旋轉法
由於在A的右孩子C的左子樹上插入結點F，使A的平衡因子由-1減至-2而失去平衡。故需進行兩次旋轉操作（先順時針，後逆時針），即先將A結點的右孩子C的左子樹的根結點D向右上旋轉提升到C結點的位置，然後再把該D結點向左上旋轉提升到A結點的位置。即先使之成為RR型，再按RR型處理。
如圖中所示，即先將圓圈部分先調整為平衡樹，然後將其以根結點接到A的左子樹上，此時成為RR型，再按RR型處理成平衡型。
平衡化靠的是旋轉。參與旋轉的是3個節點（其中一個可能是外部節點NULL），旋轉就是把這3個節點轉個位置。注意的是，左旋的時候p->right一定不為空，右旋的時候p->left一定不為空，這是顯而易見的。
如果從空樹開始建立，並時刻保持平衡，那麼不平衡只會發生在插入刪除操作上，而不平衡的標志就是出現bf == 2或者bf == -2的節點。
32.棧有兩種存儲方法：一是順序棧；二是鏈式棧。棧的順序存儲結構是利用一組地址連續的存儲單元依次存儲自棧底到棧頂的數據元素，同時附設指針top指示棧頂元素的位置。由於棧的操作是線性表操作的特例，相對而言，鏈式棧的操作更易於實現。
33.注意邏輯與或運算的規則，若與運算左操作數為假，則不再執行右操作數（直接返回假），同理，若或運算左操作數為真，則不再執行右操作數（直接返回真）。
34. 排序算法特點總結：
35.final修飾符
如果一個類被聲明為final，意味著它不能再派生出新的子類，不能作為父類被繼承。因此一個類不能既被聲明為abstract的，又被聲明為final的。將變量或方法聲明為final，可以保證它們在使用中不被改變。被聲明為final的變量必須在聲明時給定初值，而在以後的引用中只能讀取，不可修改。
finally
異常處理時提供 finally 塊來執行任何清除操作。如果拋出一個異常，那麼相匹配的 catch 子句就會執行，然後控制就會進入 finally 塊（如果有的話）。一般異常處理塊需要方法名。
finalize
Java 技術允許使用 finalize() 方法在垃圾收集器將對象從內存中清除出去之前做必要的清理工作。這個方法是由垃圾收集器在確定這個對象沒有被引用時對這個對象調用的。它是在Object 類中定義的，因此所有的類都繼承了它。子類覆蓋finalize() 方法以整理系統資源或者執行其他清理工作。finalize() 方法是在垃圾收集器刪除對象之前對這個對象調用的。 Java中所有類都從Object類中繼承finalize()方法。當垃圾回收器(garbage colector)決定回收某對象時，就會運行該對象的finalize()方法。
36.注意free一個指針和delete一個指針是不同的，前者釋放一個指針，free 掉一個指針後，指針仍然指向原來的地址。free 的意義在於告訴系統目標地址可以被回收。而delete則是將指針刪除。
37. 即使是最簡單的虛函數調用，編譯器的內聯處理程序對它也愛莫能助。（這一點也不奇怪。virtual的意思是"等到運行時再決定調用哪個函數"，inline的意思是"在編譯期間將調用之處用被調函數來代替"，如果編譯器甚至還不知道哪個函數將被調用，當然就不能責怪它拒絕生成內聯調用了）。
38. 宏定義和const的區別：
（1） 編譯器處理方式不同，define宏是在預處理階段展開，const常量在編譯運行階段展開。
（2） 類型和安全檢查不同，define宏沒有類型，不做任何檢查，僅僅是展開，const常量具有具體的類型，在編譯階段會執行類型檢查。
（3） 存儲方式不同，define宏僅僅是展開，有多少地方使用就展開多少次，const常量會存儲在內存中分配，僅僅生成一次。（const可以節省空間，避免不必要的內存分配，提高了效率）。
在C++ 程序中只使用const常量而不使用宏常量，即const常量完全取代宏常量。
39. 函數reserve（size）將字符串的容量設置為至少size。如果size所指定的數值小於當前字符串中的字符數，容量將被設置為恰好容納字符的數值。reserve()以線性時間運行。其最大用處是為了避免反復重新分配緩沖區內存而導致效率降低，或者在使用某些STL操作之前保證緩沖區足夠大。
40. 關於final的重要知識點;
（1） final關鍵字可以用於成員變量、本地變量、方法以及類。
（2） final成員變量必須在聲明的時候初始化或者在構造器中初始化，否則就會報編譯錯誤。
（3） 你不能夠對final變量再次賦值。
（4） 本地變量必須在聲明時賦值。
（5） 在匿名類中所有變量都必須是final變量。
（6） final方法不能被重寫。
（7） final類不能被繼承。
（8） 沒有在聲明時初始化final變量的稱為空白final變量(blank final variable)，它們必須在構造器中初始化，或者調用this()初始化。不這麼做的話，編譯器會報錯“final變量(變量名)需要進行初始化”。
41. 只要兩個操作數中有一個是double類型的，另一個將會被轉換成double類型，並且結果也是double類型，如果兩個操作數中有一個是float類型的，另一個將會被轉換為float類型，並且結果也是float類型，如果兩個操作數中有一個是long類型的，另一個將會被轉換成long類型，並且結果也是long類型，否則（操作數為：byte、short、int 、char），兩個數都會被轉換成int類型，並且結果也是int類型。
42. 非法指針是指向的內存已被回收，或者指向一個錯誤的地址。
43. 擁有虛函數的類存儲時首地址存儲為虛函數指針，其次是成員變量。
44. 一般的當將一個類對象指針轉化為其他類型指針時，指針自身不變，只是將讀取地址的方式進行了轉變，指針指向還是之前那個位置。
45. 在重載一個運算符為成員函數時，其參數表中沒有任何參數，這說明該運算符是前綴一元運算符，若參數列表中有一個int，則為後綴一元運算符。
46. 對字符串進行sizeof操作的時候，會把字符串的結束符"\0"計算進去的，進行strlen操作求字符串的長度的時候，不計算\0。
47. B樹的定義是這樣的，一棵m階的B樹滿足下列條件：(1)每個結點至多有m棵子樹；(2)除根結點外，其他每個非葉子結點至少有m/2棵子樹；(3)若根結點不是葉子結點，則至少有兩棵子樹；(4)所有葉結點在同一層上。B樹的葉結點可以看成一種外部結點，不包含任何信息；(5)所有的非葉子結點中包含的信息數據為：(n,p0,k1,p1,k2,P2,…，kj-1,Pj-1)其中，ki為關鍵字，且滿足kiki+1;pi為指向子樹根結點的指針，並且Pi-1所指的子樹中的所有結點的關鍵字均小於ki，Pj-1所指的子樹中的所有結點的關鍵字均大於kj-1。B+樹是應文件系統所需而出現的一種B樹的變型樹，其主要區別是一棵非葉子結點有n個子樹就有n個關鍵字，這些關鍵字的作用是索引；所有的葉子結點包含了全部關鍵字的信息，以及指向這些關鍵字記錄的指針，且葉子結點本身的關鍵字的大小自小而大順序鏈接。從上述的特點中我們知道，這兩種樹都是平衡的多分樹，它們都可以用於文件的索引結構，但B樹只能支持隨機檢索，而B+樹是有序的樹，既能支持隨機檢索，又能支持順序檢索。
48. 在同一個運算式中使用對同一個變量使用後置++，在當前表達式中調用的為變化前的對象，不管使用多少次。而前置++則每次都會改變變量。但是在當前運算式結束後，原變量均發生變化。例如x=1;y=(x++)+(x++);得到的y=2;x=3
49. 在c++STL中list使用了鏈式數據結構，而map 使用了紅黑樹的數據結構。
50. Byte是字節，bit是位。
51. 字節對齊規則指出對一個結構體而言，其起始地址和大小必須是對齊數的正數倍，而其中成員的所占空間滿足各自的對其規則，在需要時進行必要的填充。
