一德迹、 C/C++程序基礎(chǔ)

面試?yán)}1——分析代碼寫輸出（一般賦值語(yǔ)句的概念和方法）逸尖。

面試?yán)}2——分析代碼寫運(yùn)行結(jié)果（C++域操作符）敢靡。

面試?yán)}3——分析代碼寫輸出（i++和++i的區(qū)別）救军。

面試?yán)}4——i++和++i哪個(gè)效率更高嫉髓。++i可以返回對(duì)象引用，i++必須返回對(duì)象的值谎仲。在內(nèi)建數(shù)據(jù)類型的情況下浙垫，效率沒(méi)有區(qū)別。在自定義數(shù)據(jù)類型的情況下郑诺，++i效率較高夹姥。

面試?yán)}5——選擇編程風(fēng)格良好的條件比較語(yǔ)句。

面試?yán)}6——分析代碼寫結(jié)果（有符號(hào)變量與無(wú)符號(hào)變量值的轉(zhuǎn)換辙诞，負(fù)數(shù)最高位為1）辙售。

面試?yán)}7——將數(shù)a、b的值進(jìn)行交換飞涂，并且不使用任何中間變量（局部變量旦部、加減運(yùn)算、異或運(yùn)算）较店。

面試?yán)}8——C和C++有什么不同（面向過(guò)程與面向?qū)ο螅?/p>

面試?yán)}9——C++是面向?qū)ο蠡亩鳦是面向過(guò)程化的士八？

面試?yán)}10——為什么標(biāo)準(zhǔn)頭文件都有類似一下所示的結(jié)構(gòu)？（預(yù)處理結(jié)構(gòu)梁呈，如ifndef婚度、define、extern “C”官卡、endif等）蝗茁。

面試?yán)}11——頭文件引用中< >（工程或標(biāo)準(zhǔn)頭文件）和“ ”（用戶提供）的區(qū)別醋虏。

面試?yán)}12——C++中main函數(shù)執(zhí)行完后還執(zhí)行其他語(yǔ)句（exit()、atexit()函數(shù)）哮翘。

二灰粮、 預(yù)處理、const忍坷、static與sizeof

面試?yán)}1——分析代碼寫結(jié)果（預(yù)處理的使用）：#ifdef粘舟、#else、#endif佩研。

面試?yán)}2——用#define實(shí)現(xiàn)宏柑肴，并求最大值和最小值。

                  類如#define MAX(x, y) (((x)>(y)) ? (x): (y))

面試?yán)}3——分析代碼寫結(jié)果（宏定義的使用）旬薯。

面試?yán)}4——分析代碼寫結(jié)果（宏參數(shù)的連接）晰骑。

面試?yán)}5——用宏定義得到一個(gè)字的高位和低位字節(jié)。

                  #define WORD_LO(xxx) ((byte)((word)(xxx)&255))

                  #define WORD_HI(xxx) ((byte)((word)(xxx)>>8))

面試?yán)}6——用宏定義得到一個(gè)數(shù)組所含的元素個(gè)數(shù)绊序。

                  #define ARR_SIZE(a) (sizeof((a))/sizeof((a[0])))

面試?yán)}7——找錯(cuò)（const的使用）硕舆。

面試?yán)}8——請(qǐng)說(shuō)明const與#define的各自特點(diǎn)和區(qū)別。

面試?yán)}9——C++中const的作用：定義常量骤公、修飾函數(shù)形式參數(shù)（如const &參數(shù)抚官，提高效率）、修飾函數(shù)的返回值（返回值不能被直接修改）阶捆、修飾類的成員函數(shù)（函數(shù)定義體）凌节。

面試?yán)}10——static的作用：在函數(shù)體靜態(tài)變量維持其值不變；在模塊內(nèi)靜態(tài)變量不能被模塊外其他函數(shù)訪問(wèn)洒试；在模塊內(nèi)靜態(tài)函數(shù)只能被這一模塊內(nèi)的其他函數(shù)調(diào)用倍奢。

面試?yán)}11——static全局變量與普通全局變量有什么區(qū)別（前者只初始化一次，防止在其他單元中被引用）垒棋。static局部變量和普通局部變量有什么區(qū)別（前者只初始化一次卒煞，下一次依據(jù)上一次結(jié)果值）。static函數(shù)與普通函數(shù)有什么區(qū)別（前者在內(nèi)存中只有一份叼架，后者在每個(gè)被調(diào)用中維持一份復(fù)制品）畔裕。

面試?yán)}12——分析代碼寫結(jié)果（C++類的靜態(tài)成員）：調(diào)用時(shí)用“::”域操作符。

面試?yán)}13——填空（使用sizeof計(jì)算普通變量所占空間）碉碉。

面試?yán)}14——分析代碼寫結(jié)果（使用sizeof計(jì)算類對(duì)象所占空間大胁褡辍）。填充字節(jié)（滿足最寬的基本類型成員的大小整除）垢粮。

面試?yán)}15——分析代碼寫結(jié)果（使用sizeof計(jì)算含有虛函數(shù)的類對(duì)象的空間大小）靠粪。隱含的虛表指針成員（8字節(jié)）蜡吧。

面試?yán)}16——分析代碼寫結(jié)果（使用sizeof計(jì)算虛擬繼承的類對(duì)象的空間大泻硫尽）。編譯器為虛擬繼承的子類安插一個(gè)指向父類的指針昔善，大小為4元潘。

面試?yán)}17——sizeof與strlen的區(qū)別（前者空間大小，后者計(jì)算字符串長(zhǎng)度）君仆。

面試?yán)}18——sizeof用途（與存儲(chǔ)分配和I/O系統(tǒng)的例程進(jìn)行通信翩概；查看某個(gè)類型的對(duì)象在內(nèi)存中所占的單元字節(jié)；動(dòng)態(tài)分配對(duì)象時(shí)返咱，可以使系統(tǒng)知道要分配多少內(nèi)存钥庇；便于一些類型的擴(kuò)充；建議在涉及操作數(shù)字節(jié)大小時(shí)用sizeof來(lái)代替常量計(jì)算咖摹；如果操作數(shù)是函數(shù)中的數(shù)組形參或函數(shù)類型的形參评姨，sizeof給出其指針的大小）萤晴。

面試?yán)}19——找錯(cuò)（使用strlen()函數(shù)代替sizeof計(jì)算sizeof計(jì)算字符串長(zhǎng)度）吐句。

面試?yán)}20——分析代碼寫結(jié)果（使用sizeof計(jì)算聯(lián)合體的大小）店读。

面試?yán)}21——選擇題（#pragma pack的作用：設(shè)置對(duì)齊方式）嗦枢。

面試?yán)}22——為什么要引入內(nèi)聯(lián)函數(shù)（用它代替C中表達(dá)式形式的宏定義，解決程序中函數(shù)調(diào)用的效率問(wèn)題）屯断。

