c++面试

一、 C/C++程序基础

面试例题1——分析代码写输出（一般赋值语句的概念和方法）。

面试例题2——分析代码写运行结果（C++域操作符）。

面试例题3——分析代码写输出（i++和++i的区别）。

面试例题4——i++和++i哪个效率更高。++i可以返回对象引用，i++必须返回对象的值。在内建数据类型的情况下，效率没有区别。在自定义数据类型的情况下，++i效率较高。

面试例题5——选择编程风格良好的条件比较语句。

面试例题6——分析代码写结果（有符号变量与无符号变量值的转换，负数最高位为1）。

面试例题7——将数a、b的值进行交换，并且不使用任何中间变量（局部变量、加减运算、异或运算）。

面试例题8——C和C++有什么不同（面向过程与面向对象）。

面试例题9——C++是面向对象化的而C是面向过程化的？

面试例题10——为什么标准头文件都有类似一下所示的结构？（预处理结构，如ifndef、define、extern “C”、endif等）。

面试例题11——头文件引用中< >（工程或标准头文件）和“ ”（用户提供）的区别。

面试例题12——C++中main函数执行完后还执行其他语句（exit()、atexit()函数）。

二、 预处理、const、static与sizeof

面试例题1——分析代码写结果（预处理的使用）：#ifdef、#else、#endif。

面试例题2——用#define实现宏，并求最大值和最小值。

                  类如#define MAX(x, y) (((x)>(y)) ? (x): (y))

面试例题3——分析代码写结果（宏定义的使用）。

面试例题4——分析代码写结果（宏参数的连接）。

面试例题5——用宏定义得到一个字的高位和低位字节。

                  #define WORD_LO(xxx) ((byte)((word)(xxx)&255))

                  #define WORD_HI(xxx) ((byte)((word)(xxx)>>8))

面试例题6——用宏定义得到一个数组所含的元素个数。

                  #define ARR_SIZE(a) (sizeof((a))/sizeof((a[0])))

面试例题7——找错（const的使用）。

面试例题8——请说明const与#define的各自特点和区别。

面试例题9——C++中const的作用：定义常量、修饰函数形式参数（如const &参数，提高效率）、修饰函数的返回值（返回值不能被直接修改）、修饰类的成员函数（函数定义体）。

面试例题10——static的作用：在函数体静态变量维持其值不变；在模块内静态变量不能被模块外其他函数访问；在模块内静态函数只能被这一模块内的其他函数调用。

面试例题11——static全局变量与普通全局变量有什么区别（前者只初始化一次，防止在其他单元中被引用）。static局部变量和普通局部变量有什么区别（前者只初始化一次，下一次依据上一次结果值）。static函数与普通函数有什么区别（前者在内存中只有一份，后者在每个被调用中维持一份复制品）。

面试例题12——分析代码写结果（C++类的静态成员）：调用时用“::”域操作符。

面试例题13——填空（使用sizeof计算普通变量所占空间）。

面试例题14——分析代码写结果（使用sizeof计算类对象所占空间大小）。填充字节（满足最宽的基本类型成员的大小整除）。

面试例题15——分析代码写结果（使用sizeof计算含有虚函数的类对象的空间大小）。隐含的虚表指针成员（8字节）。

面试例题16——分析代码写结果（使用sizeof计算虚拟继承的类对象的空间大小）。编译器为虚拟继承的子类安插一个指向父类的指针，大小为4。

面试例题17——sizeof与strlen的区别（前者空间大小，后者计算字符串长度）。

面试例题18——sizeof用途（与存储分配和I/O系统的例程进行通信；查看某个类型的对象在内存中所占的单元字节；动态分配对象时，可以使系统知道要分配多少内存；便于一些类型的扩充；建议在涉及操作数字节大小时用sizeof来代替常量计算；如果操作数是函数中的数组形参或函数类型的形参，sizeof给出其指针的大小）。

