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ù)：if( NULL =

2、 flag )A;elseB；float 型數(shù)據(jù)：if ( ( flag >= NORM ) && ( flag <= NORM ) )A； 2注意：應(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ū)別：q sizeof 是一個(gè)操作符， strlen 是庫(kù)函數(shù)。q sizeof 的參數(shù)可以是數(shù)據(jù)的類型，也可以是變量，而 strlen 只能以結(jié)尾為0

3、的字符串作參數(shù)。q 編譯器在編譯時(shí)就計(jì)算出了 sizeof 的結(jié)果。而 strlen 函數(shù)必須在運(yùn)行時(shí)才能計(jì)算出來(lái)。并且 sizeof計(jì)算的是數(shù)據(jù)類型占內(nèi)存的大小，而 strlen 計(jì)算的是字符串實(shí)際的長(zhǎng)度。q 數(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)

4、修飾局部靜態(tài)變量和外部靜態(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： 中的 malloc 和中的 new 有什么區(qū)別malloc 和 new 有以下不同：（ 1） new、 delete 是操作符，可以重載，只能在 C+中使用。（ 2） malloc、 free 是函數(shù)，可以覆蓋， C、 C+中都可以使用。（ 3） new 可以調(diào)用對(duì)象的構(gòu)造函數(shù)，對(duì)應(yīng)的 delete 調(diào)用相

5、應(yīng)的析構(gòu)函數(shù)。（ 4） malloc 僅僅分配內(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 指針就自加了兩次，違背

6、了 MIN 的本意。3 面試題 7： 一個(gè)指針可以是 volatile 嗎可以，因?yàn)橹羔樅推胀ㄗ兞恳粯樱袝r(shí)也有變化程序的不可控性。常見(jiàn)例：子中斷服務(wù)子程序修改一個(gè)指向一個(gè) buffer 的指針時(shí)，必須用 volatile 來(lái)修飾這個(gè)指針。說(shuō)明：指針是一種普通的變量，從訪問(wèn)上沒(méi)有什么不同于其他變量的特性。其保存的數(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,

7、2,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)生堆內(nèi)碎塊。一個(gè) C、

9、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 主要實(shí)現(xiàn)其他

10、數(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ū)ο蟮娜筇卣魇欠庋b性、繼承性和多態(tài)性：q

11、封裝性：將客觀事物抽象成類，每個(gè)類對(duì)自身的數(shù)據(jù)和方法實(shí)行 protection（ private， protected，public）。q 繼承性：廣義的繼承有三種實(shí)現(xiàn)形式： 實(shí)現(xiàn)繼承（ 使用基類的屬性和方法而無(wú)需額外編碼的能力)、可視繼承(子窗體使用父窗體的外觀和實(shí)現(xiàn)代碼)、接口繼承(僅使用屬性和方法,實(shí)現(xiàn)滯后到子類實(shí)現(xiàn))。q 多態(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ù)雜，程序員應(yīng)該多看、多練。 面試題

12、 13： C+的空類有哪些成員函數(shù)q 缺省構(gòu)造函數(shù)。q 缺省拷貝構(gòu)造函數(shù)。q 缺省析構(gòu)函數(shù)。q 缺省賦值運(yùn)算符。q 缺省取址運(yùn)算符。q 缺省取址運(yùn)算符 const。注意：有些書上只是簡(jiǎn)單的介紹了前四個(gè)函數(shù)。沒(méi)有提及后面這兩個(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ì)象是否和新建對(duì)象相

13、同。而賦值運(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;/C c;return;

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

15、lt;< 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)性時(shí)一定要深刻理解虛函數(shù)表的工作原

16、理。 面試題 17： 簡(jiǎn)述類成員函數(shù)的重寫、重載和隱藏的區(qū)別（ 1）重寫和重載主要有以下幾點(diǎn)不同。q 范圍的區(qū)別：被重寫的和重寫的函數(shù)在兩個(gè)類中，而重載和被重載的函數(shù)在同一個(gè)類中。q 參數(shù)的區(qū)別：被重寫函數(shù)和重寫函數(shù)的參數(shù)列表一定相同，而被重載函數(shù)和重載函數(shù)的參數(shù)列表一定不同。q virtual 的區(qū)別：重寫的基類中被重寫的函數(shù)必須要有 virtual 修飾，而重載函數(shù)和被重載函數(shù)可以被7virtual 修飾，也可以沒(méi)有。（ 2）隱藏和重寫、重載有以下幾點(diǎn)不同。q 與重載的范圍不同：和重寫一樣，隱藏函數(shù)和被隱藏函數(shù)不在同一個(gè)類中。q 參數(shù)的區(qū)別：隱藏函數(shù)和被隱藏的函數(shù)的參數(shù)列表可以相同，也可不

