计算机考研常见面试题总结

操作系统
C++
数据结构与算法
软件工程
计算机网络
数据库
其他
- 线性代数中特征值和特征向量的意义？

操作系统

进程的三个组成部分？

程序段、数据段、PCB(Process Control Block)

什么是物理内存？什么是虚拟内存？两者的关系？

物理内存（内存条）：当打开程序时，系统会将程序自动加载到物理内存上。

虚拟内存（硬盘）：虚拟内存是代替物理内存行使存储的功能，但无法代替物理内存行使加载程序的功能。

关系：当运行的程序过多，物理内存不够时，系统会将一部分硬盘空间当内存条使用，这就变成了虚拟内存。

分页与分段的区别？

页是信息的物理单位，分页是为了实现离散分配方式，以消减内存的外零头，提高内存的利用率，分页仅仅是系统的需要。

段是信息的逻辑单位，分段是为了更好的满足用户的需要。

页的大小固定，分为页号+页内地址。段的长度可变，取决于用户编写的程序。

分页的作业地址是一维的，分段的地址是作业地址是二维的。

cache的作用是什么？

cache（高速缓冲存储器）位于CPU和主存之间的，它的容量小，但是速度很快，解决CPU与主存之间速度不匹配的问题。

硬中断与软中断的区别？

硬中断：硬中断是由硬件产生的，可以直接中断CPU。

软中断：软中断是由当前正在运行的进程产生的，不能中断CPU，软中断是需要内核为正在运行的进程去做一些I/O请求。

程序什么时候应该使用线程，什么时候单线程效率高。

耗时的操作使用线程，提高应用程序响应。
并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求。
多CPU系统中，使用线程提高CPU利用率。
改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序会利于理解和修改。

其他情况都使用单线程。

进程和线程的差别。

线程是指进程内的一个执行单元，也是进程内的可调度实体。与进程的区别:

调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位
并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行
拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源
系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销

并发与并行区别？

并发：一个处理器同时处理多个任务。并行：多个处理器或者是多核的处理器同时处理多个不同的任务。

死锁的四个必要条件

互斥、请求保持、不可剥夺、环路

死锁的处理

鸵鸟策略、预防策略、避免策略、检测与解除死锁

描述实时系统的基本特性

在特定时间内完成特定的任务，实时性与可靠性。

页面置换算法

最佳置换算法OPT 。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。
先进先出置换算法FIFO
最近最久未使用算法LRU
时钟算法CLOCK
改进型时钟算法

中断和系统调用区别？

中断：解决处理器速度和硬件速度不匹配，是多道程序设计的必要条件。每个中断都有自己的数字标识，当中断发生时，指令计数器PC和处理机状态字PSW中的内容自动压入处理器堆栈，同时新的PC和PSW的中断向量也装入各自的寄存器中。这时，PC中包含的是该中断的中断处理程序的入口地址，它控制程序转向相应的处理，当中断处理程序执行完毕，该程序的最后一条iret（中断返回），它控制着恢复调用程序的环境。

中断和系统调用的区别：中断是由外设产生，无意的，被动的

系统调用是由应用程序请求操作系统提供服务产生，有意的，主动的。

要从用户态通过中断进入内核态。（联系）

中断过程：中断请求中断响应断点保护执行中断服务程序断点恢复中断返回

系统调用过程：应用程序在用户态执行时请求系统调用，中断，从用户态进入内核态，在内核态执行相应的内核代码。

网络编程中设计并发服务器，使用多进程与多线程，请问有什么区别？

进程：子进程是父进程的复制品。子进程获得父进程数据空间、堆和栈的复制品。
线程：相对与进程而言，线程是一个更加接近于执行体的概念，它可以与同进程的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。

两者都可以提高程序的并发度，提高程序运行效率和响应时间。

线程和进程在使用上各有优缺点：线程执行开销小，但不利于资源管理和保护；而进程正相反。同时，线程适

合于在SMP机器上运行，而进程则可以跨机器迁移。

C++

C++的特点是什么？

