C和C++經(jīng)典面試題(面試必備)

1、C/C+經(jīng)典面試題面試必備面試題 1：變量的聲明和定義有什么區(qū)別 為變量分配地址和存儲(chǔ)空間的稱為定義， 不分配地址的稱為聲明。 一 個(gè)變量可以在多個(gè)地方聲明，但是只在一個(gè)地方定義。 參加 extern 修飾的是變量的聲明， 說(shuō)明此 變量將在文件以外或在文件后面局部定義。說(shuō)明：很多時(shí)候一個(gè)變量， 只是聲明不分配內(nèi)存空間，直到具體使用 時(shí)才初始化，分配內(nèi)存空間，如外部變量。 面試題 2 ：寫出 bool 、 int 、 float 、指針變量與 “零值 比擬的 if 語(yǔ)句bool 型數(shù)據(jù)：if( flag )A;elseB；int 型數(shù)據(jù)：if( 0 != flag )A;elseB；指針型數(shù)：i

2、f( NULL = flag )A;elseB；float 型數(shù)據(jù)：if ( ( flag >= NORM ) && ( flag <= NORM ) )A；注意：應(yīng)特別注意在 int 、指針型變量和 “零值比擬的時(shí)候，把“零 值放在左邊，這樣當(dāng)把“ = 誤寫成“ =時(shí)，編譯器可以報(bào)錯(cuò)，否那么這種邏輯錯(cuò)誤不容易發(fā)現(xiàn)， 并且可能導(dǎo)致很嚴(yán)重的后果。 面試題 3 ： sizeof 和 strlen 的區(qū) 別 sizeof 和 strlen 有以下區(qū)別：是一個(gè)操作符， 是庫(kù)函數(shù)。 的參數(shù)可以是數(shù)據(jù)的類型，也可以是變量，而 只能以結(jié)尾為 0的字符串作參數(shù)。編譯器在編譯時(shí)就計(jì)算

3、出了 sizeof 的結(jié)果。而 strlen 函數(shù)必須 在運(yùn)行時(shí)才能計(jì)算出來(lái)。并且 sizeof 計(jì)算的是數(shù)據(jù)類型占內(nèi)存的大小，而 strlen 計(jì)算的是字符串實(shí)際的 長(zhǎng)度。數(shù)組做 sizeof 的參數(shù)不退化，傳遞給 strlen 就退化為指針了。 注意：有些是操作符看起來(lái)像是函數(shù)， 而有些函數(shù)名看起來(lái)又像操作 符，這類容易混淆的名稱一定 要加以區(qū)分，否那么遇到數(shù)組名這類特殊數(shù)據(jù)類型作參數(shù)時(shí)就很容易出 錯(cuò)。最容易混淆為函數(shù)的操作符就 是 sizeof 。面試題 4 ： C 語(yǔ)言的關(guān)鍵字 static 和 C+ 的關(guān)鍵字 static 有 什么區(qū)別在 C 中 static 用來(lái)修飾局部靜態(tài)變量和

4、外部靜態(tài)變量、函數(shù)。而C+中除了上述功能外，還用來(lái)定 義類的成員變量和函數(shù)。即靜態(tài)成員和靜態(tài)成員函數(shù)。 注意：編程時(shí) static 的記憶性， 和全局性的特點(diǎn)可以讓在不同時(shí)期 調(diào)用的函數(shù)進(jìn)行通信，傳遞信息，而C+的靜態(tài)成員那么可以在多個(gè)對(duì)象實(shí)例間進(jìn)行通信，傳遞信息。 面試題5 : C中的malloc和C + +中的new有什么區(qū)別 malloc 和 new 有以下不同：1n ew、delete是操作符，可以重載，只能在C+沖使用。2malloc、free是函數(shù)，可以覆蓋，C、C+中都可以使用。 3 new 可以調(diào)用對(duì)象的構(gòu)造函數(shù)， 對(duì)應(yīng)的 delete 調(diào)用相應(yīng)的析 構(gòu)函數(shù)。 4 malloc

5、 僅僅分配內(nèi)存， free 僅僅回收內(nèi)存， 并不執(zhí)行構(gòu)造和 析構(gòu)函數(shù) 5 new、 delete 返回的是某種數(shù)據(jù)類型指針， malloc、 free 返 回的是 void 指針。注意: malloc 申請(qǐng)的內(nèi)存空間要用 free 釋放，而 new 申請(qǐng)的內(nèi) 存空間要用 delete 釋放，不要混用。因?yàn)閮烧邔?shí)現(xiàn)的機(jī)理不同。 面試題 6: 寫一個(gè)“ 標(biāo)準(zhǔn) 宏 MIN #define min(a,b)(a)<=(b)?(a):(b)注意:在調(diào)用時(shí)一定要注意這個(gè)宏定義的副作用，如下調(diào)用: (+*p)<=(x)?(+*p):(x) 。p 指針就自加了兩次，違背了 MIN 的本意。3 面試

6、題 7 ： 一個(gè)指針可以是 volatile 嗎 可以，因?yàn)橹羔樅推胀ㄗ兞恳粯?，有時(shí)也有變化程序的不可控性。常 見例：子中斷效勞子程序修改一個(gè)指向一個(gè) buffer 的指針時(shí)，必須用 volatile 來(lái)修飾這個(gè)指針。 說(shuō)明：指針是一種普通的變量， 從訪問上沒有什么不同于其他變量的 特性。其保存的數(shù)值是個(gè)整型 數(shù)據(jù)，和整型變量不同的是，這個(gè)整型數(shù)據(jù)指向的是一段內(nèi)存地址。 面試題 8 ： a 和 &a 有什么區(qū)別 請(qǐng)寫出以下代碼的打印結(jié)果，主要目的是考察 a 和 &a 的區(qū)別。 #include<stdio.h> void main( void )int a5=1,2