面试例题19——找错（使用strlen()函数代替sizeof计算sizeof计算字符串长度）。

面试例题20——分析代码写结果（使用sizeof计算联合体的大小）。

面试例题21——选择题（#pragma pack的作用：设置对齐方式）。

面试例题22——为什么要引入内联函数（用它代替C中表达式形式的宏定义，解决程序中函数调用的效率问题）。

面试例题23——为什么inline能很好地取代表达式形式的预定义（没有了调用的开销，效率很高；仍旧是一个真正的函数；可以作为某个类的成员函数）。

面试例题24——内联函数使用的场合（设有或者保护成员的读写）。

面试例题25——为什么不把所有的函数都定义成内联函数（内联是以代码膨胀（复制）为代价，仅仅省去了函数调用的开销，从而提高函数的执行效率）。

面试例题26——内联函数与宏有什么区别（前者在编译时展开，宏在预编译时展开；在编译的时候内联函数可以直接被嵌入到目标代码中，而宏只是一个简单的文本替换；前者可以完成诸如类检测、语句是否正确等编译功能，宏就不具有这样的功能；宏不是函数，前者是函数；宏在定义时要小心处理宏参数，否则容易产生二义性，而前者不会出现二义性。

三、 引用和指针

面试例题1——分析代码写结果（一般变量引用：&）。

面试例题2——分析代码写结果（指针变量引用：&）。

面试例题3——分析代码找错误（变量引用）。

面试例题4——交换两个字符串（参数引用）。

面试例题5——程序差错（参数引用）。

面试例题6——程序差错（参数引用：常量引用类型在函数体内其值不能被修改；非常量引用不能作为常量的引用）。

面试例题7——指针与引用的区别（初始化要求不同，引用要求创建同时必须初始化，指针可以在定义后的任何地方重新赋值；可修改性不同，引用一旦被初始化，它就不能被另一个对象引用，而指针可以；不存在NULL引用；测试时，使用引用之前不需要测试它的合法性，而指针可以指向NULL，故必须经常进行测试；应用上，如果指向一个对象就不会改变指向，那么应该使用引用。）。

面试例题8——为什么引用比指针安全（不存在NULL引用）。

面试例题9——复杂指针的声明（首先从最里面的圆括号看起，然后往右看，再往左看）。

面试例题10——分析代码写结果（用指针赋值）。

面试例题11——分析代码写结果（指针加减操作）。

面试例题12——分析代码写结果（指针比较）。

面试例题13——分析代码找错误（内存访问违规）。

面试例题14——分析代码找错误（指针的隐式转换）。

面试例题15——指针常量和常量指针的区别（前者是指针形式的常量，不可改变地址的指针，但可以对它指向的内容修改；后者是常量形式的指针，即常量指针是指向常量的一个指针，所指向的地址的内容不能改变。）。

面试例题16——同15。

面试例题17——同15。

面试例题18——this指针的正确叙述（类的非静态成员函数才有this指针）。

面试例题19——同18。

面试例题20——指针数组和数组指针（前者表示数组的元素是指针形式，后者表示指向数组的指针。）。

面试例题21——同20。

面试例题22——函数指针和指针函数（指针函数是指带指针的函数，即本质是一个函数，并且返回的是某一类型的指针。函数指针是指向函数的指针变量。）。

面试例题23——数组指针和函数指针的定义。

面试例题24——各种指针的定义（函数指针、函数返回指针、const指针、指向const的指针、指向const的const指针）。

面试例题25——代码改错（函数指针的使用）。

面试例题26——分析代码写结果（函数指针的使用）。

面试例题27——typedef用于函数指针定义（使用typedef自定义数据类型）。

面试例题28——“野指针”是什么（不是NULL指针，是指向“垃圾”内存的指针。成因：指针变量没有初始化；指针p被free或者delete之后，没有置为NULL。）。

面试例题29——分析代码差错（“野指针”的危害：程序崩溃）。

