一、編程語言
1.根據(jù)熟悉的語言，談?wù)剝煞N語言的區(qū)別？
主要淺談下C/C++和PHP語言的區(qū)別:
1)PHP弱類型語言，一種腳本語言，對數(shù)據(jù)的類型不要求過多，較多的應(yīng)用于Web應(yīng)用開發(fā)，現(xiàn)在好多互聯(lián)網(wǎng)開發(fā)公司的主流web后臺開發(fā)語言，主要框架為mvc模型，如smarty,yaf，升級的PHP7速度較快，對服務(wù)器的壓力要小很多，在新浪微博已經(jīng)有應(yīng)用，對比很明顯。
2)C/C++開發(fā)語言，C語言更偏向硬件底層開發(fā)，C++語言是目前為止我認(rèn)為語法內(nèi)容最多的一種語言。C/C++在執(zhí)行速度上要快很多，畢竟其他類型的語言大都是C開發(fā)的，更多應(yīng)用于網(wǎng)絡(luò)編程和嵌入式編程。
2.volatile是干啥用的，（必須將cpu的寄存器緩存機制回答的很透徹），使用實例有哪些？（重點）
1）訪問寄存器比訪問內(nèi)存單元要快,編譯器會優(yōu)化減少內(nèi)存的讀取，可能會讀臟數(shù)據(jù)。聲明變量為volatile，編譯器不再對訪問該變量的代碼優(yōu)化，仍然從內(nèi)存讀取，使訪問穩(wěn)定。
總結(jié)：volatile關(guān)鍵詞影響編譯器編譯的結(jié)果，用volatile聲明的變量表示該變量隨時可能發(fā)生變化，與該變量有關(guān)的運算，不再編譯優(yōu)化，以免出錯。
2）使用實例如下(區(qū)分C程序員和嵌入式系統(tǒng)程序員的最基本的問題。)：
并行設(shè)備的硬件寄存器（如：狀態(tài)寄存器）
一個中斷服務(wù)子程序中會訪問到的非自動變量(Non-automatic variables)
多線程應(yīng)用中被幾個任務(wù)共享的變量
3)一個參數(shù)既可以是const還可以是volatile嗎？解釋為什么。
可以。一個例子是只讀的狀態(tài)寄存器。它是volatile因為它可能被意想不到地改變。它是const因為程序不應(yīng)該試圖去修改它。
4）一個指針可以是volatile 嗎？解釋為什么。
可以。盡管這并不很常見。一個例子當(dāng)中斷服務(wù)子程序修該一個指向一個buffer的指針時。
下面的函數(shù)有什么錯誤：
int square(volatile int *ptr) {
return *ptr * *ptr;
}
下面是答案：
這段代碼有點變態(tài)。這段代碼的目的是用來返指針*ptr指向值的平方，但是，由于*ptr指向一個volatile型參數(shù)，編譯器將產(chǎn)生類似下面的代碼：
int square(volatile int *ptr){
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}
由于*ptr的值可能被意想不到地該變，因此a和b可能是不同的。結(jié)果，這段代碼可能返不是你所期望的平方值！正確的代碼如下：
long square(volatile int *ptr){
int a;
a = *ptr;
return a * a;
}
3.static const等等的用法，（能說出越多越好）（重點）
2 首先說說const的用法（絕對不能說是常數(shù)）
1）在定義的時候必須進行初始化
2）指針可以是const 指針，也可以是指向const對象的指針
3）定義為const的形參，即在函數(shù)內(nèi)部是不能被修改的
4）類的成員函數(shù)可以被聲明為常成員函數(shù)，不能修改類的成員變量
5）類的成員函數(shù)可以返回的是常對象，即被const聲明的對象
6）類的成員變量是常成員變量不能在聲明時初始化，必須在構(gòu)造函數(shù)的列表里進行初始化
（注：千萬不要說const是個常數(shù)，會被認(rèn)為是外行人的?。。?！哪怕說個只讀也行）
下面的聲明都是什么意思？
const int a; a是一個常整型數(shù)
int const a; a是一個常整型數(shù)
const int *a; a是一個指向常整型數(shù)的指針，整型數(shù)是不可修改的，但指針可以
int * const a; a為指向整型數(shù)的常指針，指針指向的整型數(shù)可以修改，但指針是不可修改的
int const * a const; a是一個指向常整型數(shù)的常指針，指針指向的整型數(shù)是不可修改的，同時指針也是不可修改的
通過給優(yōu)化器一些附加的信息，使用關(guān)鍵字const也許能產(chǎn)生更緊湊的代碼。合理地使用關(guān)鍵字const可以使編譯器很自然地保護那些不希望被改變的參數(shù)，防止其被無意的代碼修改。簡而言之，這樣可以減少bug的出現(xiàn)。
Const如何做到只讀？
這些在編譯期間完成，對于內(nèi)置類型，如int， 編譯器可能使用常數(shù)直接替換掉對此變量的引用。而對于結(jié)構(gòu)體不一定。
2 再說說static的用法（三個明顯的作用一定要答出來）
1）在函數(shù)體，一個被聲明為靜態(tài)的變量在這一函數(shù)被調(diào)用過程中維持其值不變。
2）在模塊內(nèi)（但在函數(shù)體外），一個被聲明為靜態(tài)的變量可以被模塊內(nèi)所用函數(shù)訪問，但不能被模塊外其它函數(shù)訪問。它是一個本地的全局變量。
3）在模塊內(nèi)，一個被聲明為靜態(tài)的函數(shù)只可被這一模塊內(nèi)的其它函數(shù)調(diào)用。那就是，這個函數(shù)被限制在聲明它的模塊的本地范圍內(nèi)使用
4）類內(nèi)的static成員變量屬于整個類所擁有，不能在類內(nèi)進行定義，只能在類的作用域內(nèi)進行定義
5）類內(nèi)的static成員函數(shù)屬于整個類所擁有，不能包含this指針，只能調(diào)用static成員函數(shù)
static全局變量與普通的全局變量有什么區(qū)別?static局部變量和普通局部變量有什么區(qū)別?static函數(shù)與普通函數(shù)有什么區(qū)別?
static全局變量與普通的全局變量有什么區(qū)別：static全局變量只初使化一次，防止在其他文件單元中被引用;
static局部變量和普通局部變量有什么區(qū)別：static局部變量只被初始化一次，下一次依據(jù)上一次結(jié)果值；
static函數(shù)與普通函數(shù)有什么區(qū)別：static函數(shù)在內(nèi)存中只有一份，普通函數(shù)在每個被調(diào)用中維持一份拷貝
4.extern c 作用
告訴編譯器該段代碼以C語言進行編譯。
5.指針和引用的區(qū)別
1）引用是直接訪問，指針是間接訪問。
2）引用是變量的別名，本身不單獨分配自己的內(nèi)存空間，而指針有自己的內(nèi)存空間
3）引用綁定內(nèi)存空間（必須賦初值），是一個變量別名不能更改綁定，可以改變對象的值。
總的來說：引用既具有指針的效率，又具有變量使用的方便性和直觀性
6. 關(guān)于靜態(tài)內(nèi)存分配和動態(tài)內(nèi)存分配的區(qū)別及過程
1) 靜態(tài)內(nèi)存分配是在編譯時完成的，不占用CPU資源；動態(tài)分配內(nèi)存運行時完成，分配與釋放需要占用CPU資源；
2)靜態(tài)內(nèi)存分配是在棧上分配的，動態(tài)內(nèi)存是堆上分配的；
3)動態(tài)內(nèi)存分配需要指針或引用數(shù)據(jù)類型的支持，而靜態(tài)內(nèi)存分配不需要；
4)靜態(tài)內(nèi)存分配是按計劃分配，在編譯前確定內(nèi)存塊的大小，動態(tài)內(nèi)存分配運行時按需分配。
5)靜態(tài)分配內(nèi)存是把內(nèi)存的控制權(quán)交給了編譯器，動態(tài)內(nèi)存把內(nèi)存的控制權(quán)交給了程序員；
6)靜態(tài)分配內(nèi)存的運行效率要比動態(tài)分配內(nèi)存的效率要高，因為動態(tài)內(nèi)存分配與釋放需要額外的開銷；動態(tài)內(nèi)存管理水平嚴(yán)重依賴于程序員的水平，處理不當(dāng)容易造成內(nèi)存泄漏。
7. 頭文件中的 ifndef/define/endif 干什么用？
預(yù)處理，防止頭文件被重復(fù)使用，包括pragma once都是這樣的
8. 宏定義求兩個元素的最小值
#define MIN(A,B) （（A） <= (B) ? (A) : (B))
9. 分別設(shè)置和清除一個整數(shù)的第三位？
#define BIT3 (0x1<<3)
static int a;
void set_bit3(void){
a |= BIT3;
}
void clear_bit3(void){
a &= ~BIT3;
}
10. 用預(yù)處理指令#define 聲明一個常數(shù)，用以表明1年中有多少秒
#define SECONDS_PER_YEAR (60 * 60 * 24 * 365)UL
11. 預(yù)處理器標(biāo)識#error的目的是什么？
拋出錯誤提示，標(biāo)識外部宏是否被定義!
12. 嵌入式系統(tǒng)中經(jīng)常要用到無限循環(huán)，你怎么樣用C編寫死循環(huán)呢？
記住這是第一方案?。。?！
while(1)
{
}
一些程序員更喜歡如下方案：
for(;;){
}
匯編語言的無線循環(huán)是：
Loop:
...
goto Loop;
13. 用變量a給出下面的定義
一個有10個指針的數(shù)組，該指針指向一個函數(shù)，該函數(shù)有一個整型參數(shù)并返回一個整型數(shù) int (*a[10])(int);
14. 中斷是嵌入式系統(tǒng)中重要的組成部分，這導(dǎo)致了很多編譯開發(fā)商提供一種擴展—讓標(biāo)準(zhǔn)C支持中斷。具代表事實是，產(chǎn)生了一個新的關(guān)鍵字 __interrupt
16. memcpy函數(shù)的實現(xiàn)
void *memcpy(void *dest, const void *src, size_t count) {
char *tmp = dest;
const char *s = src;
while (count--)
*tmp++ = *s++;
return dest;
}
17. Strcpy函數(shù)實現(xiàn)
char *strcpy(char *dst,const char *src) {
assert(dst != NULL && src != NULL);
char *ret = dst;
while((* dst++ = * src++) != '\0') ;
return ret;
}
18. strcat函數(shù)的實現(xiàn)
char *strcat(char *strDes, const char *strSrc){
assert((strDes != NULL) && (strSrc != NULL));
char *address = strDes;
while (*strDes != ‘\0′)
++ strDes;
while ((*strDes ++ = *strSrc ++) != ‘\0′)
return address;
}
19．strncat實現(xiàn)
char *strncat(char *strDes, const char *strSrc, int count){
assert((strDes != NULL) && (strSrc != NULL));
char *address = strDes;
while (*strDes != ‘\0′)
++ strDes;
while (count — && *strSrc != ‘\0′ )
*strDes ++ = *strSrc ++;
*strDes = ‘\0′;
return address;
}
20. strcmp函數(shù)實現(xiàn)
int strcmp(const char *str1,const char *str2){
/*不可用while(*str1++==*str2++)來比較，當(dāng)不相等時仍會執(zhí)行一次++，
return返回的比較值實際上是下一個字符。應(yīng)將++放到循環(huán)體中進行。*/
while(*str1 == *str2){
if(*str1 == '\0')
return0;
++str1;
++str2;
}
return *str1 - *str2;
}
21. strncmp實現(xiàn)
int strncmp(const char *s, const char *t, int count){
assert((s != NULL) && (t != NULL));
while (*s && *t && *s == *t && count –) {
++ s;
++ t;
}
return (*s – *t);
}
22.strlen函數(shù)實現(xiàn)
int strlen(const char *str){
assert(str != NULL);
int len = 0;
while (*str ++ != ‘\0′)
++ len;
return len;
}
23. strpbrk函數(shù)實現(xiàn)
char * strpbrk(const char * cs,const char * ct){
const char *sc1,*sc2;
for( sc1 = cs; *sc1 != '\0'; ++sc1){
for( sc2 = ct; *sc2 != '\0'; ++sc2){
if (*sc1 == *sc2){
return (char *) sc1;
}
}
}
return NULL;
}
24. strstr函數(shù)實現(xiàn)
char *strstr(const char *s1,const char *s2){
int len2;
if(!(len2=strlen(s2)))//此種情況下s2不能指向空，否則strlen無法測出長度，這條語句錯誤
return(char*)s1;
for(;*s1;++s1)
{
if(*s1==*s2 && strncmp(s1,s2,len2)==0)
return(char*)s1;
}
return NULL;
}
25. string實現(xiàn)（注意：賦值構(gòu)造，operator=是關(guān)鍵）
class String{
public:
//普通構(gòu)造函數(shù)
String(const char *str = NULL);
//拷貝構(gòu)造函數(shù)
String(const String &other);
//賦值函數(shù)
String & operator=(String &other) ;
//析構(gòu)函數(shù)
~String(void);
private:
char* m_str;
};
分別實現(xiàn)以上四個函數(shù)
//普通構(gòu)造函數(shù)
String::String(const char* str){
if(str==NULL) //如果str為NULL，存空字符串{
m_str = new char[1]; //分配一個字節(jié)
*m_str = ‘\0′; //賦一個’\0′
}else{
str = new char[strlen(str) + 1];//分配空間容納str內(nèi)容
strcpy(m_str, str); //復(fù)制str到私有成員m_str中
}
}
//析構(gòu)函數(shù)
String::~String(){
if(m_str!=NULL) //如果m_str不為NULL，釋放堆內(nèi)存{
delete [] m_str;
m_str = NULL;
}
}
//拷貝構(gòu)造函數(shù)
String::String(const String &other){
m_str = new char[strlen(other.m_str)+1]; //分配空間容納str內(nèi)容
strcpy(m_str, other.m_str); //復(fù)制other.m_str到私有成員m_str中
}
//賦值函數(shù)
String & String::operator=(String &other){
if(this == &other) //若對象與other是同一個對象，直接返回本{
return *this
}
delete [] m_str; //否則，先釋放當(dāng)前對象堆內(nèi)存
m_str = new char[strlen(other.m_str)+1]; //分配空間容納str內(nèi)容
strcpy(m_str, other.m_str); //復(fù)制other.m_str到私有成員m_str中
return *this；
}
26. C語言同意一些令人震驚的結(jié)構(gòu),下面的結(jié)構(gòu)是合法的嗎，如果是它做些什么？
int a = 5, b = 7, c;
c = a+++b; 等同于 c = a++ + b;
因此, 這段代碼持行后a = 6, b = 7, c = 12。
27. 用struct關(guān)鍵字與class關(guān)鍵定義類以及繼承的區(qū)別
（1）定義類差別
struct關(guān)鍵字也可以實現(xiàn)類，用class和struct關(guān)鍵字定義類的唯一差別在于默認(rèn)訪問級別：默認(rèn)情況下，struct成員的訪問級別為public，而class成員的為private。語法使用也相同，直接將class改為struct即可。
（2）繼承差別
使用class保留字的派生類默認(rèn)具有private繼承，而用struct保留字定義的類某人具有public繼承。其它則沒有任何區(qū)別。
主要點就兩個：默認(rèn)的訪問級別和默認(rèn)的繼承級別 class都是private
28.派生類與虛函數(shù)概述
(1) 派生類繼承的函數(shù)不能定義為虛函數(shù)。虛函數(shù)是希望派生類重新定義。如果派生類沒有重新定義某個虛函數(shù)，則在調(diào)用的時候會使用基類中定義的版本。
(2)派生類中函數(shù)的聲明必須與基類中定義的方式完全匹配。
(3) 基類中聲明為虛函數(shù)，則派生類也為虛函數(shù)。
29. 虛函數(shù)與純虛函數(shù)區(qū)別
1）虛函數(shù)在子類里面也可以不重載的；但純虛必須在子類去實現(xiàn)
2）帶純虛函數(shù)的類叫虛基類也叫抽象類，這種基類不能直接生成對象，只能被繼承，重寫虛函數(shù)后才能使用，運行時動態(tài)動態(tài)綁定！
30.深拷貝與淺拷貝
淺拷貝：
char ori[]=“hello”；char *copy=ori；
深拷貝：
char ori[]="hello"; char *copy=new char[]; copy=ori;
淺拷貝只是對指針的拷貝，拷貝后兩個指針指向同一個內(nèi)存空間，深拷貝不但對指針進行拷貝，而且對指針指向的內(nèi)容進行拷貝，經(jīng)深拷貝后的指針是指向兩個不同地址的指針。
淺拷貝可能出現(xiàn)的問題：
1） 淺拷貝只是拷貝了指針，使得兩個指針指向同一個地址，這樣在對象塊結(jié)束，調(diào)用函數(shù)析構(gòu)的時，會造成同一份資源析構(gòu)2次，即delete同一塊內(nèi)存2次，造成程序崩潰。
2） 淺拷貝使得兩個指針都指向同一塊內(nèi)存，任何一方的變動都會影響到另一方。
3） 同一個空間，第二次釋放失敗，導(dǎo)致無法操作該空間，造成內(nèi)存泄漏。
31. stl各容器的實現(xiàn)原理（必考）
1) Vector順序容器，是一個動態(tài)數(shù)組，支持隨機插入、刪除、查找等操作，在內(nèi)存中是一塊連續(xù)的空間。在原有空間不夠情況下自動分配空間，增加為原來的兩倍。vector隨機存取效率高，但是在vector插入元素，需要移動的數(shù)目多，效率低下。
注：vector動態(tài)增加大小時是以原大小的兩倍另外配置一塊較大的空間，然后將原內(nèi)容拷貝過來，然后才開始在原內(nèi)容之后構(gòu)造新元素，并釋放原空間。因此，對vector空間重新配置，指向原vector的所有迭代器就都失效了。
2) Map關(guān)聯(lián)容器，以鍵值對的形式進行存儲，方便進行查找。關(guān)鍵詞起到索引的作用，值則表示與索引相關(guān)聯(lián)的數(shù)據(jù)。紅黑樹的結(jié)構(gòu)實現(xiàn)，插入刪除等操作都在O(logn)時間內(nèi)完成。
3) Set是關(guān)聯(lián)容器，set每個元素只包含一個關(guān)鍵字。set支持高效的關(guān)鍵字檢查是否在set中。set也是以紅黑樹的結(jié)構(gòu)實現(xiàn)，支持高效插入、刪除等操作。
32.哪些庫函數(shù)屬于高危函數(shù)，為什么？
strcpy 賦值到目標(biāo)區(qū)間可能會造成緩沖區(qū)溢出！
33.STL有7種主要容器：vector,list,deque,map,multimap,set,multiset
34.你如何理解MVC。簡單舉例來說明其應(yīng)用。
MVC模式是observer 模式的一個特例,現(xiàn)在很多都是java的一些框架，MFC的，PHP的。
35.C++特點是什么，多態(tài)實現(xiàn)機制？（面試問過）多態(tài)作用？兩個必要條件？
C++中多態(tài)機制主要體現(xiàn)在兩個方面，一個是函數(shù)的重載，一個是接口的重寫。接口多態(tài)指的是“一個接口多種形態(tài)”。每一個對象內(nèi)部都有一個虛表指針，該虛表指針被初始化為本類的虛表。所以在程序中，不管你的對象類型如何轉(zhuǎn)換，但該對象內(nèi)部的虛表指針是固定的，所以呢，才能實現(xiàn)動態(tài)的對象函數(shù)調(diào)用，這就是C++多態(tài)性實現(xiàn)的原理。
多態(tài)的基礎(chǔ)是繼承，需要虛函數(shù)的支持，簡單的多態(tài)是很簡單的。子類繼承父類大部分的資源，不能繼承的有構(gòu)造函數(shù)，析構(gòu)函數(shù)，拷貝構(gòu)造函數(shù)，operator=函數(shù)，友元函數(shù)等等
作用：
必要條件：
1. 一個基類的指針或者引用指向派生類的對象；2.虛函數(shù)
36. 多重繼承有什么問題? 怎樣消除多重繼承中的二義性?
1)增加程序的復(fù)雜度，使程序的編寫和維護比較困難，容易出錯；
2)繼承類和基類的同名函數(shù)產(chǎn)生了二義性，同名函數(shù)不知道調(diào)用基類還是繼承類，C++中使用虛函數(shù)解決這個問題
3)繼承過程中可能會繼承一些不必要的數(shù)據(jù)，對于多級繼承，可能會產(chǎn)生數(shù)據(jù)很長
可以使用成員限定符和虛函數(shù)解決多重繼承中函數(shù)的二義性問題。
37.求兩個數(shù)的乘積和商數(shù)，該作用由宏定義來實現(xiàn)
#define product(a,b) ((a)*(b))
#define divide(a,b) ((a)/(b))
38.什么叫靜態(tài)關(guān)聯(lián)，什么叫動態(tài)關(guān)聯(lián)
多態(tài)中，靜態(tài)關(guān)聯(lián)是程序在編譯階段就能確定實際執(zhí)行動作，程序運行才能確定叫動態(tài)關(guān)聯(lián)
39.什么叫智能指針?常用的智能指針有哪些？智能指針的實現(xiàn)？
智能指針是一個存儲指向動態(tài)分配（堆）對象指針的類，構(gòu)造函數(shù)傳入普通指針，析構(gòu)函數(shù)釋放指針。棧上分配，函數(shù)或程序結(jié)束自動釋放，防止內(nèi)存泄露。使用引用計數(shù)器，類與指向的對象相關(guān)聯(lián)，引用計數(shù)跟蹤該類有多少個對象共享同一指針。創(chuàng)建類的新對象時，初始化指針并將引用計數(shù)置為1；當(dāng)對象作為另一對象的副本而創(chuàng)建，增加引用計數(shù)；對一個對象進行賦值時，減少引用計數(shù)，并增加右操作數(shù)所指對象的引用計數(shù)；調(diào)用析構(gòu)函數(shù)時，構(gòu)造函數(shù)減少引用計數(shù)，當(dāng)引用計數(shù)減至0，則刪除基礎(chǔ)對象。
std::auto_ptr，不支持復(fù)制（拷貝構(gòu)造函數(shù)）和賦值（operator =），編譯不會提示出錯。
C++11引入的unique_ptr， 也不支持復(fù)制和賦值，但比auto_ptr好，直接賦值會編譯出錯。
C++11或boost的shared_ptr，基于引用計數(shù)的智能指針。可隨意賦值，直到內(nèi)存的引用計數(shù)為0的時候這個內(nèi)存會被釋放。還有Weak_ptr
40.枚舉與#define 宏的區(qū)別
1）#define 宏常量是在預(yù)編譯階段進行簡單替換。枚舉常量則是在編譯的時候確定其值。
2）可以調(diào)試枚舉常量，但是不能調(diào)試宏常量。
3）枚舉可以一次定義大量相關(guān)的常量，而#define 宏一次只能定義一個。
41.介紹一下函數(shù)的重載
重載是在不同類型上作不同運算而又用同樣的名字的函數(shù)。重載函數(shù)至少在參數(shù)個數(shù)，參數(shù)類型， 或參數(shù)順序上有所不同。
42.派生新類的過程要經(jīng)歷三個步驟
1.吸收基類成員 2.改造基類成員 3.添加新成員
43.面向?qū)ο蟮娜齻€基本特征，并簡單敘述之?
1)封裝：將客觀事物抽象成類，每個類對自身的數(shù)據(jù)和方法實行2)繼承3)多態(tài)：允許一個基類的指針或引用指向一個派生類對象
44.多態(tài)性體現(xiàn)都有哪些？動態(tài)綁定怎么實現(xiàn)？
多態(tài)性是一個接口,多種實現(xiàn)，是面向?qū)ο蟮暮诵摹?編譯時多態(tài)性：通過重載函數(shù)實現(xiàn)。運行時多態(tài)性：通過虛函數(shù)實現(xiàn),結(jié)合動態(tài)綁定。
45.虛函數(shù)，虛函數(shù)表里面內(nèi)存如何分配？
編譯時若基類中有虛函數(shù)，編譯器為該的類創(chuàng)建一個一維數(shù)組的虛表，存放是每個虛函數(shù)的地址?；惡团缮惗及摵瘮?shù)時，這兩個類都建立一個虛表。構(gòu)造函數(shù)中進行虛表的創(chuàng)建和虛表指針的初始化。在構(gòu)造子類對象時，要先調(diào)用父類的構(gòu)造函數(shù)，初始化父類對象的虛表指針，該虛表指針指向父類的虛表。執(zhí)行子類的構(gòu)造函數(shù)時，子類對象的虛表指針被初始化，指向自身的虛表。每一個類都有虛表。虛表可以繼承，如果子類沒有重寫虛函數(shù)，那么子類虛表中仍然會有該函數(shù)的地址，只不過這個地址指向的是基類的虛函數(shù)實現(xiàn)。派生類的虛表中虛函數(shù)地址的排列順序和基類的虛表中虛函數(shù)地址排列順序相同。當(dāng)用一個指針/引用調(diào)用一個函數(shù)的時候，被調(diào)用的函數(shù)是取決于這個指針/引用的類型。即如果這個指針/引用是基類對象的指針/引用就調(diào)用基類的方法；如果指針/引用是派生類對象的指針/引用就調(diào)用派生類的方法，當(dāng)然如果派生類中沒有此方法，就會向上到基類里面去尋找相應(yīng)的方法。這些調(diào)用在編譯階段就確定了。當(dāng)涉及到多態(tài)性的時候，采用了虛函數(shù)和動態(tài)綁定，此時的調(diào)用就不會在編譯時候確定而是在運行時確定。不在單獨考慮指針/引用的類型而是看指針/引用的對象的類型來判斷函數(shù)的調(diào)用，根據(jù)對象中虛指針指向的虛表中的函數(shù)的地址來確定調(diào)用哪個函數(shù)。
46. 純虛函數(shù)如何定義？含有純虛函數(shù)的類稱為什么？為什么析構(gòu)函數(shù)要定義成虛函數(shù)？
純虛函數(shù)是在基類中聲明的虛函數(shù)，它在基類中沒有定義，但要求任何派生類都要定義自己的實現(xiàn)方法。純虛函數(shù)是虛函數(shù)再加上= 0。virtual void fun ()=0。含有純虛函數(shù)的類稱為抽象類在很多情況下，基類本身生成對象是不合情理的。例如，動物作為一個基類可以派生出老虎、孔雀等子類，但動物本身生成對象明顯不合常理。同時含有純虛擬函數(shù)的類稱為抽象類，它不能生成對象。如果析構(gòu)函數(shù)不是虛函數(shù)，那么釋放內(nèi)存時候，編譯器會使用靜態(tài)聯(lián)編，認(rèn)為p就是一個基類指針，調(diào)用基類析構(gòu)函數(shù)，這樣子類對象的內(nèi)存沒有釋放，造成內(nèi)存泄漏。定義成虛函數(shù)以后，就會動態(tài)聯(lián)編，先調(diào)用子類析構(gòu)函數(shù)，再基類。
47. C++中哪些不能是虛函數(shù)？
1）普通函數(shù)只能重載，不能被重寫，因此編譯器會在編譯時綁定函數(shù)。
2）構(gòu)造函數(shù)是知道全部信息才能創(chuàng)建對象，然而虛函數(shù)允許只知道部分信息。
3）內(nèi)聯(lián)函數(shù)在編譯時被展開，虛函數(shù)在運行時才能動態(tài)綁定函數(shù)。
4）友元函數(shù) 因為不可以被繼承。
5）靜態(tài)成員函數(shù) 只有一個實體，不能被繼承。父類和子類共有。
48. 類型轉(zhuǎn)換有哪些？各適用什么環(huán)境？dynamic_cast轉(zhuǎn)換失敗時，會出現(xiàn)什么情況(對指針，返回NULL.對引用，拋出bad_cast異常)？
靜態(tài)類型轉(zhuǎn)換，static_cast，基本類型之間和具有繼承關(guān)系的類型。
例子A,double類型轉(zhuǎn)換成int。B,將子類對象轉(zhuǎn)換成基類對象。
常量類型轉(zhuǎn)換，const_cast, 去除指針變量的常量屬性。
無法將非指針的常量轉(zhuǎn)換為普通變量。
動態(tài)類型轉(zhuǎn)換，dynamic_cast，運行時進行轉(zhuǎn)換分析的，并非在編譯時進行。dynamic_cast轉(zhuǎn)換符只能用于含有虛函數(shù)的類。dynamic_cast用于類層次間的向上轉(zhuǎn)換和向下轉(zhuǎn)換，還可以用于類間的交叉轉(zhuǎn)換。在類層次間進行向上轉(zhuǎn)換，即子類轉(zhuǎn)換為父類，此時完成的功能和static_cast是相同的，因為編譯器默認(rèn)向上轉(zhuǎn)換總是安全的。向下轉(zhuǎn)換時，dynamic_cast具有類型檢查的功能，更加安全。類間的交叉轉(zhuǎn)換指的是子類的多個父類之間指針或引用的轉(zhuǎn)換。該函數(shù)只能在繼承類對象的指針之間或引用之間進行類型轉(zhuǎn)換，或者有虛函數(shù)的類。
49. 如何判斷一段程序是由C 編譯程序還是由C++編譯程序編譯的？
#ifdef __cplusplus
cout<<"C++";
#else
cout<<"c";
#endif
50. 為什么要用static_cast轉(zhuǎn)換而不用c語言中的轉(zhuǎn)換？
Static_cast轉(zhuǎn)換，它會檢查類型看是否能轉(zhuǎn)換，有類型安全檢查。
比如，這個在C++中合法，但是確實錯誤的。
A* a= new A;
B* b = (B*)a;
51. 操作符重載（+操作符），具體如何去定義？
除了類屬關(guān)系運算符”.”、成員指針運算符”.*”、作用域運算符”::”、sizeof運算符和三目運算符”?:”以外，C++中的所有運算符都可以重載。
<返回類型說明符> operator <運算符符號>(<參數(shù)表>){}
重載為類的成員函數(shù)和重載為類的非成員函數(shù)。參數(shù)個數(shù)會不同，應(yīng)為this指針。
52. 內(nèi)存對齊的原則？
A.結(jié)構(gòu)體的大小為最大成員的整數(shù)倍。
B.成員首地址的偏移量為其類型大小整數(shù)倍。
53. 內(nèi)聯(lián)函數(shù)與宏定義的區(qū)別？
內(nèi)聯(lián)函數(shù)是用來消除函數(shù)調(diào)用時的時間開銷。頻繁被調(diào)用的短小函數(shù)非常受益。
A. 宏定義不檢查函數(shù)參數(shù)，返回值什么的，只是展開，相對來說，內(nèi)聯(lián)函數(shù)會檢查參數(shù)類型，所以更安全。
B. 宏是由預(yù)處理器對宏進行替代，而內(nèi)聯(lián)函數(shù)是通過編譯器控制來實現(xiàn)的
54. 動態(tài)分配對象和靜態(tài)分配對象的區(qū)別？
動態(tài)分配就是用運算符new來創(chuàng)建一個類的對象，在堆上分配內(nèi)存。
靜態(tài)分配就是A a;這樣來由編譯器來創(chuàng)建一個對象，在棧上分配內(nèi)存。
55. explicit是干什么用的 ?
構(gòu)造器 ，可以阻止不應(yīng)該允許的經(jīng)過轉(zhuǎn)換構(gòu)造函數(shù)進行的隱式轉(zhuǎn)換的發(fā)生。explicit是用來防止外部非正規(guī)的拷貝構(gòu)造的，要想不存在傳值的隱式轉(zhuǎn)換問題。
56. 內(nèi)存溢出有那些因素？
(1) 使用非類型安全(non-type-safe)的語言如 C/C++ 等。
(2) 以不可靠的方式存取或者復(fù)制內(nèi)存緩沖區(qū)。
(3) 編譯器設(shè)置的內(nèi)存緩沖區(qū)太靠近關(guān)鍵數(shù)據(jù)結(jié)構(gòu)。
57. new與malloc的區(qū)別，delete和free的區(qū)別？
1.malloc/free是C/C++語言的標(biāo)準(zhǔn)庫函數(shù)，new/delete是C++的運算符
2.new能夠自動分配空間大小，malloc傳入?yún)?shù)。
3. new/delete能進行對對象進行構(gòu)造和析構(gòu)函數(shù)的調(diào)用進而對內(nèi)存進行更加詳細(xì)的工作，而malloc/free不能。
既然new/delete的功能完全覆蓋了malloc/free，為什么C++還保留malloc/free呢？因為C++程序經(jīng)常要調(diào)用C函數(shù)，而C程序只能用malloc/free管理動態(tài)內(nèi)存。
58. 必須使用初始化列表初始化數(shù)據(jù)成員的情況
1.是對象的情況；
2.const修飾的類成員；
3.引用成員數(shù)據(jù)；
類成員變量的初始化不是按照初始化表順序被初始化，是按照在類中聲明的順序被初始化的。
59.深入談?wù)劧押蜅?/span>
1).分配和管理方式不同 ：
堆是動態(tài)分配的，其空間的分配和釋放都由程序員控制。
棧由編譯器自動管理。棧有兩種分配方式：靜態(tài)分配和動態(tài)分配。靜態(tài)分配由編譯器完成，比如局部變量的分配。動態(tài)分配由alloca()函數(shù)進行分配，但是棧的動態(tài)分配和堆是不同的，它的動態(tài)分配是由編譯器進行釋放，無須手工控制。
2).產(chǎn)生碎片不同
對堆來說，頻繁的new/delete或者malloc/free勢必會造成內(nèi)存空間的不連續(xù)，造成大量的碎片，使程序效率降低。
對棧而言，則不存在碎片問題，因為棧是先進后出的隊列，永遠不可能有一個內(nèi)存塊從棧中間彈出。
3).生長方向不同
堆是向著內(nèi)存地址增加的方向增長的，從內(nèi)存的低地址向高地址方向增長。
棧是向著內(nèi)存地址減小的方向增長，由內(nèi)存的高地址向低地址方向增長。
60.內(nèi)存的靜態(tài)分配和動態(tài)分配的區(qū)別？
時間不同。靜態(tài)分配發(fā)生在程序編譯和連接時。動態(tài)分配則發(fā)生在程序調(diào)入和執(zhí)行時。
空間不同。堆都是動態(tài)分配的，沒有靜態(tài)分配的堆。棧有2種分配方式：靜態(tài)分配和動態(tài)分配。靜態(tài)分配是編譯器完成的，比如局部變量的分配。alloca，可以從棧里動態(tài)分配內(nèi)存，不用擔(dān)心內(nèi)存泄露問題，當(dāng)函數(shù)返回時，通過alloca申請的內(nèi)存就會被自動釋放掉。
61. 模版怎么實現(xiàn)？模版作用？
實現(xiàn)：template void swap(T& a, T& b){}
作用：將算法與具體對象分離，與類型無關(guān)，通用，節(jié)省精力
62. 多重類構(gòu)造和析構(gòu)的順序
記住析構(gòu)函數(shù)的調(diào)用順序與構(gòu)造函數(shù)是相反的。
63. 迭代器刪除元素的會發(fā)生什么？
迭代器失效
64. 靜態(tài)成員函數(shù)和數(shù)據(jù)成員有什么意義？
1）非靜態(tài)數(shù)據(jù)成員，每個對象都有自己的拷貝。而靜態(tài)數(shù)據(jù)成員被當(dāng)作是類的成員，是該類的所有對象所共有的，在程序中只分配一次內(nèi)存只有一份拷貝，所以對象都共享，值對每個對象都是一樣的，它的值可以更新。
2）靜態(tài)數(shù)據(jù)成員存儲在全局?jǐn)?shù)據(jù)區(qū)，所以不能在類聲明中定義，應(yīng)該在類外定義。由于它不屬于特定的類對象，在沒有產(chǎn)生類對象時作用域就可見，即在沒有產(chǎn)生類的實例時，我們就可以操作它。
3）靜態(tài)成員函數(shù)與靜態(tài)數(shù)據(jù)成員一樣，都是在類的內(nèi)部實現(xiàn)，屬于類定義的一部分。因為普通成員函數(shù)總是具體的屬于具體對象的，每個有this指針。靜態(tài)成員函數(shù)沒有this指針，它無法訪問屬于類對象的非靜態(tài)數(shù)據(jù)成員，也無法訪問非靜態(tài)成員函數(shù)。靜態(tài)成員之間可以互相訪問，包括靜態(tài)成員函數(shù)訪問靜態(tài)數(shù)據(jù)成員和訪問靜態(tài)成員函數(shù)；
4）非靜態(tài)成員函數(shù)可以任意地訪問靜態(tài)成員函數(shù)和靜態(tài)數(shù)據(jù)成員；
5）沒有this指針的額外開銷，靜態(tài)成員函數(shù)與類的全局函數(shù)相比，速度上會有少許的增長；
6）調(diào)用靜態(tài)成員函數(shù)，可以用成員訪問操作符(.)和(->)為一個類的對象或指向類對象的指調(diào)用靜態(tài)成員函數(shù)。
65.sizeof一個類求大?。ㄗ⒁獬蓡T變量，函數(shù)，虛函數(shù)，繼承等等對大小的影響）
http://blog.csdn.net/jollyhope/article/details/1895357
http://www.cnblogs.com/BeyondTechnology/archive/2010/09/21/1832369.html
66請用C/C++實現(xiàn)字符串反轉(zhuǎn)（不調(diào)用庫函數(shù)）”abc”類型的
char *reverse_str(char *str) {
if(NULL == str) { //字符串為空直接返回
return str;
}
char *begin;
char *end;
begin = end = str;
while(*end != '\0') { //end指向字符串的末尾
end++;
}
--end;
char temp;
while(begin < end) { //交換兩個字符
temp = *begin;
*begin = *end;
*end = temp;
begin++;
end--;
}
return str; //返回結(jié)果
}
67.寫一個函數(shù)，將字符串翻轉(zhuǎn)，翻轉(zhuǎn)方式如下：“I am a student”反轉(zhuǎn)成“student a am I”，不借助任何庫函數(shù)
1 #include "stdio.h"
2 #include <iostream>
3 using namespace std;
4
5 void revesal(char * start, char* end){
6 char *temp_s = start;
7 char *temp_e = end;
8 while(temp_s < temp_e){
9 char temp= *temp_s;
10 *temp_s= *temp_e;
11 *temp_e = temp;
12 ++temp_s;
13 --temp_e;
14 }
15 return;
16 }
17
18 void revesal_str(char *str){
19 if(str == NULL){
20 return;
21 }
22
23 char *start = str;
24 char *end = str;
25
26 while(*++end !='\0');
27 revesal(start, end-1);
28 cout << str << endl;
29 char *sub_start = str;
30 while(start < end + 1 ){
31 if(*start == ' ' || *start == '\0'){
32 char *temp = start - 1;
33 revesal(sub_start,temp);
34 while(*++start ==' ');
35 sub_start = start;
36 continue;
37 }
38 ++start;
39 }
40 }
68.析構(gòu)函數(shù)可以拋出異常嗎？為什么不能拋出異常？除了資源泄露，還有其他需考慮的因素嗎？
C++標(biāo)準(zhǔn)指明析構(gòu)函數(shù)不能、也不應(yīng)該拋出異常。C++異常處理模型最大的特點和優(yōu)勢就是對C++中的面向?qū)ο筇峁┝俗顝姶蟮臒o縫支持。那么如果對象在運行期間出現(xiàn)了異常，C++異常處理模型有責(zé)任清除那些由于出現(xiàn)異常所導(dǎo)致的已經(jīng)失效了的對象(也即對象超出了它原來的作用域)，并釋放對象原來所分配的資源， 這就是調(diào)用這些對象的析構(gòu)函數(shù)來完成釋放資源的任務(wù)，所以從這個意義上說，析構(gòu)函數(shù)已經(jīng)變成了異常處理的一部分。
1）如果析構(gòu)函數(shù)拋出異常，則異常點之后的程序不會執(zhí)行，如果析構(gòu)函數(shù)在異常點之后執(zhí)行了某些必要的動作比如釋放某些資源，則這些動作不會執(zhí)行，會造成諸如資源泄漏的問題。
2）通常異常發(fā)生時，c++的機制會調(diào)用已經(jīng)構(gòu)造對象的析構(gòu)函數(shù)來釋放資源，此時若析構(gòu)函數(shù)本身也拋出異常，則前一個異常尚未處理，又有新的異常，會造成程序崩潰的問題。
69. 拷貝構(gòu)造函數(shù)作用及用途？什么時候需要自定義拷貝構(gòu)造函數(shù)？
一般如果構(gòu)造函數(shù)中存在動態(tài)內(nèi)存分配，則必須定義拷貝構(gòu)造函數(shù)。否則，可能會導(dǎo)致兩個對象成員指向同一地址，出現(xiàn)“指針懸掛問題”。
70. 100萬個32位整數(shù)，如何最快找到中位數(shù)。能保證每個數(shù)是唯一的，如何實現(xiàn)O(N)算法？
1).內(nèi)存足夠時：快排
2).內(nèi)存不足時：分桶法：化大為小，把所有數(shù)劃分到各個小區(qū)間，把每個數(shù)映射到對應(yīng)的區(qū)間里，對每個區(qū)間中數(shù)的個數(shù)進行計數(shù)，數(shù)一遍各個區(qū)間，看看中位數(shù)落在哪個區(qū)間，若夠小，使用基于內(nèi)存的算法，否則 繼續(xù)劃分
71. OFFSETOF(s, m)的宏定義，s是結(jié)構(gòu)類型，m是s的成員，求m在s中的偏移量。#define OFFSETOF（s, m） size_t（&((s*)0)->m）
72. C++虛函數(shù)是如何實現(xiàn)的？使用虛函數(shù)表。 C++對象使用虛表， 如果是基類的實例，對應(yīng)位置存放的是基類的函數(shù)指針；如果是繼承類，對應(yīng)位置存放的是繼承類的函數(shù)指針（如果在繼承類有實現(xiàn)）。所以 ，當(dāng)使用基類指針調(diào)用對象方法時，也會根據(jù)具體的實例，調(diào)用到繼承類的方法。
73. C++的虛函數(shù)有什么作用？虛函數(shù)作用是實現(xiàn)多態(tài)，虛函數(shù)其實是實現(xiàn)封裝，使得使用者不需要關(guān)心實現(xiàn)的細(xì)節(jié)。在很多設(shè)計模式中都是這樣用法，例如Factory、Bridge、Strategy模式。
74.MFC中CString是類型安全類嗎，為什么？
不是，其他數(shù)據(jù)類型轉(zhuǎn)換到CString可以使用CString的成員函數(shù)Format來轉(zhuǎn)換
75.動態(tài)鏈接庫的兩種使用方法及特點？1)．載入時動態(tài)鏈接，模塊非常明確調(diào)用某個導(dǎo)出函數(shù)，使得他們就像本地函數(shù)一樣。這需要鏈接時鏈接那些函數(shù)所在DLL的導(dǎo)入庫，導(dǎo)入庫向系統(tǒng)提供了載入DLL時所需的信息及DLL函數(shù)定位。
2)運行時動態(tài)鏈接。
二、服務(wù)器編程
1.多線程和多進程的區(qū)別（重點 必須從cpu調(diào)度，上下文切換，數(shù)據(jù)共享，多核cup利用率，資源占用，等等各方面回答，然后有一個問題必須會被問到：哪些東西是一個線程私有的？答案中必須包含寄存器，否則悲催）！
1）進程數(shù)據(jù)是分開的:共享復(fù)雜，需要用IPC，同步簡單；多線程共享進程數(shù)據(jù)：共享簡單，同步復(fù)雜
2）進程創(chuàng)建銷毀、切換復(fù)雜，速度慢 ；線程創(chuàng)建銷毀、切換簡單，速度快
3）進程占用內(nèi)存多， CPU利用率低；線程占用內(nèi)存少， CPU利用率高
4）進程編程簡單，調(diào)試簡單；線程 編程復(fù)雜，調(diào)試復(fù)雜
5）進程間不會相互影響 ；線程一個線程掛掉將導(dǎo)致整個進程掛掉
6）進程適應(yīng)于多核、多機分布；線程適用于多核
線程所私有的：
線程id、寄存器的值、棧、線程的優(yōu)先級和調(diào)度策略、線程的私有數(shù)據(jù)、信號屏蔽字、errno變量、
2. 多線程鎖的種類有哪些？
a.互斥鎖（mutex）b.遞歸鎖 c.自旋鎖 d.讀寫鎖
3. 自旋鎖和互斥鎖的區(qū)別？
當(dāng)鎖被其他線程占用時，其他線程并不是睡眠狀態(tài)，而是不停的消耗CPU，獲取鎖；互斥鎖則不然，保持睡眠，直到互斥鎖被釋放激活。
自旋鎖，遞歸調(diào)用容易造成死鎖，對長時間才能獲得到鎖的情況，使用自旋鎖容易造成CPU效率低，只有內(nèi)核可搶占式或SMP情況下才真正需要自旋鎖。
4.進程間通信和線程間通信
1）.管道 2）消息隊列 3)共享內(nèi)存 4)信號量 5)套接字 6)條件變量
5.多線程程序架構(gòu)，線程數(shù)量應(yīng)該如何設(shè)置？
應(yīng)盡量和CPU核數(shù)相等或者為CPU核數(shù)+1的個數(shù)
6.什么是原子操作，gcc提供的原子操作原語，使用這些原語如何實現(xiàn)讀寫鎖？
原子操作是指不會被線程調(diào)度機制打斷的操作；這種操作一旦開始，就一直運行到結(jié)束，中間不會有任何 context switch。
7.網(wǎng)絡(luò)編程設(shè)計模式，reactor/proactor/半同步半異步模式？
reactor模式：同步阻塞I/O模式，注冊對應(yīng)讀寫事件處理器，等待事件發(fā)生進而調(diào)用事件處理器處理事件。 proactor模式：異步I/O模式。Reactor和Proactor模式的主要區(qū)別就是真正的讀取和寫入操作是有誰來完成的，Reactor中需要應(yīng)用程序自己讀取或者寫入數(shù)據(jù)，Proactor模式中，應(yīng)用程序不需要進行實際讀寫過程。
Reactor是：
主線程往epoll內(nèi)核上注冊socket讀事件，主線程調(diào)用epoll_wait等待socket上有數(shù)據(jù)可讀，當(dāng)socket上有數(shù)據(jù)可讀的時候，主線程把socket可讀事件放入請求隊列。睡眠在請求隊列上的某個工作線程被喚醒，處理客戶請求，然后往epoll內(nèi)核上注冊socket寫請求事件。主線程調(diào)用epoll_wait等待寫請求事件，當(dāng)有事件可寫的時候，主線程把socket可寫事件放入請求隊列。睡眠在請求隊列上的工作線程被喚醒，處理客戶請求。
Proactor:
主線程調(diào)用aio_read函數(shù)向內(nèi)核注冊socket上的讀完成事件，并告訴內(nèi)核用戶讀緩沖區(qū)的位置，以及讀完成后如何通知應(yīng)用程序，主線程繼續(xù)處理其他邏輯，當(dāng)socket上的數(shù)據(jù)被讀入用戶緩沖區(qū)后，通過信號告知應(yīng)用程序數(shù)據(jù)已經(jīng)可以使用。應(yīng)用程序預(yù)先定義好的信號處理函數(shù)選擇一個工作線程來處理客戶請求。工作線程處理完客戶請求之后調(diào)用aio_write函數(shù)向內(nèi)核注冊socket寫完成事件，并告訴內(nèi)核寫緩沖區(qū)的位置，以及寫完成時如何通知應(yīng)用程序。主線程處理其他邏輯。當(dāng)用戶緩存區(qū)的數(shù)據(jù)被寫入socket之后內(nèi)核向應(yīng)用程序發(fā)送一個信號，以通知應(yīng)用程序數(shù)據(jù)已經(jīng)發(fā)送完畢。應(yīng)用程序預(yù)先定義的數(shù)據(jù)處理函數(shù)就會完成工作。
半同步半異步模式：
上層的任務(wù)（如：數(shù)據(jù)庫查詢，文件傳輸）使用同步I/O模型，簡化了編寫并行程序的難度。
而底層的任務(wù)（如網(wǎng)絡(luò)控制器的中斷處理）使用異步I/O模型，提供了執(zhí)行效率。
8.有一個計數(shù)器，多個線程都需要更新，會遇到什么問題，原因是什么，應(yīng)該如何做？如何優(yōu)化？
有可能一個線程更新的數(shù)據(jù)已經(jīng)被另外一個線程更新了，更新的數(shù)據(jù)就會出現(xiàn)異常，可以加鎖，保證數(shù)據(jù)更新只會被一個線程完成。
9.如果select返回可讀，結(jié)果只讀到0字節(jié)，什么情況？
某個套接字集合中沒有準(zhǔn)備好，可能會select內(nèi)存用FD_CLR清為0.
10. connect可能會長時間阻塞，怎么解決?
1.使用定時器；（最常用也最有效的一種方法）
2.采用非阻塞模式：設(shè)置非阻塞，返回之后用select檢測狀態(tài)。
11.keepalive 是什么東西？如何使用？
keepalive，是在TCP中一個可以檢測死連接的機制。
1）.如果主機可達，對方就會響應(yīng)ACK應(yīng)答，就認(rèn)為是存活的。
2）.如果可達，但應(yīng)用程序退出，對方就發(fā)RST應(yīng)答，發(fā)送TCP撤消連接。
3）.如果可達，但應(yīng)用程序崩潰，對方就發(fā)FIN消息。
4）.如果對方主機不響應(yīng)ack, rst，繼續(xù)發(fā)送直到超時，就撤消連接。默認(rèn)二個小時。
12.socket什么情況下可讀？
1.socket接收緩沖區(qū)中已經(jīng)接收的數(shù)據(jù)的字節(jié)數(shù)大于等于socket接收緩沖區(qū)低潮限度的當(dāng)前值;對這樣的socket的讀操作不會阻塞,并返回一個大于0的值(準(zhǔn)備好讀入的數(shù)據(jù)的字節(jié)數(shù)).
2.連接的讀一半關(guān)閉(即:接收到對方發(fā)過來的FIN的TCP連接),并且返回0;
3.socket收到了對方的connect請求已經(jīng)完成的連接數(shù)為非0.這樣的soocket處于可讀狀態(tài)；
4.異常的情況下socket的讀操作將不會阻塞,并且返回一個錯誤(-1)。
13.udp調(diào)用connect有什么作用？
1).因為UDP可以是一對一，多對一，一對多，或者多對多的通信，所以每次調(diào)用sendto()/recvfrom()時都必須指定目標(biāo)IP和端口號。通過調(diào)用connect()建立一個端到端的連接，就可以和TCP一樣使用send()/recv()傳遞數(shù)據(jù)，而不需要每次都指定目標(biāo)IP和端口號。但是它和TCP不同的是它沒有三次握手的過程。
2).可以通過在已建立連接的UDP套接字上，調(diào)用connect()實現(xiàn)指定新的IP地址和端口號以及斷開連接。
14. socket編程，如果client斷電了，服務(wù)器如何快速知道？
使用定時器（適合有數(shù)據(jù)流動的情況）；
使用socket選項SO_KEEPALIVE（適合沒有數(shù)據(jù)流動的情況）;
1）、自己編寫心跳包程序,簡單的說就是自己的程序加入一條線程,定時向?qū)Χ税l(fā)送數(shù)據(jù)包,查看是否有ACK,根據(jù)ACK的返回情況來管理連接。此方法比較通用,一般使用業(yè)務(wù)層心跳處理,靈活可控,但改變了現(xiàn)有的協(xié)議;
2）、使用TCP的keepalive機制,UNIX網(wǎng)絡(luò)編程不推薦使用SO_KEEPALIVE來做心）跳檢測。
keepalive原理:TCP內(nèi)嵌有心跳包,以服務(wù)端為例,當(dāng)server檢測到超過一定時間(/proc/sys/net/ipv4/tcp_keepalive_time 7200 即2小時)沒有數(shù)據(jù)傳輸,那么會向client端發(fā)送一個keepalive packet。
三、liunx操作系統(tǒng)
1.熟練netstat tcpdump ipcs ipcrm
netstat:檢查網(wǎng)絡(luò)狀態(tài)，tcpdump:截獲數(shù)據(jù)包，ipcs:檢查共享內(nèi)存，ipcrm:解除共享內(nèi)存
2.共享內(nèi)存段被映射進進程空間之后，存在于進程空間的什么位置？共享內(nèi)存段最大限制是多少？
將一塊內(nèi)存映射到兩個或者多個進程地址空間。通過指針訪問該共享內(nèi)存區(qū)。一般通過mmap將文件映射到進程地址共享區(qū)。
存在于進程數(shù)據(jù)段，最大限制是0x2000000Byte
3.進程內(nèi)存空間分布情況
4.ELF是什么？其大小與程序中全局變量的是否初始化有什么關(guān)系（注意未初始化的數(shù)據(jù)放在bss段）
可執(zhí)行連接格式?？梢詼p少重新編程重新編譯的代碼。
5.動態(tài)鏈接和靜態(tài)鏈接的區(qū)別？
動態(tài)鏈接是只建立一個引用的接口，而真正的代碼和數(shù)據(jù)存放在另外的可執(zhí)行模塊中，在可執(zhí)行文件運行時再裝入；而靜態(tài)鏈接是把所有的代碼和數(shù)據(jù)都復(fù)制到本模塊中，運行時就不再需要庫了
6.32位系統(tǒng)一個進程最多有多少堆內(nèi)存
32位意味著4G的尋址空間，Linux把它分為兩部分：最高的1G(虛擬地址從0xC0000000到0xffffffff)用做內(nèi)核本身，成為“系統(tǒng)空間”，而較低的3G字節(jié)（從0x00000000到0xbffffff）用作各進程的“用戶空間”。每個進程可以使用的用戶空間是3G。雖然各個進程擁有其自己的3G用戶空間，系統(tǒng)空間卻由所有的進程共享。從具體進程的角度看，則每個進程都擁有4G的虛擬空間，較低的3G為自己的用戶空間，最高的1G為所有進程以及內(nèi)核共享的系統(tǒng)空間。實際上有人做過測試也就2G左右。
7.寫一個c程序辨別系統(tǒng)是64位 or 32位
void* number = 0; printf("%d\n",sizeof(&number));
輸出8就是64位 輸出4就是32位的 根據(jù)邏輯地址判斷的
8.寫一個c程序辨別系統(tǒng)是大端or小端字節(jié)序
union{ short value; char a[sizeof(short)];}test;
test.value= 0x0102;
if((test.a[0] == 1) && (test.a[1] == 2)) cout << "big"<<endl; else cout << "little" << endl;
9.信號：列出常見的信號，信號怎么處理？
1).進程終止的信號 2).跟蹤進程的信號 3).與進程例外事件相關(guān)的信號等
對于信號的處理或者執(zhí)行相關(guān)的操作進行處理或者直接忽略
10.i++ 是否原子操作?并解釋為什么?
答案肯定不是原子操作，i++主要看三個步驟
首先把數(shù)據(jù)從內(nèi)存放到寄存器上，在寄存器上進行自增處理，放回到寄存器上，每個步驟都可能會被中斷分離開！
11.說出你所知道的各類linux系統(tǒng)的各類同步機制（重點），什么是死鎖？如何避免死鎖（每個技術(shù)面試官必問）
1).原子操作 2).信號量（其實就是互斥鎖也就是鎖的機制）3).讀寫信號量（就是讀寫鎖） 4）.自旋鎖 5.內(nèi)核鎖 6）.順序鎖
死鎖就是幾個進程申請資源，出現(xiàn)了循環(huán)等待的情況！
避免死鎖的方法：
1）.資源是互斥的 2）.不可搶占 3）占有且申請 4）.循環(huán)等待
12、exit() _exit()的區(qū)別？
13、如何實現(xiàn)守護進程？
1）創(chuàng)建子進程，父進程退出
2）在子進程中創(chuàng)建新會話
3）改變當(dāng)前目錄為根目
4）重設(shè)文件權(quán)限掩碼
5) 關(guān)閉文件描述符
6) 守護進程退出處理
當(dāng)用戶需要外部停止守護進程運行時，往往會使用 kill命令停止該守護進程。所以，守護進程中需要編碼來實現(xiàn)kill發(fā)出的signal信號處理，達到進程的正常退出。
14、linux的任務(wù)調(diào)度機制是什么？
Linux 分實時進程和普通進程，實時進程應(yīng)該先于普通進程而運行。實時進程：
1） FIFO(先來先服務(wù)調(diào)度)
2） RR（時間片輪轉(zhuǎn)調(diào)度）。
每個進程有兩個優(yōu)先級（動態(tài)優(yōu)先級和實時優(yōu)先級），實時優(yōu)先級就是用來衡量實時進程是否值得運行的。 非實時進程有兩種優(yōu)先級，一種是靜態(tài)優(yōu)先級，另一種是動態(tài)優(yōu)先級。實時進程又增加了第三種優(yōu)先級，實時優(yōu)先級。優(yōu)先級越高，得到CPU時間的機會也就越大。
15、標(biāo)準(zhǔn)庫函數(shù)和系統(tǒng)調(diào)用的區(qū)別？
系統(tǒng)調(diào)用：是操作系統(tǒng)為用戶態(tài)運行的進程和硬件設(shè)備(如CPU、磁盤、打印機等)進行交互提供的一組接口，即就是設(shè)置在應(yīng)用程序和硬件設(shè)備之間的一個接口層。inux內(nèi)核是單內(nèi)核，結(jié)構(gòu)緊湊，執(zhí)行速度快，各個模塊之間是直接調(diào)用的關(guān)系。linux系統(tǒng)上到下依次是用戶進程->linux內(nèi)核->硬件。其中系統(tǒng)調(diào)用接口是位于Linux內(nèi)核中的，整個linux系統(tǒng)從上到下可以是：用戶進程->系統(tǒng)調(diào)用接口->linux內(nèi)核子系統(tǒng)->硬件，也就是說Linux內(nèi)核包括了系統(tǒng)調(diào)用接口和內(nèi)核子系統(tǒng)兩部分；或者從下到上可以是：物理硬件->OS內(nèi)核->OS服務(wù)->應(yīng)用程序，操作系統(tǒng)起到“承上啟下”作用，向下管理物理硬件，向上為操作系服務(wù)和應(yīng)用程序提供接口，這里的接口就是系統(tǒng)調(diào)用了。
庫函數(shù)：把函數(shù)放到庫里。是把一些常用到的函數(shù)編完放到一個lib文件里，供別人用。別人用的時候把它所在的文件名用#include<>加到里面就可以了。一類是c語言標(biāo)準(zhǔn)規(guī)定的庫函數(shù)，一類是編譯器特定的庫函數(shù)。
系統(tǒng)調(diào)用是為了方便使用操作系統(tǒng)的接口，而庫函數(shù)則是為了人們編程的方便。
16、系統(tǒng)如何將一個信號通知到進程？
內(nèi)核給進程發(fā)送信號，是在進程所在的進程表項的信號域設(shè)置對應(yīng)的信號的位。進程處理信號的時機就是從內(nèi)核態(tài)即將返回用戶態(tài)度的時候。執(zhí)行用戶自定義的信號處理函數(shù)的方法很巧妙。把該函數(shù)的地址放在用戶棧棧頂，進程從內(nèi)核返回到用戶態(tài)的時候，先彈出信號處理函數(shù)地址，于是就去執(zhí)行信號處理函數(shù)了，然后再彈出，才是返回進入內(nèi)核時的狀態(tài)。
17. fork()一子進程程后父進程的全局變量能不能使用？
fork后子進程將會擁有父進程的幾乎一切資源，父子進程的都各自有自己的全局變量。不能通用，不同于線程。對于線程，各個線程共享全局變量。
18. 請畫出socket通信連接過程
19. 請用socket消息隊列實現(xiàn)“同步非阻塞”和“異步阻塞”兩種模式，并指出兩者的差別和優(yōu)劣
http://blog.csdn.net/yongchurui/article/details/12780653
四、網(wǎng)絡(luò)編程
1. TCP頭大小，包含字段？三次握手，四次斷開描述過程，都有些什么狀態(tài)。狀態(tài)變遷圖。TCP/IP收發(fā)緩沖區(qū)（2次）
頭部大小是20字節(jié)，包含數(shù)據(jù)如下：
三次握手：
四次釋放：
狀態(tài)變遷圖：
收發(fā)緩沖區(qū)：
2. 使用udp和tcp進程網(wǎng)絡(luò)傳輸，為什么tcp能保證包是發(fā)送順序，而 udp無法保證？
因為TCP發(fā)送的數(shù)據(jù)包是按序號發(fā)送，有確認(rèn)機制和丟失重傳機制，而udp是不可靠的發(fā)送機制，發(fā)送的對應(yīng)端口的數(shù)據(jù)包不是按順序發(fā)送的。
3. epoll哪些觸發(fā)模式，有啥區(qū)別？（必須非常詳盡的解釋水平觸發(fā)和邊緣觸發(fā)的區(qū)別，以及邊緣觸發(fā)在編程中要做哪些更多的確認(rèn)）
epoll有EPOLLLT和EPOLLET兩種觸發(fā)模式，LT是默認(rèn)的模式，ET是“高速”模式。LT模式下，只要這個fd還有數(shù)據(jù)可讀，每次 epoll_wait都會返回它的事件，提醒用戶程序去操作，而在ET（邊緣觸發(fā)）模式中，它只會提示一次，直到下次再有數(shù)據(jù)流入之前都不會再提示了，無論fd中是否還有數(shù)據(jù)可讀。所以在ET模式下，read一個fd的時候一定要把它的buffer讀光，也就是說一直讀到read的返回值小于請求值。
也就是說在LT模式的情況下一定要確認(rèn)收發(fā)的數(shù)據(jù)包的buffer是不是足夠大如果收發(fā)數(shù)據(jù)包大小大于buffer的大小的時候就可能會出現(xiàn)數(shù)據(jù)丟失的情況。
4. tcp與udp的區(qū)別（必問）為什么TCP要叫做數(shù)據(jù)流？
1）．基于連接與無連接
2）．對系統(tǒng)資源的要求（TCP較多，UDP少）
3）．UDP程序結(jié)構(gòu)較簡單
4）．流模式與數(shù)據(jù)報模式
5）．TCP保證數(shù)據(jù)正確性，UDP可能丟包，TCP保證數(shù)據(jù)順序，UDP不保證
6）.TCP有擁塞控制和流量控制，UDP沒有
TCP提供的是面向連接、可靠的字節(jié)流服務(wù)。當(dāng)客戶和服務(wù)器彼此交換數(shù)據(jù)前，必須先在雙方之間建立一個TCP連接，之后才能傳輸數(shù)據(jù)。TCP提供超時重發(fā)，丟棄重復(fù)數(shù)據(jù)，檢驗數(shù)據(jù)，流量控制等功能，保證數(shù)據(jù)能從一端傳到另一端。
是一個簡單的面向數(shù)據(jù)報的運輸層協(xié)議。UDP不提供可靠性，它只是把應(yīng)用程序傳給IP層的數(shù)據(jù)報發(fā)送出去，但是并不能保證它們能到達目的地。由于UDP在傳輸數(shù)據(jù)報前不用在客戶和服務(wù)器之間建立一個連接，且沒有超時重發(fā)等機制，故而傳輸速度很快
5．流量控制和擁塞控制的實現(xiàn)機制
網(wǎng)絡(luò)擁塞現(xiàn)象是指到達通信子網(wǎng)中某一部分的分組數(shù)量過多,使得該部分網(wǎng)絡(luò)來不及處理,以致引起這部分乃至整個網(wǎng)絡(luò)性能下降的現(xiàn)象,嚴(yán)重時甚至?xí)?dǎo)致網(wǎng)絡(luò)通信業(yè)務(wù)陷入停頓,即出現(xiàn)死鎖現(xiàn)象。擁塞控制是處理網(wǎng)絡(luò)擁塞現(xiàn)象的一種機制。數(shù)據(jù)的傳送與接收過程當(dāng)中很可能出現(xiàn)收方來不及接收的情況,這時就需要對發(fā)方進行控制,以免數(shù)據(jù)丟失。
6. 滑動窗口的實現(xiàn)機制
滑動窗口機制，窗口的大小并不是固定的而是根據(jù)我們之間的鏈路的帶寬的大小，這個時候鏈路是否擁護塞。接受方是否能處理這么多數(shù)據(jù)了。 滑動窗口協(xié)議，是TCP使用的一種流量控制方法。該協(xié)議允許發(fā)送方在停止并等待確認(rèn)前可以連續(xù)發(fā)送多個分組。由于發(fā)送方不必每發(fā)一個分組就停下來等待確認(rèn)，因此該協(xié)議可以加速數(shù)據(jù)的傳輸。
7.epoll和select的區(qū)別？
1）select在一個進程中打開的最大fd是有限制的，由FD_SETSIZE設(shè)置，默認(rèn)值是2048。不過 epoll則沒有這個限制，內(nèi)存越大，fd上限越大，1G內(nèi)存都能達到大約10w左右。
2）select的輪詢機制是系統(tǒng)會去查找每個fd是否數(shù)據(jù)已準(zhǔn)備好，當(dāng)fd很多的時候，效率當(dāng)然就直線下降了，epoll采用基于事件的通知方式，一旦某個fd數(shù)據(jù)就緒時，內(nèi)核會采用類似callback的回調(diào)機制，迅速激活這個文件描述符，高效。
3）select還是epoll都需要內(nèi)核把FD消息通知給用戶空間，epoll是通過內(nèi)核于用戶空間mmap同一塊內(nèi)存實現(xiàn)的，而select則做了不必要的拷貝
8. 網(wǎng)絡(luò)中，如果客戶端突然掉線或者重啟，服務(wù)器端怎么樣才能立刻知道？
若客戶端掉線或者重新啟動，服務(wù)器端會收到復(fù)位信號，每一種tcp/ip得實現(xiàn)不一樣，控制機制也不一樣。
9. TTL是什么？有什么用處，通常那些工具會用到它？ping? traceroute? ifconfig? netstat?
TTL是Time To Live，每經(jīng)過一個路由就會被減去一，如果它變成0，包會被丟掉。它的主要目的是防止包在有回路的網(wǎng)絡(luò)上死轉(zhuǎn)，浪費網(wǎng)絡(luò)資源。ping和traceroute用到它。
10.linux的五種IO模式/異步模式.
1）同步阻塞I/O
2）同步非阻塞I/O
3）同步I/O復(fù)用模型
4） 同步信號驅(qū)動I/O
5） 異步I/O模型
11. 請說出http協(xié)議的優(yōu)缺點.
1.支持客戶/服務(wù)器模式。2.簡單快速：客戶向服務(wù)器請求服務(wù)時，只需傳送請求方法和路徑，通信速度很快。3.靈活：HTTP允許傳輸任意類型的數(shù)據(jù)對象。4.無連接：無連接的含義是限制每次連接只處理一個請求。服務(wù)器處理完客戶的請求，并收到客戶的應(yīng)答后，即斷開連接。采用這種方式可以節(jié)省傳輸時間。5.無狀態(tài)：HTTP協(xié)議是無狀態(tài)協(xié)議。無狀態(tài)是指協(xié)議對于事務(wù)處理沒有記憶能力。缺少狀態(tài)意味著如果后續(xù)處理需要前面的信息，則它必須重傳，導(dǎo)致每次連接傳送的數(shù)據(jù)量增大。缺點就是不夠安全，可以使用https完成使用
12.NAT類型，UDP穿透原理。
1）Full cone NAT （全克隆nat）:一對一NAT一旦一個內(nèi)部地址（iAddr:port1）映射到外部地址（eAddr:port2）。
2）Address-Restricted cone NAT（地址受限克隆nat）:任意外部主機（hostAddr:any）都能通過給eAddr:port2發(fā)包到達iAddr:port1的前提是：iAddr:port1之前發(fā)送過包到hostAddr:any. "any"也就是說端口不受限制
3). Port-Restricted cone NAT:內(nèi)部地址（iAddr:port1）映射到外部地址（eAddr:port2），所有發(fā)自iAddr:port1的包都經(jīng)eAddr:port2向外發(fā)送。一個外部主機（hostAddr:port3）能夠發(fā)包到達iAddr:port1的前提是：iAddr:port1之前發(fā)送過包到hostAddr:port3.
4). Symmetric NAT（對稱NAT）:同內(nèi)部IP與port的請求到一個特定目的地的IP地址和端口，映射到一個獨特的外部來源的IP地址和端口。同一個內(nèi)部主機發(fā)出一個信息包到不同的目的端，不同的映射使用外部主機收到了一封包從一個內(nèi)部主機可以送一封包回來
13.大規(guī)模連接上來，并發(fā)模型怎么設(shè)計
Epoll+線程池（epoll可以采用libevent處理）
14.tcp三次握手的，accept發(fā)生在三次握手哪個階段？三次握手：C----->SYN K
S------>ACK K+1 SYN J
C------->ACK J+1
DONE!
client 的 connect 引起3次握手
server 在socket， bind， listen后，阻塞在accept，三次握手完成后，accept返回一個fd，
16.流量控制與擁塞控制的區(qū)別，節(jié)點計算機怎樣感知網(wǎng)絡(luò)擁塞了？擁塞控制是把整體看成一個處理對象的，流量控制是對單個的節(jié)點。
感知的手段應(yīng)該不少，比如在TCP協(xié)議里，TCP報文的重傳本身就可以作為擁塞的依據(jù)。依據(jù)這樣的原理， 應(yīng)該可以設(shè)計出很多手段。
五、算法和數(shù)據(jù)結(jié)構(gòu)
1.給定一個單向鏈表（長度未知），請設(shè)計一個既節(jié)省時間又節(jié)省空間的算法來找出該鏈表中的倒數(shù)第m個元素。實現(xiàn)這個算法，并為可能出現(xiàn)的特例情況安排好處理措施。“倒數(shù)第m個元素”是這樣規(guī)定的：當(dāng)m=0時，鏈表的最后一個元素將被返回。
解決問題方法思路如下：
方法一、如果我們知道鏈表的長度n，查找倒數(shù)第m個元素，也就是查找正序的第（n - m）個元素（這里的序號只是為了分析，可能跟題目不一定正確的符合）。那么這樣來說就簡單很多。首先遍歷鏈表得到鏈表長度，然后重新遍歷一次，查找正數(shù)第（n-m）個元素。時間復(fù)雜度大約是O(2n)。
方法二、我們是不是可以提供一個輔助存儲空間，是的我們在遍歷到鏈表結(jié)束的時候可以回溯到倒數(shù)第m個元素。比如用一個支持隨機訪問的容器記錄鏈表每一個節(jié)點的地址。那么這樣的就可以只遍歷一次鏈表就能得到結(jié)果。時間復(fù)雜度大約是O(n)，但是我們是用空間換取時間的，輔助存儲空間的大小由m決定，如果m過大也是不可取的。
方法三、頭結(jié)點指針為當(dāng)前指針，尾節(jié)點指針為拖后指針。開始的時候當(dāng)前指針和拖后指針初始化為鏈表的頭結(jié)點，首先我們讓當(dāng)前指針遍歷到第m個元素，拖后指針不變；然后同步更新當(dāng)前指針和拖后指針；直到當(dāng)前指針為鏈表結(jié)尾。這樣我們就能保證當(dāng)前指針和拖尾指針之間的距離是m。
代碼如下：
Node* FindMToLastNode(Node* pHead, int m) {
// 查找到第m個元素
Node* pCurrent = pHead;
for (int i = 0; i < m; ++i)
{
if (pCurrent)
{
pCurrent = pCurrent->next;
}
else
{
return NULL;
}
}
Node* pFind = pHead;
while (pCurrent) {
pFind = pFind->next;
pCurrent = pCurrent->next;
}
return pFind;
}
2. 給定一個單向鏈表（長度未知），請遍歷一次就找到中間的指針，假設(shè)該鏈表存儲在只讀存儲器，不能被修改
設(shè)置兩個指針，一個每次移動兩個位置，一個每次移動一個位置，當(dāng)?shù)谝粋€指針到達尾節(jié)點時，第二個指針就達到了中間節(jié)點的位置
處理鏈表問題時，”快行指針“是一種很常見的技巧，快行指針指的是同時用兩個指針來迭代訪問鏈表，只不過其中一個比另一個超前一些?？熘羔樛刃袔撞?，或與慢指針相差固定的步數(shù)。
node *create() {
node *p1, *p2, *head;
int cycle = 1, x;
head = (node*)malloc(sizeof(node));
p1 = head;
while (cycle)
{
cout << "please input an integer: ";
cin >> x;
if (x != 0)
{
p2 = (node*)malloc(sizeof(node));
p2->data = x;
p1->next = p2;
p1 = p2;
}
else
{
cycle = 0;
}
}
head = head->next;
p1->next = NULL;
return head;
}
void findmid(node* head) {
node *p1, *p2, *mid;
p1 = head;
p2 = head;
while (p1->next->next != NULL)
{
p1 = p1->next->next;
p2 = p2->next;
mid = p2;
}
}
3. 將一個數(shù)組生成二叉排序樹
排序，選數(shù)組中間的一個元素作為根節(jié)點，左邊的元素構(gòu)造左子樹，右邊的節(jié)點構(gòu)造有子樹。
4. 查找數(shù)組中第k大的數(shù)字？
因為快排每次將數(shù)組劃分為兩組加一個樞紐元素，每一趟劃分你只需要將k與樞紐元素的下標(biāo)進行比較，如果比樞紐元素下標(biāo)大就從右邊的子數(shù)組中找，如果比樞紐元素下標(biāo)小從左邊的子數(shù)組中找，如果一樣則就是樞紐元素，找到，如果需要從左邊或者右邊的子數(shù)組中再查找的話，只需要遞歸一邊查找即可，無需像快排一樣兩邊都需要遞歸，所以復(fù)雜度必然降低。
最差情況如下：假設(shè)快排每次都平均劃分，但是都不在樞紐元素上找到第k大第一趟快排沒找到，時間復(fù)雜度為O(n)，第二趟也沒找到，時間復(fù)雜度為O(n/2)，第k趟找到，時間復(fù)雜度為O(n/2k)，所以總的時間復(fù)雜度為O(n(1+1/2+....+1/2k))=O(n)，明顯比冒泡快，雖然遞歸深度是一樣的，但是每一趟時間復(fù)雜度降低。
5. 紅黑樹的定義和解釋？B樹的基本性質(zhì)？
紅黑樹：
性質(zhì)1. 節(jié)點是紅色或黑色。
性質(zhì)2. 根節(jié)點是黑色。
性質(zhì)3. 每個葉子結(jié)點都帶有兩個空的黑色結(jié)點（被稱為黑哨兵），如果一個結(jié)點n的只有一個左孩子，那么n的右孩子是一個黑哨兵；如果結(jié)點n只有一個右孩子，那么n的左孩子是一個黑哨兵。
性質(zhì)4 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
性質(zhì)5. 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
B樹：
1.所有非葉子結(jié)點至多擁有兩個兒子（Left和Right）；
2.所有結(jié)點存儲一個關(guān)鍵字；
3.非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹；
6. 常見的加密算法？
對稱式加密就是加密和解密使用同一個密鑰。
非對稱式加密就是加密和解密所使用的不是同一個密鑰，通常有兩個密鑰，稱為“公鑰”和“私鑰”，它們兩個必需配對使用。
DES：對稱算法，數(shù)據(jù)加密標(biāo)準(zhǔn)，速度較快，適用于加密大量數(shù)據(jù)的場合；
MD5的典型應(yīng)用是對一段Message產(chǎn)生fingerprint(指紋)，以防止被“篡改”。
RSA是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。
7. https?
HTTP下加入SSL層，HTTPS的安全基礎(chǔ)是SSL。
8.有一個IP庫，給你一個IP,如何能夠快速的從中查找到對應(yīng)的IP段？不用數(shù)據(jù)庫如何實現(xiàn)？要求省空間
9.簡述一致性hash算法。
1）首先求memcached服務(wù)器（節(jié)點）的哈希值，并將其配置到0～232的圓（continuum）。
2）然后采用同樣的方法求出存儲數(shù)據(jù)的鍵的哈希值，并映射到相同的圓上。
3）然后從數(shù)據(jù)映射到的位置開始順時針查找，將數(shù)據(jù)保存到找到的第一個服務(wù)器上。如果超過232仍然找不到服務(wù)器，就會保存到第一臺memcached服務(wù)器上。
11.描述一種hash table的實現(xiàn)方法
1） 除法散列法: p ，令 h(k ) = k mod p ，這里， p 如果選取的是比較大的素數(shù)，效果比較好。而且此法非常容易實現(xiàn)，因此是最常用的方法。最直觀的一種，上圖使用的就是這種散列法，公式： index = value % 16，求模數(shù)其實是通過一個除法運算得到的。
2） 平方散列法 :求index頻繁的操作，而乘法的運算要比除法來得省時。公式： index = (value * value) >> 28 （右移，除以2^28。記法：左移變大，是乘。右移變小，是除）
3） 數(shù)字選擇法:如果關(guān)鍵字的位數(shù)比較多，超過長整型范圍而無法直接運算，可以選擇其中數(shù)字分布比較均勻的若干位，所組成的新的值作為關(guān)鍵字或者直接作為函數(shù)值。
4） 斐波那契（Fibonacci）散列法:平方散列法的缺點是顯而易見的，通過找到一個理想的乘數(shù)index = (value * 2654435769) >> 28
沖突處理：令數(shù)組元素個數(shù)為 S ，則當(dāng) h(k) 已經(jīng)存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發(fā)現(xiàn)空單元，這就是哈希表已經(jīng)滿了，發(fā)生了錯誤。當(dāng)然這是可以通過擴大數(shù)組范圍避免的）。
12、各類樹結(jié)構(gòu)的實現(xiàn)和應(yīng)用
13、hash，任何一個技術(shù)面試官必問（例如為什么一般hashtable的桶數(shù)會取一個素數(shù)？如何有效避免hash結(jié)果值的碰撞）
不選素數(shù)的話可能會造成hash出值的范圍和原定義的不一致
14.什么是平衡二叉樹?
左右子樹都是平衡二叉樹，而且左右子樹的深度差值的約對值不大于1。
15．?dāng)?shù)組和鏈表的優(yōu)缺點
數(shù)組，在內(nèi)存上給出了連續(xù)的空間。鏈表，內(nèi)存地址上可以是不連續(xù)的，每個鏈表的節(jié)點包括原來的內(nèi)存和下一個節(jié)點的信息(單向的一個，雙向鏈表的話，會有兩個)。
數(shù)組優(yōu)于鏈表的:
A. 內(nèi)存空間占用的少。
B. 數(shù)組內(nèi)的數(shù)據(jù)可隨機訪問，但鏈表不具備隨機訪問性。
C. 查找速度快
鏈表優(yōu)于數(shù)組的:
A. 插入與刪除的操作方便。
B. 內(nèi)存地址的利用率方面鏈表好。
C. 方便內(nèi)存地址擴展。
17.最小堆插入，刪除編程實現(xiàn)
18. 4G的long型整數(shù)中找到一個最大的，如何做？
每次從磁盤上盡量多讀一些數(shù)到內(nèi)存區(qū)，然后處理完之后再讀入一批。減少IO次數(shù)，自然能夠提高效率。分批讀入選取最大數(shù)，再對緩存的最大數(shù)進行快排。
19. 有千萬個string在內(nèi)存怎么高速查找，插入和刪除？
對千萬個string做hash，可以實現(xiàn)高速查找，找到了，插入和刪除就很方便了。關(guān)鍵是如何做hash，對string做hash，要減少碰撞頻率。
20.100億個數(shù)，求最大的1萬個數(shù)，并說出算法的時間復(fù)雜度在內(nèi)存中維護一個大小為10000的最小堆，每次從文件讀一個數(shù)，與最小堆的堆頂元素比較，若比堆頂元素大，則替換掉堆頂元素，然后調(diào)整堆。最后剩下的堆內(nèi)元素即為最大的1萬個數(shù)，算法復(fù)雜度為O(NlogN)
21.設(shè)計一個洗牌的算法，并說出算法的時間復(fù)雜度。（1）全局洗牌法
a）首先生成一個數(shù)組，大小為54，初始化為1~54
b）按照索引1到54，逐步對每一張索引牌進行洗牌，首先生成一個余數(shù) value = rand %54，那么我們的索引牌就和這個余數(shù)牌進行交換處理
c）等多索引到54結(jié)束后，一副牌就洗好了
（2）局部洗牌法：索引牌從1開始，到54結(jié)束。這一次索引牌只和剩下還沒有洗的牌進行交換， value = index + rand（） %（54 - index）
算法復(fù)雜度是O(n)
22．請分別用遞歸和非遞歸方法，先序遍歷二叉樹
http://blog.csdn.net/pi9nc/article/details/13008511
24.其他各種排序方法
http://blog.csdn.net/hguisu/article/details/7776068
25.哈希表沖突解決方法？
常見的hash算法如下：
解決沖突的方法：
也叫散列法，主要思想是當(dāng)出現(xiàn)沖突的時候，以關(guān)鍵字的結(jié)果值作為key值輸入，再進行處理，依次直到?jīng)_突解決
線性地址再散列法
當(dāng)沖突發(fā)生時，找到一個空的單元或者全表
二次探測再散列
沖突發(fā)生時，在表的左右兩側(cè)做跳躍式的探測
偽隨機探測再散列
同時構(gòu)造不同的哈希函數(shù)
將同樣的哈希地址構(gòu)造成一個同義詞的鏈表
建立一個基本表和溢出區(qū)，凡是和基本元素發(fā)生沖突都填入溢出區(qū)
六、系統(tǒng)架構(gòu)
1.設(shè)計一個服務(wù)，提供遞增的SessionID服務(wù)，要求保證服務(wù)的高可靠性，有哪些方案？集中式/非集中式/分布式
2.多臺服務(wù)器要執(zhí)行計劃任務(wù)，但只有拿到鎖的任務(wù)才能執(zhí)行，有一個中心服務(wù)器來負(fù)責(zé)分配鎖，但要保證服務(wù)的高可靠性。
3.如何有效的判斷服務(wù)器是否存活？服務(wù)器是否踢出集群的決策如何產(chǎn)生？
4.兩個服務(wù)器如何在同一時刻獲取同一數(shù)據(jù)的時候保證只有一個服務(wù)器能訪問到數(shù)據(jù)？
可以采用隊列進行處理，寫一個隊列接口保證同一時間只有一個進程能夠訪問到數(shù)據(jù)，或者對于存取數(shù)據(jù)庫的來說，數(shù)據(jù)庫也是可以加鎖處理的
性能對服務(wù)器程序來說是至關(guān)重要的了，畢竟每個客戶都期望自己的請求能夠快速的得到響應(yīng)并處理。那么影響服務(wù)器性能的首要因素應(yīng)該是：
（1）系統(tǒng)的硬件資源，比如說CPU個數(shù)，速度，內(nèi)存大小等。不過由于硬件技術(shù)的飛速發(fā)展，現(xiàn)代服務(wù)器都不缺乏硬件資源。因此，需要考慮的主要問題是如何從“軟環(huán)境”來提升服務(wù)器的性能。
服務(wù)器的”軟環(huán)境“
（2）一方面是指系統(tǒng)的軟件資源，比如操作系統(tǒng)允許用戶打開的最大文件描述符數(shù)量
（3）另一方面指的就是服務(wù)器程序本身，即如何從編程的角度來確保服務(wù)器的性能。
主要就要考慮大量并發(fā)的處理這涉及到使用進程池或線程池實現(xiàn)高效的并發(fā)模式（半同步/半異步和領(lǐng)導(dǎo)者/追隨者模式），以及高效的邏輯處理方式--有限狀態(tài)機內(nèi)存的規(guī)劃使用比如使用內(nèi)存池，以空間換時間，被事先創(chuàng)建好，避免動態(tài)分配，減少了服務(wù)器對內(nèi)核的訪問頻率，數(shù)據(jù)的復(fù)制，服務(wù)器程序還應(yīng)該避免不必要的數(shù)據(jù)復(fù)制，尤其是當(dāng)數(shù)據(jù)復(fù)制發(fā)生在用戶空間和內(nèi)核空間之間時。如果內(nèi)核可以直接處理從socket或者文件讀入的數(shù)據(jù)，則應(yīng)用程序就沒必要將這些數(shù)據(jù)從內(nèi)核緩沖區(qū)拷貝到應(yīng)用程序緩沖區(qū)中。這里所謂的“直接處理”，是指應(yīng)用程序不關(guān)心這些數(shù)據(jù)的具體內(nèi)容是什么，不需要對它們作任何分析。比如說ftp服務(wù)器，當(dāng)客戶請求一個文件時，服務(wù)器只需要檢測目標(biāo)文件是否存在，以及是否有權(quán)限讀取就可以了，不需要知道這個文件的具體內(nèi)容，這樣的話ftp服務(wù)器就不需要把目標(biāo)文件讀入應(yīng)用程序緩沖區(qū)然后調(diào)用send函數(shù)來發(fā)送，而是直接使用“零拷貝”函數(shù)sendfile直接將其發(fā)送給客戶端。另外，用戶代碼空間的數(shù)據(jù)賦值也應(yīng)該盡可能的避免復(fù)制。當(dāng)兩個工作進程之間需要傳遞大量的數(shù)據(jù)時，我們就應(yīng)該考慮使用共享內(nèi)存來在他們直接直接共享這些數(shù)據(jù)，而不是使用管道或者消息隊列來傳遞。上下文切換和鎖：并發(fā)程序必須考慮上下文的切換問題，即進程切換或線程切換所導(dǎo)致的系統(tǒng)開銷。即時I/O密集型服務(wù)器也不應(yīng)該使用過多的工作線程（或工作進程），否則進程間切換將占用大量的CPU時間，服務(wù)器真正處理業(yè)務(wù)邏輯的CPU時間比重就下降了。因此為每個客戶連接都創(chuàng)建一個工作線程是不可取的。應(yīng)該使用某種高效的并發(fā)模式。（半同步半異步或者說領(lǐng)導(dǎo)者追隨者模式）另一個問題就是共享資源的加鎖保護。鎖通常被認(rèn)為是導(dǎo)致服務(wù)器效率低下的一個因素，因為由他引入的代碼不僅不處理業(yè)務(wù)邏輯，而且需要訪問內(nèi)核資源，因此如果服務(wù)器有更好的解決方案，應(yīng)該盡量避免使用鎖?；蛘哒f服務(wù)器一定非要使用鎖的話，盡量使用細(xì)粒度的鎖，比如讀寫鎖，當(dāng)工作線程都只讀一塊內(nèi)存區(qū)域時，讀寫鎖不會增加系統(tǒng)開銷，而只有當(dāng)需要寫時才真正需要鎖住這塊內(nèi)存區(qū)域。對于高峰和低峰的伸縮處理，適度的緩存。
6. QQ飛車新用戶注冊時，如何判斷新注冊名字是否已存在？（數(shù)量級：幾億)
可以試下先將用戶名通過編碼方式轉(zhuǎn)換，如轉(zhuǎn)換64位整型。然后設(shè)置N個區(qū)間，每個區(qū)間為2^64/N的大小。對于新的用戶名，先通過2分尋找該用戶名屬于哪個區(qū)間，然后在在這個區(qū)間，做一個hash。對于不同的時間復(fù)雜度和內(nèi)存要求可以設(shè)置不同N的大小~
加一些基礎(chǔ)的技術(shù)面試之外的職業(yè)素養(yǎng)的面試問題
1.你在工作中犯了個錯誤，有同事打你小報告，你如何處理？
a.同事之間應(yīng)該培養(yǎng)和形成良好的同事關(guān)系，就是要互相支持而不是互相拆臺，互相學(xué)習(xí)，互相幫助，共同進步。
b.如果小報告里邊的事情都是事實也就是說確實是本人做的不好不對的方面，那么自己應(yīng)該有則改之，提高自己。如果小報告里邊的事
情全部不是事實，就是說確實誣陷，那么應(yīng)該首先堅持日久見人心的態(tài)度，持之以恒的把本職工作做好，然后在必要的時候通過適當(dāng)?shù)?/p>
方式和領(lǐng)導(dǎo)溝通，相信領(lǐng)導(dǎo)會知道的。
2.你和同事合作完成一個任務(wù)，結(jié)果任務(wù)錯過了截止日期，你如何處理？
3.職業(yè)規(guī)劃？
4.離職原因？
5. 項目中遇到的難題，你是如何解決的?
A．時間 b要求 c.方法
