By SmartPtr(http://www.shnenglu.com/SmartPtr/)
      
    近一年以來，AUTODESK的面試題在網上是鬧的沸沸揚揚，作為一個名企，這是可以理解的，況且其面試題質量也是不錯的。抽一些閑暇時間，把網上傳的比較多的70道題簡單的解答了一遍，不為別的，只為再熟悉一下在大學學過的一些基礎知識。希望對大家有用。當然，這只是我的個人解答，有什么不對的或者需要補充的，大家盡管提上來，好的話我加上去的。。。

     

1. 在類的普通成員函數中調用虛函數，情況是怎么樣的？（對象、引用、指針）

多態， 事實上，這是 Template Method模式的關鍵
2. 關于成員變量初始化順序，幾個有依賴關系的成員變量要初始化，讓寫出構造函數。

在初始化列表中，成員變量的初始化順序是其在類中聲明順序，而非列表中的順序。

3. 寫一個雙鏈表。

Struct ListNode

{

    int nData;

    ListNode* pPreviousNode;

    ListNode* pNextNode;

}

一般鏈表都會有一個表頭節點與指向表頭節點的頭指針， 應該會提供列表接口， 按此數據結構實現即可。

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可以用來聲明模板參數，而struct不能

6. 稱8個小球的問題

沒題

7. stl 里面vector的實現（內部空間的申請與分配）

Vector中文名字是動態數組， 其內部數據結構就是一個數組， 但是在數組元素不夠用的時候，就要動態的重新分配， 一般是現在大小的兩倍， 然后把原數組的內容拷貝過去。所以， 在一般情況下， 其訪問速度同一般數組， 只有在重新分配發生時， 其性能才會下降

8. struct /class的區別

重復了

9. 為什么要用struct

成員的默認屬性不同，用struct的話，主要是作為數據的集合。

10. 怎樣使一個class不能被實例化

1，構造函數私有化，2，抽象類

11. 私有繼承和public繼承的區別。

私有繼承： 只繼承實現，不繼承實現 has-a

公有繼承：繼承接口與實現    is-a

12. void *p的問題

不能++

13. 引用和指針的區別與聯系。引用是否可以更改

聯系： 支持多態，可以用來引用同一對象

區別：指針可以為NULL， 引用不可以； 指針可以重賦值， 引用不可以；

14. windows編程基礎，線程與進程的區別

程序是一系列靜態的指令序列

進程是程序的一次動態執行，進程其實是一個資源的容器，包括一個私有的虛擬地址空間，一些初始的代碼與數據， 一些系統資源的句柄等

線程是一個進程中的執行體， 一般包括CPU寄存器狀態，兩個棧（內核模式，用戶模式）以及一個TLS(Thread-Local Storage)等

15. com+是否熟悉

COM+是COM技術的延伸與發展， 它包括了所有COM的基本功能（基于接口的編程模型，基本組件服務），并組合了DCOM（使組件技術延伸到了分布式領域）和MTS-Microsoft Transaction Server（提供了服務器端的組件管理與配置管理），并新增了一些服務：負載平衡，內存數據庫，事件模型，隊列服務等，主要用于Windows DNA(Distributed interNet Application Architecture)三層結構的中間層。

16. 簡述一下hash算法

哈希表的目的是表查詢插入修改能夠達到O(1)的算法復雜度， 通過對key編碼來確定其存儲地址來實現， 當不同的key得到相同的編碼時，便需要進行沖突檢測與處理，一般方法有除留余數法， 線性探測法，平方探測法， 這使其無法真正達到O(1)

17. 一個32位的數據，怎樣找到最左邊的一個1？

如果是在最左位，這個數是負數，否則的話，左移一位，看是否變成負數，這是O(n)的算法， 也可以用一個模板去與，并不斷改變這個模板

O(n/2)的算法：二分方式查找 ？？？

18. 一個4*4的格子，填入1~15 然后給個目標狀態，怎樣去搜索。
比如：
 1   2  3    6
 0   4  5    7
 8   9  10 11
12 13 14 14

再給出個最終的狀態 （隨便都可以）
0 表示一個空格，可以移動，有點像拼圖； 

人工智能的教材上用的應該就是這個例子，用A*算法，它既不是廣度搜索，也不是深度搜索，而是一種啟發式搜索，在進行下一步搜索之前，會用一個估價函數來對后面的節點評分， 取評分最優的進行下一步搜索，如果找不到結果，回溯。對于本題，用曼哈頓距離作為評分標準是個不錯的選擇。

19. 給你100萬個數據，數據的值在0~65535之間 用最快的速度排序

多關鍵字基數排序MSD(MOST SIGNIFICANT DIGIT FIRST)

20. 如果我們的一個軟件產品，用戶回復說：運行速度很慢，你怎么處理？

詢問其Workflow, 用戶的硬件環境

21. 八皇后問題，詳述解法 （八皇后問題說的是在8*8國際象棋棋盤上,要求在每一行放置一個皇后,且能做到在豎方向,斜方向都沒有沖突）

回溯法

22. kmp快速匹配算法 ---不算輕松的搞定

普通的模式匹配算法，一旦不匹配，模式串右移一位；但是其實根據一直條件，我們可以算出應該向右移幾位以避免不必要的比較；算法實現比較曲折

23. 無向圖中兩點間最短路問題 ---偉大的迪杰克斯拉算法

假設一共有N個節點， 需要一個一維數組Previous[N]來記錄前一個節點序號；一個一維數組TotalLength[N]來記錄從原點到當前節點最短路徑；一個二維數組Weights[N][N]來記錄各點之間邊的權重(如果存在)， 然后從源點到終點進行深度搜索或廣度搜索， 按以下規則：搜索到某個節點b時，假設其前一個節點為a, 把TotalLength[a] + Weights[a][b]與TotalLength[b]相比較，如果小于TotalLength[b]， 則TotalLength[b] = TotalLength[a] + Weights[a][b], Previous[b] = a; 反之則不做任何操作。這樣到搜索結束后， 從Previous[N]數組中就能得到整條最短路徑了

24. 空間中任意給兩個向量，求角平分線

先單位化， 假設單位化后結果為nv1, nv2, 則角平分線為(nv1+nv2) / 2

25. 什么是平衡樹

左右子樹都是平衡樹，且高度相差不超過1的有序二叉樹

26. 哈夫曼編碼問題

理論基礎:霍夫曼樹是帶權路徑長度（WPL：Weighted Path Length）最小的二叉樹，它不一定是完全二叉樹，應該是權值大的外結點離根節點最近的擴充二叉樹。霍夫曼編碼是為了實現數據的最小冗余編碼，是數據壓縮學的基礎。 它根據字符在電文中出現的頻率為權值，構造霍夫曼樹，左為0， 右為1. 其有兩個效果，一是保證電文有最短的編碼，二是字符間不需要分隔符，因為不同的字符必定有不同的開頭（成為前綴編碼）。

27. 有向圖求環

以該節點為源點與終點嗎進行深度優先或廣度優先搜索

28. .給n個點，求凸包問題

凸包(convex hull)是指一個最小凸多邊形，滿足這N個點都在多邊形上，或其內。算法描述：

求出最右的那個點作為凸多邊形的一個頂點(P0)，遍歷其他所有點(Pi)， 如果其他點都在向量P0Pi的同一側，則Pi也為凸多邊形的頂點。

29. 四則運算（給一個前綴表達式（波蘭式）或后綴表達式(逆波蘭式)，然后求解；給一個中綴表達式）

+*-CDBA -/EF---------------------> A+B*(C-D)-E/F       前綴-中綴

操作符進棧，一個變量tmp放上一個中間操作數（運算結果），遇到操作數檢查tmp是否為空， 空的話取兩個操作數，不空的話取一個操作數，另一個就是tmp了，操作符出棧運算，結果放入tmp中，如果是操作符，tmp清空

 ABCD-*+EF/- ---------------------> A+B*(C-D)-E/F     后綴-中綴

操作數進棧，遇到操作符，兩個操作數出棧，計算結果入棧

30. STL中container有哪些？

序列容器： vector, list, deque, bitset

關聯容器:     set, multiset, map, multimap

適配容器：stack, queue, priority_queue

類容器:         string, valarray, bitset

擴展容器：hash_set, hash_multiset, hash_map, hash_multimap

31. map中的數據存儲方式是什么？

紅黑樹， 是一種平衡二叉搜索樹， 具有良好的最壞情況運行時間（統計性能好與AVL樹）

32. map和hashmap有什么區別？

內部數據結構不同， map是紅黑樹，hashmap是哈希表

33. hashmap是標準庫中的嗎？

不是的，但在SGI stl與vc2005中都提供了。

34. vector中的erase方法跟algorithm的remove有什么區別？

vector中erase是真正刪除了元素， 迭代器訪問不到了。 algorithm中的remove只是簡單的把要remove的元素移到了容器最后面，迭代器還是可以訪問到的。因為algorithm通過迭代器操作，不知道容器的內部結構，所以無法做到真正刪除。

35. object是什么？

具有內部狀態，以及操作的 軟件構造，用來表示真實存在（物理上或概念上）的對象

36. C++中如何阻止一個類被實例化？

純虛函數；構造函數私有化（友元）

37. 一般在什么時候構造函數被聲明成private呢？

 singleton模式； 阻止某些操作（如阻止拷貝構造）

38. 什么時候編譯器會生成默認的copy constructor呢？

用戶沒有自定義copy constructor；在代碼中使用到了copy constructor;

39. 如果你已經寫了一個構造函數，編譯器還會生成copy constructor嗎？

如果我寫的是copy constructor, 不會

如果我寫的不是copy constructor, 同38

40. 為什么說如果一個類作為基類，則它的析構函數要聲明成virtual的？

因為，如果delete一個基類的指針時， 如果它指向的是一個子類的對象，那么析構函數不為虛就會導致無法調用子類析構函數，從而導致資源泄露。 當然，另一種做法是將基類析構函數設為protected.

41. inline的函數和#define有什么區別？什么時候會真的被inline，什么時候不會呢？

1) 宏是在預編譯階段簡單文本替代， inline在編譯階段實現展開