面试例题30——malloc/free和new/delete（前者是库函数而不是运算符，不能满足动态对象的要求，不能够把执行构造函数和析构函数的任务强加给它）。

面试例题31——程序改错（“野指针”，即指针的初始化）。

面试例题32——各种内存分配和释放的函数的联系和区别：malloc、calloc、realloc、free等。调用格式如下：

          (类型*) malloc (size); 长度为size的内存。

          (类型*) calloc(n, size); 长度为size的n块内存。

          (类型*) realloc(*p, size); 将p的长度增大到size。

          free(void *p); 释放。

面试例题33——程序找错（动态内存的传递）。

面试例题34——程序分析（动态内存的传递：在C中采用指向指针的指针解决动态内存不能传递的问题；在C++中采用传递指针的引用解决；也可使用函数返回值来传递动态内存。）。

面试例题35——比较分析两个代码段的输出（动态内存的传递）。

面试例题36——程序差错（“野指针”用于变量值的互换）。

面试例题37——内存的分配方式（静态存储区（如全局变量）、栈（效率很高，但是分配的村内存容量有限）、堆（亦称动态内存分配））。

面试例题38——句柄（用来标识项目的，这些项目包括：模块module；任务task；实例instance；文件file；内存块block of memory；菜单menu；控制control；字体font；资源resource（包括图标icon、光标cursor、字符串string等）；GDI对象GDI object（包括位图bitmap、画刷brush、元文件metafile、调色板palette、画笔pen、区域region以及设备描述表device context）。程序执行顺序：句柄地址（稳定）→记载对象在内存中的地址→对象在内存中的地址（不稳定）→实际对象。）。

面试例题39——指针和句柄的区别（句柄所指可以是一个复杂的结构，并且可以与系统有关；指针也可以指向一个复杂的结构，但是通常是由用户定义的，所以必要的工作要由用户完成，特别删除部分的工作。）。

四、 字符串

面试例题1——使用库函数将数字转换为字符串：itoa()为整型；ltoa()为长整型；ulota()为无符号长整型；gcvt()为浮点数，取四舍五入；ecvt()为双精度浮点型，结果中不包含十进制小数点；fcvt()指定位数为转换精度，其余同ecvt()。

面试例题2——不适用库函数将数字转换为字符串：ASCII码。

面试例题3——使用库函数将字符串转换为数字：atof双精度浮点型、atoi整型、atol长整型、strtod双精度浮点数、strtol长整型、strtoul无符号长整型。后面三者不同于前面的区别在于：它们报告不能转换的所有剩余字符。

面试例题4——不使用库函数将字符串转换为数字：ASCII码。

面试例题5——编程实现strcpy函数。

面试例题6——编程实现memcpy函数。

面试例题7——strcpy和memcpy的区别：复制的内容不同，前者只能复制字符串，后者可以复制任意内容，例如字符数组、整型、结构体、类等；复制的方法不同，前者不需要指定长度，遇到字符串结束符“\0”便结束，后者需要给定复制长度的参数；用途不同。

面试例题8——该错（数组越界）。

面试例题9——分析程序（数组越界）。

面试例题10——分析程序（打印操作可能产生数组越界）。

面试例题11——编程实现字符串的长度检测（strlen函数）。

面试例题12——编程实现字符串中子串的查找（strstr函数）。

面试例题13——编程实现字符串中各单词的翻转（查找空格和字符串的结束符号）。

面试例题14——编程判断字符串是否为回文（先判断长度，再比较）。

面试例题15——编程实现strcmp库函数（判断字符串相等）。

面试例题16——编程查找两个字符串的最大公共子串。

面试例题17——不能使用printf，将十进制数以二进制和十六进制的形式输出（用字符串表示十进制数）。

面试例题18——在字符串中，插入字符统计的个数。

面试例题19——字符串编码例题。

面试例题20——反转字符串，但其指定的子串不反转（编写函数对输入字符串和子串进行反转，然后在输入字符串的反转中查找子串的反转）。

