C++及数据结构复习笔记（十）（面试笔试考点）

1.13 C++面试笔试中概念性问题考点

1、结构体和共同体的区别：

       结构体和共同体都是由多个不同的数据类型成员组成，共同体中只存放了一个被选中的成员，而结构体的所有成员都存在。在结构体中，各成员都占有自己的内存空间，它们是同时存在的。一个结构体变量的总长度等于所有成员长度之和。在共同体中，所有成员不能同时占有它的内存空间，它们不能同时存在。共同体变量的长度等于最长成员的长度。对共同体不同成员赋值，将会对其他成员重写，而对于结构体的不同成员赋值是互不影响的。

2、static和const分别怎么用，类里面static和const可以同时修饰成员函数吗？

对于变量：

       静态局部变量：当static用来修饰局部变量时，它改变了局部变量的存储位置（从栈中存放改为静态存储区）及其生命周期（局部静态变量在离开作用域时仍存放在内存中，直到程序结束），但未改变其作用域。

       静态全局变量：并未改变其存储位置及生命周期，但是改变了其作用域，使该文件外的其他文件无法访问该变量。使得其他文件可以使用相同的变量。

对于类：

       静态数据成员：用static修饰类的数据成员实际使其成为类的全局变量，会被类的所有对象共享，包括派生类的对象。static声明的数据成员必须在类外进行初始化。

       静态成员函数：静态成员函数用于引用静态数据成员。

       不可以同时用const和static修饰成员函数：C++在实现const成员函数的时候会在函数中添加一个隐式指针const this，以确保该函数不能修改类的实例的状态。但当一个成员函数是static的时候，该函数是没有this指针的。因此const的用法和static是冲突的。

3、指针和引用的区别，引用可以用常指针实现吗？

       本质上的区别是，指针是一个新的变量，只是这个变量存储的是另一个变量的地址，我们通过访问这个地址来修改变量。而引用只是一个别名，还是变量本身。对引用进行的任何操作就是对变量本身进行操作，因此以达到修改变量的目的。

4、各个排序算法的时间复杂度和稳定性，每种排序的原理。

插入排序：每次将一个待排序的数据，跟前面已经有序的序列的数字一一比较找到自己合适的位置，插入到序列中，直到全部数据插入完成。

希尔排序：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序，因此可以形象的称希尔排序为“跳着插”

冒泡排序：通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。冒泡排序改进1：在某次遍历中如果没有数据交换，说明整个数组已经有序。因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。冒泡排序改进2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。

选择排序：数组分成有序区和无序区，初始时整个数组都是无序区，然后每次从无序区选一个最小的元素直接放到有序区的最后，直到整个数组变有序区。

5、进程和线程

       进程：是并发执行的程序在执行过程中分配和管理资源的基本单位，每一个进程都有一个自己的地址空间，即进程空间。进程空间的大小只与处理机位数有关。进程至少有 5 种基本状态，它们是：初始态，执行态，等待状态，就绪状态，终止状态。

       线程：线程：是进程的一个执行单元，是进程内科调度实体。比进程更小的独立运行的基本单位。线程也被称为轻量级进程。

6、C++将基类的析构函数定义为虚函数的目的。

       若将基类的析构函数定义为虚函数，当删除一个指向派生类的基类指针时，首先会调用派生类的析构函数，然后再调用基类的析构函数；否则只会调用基类的析构函数。

7、怎样定义一个纯虚函数？纯虚函数与抽象类的关系？抽象类的特点？ 

       将虚函数赋值为0即可得到一个纯虚函数；包含纯虚函数的类是抽象类。抽象类有以下特点：不能实例化；不能作为函数参数及函数返回类型；可以定义抽象类类型的指针。

8、malloc与new的区别。

1)malloc是函数，而new是操作符 
2)malloc申请内存时，需要我们指定申请的空间大小，且返回的类型为void*，需要将其强制转换为所需类型指针；new申请内存时，会根据所申请的类型自动计算申请空间的大小，且可直接返回指定类型的指针 
3)malloc释放内存时，用free函数，而new删除对象时，用的是delete操作符 
4)malloc/free申请释放内存时，不需要需要调用析构函数，而new/delete申请释放内存时需要调用析构函数

9、二维数组作为参数传递的注意事项？ 

       需要指明数组的第二维，第一维不是必须要显式指定。

10、sizeof(字符串序列)和sizeof(字符串数组)的区别？

sizeof（字符串序列）=字符串长度+1；（算上最后面的’\0’） 
sizeof(字符串数组)=字符串长度；（用{}表示时）