7、,3,4,5; int *ptr=(int *)(&a+1); printf("%d,%d",*(a+1),*(ptr-1); return; 輸出結(jié)果： 2， 5。注意：數(shù)組名 a 可以作數(shù)組的首地址，而 &a 是數(shù)組的指針。思考， 將原式的 int *ptr=(int *)(&a+1);改為 int *ptr=(int *)(a+1); 時(shí)輸出結(jié)果將是什么呢？ 面試題 9 ： 簡(jiǎn)述C、C+程序編譯的內(nèi)存分配情況C C+中內(nèi)存分配方式可以分為三種: 1 從靜態(tài)存儲(chǔ)區(qū)域分配：內(nèi)存在程序編譯時(shí)就已經(jīng)分配好， 這塊內(nèi)存在程序的整個(gè)運(yùn)行期間都 存在。 速度

8、快、 不容易出錯(cuò)，因?yàn)橛邢到y(tǒng)會(huì)善后。 例如全局變量， static 變量等。 2 在棧上分配:在執(zhí)行函數(shù)時(shí)， 函數(shù)內(nèi)局部變量的存儲(chǔ)單元都在棧上創(chuàng)立， 函數(shù)執(zhí)行 結(jié)束時(shí)這些存儲(chǔ)單元自動(dòng)被釋 放。棧內(nèi)存分配運(yùn)算內(nèi)置于處理器的指令集中，效率很高，但是分配 的內(nèi)存容量有限。 3 從堆上分配:即動(dòng)態(tài)內(nèi)存分配。程序在運(yùn)行的時(shí)候用 malloc 或 new 申請(qǐng)任意大 小的內(nèi)存，程序員自己負(fù)責(zé)在何時(shí)用 free 或 delete 釋放內(nèi)存。 動(dòng)態(tài)內(nèi)存的生存期由程序員決定， 使 用非常靈活。 如果在堆上分配了空間， 就有責(zé)任回收它，否那么運(yùn)行的程序會(huì)出現(xiàn)內(nèi)存泄漏， 另外頻繁地分 配和釋放不同大小的堆空間將會(huì)產(chǎn)

9、生堆內(nèi)碎塊。一個(gè)C、C+程序編譯時(shí)內(nèi)存分為 5大存儲(chǔ)區(qū)：堆區(qū)、棧區(qū)、全局區(qū)、文字常量區(qū)、程序代碼區(qū)。4 面試題 10： 簡(jiǎn)述 strcpy、 sprintf 與 memcpy 的區(qū)別 三者主要有以下不同之處： 1 操作對(duì)象不同， strcpy 的兩個(gè)操作對(duì)象均為字符串， sprintf 的操作源對(duì)象可以是多種數(shù)據(jù)類型，目的操作對(duì)象是字符串， memcpy 的兩個(gè)對(duì)象就是兩個(gè)任意可操作 的內(nèi)存地址，并不限于何種數(shù)據(jù)類型。 2 執(zhí)行效率不同， memcpy 最高， strcpy 次之， sprintf 的效 率最低。 3 實(shí)現(xiàn)功能不同， strcpy 主要實(shí)現(xiàn)字符串變量間的拷貝， sprintf

10、主要實(shí)現(xiàn)其他數(shù)據(jù)類型格式到字符串的轉(zhuǎn)化， memcpy 主要是內(nèi)存塊間的拷貝。說(shuō)明： strcpy 、 sprintf 與 memcpy 都可以實(shí)現(xiàn)拷貝的功能，但是 針對(duì)的對(duì)象不同，根據(jù)實(shí)際需求，來(lái) 選擇適宜的函數(shù)實(shí)現(xiàn)拷貝功能。 面試題 11： 設(shè)置地址為 0x67a9 的整型變量的值為 0xaa66int *ptr;ptr = (int *)0x67a9;*ptr = 0xaa66;說(shuō)明：這道題就是強(qiáng)制類型轉(zhuǎn)換的典型例子， 無(wú)論在什么平臺(tái)地址長(zhǎng) 度和整型數(shù)據(jù)的長(zhǎng)度是一樣的， 即一個(gè)整型數(shù)據(jù)可以強(qiáng)制轉(zhuǎn)換成地址指針類型， 只要有意義即可。 面 試題 12 ： 面向?qū)ο蟮娜筇卣?面向?qū)ο蟮娜筇?/p>

11、征是封裝性、繼承性和多態(tài)性： 封裝性：將客觀事物抽象成類，每個(gè)類對(duì)自身的數(shù)據(jù)和方法實(shí)行protection private， protected ，public。繼承性：廣義的繼承有三種實(shí)現(xiàn)形式： 實(shí)現(xiàn)繼承 使用基類的 屬性和方法而無(wú)需額外編碼的能力 、可 視繼承子窗體使用父窗體的外觀和實(shí)現(xiàn)代碼 、接口繼承 僅使用屬性 和方法 ,實(shí)現(xiàn)滯后到子類實(shí)現(xiàn) 。多態(tài)性：是將父類對(duì)象設(shè)置成為和一個(gè)或更多它的子對(duì)象相等的 技術(shù)。用子類對(duì)象給父類對(duì)象賦值 之后，父類對(duì)象就可以根據(jù)當(dāng)前賦值給它的子對(duì)象的特性以不同的方 式運(yùn)作。 說(shuō)明：面向?qū)ο蟮娜齻€(gè)特征是實(shí)現(xiàn)面向?qū)ο蠹夹g(shù)的關(guān)鍵， 每一個(gè)特征 的相關(guān)技術(shù)都非常的復(fù)