面試?yán)}23——為什么inline能很好地取代表達(dá)式形式的預(yù)定義（沒(méi)有了調(diào)用的開銷净宵，效率很高；仍舊是一個(gè)真正的函數(shù)裹纳；可以作為某個(gè)類的成員函數(shù)）择葡。

面試?yán)}24——內(nèi)聯(lián)函數(shù)使用的場(chǎng)合（設(shè)有或者保護(hù)成員的讀寫）。

面試?yán)}25——為什么不把所有的函數(shù)都定義成內(nèi)聯(lián)函數(shù)（內(nèi)聯(lián)是以代碼膨脹（復(fù)制）為代價(jià)剃氧，僅僅省去了函數(shù)調(diào)用的開銷敏储，從而提高函數(shù)的執(zhí)行效率）。

面試?yán)}26——內(nèi)聯(lián)函數(shù)與宏有什么區(qū)別（前者在編譯時(shí)展開朋鞍，宏在預(yù)編譯時(shí)展開已添；在編譯的時(shí)候內(nèi)聯(lián)函數(shù)可以直接被嵌入到目標(biāo)代碼中，而宏只是一個(gè)簡(jiǎn)單的文本替換滥酥；前者可以完成諸如類檢測(cè)更舞、語(yǔ)句是否正確等編譯功能，宏就不具有這樣的功能坎吻；宏不是函數(shù)缆蝉，前者是函數(shù)；宏在定義時(shí)要小心處理宏參數(shù)，否則容易產(chǎn)生二義性刊头，而前者不會(huì)出現(xiàn)二義性黍瞧。

三、 引用和指針

面試?yán)}1——分析代碼寫結(jié)果（一般變量引用：&）原杂。

面試?yán)}2——分析代碼寫結(jié)果（指針變量引用：&）印颤。

面試?yán)}3——分析代碼找錯(cuò)誤（變量引用）。

面試?yán)}4——交換兩個(gè)字符串（參數(shù)引用）穿肄。

面試?yán)}5——程序差錯(cuò)（參數(shù)引用）年局。

面試?yán)}6——程序差錯(cuò)（參數(shù)引用：常量引用類型在函數(shù)體內(nèi)其值不能被修改；非常量引用不能作為常量的引用）咸产。

面試?yán)}7——指針與引用的區(qū)別（初始化要求不同矢否，引用要求創(chuàng)建同時(shí)必須初始化，指針可以在定義后的任何地方重新賦值锐朴；可修改性不同兴喂，引用一旦被初始化，它就不能被另一個(gè)對(duì)象引用焚志，而指針可以衣迷；不存在NULL引用；測(cè)試時(shí)酱酬，使用引用之前不需要測(cè)試它的合法性壶谒，而指針可以指向NULL，故必須經(jīng)常進(jìn)行測(cè)試膳沽；應(yīng)用上汗菜，如果指向一個(gè)對(duì)象就不會(huì)改變指向，那么應(yīng)該使用引用挑社。）陨界。

面試?yán)}8——為什么引用比指針安全（不存在NULL引用）。

面試?yán)}9——復(fù)雜指針的聲明（首先從最里面的圓括號(hào)看起痛阻，然后往右看菌瘪，再往左看）。

面試?yán)}10——分析代碼寫結(jié)果（用指針賦值）阱当。

面試?yán)}11——分析代碼寫結(jié)果（指針加減操作）俏扩。

面試?yán)}12——分析代碼寫結(jié)果（指針比較）。

面試?yán)}13——分析代碼找錯(cuò)誤（內(nèi)存訪問(wèn)違規(guī)）弊添。

面試?yán)}14——分析代碼找錯(cuò)誤（指針的隱式轉(zhuǎn)換）录淡。

面試?yán)}15——指針常量和常量指針的區(qū)別（前者是指針形式的常量，不可改變地址的指針油坝，但可以對(duì)它指向的內(nèi)容修改嫉戚；后者是常量形式的指針刨裆，即常量指針是指向常量的一個(gè)指針，所指向的地址的內(nèi)容不能改變彼水。）崔拥。

面試?yán)}16——同15极舔。

面試?yán)}17——同15凤覆。

面試?yán)}18——this指針的正確敘述（類的非靜態(tài)成員函數(shù)才有this指針）。

面試?yán)}19——同18拆魏。

面試?yán)}20——指針數(shù)組和數(shù)組指針（前者表示數(shù)組的元素是指針形式盯桦，后者表示指向數(shù)組的指針。）渤刃。

面試?yán)}21——同20拥峦。

面試?yán)}22——函數(shù)指針和指針函數(shù)（指針函數(shù)是指帶指針的函數(shù)，即本質(zhì)是一個(gè)函數(shù)卖子，并且返回的是某一類型的指針略号。函數(shù)指針是指向函數(shù)的指針變量。）洋闽。

面試?yán)}23——數(shù)組指針和函數(shù)指針的定義玄柠。

面試?yán)}24——各種指針的定義（函數(shù)指針、函數(shù)返回指針诫舅、const指針羽利、指向const的指針、指向const的const指針）刊懈。

面試?yán)}25——代碼改錯(cuò)（函數(shù)指針的使用）这弧。

面試?yán)}26——分析代碼寫結(jié)果（函數(shù)指針的使用）。

面試?yán)}27——typedef用于函數(shù)指針定義（使用typedef自定義數(shù)據(jù)類型）虚汛。

面試?yán)}28——“野指針”是什么（不是NULL指針匾浪，是指向“垃圾”內(nèi)存的指針。成因：指針變量沒(méi)有初始化卷哩；指針p被free或者delete之后蛋辈，沒(méi)有置為NULL。）殉疼。

面試?yán)}29——分析代碼差錯(cuò)（“野指針”的危害：程序崩潰）梯浪。

面試?yán)}30——malloc/free和new/delete（前者是庫(kù)函數(shù)而不是運(yùn)算符，不能滿足動(dòng)態(tài)對(duì)象的要求瓢娜，不能夠把執(zhí)行構(gòu)造函數(shù)和析構(gòu)函數(shù)的任務(wù)強(qiáng)加給它）挂洛。

面試?yán)}31——程序改錯(cuò)（“野指針”，即指針的初始化）眠砾。

面試?yán)}32——各種內(nèi)存分配和釋放的函數(shù)的聯(lián)系和區(qū)別：malloc虏劲、calloc、realloc、free等柒巫。調(diào)用格式如下：

          (類型*) malloc (size); 長(zhǎng)度為size的內(nèi)存励堡。

          (類型*) calloc(n, size); 長(zhǎng)度為size的n塊內(nèi)存。

          (類型*) realloc(*p, size); 將p的長(zhǎng)度增大到size堡掏。

          free(void *p); 釋放应结。

面試?yán)}33——程序找錯(cuò)（動(dòng)態(tài)內(nèi)存的傳遞）。