11、用strlen得到字符串的长度？

       对于字符串序列，到第一个’\0’为止（’\0’自动添加且不计算在内）；对于字符串数组，必须要显示指定’\0’。对于string型字符串，不能直接使用strlen，而需要使用strlen(s.c_str())计算。

12、sizeof(class)需注意情况？ 

       sizeof只计算数据成员的大小；不计算static数据成员的大小；继承时需要考虑基类数据成员问题，考虑虚函数问题，无论有多少个虚函数，计算空间时虚函数表只计算一次。 

13、静态分配与动态分配的区别？ 

       静态分配是指在编译期间就能确定内存的大小，由编译器分配内存。动态分配是指在程序运行期间，由程序员申请的内存空间。堆和栈都可以动态分配，但静态分配只能是栈。

14、当编译器处理一个const时会将其转化成一个立即数。

15、为什么不能重新定义继承而来的非虚函数？ 

       因为非虚函数是静态绑定的，如果重新定义继承而来的非虚函数，则指向派生类的基类指针在调用该非虚函数时，将可能会产生行为异常。

16、面向过程static全局变量与全局变量的区别。 

1）全局变量默认是有外部链接性的，作用域是整个工程，在一个文件内定义的全局变量，在另一个文件中，通过extern全局变量名的声明，就可以使用全局变量。 
2）静态全局变量是显式用static修饰的全局变量，作用域是声明此变量所在的文件，其他的文件即使用extern声明也不能使用。

17、面向过程静态局部变量的特点。

1）在全局数据区分配内存； 
2）在程序执行到该对象的声明处时被首次初始化，且以后不再初始化； 
3）一般在声明处初始化，如果没有显式初始化，会被程序自动初始化为0； 
4）它始终驻留在全局数据区，直到程序运行结束。但其作用域为局部作用域，当定义它的函数或语句块结束时，其作用域随之结束；

18、面向对象静态数据成员的特点。

       静态数据成员被当作是类的成员。只分配一次内存，供所有对象共用。 静态数据成员存储在全局数据区。静态数据成员定义时要分配空间，所以不能在类声明中定义（conststatic成员可以在类中定义）。 静态数据成员主要用在各个对象都有相同的某项属性的时候。

19、面向对象静态成员函数的特点。 

       普通的成员函数一般都隐含了一个this指针，this指针指向类的对象本身，因为普通成员函数总是具体的属于某个类的具体对象的。但是与普通函数相比，静态成员函数由于不与任何的对象相联系，因此它不具有this指针。从这个意义上讲，它无法访问属于类对象的非静态数据成员，也无法访问非静态成员函数，它只能调用其余的静态成员。 

20、静态成员与非静态成员之间的可访问性。

       静态成员之间可以互相访问；非静态成员可以访问静态成员及非静态成员，而静态成员不能访问非静态成员。

21、不能声明为虚函数的几种情况。 

1)普通函数（非类成员函数）（不能被覆盖） 
2)友元函数（C++不支持友元函数继承） 
3)内联函数（编译期间展开，虚函数是在运行期间绑定） 
4)构造函数（没有对象不能使用虚函数，先有构造函数后有虚函数，虚函数是对对象的动作（构造函数不能继承）） 
5)静态成员函数（只有一份大家共享）

22、虚函数的定义及功能。

       定义：在某基类中声明为virtual 并在一个或多个派生类中被重新定义的非static成员函数。功能：实现多态性，通过指向派生类的基类指针或引用，访问派生类中同名覆盖成员函数。

23、抽象类的特点。

       含有纯虚拟函数的类称为抽象类，它不能生成对象。

       在面向对象的概念中，所有的对象都是通过类来描绘的，但是反过来，并不是所有的类都是用来描绘对象的，如果一个类中没有包含足够的信息来描绘一个具体的对象，这样的类就是抽象类。

       抽象类只能作为基类来使用，其纯虚函数的实现由派生类给出。如果派生类中没有重新定义纯虚函数，而只是继承基类的纯虚函数，则这个派生类仍然还是一个抽象类。如果派生类中给出了基类纯虚函数的实现，则该派生类就不再是抽象类了，它是一个可以建立对象的具体的类。

24、什么是多态？

       多态：同一操作作用于不同的对象，可以有不同的解释，产生不同的执行结果。在运行时，可以通过指向派生类的基类的指针或引用，来调用实现派生类中的方法。

25、#define与typedef的区别。

1) #define是预处理指令，在编译预处理时进行简单的替换，不作正确性检查。 
2)typedef是在编译时处理的。它在自己的作用域内给一个已经存在的类型一个别名。 

26、指针和引用的相同点与区别