12、雜，程序員應(yīng)該多看、多練。 面試題13 : C+的空類有哪些成員函數(shù)缺省構(gòu)造函數(shù)。缺省拷貝構(gòu)造函數(shù)。缺省析構(gòu)函數(shù)。缺省賦值運(yùn)算符。缺省取址運(yùn)算符。 缺省取址運(yùn)算符 const。 注意:有些書上只是簡(jiǎn)單的介紹了前四個(gè)函數(shù)。 沒有提及后面這兩個(gè) 函數(shù)。但后面這兩個(gè)函數(shù)也是空類的默認(rèn)函數(shù)。 另外需要注意的是， 只有當(dāng)實(shí)際使用這些函數(shù)的時(shí)候，編譯器才會(huì)去定義它們5 面試題 14 :談?wù)勀銓?duì)拷貝構(gòu)造函數(shù)和賦值運(yùn)算符的認(rèn)識(shí)拷貝構(gòu)造函數(shù)和賦值運(yùn)算符重載有以下兩個(gè)不同之處： 1拷貝構(gòu)造函數(shù)生成新的類對(duì)象，而賦值運(yùn)算符不能。 2由于拷貝構(gòu)造函數(shù)是直接構(gòu)造一個(gè)新的類對(duì)象， 所以在初始化 這個(gè)對(duì)象之前不用檢驗(yàn)源對(duì)象

13、是否和新建對(duì)象相同。 而賦值運(yùn)算符那么需要這個(gè)操作， 另外賦值運(yùn)算 中如果原來(lái)的對(duì)象中有內(nèi)存分配要先把內(nèi)存釋放掉注意：當(dāng)有類中有指針類型的成員變量時(shí)， 一定要重寫拷貝構(gòu)造函數(shù) 和賦值運(yùn)算符，不要使用默認(rèn)的。面試題15 :用C+設(shè)計(jì)一個(gè)不能被繼承的類template <typename T> class Afriend T;private:A() A() ;class B : virtual public A<B>public:B() B() ;class C : virtual public Bpublic:C() C() ;void main( void )B b;/

14、C c;return;注意：構(gòu)造函數(shù)是繼承實(shí)現(xiàn)的關(guān)鍵，每次子類對(duì)象構(gòu)造時(shí)，首先調(diào)用 的是父類的構(gòu)造函數(shù)，然后才是自己的。 面試題 16 ： 訪問基類的私有虛函數(shù) 寫出以下程序的輸出結(jié)果：#include <iostream.h>class Avirtual void g()cout << "A:g" << endl;private:virtual void f()cout << "A:f" << endl;class B : public Avoid g()cout << "

15、;B:g" << endl;virtual void h()cout << "B:h" << endl; ;typedef void( *Fun )( void );void main()B b;Fun pFun;for(int i = 0 ; i < 3; i+)pFun = ( Fun )*( ( int* ) * ( int* )( &b ) + i );pFun();輸出結(jié)果：B:gA:fB:h注意：此題主要考察了面試者對(duì)虛函數(shù)的理解程度。 一個(gè)對(duì)虛函數(shù)不 了解的人很難正確的做出此題。在學(xué)習(xí)面向?qū)ο蟮亩鄳B(tài)性

16、時(shí)一定要深刻理解虛函數(shù)表的工作原理。面試題 17 ： 簡(jiǎn)述類成員函數(shù)的重寫、重載和隱藏的區(qū)別 1重寫和重載主要有以下幾點(diǎn)不同。范圍的區(qū)別： 被重寫的和重寫的函數(shù)在兩個(gè)類中，而重載和被重載的函數(shù)在同一個(gè)類中。參數(shù)的區(qū)別： 被重寫函數(shù)和重寫函數(shù)的參數(shù)列表一定相同，而被重載函數(shù)和重載函數(shù)的參數(shù)列表一定不同。的區(qū)別：重寫的基類中被重寫的函數(shù)必須要有修飾，而重載函數(shù)和被重載函數(shù)可以被修飾，也可以沒有。 2隱藏和重寫、重載有以下幾點(diǎn)不同。 與重載的范圍不同：和重寫一樣，隱藏函數(shù)和被隱藏函數(shù)不在同 一個(gè)類中。參數(shù)的區(qū)別： 隱藏函數(shù)和被隱藏的函數(shù)的參數(shù)列表可以相同，也 可不同，但是函數(shù)名肯定要相同。 當(dāng)參數(shù)不

17、相同時(shí)，無(wú)論基類中的參數(shù)是否被 virtual 修飾，基類的函 數(shù)都是被隱藏，而不是被重寫。 說(shuō)明：雖然重載和覆蓋都是實(shí)現(xiàn)多態(tài)的根底， 但是兩者實(shí)現(xiàn)的技術(shù)完 全不相同，到達(dá)的目的也是完 全不同的，覆蓋是動(dòng)態(tài)態(tài)綁定的多態(tài)， 而重載是靜態(tài)綁定的多態(tài)。 面 試題 18 ： 簡(jiǎn)述多態(tài)實(shí)現(xiàn)的原理 編譯器發(fā)現(xiàn)一個(gè)類中有虛函數(shù)， 便會(huì)立即為此類生成虛函數(shù)表 vtable。 虛函數(shù)表的各表項(xiàng)為指向?qū)?yīng)虛函數(shù)的指針。編譯器還會(huì)在此類中隱含插入一個(gè)指針vpt對(duì)VC編譯器來(lái)說(shuō)，它插在類的第一個(gè)位 置上指向虛函數(shù)表。 調(diào)用此類的構(gòu)造函數(shù)時(shí)， 在類的構(gòu)造函數(shù)中， 編譯器會(huì)隱含執(zhí)行 vptr 與 vtable 的關(guān)聯(lián)代碼