面試?yán)}34——程序分析（動(dòng)態(tài)內(nèi)存的傳遞：在C中采用指向指針的指針解決動(dòng)態(tài)內(nèi)存不能傳遞的問(wèn)題泉唁；在C++中采用傳遞指針的引用解決鹅龄；也可使用函數(shù)返回值來(lái)傳遞動(dòng)態(tài)內(nèi)存。）亭畜。

面試?yán)}35——比較分析兩個(gè)代碼段的輸出（動(dòng)態(tài)內(nèi)存的傳遞）扮休。

面試?yán)}36——程序差錯(cuò)（“野指針”用于變量值的互換）。

面試?yán)}37——內(nèi)存的分配方式（靜態(tài)存儲(chǔ)區(qū)（如全局變量）拴鸵、棧（效率很高玷坠，但是分配的村內(nèi)存容量有限）、堆（亦稱動(dòng)態(tài)內(nèi)存分配））劲藐。

面試?yán)}38——句柄（用來(lái)標(biāo)識(shí)項(xiàng)目的八堡，這些項(xiàng)目包括：模塊module；任務(wù)task瘩燥；實(shí)例instance秕重；文件file；內(nèi)存塊block of memory厉膀；菜單menu溶耘；控制control；字體font服鹅；資源resource（包括圖標(biāo)icon凳兵、光標(biāo)cursor、字符串string等）企软；GDI對(duì)象GDI object（包括位圖bitmap庐扫、畫刷brush、元文件metafile仗哨、調(diào)色板palette形庭、畫筆pen、區(qū)域region以及設(shè)備描述表device context）厌漂。程序執(zhí)行順序：句柄地址（穩(wěn)定）→記載對(duì)象在內(nèi)存中的地址→對(duì)象在內(nèi)存中的地址（不穩(wěn)定）→實(shí)際對(duì)象萨醒。）。

面試?yán)}39——指針和句柄的區(qū)別（句柄所指可以是一個(gè)復(fù)雜的結(jié)構(gòu)苇倡，并且可以與系統(tǒng)有關(guān)富纸；指針也可以指向一個(gè)復(fù)雜的結(jié)構(gòu)囤踩，但是通常是由用戶定義的，所以必要的工作要由用戶完成晓褪，特別刪除部分的工作堵漱。）。

四涣仿、 字符串

面試?yán)}1——使用庫(kù)函數(shù)將數(shù)字轉(zhuǎn)換為字符串：itoa()為整型勤庐；ltoa()為長(zhǎng)整型；ulota()為無(wú)符號(hào)長(zhǎng)整型变过；gcvt()為浮點(diǎn)數(shù)埃元，取四舍五入涝涤；ecvt()為雙精度浮點(diǎn)型媚狰，結(jié)果中不包含十進(jìn)制小數(shù)點(diǎn)；fcvt()指定位數(shù)為轉(zhuǎn)換精度阔拳，其余同ecvt()崭孤。

面試?yán)}2——不適用庫(kù)函數(shù)將數(shù)字轉(zhuǎn)換為字符串：ASCII碼。

面試?yán)}3——使用庫(kù)函數(shù)將字符串轉(zhuǎn)換為數(shù)字：atof雙精度浮點(diǎn)型糊肠、atoi整型辨宠、atol長(zhǎng)整型、strtod雙精度浮點(diǎn)數(shù)货裹、strtol長(zhǎng)整型嗤形、strtoul無(wú)符號(hào)長(zhǎng)整型。后面三者不同于前面的區(qū)別在于：它們報(bào)告不能轉(zhuǎn)換的所有剩余字符弧圆。

面試?yán)}4——不使用庫(kù)函數(shù)將字符串轉(zhuǎn)換為數(shù)字：ASCII碼赋兵。

面試?yán)}5——編程實(shí)現(xiàn)strcpy函數(shù)。

面試?yán)}6——編程實(shí)現(xiàn)memcpy函數(shù)搔预。

面試?yán)}7——strcpy和memcpy的區(qū)別：復(fù)制的內(nèi)容不同霹期，前者只能復(fù)制字符串，后者可以復(fù)制任意內(nèi)容拯田，例如字符數(shù)組历造、整型、結(jié)構(gòu)體船庇、類等吭产；復(fù)制的方法不同，前者不需要指定長(zhǎng)度鸭轮，遇到字符串結(jié)束符“\0”便結(jié)束臣淤，后者需要給定復(fù)制長(zhǎng)度的參數(shù)；用途不同张弛。

面試?yán)}8——該錯(cuò)（數(shù)組越界）荒典。

面試?yán)}9——分析程序（數(shù)組越界）酪劫。

面試?yán)}10——分析程序（打印操作可能產(chǎn)生數(shù)組越界）。

面試?yán)}11——編程實(shí)現(xiàn)字符串的長(zhǎng)度檢測(cè)（strlen函數(shù)）寺董。

面試?yán)}12——編程實(shí)現(xiàn)字符串中子串的查找（strstr函數(shù)）覆糟。

面試?yán)}13——編程實(shí)現(xiàn)字符串中各單詞的翻轉(zhuǎn)（查找空格和字符串的結(jié)束符號(hào)）。

面試?yán)}14——編程判斷字符串是否為回文（先判斷長(zhǎng)度遮咖，再比較）滩字。

面試?yán)}15——編程實(shí)現(xiàn)strcmp庫(kù)函數(shù)（判斷字符串相等）。

面試?yán)}16——編程查找兩個(gè)字符串的最大公共子串御吞。

面試?yán)}17——不能使用printf麦箍，將十進(jìn)制數(shù)以二進(jìn)制和十六進(jìn)制的形式輸出（用字符串表示十進(jìn)制數(shù)）。

面試?yán)}18——在字符串中陶珠，插入字符統(tǒng)計(jì)的個(gè)數(shù)挟裂。

面試?yán)}19——字符串編碼例題。

面試?yán)}20——反轉(zhuǎn)字符串揍诽，但其指定的子串不反轉(zhuǎn)（編寫函數(shù)對(duì)輸入字符串和子串進(jìn)行反轉(zhuǎn)诀蓉，然后在輸入字符串的反轉(zhuǎn)中查找子串的反轉(zhuǎn)）。

面試?yán)}21——編寫字符串反轉(zhuǎn)函數(shù)strrev（法一：遍歷字符串，將第一個(gè)字符和最后一個(gè)字符交換，再往中間循環(huán)贱呐；法二：通過(guò)數(shù)組下標(biāo)的方式訪問(wèn)字符串，也可以用指針直接操作沥曹；法三：異或運(yùn)算符；法四：+和-運(yùn)算符碟联。）妓美。

面試?yán)}22——編程實(shí)現(xiàn)任意長(zhǎng)度的兩個(gè)正整數(shù)相加。