面试例题21——编写字符串反转函数strrev（法一：遍历字符串，将第一个字符和最后一个字符交换，再往中间循环；法二：通过数组下标的方式访问字符串，也可以用指针直接操作；法三：异或运算符；法四：+和-运算符。）。

面试例题22——编程实现任意长度的两个正整数相加。

面试例题23——编程实现字符串循环右移。

   面试例题24——从字符串的指定位置开始，删除其指定长度字符。

   面试例题25——字符串的排序及交换。

面试例题26——编程实现删除字符串中所有指定的字符。

面试例题27——分析代码（使用strcat函数连接字符串）。

面试例题28——编程实现库函数strcat。

面试例题29——计算含有汉字的字符串的长度。

面试例题30——找出01字符串中0和1连续出现的最大次数。

面试例题31——实现字符串的替换。

五、 位运算与嵌入式编程

面试例题1——分析代码写结果（位制转换：使用printf输出不同类型变量）。

面试例题2——分析代码写出结果（位运算：左移<<（相当于乘法）和右移>>（相当于除法））。

面试例题3——设置或清除特定的位（使用“&”和“|”位操作符）。

面试例题4——计算一字节里有多少位被置1。

面试例题5——位运算改错（位运算符和逻辑运算符）。

面试例题6——运用位运算交换a、b两个数。

面试例题7——列举并解释C++中的四种运算符转化，说明它们的不同点（const_cast、dynamic_cast、reinterpret_cast和static_cast）。

面试例题8——用#define声明一个常数，用以表明一年中有多少秒。如：

   #define SECONDS_PER_YEAR(60*60*24*365)UL

面试例题9——用C语言写死循环（while(1){}或for(;;){}或loop:…goto loop;）。

面试例题10——如果访问特定位置的内存。

面试例题11——对中断服务代码的评论（_interrupt）。

面试例题12——分析代码写结果（整数的自动转换）。

面试例题13——关键字static的作用。

面试例题14——关键字volatile的作用：定义为volatile的变量可能会被意想不到地改变，这样，编译器就不会去假设这个变量的值。几个例子：并行设备的硬件寄存器（如状态寄存器）；一个中断服务子程序中会访问到的非自动变量（Non-automatic variables）；多线程应用中被几个任务共享的变量。

面试例题15——判断处理器使用Big_endian还是Little_endian模式存储数据（若是前者，返回0；若是后者，返回1。）。

面试例题16——评价代码片断（处理器字长）。

六、 C++面向对象

面试例题1——面向对象技术的基本概率（类（抽象、继承、封装、重载、多态）、对象、消息）。

面试例题2——判断题（类的基本概念）。

面试例题3——选C相比，C++的改进（面向对象）。

面试例题4——class和struct的区别（在C中，struct只是作为一种复杂数据类型定义，不能用于面向对象编程；C++中对于成员访问权限及继承方式，class中默认的是private，而struct中则是public。class还可以用于表示模板类型，struct则不行。）。

面试例题5——改错（C++类对象的声明，与构造函数相匹配）。

面试例题6——分析代码写结果（C++类成员的访问）。

面试例题7——找错（类成员的初始化）。

面试例题8­——分析代码写结果（静态成员变量的使用：是该类类型的全局变量。静态成员只是一个，由该类类型的所有对象共享访问）。

面试例题9——与全局对象相比，使用静态数据成员有什么优势（静态数据成员没有进入程序的全局名字空间，因此不存在程序中其他全局名字冲突的问题。使用静态成员可以隐藏信息，因此静态成员可以是private成员，而全局对象不能。）。

面试例题10——有哪几种情况只能初始化列表（initialization list），而不能用赋值（assignment）：const和reference类型成员变量只能被初始化而不能被赋值操作；类的构造函数需要调用其基类的构造函数。

面试例题11——代码改错（静态成员的使用）。