18、，將 vptr 指向?qū)?yīng)的 vtable， 將類與此類的 vtable 聯(lián)系 了起來(lái)。 另外在調(diào)用類的構(gòu)造函數(shù)時(shí)， 指向根底類的指針此時(shí)已經(jīng)變成指向具體的類的 this 指針，這樣依 靠此 this 指針即可得到正確的 vtable，。 如此才能真正與函數(shù)體進(jìn)行連接， 這就是動(dòng)態(tài)聯(lián)編， 實(shí)現(xiàn)多態(tài)的根本 原理。 注意：一定要區(qū)分虛函數(shù)，純虛函數(shù)、虛擬繼承的關(guān)系和區(qū)別。牢記 虛函數(shù)實(shí)現(xiàn)原理，因?yàn)槎鄳B(tài)C+面試的重要考點(diǎn)之一，而虛函數(shù)是實(shí)現(xiàn)多態(tài)的根底。面試題 19 ： 鏈表和數(shù)組有什么區(qū)別 數(shù)組和鏈表有以下幾點(diǎn)不同： 1存儲(chǔ)形式： 數(shù)組是一塊連續(xù)的空間，聲明時(shí)就要確定長(zhǎng)度。 鏈表是一塊可不連續(xù)的動(dòng)態(tài)空

19、間， 長(zhǎng)度可變，每個(gè)結(jié)點(diǎn)要保存相鄰結(jié)點(diǎn)指針。 2數(shù)據(jù)查找： 數(shù)組的線性查找速度快， 查找操作直接使用偏移 地址。 鏈表需要按順序檢索結(jié)點(diǎn)，效率低。 3數(shù)據(jù)插入或刪除： 鏈表可以快速插入和刪除結(jié)點(diǎn)， 而數(shù)組那么 可能需要大量數(shù)據(jù)移動(dòng)。 4越界問題： 鏈表不存在越界問題，數(shù)組有越界問題。 說(shuō)明：在選擇數(shù)組或鏈表數(shù)據(jù)結(jié)構(gòu)時(shí)， 一定要根據(jù)實(shí)際需要進(jìn)行選擇。 數(shù)組便于查詢，鏈表便于插入刪除。數(shù)組節(jié)省空間但是長(zhǎng)度固定， 鏈表雖然變長(zhǎng)但是占了更多的 存儲(chǔ)空間。面試題 20 ： 怎樣把一個(gè)單鏈表反序 1 反轉(zhuǎn)一個(gè)鏈表。循環(huán)算法。List reverse(List n)if(!n) / 判斷鏈表是否為空，為空即

20、退出。return n;list cur = n.next; /保存頭結(jié)點(diǎn)的下個(gè)結(jié)點(diǎn)list pre = n; / 保存頭結(jié)點(diǎn)list tmp;8pre.next = null; /頭結(jié)點(diǎn)的指針指空，轉(zhuǎn)換后變尾結(jié)點(diǎn)while ( NULL != cur.next ) /循環(huán)直到 cur.next 為空tmp = cur; / 實(shí)現(xiàn)如圖 10.3 圖 10.5 所示tmp.next = prepre = tmp;cur = cur.next;return tmp; /f 返回頭指針 2 反轉(zhuǎn)一個(gè)鏈表。遞歸算法。List *reverse( List *oldList, List *newHead

21、 = NULL )List *next = oldList-> next; /記錄上次翻轉(zhuǎn)后的鏈表oldList-> next = newHead; / 將當(dāng)前結(jié)點(diǎn)插入到翻轉(zhuǎn)后鏈表的開 頭newHead = oldList; / 遞歸處理剩余的鏈表return ( next=NULL )? newHead: reverse( t, newHead );說(shuō)明： 循環(huán)算法就是圖 10.2 圖 10.5 的移動(dòng)過程， 比擬好理解和 想到。遞歸算法的設(shè)計(jì)雖有一點(diǎn)難 度，但是理解了循環(huán)算法，再設(shè)計(jì)遞歸算法就簡(jiǎn)單多了。面試題 21 ：簡(jiǎn)述隊(duì)列和棧的異同隊(duì)列和棧都是線性存儲(chǔ)結(jié)構(gòu)， 但是兩者的插入

22、和刪除數(shù)據(jù)的操作不同， 隊(duì)列是“先進(jìn)先出，棧是“后進(jìn)先出。注意：區(qū)別棧區(qū)和堆區(qū)。 堆區(qū)的存取是 “順序隨意，而棧區(qū)是“后進(jìn) 先出。棧由編譯器自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于 數(shù)據(jù)結(jié)構(gòu)中的棧。 堆一般由程序員分配釋放， 假設(shè)程序員不釋放，程序結(jié)束時(shí)可能由 OS 回收。分配 方式類似于鏈表。它與此題中的堆和棧是兩回事。 堆棧只是一種數(shù)據(jù)結(jié)構(gòu)， 而堆區(qū)和棧 區(qū)是程序的不同內(nèi)存存儲(chǔ)區(qū)域。面試題 22 ： 能否用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列的功能 結(jié)點(diǎn)結(jié)構(gòu)體：typedef struct nodeint data; node *next;node,*LinkStack; 創(chuàng)立空棧