面試?yán)}23——編程實(shí)現(xiàn)字符串循環(huán)右移玄帕。

   面試?yán)}24——從字符串的指定位置開始部脚，刪除其指定長(zhǎng)度字符。

   面試?yán)}25——字符串的排序及交換裤纹。

面試?yán)}26——編程實(shí)現(xiàn)刪除字符串中所有指定的字符委刘。

面試?yán)}27——分析代碼（使用strcat函數(shù)連接字符串）。

面試?yán)}28——編程實(shí)現(xiàn)庫(kù)函數(shù)strcat鹰椒。

面試?yán)}29——計(jì)算含有漢字的字符串的長(zhǎng)度锡移。

面試?yán)}30——找出01字符串中0和1連續(xù)出現(xiàn)的最大次數(shù)。

面試?yán)}31——實(shí)現(xiàn)字符串的替換漆际。

五淆珊、 位運(yùn)算與嵌入式編程

面試?yán)}1——分析代碼寫結(jié)果（位制轉(zhuǎn)換：使用printf輸出不同類型變量）。

面試?yán)}2——分析代碼寫出結(jié)果（位運(yùn)算：左移<<（相當(dāng)于乘法）和右移>>（相當(dāng)于除法））奸汇。

面試?yán)}3——設(shè)置或清除特定的位（使用“&”和“|”位操作符）施符。

面試?yán)}4——計(jì)算一字節(jié)里有多少位被置1往声。

面試?yán)}5——位運(yùn)算改錯(cuò)（位運(yùn)算符和邏輯運(yùn)算符）。

面試?yán)}6——運(yùn)用位運(yùn)算交換a戳吝、b兩個(gè)數(shù)浩销。

面試?yán)}7——列舉并解釋C++中的四種運(yùn)算符轉(zhuǎn)化，說(shuō)明它們的不同點(diǎn)（const_cast听哭、dynamic_cast慢洋、reinterpret_cast和static_cast）。

面試?yán)}8——用#define聲明一個(gè)常數(shù)陆盘，用以表明一年中有多少秒普筹。如：

   #define SECONDS_PER_YEAR(60*60*24*365)UL

面試?yán)}9——用C語(yǔ)言寫死循環(huán)（while(1){}或for(;;){}或loop:…goto loop;）。

面試?yán)}10——如果訪問(wèn)特定位置的內(nèi)存隘马。

面試?yán)}11——對(duì)中斷服務(wù)代碼的評(píng)論（_interrupt）太防。

面試?yán)}12——分析代碼寫結(jié)果（整數(shù)的自動(dòng)轉(zhuǎn)換）。

面試?yán)}13——關(guān)鍵字static的作用祟霍。

面試?yán)}14——關(guān)鍵字volatile的作用：定義為volatile的變量可能會(huì)被意想不到地改變杏头，這樣，編譯器就不會(huì)去假設(shè)這個(gè)變量的值沸呐。幾個(gè)例子：并行設(shè)備的硬件寄存器（如狀態(tài)寄存器）；一個(gè)中斷服務(wù)子程序中會(huì)訪問(wèn)到的非自動(dòng)變量（Non-automatic variables）呢燥；多線程應(yīng)用中被幾個(gè)任務(wù)共享的變量崭添。

面試?yán)}15——判斷處理器使用Big_endian還是Little_endian模式存儲(chǔ)數(shù)據(jù)（若是前者，返回0叛氨；若是后者呼渣，返回1。）寞埠。

面試?yán)}16——評(píng)價(jià)代碼片斷（處理器字長(zhǎng)）屁置。

六、 C++面向?qū)ο?/p>

面試?yán)}1——面向?qū)ο蠹夹g(shù)的基本概率（類（抽象仁连、繼承蓝角、封裝、重載饭冬、多態(tài)）使鹅、對(duì)象、消息）昌抠。

面試?yán)}2——判斷題（類的基本概念）患朱。

面試?yán)}3——選C相比，C++的改進(jìn)（面向?qū)ο螅?/p>

面試?yán)}4——class和struct的區(qū)別（在C中炊苫，struct只是作為一種復(fù)雜數(shù)據(jù)類型定義裁厅，不能用于面向?qū)ο缶幊瘫常籆++中對(duì)于成員訪問(wèn)權(quán)限及繼承方式，class中默認(rèn)的是private执虹，而struct中則是public倦淀。class還可以用于表示模板類型，struct則不行声畏。）撞叽。

面試?yán)}5——改錯(cuò)（C++類對(duì)象的聲明，與構(gòu)造函數(shù)相匹配）插龄。

面試?yán)}6——分析代碼寫結(jié)果（C++類成員的訪問(wèn)）愿棋。

面試?yán)}7——找錯(cuò)（類成員的初始化）。

面試?yán)}8-——分析代碼寫結(jié)果（靜態(tài)成員變量的使用：是該類類型的全局變量均牢。靜態(tài)成員只是一個(gè)糠雨，由該類類型的所有對(duì)象共享訪問(wèn)）。

面試?yán)}9——與全局對(duì)象相比徘跪，使用靜態(tài)數(shù)據(jù)成員有什么優(yōu)勢(shì)（靜態(tài)數(shù)據(jù)成員沒(méi)有進(jìn)入程序的全局名字空間甘邀，因此不存在程序中其他全局名字沖突的問(wèn)題。使用靜態(tài)成員可以隱藏信息垮庐，因此靜態(tài)成員可以是private成員松邪，而全局對(duì)象不能。）哨查。

面試?yán)}10——有哪幾種情況只能初始化列表（initialization list）逗抑，而不能用賦值（assignment）：const和reference類型成員變量只能被初始化而不能被賦值操作；類的構(gòu)造函數(shù)需要調(diào)用其基類的構(gòu)造函數(shù)寒亥。

面試?yán)}11——代碼改錯(cuò)（靜態(tài)成員的使用）邮府。

面試?yán)}12——選擇題（對(duì)靜態(tài)數(shù)據(jù)成員的正確描述：不受private控制符作用，可以直接用類名調(diào)用溉奕。）褂傀。

面試?yán)}13——main函數(shù)執(zhí)行以前，會(huì)執(zhí)行什么代碼（全局對(duì)象的構(gòu)造函數(shù)）加勤。

面試?yán)}14——C++中的空類仙辟，默認(rèn)情況下會(huì)產(chǎn)生哪些類成員函數(shù)：默認(rèn)構(gòu)造函數(shù)和復(fù)制構(gòu)造函數(shù)，它們被用于類的對(duì)象的構(gòu)造過(guò)程胸竞；析構(gòu)函數(shù)欺嗤，它被用于類的對(duì)象的析構(gòu)過(guò)程；賦值函數(shù)卫枝，它被用于同類的對(duì)象間的賦值過(guò)程煎饼；取值運(yùn)算，當(dāng)對(duì)類的對(duì)象進(jìn)行取地址（&）時(shí)校赤，此函數(shù)被調(diào)用吆玖。