2)宏肯定會被替代，而復雜的inline函數不會被展開

3)宏容易出錯（運算順序），且難以被調試,inline不會

4)宏不是類型安全，而inline是類型安全的，會提供參數與返回值的類型檢查

當出現以下情況時inline失敗

函數size太大

inline虛函數

函數中存在循環或遞歸

函數調用其他inline函數

42. 如果把一個類的成員函數寫在類的聲明中是什么意思？

inline此函數 （inline與template類似， 必須在.h中實現）

43. public繼承和private繼承有什么架構上的區別？

public是is-a的關系，繼承接口與實現

private是has-a的關系 ，只繼承實現

44. 在多繼承的時候，如果一個類繼承同時繼承自class A和class B，而class A和B中都有一個函數叫foo()，如何明確的在子類中指出override哪個父類的foo()？

首先，foo在A,B總應該都是虛函數，否則就直接覆蓋了，就沒有這個問題了；其次，這個問題從語法角度來看似乎是無法解決。因為我們不能改原有設計（不然也沒這個問題了:)）,所有只好從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不同的函數來達到這個目的了

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. 部分模版特例化和全部模版特例化有什么區別？

偏特化只使用于類模板，而全特化適用與函數模板，類模板。

偏特化的結果還是一個模板，而全特化的結果是一個具體的類型。