23、：LinkStack CreateNULLStack( LinkStack &S)S= (LinkStack)malloc( sizeof( node ) ); 申/ 請(qǐng)新結(jié)點(diǎn) if( NULL = S)printf("Fail to malloc a new node.n");9return NULL; S->data = 0; / 初始化新結(jié)點(diǎn)S->next = NULL;return S;棧的插入函數(shù)：LinkStack Push( LinkStack &S, int data)if( NULL = S) /檢/ 驗(yàn)棧printf(&quo

24、t;There no node in stack!");return NULL;LinkStack p = NULL;申請(qǐng)新結(jié)點(diǎn)p = (LinkStack)malloc( sizeof( node ) ); / if( NULL = p)printf("Fail to malloc a new node.n"); return S;if( NULL = S->next)p->next = NULL;elsep->next = S->next; p->data = data; / 初始化新結(jié)點(diǎn)S->next = p; / 插入新

25、結(jié)點(diǎn) return S;出棧函數(shù)：node Pop( LinkStack &S)node temp;temp.data = 0;temp.next = NULL;if( NULL = S) /檢/ 驗(yàn)棧printf("There no node in stack!"); return temp;temp = *S;10 if( S->next = NULL ) printf("The stack is NULL,can't pop!n"); return temp;LinkStack p = S ->next; /節(jié)點(diǎn)出棧S-

26、>next = S->next->next; temp = *p;free( p ); p = NULL; return temp; 雙棧實(shí)現(xiàn)隊(duì)列的入隊(duì)函數(shù)： LinkStack StackToQueuPush( LinkStack &S, int data) node n;LinkStack S1 = NULL;CreateNULLStack( S1 ); 創(chuàng)/ 建空棧while( NULL != S->next ) /S 出棧入 S1 n = Pop( S );Push( S1, n.data );Push( S1, data ); /新結(jié)點(diǎn)入棧while(

27、 NULL != S1->next ) /S1出棧入 Sn = Pop( S1 );Push( S, n.data );return S;說(shuō)明：用兩個(gè)棧能夠?qū)崿F(xiàn)一個(gè)隊(duì)列的功能， 那用兩個(gè)隊(duì)列能否實(shí)現(xiàn)一 個(gè)隊(duì)列的功能呢？結(jié)果是否認(rèn) 的，因?yàn)闂Ｊ窍冗M(jìn)后出，將兩個(gè)棧連在一起，就是先進(jìn)先出。而隊(duì)列 是現(xiàn)先進(jìn)先出，無(wú)論多少個(gè)連在一 起都是先進(jìn)先出，而無(wú)法實(shí)現(xiàn)先進(jìn)后出。面試題 23 ： 計(jì)算一顆二叉樹的深度 深度的計(jì)算函數(shù)：int depth(BiTree T)if(!T) return 0; / 判斷當(dāng)前結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)11int d1= depth(T->lchild); / int d

28、2= depth(T->rchild); /求當(dāng)前結(jié)點(diǎn)的左孩子樹的深度求當(dāng)前結(jié)點(diǎn)的右孩子樹的深度return (d1>d2?d1:d2)+1; 注意：根據(jù)二叉樹的結(jié)構(gòu)特點(diǎn)，很多算法都可以用遞歸算法來(lái)實(shí)現(xiàn)。 面試題 24 ： 編碼實(shí)現(xiàn)直接插入排序 直接插入排序編程實(shí)現(xiàn)如下：#include<iostream.h>void main( void )int ARRAY10 = 0, 6, 3, 2, 7, 5, 4, 9, 1, 8 ;int i,j;for( i = 0; i < 10; i+) cout<<ARRAYi<<" &qu

29、ot;cout<<endl;for( i = 2; i <= 10; i+ ) /將 ARRAY2,ARRAYn依次按序插入if(ARRAYi < ARRAYi-1) /如果 ARRAYi大于一切有序的數(shù)值，/ARRAYi 將保持原位不動(dòng)ARRAY0二 ARRAYi; / 將 ARRAY0看做是哨兵，是 ARRAYi的 副本j = i - 1;do / 從右向左在有序區(qū) ARRAY1 i-1 中/ 查找 ARRAYi 的插入位置ARRAYj+1 = ARRAYj; / 將數(shù)值大于 ARRAYi 記錄后移j- ;while( ARRAY0 < ARRAYj );AR

30、RAYj+1=ARRAY0; /ARRAYi 插入到正確的位置上for( i = 0; i < 10; i+)cout<<ARRAYi<<" "cout<<endl;12注意： 所有為簡(jiǎn)化邊界條件而引入的附加結(jié)點(diǎn) 元素 均可稱為 哨兵。引入哨兵后使得查找循環(huán)條件的時(shí)間大約減少了一半， 對(duì)于記錄數(shù)較大的文件節(jié)約的時(shí)間就相 當(dāng)可觀。類似于排序這樣使用頻率非常高的算法， 要盡可能地減少其運(yùn)行時(shí)間。 所以不能把上述算法中的 哨兵視為雕蟲小技。 面試題 25 ： 編碼實(shí)現(xiàn)冒泡排序 冒泡排序編程實(shí)現(xiàn)如下：#include <stdio.h

31、>#define LEN 10 /數(shù)組長(zhǎng)度void main( void )int ARRAY10 = 0, 6, 3, 2, 7, 5, 4, 9, 1, 8 ; /數(shù)組printf( "n" );for( int a = 0; a < LEN; a+ ) /打印數(shù)組內(nèi)容printf( "%d ", ARRAYa );int i = 0;int j = 0;bool isChange; / 設(shè)定交換標(biāo)志for( i = 1; i < LEN; i+ ) / 最多做 LEN-1 趟排序isChange = 0; / 本趟排序開始前 ,

