2020年度C和C經(jīng)典面試題面試必備

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

資料僅供參考

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

面試題1:變量的聲明和定義有什么區(qū)別

為變量分配地址和存儲(chǔ)空間的稱為定義，不分配地址的稱為聲明。一

個(gè)變量能夠在多個(gè)地方聲明，

可是只在一個(gè)地方定義。加入extern修飾的是變量的聲明，說明

此變量將在文件以外或在文件后面部分

定義。

說明：很多時(shí)候一個(gè)變量，只是聲明不分配內(nèi)存空間，直到具體使用

時(shí)才初始化，分配內(nèi)存空間，

如外部變量。面試題2:寫出bool、int>float、指針變量與

“零值”比較的if語句

bool型數(shù)據(jù)：

if(flag)

(

A;

}

else

(

B;

}

int型數(shù)據(jù)：

資料僅供參考

if(0!=flag)

A;

)

else

(

B;

)

指針型數(shù)：

if(NULL==flag)

(

A;

)

else

(

B;

)

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ū)別：

□?*3€幾口點(diǎn)是一個(gè)操作符，??口?n?是庫(kù)函數(shù)。

□?興邦見口點(diǎn)的參數(shù)能夠是數(shù)據(jù)的類型，也能夠是變量，而

??口?叱?只能以結(jié)尾為的字符串作參數(shù)。

□編譯器在編譯時(shí)就計(jì)算出了sizeof的結(jié)果。而strlen函數(shù)必

須在運(yùn)行時(shí)才能計(jì)算出來。而且sizeof

計(jì)算的是數(shù)據(jù)類型占內(nèi)存的大小，而strlen計(jì)算的是字符串實(shí)際的

長(zhǎng)度。

□數(shù)組做sizeof的參數(shù)不退化，傳遞給strlen就退化為指針了。

注意：有些是操作符看起來像是函數(shù)，而有些函數(shù)名看起來又像操作

符，這類容易混淆的名稱一定

要加以區(qū)分，否則遇到數(shù)組名這類特殊數(shù)據(jù)類型作參數(shù)時(shí)就很容易出

錯(cuò)。最容易混淆為函數(shù)的操作符就

是sizeofo

面試題4；C語言的關(guān)鍵字static和C++的關(guān)鍵字static有什

么區(qū)別

在C中static用來修飾局部靜態(tài)變量和外部靜態(tài)變量、函數(shù)。而

資料僅供參考

C++中除了上述功能外，還用來定

義類的成員變量和函數(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ū)別

ma11oc和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)用相應(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

#definemin(a,b)((a)<=(b)?(a):(b))

注意：在調(diào)用時(shí)一定要注意這個(gè)宏定義的副作用，如下調(diào)用：

((++*p)<=(x)?(++*p):(x)o

P指針就自加了兩次，違背了MIN的本意。

資料僅供參考

3面試題7:一個(gè)指針能夠是volatile嗎

能夠，因?yàn)橹羔樅推胀ㄗ兞恳粯?，有時(shí)也有變化程序的不可控性。常

見例：子中斷服務(wù)子程序修改

一個(gè)指向一個(gè)buffer的指針時(shí),必須用volatile來修飾這個(gè)指針。

說明：指針是一種普通的變量，從訪問上沒有什么不同于其它變量的

特性。其保存的數(shù)值是個(gè)整型

數(shù)據(jù)，和整型變量不同的是，這個(gè)整型數(shù)據(jù)指向的是一段內(nèi)存地址。

面試題8：a和&a有什么區(qū)別

請(qǐng)寫出以下代碼的打印結(jié)果，主要目的是考察a和&a的區(qū)別。

#include<stdio.h>

voidmain(void)

(

inta[5]={l,2,3,4,5};

int*ptr=(int*)(&a+l);

printf("%d,%d”,*(a+1),*(ptr-l));

return;

)

輸出結(jié)果：2,5o

注意：數(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)行期間都

存在。速度快、不容易出錯(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、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)其它數(shù)據(jù)類型格式到字

符串的轉(zhuǎn)化，memcpy主要是內(nèi)存塊間的拷貝。

說明：strcpy、sprintf與memcpy都能夠?qū)崿F(xiàn)拷貝的功能，可是

針正確對(duì)象不同，根據(jù)實(shí)際需求，來

選擇合適的函數(shù)實(shí)現(xiàn)拷貝功能。面試題11:設(shè)置地址為0x67a9的

整型變量的值為0xaa66

int*ptr;

ptr=(int*)0x67a9;

*ptr=0xaa66;

說明：這道題就是強(qiáng)制類型轉(zhuǎn)換的典型例子，無論在什么平臺(tái)地址長(zhǎng)

度和整型數(shù)據(jù)的長(zhǎng)度是一樣的，

即一個(gè)整型數(shù)據(jù)能夠強(qiáng)制轉(zhuǎn)換成地址指針類型，只要有意義即可。面

試題12:面向?qū)ο蟮娜筇卣?/p>