17、同，但是函數(shù)名肯定要相同。當(dāng)參數(shù)不相同時(shí)，無(wú)論基類中的參數(shù)是否被 virtual 修飾，基類的函數(shù)都是被隱藏，而不是被重寫。說(shuō)明：雖然重載和覆蓋都是實(shí)現(xiàn)多態(tài)的基礎(chǔ)，但是兩者實(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è)指針 vptr（對(duì) vc 編譯器來(lái)說(shuō)，它插在類的第一個(gè)位置上） 指向虛函數(shù)表。 調(diào)用此類的構(gòu)造函數(shù)時(shí)，在類的構(gòu)造函數(shù)中，編譯器會(huì)隱含執(zhí)行 vptr 與

18、vtable 的關(guān)聯(lián)代碼，將 vptr 指向?qū)?yīng)的 vtable， 將類與此類的 vtable 聯(lián)系了起來(lái)。 另外在調(diào)用類的構(gòu)造函數(shù)時(shí)，指向基礎(chǔ)類的指針此時(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)的基礎(chǔ)。面試題 19： 鏈表和數(shù)組有什么區(qū)別數(shù)組和鏈表有以下幾點(diǎn)不同：（ 1）存儲(chǔ)形式： 數(shù)組是一塊連續(xù)的空間，聲明時(shí)就要確定長(zhǎng)度。 鏈表是一塊可不連續(xù)的

19、動(dòng)態(tài)空間，長(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）越界問(wèn)題： 鏈表不存在越界問(wèn)題，數(shù)組有越界問(wèn)題。說(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)過(guò)程，比較好理解和想到。遞歸算法的設(shè)計(jì)雖有一點(diǎn)難度，但是理解了循環(huán)算法，再設(shè)計(jì)遞歸算法就簡(jiǎn)單多了。面試題 21：簡(jiǎn)述隊(duì)列和棧的異同隊(duì)列和棧都是線性存儲(chǔ)結(jié)構(gòu)，但是兩者的插入和刪除數(shù)據(jù)的操作不同

22、，隊(duì)列是“先進(jìn)先出”，棧是“后進(jìn)先出”。注意：區(qū)別棧區(qū)和堆區(qū)。堆區(qū)的存取是“順序隨意”，而棧區(qū)是“后進(jìn)先出”。棧由編譯器自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。 堆一般由程序員分配釋放， 若程序員不釋放，程序結(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)建空棧：LinkStack CreateNUL

23、LStack( 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("There no node in stack

24、!");return NULL;LinkStack p = NULL;p = (LinkStack)malloc( sizeof( node ) ); /申請(qǐng)新結(jié)點(diǎn)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; /插入新結(jié)點(diǎn)return S;出棧函數(shù)：node Pop( Li

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

26、 = *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 出棧入 S1n = Pop( S );Push( S1, n.data );Push( S1, data ); /新結(jié)點(diǎn)入棧while( NULL != S1->next ) /S1 出棧入 Sn = Pop( S1

27、 );Push( S, n.data );return S;說(shuō)明：用兩個(gè)棧能夠?qū)崿F(xiàn)一個(gè)隊(duì)列的功能，那用兩個(gè)隊(duì)列能否實(shí)現(xiàn)一個(gè)隊(duì)列的功能呢？結(jié)果是否定的，因?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); /求當(dāng)前結(jié)點(diǎn)的左孩子樹的深度int d2= depth(T->rchild); /求當(dāng)前結(jié)點(diǎn)的右孩子樹的深度

28、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<<" "cout<<endl;for( i = 2; i <= 10; i+ ) /將 ARR

29、AY2,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 );ARRAYj+1=ARRAY0; /ARRAYi插入到正確的位置上for( i = 0; i < 10; i+)cout&l

30、t;<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>#define LEN 10 /數(shù)組長(zhǎng)度void main( void )int ARRAY10 = 0, 6, 3, 2, 7,