32、交換標(biāo)志應(yīng)為假 for( j = LEN-1; j >= i; j- ) /對(duì)當(dāng)前無(wú)序區(qū)自下向上掃描待排序ARRAYi.LENif( ARRAYj+1 < ARRAYj ) / 交換記錄ARRAY0 = ARRAYj+1; /ARRAY0 不是哨兵 , 僅做暫存單元ARRAYj+1 = ARRAYj;ARRAYj = ARRAY0;isChange = 1; / 發(fā)生了交換 , 故將交換標(biāo)志置為真printf( "n" );for( a = 0; a < LEN; a+) /打印本次排序后數(shù)組內(nèi)容printf( "%d ", ARRAY

33、a );if( !isChange ) / 本趟排序未發(fā)生交換 ,提前終止算法break;printf( "n" );return;13 面試題 26 ： 編碼實(shí)現(xiàn)直接選擇排序 #include"stdio.h" #define LEN 9void main( void )待序數(shù)組int ARRAYLEN= 5, 6, 8, 2, 4, 1, 9, 3, 7 ; / printf("Before sorted:n");for( int m = 0; m < LEN; m+ ) /打印排序前數(shù)組printf( "%d &

34、quot;, ARRAYm );for (int i = 1; i <= LEN - 1; i+) /選擇排序int t = i - 1;int temp = 0;for (int j = i; j < LEN; j+)if (ARRAYj < ARRAYt)t = j;if (t != (i - 1)temp = ARRAYi - 1;ARRAYi - 1 = ARRAYt;ARRAYt = temp;printf( "n" );printf("After sorted:n");for( i = 0; i < LEN; i+ )

35、 /打印排序后數(shù)組printf( "%d ", ARRAYi );printf( "n" ); 注意：在直接選擇排序中，具有相同關(guān)鍵碼的對(duì)象可能會(huì)顛倒次序， 因而直接選擇排序算法是一種不穩(wěn)定的排序方法。 在本例中只是例舉了簡(jiǎn)單的整形數(shù)組排序， 肯定 不會(huì)有什么問題。但是在復(fù)雜的數(shù)據(jù)元素序列組合中， 只是根據(jù)單一的某一個(gè)關(guān)鍵值排序， 直接選擇排 序那么不保證其穩(wěn)定性，這是直接選擇排序的一個(gè)弱點(diǎn)。 面試題 27 ： 編程實(shí)現(xiàn)堆排序 堆排序編程實(shí)現(xiàn)：#include <stdio.h>void createHeep(int ARRAY,int sP

36、oint, int Len) /生/ 成大根堆while( ( 2 * sPoint + 1 ) < Len )int mPoint = 2 * sPoint + 1 ;if( ( 2 * sPoint + 2 ) < Len )if(ARRAY 2 * sPoint + 1 < ARRAY 2 * sPoint + 2 )mPoint = 2*sPoint+2;if(ARRAY sPoint < ARRAY mPoint ) /堆被破壞，需要重新調(diào)整int tmpData= ARRAY sPoint ; / 交換 sPoint 與 mPoint 的數(shù) 據(jù)ARRAY s

37、Point = ARRAY mPoint ;ARRAY mPoint = tmpData;sPoint = mPoint ;elsebreak; / 堆未破壞，不再需要調(diào)整return;void heepSort( int ARRAY, int Len ) / 堆排序int i=0;for ( i = ( Len / 2 - 1 ); i >= 0; i- ) /將 Hr0 ， Lenght-1 建成大根堆createHeep(ARRAY, i, Len);for ( i = Len - 1; i > 0; i- )int tmpData = ARRAY0; / 與最后一個(gè)記錄交換

38、ARRAY0 = ARRAYi;ARRAYi = tmpData;createHeep( ARRAY, 0, i ); /將 H.r0.i 重新調(diào)整為大根堆return; int main( void )15int ARRAY = 5, 4, 7, 3, 9, 1, 6, 8, 2;printf("Before sorted:n"); / 打印排序前數(shù)組內(nèi)容for ( int i = 0; i < 9; i+ )printf("%d ", ARRAYi);printf("n");heepSort( ARRAY, 9 ); / 堆

39、排序printf("After sorted:n"); /打印排序后數(shù)組內(nèi)容for( i = 0; i < 9; i+ )printf( "%d ", ARRAYi );printf( "n" );return 0;說(shuō)明：堆排序，雖然實(shí)現(xiàn)復(fù)雜，但是非常的實(shí)用。另外讀者可是自己 設(shè)計(jì)實(shí)現(xiàn)小堆排序的算法。雖然和大堆排序的實(shí)現(xiàn)過程相似， 但是卻可以加深對(duì)堆排序的記憶和理 解。 面試題 28 ： 編程實(shí)現(xiàn)基數(shù)排序#include <stdio.h>#include <malloc.h>#define LEN 8t

40、ypedef struct node /隊(duì)列結(jié)點(diǎn)int data;struct node * next;node,*QueueNode;typedef struct Queue /隊(duì)列QueueNode front;QueueNode rear;Queue,*QueueLink;創(chuàng)立空隊(duì)列QueueLink CreateNullQueue( QueueLink &Q) /Q = NULL;Q = ( QueueLink )malloc( sizeof( Queue ) );if( NULL = Q )printf("Fail to malloc null queue!n&qu

41、ot;);return NULL;16Q->front = ( QueueNode )malloc( sizeof( node ) );Q->rear = ( QueueNode )malloc( sizeof( node ) ); if( NULL = Q->front | NULL = Q->rear )printf("Fail to malloc a new queue's fornt or rear!n"); return NULL; Q->rear = NULL;Q->front->next= Q->rear