封装被定义为"把一个或多个项目封闭在一个物理的或者逻辑的包中"。在面向对象程序设计方法论中，封装是为了防止对实现细节的访问。封装只公开某些对外接口，隐藏具体实现细节。增加了一定的安全性，防止信息的泄露以及破坏。
继承在现有类（基类、父类）上建立新类（派生类、子类）的处理过程称为继承。派生类能自动获得基类的除了构造函数和析构函数以外的所有成员，可以在派生类中添加新的属性和方法扩展其功能。
多态多态指在程序设计中存在同名不同方法的存在，主要通过子类对父类的覆盖来实现多态，设计原则之一就是要依赖于抽象，而不依赖于具体，增加灵活性。多态就是为了体现这一原则。

支持面向对象和面向过程的开发。

C++的异常处理机制？

抛出异常和捕捉异常进行处理。

c和c++，java的区别?

c是纯过程，c++是对象加过程，java是纯面向对象的。

纯虚函数

被virtual修饰的成员函数，纯虚函数是一种特殊的虚函数，在许多情况下，在基类中不能对虚函数给出有意义的实现，而把它声明为纯虚函数，它的实现留给该基类的派生类去做。这就是纯虚函数的作用。

关键字static的作用是什么？

C语言中

在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
在模块内（但在函数体外），一个被声明为静态的变量可以被模块内所用函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。
在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的模块的本地范围内使用。

在嵌入式系统中，要时刻懂得移植的重要性，程序可能是很多程序员共同协作同时完成，在定义变量及函数的过程，可能会重名，这给系统的集成带来麻烦，因此保证不冲突的办法是显示的表示此变量或者函数是本地的，static即可。

在Linux的模块编程中，这一条很明显，所有的函数和全局变量都要用static关键字声明，将其作用域限制在本模块内部，与其他模块共享的函数或者变量要EXPORT到内核中。

关键字const有什么含意?

表示常量不可以修改的变量。

const int a;

int const a;

这两个的作用是一样，a是一个常整型数。

const int *a;

a是一个指向常整型数的指针（也就是，整型数是不可修改的，但指针可以）。

int * const a;

a是一个指向整型数的常指针（也就是说，指针指向的整型数是可以修改的，但指针是不可修改的）。

int const * a const;

a是一个指向常整型数的常指针（也就是说，指针指向的整型数是不可修改的，同时指针也是不可修改的）。

也许你可能会问，即使不用关键字 const，也还是能很容易写出功能正确的程序，那么我为什么还要如此看重关键字const呢？我也如下的几下理由：

关键字const的作用是为给读你代码的人传达非常有用的信息，实际上，声明一个参数为常量是为了告诉了用户这个参数的应用目的。如果你曾花很多时间清理其它人留下的垃圾，你就会很快学会感谢这点多余的信息。（当然，懂得用const的程序员很少会留下的垃圾让别人来清理的。）
通过给优化器一些附加的信息，使用关键字const也许能产生更紧凑的代码
合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数，防止其被无意的代码修改。

简而言之，这样可以减少bug的出现

如何引用一个已经定义过的全局变量？

可以用引用头文件的方式，也可以用extern关键字，如果用引用头文件方式来引用某个在头文件中声明的全局变理，假定你将那个变量写错了，那么在编译期间会报错，如果你用extern方式引用时，假定你犯了同样的错误，那么在编译期间不会报错，而在连接期间报错。

用变量a给出下面的定义

一个整型数（An integer）int a;

一个指向整型数的指针（ A pointer to an integer） int *a;

一个指向指针的的指针，它指向的指针是指向一个整型数（ A pointer to a pointer to an integer） int **a;

一个有10个整型数的数组（ An array of 10 integers） int a[10];

一个有10个指针的数组，该指针是指向一个整型数的。（An array of 10 pointers to integers） int *a[10];

一个指向有10个整型数数组的指针（ A pointer to an array of 10 integers） int (*a)[10];

一个指向函数的指针，该函数有一个整型参数并返回一个整型数（A pointer to a function that takes an integer as an argument and returns an integer） int (*a)(int);

一个有10个指针的数组，该指针指向一个函数，该函数有一个整型参数并返回一个整型数 int (*a[10])(int);