面试例题12——选择题（对静态数据成员的正确描述：不受private控制符作用，可以直接用类名调用。）。

面试例题13——main函数执行以前，会执行什么代码（全局对象的构造函数）。

面试例题14——C++中的空类，默认情况下会产生哪些类成员函数：默认构造函数和复制构造函数，它们被用于类的对象的构造过程；析构函数，它被用于类的对象的析构过程；赋值函数，它被用于同类的对象间的赋值过程；取值运算，当对类的对象进行取地址（&）时，此函数被调用。

面试例题15——构造函数和析构函数是否可以被重载（前者可以，后者不可以）。

面试例题16——分析代码（重载构造函数的调用）。

面试例题17——分析代码（构造函数的使用）。

面试例题18——构造函数explicit与普通构造函数的区别（前者只能被显式调用，后者能够被隐式调用）。

面试例题19——分析代码（explicit构造函数的使用）。

面试例题20——C++中虚析构函数的作用（实现多态。只有当一个类被用来作为基类的时候，才会把析构函数写成虚函数。）。

面试例题21——分析代码写结果（析构函数的执行顺序：与构造函数相反）。

面试例题22——拷贝构造函数（复制构造函数）何时调用：一个对象以值传递的方式传入函数体；一个对象以值传递的方式从函数返回；一个对象需要通过另外一个对象进行初始化。浅拷贝是让新旧两个对象指向同一个外部的内容，而深拷贝是指为新对象制作了外部对象的独立复制。

面试例题23——什么时候编译器会生成默认的拷贝构造函数：用户没有定义拷贝构造函数而在代码中使用到了拷贝构造函数时，编译器就会生成默认的拷贝构造函数。但如果用户定义了拷贝构造函数，编译器就不会生成默认的copy constructor。

面试例题24——写一个继承类的复制函数的原则是：使用基类的拷贝构造函数。

面试例题25——拷贝构造函数与赋值函数的区别：前者是一个对象初始化一块内存区域，这块内存就是新对象的内存区，后者是对于一个已经被初始化的对象来进行赋值操作。前者大多数情况下是复制，后者则是引用对象。实现不一样，前者首先是一个构造函数，它调用的时候是通过参数的对象初始化一个对象，而后者则是把一个新的对象赋值给一个原有的对象。

面试例题26——编写类string的构造函数、析构函数和赋值函数。

面试例题27——分析代码写结果（C++类各成员函数关系：构造、析构和赋值）。

面试例题28——分析代码写结果（C++类的临时对象）。

面试例题29——分析代码写输出（拷贝构造函数和析构函数）。

面试例题30——分析代码写结果（C++静态成员和临时对象）。

面试例题31——什么是临时对象？在什么情况下产生？（仅使用一小段时间的变量称为临时变量，应避免它的使用，因为会影响程序的效率。）。

面试例题32——什么是函数重载（用来描述同名函数具有相同或者相似功能，但数据类型或者是参数不同的函数管理操作）。C++支持而C不支持。

面试例题33——函数重载的正确声明。

面试例题34——重载与覆写的区别（重载overriding是指子类改写父类的方法；覆写overloading是指同一个函数的不同版本之间参数不同。）重载特征：方法名必须相同；参数列表必须不相同；返回值类型可以不相同。覆写特征：只有虚方法和抽象方法才能够被覆写；具有相同的函数名；具有相同的参数列表；具有相同的返回值类型。

面试例题35——重载“=”和“+”运算符。形式：type operator @ (arglist)

面试例题36——各类运算符重载函数的编写（“<”、“>”、“==”、“!=”、“+=­­­­­”以及输入输出运算符）。

面试例题37——分析代码写输出（new操作符重载的使用）。

七、 C++继承与多态

面试例题1——C++类继承的三种关系（public、private和protected）。

面试例题2——同1。

面试例题3——同1。