42、; return Q;int lenData( node data, int len) / 計(jì)算隊(duì)列中各結(jié)點(diǎn)的數(shù)據(jù) 的最大位數(shù)int m = 0;int temp = 0;int d;for( int i = 0; i < len; i+)d = datai.data;while( d > 0) d /= 10; temp +; if( temp > m ) m = temp;temp = 0;return m;將數(shù)據(jù)壓入隊(duì)列QueueLink Push( QueueLink &Q , node node ) / QueueNode p1,p;p =( QueueNo

43、de )malloc( sizeof( node ) );if( NULL = p )printf("Fail to malloc a new node!n");return NULL; p1 = Q->front; while(p1->next != NULL) p1 = p1->next; p->data = node.data; p1->next = p; p->next = Q->rear;17return NULL;數(shù)據(jù)出隊(duì)列node Pop( QueueLink &Q) / node temp; temp.dat

44、a = 0; temp.next = NULL; QueueNode p; p = Q->front->next; if( p != Q->rear ) temp = *p;Q->front->next = p->next;free( p );p = NULL;return temp;int IsEmpty( QueueLink Q)if( Q->front->next = Q->rear )return 0;return 1;int main( void )int i = 0;int Max = 0; /記錄結(jié)點(diǎn)中數(shù)據(jù)的最大位數(shù)int d

45、 = 10;int power = 1;int k = 0; 781,NULL,node ArrayLEN =450, NULL, 32,NULL, 57 ,NULL, 組 145,NULL, 613,NULL, 401,NULL, 594,NULL;/ 隊(duì)列結(jié)點(diǎn)數(shù)QueueLink Queue10;for( i = 0; i < 10; i+)CreateNullQueue( Queuei); /for( i = 0; i < LEN; i+)printf("%d ",Arrayi.data);printf("n");Max = lenDa

46、ta( Array, LEN ); /printf("%dn",Max);18for(int j = 0; j < Max; j+) /if(j = 0) power = 1; else power = power *d;for(i = 0; i < LEN; i+)初始化隊(duì)列數(shù)組計(jì)算數(shù)組中關(guān)鍵字的最大位數(shù)按位排序k = Arrayi.data /power - (Arrayi.data/(power * d) * d;Push( Queuek, Arrayi );for(int l = 0, k = 0; l < d; l+) /排序后出隊(duì)列重入數(shù)組wh

47、ile( IsEmpty( Queuel ) )Arrayk+ = Pop( Queuel );for( int t = 0; t < LEN; t+)printf("%d ",Arrayt.data);printf("n");return 0;說(shuō)明：隊(duì)列為基數(shù)排序的實(shí)現(xiàn)提供了很大的方便， 適當(dāng)?shù)臄?shù)據(jù)機(jī)構(gòu)可 以減少算法的復(fù)雜度，讓更多的算法實(shí)現(xiàn)更容易。 面試題 29 ：談?wù)勀銓?duì)編程標(biāo)準(zhǔn)的理解或認(rèn)識(shí) 編程標(biāo)準(zhǔn)可總結(jié)為：程序的可行性，可讀性、可移植性以及可測(cè)試性。說(shuō)明： 這是編程標(biāo)準(zhǔn)的總綱目，面試者不一定要去背誦上面給出的 那幾個(gè)例子，應(yīng)該去理解這幾個(gè)

48、 例子說(shuō)明的問題，想一想，自己如何解決可行性、可讀性、可移植性 以及可測(cè)試性這幾個(gè)問題，結(jié)合以 上幾個(gè)例子和自己平時(shí)的編程習(xí)慣來(lái)答復(fù)這個(gè)問題。 面試題 30： short i = 0; i = i + 1L；這兩句有錯(cuò)嗎代碼一是錯(cuò)的，代碼二是正確的。 說(shuō)明：在數(shù)據(jù)平安的情況下大類型的數(shù)據(jù)向小類型的數(shù)據(jù)轉(zhuǎn)換一定要 顯示的強(qiáng)制類型轉(zhuǎn)換。 面試題 31： &&和&、 | 和|有什么區(qū)別 1 &和| 對(duì)操作數(shù)進(jìn)行求值運(yùn)算， &&和| 只是判斷邏輯關(guān)系。 19 2 && 和 | 在在判斷左側(cè)操作數(shù)就能確定結(jié)果的情況下就不再對(duì) 右側(cè)操作數(shù)求值

49、。注意：在編程的時(shí)候有些時(shí)候?qū)?&&或| 替換成&或| 沒有出錯(cuò)，但是其 邏輯是錯(cuò)誤的，可能會(huì)導(dǎo)致不 可預(yù)想的后果比方當(dāng)兩個(gè)操作數(shù)一個(gè)是 1 另一個(gè)是 2 時(shí)。面試題32 : C+的引用和C語(yǔ)言的指針有什么區(qū)別 指針和引用主要有以下區(qū)別： 1 引用必須被初始化，但是不分配存儲(chǔ)空間。 指針不聲明時(shí)初 始化，在初始化的時(shí)候需要分配 存儲(chǔ)空間。 2 引用初始化以后不能被改變，指針可以改變所指的對(duì)象。 3 不存在指向空值的引用，但是存在指向空值的指針。 注意：引用作為函數(shù)參數(shù)時(shí)， 會(huì)引發(fā)一定的問題，因?yàn)樽屢米鲄?shù)， 目的就是想改變這個(gè)引用所指向地址的內(nèi)容， 而函數(shù)調(diào)用時(shí)傳入的

