春招面试准备

90道

1、引用和指针的区别。

a、定义指针时分配内存，引用不分配内存，而和原变量内存地址相同，这是最本质的区别。
b、引用必须初始化
c、没有指向空值的引用，但是存在指向空值的指针。

2、值传递、地址传递、引用传递的区别。

a、值传递，为形参重新分配内存空间，拷贝，形参不改变实参的值，结束后释放空间。
b、引用传递：不重新分配内存，形参会改变实参的值，不涉及内存分配和释放，效率最高。
c、地址传递：形参是指针变量，会给该指针变量分配内存空间，形参会改变实参的值，结束后释放空间。

3、static的作用

a、static变量的作用范围属于整个函数体，内存只会分配一次，和auto变量不同，多次调用该函数不会重
新分配新的变量，一次调用，持久保存。
普通函数f，调用三次，输出000
若f中有static，调用三次，输出012
b、在模块内的static变量可以被模块内函数访问，但不能被模块外其他函数访问，即使extern也不行。
c、static函数也会被限定在模块内
d、类中static成员变量属于整个类所拥有的，所有对象只有一个实例
e、类中static成员函数属于整个类所拥有，所以不接受this指针，只能访问类中static成员变量。

4、const关键字的用处

a、阻止一个变量被改变，const表示常量，需要初始化
b、对指针来说，可以指定指针本身const，也可以指定指针所指的数据为const，或两者都是const
const int p;//const是底层cosnt，表示p所指向的数据是一个常量，不可通过p修改该常量的值，但是p可以指向其他变量
int const p;//顶层const，表示指针p本身是一个常量，不可以再指向其他变量，但是它所指的变量可以改变值
c、函数参数const，函数内不能改变值
d、类的成员函数const，常函数，不能修改类的成员变量
e、对类的成员函数，有时候会指定其返回值为cosnt，以使得返回值不为“左值”，因为在c++中可能存在给一个函数赋值的情况，即函数返回一个引用。

5、链表和数组的区别。

a、数组是顺序表，开辟连续空间。而链表靠指针连接不连续的空间
b、数组要求空间连续，占用总空间小，链表则相反
c、数组方便排序查找，删除修改较慢；链表则相反。

6、直接实现strlen（）

int mystrlen(char *str)
{
   if(str==NULL)
      return 0;
   int i=0;
   for(i=0;str[i]!='\0';i++);
   return i;
}

7、直接实现strstr(char str,char sub)搜寻子串的函数

char* mystrstr(char *str,char* sub)
{
char *pos;
char *s;
for(int i=0;i<strlen(str);i++)
{
	pos=&str[i];
	s=sub;
	while(*pos==*s)
	{
		pos++;s++;
		if(*s=='\0')
			return &str[i];
	}
}
return NULL;
}

8、直接实现strcat(char str1,char str2)

char* mystrcat(char *str1,char *str2)
{
	char *p=str1;
	while(*str1!='\0')
		str1++;
	while(*str2!='\0')
	{
		*str1=*str2;
		str1++;
		str2++;
	}
	*str1='\0';
	return p;
}

9、直接实现strcmp(char str1,char str2)

int mystrcmp(char *str1,char *str2)
{
	if(str1==NULL || str2==NULL)
		throw "invalid arguments";
	while(1)
	{
		if(*str1>*str2)
			return 1;
		else if(*str1<*str2)
			return -2;
		else
		{
			if(*str1=='\0')
				return 0;
			else
				str1++;str2++;
		}		
	}
}

10、请给出函数指针数组等定义

int *a;指向指针的指针
int a[10];一个数组，每个元素是一个int指针
int (a)[10];一个指针，指向有10个元素的int数组
int (a) (int);一个指向函数的指针，该函数有一个整形参数并返回一个整形
int (*a[10])(int);函数指针数组，一个包含10个元素的数组，每个元素是一个函数指针，每个函数一个int参数返回一个int

11、给定一个整形变量a，设置或清除bit N

与或非操作

12、C++中的空类，默认产生哪些成员函数.

缺省构造函数
拷贝构造函数
析构函数
赋值运算符
当类成员有指针的时候，拷贝构造和赋值运算符需要重写。

13、struct和class的区别

c中struct不可以有成员函数，c++中可以
c++中 struct默认权限public，class默认权限private

14、内存思考题

void get(char *p)
{p=(char*)malloc(100);}
voit Test()
{
char *str=NULL;
get(str);
strcpy(str,"hello world");
printf(str);
}

程序崩溃，因为get不会传递动态内存，test中的str一直是null。
指针free后需要置为null，否则会成野指针

15、关键字volatile有什么含义

被volatile修饰的变量是说这个变量可能会被意想不到地改变
比如硬件寄存器中的值可能经常变，所以使用的时候就要读取
多线程中的变量也是一样。
volatile告诉编译器不要优化这个变量，每次读取都读取实际的值而不是读取缓存

16、读写绝对地址

int ptr;
ptr=(int )0x67a9;
*ptr=0xaa55

17、heap与stack的区别

stack的空间由操作系统自动分配/释放，heap上的空间是手动分配释放的。
stack空间有限，heap有很大的自由存储区（new）
程序在编译期对变量和函数分配内存都在栈上，且程序运行过程中函数调用参数的传递也在栈上。
还有一种静态内存，保存局部static对象

18、不借助第三个数交换两个数的值。

第一种：a=a+b;b=a-b;a=a-b;
第二种：a=a*b;b=a/b;a=a/b;（b不为0）
第三种：a=a^b;b=a^b;a=a^b;

19、用宏定义写出swap（x，y）

#define swap(x,y) (x)=(x)+(y);(y)=(x)-(y);(x)=(x)-(y);
宏定义时参数用括号括起来，且表达式之间不要有空格

20、用宏定义返回两个参数中较小的一个

#define Min(x,y) ((x)>(y)?(y):(x))
结尾没有分号

21、带参数的宏和带参数的函数的区别