面试例题4——私有继承作用：编译器一般不会将派生类对象转换成基类对象；从私有基类继承而来的成员成为派生类的私有成员。

面试例题5——私有继承和组合的相同点和不同点：它们都可以表示“hasa”（即有一个）关系；但私有继承中派生类访问基类的protected成员，并且可以重写基类的虚拟函数（甚至当基类是抽象类时），组合不具有这些功能。选择它们的原则为尽可能使用组合，万不得已时使用私有继承。

面试例题6——多态：编译时的多态性（重载）、运行时的多态性（虚成员）。

面试例题7——虚函数如何实现：如果一个类中含有虚函数，则系统会为这个类分配一个指针成员指向一张虚函数表（vtbl），表中每一项指向一个虚函数的地址，实现上就是一个函数指针的数组。虚函数表既有继承性又有多态性。，每个派生类的虚函数表继承了它各个基类的虚函数表。在类对象的内存分布中，首先是虚函数表指针，然后才是对象数据。

面试例题8——分析代码写输出（构造函数调用虚函数：虚函数不会向下匹配到派生类，而是直接执行基类的函数。）。

面试例题9­­——分析代码写输出（虚函数的作用）。

面试例题10——分析代码写结果（虚函数）。

面试例题11——选择题（虚函数相关）。

面试例题12——多重继承的优点在于对象可以调用多个基类中的接口；缺点是如果派生类所继承的多个基类有相同的基类，而派生类对象需要调用这个祖先类的接口方法，容易产生二义性（解决方法：加上全局符确定调用复制；使用虚拟继承。）。

面试例题13——分析代码找错（多重继承中的二义性）。

面试例题14——多重继承二义性的消除（虚拟继承）。

面试例题15——分析代码写结果（多重继承和虚拟继承）。

面试例题16——为什么要引入抽象基类和纯虚函数：为了方便使用多态特性；在很多情况下，基类本身生成对象时不合情理的。纯虚函数在基类中没有定义，必须在子类中加以实现。如果基类含有一个或多个纯虚函数，那么它就属于抽象基类，不能被实例化。

面试例题17——虚函数与纯虚函数的区别：（1）类里声明虚函数的作用是为了能让这个函数在它的子类里面被覆盖，这样编译器就可以使用后期绑定来达到多态了。纯虚函数只是一个接口，是个函数的声明而已，它要留到子类中去实现。（2）虚函数在子类里面也可以不重载，但纯虚函数必须在子类中去实现。（3）虚函数的类用于“实作继承”，也就是说继承接口的同时也继承了父类的实现。纯虚函数的类用于“界面继承”，即纯虚函数关注的是接口的统一性，实现由子类完成。

面试例题18——程序找错（抽象类不能实例化）。

面试例题19——应用题（用面向对象的方法进行设计）。

面试例题20——什么是COM（组件对象模型Component Object Model）：通过定义二进制标准解决一下问题，即DLLsf是针对C接口写的，它们只能被C或理解C调用规范的语言使用，由编程语言实现共享代码，而不是由动态链接库本身实现。简单地说，它定义了一种二进制标准，使得任何编程语言都能存取它所编写的模块。

面试例题21——COM组件是一种商业标准，其商业品牌被称为ActiveX。组件的特点有：组件与开发工具语言无关；通过接口有效保证了组件的复用性；组件运行效率高，便于使用和管理。

面试例题22——如何理解COM对象和接口：一个对象实现一个接口，一个接口定义了接口的成员函数、调用方法、返回类型、它们的参数类型和参数数量，以及这些函数要干什么。接口的实现就是程序员在一个接口定义上提供的执行相关动作的代码。但是，在COM模型中，对象本身对于客户来说是不可见的，客户请求服务时，只能通过接口实现，每个接口都由一个128位的全局标识符（GUID，Globally unique Identifier）来标识。与接口类似，每个对象也用一个GUID来标识，称为CLSID（class ID）。继承在COM里并不意味着代码的重用。如果一个接口由另一个接口继承的话，它就包含了另一个接口定义的所有方法。管理实现COM对象的IUnknown::QueryInterface方法的3个主要规则：对象必须要有一个标识符；对象实例的接口集合必须是静态的；在对象中从任何其他的接口查询此接口都应该成功。