相同点： 
1. 都是地址的概念； 
指针指向一块内存，它的内容是所指内存的地址；引用是某块内存的别名。 
区别： 
1. 指针是一个实体，而引用仅是别名； 
2. 引用使用时无需解引用(*)，指针需要解引用； 
3. 引用只能在定义时被初始化一次，之后不可变；指针可变； 
4. 引用不能为空，指针可以为空； 
5. “sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到的是指针本身(所指向的变量或对象的地址)的大小； 
6. 指针和引用的自增(++)运算意义不一样；引用的++实际上是绑定引用的对象的++，而指针的++，将指向指针之后的内存 
7.从内存分配上看：程序为指针变量分配内存区域，而引用不需要分配内存区域。

27、什么是数据抽象和封装？ 

       类的基本思想是数据抽象和封装。数据抽象是一种依赖于接口和实现分离的编程技术。类的接口包括用户所能执行的操作；类的实现则包括类的数据成员、负责接口实现的函数体以及定义类所需的各种私有函数。 
       封装实现了类的接口和实现的分离。封装后的类隐藏了它的实现细节。也就是说，类的用户只能实现接口而无法访问实现部分。

28、友元函数及友元类。

       类可以允许其他类或者函数访问它的非公有成员，方法是令其他类或者函数成为它的友元。 
       友元声明只能出现在类的内部。

29、默认构造函数

       默认构造函数（default constructor）就是在没有显式提供初始化式时调用的构造函数。它由不带参数的构造函数，或者为所有的形参提供默认实参的构造函数定义。 
       如果你没有为你的类提供任何构造函数，那么编译器将自动为你生成一个默认的无参构造函数。一旦你为你的类定义了构造函数，哪怕只是一个，那么编译器将不再生成默认的构造函数。

30、类模板的优点。

(1)可用来创建动态增长和减小的数据结构（2）它是类型无关的，因此具有很高的可复用性。（3）它在编译时而不是运行时检查数据类型，保证了类型安全。（4）它是平台无关的，可移植性。（5）可用于基本数据类型

31、果用位方法求x%y，则其通用公式为x&(y-1)。

32、在C++中，如果一个整形变量频繁使用，最好将其定义为register类型（寄存器类型）。

33、执行”int x=1;int y=~x;”语句后,y的值为？ 

       假设int占1个字节，那么1的二进制表示是 00000001 ，~表示按位取反，则 00000001变为1111 1110，在计算机中整数用补码形式表示，正数的补码是它本身，负数的补码是原数值除符号位按位取反再加一，由补码求原数值也是按位取反再加一，那么1111 1110 除符号位按位取反再加一变成1000 0010，即-2。

34、类中的this指针的含义。

       this指针是一个隐含的指针，它是指向对象本身的，表示当前对象的地址。

35、volatile关键字 。

       volatile关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改，简单地说，就是防止编译器对代码的优化。

36、程序运行时间 

       clock()是C/C++中的计时函数，而与其相关的数据类型是clock_t。在MSDN中，查得对clock函数定义如下： 
       clock_t clock(void) ; 
       clock_t为long类型； 

37、C++的多态性

       多态性可以简单地概括为“一个接口，多种方法”。 
       分为编译时多态性和运行时多态性。 
       编译时多态性：通过重载函数实现。重载允许有多个同名的函数，而这些函数的参数列表不同。编译器会根据实参类型来选定相应的函数。 
       运行时多态性：通过虚函数实现。虚函数允许子类重新定义成员函数，而子类重新定义父类的做法称为覆盖(override)，或者重写。

38、内置函数的优点以及和宏定义的区别

       内联函数是指用inline关键字修饰的简单短小的函数，它在编译阶段会在函数调用处替换成函数语句，从而减少函数调用的开销。在类内定义的函数被默认成内联函数。 
    1.宏定义是在预处理阶段进行简单替换，而内联函数是在编译阶段进行替换 
    2.编译器会对内联函数的参数类型做安全检查或自动类型转换，而宏定义则不会； 
    3.内联函数在运行时可调试，而宏定义不可以 
    4.在类中声明同时定义的成员函数，自动转化为内联函数。 
    5.宏定义会出现二义性，而内联函数不会 
    6.内联函数可以访问类的成员变量，宏定义则不能

39、虚函数内存分配

       C++的编译器保证虚函数表的指针存在于对象实例中最前面的位置（这是为了保证取到的虚函数表有最高的性能——如果有多层继承或是多重继承的情况下）。 