47. 編一個函數，使一個單項鏈表轉置。

應該是逆序吧

這個小算法竟然花了我不少時間，沒有測試過的：

 

48. 拆解一個整數，比如4,可以拆解成4=3+1；4=2+2；4=2+1+1；4=1+1+1+1

首先，對一個數進行拆分后，可能又要對最后一個因子進行拆分，所以要用遞歸；其次，第n+1個因子是小于等于第n個因子的；再者，對最后一個因子，我可以直接輸出，也可以繼續拆分。

算法如下：

唉，老了，這個小東西搞了我N久的。。。。

49. 不用庫函數，實現strcpy或者memcpy等函數

一個字節一個字節的拷過去吧，但是要考慮源內存與目標內存的重疊。

50. 內聯函數的作用和缺點

把代碼直接插入到調用的地方，可以減少函數調用的次數，但是會增加代碼的size，還有，如果內聯失敗，在每個調用的obj里，都會產生一份該函數的拷貝，這樣既沒有怎么減少代碼的size，又沒有減少函數的調用，賠了夫人又折兵。。。

51. 指針和引用的區別

指針可以不初始化，引用必須初始化

指針可以是NULL，而引用必須引用一個實在的對象

指針可以重指向其他對象，引用一旦初始化，便不再改變

52. 友元的意義

使被聲明為友元的函數或類可以訪問某個類的非共有成員。

53. 虛函數的意義

實現多態

54. Overload, Overwrite, Override 各自的特點和意義

Overload: 函數重載(名字相同，參數不同)

Overwrite：覆蓋

Override: 虛函數重載

55. 頭文件中的ifndef/define/endif 干什么用？

防止該頭文件被重復引用。

56. ＃i nclude <filename.h> 和＃i nclude “filename.h” 有什么區別？

＃i nclude <filename.h>： 從標準庫路徑去尋找該文件，對于VC來說，應該還包括VC環境設置選項中的包含目錄以及工程屬性中指定的目錄

＃i nclude “filename.h”：先在當前目錄查找，如果找不到，按上面那種方式尋找

57. 在C++ 程序中調用被C 編譯器編譯后的函數，為什么要加extern “C”？