a、宏在编译时处理，会展开，而函数在运行时处理
b、宏里的参数不需要定义类型，函数中参数必须有类型
c、宏会使程序变长，而函数不会
d、宏不占用存储空间，函数占用
e、宏不占用运行时间，函数调用和返回时占用运行时间
带参宏简单，不灵活

22、定义宏，求出数组元素的个数

#define NTBL(table) (sizeof(table)/sizeof(table[0]))

23、两个栈实现一个队列的功能

入队：将元素压入栈a
出队：
（1）判断栈b是否为空
（2）如果不为空，则将栈a中所有元素依次pop出并push到栈b
（3）将栈b的栈顶元素pop出，即出队元素

24、在c++中调用c函数，为什么要加extern c?

答：c++支持函数重载，c语言不支持函数重载。函数被c++编译后在库中的名字和c的不同。
void foo(int x,int y)
在c中编译结果：_foo
在c++中：_foo_int_int
所以要加extern “c”来解决名字匹配问题

25、找出程序中的错误

视频第26题：5个错误
27题：4个（可不看）

26、一句话判断x是否是2的次幂

a、x&(x-1)
上式为0，则是，否则不是。
b、判断logx/log2是不是整数

27、按要求定义变量

定义全零全一的变量
unsigned int zero=0;
unsigned int compzero=~0;
不能写unsigned int compzero=0xFFFF，因为处理器位数不一定

28、malloc分配内存

ptr=(char *)malloc(0)
分配能否成功？
分配虽然成功，但它是0个字节，无法真正使用。

29、对数组名取地址

数组名本身表示数组第一个元素的地址
数组名取地址代表整个数组，该地址+1是加了整个数组的长度。

30、static修饰局部变量

生命周期延长

31、switch。。。case接受哪种基本数据类型？省略break会怎样？

不接受float、double。
若省略break则匹配成功后一直运行到结束或遇到第一个break

32、无符号数据类型转换

无符号和有符号相运算，有符号会转化成无符号，若是负数则会变为极大的正数。

33、算出一个字节中被置1的位个数

循环移位并判断最后一位是否为1
或者用x&(x-1)计算

34、编写函数将给定的字符串转换成整数。

int invert(char *str)
{
	int num=0;
	while(*str!='\0')
	{
		int d=*str-48;
		num=num*10+d;
		str=str+1;
	}
	return num;
}

35、将整数转换成字符串。

void fun(int num, char *pval)
{
	char strval[100];
	int i,j;
	int val0=0;
	int val1=0;
	val0=num;
	while(1)
	{
		val1=val0%10;
		val0=val0/10;
		strval[i]=val1+48;
		if(val0<10)
		{
			i++;
			strval[i]=val0+48;
			break;
		}
	}
	for(j=0;j<=i;j++)
		pval[j]=strval[i-j];
	pval[j]='\0';
}

36、怎么判断链表中是否有环？

追逐方式。
两个指针遍历链表，一个每次走一步，一个每次走两步，若后者能追上前者，则表示有环。

37、双向链表的插入和删除。

插入修改四个指针。
删除只需要修改两个。

38、二维数组转置。

核心操作:b[j][i]=a[i][j]

39、输入一行字符，统计其中有多少个单词。

按空格累加。

40、杨辉三角

41、计算字符串中子串出现的次数

循环比较。

42、数组a[n]，存放1到n，找出被重复的数字，时间复杂度为O（n）

int do_dup(int a[],int N)
{
	int sum=0;
	for(int i=0;i<N;i++)
		sum+=a[i];
	sum=sum-(N-1)(N)/2;
	return sum;
}

43、16bit的整数，每4bit为一个数，写函数求他们的和

循环，移位相加即可。
c+=n&15;
n=n>>4;

47、什么函数不能声明为虚函数？

virtual
a、内联函数，内联函数在编译时展开，而虚函数是运行时动态绑定，所以两者矛盾。
b、构造函数，构造函数用来创建一个新的对象，而虚函数运行时建立在对象基础上，在构造函数时对象尚未形成。
c、静态成员函数，静态成员函数属于一个类而非某一对象，没有this指针，无法进行对象的判别。
d、非成员函数
e、类的成员函数是模板函数的时候。

48、编写一个函数作用是把char数组字符串循环右移n位

void LoopMove(char *pstr,int steps)
{
	int n=strlen(pstr)-steps;
	char temp[MAX_LEN];
	strcpy(temp,pstr+n);
	strcpy(temp+steps,pstr);
	*(tmp+strlen(pstr))='\0';
	strcpy(pstr,temp);
}

49、编写类String的构造函数、析构函数和赋值函数。

一个类包含指针的话，一般会有析构函数，而且要重写拷贝构造和赋值运算符，因为默认是地址的拷贝和赋值，对指针来说无意义。

class String{
public:
	String(const char *str=NULL);
	String(const string &other);//拷贝构造
	~String();
	String & operator=(const String &other);//赋值运算符

};

50、指向二维数组的指针1。

51、指向二维数组的指针2。

注意++到底是加的一维数组还是一个元素。

52、逗号运算符（优先级最低）

a=3;b=5;
c=a,b;
d=(a,b);
执行之后，c=3，d=5.

53、sizeof运算符。

int i=3;
int j;
j=sizeof(++i+ ++i);
print(“i=%d,j=%d”,i,j);
输出：i=3，j=4
原因：编译器进行优化，发现++对sizeof根本没影响，所以会优化不计算++，发生短路现象。

54、递归展开求值。

55、赋值运算符=作为循环条件。

赋非零值，无限循环。
赋0，不循环。

56、（a+b）+c与（a+c）+b是否恒等

不一定，可能会溢出。假设a+b溢出，但是c是负数，a+c后再加b就不一定溢出了。
a+b+c一定等于b+a+c

57、进程和线程的差别。

线程是指进程内的一个执行单元，也是进程内的可调度实体。
a、线程是调度分配的基本单位，进程是拥有资源的基本单位。
b、并发性，都可以并发。进程切换比线程切换开销大。
c、拥有资源，进程是拥有资源的独立单位，线程不拥有系统资源，但是可以访问所属进程的资源。
d、系统开销，在创建或撤销进程时，由于系统都要分配和回收资源，所以开销较大。

