1、C++内置类型
包括基本类型和复合类型。
基本类型包括整数和浮点数。
复合类型包括数组、字符串、指针、引用、结构体和共用体等。
2、内存分区（5个）
1）堆：动态内存区，由程序员手动分配和释放，不同于数据结构的堆，分配方式类似链表。由malloc或new分配，由free或delete释放，最好手动释放，如果程序员不释放且运行期间不出错，则程序结束后由系统释放。
2）栈：编译器自动分配和释放，存放函数的参数值、局部变量等，操作方式类似数据结构的栈。
3）全局静态存储区：存放全局变量和静态变量，包括DATA段和BSS段，初始化过的放在DATA中，否则放在BSS中。
4）文字常量区：存放常量字符串。
5）程序代码区：存放函数体的二进制代码。
详见P2
一、数组
1、没有引用数组，因为引用不能赋值。
2、C风格字符串包括两种，字符串常量（末尾自动添加空字符’\0’）和以’\0’结尾的字符数组。
3、C++规定，在声明和初始化一个二维数组时，如果对所有元素赋值，则可省略行数。
4、顺序表插入、删除和查找算法的平均时间是O（n）。
5、数组指针和指针数组。
习题14 15 16 17 18
二、字符串
1、strcpy和memcpy的区别，前者参数是char，后者是void，表示后者可用于任何类型，范围比strcpy广。
a、复制的内容不同。strcpy只能复制字符串，而memcpy可以复制任意内容。strcpy只用于字符串复制，并且它不仅复制字符串内容，还会复制字符串的结束符。memcpy对于需要复制的内容没有限制，因此用途更广。
b、复制的方法不同。strcpy不需要指定长度，它遇到被复制字符的串结束符‘\0’才结束，容易溢出。memcpy根据第三个参数决定复制的长度。
c、用途不同，strcpy复制字符串，其他类型一般用memcpy。
2、长度为M的字符串中查找长度为N的子串，最少时间复杂度O（M+N）。（利用KMP算法）
3、循环移位包串，第一种方法取模，第二种就是把m变成mm，再找n子串。
4、判断某字符串是不是包含什么字符之类的问题，可转为素数相乘。
5、字符串查找类题目可以联想到素数和桶排序，有时会解决问题。
6、memset将s中第三个参数表示的前n个字节用ch替换，作用是在一段内存块中填充某个给定的值，它是对较大结构体或数组清零的最快方法。
三、结构体
1、sizeof是运算符不是函数，它的计算发生在编译时刻，所以可以被当做常量表达式使用，且会忽略括号中的各种运算，如sizeof（a++），“++”并不会执行。若对一个函数调用使用，则求到的是函数返回类型的值，不可以对函数使用，而且函数并不会被调用。
2、不可以用sizeof的：函数、返回void的函数调用、位域成员。
3、strlen不包括‘\0’，sizeof包括。
4、大小端对位域影响，自己的理解：
首先2个字节8位是一个划分单元。
大端下：对每个八位，按照位域成员声明顺序从左往右填入bit，不够的留到下一个八位中继续按照从左往右填。
小端下：对每个八位，按照位域成员声明顺序从右往左填入成员bit，以此类推。
（不知道对不对，总之根据题目上这么理解似乎正确。）
5、结构体占内存空间大小：P51.
6、结构体内函数和类型重定义不占字节。
四、运算符及其优先级
1、亦或运算可以用来找成对数组中不成对的那个数。
2、~运算符的优先级>移位运算符优先级>与或异或运算符的优先级
运算符优先级记忆规则：
a、括号、下标，->和.运算级别最高。
b、单目比双目高，算术双目的比其他双目的高
c、移位运算符高于关系运算符，关系运算符高于按位运算，按位运算高于逻辑运算。
d、三目的只有一个条件运算，低于逻辑运算
e、赋值运算符仅比逗号运算符高，且所有赋值运算符优先级相同，结合访问位从右到左。
五、C预处理器、作用域、static、const以及内存管理
预处理主要有三个方面的内容：
a、宏定义与宏替换
b、文件包含
c、条件编译
1、宏定义和宏替换：
宏名一般大写，宏名和参数括号间不能有空格，末尾不加分号
宏替换只做替换，不做语法检查，不做计算，不做表达式求解；
宏替换在编译前进行，不分配内存，函数调用在编译后程序运行时进行，并且分配；
函数只有一个返回值，利用宏则可以设法得到多个值
宏替换使源程序变长，函数调用不会
宏替换不占运行时间，只占编译时间，函数调用占运行时间。
尽量少用宏，用const、enum和inline替换。
2、static的作用（不考虑类）：a隐藏，b把变量默认初始化为0，c保持局部变量内容的持久。
类中的作用：属于一个类但不属于此类中任何特定对象的变量和函数。
static数据成员必须在类定义体的外部定义。
static成员函数不能被声明为const、虚函数、volatile。
3、const
const和#define相比的好处：
1）const常量有数据类型，而宏常量没有数据类型，所以前者可以有类型安全检查。
2）使用const会产生更小的目标代码；
3）const还会进行常量折叠。
常量数据成员必须在构造函数的成员初始化列表中初始化。
c中的const意思是一个不能被改变的普通变量，纵使占用存储，不能把const视为一个编译期间的常量。
const的使用场景：
a常量
b指针和const修饰符
c修饰函数参数和返回值
d类中。const成员函数、const数据成员。
static、const以及static const成员变量初始化的不同。
static必须在类内声明，类外定义，定义时不能标为static。
const数据成员的初始化只能在类的构造函数初始值列表中进行，const数据成员只在某个对象生存期内是常量，对整个类而言却是可变的。
static const类内声明，类外定义，定义时加const不加static。
4、malloc/free和new/delete的异同（p104）
相同点：两组都是用来动态分配/释放内存的。
1）操作对象不同点：malloc和free是库函数，而new和delete是运算符，后者两个可以执行构造函数和析构函数。
operator new的执行流程：先分配足够大的原始空间，然后调用该类型的一个构造函数，最后返回指针。
operator delete的执行流程：先调用析构函数，再回收空间。
2）用法不同
malloc原型返回void*，所以要进行显式转换，它只关心分配的字节数，不关心类型。
malloc手工计算字节数，new自动分配。
new类型安全，而malloc不是。
malloc和free需要包含库文件，而new和delete不需要。
六、函数
1、使用无参数构造函数的时候不要加()，不然会被看做是某个函数的声明，如：
Foo b();
本意是构造Foo的一个对象b，但却被看做是一个函数声明，应改为 Foo b;
2、c++中调用被c编译过的函数，为什么要加extern “c”
c++是一种面向对象的编程语言，为了支持重载，编译器会对函数名字进行一些处理。而在c中编译就只是简单函数名而已，两者处理函数名的方式是不一样的。加了extern “c”就说明函数是用c编译器编译的，请用c的方式链接它们，否则链接会错。
七、指针和引用
1、函数返回void时表示返回一个特殊的指针，并不是没有返回值。
void指针的操作：
和另一个指针进行比较。
向函数传递void指针或从函数函数void指针。
给另一个void*指针赋值。
2、具有函数类型的形参所对应的的实参将被自动转化为指向响应函数类型的指针，然而当返回类型是函数时，却不会转换成对应的指针。
3、引用和指针的区别
虽然引用和指针都可以间接访问另一个变量，但它们之间存在重要区别。
1）引用不能为空，当引用被创建时，必须被初始化，指针则可以为空。
2）一旦一个引用被初始化为指向某一对象，它就不能改变指向其他对象。指针可以。
3）没有NULL引用。
4）sizeof运算符对引用是求它所指对象大小，而对指针就是求指针本身大小。
5）给引用赋值就是修改它指向的那个对象的值，并不是改变引用所指的对象。
6）引用没有解引用，而指针需要解引用。
7）动态分配的对象或内存必须使用指针。
8）&操作符对引用是取它所指对象的地址，而对指针就是求指针的地址。
4、引用类型类数据成员的初始化必须在初始化列表中，而且必须手动写构造函数。
5、野指针。
野指针是指向不可用内存的指针。
下列三种情况会产生野指针：
a当一个指针被初始化时不会自动成为NULl指针，而是一个野指针，默认值是随机的。
b当指针被free或delete后未把指针置为NULL，此时是野指针。
c指针操作超越变量作用范围时也是野指针。
八、类
1、在c++中，成员变量的初始化顺序与变量在类中声明的顺序相同，与初始化时的顺序无关。
2、没有默认构造函数的类类型成员、const成员和引用成员必须在初始值列表里初始化。
3、深复制和浅复制。
浅复制：被复制的对象的所有变量都和原来对象的值相同，而所有的对其他对象的引用仍然指向原来的对象。浅复制仅复制对象，而不复制所引用的对象。
深复制：相反，深复制把所有对象以及引用的对象都复制了一遍。
浅复制可能导致运行时错误。
4、虚基类的构造函数最先调用。
5、复制构造函数只在对象实例化的时候才调用，没有返回值。
赋值运算符则在一个现存对象被赋值时调用，有返回值。
6、new operator和operator new不同。
可以重载的是operator new而不是new operator。
即不能重定义new和delete表达式的行为，可以重载的是全局函数operator new和operator delete。
new表达式行为中调用operator new分配空间，然后调用合适的构造函数。
delete表达式先析构，在调用合适的operator delete释放空间。
九、面向对象编程。
1、公有继承下，派生类的对象、对象指针、对象引用可以赋值给基类的对象、对象指针、对象引用，这是隐式转化，保护继承和私有继承没有。
公有继承下，基类的对象指针、对象引用不可以隐式转换成派生类的指针和引用，但是可以显式转换（强制转换）过去。p157
2、类型转换函数的作用是将一个类的对象转换为另一个类型的数据。
转换函数必须是成员函数不能是友元，不能指定返回类型，但在函数体内必须用return以传值的方式返回一个目标类型的变量；转换函数不能有参数。
operator 类型(){return 类型的值；}
转换构造函数：可以用单个实参来调用的构造函数定义从形参类型到该类类型的一个隐式转换。
静态动态性包括函数重载和运算符重载，动态多态性包括虚函数。
3、非C++内建类型A和B，三种情况下B能隐式转换成A。
B公有继承自A
B中有类型转换函数转换成A
A实现了非explicit的参数为B的构造函数。
4、不能做虚函数的有哪些。
非成员函数、静态成员函数、构造函数、友元函数。
而内联成员函数和赋值操作符函数声明为虚函数也无意义。
5、C++对象模型p167，重要。
简单来说，static成员数据和函数都在全局静态区，非static数据成员才在对象内部，不是虚的成员函数也在对象外部。
虚函数在对象内部留一个pvtr指针，指向一个虚函数表，虚函数表里存放虚函数和type_info.
6、抽象类不可以定义对象，但可以作为指针或引用类型使用。
7、仅当类型之间存在隐式转换的时候（类间下行转换除外），static_cast才合法。
reinterpret_cast代替圆括号的显式转换，强制转换。
dynami_cast将基类指针或引用安全转换为派生类指针或引用，做两件事，检查是否可以转换，若有效才真正转换。
十、分治法、动态规划与贪心算法
p196，开学后看下算法导论对应例题。
十一、
1、Catalan数p211
h(n)=h(0)h(n-1)+h(1)h(n-2)+…+h(n-1)*h(0) h(0)=1
2、求二叉树中节点之间的最大距离。
3、树中路径上所有节点之和等于给定值。p223
4、红黑树是一种特殊的二叉搜索树，满足以下条件：
节点不是红就是黑。
根节点是黑。
如果节点是红，其子节点必须是黑。
任一节点至null的任何路径，所含之黑节点数必须相同。
5、判断树是不是平衡树p227
6、并查集p231
第十四章、图
第十五章、排序
1、插入排序包括直接插入排序和希尔排序。
直接插入排序时间复杂度n2，空间复杂度1，最好情况下表中元素已经有序，此时每插入一个元素都只需要比较一次而不用移动，因为时间复杂度是n，是稳定的。
希尔排序的时间复杂度不确定，空间复杂度是1，不稳定。
2、交换排序
冒泡排序，时间复杂n2，空间复制1，稳定，最好情况下时间复杂n。
快速排序是所有内部排序中平均性能最好的算法，空间复杂度最坏n，平均logn，时间复杂度最坏n2但很少见，最好nlogn，不稳定。
快速排序两种划分方法p253
3、选择排序时间复杂度始终n2.
元素间的比较次数和原始序列无关，都是n(n-1)/2.
4、建堆的时间复杂度为n。
空间复杂度1，时间复杂度nlogn。
5、二路归并排序（递归分支，merge）
空间n，时间nlogn。
第十六章：查找
1、后缀数组
2、键树又称数字查找树，用树的孩子-兄弟链表来表示键树。
用多重链表表示键树，则树的每个节点中包含d个指针域，此时又称Trie树
3、分布式存储方式
普通集群：把固定的key映射到固定的节点上，节点只存放各自key的数据。查找时需要遍历，查找速度慢。
hash集群：更迭慢，需要重新扫描计算一次所有节点。
一致性hash
4、处理海量数据大文件
分治——hash映射到不同块中，对每个块再分别处理。
最小k个数p261
布隆过滤器：
大小为m，样本数量为n，失误率为p
m=-(nlnp)/(ln2)2
k=ln2(m/n)
p=(1-e(-nk/m))k
计网
1、ping使用ICMP协议。
网络层协议：IP 、IPX 、ICMP、IGMP、ARP、RARP、OSPF
传输层协议：TCP、UDP、SCTP
应用层协议：RIP、TELNET、TFP、HTTP、SNMP
TCP
a、TCP是一种面向连接的协议，提供客户与服务器的连接
b、tcp提供可靠性，当使用tcp向另一端发送数据时，它要求对端返回一个确认。如果没有收到确认，tcp自动重传数据并等待更长时间。在数次重传失败后，tcp才放弃。
c、tcp通过给发送数据的每一个字节关联一个序列号进行排序。udp提供不可靠的数据报传送，不提供确认、序列号、超时重传等机制。
d、tcp提供流量控制，而udp不提供。
e、tcp的连接是全双工的，udp的也可以是全双工的。
和udp的主要区别在于udp不一定提供可靠的数据传输，但是udp对系统资源要求少、实时性好、网络开销小。
2、终止tcp连接通常调用close，但是close有两个弊端，可用shutdown来避免。
close函数把套接字的引用计数减1，仅在计数变为0时才关闭，而使用shutdown不管计数如何会直接激发正常终止序列。
close同时关闭读写，但有时候需要关闭写但仍然可以读，这个时候就可以用shutdown。
3、tcp七个定时器：连接建立定时器，重传定时器，延迟定时器，持续定时器，保活定时器，FIN_WAIT2定时器，TIME_WAIT定时器
为了提高ip数据报成功交付机会，在网络层使用icmp来使得主机可以报告差错或异常情况。
4、输入url后按下回车发生什么？
向dns服务器查询url对应的IP地址。
dns返回ip地址。
浏览器打开tcp连接，并向web服务器发送http请求。
若页面发生跳转，服务器以重定向响应，然后转到5，否则直接转6.
浏览器跟随重定向，再次发送http请求。
服务器处理请求，并返回html响应。
浏览器接受请求的页面源码。
浏览器开始渲染html。
浏览器发送嵌入到html中的对象请求。
浏览器进一步发送异步请求。
浏览器关闭tcp连接。
ping用来检查网络是否通畅
tracert路由跟踪
telnet网络测试，如测试80端口的web服务器是否正常
netstat监控tcp/ip的工具
操作系统
1、四个特征：并发、异步、共享、虚拟。
2、进程与线程的区别。p325
3、调度算法例题，p328例二。
4、死锁产生的必要条件：互斥、不剥夺、请求和保持、循环等待。
预防死锁：破坏四个条件之一
避免：银行家算法
检测及解除：剥夺资源、撤销进程、进程回退。
线程独有的：线程id、寄存器组的值、堆栈、错误返回码、信号屏蔽码、线程优先级
进程和线程的区别：
a、调度：引入线程后，线程是独立调度的基本单位，进程是拥有资源的基本单位拟。在同一进程中，线程的切换不会引起进程切换，不同进程中的线程切换会引起进程切换。
b、拥有资源：进程是拥有资源的基本单位，但是线程可以共享其隶属进程的系统资源。
c、并发，进程可以并发，线程也可以并发，而且线程并发性更高，提高系统吞吐量。
d、系统开销：创建和撤销进程时，系统都要为之分配或回收资源，因为付出的开销远远大于创建或撤销线程的开销。进程切换的开销也比线程大。另外，同一进程后的多个线程共享进程的地址空间，因此及这些线程间的同步通信比较容易实现，无需操作系统干预。
e、进程的地址空间相互独立，统一进程的各线程间共享进程的资源，某进程内的线程对其他进程不可见。
f、通信方面，进程间通信需要借助操作系统，而线程可以直接读写（全局变量）进行通信。
5、临界区是统一进程下的线程间通信机制。
6、默认下，Linux一个进程最多能打开1024个文件。
进程间通信：管道、共享内存、消息队列、信号量、socket。
线程间通信：临界区（只可以用于线程间）、互斥量、信号量、事件。
Linux常用命令：
1、cd变换工作目录
2、pwd显示目前所在目录
3、mkdir建立新目录 rmdir删目录
4、ls
5、cp复制文件或目录
6、rm删除，加参数-r表示删除目录
7、cat由第一行开始查看文件
8、tac从最后一行开始显示文件
9、head -n number file 只显示一开始的几行
10、touch常用来新建空文件
11、grep分析一行信息，若其中有我们所需要的信息就将该行显示出来，常用在管道中。
12、df列出文件系统的整体磁盘使用量
13、ps将某个时间点的程序运行情况显示出来
14、top可以持续侦测程序运作的状态，比如看内存使用率
数据库：
1、数据库的核心和基础是数据模型。
2、数据模型一般由数据结构、数据操作和完整性约束条件三部分组成。
3、事务的四个特征：原子性a，一致性c，隔离性i，持续性d。
4、设置索引是要付出代价的，一是增加了存储空间，二是插入和修改数据要花费较多的时间。
5、mysql为学生表学号增加降序唯一索引
create unique index Stusno on Student（Sno desc）
删除该索引
alter table Student drop index Stusno
6、索引的优缺点以及该不该建索引。p345
创建索引可以大大提高系统的性能。
第一、通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
第二、可以加快数据检索速度，这也是加索引的最主要原因。
第三：可以加速表与表之间的连接，特别是在实现数据的参照完整性方面特别有意义。
第四、再使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
第五、通过使用索引，可以在查询中使用优化隐藏器，提高系统的性能。
缺点：
第一、创建索引和维护索引要耗费时间，而且这种时间随着数据量的增加而增加。
第二、索引需要占物理空间。
第三、当表中数据增加、删除、修改的时候，索引也要动态维护，降低了数据维护性能。
索引是建在某些列上的。
适合建索引的：
1）、在经常需要搜索的列上建索引，强制该列的唯一性和组织表中数据的排列结构。
2、在作为主键的列上创建索引，加快连接的速度。
3、在经常用到连接的列上建索引。
4、在经常需要根据范围进行搜索的列上创建索引。
5、在经常需要排序的列上创建索引。
6、在经常使用where子句的列上创建索引，加快条件判断。
不适合建索引的：
1）、在查询中很少使用到的列
2）、只有很少数据值的列
3）、定义为text和bit等数据类型的列，因为这些列的数据量要么大要么取值很少，不利于使用索引
4）当修改操作远远大于检索操作时，不该建索引。修改性能和检索性能是相互对立矛盾的。
7、存储过程（Stored Procedure）是在大型数据库系统中，一组为了完成特定功能的SQL 语句集，存储在数据库中，经过第一次编译后再次调用不需要再次编译，用户通过指定存储过程的名字并给出参数（如果该存储过程带有参数）来执行它。
8、%表示任意长度的通配符，_表示一个长度的通配符
9、LIMIT两种参数使用，limit n等同于limit 0 n。输出从0开始，到n之前的n行数据。
设计模式：
1、面向对象最基本的五个设计原则：单一职责原则，开放封闭原则，依赖倒置原则，接口隔离原则和Liskov替换原则。
数学：
1、N条直线有M个交点，则平面被划分成N+M+1个区域。
其他：
1、简述Java和C++的不同。
java运行在虚拟机上
c++支持无符号运算和指针，java不支持。
java中参数传递总是值传递（参数是对象时传递的是对象的引用），在c++中，参数传递有值传递、引用传递、指针传递。
java有垃圾回收，c++没有。
c++允许运算符重载，java不允许。
c++允许多继承，java只允许单继承。
2、常见的度量软件可靠性的指标。
MTTF平均失效前时间
MTBF平均无故障时间。