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. 編一個函數，使一個單項鏈表轉置。
應該是逆序吧
這個小算法竟然花了我不少時間，沒有測試過的：
struct ListNode
{
int data;
ListNode* next;
};
void ReverseList(ListNode* p)
{
ListNode* p0 = NULL;
ListNode* p1 = p->next;
ListNode* p2 = p1 ? p1->next : NULL;
// 三個指針，分別表示當前處理節點，前一節點與后一節點
// 復用頭節點的next來保存節點
while (NULL != p2)
{
p->next = p2->next; //暫存
p1->next = p0; //逆轉
p2->next = p1;
p0 = p1; //往下一個節點
p1 = p2;
p2 = p->next;
}
p->next = p1; //p1末元素變為首元素，鏈到頭節點上
}
48. 拆解一個整數，比如4,可以拆解成4=3+1；4=2+2；4=2+1+1；4=1+1+1+1
首先，對一個數進行拆分后，可能又要對最后一個因子進行拆分，所以要用遞歸；其次，第n+1個因子是小于等于第n個因子的；再者，對最后一個因子，我可以直接輸出，也可以繼續拆分。
算法如下：
void print(int res[], int num)
{
for (int i = 0; i < num; ++i)
{
printf("%d ", res[i]);
}
printf("\n");
}
// n表示總數，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;
//最大因子不可能大于總數
if(m>n) m = n;
// 循環，第二個因子可以繼續拆分，而且按照最大因子不同可以拆分成多個
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. 不用庫函數，實現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各自有序，請把它們合并成一個鏈表依然有序，要求用遞歸方法進行。
歸并排序，應該比較簡單。要注意的是如果一個鏈表為空，那么可以簡單的把另一個直接鏈過去了。
注：有一部分題的答案是在網上看到的題中就包含了的。
posted on 2007-08-17 12:28
SmartPtr 閱讀(6038)
評論(14) 編輯 收藏 引用