一些常考的基础知识点个人总结，大神勿喷，欢迎指正。

1.广义表的表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值.表尾或为表，或为空表。

2.构造函数不能声明为虚函数。

构造函数为什么不能是虚函数？

1. 从存储空间角度，虚函数对应一个指向vtable虚函数表的指针，这大家都知道，可是这个指向vtable的指针其实是存储在对象的内存空间的。问题出来了，如果构造函数是虚的，就需要通过 vtable来调用，可是对象还没有实例化，也就是内存空间还没有，怎么找vtable呢？所以构造函数不能是虚函数。

2. 从使用角度，虚函数主要用于在信息不全的情况下，能使重载的函数得到对应的调用。构造函数本身就是要初始化实例，那使用虚函数也没有实际意义呀。所以构造函数没有必要是虚函数。虚函数的作用在于通过父类的指针或者引用来调用它的时候能够变成调用子类的那个成员函数。而构造函数是在创建对象时自动调用的，不可能通过父类的指针或者引用去调用，因此也就规定构造函数不能是虚函数。

3. 构造函数不需要是虚函数，也不允许是虚函数，因为创建一个对象时我们总是要明确指定对象的类型，尽管我们可能通过基类的指针或引用去访问它但析构却不一定，我们往往通过基类的指针来销毁对象。这时候如果析构函数不是虚函数，就不能正确识别对象类型从而不能正确调用析构函数。

4. 从实现上看，vbtl在构造函数调用后才建立，因而构造函数不可能成为虚函数从实际含义上看，在调用构造函数时还不能确定对象的真实类型（因为子类会调父类的构造函数）；而且构造函数的作用是提供初始化，在对象生命期只执行一次，不是对象的动态行为，也没有必要成为虚函数。

5. 当一个构造函数被调用时，它做的首要的事情之一是初始化它的VPTR。因此，它只能知道它是“当前”类的，而完全忽视这个对象后面是否还有继承者。当编译器为这个构造函数产生代码时，它是为这个类的构造函数产生代码——既不是为基类，也不是为它的派生类（因为类不知道谁继承它）。所以它使用的VPTR必须是对于这个类的VTABLE。而且，只要它是最后的构造函数调用，那么在这个对象的生命期内，VPTR将保持被初始化为指向这个VTABLE, 但如果接着还有一个更晚派生的构造函数被调用，这个构造函数又将设置VPTR指向它的 VTABLE，等.直到最后的构造函数结束。VPTR的状态是由被最后调用的构造函数确定的。这就是为什么构造函数调用是从基类到更加派生类顺序的另一个理由。但是，当这一系列构造函数调用正发生时，每个构造函数都已经设置VPTR指向它自己的VTABLE。如果函数调用使用虚机制，它将只产生通过它自己的VTABLE的调用，而不是最后的VTABLE（所有构造函数被调用后才会有最后的VTABLE）。

3.二叉树的相关概念：

深度：树的层数；

度：（对节点来说是）一个节点的孩子数；（对整棵树来说是）其节点的度的最大值。

完全二叉树： 将满二叉树从右向左删除节点所得的二叉树为完全二叉树。

如果一棵树有 n 个 叶子节点，那么 度为2的节点 就有 n -1个。如果我们知道一棵完全二叉树有 n 个叶子节点，那么它的节点数最多 2n 个。

任何二叉树中度为0的结点比度为2的结点多一个。

4.堆的插入元素是在最后插入，然后进行调整堆；删除元素是把最后的元素放到删除元素的地方，然后进行调整堆。

5.由先序遍历和中序遍历可以唯一确定二叉树，确定方法是：由先序序列确定根节点；按根节点把中序序列分为两端，前面的是左子树，后面的是右子树；对左右子树重复前面的步骤还原树形结构。

6.printf是从右向左压入栈，先运行右侧项，再运行左侧项。例如printf(“%d,%d”,a,++a);输出的结果应该是两个相等的值（都是a+1以后的值）。

7.在写判断语句时最好将一个右值放在= =左侧，而把左值放在右侧，因为这样可以检查出误写成赋值运算符的情况。

8.所有的ASCII码都可以用“\”加数字（一般是8进制数字）来表示。因此看到\后跟三位数字的时候要明白这是一个字符。

9.在二叉树结点的前序序列、中序序列和后序序列中,所有叶结点的先后顺序完全相同。

10.一种类型a至少提供另外一种类型t的行为,那么a类型就是b类型的子类型。公有继承的派生类就是基类的子类型。类a是类b的子类型,意味着类a适应类b,即:类a对象可以使用的场合同样适合类b的对象。

11.拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。拓扑排序得出的线性序列，只要能满足排在前面的任务先完成即可，例如V1→V2，序列中只要V1在V2前面即可（所以得出的序列可能不唯一）。

12.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足只有一个叶子节点。

13.++ 是一目运算符，自增运算，它只能用于一个变量，即变量值自增1， 不能用于表达式。++运算符有个很有意思的特点，前置++返回的为左值对象，可以在一个运算式中多次使用例如++++i，但是后置++则返回右值，无法在一个运算式中多次使用后置++（对于- -是一样的），由于无法对右值进行自增运算，因此一个对象一旦后置自增后就不能再被当前式中自增。（可以在下次自增）可以这样理解：前置运算将对象返回了，该对象的值为自增以后的，而后置操作返回的是一个值，而不是一个对象，对象自身自增了，但是并没有返回。

14.对任意一棵树,设它有n个结点,这n个结点的度数之和为n-1.

15.多型数据类型是指包含的数据元素的类型并不确定。

16.一个char占用一个字节，一个short占用2个字节，一个int占用4个字节。

17.三种数据的存储区：局部变量存储在栈，全局变量及静态变量存储在静态存储区，动态分配对象存储在堆区（动态存储区）。

18.对一个数组使用取地址符号，返回的是一个指向整个数组（而不是首元素）的指针，对于指向数组首元素的指针，只需要直接将数组赋值给指针即可。例如int a[]={1,2,3,4};&a 返回的是int （*）[4]即数组指针类型。

19.字符类型占1字节， 可以从任何地址开始，short类型占2字节， 必须从2字节倍数地址开始，int类型占4字节，必须从4字节倍数地址开始。

20.结构体在内存组织上是顺序式的，联合体则是重叠式，各成员共享一段内存，所以整个联合体的sizeof也就是每个成员sizeof的最大值。（需要考虑对齐）。

21.在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。

22.纯虚函数是在基类声明的虚函数，它在基类中没有定义，但是要求派生类都要定义自己的实现方法。在基类中实现纯虚函数的方法是在函数原型后面添加“=0”

23.比如 virtual void f()=0;

24.而c++中包含纯虚函数的类称为抽象类，由于抽象类中包含了没有定义的纯虚函数，所以不能定义抽象类的对象。总结：1.抽象类只能用作其他类的基类，不能定义抽象类的对象。2.抽象类不能用于参数类型、函数返回值或显示转换的类型3.抽象类可以定义抽象类的指针和引用，此指针可以指向它的派生类，进而实现多态性。