[url]http://blog.sina.com.cn/s/blog_5821e00e010006qy.html[/url]

一、预备知识—程序的内存分配
一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
4、文字常量区 —常量字符串就是放在这里的。程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。

二、例子程序
这是一个前辈写的，非常详细
//main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[] = "abc"; 栈
char *p2; 栈
char *p3 = "123456"; 123456\0在常量区，p3在栈上。
static int c =0； 全局（静态）初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
分配得来得10和20字节的区域就在堆区。
strcpy(p1, "123456"); 123456\0放在常量区，编译器可能会将它与p3所指向的"123456"优化成一个地方。
}
二、堆和栈的理论知识
2.1申请方式
stack:
由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
heap:
需要程序员自己申请，并指明大小，在c中malloc函数
如p1 = (char *)malloc(10);
在C++中用new运算符
如p2 = (char *)malloc(10);
但是注意p1、p2本身是在栈中的。
2.2
申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，
会 遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内 存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大 小，系统会自动的将多余的那部分重新放入空闲链表中。
2.3申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块 连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因 此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
2.4申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活
2.5堆和栈中的存储内容
栈：在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
2.6存取效率的比较

char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的；
而bbbbbbbbbbb是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
比如：
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
}
对应的汇编代码
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中，而第二种则要先把指针值读到edx中，在根据edx读取字符，显然慢了。
?

2.7小结：
堆和栈的区别可以用如下的比喻来看出：
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。

堆和栈的区别主要分：
操作系统方面的堆和栈，如上面说的那些，不多说了。
还有就是数据结构方面的堆和栈，这些都是不同的概念。这里的堆实际上指的就是（满足堆性质的）优先队列的一种数据结构，第1个元素有最高的优先权；栈实际上就是满足先进后出的性质的数学或数据结构。
虽然堆栈，堆栈的说法是连起来叫，但是他们还是有很大区别的，连着叫只是由于历史的原因。

By SmartPtr(http://www.cppblog.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)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 然后给个目标状态，怎样去搜索。

题意不懂

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 释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。

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各自有序，请把它们合并成一个链表依然有序，要求用递归方法进行。

归并排序，应该比较简单。要注意的是如果一个链表为空，那么可以简单的把另一个直接链过去了。

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