嵌入式系统中经常要用到无限循环，你怎么样用C编写死循环呢？

while(1){ }或者for( ; ; ){ }

引用与指针有什么区别？

引用必须被初始化，指针不必。
引用初始化以后不能被改变，指针可以改变所指的对象。
不存在指向空值的引用，但是存在指向空值的指针。

局部变量能否和全局变量重名？

能，局部会屏蔽全局。要用全局变量，需要使用 "::"

局部变量可以与全局变量同名，在函数内引用这个变量时，会用到同名的局部变量，而不会用到全局变量。对于有些编译器而言，在同一个函数内可以定义多个同名的局部变量，比如在两个循环体内都定义一个同名的局部变量，而那个局部变量的作用域就在那个循环体内。

全局变量和局部变量在内存中是否有区别？如果有，是什么区别？

全局变量储存在静态数据库，局部变量在堆栈。

堆栈溢出一般是由什么原因导致的？

没有回收垃圾资源。

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

构造函数不能声明为虚函数

对于一个频繁使用短小函数，在C语言中应用什么实现，在C++中应用什么实现?

c用宏定义；

c++用inline，表示为内联函数。inline 只适合涵数体内代码简单的涵数使用，不能包含复杂的结构控制语句例如 while、switch，并且不能内联函数本身不能是直接递归函数（即，自己内部还调用自己的函数）。

c和c++中的struct有什么不同？

c和c++中struct的主要区别是

c中的struct不可以含有成员函数，而c++中的struct可以。

c++中struct和class的主要区别在于默认的存取权限不同，struct默认为public，而class默认为private

举几种进程的同步机制，并比较其优缺点。

信号量机制一个信号量只能置一次初值，以后只能对之进行p操作或v操作。由此也可以看到，信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点。
自旋锁旋锁是为了保护共享资源提出的一种锁机制。调用者申请的资源如果被占用，即自旋锁被已经被别的执行单元保持，则调用者一直循环在那里看是否该自旋锁的保持着已经释放了锁自旋锁是一种比较低级的保护数据结构和代码片段的原始方式，可能会引起以下两个问题
- 死锁
- 过多地占用CPU资源
管程信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。
- 其基本思想是将共享变量和对它们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰，便于维护和修改，易于保证正确性。
- 如果一个分布式系统具有多个CPU，并且每个CPU拥有自己的私有内存，它们通过一个局域网相连，那么这些原语将失效。
会合进程直接进行相互作用
分布式系统

数据结构与算法

常见的数据结构

数组：顺序存储，随机访问
链表：链表存储，顺序访问
栈：分为栈顶和栈底，遵循先进后出原则
队列：一个线性表，像排队一样，受约束控制，遵循先进先出原则
树：二叉树、平衡二叉树、大顶堆，小顶堆等
图：最短路径，关键路径

什么是平衡二叉树？

左右子树都是平衡二叉树且左右子树的深度差值的绝对值不大于1。

冒泡排序算法的时间复杂度是什么？

时间复杂度是O(n²)。

数组和链表的区别

从逻辑结构来看：
- 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。
- 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐），链表必须根据next指针找到下一个元素。
从内存存储来看：
- (静态)数组从栈中分配空间，对于程序员方便快速,但是自由度小
- 链表从堆中分配空间，自由度大但是申请管理比较麻烦

从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反，如果需要经常插入和删除元素就需要用链表数据结构了。

排序算法有哪些？

插入排序，冒泡排序，选择排序，快速排序，堆排序，归并排序，基数排序，希尔排序等。

排序方法	平均时间复杂度	最坏情况下时间复杂度	额外空间复杂度	稳定性
简单选择排序	O(n²)	O(n²)	O(1)	不稳定
冒泡排序	O(n²)	O(n²)	O(1)	稳定
直接插入排序	O(n²)	O(n²)	O(1)	稳定
希尔排序	O(n^d)	O(n²)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定
快速排序	O(nlogn)	O(n²)	O(logn)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(n)	稳定
基数排序	O(P(N + B))	O(P(N + B))	O(n + b)	稳定

