C++面试基础

• 自己整理了一些常见的面试题，频率挺高的都是，而且感觉这里这些基础的东西都会问，自己过几天也要面试了，所以发上来让大家一起看看，有什么错误的地方望提醒我纠正。
• 32位数据类型以及sizeof大小、
  • 　　char：1；  short int：2；  int：4；  long：4；  long long：8；  float：4；  double：8；bool：1 
  • 　　 指针类型的都是4（虚函数也是4，因为它是靠虚指针管理的）。sizeof结构体的运算都是内存对其的知识点。（或者可以按照8的倍数去算）。
  • 　　对类来说：空类：1个。若类中有虚函数：保存了一个指针(vptr)指向虚表，所以虚函数四个。继承的时候要把基类的内存分配的大小也算上。
  • 　　int arr[6]={};sizeof(arr)=4*6;sizeof (array） / sizeof (int)  这个是返回数组元素个数
    详见：http://blog.csdn.net/Hello_Hwc/article/details/41170719
    
    
• 内存分配有哪几种形式？分别为何？区别是什么？对编译速度影响是何（详解：http://www.cnblogs.com/daocaoren/archive/2011/06/29/2092957.html）
  • 　　栈：存储局部变量，函数参数。由系统自动创建和释放的。
  • 　　堆：它是通过new和delete管理的，不用编译器管理，由程序员管理，如果没有释放掉，操作系统会自动的回收，动态的扩展和收缩。
  • 　　栈和堆的区别
    • 管理方式：栈由系统控制，堆由程序员管理，所以堆容易产生碎片（忘记释放空间）；
    • 大小：栈比较小，堆比较大；
    • 生长方式：堆是向上生长的，栈是向下生长的。
    • 碎片问题：堆如果频繁new和delete来申请和释放内存，会导致内存的不连续，这样可能会造成大量的内存浪费（产生许多碎片）；栈是先进后出的，所以在一块内存弹出之前，它的上一块内存早就弹出了，不会出现内存保留问题
    • 分配方式：栈可以动态也可以静态，堆由于是new和delete 操作所以只能是动态的
    • 分配效率：栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是 C/C++ 函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。
  • 　　自由存储区：malloc和free申请内存你的地方，和堆很相似。
  • 　　全局静态存储区：存储全局变量，静态变量。
  • 　　常量存储区：只是存储常量，一般不允许修改。
  • 知道局部变量为什么比全局变量快么？
    • 　　当Cache命中的时候，CPU访问内存的效率是最高的 由于局部变量是存在栈中的，当一个函数占用的栈空间不是很大的时候，这部分内存很有可能全部命中cache，这时候CPU访问的效率是很高
      
      
      
• new，delete和malloc，free的区别
  • 　　new是C++的运算符，malloc是C中的库函数（STL的底层结构的内存管理都是用malloc来进行的（为什么自己查））
  • 　　malloc只管分配不进行初始化，产生的都是随机值；  
  • 　　new返回的是一个指针对象，malloc返回的是一个强制转换的指针对象
    • 　　int *p=new int pp[100]；         int *p=(Int*)malloc(sizeof(int)*128);
      
      
  • 有了malloc/free为什么还要new/delete？
    • 　　malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
    • 　　由于C++函数经常要调用C中的库函数，那么就可能会用到malloc函数，所以要有malloc。
    • 　　对于不是内置的数据类型，malloc和free无法满足动态对象的需求，对象在创建和销毁的时候会调用构造函数和析构函数，但是这两个函数不是运算符，不在编译器管理范围之内，所以只能用new和delete
      
      
      
• 内联函数与宏定义的区别，它们各有什么优点
  • 　　内联函数在运行时可调试，而宏定义不可以
  • 　　编译器会对内联函数的参数类型做安全检查或自动类型转换（同普通函数），而宏定义则不会；
  • 　　内联函数可以访问类的成员变量，宏定义则不能
  • 　　在类中声明同时定义的成员函数，自动转化为内联函数
  • 　　内联函数的优点
    • 　　上面都是，也能够减少内存开销，提高效率（函数调用引起的）
      
    • 　　缺点：引入内联函数过多，导致代码膨胀。
  • 　　宏定义优点：
    • 　　使程序简洁易懂，提高程序的运行效率（使用带参数的宏定义可以完成函数的调用功能，减少了函数调用产生的出栈入栈的开销，提高了运行的效率）
    • 　　缺点：会产生二义性（括号的使用等），不会检查参数是否合法，存在安全隐患，还有上面的那些区别。
      
      
• 理解什么是重载、覆盖、隐藏，区别是何？可否举例？（详见：http://www.cnblogs.com/qlee/archive/2011/07/04/2097055.html）
  • 　　重载：在一个类中对函数进行重载，函数名称相同，函数的参数个数，参数可能不同。
  • 　　覆盖：派生类覆盖了基类中的同名函数，函数名称相同，参数相同，基类函数必须是虚函数，
  • 　　隐藏：派生类中的函数屏蔽了与其同名的基类函数，如果函数名称相同，参数不同（无论是不是虚函数），隐藏；如果函数名称相同，参数相同，但是不是虚函数，也隐藏
    
    
• 多态 
  • 　　多态是什么：多态是由虚函数实现的。举例：动物基类和派生类（叫声）
  • 　　多态都有哪些（动态和静态的）：http://blog.csdn.net/hackbuteer1/article/details/7475622
    • 　　多态与非多态的实质区别就是函数地址是早绑定还是晚绑定。如果函数的调用，在编译器编译期间就可以确定函数的调用地址，并生产代码，是静态的，就是说地址是早绑定的。（通过函数重载实现的）而如果函数调用的地址不能在编译器期间确定，需要在运行时才确定，这就属于晚绑定。（通过虚函数实现的）
    • 　　动态绑定怎么实现：声明基类的指针，利用该指针指向任意一个子类对象，调用相应的虚函数，可以根据指向的子类的不同而实现不同的方法。
      • 　　例如：A *a；B b；a=&b；a.god();//这也是相当于动态绑定（有些题目比较难理解）
  • 　　纯虚函数和虚函数区别
    • 　　纯虚函数：在基类中只能声明不能定义，在派生类中必须都实现这个纯虚函数。带有纯虚函数的称为抽象类，只能当做基类使用，抽象类不能定义对象
    • 　　虚函数：在基类中声明定义，但是在派生类中可以不定义。
    • 　　引入纯虚函数比较安全，效率也比较高。
  • 　　虚函数原理：主要是通过虚函数指针和一个虚函数表来实现的。举个例子：在一个类中有一个虚函数，当这个类创建一个实例对象的时候，那么对象的内存中会存在一个虚函数表（保存虚函数的地址），同时创建一个虚函数指针，保存虚函数表的地址，当调用方法的时候，虚函数指针去指向这个虚函数表。对象不同调用的方法也就不想同，这就实现了多态。
    
    
  • 虚函数表的内存分配？
    • • 　　所有虚函数共用一张虚函数表（虚函数表中存放着所有虚函数的地址），而对象是通过一个指针来指向虚函数表的（指针中存放的是虚函数表的地址），C++的编译器保证虚函数指针永远是在对象内存的第一个位置，下面才是各个对象的属性。如图
        

        

        
        
        
  • 为什么析构函数要定义成虚函数
    • 首先要明确：1.每个析构函数（不加 virtual） 只负责清除自己的成员。
      2.可能有基类指针，指向的确是派生类成员的情况。（这是很正常的）
      
      那么当析构一个指向派生类成员的基类指针时，程序就不知道怎么办了。
      所以要保证运行适当的析构函数，基类中的析构函数必须为虚析构。
      反正你在写一个类时，将其析构函数写为虚函数总不会错，一样重载的。
      
      
      
      
• struct 和class有什么区别？c语言中的struct 和c＋＋中的struct一样么？有什么区别？
  • 　　C++中的struct和class区别
    • 　　默认的访问权限：struct是C中升级版本，struct的默认是public；class默认是private
    • 　　默认的继承权限;struct是public，class是private
    • 　　class可以有默认的构造和析构函数，而struct没有。
    • 　　他们都有成员函数，继承，多态，struct其实也是一个类（但是实际上也还是一个数据结构）。class可以继承struct，struct可以继承class
  • 　　C中的struct和C++中的struct区别
    • 　　C中的struct只是一个自定义的数据类型（结构体），struct是抽象的数据类型，支持一些类的操作和定义
      
      
• 说说什么是野指针？野指针什么情况下出现？ （详细）
  • 　　野指针：指向一个已经删除的对象或者未申请访问受限地址的指针。
  • 　　出现情况：没有初始化（要么等于NULL，要么指向对的地方），释放指针没有置为NULL（释放只是释放了指针所指的内存，指针本身并没有释放掉）
    
    
• 你熟悉预编译指令么？条件编译是用来做什么的？你会写么？
  • 　　预编译主要是处理#开头的指令，如#include，宏定义，条件编译等，进行初期的代码替换的工作（宏替换等）
  • 　　#include 包含源代码；#ifdef（#if define），#ifndef（ifndef=if not define：如果没有宏定义），#endif：
  • 　　条件编译：#if #else 　　#elif  #endif  目的是：防止头文件的重复包含和编译
  • 

     1 　　#ifdef 标识符
     2 　　/*程序段 1*/
     3 　　#else
     4 　　/*程序段 2*/
     5 　　#endif
     6 
     7 它的作用是当标识符已经由#define定义过了,则编译程序段1,否则编译程序段2，也可以使用简单形式
     8 
     9    #ifdef 标识符
    10 　　/*程序段1*/
    11 　 　#endif

    View Code
• String　　
• 知道断言ASSERT（）怎么样么？一定要常用。它是函数还是宏？为什么不能是函数？
  • 　assert其实是一个宏，我自己没怎么用过，它的作用是一个判断计算表达式真假。例如：assert（a!=0）（一般的它只允许调用一个表达式参数，如果多个参数判断不准确）,如果a!=0，就是结果正确，程序继续运行，如果false那就会先向stderr打印一个错误信息，然后再调用abort终止程序。（一般把这个宏放在程序中来进行调试，它主要是用作debug版本中 ）
  • 它的缺点是：频繁的调用会影响程序的性能，会增加额外的开销。
    
    
• 链表的一些操作和面试常见的题目
  • 　　http://blog.csdn.net/luckyxiaoqiang/article/details/7393134
  • 　　题目
    • 1. 求单链表中结点的个数
    • 2. 将单链表反转
    • 3. 查找单链表中的倒数第K个结点（k > 0）
    • 4. 查找单链表的中间结点
    • 5. 从尾到头打印单链表
    • 6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
    • 7. 判断一个单链表中是否有环
    • 8. 判断两个单链表是否相交
    • 9. 求两个单链表相交的第一个节点
    • 10. 已知一个单链表中存在环，求进入环中的第一个节点
    • 11. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted
• 栈的一些操作和面试题：
  • 　　题目：
    • 　　两个队列实现栈
    • 　　两个栈实现队列
    • 　　元素出栈、入栈顺序的合法性
    • 　　一个数组构造两个栈（最大限度利用空间，就是通过两个个指针：前后各一个分别扩充两个栈的内存）
      
      
• 二叉树，红黑树的一些操作和面试题
  • 　　红黑树：（详见：http://www.cnblogs.com/skywang12345/p/3245399.html）
    • 　　红黑树的数据结构（枚举颜色，父，左，右指针，颜色，节点值）
      • 

         1 enum Color
         2 {
         3           RED = 0,
         4           BLACK = 1
         5 };
         6 
         7 struct RBTreeNode
         8 {
         9            struct RBTreeNode*left, *right, *parent;
        10            int   key;
        11            int data;
        12            Color color;
        13 };

        View Code
    • 　　红黑树的各种操作的时间复杂度是多少？（所有操作都是logn）而二叉树的都是o（h）
    • 　　红黑树的特性（五点）
    • 　　红黑树和哈希表怎么选择？
      • 　　应该从四个方面分析：数据总量，空间消耗，查找效率
      • 　　查找效率：哈希表，常数时间不是吹的，这个和数据总量无关的，红黑树是logn级别的。（但是不一定选哪个，如果数量到达了一定的级别，哈希表还是比较好的，但是哈希表还有别的函数的消耗，这个也会影响）
      • 　　内存消耗：对内存消耗十分严格，最好是用红黑树，哈希表有可能会太大太难管理
      • 在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。
    • 　　红黑树相比于BST和AVL树有什么优点？
      • 　　红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。
      • 　　相比于BST（log（n+1）/log2），它的时间复杂度是更低的，而且最坏的时间复杂度是oN，这是不如红黑树的
      • 　　相比于AVL树，时间复杂度是相同的，但是红黑树的统计效率更高。其实选择哪个树主要是看插入的数据，插入的数据分布比较好则适合AVL，插入的数据比较混乱的话就适合红黑树了
    • 　　插入和删除操作（画图解释）
      • 　　左旋（将X变为左子节点），右旋操作（将Y变成右子节点）；插入（三种情况）删除（四种情况）操作。（画图解释原理）
  • 　　二叉树
    • 　　二叉树的一些节点的公式（）
      • 　　二叉树第i层上的结点数目最多为 2^{i-1} (i≥1)。
      • 　　深度为k的二叉树至多有2^{k}-1个结点(k≥1)。
      • 　　包含n个结点的二叉树的高度至少为log₂ (n+1)。
      • 　　在任意一棵二叉树中，若终端结点的个数为n₀，度为2的结点数为n₂，则n₀=n₂+1。
    • 　　二叉树的操作的复杂度：o（H）
    • 　　二叉树的一些面试题目
      • 　　前序，中序，后序遍历。（递归的）
      • 　　怎么判断二叉树是不是平衡。（每个部分都是平衡的才算平衡（高度差来判断））：递归法和非递归法
      • 　　二叉搜索树转化为有序双链表
      • 　　求一个二叉树的深度（递归）
      • 　　二叉树中两个节点的最近公共祖先节点（三种情况：无根，有parent；有根，无parent，有左右；有根和节点值）
      • 　　二叉树中叶子节点的个数（递归分别求左子树中的叶子节点和右子树的叶子节点））
        
        
• 你知道函数不能返回栈指针么？
  • 　　

    #include<iostream>
    #include<string>
    using namespace std;
    char * fun()
    {
       char s[]="abc";//局部变量存储在栈中
       return s;//返回的是栈指针
    }
    string fun1(){
        string s="abc";
        return s;
    }
    int main(){
       char *ptr=fun();//返回的栈指针，但是不管指向地方的内容是什么，一旦发生了函数调用（这里发生了函数调用，函数的入栈
                        //压栈操作使得上次栈指针往下压了（栈是向下生长的），指向的内容也就发生了变化
    　　但是栈指针指向的所以返回的栈指针指向的内容就变了，返回乱码。
       string s=fun1();
       cout<<ptr<<endl;
       cout<<s<<endl;
       return 0;
    }

• 排序
  • 　　冒泡，交换，快排，堆排序，选择排序
  • 　　http://www.cnblogs.com/Kobe10/p/5573415.html
    
    
• 知道什么是struct中的对齐么？
  • 　　http://blog.chinaunix.net/uid-14802518-id-2784907.html
  • 　　内存对齐的原则（http://blog.chinaunix.net/uid-26548237-id-3874378.html）
    • 　　（1）数据成员的对齐：对于结构的各个成员，第一个成员位于偏移为0的位置，以后每个暑假成员的偏移量必须是min(#pragma pack()指定的数，这个数据成员自身长度)的倍数；
            （2）结构体的对齐：在数据成员完成各自对齐之后，结构（或联合）本身也要进行对齐，对齐将按照#pragma pack指定的数值和结构（或联合）最大数据成员大小中，比较小的那个进行；（自己举例）结构体（char，int，short）=12
      
      
      
• extern c‘ 是干什么的？
  • 　　extern可以置于变量或者函数前，以标示变量或者函数的定义在别的文件中，
  • 　　此外extern也可用来进行链接指定。
  • 　　也就是说extern有两个作用，第一个,当它与"C"一起连用时，如: extern "C" void fun(int a, int b);则告诉编译器在编译fun这个函数名时按着C的规则去翻译相应的函数名而不是C++的，C++的规则在翻译这个函数名时会把fun这个名字变得面目 全非，可能是fun@aBc_int_int#%$也可能是别的，这要看编译器的"脾气"了(不同的编译器采用的方法不一样)，为什么这么做呢，因为 C++支持函数的重载啊，在这里不去过多的论述这个问题，如果你有兴趣可以去网上搜索，相信你可以得到满意的解释!
        第二，当extern不与"C"在一起修饰变量或函数时，如在头文件中: extern int g_Int; 它的作用就是声明函数或全局变量的作用范围的关键字，其声明的函数和变量可以在本模块活其他模块中使用，记住它是一个声明不是定义!也就是 说B模块(编译单元)要是引用模块(编译单元)A中定义的全局变量或函数时，它只要包含A模块的头文件即可,在编译阶段，模块B虽然找不到该函数或变量， 但它不会报错，它会在连接时从模块A生成的目标代码中找到此函数。
  • C++语言在编译的时候为了解决函数的多态问题，会将函数名和参数联合起来生成一个中间的函数名称，而C语言则不会，因此会造成链接时找不到对应函数的情况，此时C函数就需要用extern “C”进行链接指定，这告诉编译器，请保持我的名称，不要给我生成用于链接的中间函数名。
    
    
• 函数指针和指针函数（const）？
  • 　　int  *const a；常量指针。a的值不能修改，因为它的地址已经固定了，但是*a是可以修改的。 （地址的内容可以修改）
  • 　　const int *a;指针常量，指向常量的指针。*a是不能修改了，指向的是一个常量，但是a是可以修改的，可以给地址重新赋值
  • 　　const  int  const *a;既不可以修改内容，也不可以修改地址。
    
    
• 内存管理你懂多少？（包括内存泄漏，野指针知识，非法调用，内存溢出等）
  • 　　内存泄漏：程序中一块没有使用的内存，由于用完没有释放，导致一直存在程序中，但是又不能分给其他程序使用，造成了内存的浪费，它不会及时的发生错误
          导致内存泄漏：一般是new或者malloc的时候忘记了free或者delete了
    　　内存泄漏解决方式：VLD
  • 　　内存溢出：就是我申请了一块int a[10]的内存，但是我赋值的时候赋值a[11]，这就是内存溢出了
  • 　　因素：存取或者复制内存缓冲区的方式不安全。数组越界。是用非类型安全的语言（C/C++）。编译器设置的内存缓冲区太靠近关键数据结构。
     char s[]="1234567890"; char d[]="123"; strcpy(d,s);cout<<d<<endl<<s<<endl;输出的是1234567890 567890（15位的数，内存溢出了，栈的机制）
    
    
• malloc返回什么？怎么用？
  
  
• 字符串的操作和面试题
  • 　　替换空格20%
  • 　　打印字符串的所有排列
  • 　　第一个只出现一次的字符
  • 　　翻转单词顺序VS左旋转字符串
  • 　　怎样将整数转换成字符串数，并且不用itoa函数？
  • 　　把字符串转化为数字　　
  • 　　对称子字符串的最大长度（第一步先是找字串，找到字串之后从串中间开始往两边进行判断是不是对称的，这里要分两种情况，如果字串的长度是奇数的话那么就是以中间一个数为中心；如果字串的长度是偶数的话，那就得以两个数为中心）
    
    
• C++的四种类型转换机制
  • 　　const_cast,static_cast,dynamic_cast (),reinterpret_cast(ri:?n?t?:rpr?t)
  • 　　http://blog.csdn.net/it_yuan/article/details/22758561
    
    
  • 　　static_cast:（静态的类型转换）主要用在继承关系的对象类型（还有一般类型）的转换（不用于指针）。A a；B b； a=static_cast<A>b;（强制转换）
  • 　　dynamic_cast:（动态的类型转换:在运行的时候才进行）只能用于有继承关系的对象类型转换（指针和引用）。A a；B b；B*p=&b；A *pp=dynamic_cast<A*>p;
    当然有虚函数的类也行。
  • 　　const_cast：用于将指针常量转换为普通的常量。const int * p="2"; int * pp= const_cast<int *> p;
  • 　　reinterpret_cast:将一个类型的指针转换为另一个类型的指针。double * b=2.0;int *a=reinterpret_cast<double*>b;
    
    
• const的作用
  • 　　const定义的常量必须赋值初始化，不能另外的初始化。
  • 　　const修饰函数的输入参数：当传入的参数是用户自定义的类型，最好是用const引用修饰，可以提高效率。
  • 　　const修饰函数的返回值。
  • 　　const修饰类的成员函数。
    
    
• strcpy函数的编写？

  • char *strcpy(char *strDest, const char *strSrc);
    {
        assert((strDest!=NULL) && (strSrc !=NULL)); // 2分
        char *address = strDest; // 2分
        while( (*strDest++ = * strSrc++) != ‘\0’ ) ;// 2分return address ; // 2分
    }

  strcpy返回值的作用。返回的是一个char*，用来支持链式表达，举例如下
  • 　　strcpy 函数将strSrc 拷贝至输出参数strDest 中，同时函数的返回值又是strDest。 这样做并非多此一举，可以获得如下灵活性： char str[20]; int length = strlen( strcpy(str, “Hello World”) )
    
    
    
• explicit作用
  • 　　这个参数是用来修饰构造函数的，被修饰的构造函数不能发生隐式的类型转换。
    • 　　隐式转换的例子：A a=1；（这个发生了隐式转换，隐式的调用了）http://www.cnblogs.com/this-543273659/archive/2011/08/02/2124596.html
      
      
      
• 为什么使用static_cast而不是使用C中的转换函数？：static_cast更安全。
  • •  A* p1 = (A*) &b; // 这句是c风格的强制类型转换，编译不会报错，留下了隐患  
    •     A* p2 = static_cast<A*>(&b); // static_cast在编译时进行了类型检查，直接报错  
    •     A* p3 = dynamic_cast<A*>(&b);  
      
      
• C++中的异常处理机制
  • 　　通常，监测异常情况的程序语句包含在try中。如果try块中发生了异常（也就是错误），则用throw处理。异常由catch捕获，并得到处理。
  • 　　一般一个try不止一个catch（捕获并处理异常），具体哪个由系统来决定
    
    
• 构造函数中，成员变量一定要通过初始化列表来初始化的是
  • 　　const修饰的成员变量，引用。（这两个都是必须在定义的时候初始化），还有需要初始化的数据成员是对象(继承时调用基类构造函数)  
    
    
    
• auto_ptr和shared_ptr
  • 　　auto_ptr动态的管理内存资源的智能指针，当对象不存在的时候它会自动的释放内存，不需要人为的去管理，但是有缺陷，最好是用shared_ptr
  　　auto_ptr注意事项：
  • 　　auto_ptr不能共享所有权。例如auto_ptr<T> a(new A);auto_ptr<T> b(a);这样a的指针的所有权就归b了，a就不能通过指针去调用函数了。
  • 　　auto_ptr不能指向数组
  • 　　auto_ptr不能作为容器的成员
  • 　　不能通过复制操作来初始化auto_ptr
    std::auto_ptr<int> p(new int(42)); //OK
    std::atuo_ptr<int>p = new int(42);//Error
  • 　　不要把auto_ptr放入容器
  • 　　shared_ptr能共享所有权，而且很多好处，一般就用这个。
    
    

C++面试基础

原文：http://www.cnblogs.com/Kobe10/p/5790154.html