By SmartPtr(http://www.shnenglu.com/SmartPtr/)
近一年以來，AUTODESK的面試題在網(wǎng)上是鬧的沸沸揚揚，作為一個名企，這是可以理解的，況且其面試題質量也是不錯的。抽一些閑暇時間，把網(wǎng)上傳的比較多的70道題簡單的解答了一遍，不為別的，只為再熟悉一下在大學學過的一些基礎知識。希望對大家有用。當然，這只是我的個人解答，有什么不對的或者需要補充的，大家盡管提上來，好的話我加上去的。。。
1. 在類的普通成員函數(shù)中調用虛函數(shù)，情況是怎么樣的？（對象、引用、指針）
多態(tài)， 事實上，這是 Template Method模式的關鍵
2. 關于成員變量初始化順序，幾個有依賴關系的成員變量要初始化，讓寫出構造函數(shù)。
在初始化列表中，成員變量的初始化順序是其在類中聲明順序，而非列表中的順序。
3. 寫一個雙鏈表。
Struct ListNode
{
int nData;
ListNode* pPreviousNode;
ListNode* pNextNode;
}
一般鏈表都會有一個表頭節(jié)點與指向表頭節(jié)點的頭指針， 應該會提供列表接口， 按此數(shù)據(jù)結構實現(xiàn)即可。
4. 寫個is-a和has-a。
這個比較簡單
Class Pet{};
Class Dog: public Pet{};
Class Boy{Pet* m_pPet;};
5. struct vs. class.
1)默認訪問屬性， struct為public, class為private
2) 默認繼承屬性，struct為public, class為private
3)class可以用來聲明模板參數(shù)，而struct不能
6. 稱8個小球的問題
沒題
7. stl 里面vector的實現(xiàn)（內部空間的申請與分配）
Vector中文名字是動態(tài)數(shù)組， 其內部數(shù)據(jù)結構就是一個數(shù)組， 但是在數(shù)組元素不夠用的時候，就要動態(tài)的重新分配， 一般是現(xiàn)在大小的兩倍， 然后把原數(shù)組的內容拷貝過去。所以， 在一般情況下， 其訪問速度同一般數(shù)組， 只有在重新分配發(fā)生時， 其性能才會下降
8. struct /class的區(qū)別
重復了
9. 為什么要用struct
成員的默認屬性不同，用struct的話，主要是作為數(shù)據(jù)的集合。
10. 怎樣使一個class不能被實例化
1，構造函數(shù)私有化，2，抽象類
11. 私有繼承和public繼承的區(qū)別。
私有繼承： 只繼承實現(xiàn)，不繼承實現(xiàn) has-a
公有繼承：繼承接口與實現(xiàn) is-a
12. void *p的問題
不能++
13. 引用和指針的區(qū)別與聯(lián)系。引用是否可以更改
聯(lián)系： 支持多態(tài)，可以用來引用同一對象
區(qū)別：指針可以為NULL， 引用不可以； 指針可以重賦值， 引用不可以；
14. windows編程基礎，線程與進程的區(qū)別
程序是一系列靜態(tài)的指令序列
進程是程序的一次動態(tài)執(zhí)行，進程其實是一個資源的容器，包括一個私有的虛擬地址空間，一些初始的代碼與數(shù)據(jù)， 一些系統(tǒng)資源的句柄等
線程是一個進程中的執(zhí)行體， 一般包括CPU寄存器狀態(tài)，兩個棧（內核模式，用戶模式）以及一個TLS(Thread-Local Storage)等
15. com+是否熟悉
COM+是COM技術的延伸與發(fā)展， 它包括了所有COM的基本功能（基于接口的編程模型，基本組件服務），并組合了DCOM（使組件技術延伸到了分布式領域）和MTS-Microsoft Transaction Server（提供了服務器端的組件管理與配置管理），并新增了一些服務：負載平衡，內存數(shù)據(jù)庫，事件模型，隊列服務等，主要用于Windows DNA(Distributed interNet Application Architecture)三層結構的中間層。
16. 簡述一下hash算法
哈希表的目的是表查詢插入修改能夠達到O(1)的算法復雜度， 通過對key編碼來確定其存儲地址來實現(xiàn)， 當不同的key得到相同的編碼時，便需要進行沖突檢測與處理，一般方法有除留余數(shù)法， 線性探測法，平方探測法， 這使其無法真正達到O(1)
17. 一個32位的數(shù)據(jù)，怎樣找到最左邊的一個1？
如果是在最左位，這個數(shù)是負數(shù)，否則的話，左移一位，看是否變成負數(shù)，這是O(n)的算法， 也可以用一個模板去與，并不斷改變這個模板
O(n/2)的算法：二分方式查找 ？？？
18. 一個4*4的格子，填入1~15 然后給個目標狀態(tài)，怎樣去搜索。
比如：
1 2 3 6
0 4 5 7
8 9 10 11
12 13 14 14
再給出個最終的狀態(tài) （隨便都可以）
0 表示一個空格，可以移動，有點像拼圖；
人工智能的教材上用的應該就是這個例子，用A*算法，它既不是廣度搜索，也不是深度搜索，而是一種啟發(fā)式搜索，在進行下一步搜索之前，會用一個估價函數(shù)來對后面的節(jié)點評分， 取評分最優(yōu)的進行下一步搜索，如果找不到結果，回溯。對于本題，用曼哈頓距離作為評分標準是個不錯的選擇。
19. 給你100萬個數(shù)據(jù)，數(shù)據(jù)的值在0~65535之間 用最快的速度排序
多關鍵字基數(shù)排序MSD(MOST SIGNIFICANT DIGIT FIRST)
20. 如果我們的一個軟件產(chǎn)品，用戶回復說：運行速度很慢，你怎么處理？
詢問其Workflow, 用戶的硬件環(huán)境
21. 八皇后問題，詳述解法 （八皇后問題說的是在8*8國際象棋棋盤上,要求在每一行放置一個皇后,且能做到在豎方向,斜方向都沒有沖突）
回溯法
22. kmp快速匹配算法 ---不算輕松的搞定
普通的模式匹配算法，一旦不匹配，模式串右移一位；但是其實根據(jù)一直條件，我們可以算出應該向右移幾位以避免不必要的比較；算法實現(xiàn)比較曲折
23. 無向圖中兩點間最短路問題 ---偉大的迪杰克斯拉算法
假設一共有N個節(jié)點， 需要一個一維數(shù)組Previous[N]來記錄前一個節(jié)點序號；一個一維數(shù)組TotalLength[N]來記錄從原點到當前節(jié)點最短路徑；一個二維數(shù)組Weights[N][N]來記錄各點之間邊的權重(如果存在)， 然后從源點到終點進行深度搜索或廣度搜索， 按以下規(guī)則：搜索到某個節(jié)點b時，假設其前一個節(jié)點為a, 把TotalLength[a] + Weights[a][b]與TotalLength[b]相比較，如果小于TotalLength[b]， 則TotalLength[b] = TotalLength[a] + Weights[a][b], Previous[b] = a; 反之則不做任何操作。這樣到搜索結束后， 從Previous[N]數(shù)組中就能得到整條最短路徑了
24. 空間中任意給兩個向量，求角平分線
先單位化， 假設單位化后結果為nv1, nv2, 則角平分線為(nv1+nv2) / 2
25. 什么是平衡樹
左右子樹都是平衡樹，且高度相差不超過1的有序二叉樹
26. 哈夫曼編碼問題
理論基礎:霍夫曼樹是帶權路徑長度（WPL：Weighted Path Length）最小的二叉樹，它不一定是完全二叉樹，應該是權值大的外結點離根節(jié)點最近的擴充二叉樹。霍夫曼編碼是為了實現(xiàn)數(shù)據(jù)的最小冗余編碼，是數(shù)據(jù)壓縮學的基礎。 它根據(jù)字符在電文中出現(xiàn)的頻率為權值，構造霍夫曼樹，左為0， 右為1. 其有兩個效果，一是保證電文有最短的編碼，二是字符間不需要分隔符，因為不同的字符必定有不同的開頭（成為前綴編碼）。
27. 有向圖求環(huán)
以該節(jié)點為源點與終點嗎進行深度優(yōu)先或廣度優(yōu)先搜索
28. .給n個點，求凸包問題
凸包(convex hull)是指一個最小凸多邊形，滿足這N個點都在多邊形上，或其內。算法描述：
求出最右的那個點作為凸多邊形的一個頂點(P0)，遍歷其他所有點(Pi)， 如果其他點都在向量P0Pi的同一側，則Pi也為凸多邊形的頂點。
29. 四則運算（給一個前綴表達式（波蘭式）或后綴表達式(逆波蘭式)，然后求解；給一個中綴表達式）
+*-CDBA -/EF---------------------> A+B*(C-D)-E/F 前綴-中綴
操作符進棧，一個變量tmp放上一個中間操作數(shù)（運算結果），遇到操作數(shù)檢查tmp是否為空， 空的話取兩個操作數(shù)，不空的話取一個操作數(shù)，另一個就是tmp了，操作符出棧運算，結果放入tmp中，如果是操作符，tmp清空
ABCD-*+EF/- ---------------------> A+B*(C-D)-E/F 后綴-中綴
操作數(shù)進棧，遇到操作符，兩個操作數(shù)出棧，計算結果入棧
30. STL中container有哪些？
序列容器： vector, list, deque, bitset
關聯(lián)容器: set, multiset, map, multimap
適配容器：stack, queue, priority_queue
類容器: string, valarray, bitset
擴展容器：hash_set, hash_multiset, hash_map, hash_multimap
31. map中的數(shù)據(jù)存儲方式是什么？
紅黑樹， 是一種平衡二叉搜索樹， 具有良好的最壞情況運行時間（統(tǒng)計性能好與AVL樹）
32. map和hashmap有什么區(qū)別？
內部數(shù)據(jù)結構不同， map是紅黑樹，hashmap是哈希表
33. hashmap是標準庫中的嗎？
不是的，但在SGI stl與vc2005中都提供了。
34. vector中的erase方法跟algorithm的remove有什么區(qū)別？
vector中erase是真正刪除了元素， 迭代器訪問不到了。 algorithm中的remove只是簡單的把要remove的元素移到了容器最后面，迭代器還是可以訪問到的。因為algorithm通過迭代器操作，不知道容器的內部結構，所以無法做到真正刪除。
35. object是什么？
具有內部狀態(tài)，以及操作的 軟件構造，用來表示真實存在（物理上或概念上）的對象
36. C++中如何阻止一個類被實例化？
純虛函數(shù)；構造函數(shù)私有化（友元）
37. 一般在什么時候構造函數(shù)被聲明成private呢？
singleton模式； 阻止某些操作（如阻止拷貝構造）
38. 什么時候編譯器會生成默認的copy constructor呢？
用戶沒有自定義copy constructor；在代碼中使用到了copy constructor;
39. 如果你已經(jīng)寫了一個構造函數(shù)，編譯器還會生成copy constructor嗎？
如果我寫的是copy constructor, 不會
如果我寫的不是copy constructor, 同38
40. 為什么說如果一個類作為基類，則它的析構函數(shù)要聲明成virtual的？
因為，如果delete一個基類的指針時， 如果它指向的是一個子類的對象，那么析構函數(shù)不為虛就會導致無法調用子類析構函數(shù)，從而導致資源泄露。 當然，另一種做法是將基類析構函數(shù)設為protected.
41. inline的函數(shù)和#define有什么區(qū)別？什么時候會真的被inline，什么時候不會呢？
1) 宏是在預編譯階段簡單文本替代， inline在編譯階段實現(xiàn)展開
2)宏肯定會被替代，而復雜的inline函數(shù)不會被展開
3)宏容易出錯（運算順序），且難以被調試,inline不會
4)宏不是類型安全，而inline是類型安全的，會提供參數(shù)與返回值的類型檢查
當出現(xiàn)以下情況時inline失敗
函數(shù)size太大
inline虛函數(shù)
函數(shù)中存在循環(huán)或遞歸
函數(shù)調用其他inline函數(shù)
42. 如果把一個類的成員函數(shù)寫在類的聲明中是什么意思？
inline此函數(shù) （inline與template類似， 必須在.h中實現(xiàn)）
43. public繼承和private繼承有什么架構上的區(qū)別？
public是is-a的關系，繼承接口與實現(xiàn)
private是has-a的關系 ，只繼承實現(xiàn)
44. 在多繼承的時候，如果一個類繼承同時繼承自class A和class B，而class A和B中都有一個函數(shù)叫foo()，如何明確的在子類中指出override哪個父類的foo()？
首先，foo在A,B總應該都是虛函數(shù)，否則就直接覆蓋了，就沒有這個問題了；其次，這個問題從語法角度來看似乎是無法解決。因為我們不能改原有設計（不然也沒這個問題了:)）,所有只好從extend來考慮：
class EA: public class A
{
public:
virtual void foo(){fooA();}
private:
virtual void fooA() = 0;
}
class EB: public class B
{
public:
virtual void foo(){fooB();}
private:
virtual void fooB() = 0;
}
這樣， 我就可以override不同的函數(shù)來達到這個目的了
class AB: public EA, pubic EB
{
private:
virtual void fooA(){}
virtual void fooB(){}
}
45. 虛擬繼承的語法是什么？
A
/ \
B C
\ /
D
class A{};
class B: virtual public A{};
class C: virtual public A{};
class D: public B, public C{};
46. 部分模版特例化和全部模版特例化有什么區(qū)別？
偏特化只使用于類模板，而全特化適用與函數(shù)模板，類模板。
偏特化的結果還是一個模板，而全特化的結果是一個具體的類型。
47. 編一個函數(shù)，使一個單項鏈表轉置。
應該是逆序吧
這個小算法竟然花了我不少時間，沒有測試過的：
struct ListNode
{
int data;
ListNode* next;
};
void ReverseList(ListNode* p)
{
ListNode* p0 = NULL;
ListNode* p1 = p->next;
ListNode* p2 = p1 ? p1->next : NULL;
// 三個指針，分別表示當前處理節(jié)點，前一節(jié)點與后一節(jié)點
// 復用頭節(jié)點的next來保存節(jié)點
while (NULL != p2)
{
p->next = p2->next; //暫存
p1->next = p0; //逆轉
p2->next = p1;
p0 = p1; //往下一個節(jié)點
p1 = p2;
p2 = p->next;
}
p->next = p1; //p1末元素變?yōu)槭自兀湹筋^節(jié)點上
}
48. 拆解一個整數(shù)，比如4,可以拆解成4=3+1；4=2+2；4=2+1+1；4=1+1+1+1
首先，對一個數(shù)進行拆分后，可能又要對最后一個因子進行拆分，所以要用遞歸；其次，第n+1個因子是小于等于第n個因子的；再者，對最后一個因子，我可以直接輸出，也可以繼續(xù)拆分。
算法如下：
void print(int res[], int num)
{
for (int i = 0; i < num; ++i)
{
printf("%d ", res[i]);
}
printf("\n");
}
// n表示總數(shù)，m表示最大因子
void split(int n, int m)
{
static int res[100]; //保存結果
static int num = -1; //當前因子下標
num++;
//遞歸終止條件，為0不可再分，直接輸出
if(0 == n)
{
print(res, num+1);
num--;
return;
}
else
{
if(n == m)
{
// 不拆，直接輸出
res[num] = m;
print(res,num+1);
num--;
}
else
{
// 拆分出第一個
res[num] = m;
n = n-m;
//最大因子不可能大于總數(shù)
if(m>n) m = n;
// 循環(huán)，第二個因子可以繼續(xù)拆分，而且按照最大因子不同可以拆分成多個
for (int i = m; i>=1; --i)
{
split(n, i);
}
num--;
}
}
}
void Split(int n)
{
for (int i = n-1; i>=1; i--)
{
split(n, i);
}
}
唉，老了，這個小東西搞了我N久的。。。。
49. 不用庫函數(shù)，實現(xiàn)strcpy或者memcpy等函數(shù)
一個字節(jié)一個字節(jié)的拷過去吧，但是要考慮源內存與目標內存的重疊。
50. 內聯(lián)函數(shù)的作用和缺點
把代碼直接插入到調用的地方，可以減少函數(shù)調用的次數(shù)，但是會增加代碼的size，還有，如果內聯(lián)失敗，在每個調用的obj里，都會產(chǎn)生一份該函數(shù)的拷貝，這樣既沒有怎么減少代碼的size，又沒有減少函數(shù)的調用，賠了夫人又折兵。。。
51. 指針和引用的區(qū)別
指針可以不初始化，引用必須初始化
指針可以是NULL，而引用必須引用一個實在的對象
指針可以重指向其他對象，引用一旦初始化，便不再改變
52. 友元的意義
使被聲明為友元的函數(shù)或類可以訪問某個類的非共有成員。
53. 虛函數(shù)的意義
實現(xiàn)多態(tài)
54. Overload, Overwrite, Override 各自的特點和意義
Overload: 函數(shù)重載(名字相同，參數(shù)不同)
Overwrite：覆蓋
Override: 虛函數(shù)重載
55. 頭文件中的ifndef/define/endif 干什么用？
防止該頭文件被重復引用。
56. ＃i nclude <filename.h> 和＃i nclude “filename.h” 有什么區(qū)別？
＃i nclude <filename.h>： 從標準庫路徑去尋找該文件，對于VC來說，應該還包括VC環(huán)境設置選項中的包含目錄以及工程屬性中指定的目錄
＃i nclude “filename.h”：先在當前目錄查找，如果找不到，按上面那種方式尋找
57. 在C++ 程序中調用被C 編譯器編譯后的函數(shù)，為什么要加extern “C”？
C++語言支持函數(shù)重載，C 語言不支持函數(shù)重載。函數(shù)被C++編譯后在庫中的名字與C 語言的不同。C++提供了C 連接交換指定符號extern“C”來解決名字匹配問題
58. 一個類有基類、內部有一個其他類的成員對象，構造函數(shù)的執(zhí)行順序是怎樣的？
先執(zhí)行基類的（如果基類當中有虛基類，要先執(zhí)行虛基類的，其他基類則按照聲明派生類時的順序依次執(zhí)行），再執(zhí)行成員對象的，最后執(zhí)行自己的。
59. 請描述一個你熟悉的設計模式
這個看你熟悉什么了。singleton最簡單了，template method用的最多了，bridge挺炫的，command吹吹undo,redo也不錯。。。。。
60. 在UML 中，聚合(aggregation)和組合(composition)有什么區(qū)別？
其實從名字就能分別出來了。
聚合表示只是簡單的聚聚，沒什么本質的聯(lián)系，所以這些對象的生存時間也就沒什么關系了；
組合表示了更加緊密的一種關系，這些對象有著共同的生存期。
一個典型的例子是孫悟空，手臂，金箍棒的關系。。。。
61. C#和C++除了語法上的差別以外，有什么不同的地方？
C++是直接生成可執(zhí)行代碼，而C#是先生成中間代碼，等到第一次執(zhí)行時，才由JIT（Just In Time）生成可執(zhí)行的機器碼。
還有就是(1) c#有垃圾自動回收機制，程序員不用擔心對象的回收。(2)c#嚴禁使用指針，只能處理對象。如果希望使用指針，則僅可在unsafe 程序塊中能使用指針。(3)c#只能單繼承。(4)必須通過類名訪問靜態(tài)成員。不能像C++中那樣，通過對象訪問靜態(tài)成員。(5)在子類中重寫父類的虛函數(shù)時必須用關鍵字override,覆蓋父類的方法要用關鍵字new
62. New delete與malloc free 的區(qū)別
對于類，New 和delete會調用構造，析構函數(shù)
new，delete都是能感知到類型的。new返回一個制定的類型，delete刪除一個指定的類型，從而不用給定size。而malloc與free都是處理void類型的。用時時必須經(jīng)過強制類型轉換。
63. #define DOUBLE(x) x+x，i = 5*DOUBLE(10)；i是多少？正確的聲明是什么？
I = 5*10+10 = 60 60
正確的聲明是：
#define DOUBLE(x) ((x)+(x))
64. 有哪幾種情況只能用intialization list 而不能用assignment?
當類中含有const、reference 成員變量；基類的構造函數(shù)都需要參數(shù)；類中含有其他類的成員對象，而該類的構造函數(shù)都需要參數(shù)。
65. C++是不是類型安全的？
不是。兩個不同類型的指針之間可以強制轉換。C#是類型安全的。
66. main 函數(shù)執(zhí)行以前，還會執(zhí)行什么代碼？
全局對象的構造函數(shù)會在main 函數(shù)之前執(zhí)行。
67. 描述內存分配方式以及它們的區(qū)別。
（1）從靜態(tài)存儲區(qū)域分配。內存在程序編譯的時候就已經(jīng)分配好，這塊內存在程序的整個運行期間都存在。例如全局變量，static 變量。
（2） 在棧上創(chuàng)建。在執(zhí)行函數(shù)時，函數(shù)內局部變量的存儲單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結束時這些存儲單元自動被釋放。棧內存分配運算內置于處理器的指令集。用的是cache，速度較快但容量較小。
（3） 從堆上分配，亦稱動態(tài)內存分配。程序在運行的時候用malloc 或new 申請任意多少的內存，程序員自己負責在何時用free 或delete 釋放內存。動態(tài)內存的生存期由我們決定，使用非常靈活，但問題也最多。
（4）文字常量區(qū)， 如char* p = "hello, world"就是一個例子，其內存也在程序編譯的時候就已經(jīng)分配好？
一個程序除了上面這些，還有一個(5)程序代碼區(qū)了。
68. 比較一下C++中static_cast 和 dynamic_cast 的區(qū)別。
Static_cast可以顯式的做一些自動轉換，如一些int, char一些基礎類型的轉換，以及指針之間的轉換。但是其不保證安全性。Dynamic_cast主要作用其實在于把一個基類指針轉化為子類指針，因為這個基類指針真正指向的不一定是我們想轉換的類型的對象，所以轉換可能失敗，dynamic_cast能夠知道失敗而返回NULL，而static_cast就沒那么聰明了，原因是dynamic_cast會利用rtti去查找該轉換是否可行.(耗費時間多點。)
69. 當一個類A 中沒有生命任何成員變量與成員函數(shù),這時sizeof(A)的值是多少，如果不是零，請解釋一下編譯器為什么沒有讓它為零。
不為零，不同的對象應該有不同的地址，假設我聲明一個A的數(shù)組A a[2]，如果為零，那么a[0]和a[1]的地址豈不相同了
70. 已知兩個鏈表head1 和head2各自有序，請把它們合并成一個鏈表依然有序，要求用遞歸方法進行。
歸并排序，應該比較簡單。要注意的是如果一個鏈表為空，那么可以簡單的把另一個直接鏈過去了。
注：有一部分題的答案是在網(wǎng)上看到的題中就包含了的。
posted on 2007-08-17 12:28
SmartPtr 閱讀(6041)
評論(14) 編輯 收藏 引用