怎么理解哈希表，哈希表是什么？

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

请简述KMP算法

在一个字符串中查找是否包含目标的匹配字符串。

其主要思想是每趟比较过程让子串先后滑动一个合适的位置。

当发生不匹配的情况时，不是右移一位，而是移动（当前匹配的长度– 当前匹配子串的部分匹配值）位。

Dijkstra算法与Prim算法的区别

prim算法过程：

prim算法是最小生成树算法，它运用的是贪心原理，设置两个点集合，一个集合为要求的生成树的点集合A，另一个集合为未加入生成树的点B。

它的具体实现过程是：

所有的点都在集合B中，A集合为空。(memset(visited, 0, sizeof(visited))
任意以一个点为开始，把这个初始点加入集合A中，从集合B中减去这个点(visited[1]=1)。寻找与它相邻的点中路径最短的点，如后把这个点也加入集合A中，从集合B中减去这个点（visited[pos]=1）。
更新未被访问的节点的dist[]值。
重复上述过程。一直到所有的点都在A集合中结束。

dijkstra算法过程：

初始时，S只包含源点v，即S＝v。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或（若u不是v的出边邻接点）。
从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
重复步骤（2）和（3）直到所有顶点都包含在S中。

小总结

Prim是计算最小生成树的算法，Dijkstra是计算最短路径的算法，
都是使用贪婪和线性规划，每一步都是选择权值/花费最小的边。

贪婪：一个局部最有解也是全局最优解；

线性规划：主问题包含n个子问题，而且其中有重叠的子问题。

贪心算法和动态规划以及分治法的区别？

贪心算法顾名思义就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，得到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。

动态规划是把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。（各子问题重叠）

分治法（divide-and-conquer）：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。（各子问题独立）

分治模式在每一层递归上都有三个步骤：

分解（Divide）：将原问题分解成一系列子问题；
解决（conquer）：递归地解各个子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。

两个栈模仿一个队列

进队：入A栈。
出队：若B栈不为空，则B栈全部出栈；否则将A栈中数据全部入B栈，再依次出B栈。

两个队列模仿一个栈

入栈：入A队
出栈：将A队除队尾元素全部转移到B队，出A队，算法思想就是两个队列倒来倒去，只留一个元素时出栈。

如何判断链表是否有环?

设置快慢指针，快指针每次前进两步，当两指针重合则有环，快指针为null则无环。

如何判断有环链表环的入口?

将遍历过的结点都入set，如果当前结点在set里有，则此结点即为入口。
快慢指针重合后，重置fast指针

链表能否使用二分查找？

可以。先将链表排序，将各个结点的值记入数组，再二分查找。

栈应用括号匹配？

左括号入栈，右括号出栈进行匹配，栈空仍未匹配到则失败。

二叉树删除节点

被删除的节点是叶子节点，这时候只要把这个节点删除，再把指向这个节点的父节点指针置为空就行。

被删除的节点有左子树，或者有右子树，而且只有其中一个，那么只要把当前删除节点的父节点指向被删除节点的左子树或者右子树就行。

被删除的节点既有左子树而且又有右子树，这时候需要把左子树的最右边的节点或者右子树最左边的节点提到被删除节点的位置。

软件工程

有哪些软件测试分类？

黑盒测试：不考虑软件内部原理，以用户角度测试软件输入输出
白盒测试：知道软件内部工作过程，确定每个分支都能按照预定正常工作
灰盒测试：集合白盒黑盒
冒烟测试：测试软件基本功能，快速
系统测试：验证系统是否满足需求规格的黑盒类测试
性能测试：负载测试和压力测试
安全测试：假扮黑客侵入系统
兼容性测试：不同平台不同环境下的测试

类之间的关系有哪些？

继承：类继承另一个类的功能
实现：类实现接口的功能
依赖：A类的某个方法使用到了B类
关联：强依赖关系，B类作为一个属性出现在了A类
聚合：一种特别的关联，公司与个人的关系
组合：强聚合关系，整体与部分的联系更紧密，如汽车与轮胎

软件工程标准步骤？

问题定义
可行性研究
需求分析
总体设计
详细设计
编码和单元测试
综合测试
软件维护

自顶向下和自底向上测试方法的区别？

自顶向下：从程序入口主控模块开始，按照系统程序结构，沿着控制层次从上而下测试各模块。方便把握整体结构，早期可发现顶层错误。
自底向上：从最底层模块，即叶子结点开始，按照调用从下而上的测试各模块。最后一个模块提交后才能完整系统测试，某些模块可以提前测试。

确定模块的功能和模块的接口是在软件设计的那个阶段完成的?

概要设计阶段

软件工程的三要素？

方法、工具、过程。

软件工程的主要模型？

瀑布模型：前一阶段工作结束才可以进行下一阶段工作。基于文档，易于维护，但加大了工作量。
快速原型：快速建立可以运行的程序，完成的功能是最终软件的一个子集。不带反馈环，满足用户真实需求，但会导致系统设计差，难以维护。
增量模型：每个阶段不交付完整产品，软件由一系列增量构件组成。降低开发风险，易于维护，但不容易控制整体过程。
螺旋模型：结合快速原型和瀑布模型，有利于软件重用，减少风险，风险人员需要一定经验。
喷泉模型：迭代，无缝，节省开发时间。

内聚和耦合

内聚：指一个好的内聚模块内应当尽量只做一件事，描述的是模块内的功能联系。
耦合：各模块之间相互连接的一种度量，耦合强弱取决于模块间接口的复杂程度。
- 内聚类型低→高：功能内聚、信息内聚、通信内聚、过程内聚、时间内聚、逻辑内聚、偶然内聚
- 耦合类型高→低：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合

计算机网络

Internet采用哪种网络协议？该协议的主要层次结构？

TCP/IP协议

主要层次结构为：应用层/传输层/网络层/数据链路层/物理层。

Internet物理地址和IP地址转换采用什么协议？

ARP (Address Resolution Protocol)（地址解析协议）

IP地址的编码分为哪俩部分？

IP地址由两部分组成，网络号和主机号。不过是要和“子网掩码”按位与上之后才能区分哪些是网络位哪些是主机位。

OSI，TCP/IP，五层协议的体系结构

OSI分层（7层）：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。

TCP/IP分层（4层）：网络接口层、网际层、运输层、应用层。

五层协议（5层）：物理层、数据链路层、网络层、运输层、应用层。

每一层的作用如下：

物理层：激活、维持、关闭通信端点之间的机械特性、电气特性、功能特性以及过程特性。该层为上层协议提供了一个传输数据的物理媒体。
数据链路层：数据链路层在不可靠的物理介质上提供可靠的传输。该层的作用包括：物理地址寻址、数据的成帧、流量控制、数据的检错、重发等。
网络层：网络层负责对子网间的数据包进行路由选择。此外，网络层还可以实现拥塞控制、网际互连等功能。
传输层：第一个端到端，即主机到主机的层次。传输层负责将上层数据分段并提供端到端的、可靠的或不可靠的传输。此外，传输层还要处理端到端的差错控制和流量控制问题。
会话层：会话层管理主机之间的会话进程，即负责建立、管理、终止进程之间的会话。会话层还利用在数据中插入校验点来实现数据的同步。
表示层：表示层对上层数据或信息进行变换以保证一个主机应用层信息可以被另一个主机的应用程序理解。表示层的数据转换包括数据的加密、压缩、格式转换等。
应用层：为操作系统或网络应用程序提供访问网络服务的接口。

IP地址的分类

A类地址：以0开头，第一个字节范围：0~127；
B类地址：以10开头，第一个字节范围：128~191；
C类地址：以110开头，第一个字节范围：192~223；
D类地址：以1110开头，第一个字节范围为224~239；

IP组播有那些好处?

Internet上产生的许多新的应用，特别是高带宽的多媒体应用，带来了带宽的急剧消耗和网络拥挤问题。组播是一种允许一个或多个发送者（组播源）发送单一的数据包到多个接收者（一次的，同时的）的网络技术。组播可以大大的节省网络带宽，因为无论有多少个目标地址，在整个网络的任何一条链路上只传送单一的数据包。所以说组播技术的核心就是针对如何节约网络资源的前提下保证服务质量。

ARP协议的工作原理

首先，每台主机都会在自己的ARP缓冲区中建立一个 ARP列表，以表示IP地址和MAC地址的对应关系。当源主机需要将一个数据包要发送到目的主机时，会首先检查自己 ARP列表中是否存在该 IP地址对应的MAC地址：

如果有，就直接将数据包发送到这个MAC地址；
如果没有，就向本地网段发起一个ARP请求的广播包，查询此目的主机对应的MAC地址。此ARP请求数据包里包括：源主机的IP地址、硬件地址、以及目的主机的IP地址。网络中所有的主机收到这个ARP请求后，会检查数据包中的目的IP是否和自己的IP地址一致。
- 如果不相同就忽略此数据包；
- 如果相同，该主机首先将发送端的MAC地址和IP地址添加到自己的ARP列表中，如果ARP表中已经存在该IP的信息，则将其覆盖，然后给源主机发送一个 ARP响应数据包，告诉对方自己是它需要查找的MAC地址；源主机收到这个ARP响应数据包后，将得到的目的主机的IP地址和MAC地址添加到自己的ARP列表中，并利用此信息开始数据的传输。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。

路由设备与相关层

物理层：中继器（Repeater，也叫放大器），集线器。
数据链路层：网桥，交换机。
网络层：路由器。
网络层以上的设备：网关

常见的路由选择协议，以及它们的区别

常见的路由选择协议有：RIP协议、OSPF协议。

RIP协议：路由信息协议，底层是贝尔曼福特算法，它选择路由的度量标准（metric)是跳数，最大跳数是15跳，如果大于15跳，它就会丢弃数据包。
OSPF协议：开放最短路径优先，底层是迪杰斯特拉算法，是链路状态路由选择协议，它选择路由的度量标准是带宽，延迟。