31、 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; /本趟排序開始前,交換標(biāo)志應(yīng)為假for( j = LEN-1; j >= i; j- ) /對(duì)當(dāng)前無(wú)序區(qū) ARRAYi.LEN自下向上掃描if( ARRA

32、Yj+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 ", ARRAYa );if( !isChange ) /本趟排序未發(fā)生交換,提前終止算法break;printf( "n" );return;13 面試題

33、26： 編碼實(shí)現(xiàn)直接選擇排序#include"stdio.h"#define LEN 9void main( void )int ARRAYLEN= 5, 6, 8, 2, 4, 1, 9, 3, 7 ; /待序數(shù)組printf("Before sorted:n");for( int m = 0; m < LEN; m+ ) /打印排序前數(shù)組printf( "%d ", ARRAYm );for (int i = 1; i <= LEN - 1; i+) /選擇排序int t = i - 1;int temp = 0;fo

34、r (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+ ) /打印排序后數(shù)組printf( "%d ", ARRAYi );printf( "n" );注意：在直接選擇排序中，具有相同關(guān)鍵碼的

35、對(duì)象可能會(huì)顛倒次序，因而直接選擇排序算法是一種不穩(wěn)定的排序方法。在本例中只是例舉了簡(jiǎn)單的整形數(shù)組排序，肯定不會(huì)有什么問(wèn)題。但是在復(fù)雜的數(shù)據(jù)元素序列組合中，只是根據(jù)單一的某一個(gè)關(guān)鍵值排序，直接選擇排序則不保證其穩(wěn)定性，這是直接選擇排序的一個(gè)弱點(diǎn)。 面試題 27： 編程實(shí)現(xiàn)堆排序堆排序編程實(shí)現(xiàn)：#include <stdio.h>14void createHeep(int ARRAY,int sPoint, int Len) /生成大根堆while( ( 2 * sPoint + 1 ) < Len )int mPoint = 2 * sPoint + 1 ;if( ( 2 *

36、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 sPoint = ARRAY mPoint ;ARRAY mPoint = tmpData;sPoint = mPoint ;elsebreak; /堆未破壞，不再需要調(diào)整return;void hee

37、pSort( 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è)記錄交換ARRAY0 = ARRAYi;ARRAYi = tmpData;createHeep( ARRAY, 0, i ); /將 H.r0.i重新調(diào)整為大根堆return;int main( void )15int

38、 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 ); /堆排序printf("After sorted:n"); /打印排序后數(shù)組內(nèi)容for( i = 0; i < 9; i+ )printf( "%d ", ARRAYi );p

39、rintf( "n" );return 0;說(shuō)明：堆排序，雖然實(shí)現(xiàn)復(fù)雜，但是非常的實(shí)用。另外讀者可是自己設(shè)計(jì)實(shí)現(xiàn)小堆排序的算法。雖然和大堆排序的實(shí)現(xiàn)過(guò)程相似，但是卻可以加深對(duì)堆排序的記憶和理解。 面試題 28： 編程實(shí)現(xiàn)基數(shù)排序#include <stdio.h>#include <malloc.h>#define LEN 8typedef struct node /隊(duì)列結(jié)點(diǎn)int data;struct node * next;node,*QueueNode;typedef struct Queue /隊(duì)列QueueNode front;Queue

40、Node rear;Queue,*QueueLink;QueueLink CreateNullQueue( QueueLink &Q) /創(chuàng)建空隊(duì)列Q = NULL;Q = ( QueueLink )malloc( sizeof( Queue ) );if( NULL = Q )printf("Fail to malloc null queue!n");return NULL;16Q->front = ( QueueNode )malloc( sizeof( node ) );Q->rear = ( QueueNode )malloc( sizeof(

41、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;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

42、; i+)d = datai.data;while( d > 0)d /= 10;temp +;if( temp > m )m = temp;temp = 0;return m;QueueLink Push( QueueLink &Q , node node ) /將數(shù)據(jù)壓入隊(duì)列QueueNode p1,p;p =( QueueNode )malloc( sizeof( node ) );if( NULL = p )printf("Fail to malloc a new node!n");return NULL;p1 = Q->front;whi

43、le(p1->next != NULL)p1 = p1->next; p->data = node.data;p1->next = p;p->next = Q->rear;17return NULL;node Pop( QueueLink &Q) /數(shù)據(jù)出隊(duì)列node temp;temp.data = 0;temp.next = NULL;QueueNode p;p = Q->front->next;if( p != Q->rear )temp = *p;Q->front->next = p->next;free(

44、 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 = 10;int power = 1;int k = 0;node ArrayLEN =450, NULL, 32,NULL, 781,NULL, 57 ,NULL,組 145,NULL, 613,NULL, 401,NULL, 594,NULL;/隊(duì)列結(jié)點(diǎn)數(shù)Queu

45、eLink Queue10;for( i = 0; i < 10; i+)CreateNullQueue( Queuei); /初始化隊(duì)列數(shù)組for( i = 0; i < LEN; i+)printf("%d ",Arrayi.data);printf("n");Max = lenData( Array, LEN ); /計(jì)算數(shù)組中關(guān)鍵字的最大位數(shù)printf("%dn",Max);18for(int j = 0; j < Max; j+) /按位排序if(j = 0) power = 1;else power =

46、 power *d;for(i = 0; i < LEN; i+)k = Arrayi.data /power - (Arrayi.data/(power * d) * d;Push( Queuek, Arrayi );for(int l = 0, k = 0; l < d; l+) /排序后出隊(duì)列重入數(shù)組while( IsEmpty( Queuel ) )Arrayk+ = Pop( Queuel );for( int t = 0; t < LEN; t+)printf("%d ",Arrayt.data);printf("n");r

47、eturn 0;說(shuō)明：隊(duì)列為基數(shù)排序的實(shí)現(xiàn)提供了很大的方便，適當(dāng)?shù)臄?shù)據(jù)機(jī)構(gòu)可以減少算法的復(fù)雜度，讓更多的算法實(shí)現(xiàn)更容易。 面試題 29：談?wù)勀銓?duì)編程規(guī)范的理解或認(rèn)識(shí)編程規(guī)范可總結(jié)為：程序的可行性，可讀性、可移植性以及可測(cè)試性。說(shuō)明： 這是編程規(guī)范的總綱目，面試者不一定要去背誦上面給出的那幾個(gè)例子，應(yīng)該去理解這幾個(gè)例子說(shuō)明的問(wèn)題，想一想，自己如何解決可行性、可讀性、可移植性以及可測(cè)試性這幾個(gè)問(wèn)題，結(jié)合以上幾個(gè)例子和自己平時(shí)的編程習(xí)慣來(lái)回答這個(gè)問(wèn)題。 面試題 30： short i = 0; i = i + 1L；這兩句有錯(cuò)嗎代碼一是錯(cuò)的，代碼二是正確的。說(shuō)明：在數(shù)據(jù)安全的情況下大類型的數(shù)據(jù)向小類