面向?qū)ο蟮娜筇卣魇欠庋b性、繼承性和多態(tài)性：

□封裝性：將客觀事物抽象成類，每個(gè)類對(duì)自身的數(shù)據(jù)和方法實(shí)行

資料僅供參考

protection（private,protected,

public）o

□繼承性：廣義的繼承有三種實(shí)現(xiàn)形式：實(shí)現(xiàn)繼承（使用基類的

屬性和方法而無需額外編碼的能力）、可

視繼承（子窗體使用父窗體的外觀和實(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)作。

說明：面向?qū)ο蟮娜齻€(gè)特征是實(shí)現(xiàn)面向?qū)ο蠹夹g(shù)的關(guān)鍵，每一個(gè)特征

的相關(guān)技術(shù)都非常的復(fù)雜，程

序員應(yīng)該多看、多練。面試題13:C++的空類有哪些成員函數(shù)

□缺省構(gòu)造函數(shù)。

□缺省拷貝構(gòu)造函數(shù)。

□缺省析構(gòu)函數(shù)。

□缺省賦值運(yùn)算符。

□缺省取址運(yùn)算符。

□缺省取址運(yùn)算符consto

注意：有些書上只是簡(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ì)象

是否和新建對(duì)象相同。而賦值運(yùn)算符則需要這個(gè)操作，另外賦值運(yùn)算

中如果原來的對(duì)象中有內(nèi)存分配要

先把內(nèi)存釋放掉

注意：當(dāng)有類中有指針類型的成員變量時(shí)，一定要重寫拷貝構(gòu)造函數(shù)

和賦值運(yùn)算符，不要使用默認(rèn)

的。面試題15:用C++設(shè)計(jì)一個(gè)不能被繼承的類

tempIate<typenameT>classA

(

friendT;

private:

AO0

~A(){}

}；

classB:virtualpubIicA<B>

pubIic:

資料僅供參考

BO{]

~B(){}

}；

classC:virtualpubIicB

(

pubIic:

CO{}

~C(){)

h

voidmain(void)

(

Bb;

//Cc;

return;

}

注意：構(gòu)造函數(shù)是繼承實(shí)現(xiàn)的關(guān)鍵，每次子類對(duì)象構(gòu)造時(shí)，首先調(diào)用

的是父類的構(gòu)造函數(shù)，然后才

是自己的。面試題16：訪問基類的私有虛函數(shù)

寫出以下程序的輸出結(jié)果：

^include<iostream.h>

classA

{6

資料僅供參考

virtualvoidg()

cout?"A::g"?endl;

)

private:

virtualvoidf()

(

cout??endl;

}

)；

classB:publicA

(

voidg()

(

cout?"B::g"?endl;

)

virtualvoidh()

(

cout?"B::h"?endl;

)

)；

typedefvoid(*Fun)(void);

資料僅供參考

voidmain()

Bb;

FunpFun;

for(inti=0;i<3;i++)

(

pFun=(Fun)*((int*)*(int*)(&b)+i);

pFun();

}

)

輸出結(jié)果：

B::g

A::f

B::h

注意：本題主要考察了面試者對(duì)虛函數(shù)的理解程度。一個(gè)對(duì)虛函數(shù)不

了解的人很難正確的做出本題。

在學(xué)習(xí)面向?qū)ο蟮亩鄳B(tài)性時(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ù)不相同時(shí)，無論基類中的參數(shù)是否被virtual修飾，基類的