58、解释const char * const p

左边是底层const，右边是顶层const。
char const p//常量指针，p的地址不可以修改，即指针本身不可修改
const char p;//指向常量的指针，指针本身可修改，但指向的内容不可修改。
char const * p;//同上
两个const就是指针本身不可以修改，所指内容也不可更改。

59、memset、memcpy和strcpy的根本区别。

memset和memcpy需要包含memory.h，strcpy需要string.h
memset用来对一段内存空间全部设置为某个字符 memset(a,0,sizeof(a))
memcpy用来内存拷贝，拷贝任何数据类型的对象 memcpy(b,a,sizeof(b))
strcpy只能拷贝字符串，遇到’\0’就结束，所以不需要指定大小。
要注意内存溢出。

60、析构函数有何特点。

a、析构函数也是特殊的类成员函数，和构造函数一样没有返回类型
b、没有参数
c、不能重载
d、public、private、protected对析构函数无效
e、析构函数不能手动调用，只有在类对象生命周期结束的时候，由系统自动调用释放在构造函数中分配的资源，回收内存。
f、构造函数不可以是virtual，但析构函数可以。

61、虚函数有什么用？

a、虚函数的功能是使子类可以用同名的函数对父类函数进行覆盖，并且在通过父类指针调用时，如果有覆盖则自动调用子类覆盖函数，如果没覆盖调用父类中的函数，从而实现灵活扩展和多态性。
b、如果是纯虚函数，则纯粹是为了在子类覆盖时有个统一的命名而已，子类必须覆盖纯虚函数，否则子类也是抽象类
c、含有纯虚函数的类称为抽象类，不能实例化对象，主要用于做接口

62、虚析构函数的作用

虚构函数调用是先子后父。
当一个派生类对象通过使用一个基类指针删除，而这个基类有一个非虚的析构函数，就会导致运行时派生类不会被销毁，然而基类部分已经被销毁，这就导致了部分析构，造成内存泄露。
此时就需要给基类一个虚析构函数。

63、分别给出bool、in、float、指针变量与零值比较的if语句

bool:if(!var)
int:if(var==0)
float: const float var=0.000001;
​ if(x>-var && x<var)
浮点数不能精确到0，所以需要在一个范围内近似看做0
指针：if(var==NULL)

64、32位下，计算sizeof

a、
void fun(char str[100])
{
sizeof(str)=?//4
}
原因：数组做函数形参，会转化成指针
b、
void p=malloc(100);
sizeof(p) //4
c、
int a[100]
sizeof(a)//4100
d、
char *p=”aaa”
sizeof(p)=?//4

65、写函数返回1+2+3+。。+n的值

解法1：一重循环
解法2：利用高斯公式直接求 （1+n）*n/2

66、深度广度遍历二叉树。

67、内联函数和普通函数的区别。

a、内联函数是将简单函数内嵌道调用它的程序代码中，目的是节约原本函数调用时的时空开销，不能含有循环、条件、选择等复杂的结构。
b、内联函数和宏的区别，宏是由预处理器对宏进行替代，而内联函数是通过编译器来控制的。内联函数是真正的函数，取消了函数的参数压栈，减少调用开销，不用担心像宏函数的问题。
c、用inline定义内联函数，任何在类的说明部分定义的函数都会自动认为是内联函数。

68、c++重写和重载重定义区别

a、重载特征：相同的范围（同一个类），函数名字相同，参数不同
b、重写（覆盖）：派生类函数覆盖基类函数，分别位于基类和派生类中，名字相同，参数相同，基类函数必须有virtual
c、重定义是指派生类的函数屏蔽了与其同名的基类函数
如果派生类的函数和基类的函数同名，参数不同，此时不管有无virtual，基类的函数被隐藏
如果派生类的函数与基类的函数同名，参数也相同，但基类没有virtual，此时基类的函数被隐藏

69、一个数据成员是否可以既是const又是static，为什么？如果可以，如何初始化。

可以的。
static一般在类外初始化，const一般在构造函数里初始化。
既是const又是static就在类外初始化，但要在类外初始化的同时声明为const。

70、构造函数和析构函数的异同点。

构造函数的特点：
1、构造函数名字与类名相同
2、构造函数可以有任意的参数，但不能具有返回类型
3、定义对象时，编译系统自动调用构造函数
4、够咱函数是特殊的成员函数，函数体可以在类内，也可以在类外
5、构造函数不能像其他成员函数那样被显示调用，它是在定义对象的同时被调用

析构函数的特点：
1、析构函数名字与类型相同，析构函数前加一个~
2、析构函数没有参数，也没有返回值，不能被重载，一个类只能有一个析构函数
3、在撤销对象时，编译系统会自动调用析构函数
4、析构函数可以是virtual，而构造函数不可以。

71、自动调用拷贝构造函数的几种情形。

拷贝构造函数是用一个已知对象来初始化另一个同类对象。
拷贝构造函数也是类的构造函数，与雷鸣相同，又一个该类对象引用的参数。
若自己不写，则会自动生成一个默认的。
若一个类中有指针，就需要自己写，不能用默认的，因为默认的是地址拷贝。

自动调用情况：
1当类的一个对象去初始化该类另一个对象时。
2如果函数形参是类的对象，调用函数进行形参和实参结合时
3如果函数返回值是类对象，函数返回时。

72、类型转换构造函数是什么？

自动调用类型匹配的构造函数，自动将基本数据类型转换成对象。

class Person{
public:
double height;
Person(double h):height(h){}
};

void main()
{
Person p=2.3;//类型转换构造函数，将2.3转换成double调用该构造函数
cout<<p.height<<endl;
}
类型转换函数可以产生自动类型转换匹配，如下：
class Person{
public:
intheight;
Person(int h):height(h){}
};
int的构造函数也可以调用成功。

73、异常处理方式。