VPN 和 NAT

VPN（Virtual Private Network，虚拟专用网）
NAT（Network Address Translation，网络地址转换）

TCP与UDP的区别

TCP 面向连接，UDP 是无连接的。
TCP 提供可靠的服务，也就是说，通过 TCP 连接传送的数据，无差错，不丢失，不重复，且按序到达；UDP 尽最大努力交付，即不保证可靠交付。
TCP 的逻辑通信信道是全双工的可靠信道；UDP 则是不可靠信道。
每一条 TCP 连接只能是点到点的；UDP 支持一对一，一对多，多对一和多对多的交互通信。
TCP 面向字节流（可能出现黏包问题），实际上是 TCP 把数据看成一连串无结构的字节流；UDP 是面向报文的（不会出现黏包问题）
UDP 没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如 IP 电话，实时视频会议等）
TCP 首部开销20字节；UDP 的首部开销小，只有 8 个字节

TCP的可靠性如何保证？

确认和超时重传
数据合理分片和排序
流量控制
拥塞控制
数据校验

在浏览器中输入www.baidu.com后执行的全部过程

现在假设如果我们在客户端（客户端）浏览器中输入http://www.baidu.com，而baidu.com为要访问的服务器（服务器），下面详细分析客户端为了访问服务器而执行的一系列关于协议的操作：