函數(shù)都是被隱藏，而不是被重寫。

說明：雖然重載和覆蓋都是實(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ù)表

vtableo虛函數(shù)表的各表項(xiàng)為指向?qū)?/p>

應(yīng)虛函數(shù)的指針。編譯器還會(huì)在此類中隱含插入一個(gè)指針vptr（對(duì)

vc編譯器來說，它插在類的第一個(gè)位

置上）指向虛函數(shù)表。調(diào)用此類的構(gòu)造函數(shù)時(shí),在類的構(gòu)造函數(shù)中，

編譯器會(huì)隱含執(zhí)行vptr與vtable的

資料僅供參考

關(guān)聯(lián)代碼，將vptr指向?qū)?yīng)的vtable,將類與此類的vtable聯(lián)

系了起來。另外在調(diào)用類的構(gòu)造函數(shù)時(shí)，

指向基礎(chǔ)類的指針此時(shí)已經(jīng)變成指向具體的類的this指針,這樣依

靠此this指針即可得到正確的vtable,o

如此才能真正與函數(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ù)的動(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)越界問題：鏈表不存在越界問題，數(shù)組有越界問題。

說明：在選擇數(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)算法。

Listreverse(Listn)

(

if(jn)〃判斷鏈表是否為空，為空即退出。

(

returnn;

}

Iistcur=n.next;〃保存頭結(jié)點(diǎn)的下個(gè)結(jié)點(diǎn)

Iistpre=n;〃保存頭結(jié)點(diǎn)

Iisttmp;

8

pre.next=nulI;〃頭結(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=pre

pre=tmp;

cur=cur.next;

}

資料僅供參考

returntmp;//f返回頭指針

}

(2)反轉(zhuǎn)一個(gè)鏈表。遞歸算法。

List*reverse(List*oldList,List*newHead=NULL)

(

List*next=oldList->next;〃記錄上次翻轉(zhuǎn)后的鏈表

oIdList->next=newHead;〃將當(dāng)前結(jié)點(diǎn)插入到翻轉(zhuǎn)后鏈表的開

頭

newHead=oIdList;〃遞歸處理剩余的鏈表

return(next==NULL)?newHead:reverse(t,newHead);

}

說明：循環(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)，可是兩者的插入和刪除數(shù)據(jù)的操作不同,

隊(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)體：

typedefstructnode

(

intdata;

node*next;

}node,*LinkStack;

創(chuàng)立空棧：

LinkStackCreateNULLStack(LinkStack&S)

(

S=(LinkStack)malloc(sizeof(node));〃申請(qǐng)新結(jié)點(diǎn)

if(NULL=S)

(

printf("FaiItoma11ocanewnode.\n");

9

returnNULL;

}S

->data=0;〃初始化新結(jié)點(diǎn)

資料僅供參考

S->next=NULL;

returnS;

}

棧的插入函數(shù)：

LinkStackPush(LinkStack&S,intdata)

(

if(NULL==S)〃檢驗(yàn)棧

(

printf("Therenonodeinstack!");

returnNULL;

}

LinkStackp=NULL;

p=(LinkStack)ma11oc(sizeof(node));〃申請(qǐng)新結(jié)點(diǎn)

if(NULL=p)

(

printf("FaiItoma11ocanewnode.\n");

returnS;

}

if(NULL=S->next)

(

p->next=NULL;

}

資料僅供參考

else

p->next=S->next;

}P

->data=data;〃初始化新結(jié)點(diǎn)

S->next=p；〃插入新結(jié)點(diǎn)

returnS;

}

出棧函數(shù)：

nodePop(LinkStack&S)

(

nodetemp;

temp,data=0;

temp,next=NULL;

if(NULL==S)〃檢驗(yàn)棧

(

printf("Therenonodeinstack!");

returntemp;

)

temp=*S;

10

if(S->next=NULL)

資料僅供參考

printf("ThestackisNULL,can'tpop!\n");

returntemp;

}

LinkStackp=S->next;〃節(jié)點(diǎn)出棧

S->next=S->next->next;

temp=*p;

free(p);

p=NULL;

returntemp;

}

雙棧實(shí)現(xiàn)隊(duì)列的入隊(duì)函數(shù)：

LinkStackStackToQueuPush(LinkStack&S,intdata)