步骤：
1、程序执行时发生错误
2、以一个异常对象记录错误的原因及相关信息
3、程序检测到这个错误（读取错误对象）
4、程序决定如何处理错误
5、错误处理，并在此后恢复或终止程序的执行

74、成员函数和友元函数的区别

a、成员函数是类定义的一部分通过特定的对象来调用。成员函数可以隐式访问对象的成员，而无须使用成员操作符
b、友元函数不是类的组成部分，因为被称为直接函数调用。友元函数不能隐式访问类成员，必须将成员操作符用于参数传递的对象。

75、c++中哪些运算符不能重载

.
?:
sizeof（不是函数是运算符）
::
（指针解引用不可以重载，乘号可以）
.

76、如何重载前++和后++

前++不带参数，后++带一个（int）以示区分

iCount & operator++(){
	data++;
	return *this;
}
iCount operator++(int)
{
	iCount temp=*this;
	data++;
	return temp;
}

77、请说出STL标准模板库中的几个常用类

vector
list
set
stack
queue
map

78、函数模板和函数重载的异同

函数重载是指函数名字相同，但是参数类型或者个数不同，顺序不同。
函数模板是指函数算法相同，而参数类型不同。

79、类型转换构造函数是什么？

是隐式调用构造函数，将基本数据类型转换成对象。
对象不可转换成基本数据类型。

80、c++中explicit关键字有什么用。

explicit和构造函数一起使用，指明构造函数只能显式调用，目的是为了防止不必要的隐式调用类型转换构造函数。

class Person{
public:
double height;
explicit Person(double h):height(h){}
};

void main()
{
Person p=2.3;//会报错，因为explicit阻止了隐式调用，必须显式调用
Person p2(2.4);//显示调用，可以
cout<<p.height<<endl;
}

81、c++中restrict关键字有什么作用？

是用来优化的，是c99新加的关键字。
restrict只能修饰指针，修饰的指针时能够访问所指区域的唯一入口，限制多个指针指向同一地址。
如果两个指针指向同一个地址，一个被释放了，另一个就成了野指针。

82、c++中常用的设计模式又哪些？

工厂方法
策略模式
单例模式
迭代器模式
抽象工厂模式
建造者模式
适配器模式
桥接模式
折磨死
解释器模式
命令模式
中介者模式
观察者陌生
状态模式
代理模式

83、写一个单例模式的例子。

其目的是保证一个类仅有一个实例，并提供一个访问它的全局访问点。比如定义常量的类。
将构造函数私有。

class C
{
private:
	C(){};//构造函数私有
	static C * p;
public:
	static C * Get(){
		if(p==NULL)
			p=new C();
		return p;
	}
};
C * C::p==NULL;//static属性类外初始化

void main()
{
	C* p1=C::get();
	C* p2=C::get();
	cout<<(p1==p2)<<endl;//输出true
}

84、面向对象的三大特征。

a、封装
b、继承
c、多态

85、什么是封装

封装是面向对象的特征之一，是对象和类概念的主要特性。
封装，也就是把客观事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏。
c++中，public、protected、private就是封装的访问权限说明符。

86、什么是继承

继承可以使现有类的所有功能，并在无需重新编写原来类的情况下对功能进行扩展。
c++支持单继承和多继承，也有多级继承。
用public、protected和private修饰继承特性。

87、什么是多态

polymorphisn
允许将父对象设置成为一个或更多的他的子对象相等的技术。
父对象可以根据当前赋值给它的子对象的特性以不同的方式运作。
父类的指针用引用赋子类的值。
两种方式，覆盖（重写），重载。
覆盖，子类重新定义父类的virtual虚函数。
重载，允许存在多个同名函数，但参数列表不同。

88、类和对象的区别。

是一般与个别、抽象与具体、集体与个体的区别。
举个例子即可（人类和张三）

89、c++中的namespace是什么？

命名空间，类似于java中的包
避免在不同程序库中的命名冲突。
详看c++ primer

90、什么是可重入和不可重入函数？

可重入性：reentrant
函数可以由多于一个任务并发使用，而不必担心数据错误，可以在任意时刻被中断，稍后再继续运行不会丢失数据。
不可重入函数不能超过一个任务所共享。

可重入函数：
不为连续的调用持有静态数据
不返回指向静态数据的指针
使用本地数据
如果必须访问全局变量需要利用互斥信号量
不调用不可重入函数

不可重入函数：
使用了静态变量
返回静态变量
调用了不可重入函数
调用了malloc或free
调用了其他标准i/o

总的来说，一个函数使用了未受保护的共享资源，就不可重入。

hash函数、数据库基本

hash函数性质：输入域巨大，输出域固定
1、输入域无限
2、相同输入，结果相同
3、不通输入，结果可能相同也可能不同
4、不同输入值得到的hash值，均匀分布在输出域上（优劣评判）

32位无符号整数范围，0到40一亿左右。

第一范式：每一个分量都是不可分的数据项。
第二范式：每一个非主属性完全函数依赖于任何一个候选码。
第三范式：每一个非主属性既不传递依赖于码，也不部分依赖于码。
BCNF：若每一个决定因素都包含码。
一个满足BCNF的关系模式有：
所有非主属性对每一个码都是完全函数依赖。
所有主属性对每一个不包含它的码也是完全函数依赖。
没有任何属性完全函数依赖于非码的任何一组属性。

事务的ACID特性
原子性：事务中的操作要么都做，要么都不做。
一致性：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。
隔离性：一个事务的执行不能被其他事务干扰。
持续性：事务一旦提交，它对数据库中数据的改变就应是永久性的。

计算机网络

1、网络协议主要由三要素组成：语法、语义和 同步。

2、osi体系结构
物理层：单位bit，为上层提供了传输数据的物理介质。
数据链路层：单位帧，在不可靠的物理介质上提供可靠的传输。HDLC、PPP。
网络层：单位分组或数据包，负责对子网间的数据包进行路由选择。IP。
传输层：单位报文，是第一个端到端即进程到进程的层次，提供端到端的传输。TCP、UDP。
会话层：负责建立、管理、终止进程之间的会话。
表示层：进行数据转换，包括加密、压缩、格式转换等。
应用层：为操作系统或网络应用程序提供网络服务的接口。FTP、HTTP。