面試?yán)}15——構(gòu)造函數(shù)和析構(gòu)函數(shù)是否可以被重載（前者可以筒溃，后者不可以）。

面試?yán)}16——分析代碼（重載構(gòu)造函數(shù)的調(diào)用）沾乘。

面試?yán)}17——分析代碼（構(gòu)造函數(shù)的使用）怜奖。

面試?yán)}18——構(gòu)造函數(shù)explicit與普通構(gòu)造函數(shù)的區(qū)別（前者只能被顯式調(diào)用，后者能夠被隱式調(diào)用）翅阵。

面試?yán)}19——分析代碼（explicit構(gòu)造函數(shù)的使用）歪玲。

面試?yán)}20——C++中虛析構(gòu)函數(shù)的作用（實(shí)現(xiàn)多態(tài)。只有當(dāng)一個(gè)類被用來(lái)作為基類的時(shí)候掷匠，才會(huì)把析構(gòu)函數(shù)寫成虛函數(shù)滥崩。）。

面試?yán)}21——分析代碼寫結(jié)果（析構(gòu)函數(shù)的執(zhí)行順序：與構(gòu)造函數(shù)相反）讹语。

面試?yán)}22——拷貝構(gòu)造函數(shù)（復(fù)制構(gòu)造函數(shù)）何時(shí)調(diào)用：一個(gè)對(duì)象以值傳遞的方式傳入函數(shù)體钙皮；一個(gè)對(duì)象以值傳遞的方式從函數(shù)返回；一個(gè)對(duì)象需要通過(guò)另外一個(gè)對(duì)象進(jìn)行初始化顽决。淺拷貝是讓新舊兩個(gè)對(duì)象指向同一個(gè)外部的內(nèi)容短条，而深拷貝是指為新對(duì)象制作了外部對(duì)象的獨(dú)立復(fù)制。

面試?yán)}23——什么時(shí)候編譯器會(huì)生成默認(rèn)的拷貝構(gòu)造函數(shù)：用戶沒(méi)有定義拷貝構(gòu)造函數(shù)而在代碼中使用到了拷貝構(gòu)造函數(shù)時(shí)才菠，編譯器就會(huì)生成默認(rèn)的拷貝構(gòu)造函數(shù)茸时。但如果用戶定義了拷貝構(gòu)造函數(shù)，編譯器就不會(huì)生成默認(rèn)的copy constructor鸠儿。

面試?yán)}24——寫一個(gè)繼承類的復(fù)制函數(shù)的原則是：使用基類的拷貝構(gòu)造函數(shù)屹蚊。

面試?yán)}25——拷貝構(gòu)造函數(shù)與賦值函數(shù)的區(qū)別：前者是一個(gè)對(duì)象初始化一塊內(nèi)存區(qū)域，這塊內(nèi)存就是新對(duì)象的內(nèi)存區(qū)进每，后者是對(duì)于一個(gè)已經(jīng)被初始化的對(duì)象來(lái)進(jìn)行賦值操作。前者大多數(shù)情況下是復(fù)制命斧，后者則是引用對(duì)象田晚。實(shí)現(xiàn)不一樣，前者首先是一個(gè)構(gòu)造函數(shù)国葬，它調(diào)用的時(shí)候是通過(guò)參數(shù)的對(duì)象初始化一個(gè)對(duì)象贤徒，而后者則是把一個(gè)新的對(duì)象賦值給一個(gè)原有的對(duì)象。

面試?yán)}26——編寫類string的構(gòu)造函數(shù)汇四、析構(gòu)函數(shù)和賦值函數(shù)接奈。

面試?yán)}27——分析代碼寫結(jié)果（C++類各成員函數(shù)關(guān)系：構(gòu)造、析構(gòu)和賦值）通孽。

面試?yán)}28——分析代碼寫結(jié)果（C++類的臨時(shí)對(duì)象）序宦。

面試?yán)}29——分析代碼寫輸出（拷貝構(gòu)造函數(shù)和析構(gòu)函數(shù)）。

面試?yán)}30——分析代碼寫結(jié)果（C++靜態(tài)成員和臨時(shí)對(duì)象）背苦。

面試?yán)}31——什么是臨時(shí)對(duì)象互捌？在什么情況下產(chǎn)生潘明？（僅使用一小段時(shí)間的變量稱為臨時(shí)變量，應(yīng)避免它的使用秕噪，因?yàn)闀?huì)影響程序的效率钳降。）。

面試?yán)}32——什么是函數(shù)重載（用來(lái)描述同名函數(shù)具有相同或者相似功能腌巾，但數(shù)據(jù)類型或者是參數(shù)不同的函數(shù)管理操作）遂填。C++支持而C不支持。

面試?yán)}33——函數(shù)重載的正確聲明澈蝙。

面試?yán)}34——重載與覆寫的區(qū)別（重載overriding是指子類改寫父類的方法吓坚；覆寫overloading是指同一個(gè)函數(shù)的不同版本之間參數(shù)不同。）重載特征：方法名必須相同碉克；參數(shù)列表必須不相同凌唬；返回值類型可以不相同。覆寫特征：只有虛方法和抽象方法才能夠被覆寫漏麦；具有相同的函數(shù)名客税；具有相同的參數(shù)列表；具有相同的返回值類型撕贞。

面試?yán)}35——重載“=”和“+”運(yùn)算符更耻。形式：type operator @ (arglist)

面試?yán)}36——各類運(yùn)算符重載函數(shù)的編寫（“<”、“>”捏膨、“==”秧均、“!=”、“+=-----”以及輸入輸出運(yùn)算符）号涯。

面試?yán)}37——分析代碼寫輸出（new操作符重載的使用）目胡。

七、 C++繼承與多態(tài)

面試?yán)}1——C++類繼承的三種關(guān)系（public链快、private和protected）誉己。

面試?yán)}2——同1。

面試?yán)}3——同1域蜗。

面試?yán)}4——私有繼承作用：編譯器一般不會(huì)將派生類對(duì)象轉(zhuǎn)換成基類對(duì)象巨双；從私有基類繼承而來(lái)的成員成為派生類的私有成員。

面試?yán)}5——私有繼承和組合的相同點(diǎn)和不同點(diǎn)：它們都可以表示“hasa”（即有一個(gè)）關(guān)系霉祸；但私有繼承中派生類訪問(wèn)基類的protected成員筑累，并且可以重寫基類的虛擬函數(shù)（甚至當(dāng)基類是抽象類時(shí)），組合不具有這些功能丝蹭。選擇它們的原則為盡可能使用組合慢宗，萬(wàn)不得已時(shí)使用私有繼承。

面試?yán)}6——多態(tài)：編譯時(shí)的多態(tài)性（重載）、運(yùn)行時(shí)的多態(tài)性（虛成員）婆廊。