(

noden;

LinkStackSI=NULL;

CreateNULLStack(SI);〃創(chuàng)立空棧

while(NULL!=S->next)//S出棧入S1

n=Pop(S);

Push(S1,n.data);

}

資料僅供參考

Push(S1,data);〃新結(jié)點(diǎn)入棧

while(NULL!=S1->next)//S1出棧入S

(

n=Pop(S1);

Push(S,n.data);

}

returnS;

}

說明：用兩個(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)先出，無論多少個(gè)連在一

起都是先進(jìn)先出，而無法實(shí)現(xiàn)先進(jìn)后出。

面試題23：計(jì)算一顆二叉樹的深度

深度的計(jì)算函數(shù)：

intdepth(BiTreeT)

(

if(!T)return0;〃判斷當(dāng)前結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)

11

intd1=depth(T->IchiId);〃求當(dāng)前結(jié)點(diǎn)的左孩子樹的深度

intd2=depth(T->rchiId);〃求當(dāng)前結(jié)點(diǎn)的右孩子樹的深度

return(d1>d2?d1:d2)+1;

資料僅供參考

}

注意：根據(jù)二叉樹的結(jié)構(gòu)特點(diǎn)，很多算法都能夠用遞歸算法來實(shí)現(xiàn)。

面試題24:編碼實(shí)現(xiàn)直接插入排序

直接插入排序編程實(shí)現(xiàn)如下：

#include<iostream.h>

voidmain(void)

(

intARRAYE10]={0,6,3,2,7,5,4,9,1,8);

inti,j;

for(i=0;i<10;i++)

(

cout?ARRAY[i]?z，

)

cout?endl;

for(i=2;i<=10;i++)〃將ARRAY[2],…，ARRAY[n]依次按

序插入

(

if(ARRAY[i]<ARRAY[i-1])〃如果ARRAY】i]大于一切有序的數(shù)值,

〃ARRAY[i]將保持原位不動(dòng)

(

ARRAY[0]=ARRAY[i];〃將ARRAY[0]看做是哨兵，是ARRAY[i]的

副本

資料僅供參考

j=i-1;

do{〃從右向左在有序區(qū)ARRAY[1..i-1]中

〃查找ARRAYS]的插入位置

ARRAY[j+1]=ARRAY[j];〃將數(shù)值大于ARRAY[i]記錄后移

j—；

}while(ARRAY[0]<ARRAY[j]);

ARRAY[j+1]=ARRAY[0];〃ARRAY[i]插入到正確的位置上

}

}

for(i=0;i<10;i++)

(

cout?ARRAY[i]?"

}

cout?endI;

}

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)如下:

ttinclude<stdio.h>

#defineLEN10〃數(shù)組長(zhǎng)度

voidmain(void)

(

intARRAY[10]={0,6,3,2,7,5,4,9,1,8);〃待排序

數(shù)組

printf("\n");

for(inta=0;a<LEN;a++)〃打印數(shù)組內(nèi)容

(

printf("%d",ARRAY[a]);

}

inti=0;

intj=0;

booIisChange;〃設(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)前無序區(qū)ARRAY[i..LEN]

自下向上掃描

if(ARRAY[j+1]<ARRAY[j])

資料僅供參考

{〃交換記錄

ARRAY[0]=ARRAY[j+1];〃ARRAY[0]不是哨兵,僅做暫存單元

ARRAY[j+1]=ARRAY[j];

ARRAY[j]=ARRAY[0];

isChange=1;〃發(fā)生了交換,故將交換標(biāo)志置為真

}

}

printf("\n");

for(a=0;a<LEN;a++)〃打印本次排序后數(shù)組內(nèi)容

(

printf("%d",ARRAY[a]);

}

if(SisChange)〃本趟排序未發(fā)生交換,提前終止算法

(

break;

)

}

printf("\n");

return;

}

13面試題26：編碼實(shí)現(xiàn)直接選擇排序

#include"stdio.h"

資料僅供參考

#defineLEN9

voidmain(void)