tcp/ip体系结构：网络接口层、网际层、传输层和应用层。
五层体系结构就是把网络接口层依然分解为物理层和数据链路层。

3、数据链路层三个基本问题：数据成帧，透明传输，差错检测。
CRC检验码的位数就是生成多项式的最高次数。

4、路由器分组转发流程
a、从分组首部提取目的站的IP地址D，得出目的网络地址为N
b、若网络N与此路由器直接相连，则直接将分组交付给目的站D，否则转到c
c、若路由表中有目的地址为D的特定主机路由，则将分组传送给路由表中所指明的下一跳路由器，否则转d
d、若路由表有到达网络N的路由，则将分组传送给路由器表指明的下一跳路由器，否则转e
e、若路由表中有一个默认路由，则将分组传送到默认路由，否则报错。

5、ping的过程
ping是ICMP的一个重要应用。
ping同一个网段的主机：查找目的主机的mac地址，然后直接交付。如果没查到mac地址，就进行一次arp请求。
ping不同网段的主机：发送到网关让其进行转发，同样要发送到网关也得知道网关的mac地址，根据mac地址进行转发。

6、三块专用地址
A类：10.0.0.0 ~ 10.255.255.255
B类：172.16.0.0 ~ 172.31.255.255
C类：192.168.0.0 ~ 192.168.255.255

7、用户数据包协议 UDP（User Datagram Protocol）是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部）。

传输控制协议 TCP（Transmission Control Protocol） 是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块）

8、web页面请求过程
a、向DNS服务器发送DNS查询报文解析域名获得IP地址。
b、通过TCP向服务器发送连接请求。
c、服务器上会有个服务进程在不断监听80端口，当监听到连接请求后便与浏览器建立连接。建立之后服务器会随机分配一个端口号给客户端，之后的tcp传输都用这个分配的客户端。
d、TCP建立后，浏览器向服务器放松要求获取某一Web页面的http请求。
e、服务器收到http请求后构建所需信息，通过HTTP响应返回给浏览器。
f、浏览器将信息进行解析并渲染，显示页面。最后会断开tcp连接。

HTTP部分

1、get和post的请求都能使用额外的参数，但是get的参数是以查询字符串出现在url中，而post的参数存储在实体主体部分。
get的传参方式相比于post安全性较差，因为get传的参数在url是可见的，可能会谢露私密信息。并且get只支ASCII字符，如果参数为中文则可能会出现乱码，而post支持标准字符集。
get的主要目的是获取资源，而post的主要目的是传输实体主体数据。

head和get一样，但是不返回报文实体主体部分。
put不带验证机制，存在安全问题。
delete作用和put相反。
trace追踪路径
connect要求用隧道协议连接代理，加密后经过隧道传输。

状态码：
1xx：信息性状态码
2xx：成功
3xx：重定向
4xx：客户端错误
5xx：服务器错误

四种类型首部字段：
通用首部、请求首部、响应首部和实体首部

HTTP协议是无状态的，主要是为了让HTTP协议尽可能简单，使得它能够处理大量事务。HTTP/1.1引入Cookie来保存状态信息。

Cookie信息存在浏览器上。

Session和Cookie区别
Session是服务器用来跟踪用户的一种手段，每个Session都有一个唯一标识Session ID。
当服务器创建一个Session时，给客户端发送的响应报文就包含了Set-Cookie字段，其中有个名为sid的键值对，这就是Session ID。当客户端收到后就把Cookie保存在浏览器中，并且之后发送的请求报文都包含Session ID。
HTTP就是通过Session和Cookie一起合作实现跟踪用户状态的，Session用于服务器端，Cookie用于客户端。

当浏览器访问一个包含多张图片的 HTML 页面时，除了请求访问 HTML 页面资源，还会请求图片资源，如果每进行一次 HTTP 通信就要断开一次 TCP 连接，连接建立和断开的开销会很大。 持久连接 只需要进行一次 TCP 连接就能进行多次 HTTP 通信。HTTP/1.1 开始，所有的连接默认都是持久连接。

持久连接需要使用Connection首部字段进行管理。
HTTP1.1开始HTTP默认是持久连接，若要关闭需要客户端或服务端提出断开，使用connection：close。
而在HTTP1.1之前默认是非持久连接，若要持久连接则需要使用keep-alive。

代理服务器不会改变url，主要目的是缓存、网络访问控制以及访问日志记录。
网关服务器则不同，会将HTTP转化为其他协议进行通信，从而请求非HTTP服务器。

隧道：使用SSL等加密手段，为客户端和服务器之间建立一条安全的通信线路。

HTTP安全问题：
1、使用明文进行通信，内容可能会被窃听
2、不验证通信方的身份，通信方的身份可能遭遇伪装
3、无法证明报文的完整性，报文有可能被篡改。

HTTPS并不是新协议，而是HTTP先和SSL通信，再由SSL和TCP通信，提供了加密、认证和完整性保护。

加密：HTTPs使用混合加密机制，使用公钥加密用于传输信息的对称秘钥，之后使用对称秘钥进行通信。
对称秘钥的缺点：无法安全传输秘钥本身。
公钥缺点：更耗时。

认证使用证书。
SSL提供摘要功能来验证完整性。

HTTP/1.1新增内容：
1、默认为持久连接
2、提供了范围请求功能
3、提供了虚拟主机功能
4.、多了一些缓存处理字段
5、多了一些状态码

操作系统：

操作系统基本特征：并发、共享、虚拟、异步

进程和线程的区别：
1、进程是除CPU外资源分配的基本单位，但是线程不拥有资源，线程访问隶属进程的资源
2、调度：线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程内的线程切换到另一个进程内的线程时，会引起进程切换。
3、系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、IO设备等，所付出的开销远大于创建或撤销线程时的开销。类似的，在进程切换时，涉及到当前执行进程CPU环境的保存及新调度进程CPU环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
4、通信方面：进程间通信需要进程同步和异步手段的辅助，以保证数据的一致性。而进程内部通信可以通过直接读/写同一进程中的数据段来进行通信。