面試?yán)}7——虛函數(shù)如何實(shí)現(xiàn)：如果一個(gè)類中含有虛函數(shù)迅细，則系統(tǒng)會(huì)為這個(gè)類分配一個(gè)指針成員指向一張?zhí)摵瘮?shù)表（vtbl），表中每一項(xiàng)指向一個(gè)虛函數(shù)的地址淘邻，實(shí)現(xiàn)上就是一個(gè)函數(shù)指針的數(shù)組茵典。虛函數(shù)表既有繼承性又有多態(tài)性。宾舅，每個(gè)派生類的虛函數(shù)表繼承了它各個(gè)基類的虛函數(shù)表统阿。在類對(duì)象的內(nèi)存分布中，首先是虛函數(shù)表指針筹我，然后才是對(duì)象數(shù)據(jù)扶平。

面試?yán)}8——分析代碼寫輸出（構(gòu)造函數(shù)調(diào)用虛函數(shù)：虛函數(shù)不會(huì)向下匹配到派生類，而是直接執(zhí)行基類的函數(shù)蔬蕊。）结澄。

面試?yán)}9--——分析代碼寫輸出（虛函數(shù)的作用）。

面試?yán)}10——分析代碼寫結(jié)果（虛函數(shù)）岸夯。

面試?yán)}11——選擇題（虛函數(shù)相關(guān)）麻献。

面試?yán)}12——多重繼承的優(yōu)點(diǎn)在于對(duì)象可以調(diào)用多個(gè)基類中的接口；缺點(diǎn)是如果派生類所繼承的多個(gè)基類有相同的基類猜扮，而派生類對(duì)象需要調(diào)用這個(gè)祖先類的接口方法勉吻，容易產(chǎn)生二義性（解決方法：加上全局符確定調(diào)用復(fù)制；使用虛擬繼承旅赢。）齿桃。

面試?yán)}13——分析代碼找錯(cuò)（多重繼承中的二義性）。

面試?yán)}14——多重繼承二義性的消除（虛擬繼承）煮盼。

面試?yán)}15——分析代碼寫結(jié)果（多重繼承和虛擬繼承）短纵。

面試?yán)}16——為什么要引入抽象基類和純虛函數(shù)：為了方便使用多態(tài)特性；在很多情況下僵控，基類本身生成對(duì)象時(shí)不合情理的踩娘。純虛函數(shù)在基類中沒(méi)有定義，必須在子類中加以實(shí)現(xiàn)喉祭。如果基類含有一個(gè)或多個(gè)純虛函數(shù)，那么它就屬于抽象基類雷绢，不能被實(shí)例化泛烙。

面試?yán)}17——虛函數(shù)與純虛函數(shù)的區(qū)別：（1）類里聲明虛函數(shù)的作用是為了能讓這個(gè)函數(shù)在它的子類里面被覆蓋，這樣編譯器就可以使用后期綁定來(lái)達(dá)到多態(tài)了翘紊。純虛函數(shù)只是一個(gè)接口蔽氨，是個(gè)函數(shù)的聲明而已，它要留到子類中去實(shí)現(xiàn)。（2）虛函數(shù)在子類里面也可以不重載鹉究，但純虛函數(shù)必須在子類中去實(shí)現(xiàn)宇立。（3）虛函數(shù)的類用于“實(shí)作繼承”，也就是說(shuō)繼承接口的同時(shí)也繼承了父類的實(shí)現(xiàn)自赔。純虛函數(shù)的類用于“界面繼承”妈嘹，即純虛函數(shù)關(guān)注的是接口的統(tǒng)一性，實(shí)現(xiàn)由子類完成绍妨。

面試?yán)}18——程序找錯(cuò)（抽象類不能實(shí)例化）润脸。

面試?yán)}19——應(yīng)用題（用面向?qū)ο蟮姆椒ㄟM(jìn)行設(shè)計(jì)）。

面試?yán)}20——什么是COM（組件對(duì)象模型Component Object Model）：通過(guò)定義二進(jìn)制標(biāo)準(zhǔn)解決一下問(wèn)題他去，即DLLsf是針對(duì)C接口寫的毙驯，它們只能被C或理解C調(diào)用規(guī)范的語(yǔ)言使用，由編程語(yǔ)言實(shí)現(xiàn)共享代碼灾测，而不是由動(dòng)態(tài)鏈接庫(kù)本身實(shí)現(xiàn)爆价。簡(jiǎn)單地說(shuō)，它定義了一種二進(jìn)制標(biāo)準(zhǔn)媳搪，使得任何編程語(yǔ)言都能存取它所編寫的模塊铭段。

面試?yán)}21——COM組件是一種商業(yè)標(biāo)準(zhǔn)，其商業(yè)品牌被稱為ActiveX蛾号。組件的特點(diǎn)有：組件與開發(fā)工具語(yǔ)言無(wú)關(guān)稠项；通過(guò)接口有效保證了組件的復(fù)用性；組件運(yùn)行效率高鲜结，便于使用和管理展运。

面試?yán)}22——如何理解COM對(duì)象和接口：一個(gè)對(duì)象實(shí)現(xiàn)一個(gè)接口，一個(gè)接口定義了接口的成員函數(shù)精刷、調(diào)用方法拗胜、返回類型、它們的參數(shù)類型和參數(shù)數(shù)量怒允，以及這些函數(shù)要干什么埂软。接口的實(shí)現(xiàn)就是程序員在一個(gè)接口定義上提供的執(zhí)行相關(guān)動(dòng)作的代碼。但是纫事，在COM模型中勘畔，對(duì)象本身對(duì)于客戶來(lái)說(shuō)是不可見的，客戶請(qǐng)求服務(wù)時(shí)丽惶，只能通過(guò)接口實(shí)現(xiàn)炫七，每個(gè)接口都由一個(gè)128位的全局標(biāo)識(shí)符（GUID，Globally unique Identifier）來(lái)標(biāo)識(shí)钾唬。與接口類似万哪，每個(gè)對(duì)象也用一個(gè)GUID來(lái)標(biāo)識(shí)侠驯，稱為CLSID（class ID）。繼承在COM里并不意味著代碼的重用奕巍。如果一個(gè)接口由另一個(gè)接口繼承的話吟策，它就包含了另一個(gè)接口定義的所有方法。管理實(shí)現(xiàn)COM對(duì)象的IUnknown::QueryInterface方法的3個(gè)主要規(guī)則：對(duì)象必須要有一個(gè)標(biāo)識(shí)符的止；對(duì)象實(shí)例的接口集合必須是靜態(tài)的檩坚；在對(duì)象中從任何其他的接口查詢此接口都應(yīng)該成功。