(

intARRAY[LEN]={5,6,8,2,4,1,9,3,7);〃待序數(shù)組

printf("Beforesorted:\n");

for(intm=0;m<LEN;m++)〃打印排序前數(shù)組

(

printf("%d",ARRAY[m]);

}

for(inti=1;i<=LEN-1;i++)〃選擇排序

(

intt=i-1;

inttemp=0;

for(intj=i;j<LEN;j++)

(

if(ARRAY[j]<ARRAY[t])

(

t=j;

)

}

if(t!=(i-1))

資料僅供參考

temp=ARRAY[i-1];

ARRAY[i-1]=ARRAY[t];

ARRAY[t]-temp;

}

}

printf("\n");

printf("Aftersorted:\n");

for(i=0;I<LEN;i++)〃打印排序后數(shù)組

(

printf("%d",ARRAY[i]);

}

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>

資料僅供參考

14

voidcreateHeep(intARRAY[],intsPoint,intLen)〃生成大根

堆

(

whiIe((2*sPoint+1)<Len)

(

intmPoint=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)整

(

inttmpData=ARRAY[sPoint];〃交換sPoint與mPoint的數(shù)

據(jù)

ARRAY[sPoint]=ARRAY[mPoint];

ARRAY[mPoint]=tmpData;

sPoint=mPoint;

資料僅供參考

}

else

(

break;〃堆未破壞，不再需要調(diào)整

}

}

return;

}

voidheepSort(intARRAY[],intLen)〃堆排序

(

inti=0;

for(i=(Len/2-1);i>=0;i--)//將Hr[0,Lenght-1]

建成大根堆

(

createHeep(ARRAY,i,Len);

)

for(i=Len-1;i>0;i—)

(

inttmpData=ARRAY[0];〃與最后一個(gè)記錄交換

ARRAY[0]=ARRAY[i];

ARRAY[i]=tmpData;

createHeep(ARRAY,0,i);〃將H.r[0..i]重新調(diào)整為大根堆

資料僅供參考

}

return;

)

intmain(void)

15

(

intARRAY[]={5,4,7,3,9,1,6,8,2];

printf("Beforesorted:\n");〃打印排序前數(shù)組內(nèi)容

for(inti=0;i<9;i++)

(

printf("%d",ARRAY[i]);

}

printf("\n");

heepSort(ARRAY,9);〃堆排序

printf("Aftersorted:\n");〃打印排序后數(shù)組內(nèi)容

for(i=0;i<9;i++)

{

printf("%d",ARRAY[i]);

}

printf(n\n");

return0;

}

資料僅供參考

說明：堆排序，雖然實(shí)現(xiàn)復(fù)雜，可是非常的實(shí)用。另外讀者可是自己

設(shè)計(jì)實(shí)現(xiàn)小堆排序的算法。雖

然和大堆排序的實(shí)現(xiàn)過程相似，可是卻能夠加深對(duì)堆排序的記憶和理

解。面試題28:編程實(shí)現(xiàn)基數(shù)排序

#include<stdio.h>

#include<ma11oc.h>

#defineLEN8

typedefstructnode〃隊(duì)列結(jié)點(diǎn)

(

intdata;

structnode*next;

}node,*QueueNode;

typedefstructQueue〃隊(duì)列

(

QueueNodefront;

QueueNoderear;

}Queue,*QueueLink;

QueueLinkCreateNu11Queue(QueueLink&Q)〃創(chuàng)立空隊(duì)列

(

Q=NULL;

Q=(QueueLink)ma11oc(sizeof(Queue));

if(NULL=Q)

資料僅供參考

printf("FaiItoma11ocnulIqueue!\n");

returnNULL;

}

16

Q->front=(QueueNode)maIIoc(sizeof(node));

Q->rear=(QueueNode)ma11oc(sizeof(node));

if(NULL=Q->front||NULL=Q->rear)

(

printf("FaiItoma11ocanewqueue'sforntorrear!\n");

returnNULL;

}Q

->rear=NULL;

Q->front->next=Q->rear;

returnQ;

)

intlenData(nodedata[],intIen)〃計(jì)算隊(duì)列中各結(jié)點(diǎn)的數(shù)據(jù)

的最大位數(shù)

(

intm=0;

inttemp=0;

intd;

資料僅供參考

for(inti=0;i<len;i++)

(

d=data[i].data;

whiIe(d>0)

(

d/=10;

temp++;

}

if(temp>m)

(

m=temp;

}

temp=0;

}

returnm;

)