面试例题23——ActiveX是微软提出的一套基于COM的构件技术标准，实际上是对象嵌入与链接（OLE）的新版本。DCOM（Distribute COM）是基于分布式环境下的COM，它实现了COM对象与远程计算机上的另一个对象之间的相互交互。

面试例题24——DLL HELL：是指DLL（动态链接库）版本冲突的问题。

补充：虚函数表——主要是一个类的虚函数的地址，这张表解决了继承、覆盖的问题，其内容真实反映了实际函数。对于一个单继承的类，如果它有虚拟函数，则只有一张虚函数表。对于多重继承的类，它可能有多张虚函数表。

八、 数据结构

面试例题1——编程实现单链表的建立（head头节点，可作为指针使用）。

面试例题2——编程实现单链表的测长（head指针，如head->next表示先前走一步）。

面试例题3——编程实现单链表的打印（head指针，同上）。

面试例题4——编程实现单链表的节点查找（head->next）。

面试例题5——编程实现单链表的节点插入（链表首部、中间和尾端三种情况）。

面试例题6——编程实现单链表的节点删除。

面试例题7——编程实现单链表的逆转。

面试例题8——寻找单链表的中间元素（一遍扫描）。

面试例题9——单链表的正向排序。

面试例题10——判断单链表是否存在环形链表问题：假设两个指针为p1和p2，每循环一次p1->next，p2->next->next，知道p2=NULL或者p2->next=NULL或者p1==p2时循环结束。如果相等则说明存在环。

面试例题11——有序单链表的合并（非递归方法：把较短的插入到较长的即可；递归方法：比较两个链表的第一个元素，把结果链表的头节点指向元素小的那个链表的第一个节点，再对剩下的递归调用此过程。）。

面试例题12——约瑟夫问题：编号为1~N的N个人按顺时候围坐一圈，没人持有一个正整数，开始任选一个作为报数的上限值M，从第一个人按顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的正整数作为新的M值，从下一个人开始重新报数，如此下去，直至所有的人都出列为止，试编程实现。（循环链表）

面试例题13——建立以个双向链表（节点数据、前驱指针、后继指针）。

面试例题14——双向链表的测长（head->right）。

面试例题15——双向链表的打印（head->right，head->data）。

面试例题16——双向链表的节点查找（right指针遍历，直至找到数据为data的节点）。

面试例题17——双向链表的节点插入（插入位置在中间时，需要把节点的原后继节点的前驱指针指向新插入的节点，在链表末尾插入则不需要。）。

面试例题18——双向链表的节点删除（删除头结点、中间节点和末节点）。

面试例题19——实现有序双向循环链表的插入操作。

面试例题20——删除两个双向循环链表的相同节点。

面试例题21——编程实现队列的入队、出队、测长、打印。队列是可在对头front删除而在队尾rear插入的数据结构，先进先出（FIFO）。

面试例题22——栈在栈顶top插入、删除，另一端称为栈底bottom。后进先出（LIFO）。队列和栈的区别：操作的名称、可操作的方向、操作的方法都不相同。

面试例题23——队列和栈的使用。

面试例题24——同22。

面试例题25——使用队列实现栈。

面试例题26——栈的使用，同22。

面试例题27——用C++实现一个二叉排序树，完成创建节点、插入节点、删除节点、查找节点等功能。非递归方法插入节点：创建节点；查找新建节点的插入位置，把新节点插入到目标节点的正确位置。如果当前节点的数据值小于要插入的data，则应该在的左子树插入；反之则应该在它的右子树插入。