windows进程间通信：管道、共享内存、消息队列，信号量，socket
Windows线程间通信：临界区、互斥量、信号量和事件。

临界区与互斥体的区别
1、临界区只能用来同步本进程内的线程，而不能同步多个进程中的线程。互斥量、信号量、事件都可以跨越进程使用来进行同步数据操作。
2、临界区是非内核对象，只在用户态进行锁操作，速度快；互斥体是内核对象，在核心态进行锁操作，速度慢。
3、临界区和互斥体在windows平台下都可用。

死锁的必要条件：
1、互斥条件
2、占有和等待
3、不剥夺条件
4、循环等待
死锁防止策略：
打破1，可同时访问
打破2，进程执行前申请需要的全部资源，在执行过程中不再申请资源
打破3，占有资源的进程若要申请新资源，必须主动释放已占用资源
打破4，层次分配。

死锁避免：银行家算法

分段分页的区别：
1、分页透明，分区需要程序员显式划分每个段。
2、分页是一维地址，分段是二维地址。
3、页的大小不可变，而段的大小可以动态改变。
4、分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了让程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

内存池、Nginx

内存池可以减少内存碎片、避免内存泄露，提高内存分配效率。

通常我们习惯直接使用new、malloc等API申请分配内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的内存碎片并进而降低性能。

Nginx（发音同 engine x）是一款轻量级的Web 服务器／反向代理服务器及电子邮件（IMAP/POP3）代理服务器

Nginx提供的负载均衡有两种：内置策略和扩展策略。
内置策略微轮询，加权轮询，IP hash。
扩展策略url hash

I/O多路复用

目的：因为阻塞模型在没有收到数据的时候就会阻塞卡住，如果一次需要接受多个socket fd的时候，就会导致必须处理完前面的fd，才能处理后面的fd，即使可能后面的fd比前面的fd还要先准备好，所以这样就会造成客户端的严重延迟。为了处理多个请求，我们自然先想到用多线程来处理多个socket fd，但是这样又会启动大量的线程，造成资源的浪费，所以这个时候就出现了io多路复用技术。就是用一个进程来处理多个fd的请求。

与多进程/多线程相比，IO多路复用最大的好处就是系统开销小。

1应用层数据到kernel
2 kernel复制到user space
阻塞io模型就是将这个两个过程合并在一起，一起阻塞。非阻塞就是第一个不阻塞，而是不断轮询，第二个仍然阻塞。

select：
程序呼叫select，然后整个程序就阻塞了，这个时候kernel就会轮询检查所有select负责的fd，当找到其中一个client的数据准备好了，select就会返回，这个时候程序启动系统调用，将数据从kernel复制到进程缓冲区。

poll
原理和select十分相似，差别如下：
描述fd集合的方式不同，poll没使用select的fd_set结构，所以poll是链式的，没有最大连接数的限制。
poll有个特点是水平触发，也就是通知fd就绪后，如果这次没有被处理，那么下次poll的时候会再次通知同个fd已经就绪。

select缺点：
1fd_size大小为32个整数（32位机器上就是32*32，1024bit），每个fd一个bit，所以最大只能处理1024个fd

2每一次呼叫select都要从user space把fd_set复制到kernel中，因为每一次呼叫前，set都可能有变动，而epoll提供了共享记忆存储结构。

3kernel轮询每个fd，约限行时间，消耗大且效率低下。

epoll提供三个函数：
创建epoll对象，传回id
事件注册函数，将需要监听的事件和需要监听的fd交给epoll对象。
等待注册的事件被触发或timeout。等待函数。

epoll没有数量限制，最大数量只和系统能够打开多少fd有关。
epoll不需要每次都将set赋值到kernel检查，因为在注册的时候已经将fd拷贝了进来。
select/poll都是主动轮询，而epoll是被动，它不仅可以知道有fd就绪，还可以知道是哪个fd就绪，直接处理。（类比轮询和中断方式。）

3-12

nginx：异步非阻塞

nginx的请求处理：
1、操作系统提供的机制产生相关的时间
2、接受和处理这些事件，如果接收到数据，则产生更高层的request对象
3、处理request的header和body
4、产生响应，并发送回客户端
5、完成request的处理
6、重新初始化定时器及其他事件

C++11新特性

C++11新特性（很多，节选，完整看C++ Primer）
1、新定义long long类型，一个long long类型至少和一个long一样大。
2、列表初始化，就是用大括号来初始化变量。
3、引入新常量nullptr，用来得到或者初始化指针。
4、引入auto和decltype，auto一般会忽略顶层const，decltype处理顶层const和引用的方式和auto不同，他会将变量包括顶层const和引用在内的信息都返回。
5、范围for语句
6、引入了两个新函数cbegin和cend。
7、C++11规定商一律向0取整，不论正负。
8、initializer_list，参数数量未知但是全部实参类型相同时可以使用该类型，和vector类似，只是其中存储的元素都是常量，不能修改。
9、尾置返回类型：auto fun() -> int (*)[10]，返回类型是一个指向一个十个整形数组的指针。
10、constexpr函数是指能够用于常量表达式的函数，函数的返回类型和所有形参类型都必须是字面值类型。
11、可以定义所谓的委托构造函数，使用它所属类的其他构造函数来执行它自己的初始化过程。
12、定义了array和forward_list，数组和单向链表。
13、新标准引入了三个新成员—emplace，这些操作构造而不是拷贝元素，将参数传给元素类型的构造参数。
14、lambda表达式
15、bind函数。
16、四个无序容器，unordere_map unordered_set unordered_multiset unordered_multimap，使用hash函数和==运算符
17、智能指针。shared_ptr允许多个指针指向同一个对象，unique_ptr则独占所指向的对象。还有一种weak_ptr的伴随类，是一种弱引用，指向shared_ptr所管理的对象，不改变引用计数。
18、使用=default生成默认构造函数