面試?yán)}23——ActiveX是微軟提出的一套基于COM的構(gòu)件技術(shù)標(biāo)準(zhǔn)冲杀，實(shí)際上是對(duì)象嵌入與鏈接（OLE）的新版本效床。DCOM（Distribute COM）是基于分布式環(huán)境下的COM，它實(shí)現(xiàn)了COM對(duì)象與遠(yuǎn)程計(jì)算機(jī)上的另一個(gè)對(duì)象之間的相互交互权谁。

面試?yán)}24——DLL HELL：是指DLL（動(dòng)態(tài)鏈接庫(kù)）版本沖突的問(wèn)題。

補(bǔ)充：虛函數(shù)表——主要是一個(gè)類的虛函數(shù)的地址旺芽，這張表解決了繼承沪猴、覆蓋的問(wèn)題，其內(nèi)容真實(shí)反映了實(shí)際函數(shù)采章。對(duì)于一個(gè)單繼承的類运嗜，如果它有虛擬函數(shù)，則只有一張?zhí)摵瘮?shù)表悯舟。對(duì)于多重繼承的類担租，它可能有多張?zhí)摵瘮?shù)表。

八抵怎、 數(shù)據(jù)結(jié)構(gòu)

面試?yán)}1——編程實(shí)現(xiàn)單鏈表的建立（head頭節(jié)點(diǎn)奋救，可作為指針使用）。

面試?yán)}2——編程實(shí)現(xiàn)單鏈表的測(cè)長(zhǎng)（head指針反惕，如head->next表示先前走一步）尝艘。

面試?yán)}3——編程實(shí)現(xiàn)單鏈表的打印（head指針姿染，同上）背亥。

面試?yán)}4——編程實(shí)現(xiàn)單鏈表的節(jié)點(diǎn)查找（head->next）。

面試?yán)}5——編程實(shí)現(xiàn)單鏈表的節(jié)點(diǎn)插入（鏈表首部悬赏、中間和尾端三種情況）狡汉。

面試?yán)}6——編程實(shí)現(xiàn)單鏈表的節(jié)點(diǎn)刪除。

面試?yán)}7——編程實(shí)現(xiàn)單鏈表的逆轉(zhuǎn)闽颇。

面試?yán)}8——尋找單鏈表的中間元素（一遍掃描）轴猎。

面試?yán)}9——單鏈表的正向排序。

面試?yán)}10——判斷單鏈表是否存在環(huán)形鏈表問(wèn)題：假設(shè)兩個(gè)指針為p1和p2进萄，每循環(huán)一次p1->next，p2->next->next，知道p2=NULL或者p2->next=NULL或者p1==p2時(shí)循環(huán)結(jié)束中鼠。如果相等則說(shuō)明存在環(huán)可婶。

面試?yán)}11——有序單鏈表的合并（非遞歸方法：把較短的插入到較長(zhǎng)的即可；遞歸方法：比較兩個(gè)鏈表的第一個(gè)元素援雇，把結(jié)果鏈表的頭節(jié)點(diǎn)指向元素小的那個(gè)鏈表的第一個(gè)節(jié)點(diǎn)矛渴，再對(duì)剩下的遞歸調(diào)用此過(guò)程。）惫搏。

面試?yán)}12——約瑟夫問(wèn)題：編號(hào)為1~N的N個(gè)人按順時(shí)候圍坐一圈具温，沒(méi)人持有一個(gè)正整數(shù)，開始任選一個(gè)作為報(bào)數(shù)的上限值M筐赔，從第一個(gè)人按順時(shí)針?lè)较蜃?開始順序報(bào)數(shù)铣猩，報(bào)到M時(shí)停止報(bào)數(shù)。報(bào)M的人出列茴丰，將他的正整數(shù)作為新的M值达皿，從下一個(gè)人開始重新報(bào)數(shù)，如此下去贿肩，直至所有的人都出列為止峦椰，試編程實(shí)現(xiàn)。（循環(huán)鏈表）

面試?yán)}13——建立以個(gè)雙向鏈表（節(jié)點(diǎn)數(shù)據(jù)汰规、前驅(qū)指針汤功、后繼指針）。

面試?yán)}14——雙向鏈表的測(cè)長(zhǎng)（head->right）溜哮。

面試?yán)}15——雙向鏈表的打犹辖稹（head->right，head->data）茬射。

面試?yán)}16——雙向鏈表的節(jié)點(diǎn)查找（right指針遍歷鹦蠕，直至找到數(shù)據(jù)為data的節(jié)點(diǎn)）。

面試?yán)}17——雙向鏈表的節(jié)點(diǎn)插入（插入位置在中間時(shí)在抛，需要把節(jié)點(diǎn)的原后繼節(jié)點(diǎn)的前驅(qū)指針指向新插入的節(jié)點(diǎn)钟病，在鏈表末尾插入則不需要。）刚梭。

面試?yán)}18——雙向鏈表的節(jié)點(diǎn)刪除（刪除頭結(jié)點(diǎn)肠阱、中間節(jié)點(diǎn)和末節(jié)點(diǎn)）。

面試?yán)}19——實(shí)現(xiàn)有序雙向循環(huán)鏈表的插入操作朴读。

面試?yán)}20——?jiǎng)h除兩個(gè)雙向循環(huán)鏈表的相同節(jié)點(diǎn)屹徘。

面試?yán)}21——編程實(shí)現(xiàn)隊(duì)列的入隊(duì)、出隊(duì)衅金、測(cè)長(zhǎng)噪伊、打印簿煌。隊(duì)列是可在對(duì)頭front刪除而在隊(duì)尾rear插入的數(shù)據(jù)結(jié)構(gòu)，先進(jìn)先出（FIFO）鉴吹。

面試?yán)}22——棧在棧頂top插入姨伟、刪除，另一端稱為棧底bottom豆励。后進(jìn)先出（LIFO）夺荒。隊(duì)列和棧的區(qū)別：操作的名稱、可操作的方向良蒸、操作的方法都不相同技扼。

面試?yán)}23——隊(duì)列和棧的使用。

面試?yán)}24——同22嫩痰。

面試?yán)}25——使用隊(duì)列實(shí)現(xiàn)棧剿吻。

面試?yán)}26——棧的使用，同22始赎。

面試?yán)}27——用C++實(shí)現(xiàn)一個(gè)二叉排序樹和橙，完成創(chuàng)建節(jié)點(diǎn)、插入節(jié)點(diǎn)造垛、刪除節(jié)點(diǎn)魔招、查找節(jié)點(diǎn)等功能。非遞歸方法插入節(jié)點(diǎn)：創(chuàng)建節(jié)點(diǎn)五辽；查找新建節(jié)點(diǎn)的插入位置办斑，把新節(jié)點(diǎn)插入到目標(biāo)節(jié)點(diǎn)的正確位置。如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)值小于要插入的data杆逗，則應(yīng)該在的左子樹插入乡翅；反之則應(yīng)該在它的右子樹插入。