面试例题28——使用递归与非递归方法实现中序遍历：左根右。非递归：先将根节点入栈，遍历左子树；遍历完左子树返回时，根节点出栈，并打印节点数据；再中序遍历右子树。

面试例题29——使用递归与非递归方法实现先序遍历：根左右。非递归：打印根节点数据；把根节点的right（右子节点）入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为right，出栈，遍历以该指针为根的子树。

面试例题30——使用递归与非递归方法实现后序遍历：左右根。后序遍历要求在遍历完左右子树后，再访问根节点，需要判断根节点的左右子树是否均遍历过。

面试例题31——编写层次遍历二叉树的算法：一层一层地进行遍历，使用队列。

面试例题32——编写判断给定二叉树是否为二叉排序树的程序：中序遍历。

九、 排序

1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子数组中的适当位置，直到全部记录插入完成为止。分为直接插入排序（稳定）和希尔（Shell）排序（不稳定）。

面试例题1——编程实现直接插入排序：把数组分为两个区，即前面的有序区和后面的无序区，再依次把无序区的元素插入到有序区即可。编程思想：在当前有序区R[1,…,i-1]中查找R[i]的正确位置k（1<=k<=i-1）；将R[k,…,i-1]中的记录均后移一位，腾出k位置上的空间插入R[i]。

面试例题2——编程实现直接Shell排序：先将要排序的一组数按某个增量d分成若干组，对每组中全部元素进行排序，然后用一个较小的增量对它进行再次分组，并对新组进行排序。当增量减到1时，整个要排序的数被分为一组，排序完成。分组插入方法。

2、交换排序：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序为止。其主要排序方法有冒泡排序和快速排序。

面试例题3——编程实现直接冒泡排序：第一次扫描最小的记录被放在最前位置；第二次是次小的记录；依次类推，直到排序完成。

面试例题4——编程实现快速排序：通常称为分治法（Divide-and-Conquer Method），将原问题分解为若干个规模更小但结构与原问题相似的子问题，递归地解答这些子问题，然后将这些子问题的解组合为原问题的解。基本思想——分解、求解、组合。

3、选择排序：每一次从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。

面试例题5——直接选择排序：第一次排序把最小的元素与第一个元素交换；第二次次小与第二个交换；以此类推，直到排序完成。

面试例题6——编程实现堆排序：有两种堆，即小根堆（所有子节点都大于其父节点）和大根堆（所有子节点都小于父节点）。堆实质上是满足如下性质的完全二叉树：树中任意非叶节点的关键字均不大于（或不小于）其左右子节点（若存在）的关键字。

4、归并排序：利用“归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。两种实现方法：自底向上、自顶向下（分解、求解、组合）。

面试例题7——归并排序算法的实现（使用自顶向下的方法）。

5、基数排序：是箱排序的改进和推广。箱排序也称桶排序（Bucket Sort），其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0],R[1],…,R[n-1]，把关键字等于k的记录全都装入到第k个箱子里（分配），然后按序号依次将各非空的箱子首尾连接起来（收集）。有两种排序方法：最高位优先MSD（Most Significant Digit first）和最低位优先（Least Significant Digit first）。最典型的是LSD排序方法，其基本思想是：从低位到高位依次对数据进行箱排序。

面试例题8——使用基数排序对整数进行排序。

6、各种排序方法比较。

按平均时间分类：

时间复杂度

算法

O(n^2)

简单排序：直接插入、直接选择和冒泡排序

O(nlogn)

快速、堆和归并排序

O(n1+&)

&是介于0和1之间的常数，例如希尔排序

O(n)

桶、箱和基数排序

O(nlog2n)

归并排序、快速排序的最理想情况

比较结果：简单排序中直接插入最佳，快速排序最快，当文件为正序时，直接插入和冒泡最好。

选择排序方法的影响因素：待排序的记录数目n；记录的大小（规模）；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和空间复杂度。

面试例题9——各种排序算法速度的性能比较。

面试例题10——各排序算法的时间复杂度比较。