设计模式

观察者模式：定义了对象间的一对多依赖，当一个对象改变状态时，它的所有依赖者都会收到通知并自动更新。

装饰模式：动态地将责任附加到对象上。在扩展功能上，装饰者提供了比继承更有弹性的替代方案。

工厂模式：
简单工厂：在实例化一个超类的时候，可以用它的所有子类来进行实例化，要根据具体的情况来决定使用哪个子类。
工厂模式：定义一个创建对象的接口，但由子类决定要实例化哪个类。工厂方法把类实例化推迟到子类。
抽象工厂模式：提供一个接口，用于创建相关对象家族，而不需要明确指定具体类。

单例模式：
确保一个类只有一个实例，并提供一个全局访问点。
使用一个私有构造器、一个私有静态变量以及一个公有静态函数来实现。

命令模式：将命令封装成对象，以便使用不同的命令来参数化其他对象。

适配器模式：将一个类的接口，转换为客户期望的另一个接口。适配器让原来不兼容的类可以合作无间。

外观模式：提供一个统一的接口，用来访问子系统中一群接口，从而让子系统更容易使用。

模板方法模式：在一个方法中定义了一个算法的骨架，而将一些步骤延迟到子类中。这使得子类可以在不改变算法结构的情况下，重新定义算法中的某些步骤。

迭代器模式：提供顺序访问一个聚合对象中各个元素的方法，而不暴露聚合对象内部的表示。
组合模式：允许将对象组合成树形结构来表现整体/部分层次结构。组合能让客户以一致的方式处理个别对象以及组合对象。

状态模式：允许对象在内部状态改变时改变它的行为，对象看起来好像修改了它所属的类。

复合模式：
MVC：视图使用组合模式、模型使用观察着模式，控制器使用策略模式。

主流PC机的每秒钟计算量约为10^7~10^8次，一亿次左右。

3.14.2018

C++11新标准补充：
1、可以用=delete定义删除的函数，删除的函数意思是：虽然声明了它们，但不能以任何方式使用它们。
2、新标准引入了移动构造函数和move的标准库函数。
3、引入了右值引用，右值引用有一个重要的性质——只能绑定到一个将要销毁的对象。左值持久，右值短暂，不能将右值引用绑定到一个左值上。可以用static_cast显示的将一个左值转换为一个右值引用。
4.、标准库move函数来获得绑定到左值上的右值引用。
5、移动构造函数通常是noexcept。
6、虚函数的override指示符。
7、定义类为final来阻止继承。
8、引用折叠

3-15、Effective C++：

1、对于单纯常量，最好以const对象或enums替换#defines。对于形似函数的宏，最好改用inline函数来替换。
2、当const和non-const成员函数有着实质等价的实现时，令non-const版本调用const版本可避免代码重复。
3、为内置型对象进行手工初始化，因为C++不保证初始化它们。构造函数最好使用成员初值列，而不要在构造函数体内使用赋值操作。初值列列出的成员变量，其排列次序应该和它们在class中的声明次序相同。
为免除跨编译单元之初始化次序问题，请以local static对象替换non-local static对象。
4、编译器可以暗自为class创建default构造函数、copy构造函数、copy assignment操作符，以及析构函数。
5、带有多态性质的base classes应该声明一个virtual析构函数。如果class带有任何virtual函数，它就应该拥有一个virtual析构函数。如果不是为了作为base classes使用，或不是为了具备多态性，就不该声明virtual析构函数。
6、析构函数不要吐出异常，如果一个被析构函数调用的函数可能抛出异常，析构函数应该捕捉任何异常，然后吞下它们或结束程序。
如果客户需要对某个操作函数运行期间抛出的异常做出反应，那么class应该提供一个普通函数执行该操作。
7、在构造函数和析构函数中绝不要调用virtual函数。
8、令赋值操作符返回一个reference to *this。
9、确保当对象自我赋值时有良好行为，其中技术包括1比较来源对象和目标对象的地址2精心周到的语句顺序3copy and swap
10、copy函数应该确保复制对象内的所有成员变量以及所有base class成分。不要尝试以某个copy函数实现另一个copy函数，应该将共同机能放入第三个函数内，然后由两个copy函数分别调用它。
11、以对象管理资源。为防止资源泄露，请使用RAII对象，它们在构造函数中获得资源并在析构函数中释放资源。两个常被使用RAII classes是shared_ptr和auto_ptr，前者通常是较佳选择，因为auto_ptr的copy操作会使它指向NULL。
12、赋值RAII对象必须一并复制它所管理的资源，所以资源的copying行为决定RAII对象的copying行为。
13、APIs往往要求访问原始资源，所以每一个RAII classes应该提供一个取得其所管理资源的方法。对原始资源的访问可能经由显式转换或隐式转换。一般而言显示转换比较安全，但隐式转换对客户比较方便。
14、以独立语句将newed对象存储于智能指针内。如果不这样做，一旦异常被抛出，有可能导致难以察觉的资源泄露。
15、宁以pass-by-reference-to-const替换pass-by-value，但对于内置类型以及STL的迭代器和函数对象来说，pass-by-value比较好。
16、必须返回对象时，别妄想返回其reference。不要返回pointer或reference指向一个local stack对象，或返回reference指向一个heap-allocated对象。
17、将成员变量声明为private，这可赋予客户访问数据的一致性、可细微划分访问控制、允诺约束条件获得保证。protected并不比public更具封装性。
18、使用non-member、non-friend替换member函数。
19、如果一个函数的所有参数都需要类型转换，请为此采用non-member函数。
20、尽可能延后变量定义式的出现时间。
21、尽量少做转型动作，四种类型转换。
const_cast，转变对象的常量性，是唯一能将对象的常量性移除的C++转型操作符。
dynamic_cast：安全向下转型，唯一无法由旧式语法执行的动作。
reinterpret_cast：执行低级转型，强转。
static_cast:强迫隐式转换。
22、避免返回reference、pointer、iterator指向对象内部成分。
23、异常安全函数提供三个保证之一：
基本承诺：如果异常被抛出，程序内的任何事物仍然保持在有效状态下。
强烈保证：如果异常被抛出、程序状态不会改变。如果函数成功，就是完全成功，如果函数失败，程序会回复到调用函数之前的状态。
不抛掷保证：承诺绝不抛出异常。
24、inline函数：会导致代码膨胀
inline只是一个申请，不是强制命令。
不能是virtual
通过函数指针而进行的调用可能也不会被inline
不要只因为function templates出现在头文件，就将他们声明为inlines。