面試?yán)}28——使用遞歸與非遞歸方法實(shí)現(xiàn)中序遍歷：左根右罪郊。非遞歸：先將根節(jié)點(diǎn)入棧蠕蚜，遍歷左子樹；遍歷完左子樹返回時(shí)悔橄，根節(jié)點(diǎn)出棧靶累，并打印節(jié)點(diǎn)數(shù)據(jù)；再中序遍歷右子樹癣疟。

面試?yán)}29——使用遞歸與非遞歸方法實(shí)現(xiàn)先序遍歷：根左右挣柬。非遞歸：打印根節(jié)點(diǎn)數(shù)據(jù)；把根節(jié)點(diǎn)的right（右子節(jié)點(diǎn)）入棧睛挚，遍歷左子樹邪蛔；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為right扎狱，出棧侧到，遍歷以該指針為根的子樹勃教。

面試?yán)}30——使用遞歸與非遞歸方法實(shí)現(xiàn)后序遍歷：左右根。后序遍歷要求在遍歷完左右子樹后床牧，再訪問(wèn)根節(jié)點(diǎn)荣回，需要判斷根節(jié)點(diǎn)的左右子樹是否均遍歷過(guò)。

面試?yán)}31——編寫層次遍歷二叉樹的算法：一層一層地進(jìn)行遍歷戈咳，使用隊(duì)列。

面試?yán)}32——編寫判斷給定二叉樹是否為二叉排序樹的程序：中序遍歷壕吹。

九著蛙、 排序

1、插入排序：每次將一個(gè)待排序的記錄耳贬，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子數(shù)組中的適當(dāng)位置踏堡，直到全部記錄插入完成為止。分為直接插入排序（穩(wěn)定）和希爾（Shell）排序（不穩(wěn)定）咒劲。

面試?yán)}1——編程實(shí)現(xiàn)直接插入排序：把數(shù)組分為兩個(gè)區(qū)顷蟆，即前面的有序區(qū)和后面的無(wú)序區(qū)，再依次把無(wú)序區(qū)的元素插入到有序區(qū)即可腐魂。編程思想：在當(dāng)前有序區(qū)R[1,…,i-1]中查找R[i]的正確位置k（1<=k<=i-1）帐偎；將R[k,…,i-1]中的記錄均后移一位，騰出k位置上的空間插入R[i]蛔屹。

面試?yán)}2——編程實(shí)現(xiàn)直接Shell排序：先將要排序的一組數(shù)按某個(gè)增量d分成若干組削樊，對(duì)每組中全部元素進(jìn)行排序，然后用一個(gè)較小的增量對(duì)它進(jìn)行再次分組兔毒，并對(duì)新組進(jìn)行排序漫贞。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分為一組育叁，排序完成迅脐。分組插入方法。

2豪嗽、交換排序：兩兩比較待排序記錄的關(guān)鍵字谴蔑，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序?yàn)橹龟侵琛Ｆ渲饕判蚍椒ㄓ忻芭菖判蚝涂焖倥判颉?/p>

面試?yán)}3——編程實(shí)現(xiàn)直接冒泡排序：第一次掃描最小的記錄被放在最前位置树碱；第二次是次小的記錄；依次類推变秦，直到排序完成成榜。

面試?yán)}4——編程實(shí)現(xiàn)快速排序：通常稱為分治法（Divide-and-Conquer Method），將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題蹦玫，遞歸地解答這些子問(wèn)題赎婚，然后將這些子問(wèn)題的解組合為原問(wèn)題的解刘绣。基本思想——分解挣输、求解纬凤、組合。

3撩嚼、選擇排序：每一次從待排序的記錄中選出關(guān)鍵字最小的記錄停士，順序放在已排好序的子文件的最后，直到全部記錄排序完畢完丽。常用的選擇排序方法有直接選擇排序和堆排序恋技。

面試?yán)}5——直接選擇排序：第一次排序把最小的元素與第一個(gè)元素交換；第二次次小與第二個(gè)交換逻族；以此類推蜻底，直到排序完成。

面試?yán)}6——編程實(shí)現(xiàn)堆排序：有兩種堆聘鳞，即小根堆（所有子節(jié)點(diǎn)都大于其父節(jié)點(diǎn)）和大根堆（所有子節(jié)點(diǎn)都小于父節(jié)點(diǎn)）薄辅。堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任意非葉節(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右子節(jié)點(diǎn)（若存在）的關(guān)鍵字。

4抠璃、歸并排序：利用“歸并”技術(shù)來(lái)進(jìn)行排序站楚。歸并是指將若干個(gè)已排序的子文件合并成一個(gè)有序的文件。兩種實(shí)現(xiàn)方法：自底向上鸡典、自頂向下（分解源请、求解、組合）彻况。

面試?yán)}7——?dú)w并排序算法的實(shí)現(xiàn)（使用自頂向下的方法）谁尸。

5、基數(shù)排序：是箱排序的改進(jìn)和推廣纽甘。箱排序也稱桶排序（Bucket Sort）良蛮，其基本思想是：設(shè)置若干個(gè)箱子，依次掃描待排序的記錄R[0],R[1],…,R[n-1]悍赢，把關(guān)鍵字等于k的記錄全都裝入到第k個(gè)箱子里（分配）决瞳，然后按序號(hào)依次將各非空的箱子首尾連接起來(lái)（收集）。有兩種排序方法：最高位優(yōu)先MSD（Most Significant Digit first）和最低位優(yōu)先（Least Significant Digit first）左权。最典型的是LSD排序方法皮胡，其基本思想是：從低位到高位依次對(duì)數(shù)據(jù)進(jìn)行箱排序。

面試?yán)}8——使用基數(shù)排序?qū)φ麛?shù)進(jìn)行排序赏迟。

6屡贺、各種排序方法比較。

按平均時(shí)間分類：

時(shí)間復(fù)雜度

算法

O(n^2)

簡(jiǎn)單排序：直接插入、直接選擇和冒泡排序

O(nlogn)

快速甩栈、堆和歸并排序

O(n1+&)

&是介于0和1之間的常數(shù)泻仙，例如希爾排序

O(n)

桶、箱和基數(shù)排序

O(nlog2n)

歸并排序量没、快速排序的最理想情況

比較結(jié)果：簡(jiǎn)單排序中直接插入最佳玉转，快速排序最快，當(dāng)文件為正序時(shí)殴蹄，直接插入和冒泡最好究抓。

選擇排序方法的影響因素：待排序的記錄數(shù)目n；記錄的大邢啤（規(guī)模）漩蟆；關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；對(duì)穩(wěn)定性的要求妓蛮；語(yǔ)言工具的條件；存儲(chǔ)結(jié)構(gòu)圾叼；時(shí)間和空間復(fù)雜度蛤克。

面試?yán)}9——各種排序算法速度的性能比較。

面試?yán)}10——各排序算法的時(shí)間復(fù)雜度比較夷蚊。