QueueLinkPush(QueueLink&Q,nodenode)〃將數(shù)據(jù)壓入隊(duì)列

(

QueueNodep1,p;

p=(QueueNode)ma11oc(sizeof(node));

if(NULL=p)

資料僅供參考

printf("FaiItoma11ocanewnode!\n");

returnNULL;

}

p1=Q->front;

whiIe(p1->next!=NULL)

(

p1=p1->next;

}P

->data=node,data;

p1->next=p;

p->next=Q->rear;

17

returnNULL;

}

nodePop(QueueLink&Q)〃數(shù)據(jù)出隊(duì)列

(

nodetemp;

temp,data=0;

temp.next=NULL;

QueueNodep;

p=Q->front->next;

if(p!=Q->rear)

資料僅供參考

temp=*p;

Q->front->next=p->next;

free(p);

p=NULL;

}

returntemp;

}

intIsEmpty(QueueLinkQ)

(

if(Q->front->next=Q->rear)

(

return0;

}

return1;

)

intmain(void)

(

inti=0;

intMax=0;〃記錄結(jié)點(diǎn)中數(shù)據(jù)的最大位數(shù)

intd=10;

intpower=1;

資料僅供參考

intk=0;

nodeArray[LEN]={{450,NULL),{32,NULL),{781,NULL},

{57,NULL),組

{145,NULL),{613,NULL},{401,NULL},{594,NULL}};

〃隊(duì)列結(jié)點(diǎn)數(shù)

QueueLinkQueue[10];

for(i=0;i<10;i++)

(

CreateNulIQueue(Queue[i]);〃初始化隊(duì)列數(shù)組

}

for(i=0;i<LEN;i++)

(

printf("%d",Array[i].data);

}

printf("\n");

Max=IenData(Array,LEN);〃計(jì)算數(shù)組中關(guān)鍵字的最大位數(shù)

printf("%d\n",Max);

18

for(intj=0;j<Max;j++)〃按位排序

(

if(j==0)power=1;

elsepower=power*d;

資料僅供參考

for(i=0;i<LEN;i++)

k=Array[i].data/power-(Array[i].data/(power*d))*d;

Push(Queue[k],Array[i]);

}

for(intI=0,k=0;I<d;I++)〃排序后出隊(duì)列重入數(shù)組

(

whiIe(IsEmpty(Queue[I]))

(

Array[k++]=Pop(Queue[I]);

}

}

for(intt=0;t<LEN;t++)

(

printf("%d",Array[t].data);

)

printf("\n");

}

return0;

}

說明：隊(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è)試性。

說明：這是編程規(guī)范的總綱目，面試者不一定要去背誦上面給出的

那幾個(gè)例子，應(yīng)該去理解這幾個(gè)

例子說明的問題，想一想，自己如何解決可行性、可讀性、可移植性

以及可測(cè)試性這幾個(gè)問題，結(jié)合以

上幾個(gè)例子和自己平時(shí)的編程習(xí)慣來回答這個(gè)問題。面試題30:

shorti=0;i=i+1L;這兩句有錯(cuò)嗎

代碼一是錯(cuò)的，代碼二是正確的。

說明：在數(shù)據(jù)安全的情況下大類型的數(shù)據(jù)向小類型的數(shù)據(jù)轉(zhuǎn)換一定要

顯示的強(qiáng)制類型轉(zhuǎn)換。面試題31:&&和&、||和|有什么區(qū)別

(1)&和I對(duì)操作數(shù)進(jìn)行求值運(yùn)算，&&和II只是判斷邏輯關(guān)系。

19

(2)&&和||在在判斷左側(cè)操作數(shù)就能確定結(jié)果的情況下就不再對(duì)

右側(cè)操作數(shù)求值。

注意：在編程的時(shí)候有些時(shí)候?qū)?&或||替換成&或|沒有出錯(cuò)，可是其

邏輯是錯(cuò)誤的，可能會(huì)導(dǎo)致不

可預(yù)想的后果(比如當(dāng)兩個(gè)操作數(shù)一個(gè)是1另一個(gè)是2時(shí))。