3-16、effective C++

1、支持编译依存性最小化的一般构想是：相依于声明式，不要相依于定义式。基于此构想的两个手段是handle classes和interface classes。程序库头文件应该以完全且仅有声明式的形式存在。这种做法不论是否涉及templates都试用。
2、public继承意味is-a，适用于base classes身上的每一件事情一定也适用于derived classes身上，每一个derived class对象也都是一个base class对象。
3、派生类内的名称会遮掩基类内的名称。在public继承下从来没有人希望如此。为了让被遮掩的名称再见天日，可使用using声明式。
4、接口继承与实现继承不同，在public继承下，derived classes纵使继承base classes的接口。
纯虚函数只具体指定接口继承。
非纯虚函数具体指定接口继承以及缺省的实现继承。
非虚函数指定接口继承和强制性实现继承。
5、绝不重新定义继承而来的缺省参数值，因为缺省参数值都是静态绑定，而virtual函数是动态绑定。
6、复合的意义和public继承完全不同。在应用域，复合意味has-a，在实现域，复合意味着is-implemented-in-terms-of。
7、private继承意味is-implemented-in-terms-of，通常比复合的级别低。但是当derived class需要访问protected base class的成员，或需要重新定义继承而来的virtual函数时，这么设计是合理的。
8、谨慎使用多重继承。如果virtual base classes不带任何数据，将是最具实用价值的情况。
9、TMP模板元编程是编写template-based C++程序并执行于编译期的过程，可以将工作由运行期移到编译期，因为得以实现早期错误侦测和更高的执行效率。
10、operator new 应该内含一个无穷循环，并在其中尝试分配内存，如果它无法满足内存需求，就该调用new-handler。它也应该有能力处理0bytes申请。operator delete应该在收到null指针时不做任何事。class专属版本还应该能够处理比正确大小更大的错误申请。
11、当你写一个placement operator new，请确定也写出了对应的placement operator delete。如果没有这样做，可能会发生隐微而时断时续的内存泄露。当你声明placement new 和placement delete，请不要无意识的遮掩他们的正常版本。

3-18更新

redis
redis是速度非常快的非关系型内存键值数据库，可以存储五种不同类型之间的映射。
五种数据类型：
字符串string、列表list、集合set、有序集合zset、散列表hash。

键的过期时间：
redis可以为每个键设置过期时间，时间一到，自动删除。
但对于散列表，只能为整个散列表设置过期时间，而不能为键里面的单个元素设置过期时间。

redis最简单的事务实现方式是使用multi和exec命令将事务操作包裹起来。

持久化：
1、快照持久化
2、aof持久化

复制：
slave of host port命令来让一个服务器成为另一个服务器的从服务器
1、从服务器连接主服务器的过程
a、主服务器创建快照文件，发送给从服务器，并在发送期间使用缓冲区记录执行的写命令。快照文件发送完毕之后，开始向从服务器发送存储在缓冲区中的写命令。
b、从服务器丢弃所有旧数据，载入主服务器发来的快照文件，之后从服务器开始接受主服务器发来的写命令
c、主服务器每执行一次写命令，就向从服务器发送相同的写命令。
2、主从链
当负载不断增多时，可以创建中间层分担主服务器的复制工作。

分片
通过对数据进行分片，用户可以将数据存储到多台机器里面。
客户端分片：一致性hash
代理分片：将客户端请求发送到代理上，由代理转发
服务器分片：redis cluster

redis适用场景：
缓存、消息队列、计数器、好友关系

.h文件，.lib文件以及.dll文件

头文件的作用是声明函数接口，用于编译阶段。
dll文件是函数可执行代码，用于运行阶段。
lib文件告诉编译器调用的函数在哪个dll文件中以及在该dll文件中哪个位置。是h和dll的桥梁。如果生成静态库文件，则没有dll，只有lib，这时函数的可执行代码也在lib中。用于链接阶段。

静态链接库和动态链接库的区别：
a、静态链接库就是把用到的函数代码直接链接进目标程序，程序运行的时候不再需要其他库文件。动态链接库就是把调用的函数所在文件模块和调用函数在文件中的位置等信息链接进目标程序，程序运行的时候再从dll中寻找相应代码，因此需要dll的支持。
b、如果采用静态链接的方式，则无论你愿不愿意，lib中的指令都全部被包含在最终生成的exe文件中，所以会导致应用程序比较大。但如果使用动态链接库，该dll最终不会被包含在exe中，exe执行时动态的引用和卸载该dll文件。
c、静态链接库中不能再包含其他静态库或动态库，而动态链接库中可以包含其他动态或静态链接库。

dll的用法：
a、使用h、lib以及dll。
b、直接用dll，此时需要利用win32 的api函数LoadLibrary和GetProcAddress把函数指针取出来再用。

B-B+树

B-树：
B-树是一种平衡的多路查找树，在文件系统中很有用。
一棵m阶的B树，或者是一棵空树，或者是满足下列特性的m叉树：
1、树中每个结点至多有m棵子树
2、若根结点不是叶子结点，则至少有量棵子树
3、除根之外的所有非终端结点至少有m/2上限整数棵子树
4、所有非终端结点包含下列信息数据（n,A0,K1,A1,K2，A2……Kn，An）
5、所有的叶子结点都出现在同一层次上，并且不带信息。

B树的插入删除，看书。

B+树和B-树差异在于：
1、有n棵子树的结点中含有n个关键字
2、所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。