客户端浏览器通过DNS解析到www.baidu.com的IP地址220.181.27.48，通过这个IP地址找到客户端到服务器的路径。客户端浏览器，发起一个HTTP会话到220.181.27.48，然后通过TCP进行封装数据包，输入到网络层。
在客户端的传输层，把HTTP会话请求分成报文段，添加源和目的端口，如服务器使用80端口监听客户端的请求，客户端由系统随机选择一个端口如5000，与服务器进行交换，服务器把相应的请求返回给客户端的5000端口。然后使用IP层的IP地址查找目的端。
客户端的网络层不用关系应用层或者传输层的东西，主要做的是通过查找路由表确定如何到达服务器，期间可能经过多个路由器，这些都是由路由器来完成的工作，我不作过多的描述，无非就是通过查找路由表决定通过那个路径到达服务器。
客户端的链路层，包通过链路层发送到路由器，通过邻居协议【ARP协议】查找给定IP地址的MAC地址，然后发送ARP请求查找目的地址，如果得到回应后就可以使用ARP的请求应答交换的IP数据包现在就可以传输了，然后发送IP数据包到达服务器的地址。

HTTP协议包括哪些请求？

GET：请求读取由URL所标志的信息。
POST：给服务器添加信息（如注释）。
PUT：在给定的URL下存储一个文档。
DELETE：删除给定的URL所标志的资源。