48、型的數(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ù)求值。注意：在編程的時(shí)候有些時(shí)候?qū)?amp;&或|替換成&或|沒(méi)有出錯(cuò)，但是其邏輯是錯(cuò)誤的，可能會(huì)導(dǎo)致不可預(yù)想的后果（比如當(dāng)兩個(gè)操作數(shù)一個(gè)是 1 另一個(gè)是 2 時(shí)）。面試題 32： C+的引用和 C 語(yǔ)言的指針有什么區(qū)別指針和引用主要有以下區(qū)別：（ 1） 引用必須被初始化，但是不分配存儲(chǔ)空間

49、。 指針不聲明時(shí)初始化，在初始化的時(shí)候需要分配存儲(chǔ)空間。（ 2） 引用初始化以后不能被改變，指針可以改變所指的對(duì)象。（ 3） 不存在指向空值的引用，但是存在指向空值的指針。注意：引用作為函數(shù)參數(shù)時(shí)，會(huì)引發(fā)一定的問(wèn)題，因?yàn)樽屢米鲄?shù)，目的就是想改變這個(gè)引用所指向地址的內(nèi)容，而函數(shù)調(diào)用時(shí)傳入的是實(shí)參，看不出函數(shù)的參數(shù)是正常變量，還是引用，因此可能會(huì)引發(fā)錯(cuò)誤。所以使用時(shí)一定要小心謹(jǐn)慎。面試題 33： 在二元樹中找出和為某一值的所有路徑輸入一個(gè)整數(shù)和一棵二元樹。從樹的根結(jié)點(diǎn)開始往下訪問(wèn)，一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如，輸入整數(shù) 9 和如下二元樹：3/

50、 2 6/ 5 4則打印出兩條路徑： 3， 6 和 3， 2， 4?！敬鸢浮縯ypedef struct pathBiTNode* tree; /結(jié)點(diǎn)數(shù)據(jù)成員struct path* next; /結(jié)點(diǎn)指針成員PATH,*pPath;初始化樹的結(jié)點(diǎn)棧：void init_path( 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(

51、 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; /新結(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ù)：voi

52、d 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->next;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 )&a

53、mp;&( T->rchild=NULL );查找符合條件的路徑：int find_path(pBTree T, int sum, pPath L)21push_path( L, T);record += T->data;if( ( record = 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(

54、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é)活用，例如本題，把所有的結(jié)點(diǎn)都?jí)喝霔?，而不符合條件的結(jié)點(diǎn)彈出棧，很容易實(shí)現(xiàn)了有效路徑的查找。雖然用鏈表也可以實(shí)現(xiàn)，但是用棧更利于理解這個(gè)問(wèn)題，即適當(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)<

55、;=(b)?(a):(b)注意：在調(diào)用時(shí)一定要注意這個(gè)宏定義的副作用，如下調(diào)用：(+*p)<=(x)?(+*p):(x)。p 指針就自加了兩次，違背了 MIN 的本意。 面試題 35： typedef 和 define 有什么區(qū)別（ 1）用法不同： typedef 用來(lái)定義一種數(shù)據(jù)類型的別名，增強(qiáng)程序的可讀性。 define 主要用來(lái)定義常量，以及書寫復(fù)雜使用頻繁的宏。（ 2） 執(zhí)行時(shí)間不同： typedef 是編譯過(guò)程的一部分，有類型檢查的功能。 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)：便于類型檢查、 同宏定義一樣可以方便地進(jìn)行參數(shù)的修改和調(diào)整、 節(jié)省空間，避免不必要的內(nèi)存分配