小米软件开发工程师 c/c++岗一、二面经，许愿office

一、数组的特点

1.在内存中，数组是一块连续的区域 
2.数组需要预留空间

在使用前需要提前申请所占内存的大小，这样不知道需要多大的空间，就预先申请可能会浪费内存空间，即数组空间利用率低 
ps：数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小（在运行阶段是不允许改变的）

3.在数组起始位置处，插入数据和删除数据效率低。

插入数据时，待插入位置的的元素和它后面的所有元素都需要向后搬移 
删除数据时，待删除位置后面的所有元素都需要向前搬移

4.随机访问效率很高，时间复杂度可以达到O(1)

因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问到了

5.数组开辟的空间，在不够使用的时候需要扩容，扩容的话，就会涉及到需要把旧数组中的所有元素向新数组中搬移 
6.数组的空间是从栈分配的

二、数组的优点

随机访问性强，查找速度快，时间复杂度为O(1)

三、数组的缺点

1.头插和头删的效率低，时间复杂度为O(N) 
2.空间利用率不高 
3.内存空间要求高，必须有足够的连续的内存空间 
4.数组空间的大小固定，不能动态拓展

链表

一、链表的特点

1.在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续 
2.链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址

每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据

3.查找数据时效率低,时间复杂度为O(N)

因为链表的空间是分散的，所以不具有随机访问性，如要需要访问某个位置的数据，需要从第一个数据开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度达到O(N)

4.空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高 
5.任意位置插入元素和删除元素效率较高，时间复杂度为O(1) 
6.链表的空间是从堆中分配的

二、链表的优点

1.任意位置插入元素和删除元素的速度快，时间复杂度为O(1) 
2.内存利用率高，不会浪费内存 
3.链表的空间大小不固定，可以动态拓展

三、链表的缺点

随机访问效率低，时间复杂度为0(N)

本质：引用是别名，指针是地址

相同点：   都是地址的概念；

指针指向一块内存，它的内容是所指内存的地址；而引用则是某块内存的别名。

     不同点：

1、引用不可以为空，但指针可以为空 ，故定义一个引用的时候，必须初始化

2、引用不可以改变指向，对一个对象"至死不渝"；但是指针可以改变指向，而指向其它对象，虽然引用不可以改变指向，但是可以改变初始化对象的内容

3、引用的大小是所指向的变量的大小，因为引用只是一个别名而已；指针是指针本身的大小，4个字节

4、引用比指针更安全。由于不存在空引用，并且引用一旦被初始化为指向一个对象，它就不能被改变为另一个对象的引用，因此引用很安全。对于指针来说，它可以随时指向别的对象，并且可以不被初始化，或为NULL，所以不安全。

C++中的虚函数的作用主要是实现了多态的机制。关于多态，简而言之就是用父类类

别的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。

多态的实现主要分为静态多态和动态多态，静态多态主要是重载，在编译的时候就已经确定；动态多态是用虚函数机制实现的，在运行期间动态绑定。

1）多态的条件：

1、必须有继承

2、要有虚函数重写

3、用父类指针（引用）指向子类对象

     2）多态的基础理论

联编：一个程序模块，代码之间互相关联的过程

动态联编：把程序联编的过程，推迟到运行时进行

静态联编

3）多态的实现效果

   同样的调用语句，不同的表现形态

4）多态的意义

  设计模式的基础

编写框架的基础

函数指针做函数参数

不可以 因为构造函数是作用是生成类对象，如果构造函数是虚函数，虚函数有虚指针指向虚函数表，需要对象调用，如果构造是虚函数，就不能生成对象。所以构造不能是虚函数

析构、缺省构造、拷贝构造、赋值运算符、两个取址运算符

1.统计同成绩学生人数