HTTP中，POST与GET的区别

Get是从服务器上获取数据，Post是向服务器传送数据。
Get是把参数数据队列加到提交表单的Action属性所指向的URL中，值和表单内各个字段一一对应，在URL中可以看到。
Get传送的数据量小，不能大于2KB；post传送的数据量较大，一般被默认为不受限制。
根据HTTP规范，GET用于信息获取，而且应该是安全的和幂等的。
- 所谓安全的意味着该操作用于获取信息而非修改信息。换句话说，GET 请求一般不应产生副作用。就是说，它仅仅是获取资源信息，就像数据库查询一样，不会修改，增加数据，不会影响资源的状态。
- 幂等的意味着对同一URL的多个请求应该返回同样的结果。

TCP对应的协议

FTP：定义了文件传输协议，使用21端口。常说某某计算机开了FTP服务便是启动了文件传输服务。下载文件，上传主页，都要用到FTP服务。
Telnet：它是一种用于远程登陆的端口，用户可以以自己的身份远程连接到计算机上，通过这种端口可以提供一种基于DOS模式下的通信服务。如以前的BBS是-纯字符界面的，支持BBS的服务器将23端口打开，对外提供服务。
SMTP：定义了简单邮件传送协议，现在很多邮件服务器都用的是这个协议，用于发送邮件。如常见的免费邮件服务中用的就是这个邮件服务端口，所以在电子邮件设置-中常看到有这么SMTP端口设置这个栏，服务器开放的是25号端口。
POP3：它是和SMTP对应，POP3用于接收邮件。通常情况下，POP3协议所用的是110端口。也是说，只要你有相应的使用POP3协议的程序（例如Fo-xmail或Outlook），就可以不以Web方式登陆进邮箱界面，直接用邮件程序就可以收到邮件（如是163邮箱就没有必要先进入网易网站，再进入自己的邮-箱来收信）。
HTTP协议：是从Web服务器传输超文本到本地浏览器的传送协议。

UDP对应的协议

DNS：用于域名解析服务，将域名地址转换为IP地址。DNS用的是53号端口。
SNMP：简单网络管理协议，使用161号端口，是用来管理网络设备的。由于网络设备很多，无连接的服务就体现出其优势。
TFTP(Trival File Transfer Protocal)：简单文件传输协议，该协议在熟知端口69上使用UDP服务。

TCP 三次握手建立连接

第一次握手：主机A通过向主机B 发送一个含有同步序列号的标志位的数据段给主机B，向主机B 请求建立连接，通过这个数据段，主机A告诉主机B 两件事：我想要和你通信；你可以用哪个序列号作为起始数据段来回应我。
第二次握手：主机B 收到主机A的请求后，用一个带有确认应答（ACK）和同步序列号（SYN）标志位的数据段响应主机A，也告诉主机A两件事：我已经收到你的请求了，你可以传输数据了；你要用那个序列号作为起始数据段来回应我
第三次握手：主机A收到这个数据段后，再发送一个确认应答，确认已收到主机B 的数据段："我已收到回复，我现在要开始传输实际数据了，这样3次握手就完成了，主机A和主机B 就可以传输数据了。

TCP 四次挥手释放连接

第一次：当主机A完成数据传输后,将控制位FIN置1，提出停止TCP连接的请求；
第二次：主机B收到FIN后对其作出响应，确认这一方向上的TCP连接将关闭，将ACK置1；
第三次：由B端再提出反方向的关闭请求，将FIN置1 ；
第四次：主机A对主机B的请求进行确认，将ACK置1，双方向的关闭结束.。