面試題32：C++的引用和C語言的指針有什么區(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í)傳入的是實(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和

如下二元樹：

3

/\

26

/\

54

則打印出兩條路徑：3,6和3,2,4o

【答案】

typedefstructpath

資料僅供參考

BiTNode*tree;〃結(jié)點(diǎn)數(shù)據(jù)成員

structpath*next;〃結(jié)點(diǎn)指針成員

}PATH,*pPath;

初始化樹的結(jié)點(diǎn)棧：

voidinit_path(pPath*L)

(

*L=(pPath)malloc(sizeof(PATH));〃創(chuàng)立空樹

(*L)->next=NULL;

}

樹結(jié)點(diǎn)入棧函數(shù)：

voidpush_path(pPathH,pBTreeT)

(

pPathp=H->next;

pPathq=H;

while(NULL!=p)

20

(

q=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ù)：

voidprint_path(pPathL)

(

pPathp=L->next;

while(NULL!=p)〃打印當(dāng)前棧中所有數(shù)據(jù)

(

printf("%d,",p->tree->data);

p=p->next;

}

}

樹結(jié)點(diǎn)出棧函數(shù)：

voidpop_path(pPathH)

(

pPathp=H->next;

pPathq=H;

if(NULL==p)〃檢驗(yàn)當(dāng)前棧是否為空

(

printf("StackisnulI!\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)：

intIsLeaf(pBTreeT)

(

return(T->lchild==NULL)&&(T->rchild=NULL);

)

查找符合條件的路徑：

intfind_path(pBTreeT,intsum,pPathL)

21

(

push_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(T->rchild!=NULL)〃遞歸查找當(dāng)前節(jié)點(diǎn)的右孩子

(

find_path(T->rchiId,sum,L);

}

record-=T->data;

pop_path(L);

return0;

}

注意：數(shù)據(jù)結(jié)構(gòu)一定要活學(xué)活用，例如本題，把所有的結(jié)點(diǎn)都?jí)喝霔＃?/p>

而不符合條件的結(jié)點(diǎn)彈出棧，

很容易實(shí)現(xiàn)了有效路徑的查找。雖然用鏈表也能夠?qū)崿F(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è)。

【答案】

#definemin(a,b)((a)<=(b)?(a):(b))

注意：在調(diào)用時(shí)一定要注意這個(gè)宏定義的副作用，如下調(diào)用：

((++*p)<=(x)?(++*p):(x)o

p指針就自加了兩次,違背了MIN的本意。面試題35：typedef和

define有什么區(qū)別

(1)用法不同：typedef用來定義一種數(shù)據(jù)類型的別名，增強(qiáng)程

序的可讀性。define主要用來定義

常量，以及書寫復(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àn)榫湮惨由戏痔?hào)。而define不

是語句，千萬不能在句尾加分號(hào)。

資料僅供參考

22面試題36:關(guān)鍵字const是什么

const用來定義一個(gè)只讀的變量或?qū)ο?。主要?yōu)點(diǎn)：便于類型檢查、

同宏定義一樣能夠方便地進(jìn)行

參數(shù)的修改和調(diào)整、節(jié)省空間，避免不必要的內(nèi)存分配、可為函數(shù)

重載提供參考。

說明：const修飾函數(shù)參數(shù)，是一種編程規(guī)范的要求，便于閱讀，

一看即知這個(gè)參數(shù)不能被改變，

實(shí)現(xiàn)時(shí)不易出錯(cuò)。面試題37:static有什么作用

static在C中主要用于定義全局靜態(tài)變量、定義局部靜態(tài)變量、

定義靜態(tài)函數(shù)。在C++中新增了兩

種作用：定義靜態(tài)數(shù)據(jù)成員、靜態(tài)函數(shù)成員。

注意：因?yàn)閟tatic定義的變量分配在靜態(tài)區(qū)，因此其定義的變量的

默認(rèn)值為0,普通變量的默認(rèn)值

為隨機(jī)數(shù)，在定義指針變量時(shí)要特別注意。面試題38:extern有

什么作用

extern標(biāo)識(shí)的變量或者函數(shù)聲明其定義在別的文件中，提示編譯器

遇到此變量和函數(shù)時(shí)在其它模塊

中尋找其定義。面試題39：流操作符重載為