C++語言支持函數重載，C 語言不支持函數重載。函數被C++編譯后在庫中的名字與C 語言的不同。C++提供了C 連接交換指定符號extern“C”來解決名字匹配問題

58. 一個類有基類、內部有一個其他類的成員對象，構造函數的執行順序是怎樣的？

先執行基類的（如果基類當中有虛基類，要先執行虛基類的，其他基類則按照聲明派生類時的順序依次執行），再執行成員對象的，最后執行自己的。

59. 請描述一個你熟悉的設計模式

這個看你熟悉什么了。singleton最簡單了，template method用的最多了，bridge挺炫的，command吹吹undo,redo也不錯。。。。。

60. 在UML 中，聚合(aggregation)和組合(composition)有什么區別？

其實從名字就能分別出來了。

聚合表示只是簡單的聚聚，沒什么本質的聯系，所以這些對象的生存時間也就沒什么關系了；

組合表示了更加緊密的一種關系，這些對象有著共同的生存期。

一個典型的例子是孫悟空，手臂，金箍棒的關系。。。。

61. C#和C++除了語法上的差別以外，有什么不同的地方？

C++是直接生成可執行代碼，而C#是先生成中間代碼，等到第一次執行時，才由JIT（Just In Time）生成可執行的機器碼。

還有就是(1) c#有垃圾自動回收機制，程序員不用擔心對象的回收。(2)c#嚴禁使用指針，只能處理對象。如果希望使用指針，則僅可在unsafe 程序塊中能使用指針。(3)c#只能單繼承。(4)必須通過類名訪問靜態成員。不能像C++中那樣，通過對象訪問靜態成員。(5)在子類中重寫父類的虛函數時必須用關鍵字override,覆蓋父類的方法要用關鍵字new

62. New delete與malloc free 的區別

對于類，New 和delete會調用構造，析構函數

new，delete都是能感知到類型的。new返回一個制定的類型，delete刪除一個指定的類型，從而不用給定size。而malloc與free都是處理void類型的。用時時必須經過強制類型轉換。

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 成員變量；基類的構造函數都需要參數；類中含有其他類的成員對象，而該類的構造函數都需要參數。

65. C++是不是類型安全的？

不是。兩個不同類型的指針之間可以強制轉換。C#是類型安全的。

66. main 函數執行以前，還會執行什么代碼？

全局對象的構造函數會在main 函數之前執行。

67. 描述內存分配方式以及它們的區別。

（1）從靜態存儲區域分配。內存在程序編譯的時候就已經分配好，這塊內存在程序的整個運行期間都存在。例如全局變量，static 變量。

（2） 在棧上創建。在執行函數時，函數內局部變量的存儲單元都可以在棧上創建，函數執行結束時這些存儲單元自動被釋放。棧內存分配運算內置于處理器的指令集。用的是cache，速度較快但容量較小。

（3） 從堆上分配，亦稱動態內存分配。程序在運行的時候用malloc 或new 申請任意多少的內存，程序員自己負責在何時用free 或delete 釋放內存。動態內存的生存期由我們決定，使用非常靈活，但問題也最多。

 （4）文字常量區， 如char* p = "hello, world"就是一個例子，其內存也在程序編譯的時候就已經分配好？

  一個程序除了上面這些，還有一個(5)程序代碼區了。

68. 比較一下C++中static_cast 和 dynamic_cast 的區別。

Static_cast可以顯式的做一些自動轉換，如一些int, char一些基礎類型的轉換，以及指針之間的轉換。但是其不保證安全性。Dynamic_cast主要作用其實在于把一個基類指針轉化為子類指針，因為這個基類指針真正指向的不一定是我們想轉換的類型的對象，所以轉換可能失敗，dynamic_cast能夠知道失敗而返回NULL，而static_cast就沒那么聰明了，原因是dynamic_cast會利用rtti去查找該轉換是否可行.(耗費時間多點。)

69. 當一個類A 中沒有生命任何成員變量與成員函數,這時sizeof(A)的值是多少，如果不是零，請解釋一下編譯器為什么沒有讓它為零。

不為零，不同的對象應該有不同的地址，假設我聲明一個A的數組A a[2]，如果為零，那么a[0]和a[1]的地址豈不相同了

70. 已知兩個鏈表head1 和head2各自有序，請把它們合并成一個鏈表依然有序，要求用遞歸方法進行。

歸并排序，應該比較簡單。要注意的是如果一個鏈表為空，那么可以簡單的把另一個直接鏈過去了。

注：有一部分題的答案是在網上看到的題中就包含了的。