50、是實(shí)參， 看不出函數(shù)的參數(shù)是 正常變量，還是引用，因此可能會(huì) 引發(fā)錯(cuò)誤。所以使用時(shí)一定要小心謹(jǐn)慎。面試題 33 ： 在二元樹中找出和為某一值的所有路徑 輸入一個(gè)整數(shù)和一棵二元樹。 從樹的根結(jié)點(diǎn)開始往下訪問， 一直到葉 結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一 條路徑。打印出和與輸入整數(shù)相等的所有路徑。 例如，輸入整數(shù) 9 和 如下二元樹：32 65 4那么打印出兩條路徑： 3， 6 和 3， 2， 4【答案】typedef struct pathBiTNode* tree; /結(jié)點(diǎn)數(shù)據(jù)成員struct path* next; /結(jié)點(diǎn)指針成員PATH,*pPath;初始化樹的結(jié)點(diǎn)棧：void init_pat

51、h( pPath* L )*L = ( pPath )malloc( sizeof( PATH ) );創(chuàng)/ 建空樹( *L )->next = NULL;樹結(jié)點(diǎn)入棧函數(shù)：void push_path(pPath H, pBTree T)pPath p = H->next;pPath q = H;while( NULL != p )20q = p;p = p->next;p = ( pPath )malloc( sizeof( PATH ) ); 申/ 請(qǐng)新結(jié)點(diǎn) p->next = NULL; / 初始化新結(jié)點(diǎn) p->tree = T;q->next = p

52、; / 新結(jié)點(diǎn)入棧樹結(jié)點(diǎn)打印函數(shù)：void print_path( pPath L )pPath p = L->next;while( NULL != p ) /打印當(dāng)前棧中所有數(shù)據(jù)printf("%d, ", p->tree->data);p = p->next;樹結(jié)點(diǎn)出棧函數(shù)：void pop_path( pPath H )pPath p = H->next;pPath q = H;if( NULL = p ) /檢驗(yàn)當(dāng)前棧是否為空printf("Stack is null!n");return;p = p->ne

53、xt;while( NULL != p ) / 出棧q = q->next;p = p->next;free( q->next ); /釋放出棧結(jié)點(diǎn)空間q->next = NULL; 判斷結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)： int IsLeaf(pBTree T)return ( T->lchild = NULL )&&( T->rchild=NULL );查找符合條件的路徑：int find_path(pBTree T, int sum, pPath L)21push_path( L, T);record += T->data;if( ( reco

54、rd = sum ) && ( IsLeaf( T ) ) ) /打/ 印符合條件的當(dāng)前路徑 print_path( L ); printf( "n" );if( T->lchild != NULL ) /遞歸查找當(dāng)前節(jié)點(diǎn)的左孩子find_path( T->lchild, sum, L);if( T->rchild != NULL ) /遞歸查找當(dāng)前節(jié)點(diǎn)的右孩子find_path( T->rchild, sum, L);record -= T->data; pop_path(L);return 0;注意：數(shù)據(jù)結(jié)構(gòu)一定要活學(xué)活用，

55、 例如此題，把所有的結(jié)點(diǎn)都?jí)喝霔＃?而不符合條件的結(jié)點(diǎn)彈出棧，很容易實(shí)現(xiàn)了有效路徑的查找。 雖然用鏈表也可以實(shí)現(xiàn)， 但是用棧更 利于理解這個(gè)問題，即適當(dāng)?shù)臄?shù)據(jù) 結(jié)構(gòu)為更好的算法設(shè)計(jì)提供了有利的條件。 面試題 34 ：寫一個(gè)“標(biāo) 準(zhǔn) 宏 MIN寫一個(gè)“標(biāo)準(zhǔn)宏MIN,這個(gè)宏輸入兩個(gè)參數(shù)并且返回較小的一個(gè)?！?答案】#define min(a,b)(a)<=(b)?(a):(b) 注意：在調(diào)用時(shí)一定要注意這個(gè)宏定義的副作用，如下調(diào)用： (+*p)<=(x)?(+*p):(x) 。p 指針就自加了兩次，違背了 MIN 的本意。 面試題 35 ： typedef 和 define 有什么區(qū)別

56、 1用法不同： typedef 用來(lái)定義一種數(shù)據(jù)類型的別名， 增強(qiáng)程序 的可讀性。 define 主要用來(lái)定義 常量，以及書寫復(fù)雜使用頻繁的宏。 2 執(zhí)行時(shí)間不同： typedef 是編譯過程的一局部，有類型檢查 的功能。 define 是宏定義，是預(yù)編 譯的局部，其發(fā)生在編譯之前，只是簡(jiǎn)單的進(jìn)行字符串的替換，不進(jìn) 行類型的檢查。 3作用域不同： typedef 有作用域限定。 define 不受作用域約 束，只要是在 define 聲明后的引用都是正確的。 4對(duì)指針的操作不同： typedef 和 define 定義的指針時(shí)有很大 的區(qū)別。注意： typedef 定義是語(yǔ)句，因?yàn)榫湮惨由戏痔?hào)。而 define 不 是語(yǔ)句，千萬(wàn)不能在句尾加分號(hào)。22 面試題 36 ： 關(guān)鍵字 const 是什么const 用來(lái)定義一個(gè)只讀的變量或?qū)ο?。主要?yōu)點(diǎn)：便于類型檢