分为以下几种情况： 
    对于无虚函数覆盖的继承：虚函数按照其声明顺序放在虚函数表中；父类的虚函数在其子类的虚函数的前面。 
    对于有虚函数覆盖的继承：派生类中起覆盖作用的虚函数放在原基类虚函数的位置；没有被覆盖的虚函数依旧。 
    对于无虚函数覆盖的多重继承：每个父类都有自己的虚函数表；派生类的虚函数被放在了第一个父类的虚函数表中（按照声明顺序排序）。 
    对于有虚函数覆盖的多重继承：派生类中起覆盖作用的虚函数放在原基类虚函数的位置；没有被覆盖的虚函数依旧。 

40、const关键字的作用。

       const允许你告诉编译器和其他程序员某值应保持不变。    

       其使用包括：定义常量，和指针结合使用（4种表示方式），函数中使用const定义形参变量及修饰函数返回值，类中使用（修饰数据成员和成员函数）。 
        const成员函数：使类接口比较容易被理解，可以得知哪个函数不允许改动对象；使操作const对象成为可能，因为const对象只能调用const成员函数；两个成员函数如果只是常量性质不同，可以被重载。 
        在参数传递过程中，最好将确实不需改动的参数设定为const引用，因为const引用相比较普通引用，有更大的实参接受权限（形参设定为const引用，则实参可为变量，const变量，字面值常量等）。如果函数具有普通的非const引用形参，则必须给函数传递类型完全一致的非const对象。给非const引用函数传递一个字面值、一个表达式、或者一个需要进行类型转换的对象都是不允许的。

41、delete与 delete[]区别。

       delete只会调用一次析构函数，而delete[]会调用每一个成员的析构函数。简单来说，用new分配的内存用delete删除；用new[]分配的内存用delete[]删除。

42、将“引用”作为函数参数有哪些特点

1）传递引用给函数与传递指针的效果是一样的。

2）使用引用传递函数的参数，在内存中并没有产生实参的副本，它是直接对实参操作；而使用一般变量传递函数的参数，当发生函数调用时，需要给形参分配存储单元，形参变量是实参变量的副本；如果传递的是对象，还将调用拷贝构造函数。因此，当参数传递的数据较大时，用引用比用一般变量传递参数的效率和所占空间都好。

3）使用指针作为函数的参数虽然也能达到与使用引用的效果，但是，在被调函数中同样要给形参分配存储单元，且需要重复使用”*指针变量名”的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。而引用更容易使用，更清晰。

43、n=rand()%5;//产生一个5以内的随机整数

44、const型数据的小结

形式	含义
Time const t1;	t1是常对象，其值在任何情况下都不能改变
void Time::fun() const	fun是Time类中的常成员函数，可以引用，但不能修改本类中的数据成员
Time *const p;	p是指向Time类对象的常指针，p的值不能改变
const Time *p	p是指向Time类常对象的指针，其指向的类对象的值不能通过指针来改变
Time &t1=t;	t1是Time类对象t的引用，2者指向同一段内存空间

1.13 C++面试笔试中概念性问题考点

1、strcpy函数的编写（数据结构）

char *strcpy(char *strDes,const char *strSrc)//返回char* 的目的是为了实现链式表达式
{                     //链式表达式的形式如:int l=strlen(strcpy(strA,strB));
    assert(strSrc!=NULL);//若目的地址已知，也要断言目的地址不为空
    strDes=(char *)malloc(strlen(strSrc)+1);
    char *p=strDes;
    while(*strSrc!='\0')
    {
        *p++=*strSrc++;
    }
    *p='\0';
    return strDes;
}

2、string类的拷贝赋值运算符函数

class String
{
public:
    String (const char* str=NULL);//普通构造函数
    String(const String &another);//拷贝构造函数  注意形参要是常量引用类型
    ~String();//析构函数
    String & operator=(const String &another);//拷贝赋值操作符  形参要是常量引用类型，返回引用类型
private:
    char *m_data;
};
String::String(const char*str)
{
    if(NULL==str)
    {
        m_data=new char;
        m_data='\0';//此处注意
    }
    else
    {
        m_data=new char[strlen(str)+1];
        strcpy(m_data,str);
    }
}
String::~String()
{
    delete [] m_data;
    m_data=NULL;
}
String::String (const String &another)
{
    m_data=new char[strlen(another.m_data)+1];
    strcpy(m_data,another.m_data);
}
String& String::operator=(const String &another)//注意返回类型写在前面
{
    if(&another==this)
    {
        return *this;
    }
    delete [] m_data;
    m_data=NULL;
    m_data=new char[strlen(another.m_data)+1];
    strcpy(m_data,another.m_data);
    return *this;
}