TCP 为什么要进行三次握手？

因为信道不可靠，而 TCP 想在不可靠信道上建立可靠地传输，那么三次通信是理论上的最小值。

双方都需要确认对方收到了自己发送的序列号，确认过程最少要进行三次通信。

为了防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误。

TCP 为什么要进行四次挥手？

因为 TCP 是全双工模式，客户端请求关闭连接后，客户端向服务端的连接关闭（一二次挥手），服务端继续传输之前没传完的数据给客户端（数据传输），服务端向客户端的连接关闭（三四次挥手）。所以 TCP 释放连接时服务器的 ACK 和 FIN 是分开发送的（中间隔着数据传输），而 TCP 建立连接时服务器的 ACK 和 SYN 是一起发送的（第二次握手），所以 TCP 建立连接需要三次，而释放连接则需要四次。

为什么 TCP 连接时可以 ACK 和 SYN 一起发送，而释放时则 ACK 和 FIN 分开发送呢？（ACK 和 FIN 分开是指第二次和第三次挥手）

因为客户端请求释放时，服务器可能还有数据需要传输给客户端，因此服务端要先响应客户端 FIN 请求（服务端发送 ACK），然后数据传输，传输完成后，服务端再提出 FIN 请求（服务端发送 FIN）；而连接时则没有中间的数据传输，因此连接时可以 ACK 和 SYN 一起发送。

数据库

数据库的发展阶段？

人工管理阶段>>文件系统阶段>>数据库系统阶段

什么是数据库系统？

在计算机系统中引入数据库后的系统。它是由数据库、数据库用户、计算机软硬件、数据库管理员。

什么是数据库？

数据库是长期存在计算机内、有组织的、可共享数据集合。

什么是数据库系统的三级模式？

模式（逻辑模式或概念模式）、外模式（子模式或用户模式）、内模式（存储模式或物理模式）

什么是聚集索引或非聚集索引？

物理存储顺序与逻辑顺序相同

物理存储顺序与索引顺序不一致

数据库的ACID

原子性Atomicity：一个事务被视为一个最小单元，要么全部提交，要么全部回滚
一致性Consistency：事务总是由一种状态转换为另一种状态，数据库事务只会是执行前的状态或是执行后的状态，不会出现执行中的状态。即如果一个事务执行了十秒，那么第一秒读到的结果和第九秒得到的应该是相同的。
隔离性Isolation：一个事务的执行不会被另一个事务影响，互不干扰。
持久性Durability：事务只要提交了，那么数据库中的数据也永久的发生了变化。

数据库三范式

1NF(Normal Form)：R的所有属性都不能再分解为更基本的数据单位。
2NF：R的所有非主属性都依赖于R的关键属性，所有列都依赖于任意一组候选关键字。
3NF：每一列都与任意候选关键字直接相关而不是间接相关，没有传递依赖。
BCNF：3NF基础上，关系R只有一个单属性，或R的子集都是单属性，则R满足BCNF。

插入100个数据和100万个数据有何区别？

100数量级小，可以随意插入；100万数量级大，如果表里有索引，则索引更新代价很高，可以采取先删除索引再插入，插入完成后再建索引的策略。

处理大数据量的策略？

表分区，备份，入带库。

一般数据库若出现日志满了，会出现什么情况，是否还能使用？

只能执行查询等读操作，不能执行更改，备份等写操作，原因是任何写操作都要记录日志。也就是说基本上处于不能使用的状态。

其他

线性代数中特征值和特征向量的意义？

从定义出发，Ax=cx：A为矩阵，c为特征值，x为特征向量。

矩阵A乘以x表示，对向量x进行一次转换（旋转或拉伸）（是一种线性转换），而该转换的效果为常数c乘以向量x（即只进行拉伸）。

我们通常求特征值和特征向量即为求出该矩阵能使哪些向量（当然是特征向量）只发生拉伸，使其发生拉伸的程度如何（特征值大小）。这样做的意义在于，看清一个矩阵在那些方面能产生最大的效果（power），并根据所产生的每个特征向量（一般研究特征值最大的那几个）进行分类讨论与研究。