计算机考研复试面试题整理_华东师范大学软件工程专硕复试面试问题

考研复试面试题整理

---

---

前言

笔者刚刚参加完2022年考研复试，现将复试过程中自己整理的部分面试题整理出来，仅供参考。

---

数据结构部分

1.数据结构按逻辑结构可以分为哪两类？
可以分为线性结构（线性表、栈、队列）和非线性结构（树、图、集合）
2.数据结构按存储结构可以分为哪两类？
顺序存储、链式存储、索引存储、散列存储。
3.顺序结构和链式结构的区别？
顺序结构是指内存连续的存储单元进行存储，而链式结构是指内存不连续的结构，通过一个节点指向另外一个节点的地址。
顺序存储很方便随机查找，但不利于频繁的插入删除数据。
链式结构无法做到随机查找，只能通过遍历的方式依次查找，但是很方便结点的插入和删除。
4如何判断链表是否有环？
设置快慢指针，快指针每次前进两步，当两指针重合则有环，快指针为null则无环。
5如何判断有环链表环的入口？
1、将遍历过的结点都入set，如果当前结点在set里有，则此结点即为入口。
2、快慢指针重合后，重置fast指针，此时fast每次走一步，再次重合结点即为入口。
6链表能否使用二分查找？
可以。先将链表排序，将各个结点的值记入数组，再二分查找。
给定一颗二叉树的头结点，和这颗二叉树中2个节点n1和n2，求这两个节点的最近公共祖先
7栈和队列的区别？
栈是先进后出的特殊线性表，队列是先进先出的线性表。
8两个栈模仿一个队列？
进队：入A栈。
出队：若B栈不为空，则B栈全部出栈；否则将A栈中数据全部入B栈，再依次出B栈。
9两个队列模仿一个栈？
入栈：入A队
出栈：将A队除队尾元素全部转移到B队，出A队，算法思想就是两个队列倒来倒去，只留一个元素时出栈。
10复杂度是什么？
复杂度包括时间复杂度和空间复杂度，用来评价一个算法的好坏。
11头节点的作用是什么？

1. 防止单链表是空的，使得空表和非空表的处理统一。
2. 使得在链表第一个位置上的操作和在表的其他位置的操作一致，保持了单链表操作的统一性。
   12为什么要引入双向链表？
   因为单链表结点中只有一个指向其后继的指针，使得单链表只能从头开始依次顺序地向后遍历。这样的查找速度和效率不高。
   13若有n个不同的元素进展没出站元素不同排列的个数为：
   

14什么是共享栈？
利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维空间数组，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
15循环队列如何区分队空还是队满？
1）牺牲一个单元来区分，入队时少用一个队列单元，规定队头指针在队尾指针的下一个位置作为队满的标志。队空的标志仍为队头指针和队尾指针重合。
2）增设表示元素个数的数据成员。
3）增设tag数据成员，tag为0时，若因删除导致frontrear，则队空。Tag为1时，若因插入导致frontrear，则队满。
16栈和队列的应用
栈：括号匹配、递归
队列：缓冲区、队列
17介绍以下各种树
树，二叉树：有左右子树的区分和度不超过2.
二叉排序树：左子树均小于根，根均小于右节点。。
线索二叉树：设置两个标识标记左右指针指向的是孩子还是前躯节点。
平衡二叉树：左右子树高度差绝对值小于等于1。
哈夫曼树：压缩用的。权值大小排列。
完全二叉树：只能从右边为空。
n0=n2+1
18度为2的树和二叉树的区别：
二叉树有左右子树的定义。
19树的存储结构
双亲表示法、孩子表示法、孩子兄弟表示法
20树的遍历
先序中序后序三种。递归实现。
21什么是线索二叉树？
指向节点前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树
22什么是哈夫曼树？
在含有N个带权叶子结点的二叉树中，其中带权路径(WPL)最小的二叉树称为哈夫曼树
23二叉树删除节点？
被删除的节点是叶子节点，这时候只要把这个节点删除，再把指向这个节点的父节点指针置为空就行。
被删除的节点有左子树，或者有右子树，而且只有其中一个，那么只要把当前删除节点的父节点指向被删除节点的左子树或者右子树就行。
被删除的节点既有左子树而且又有右子树，这时候需要把左子树的最右边的节点或者右子树最左边的节点提到被删除节点的位置。
24图的存储
邻接矩阵和邻接表，是多对多的关系，分为有向图和无向图。
25查找有哪几种？
查找有顺序查找、折半查找、分块查找
26线性表的查找有那几类？
直接查找和有序表的二分查找。
27散列函数的构造方法
直接定址法、除留余数法、数字分析法、平方取中法
28处理冲突的方法
开放定址法：（线性探测法、平方探测法、再散列法、伪随机序列法）
拉链法
29排序算法的介绍？
插入排序有直接插入和折半插入。都是在有序表里插入进去的。
交换排序：冒泡，快速：以一个数字划分两个区域，然后分别对两个区域继续划分，直到区间为一。注意快排是不稳定。
选择排序：简单的选择排序，堆排序
归并排序：将两个有序表归并到一个有序表。将两个有序表放到一起进行各个比较，比较完之后放回原来数组内。
30排序算法总结

31什么是稳定的排序算法？
一个序列中，关键字相同的数排序后相对位置不变即稳定，比如1、3、2、4、5、2序列，第三个位置2和最后一个位置2排序后，他们的位置先后不变化则稳定。
32B树和B+树的区别？
一、关键字不同
1、b树每一个关键字有且只出现一次。
2、而b+树有n棵子树的非叶节点有n个关键字，关键字会存储重复。
二、存储内容不同
1、b树每个节点除了存储关键字，还存储数据。
2、b+树只有叶子节点存储关键字信息，以及指向关键字记录的指针。
三、查找不同
1、b树查找相当于二分查找，可以在非叶节点结束。
2、而b+树的查找路径是由根到叶子节点，每次查找路径长度比较稳定。

操作系统部分

第一章
一、操作系统的基本特征有哪些？其中最基本的是什么？
并发、共享、虚拟、异步
最基本的是并发、共享
二、什么是原语？
所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。
三、什么是系统调用？
系统调用是指用户在程序中调用操作系统所提供的一些子功能，系统调用可视为特殊的公共子程序。用户程序执行陷入指令来发起系统调用，请求操作系统提供服务。
四、为什么要区分用户态和内核态？用户态和核心态的区别是什么？他们是如何让实现转换的？
区分执行态的主要目的是保护系统程序。
处于核心态时，说明此时正在运行的是内核程序，此时可以执行特权指令。
处于用户态时，说明此时正在运行的是应用程序，此时可以执行非特权指令。
内核态->用户态：执行一条特权指令，修改PSW的标志位为用户态。
用户态->内核态：访管指令，由中断引发，硬件自动完成。
五、分别简述大内核和微内核
大内核：将操作系统的主要功能模块进行集中，从而用以提供高性能的系统服务
微内核：将内核中最基本的功能保留在内核，将不需要在核心态执行的功能转移到用户态执行，降低内核设计的复杂性。
六、中断的分类
中断分为内中断和外中断
中断也称为外中断，指来自CPU执行指令以外发生的事，一般是外设请求或人为干预。
异常也称内中断，指的是源自CPU执行指令内部的事，一般不能被屏蔽，例如：程序的非法操作码、地址越界、算术溢出、虚存系统的缺页及专门的陷入指令等引起的事件。
七、简述特权指令和非特权指令
特权指令指有特殊权限的指令，必须在核心态执行，只能用于操作系统和其他系统软件，不直接提供给用户使用。
非特权指令只能在用户态下使用
八、并行和并发的区别
并行性是指两个或多个事件在同一时刻发生。
并发性是指两个或多个事件在同一时间间隔内发生。
九、简述访管指令与访管中断
访管指令是一条在用户态下执行的指令，在用户程序中，因要求操作系统提供服务而有意识地使用访管指令，从而产生访管中断，将操作系统转换为核心态。
十、简述中断处理的过程

第二章 进程管理
一、进程映像有哪几部分构成？
进程映像由程序段、相关数据段、PCB组成。
二、进程控制块（PCB）的作用是什么？PCB主要包括哪些信息？
PCB是进程存在的唯一标志，用来描述进程的基本情况和运行状态，进而控制和管理进程。
PCB主要包括进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息。
三、简要描述进程的创建过程以及进程的终止过程
在创建一个进程时所要完成的主要工作是什么？

1. OS调用进程创建原语Creat（）；
2. 申请空白PCB;
3. 为新进程分配资源；
4. 初始化PCB；
5. 将新进程插入就绪队列.
   在撤销一个进程时所要完成的主要工作是什么？
   1.根据被终止进程标识符，从PCB集中检索出进程PCB,读出该进程状态。
   2.若被终止进程处于执行状态，立即终止该进程的执行。
   3.若该进程还有子进程，应将所有子孙进程终止。
   4.将被终止进程拥有的全部资源，归还给父进程，或归还给系统。
   5.将被终止进程PCB从所在队列或列表中移出。
   四、进程的组织方式有哪几种？
   1.链接方式：按进程状态将PCB分为多个队列，此时操作系统持有指向各个队列的指针。
   2.索引方式：根据进程状态不同，建立几张索引表，此时操作系统持有指向各个索引表的指针。
   五、进程之间的通信方式有哪些？
   共享存储、消息传递、管道通信
   共享存储：通信进程之间存在一块可以被直接访问的共享空间。
   消息传递：进程通过系统提供的发送消息和接收消息两个原语进行数据交换。
   管道通信：发送进程以字符流形式将大量数据送入写管道，接收进程从管道中接收数据。
   六、进程与线程的区别是什么？
   1.进程是资源分配的基本单位，线程是独立调度的基本单位。
   2.进程的地址空间之间相互独立，同一进程的各线程之间共享进程的资源。
   3.进程间通信需要进程同步和互斥手段的辅助以保证数据的一致性，线程间可以直接读/写进程程序段来进行通信。
   七、线程的实现方式有哪两种？各自优缺点是什么？
   用户级线程、内核级线程
   用户级线程：有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。开销低，高效，并发能力强，一个线程阻塞则进程内所有线程都阻塞。
   内核级线程：线程的管理工作全部由内核完成。由内核管理，开销大，效率低，不灵活，但并行能力强。
   八、介绍三级调度，以及三级调度的联系
   作业调度（高级调度）：从辅存中选择作业送入内存
   中级调度（内存调度）：将暂时不能运行的进程调至外存，使其进入挂起态。或者将己经具备运行条件的进程调入内存，修改其状态为就绪态。
   进程调度（低级调度）：按照某种策略或者方法从就绪队列中选取一个进程，将处理机分配给它。

作业调度为进程活动做准备，进程调度使进程正常活动起来,中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之问
作业调度次数少，中级调度次数略多，进程调度频率最高
进程调度是最基本的、不可或缺的
九、挂起和阻塞的区别是什么？
两种状态都是暂时不能获得CPU服务的状态，但挂起状态将进程映像调到外存，而阻塞态下进程映像还在内存中。
十、实现临界区互斥的基本方法有哪些？
软件方法有：单标志法、双标志先检查法、双标志后检查法、皮特森算法。
硬件实现方法有：中断屏蔽法，硬件指令法
十一、什么是死锁？死锁产生的原因是什么？
死锁是指多个进程因为竞争资源造成的一种僵局，没有外力作用，这些进程都有无法向前继续推进。
死锁产生的原因是系统资源的竞争和进程推进顺序非法。
十二、死锁产生的必要条件是什么？
互斥、不可剥夺、请求保持、循环等待
十三、死锁的处理策略有什么？哪种方法最易于实现？哪种方法使资源利用率最高？
死锁预防、死锁避免、死锁的检测和解除。
其中银行家算法是经典的死锁避免算法。
死锁预防的方法是破坏死锁产生的四个必要条件。
预防死锁最容易实现；避免死锁使资源的利用率最高
十四、简述死锁定理
在资源分配图中找到分配满足的进程，然后消去其请求边与分配边
如果最后所有边都可以被消去 ，那么就是可以简化的，不存在死锁，反之存在死锁
十五、死锁的解除有哪几种方法？
资源剥夺法、撤销进程法、进程回退法。
十六、不同进程之间存在着什么关系？
进程之间存在同步与互斥的制约关系，
同步是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。
互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源
十七、PV操作描述：整形信号量、and型信号量、记录型信号量

十八、为什么要引入进程？
为了使程序在多道程序环境下能并发执行，并对并发执行的程序加以控制和描述，在操作系统中引入了进程概念。
十九、什么是多线程？多线程和多任务的区别是什么？
多线程是指在一个程序中可以定义多个线程并同时运行它们，每个线程可以执行不同的任务。
多线程与多任务的区别：多任务是针对操作系统而言的，代表操作系统可以同时执行的程序个数：多线程是针对一个程序而言的，代表一个程序可以同时执行的线程个数，而每个线程可以完成不同的任务。
二十、为什么要引入进程同步的概念？
在多道程序共同执行的条件下，进程与进程是并发执行的，不同进程之间存在不同的互相制约关系，为了协调进程之间的互相制约关系，引入了进程同步的概念。
二十一、简述银行家算法的工作原理
银行家算法的主要思想是避免系统进入不安全状态。
在每次进行资源分配时，
①它首先检查系统是否有足够的资源满足要求，
②若有则先进行分配，并对分配后的新状态进行安全性检查。
③若新状态安全，则正式分配上述资源，
④否则拒绝分配上述资源。
这样，它保证系统始终处于安全状态，从而避免了死锁的发生。
二十二、为什么要引入线程？
在操作系统中引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性，提高CPU的利用率。
二十三、PCB的作用是什么？PCB的组织方式有哪几种？
PCB的作用是使一个在多道环境下不能独立运行的程序，成为一个独立运行的基本单位，一个能与其他进程并发执行的进程。从OS的角度来看，OS是根据PCB来对并发执行的进程进行控制和管理的。
PCB的组织方式有两种：链接方式、索引方式
二十四、PCB中包含哪些信息？
进程标识符、处理机状态、进程调度信息、进程控制信息

第三章 内存管理
一、程序的创建步骤是什么？链接有哪几种类型？装入有哪几种模式？
程序的创建分为编译、链接、装入三个步骤
链接有静态链接、装入时动态链接、运行时动态链接。
装入模式有绝对装入（单道程序环境）、可重定位装入（多道程序环境）、动态运行时装入（多道程序环境）。
二、逻辑地址与物理地址的区别是什么？
逻辑地址是相对地址，是程序按照各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。
物理地址是内存中物理单元的集合，进程在运行时执行指令和访问数据都要通过物理地址从内存中存取。
三、内存保护有哪几种方法？
1.在CPU中设置一对上下限寄存器，存放用户作业在内存中的下限和上限地址。
2.采用重定位寄存器和界地址寄存器来实现这种保护。
四、内存连续分配方式有哪几种？
单一连续分配、固定分区分配、动态分区分配
五、动态分区的分配策略有哪几种？
首次适应：空闲分区按照地址递增的顺序进行查找，找到第一个满足要求的分区进行分配。
最佳适应：按容量递增的顺序进行查找分区，将第一个满足条件的进行分配。
最坏适应：空闲分区按照容量递减的次序进行查找，第一个满足条件的进行分配。
临近适应：分配内存时从上次查找结束的位置开始继续查找。
其中首次适应算法是最简单的也是最好的和最快的。
六、描述基本分页存储管理方式中地址的变换过程
不带快表：

1、根据逻辑地址分出页号和页内偏移量。
2、判越界，比较页号和页表长度，若越界则产生越界中断。
3、根据 页表项地址=页表始址+页号*页表项长度 查找页表得到该页的物理块号
4、根据物理块号和页内偏移量得到物理地址
带快表：

1、根据逻辑地址分出页号和页内偏移量。
2、查询快表是否命中，若命中则根据物理块号和页内偏移量得到物理地址
3、若不命中，判越界，比较页号和页表长度，若越界则产生越界中断。
4、根据 页表项地址=页表始址+页号*页表项长度 查找页表得到该页的物理块号
5、根据物理块号和页内偏移量得到物理地址
七、描述基本分段存储管理方式中地址的变换过程

不带快表：
1、根据逻辑地址分出段号和段内偏移量。
2、判越界，比较段号和段表长度，若越界则产生越界中断。
3、根据 段表项地址=段表始址+段号段表项长度 查找段表得到该段的始址b和段长c，比较偏移地址与c的大小判断是否越界
4、根据段表始址和段内偏移量得到物理地址
带快表：
1、根据逻辑地址分出段号和段内偏移量。
2、查询快表是否命中，若命中则根据快表得到该段的始址b和段长c，比较偏移地址与c的大小判断是否越界，若不越界则根据段表始址b和段内偏移量得到物理地址
3、若快表未命中，判越界，比较段号和段表长度，若越界则产生越界中断。
4、根据 段表项地址=段表始址+段号段表项长度 查找段表得到该段的始址b和段长c，比较偏移地址与c的大小判断是否越界
5、根据段表始址和段内偏移量得到物理地址
八、分段与分页的区别有哪些？
1.分页对用户不可见，分段对用户可见。
2.分页的地址空间是一维的，分段的地址空间是二维的。
3.分页、分段访问一个逻辑地址空间都需要两次访存（没引入快表的情况下）
4.分段更容易实现信息的共享和保护。
九、分段与分页的区别的优缺点分别有哪些？
分页管理：
优点：内存利用率高，无外部碎片，只有少量内部碎片。
缺点：不方便按照逻辑模块实现信息的保护和共享。
分段管理：
优点：很方便按照逻辑模块实现信息的保护和共享。
缺点：会产生外部碎片。
十、什么是局部性原理？
局部性分为时间局部性和空间局部性。
时间局部性是指一条指令执行不久之后就可能再次被执行，数据访问后不久数据可能再次被访问。
空间局部性是指一旦程序访问了某个存储单元，不久之后附近的存储单元也将被访问。
十一、请求分页管理方式中的地址变换机构是什么？
1、根据逻辑地址分出页号和页内偏移量。
2、查询快表是否命中，若命中则根据物理块号和页内偏移量得到物理地址
3、若不命中，判越界，比较页号和页表长度，若越界则产生越界中断。
4、根据 页表项地址=页表始址+页号页表项长度 查找页表得到该页的物理块号
5、若没有找到该页的页表，则到内存中寻找该页，若该页在内存中则调入页表，若该页不在内存中，则产生缺页中断，请求从外存中把该页调入内存。
6、根据物理块号和页内偏移量得到物理地址
十二、虚拟内存是怎么解决问题的，它会带来什么问题？
虚拟内存使用外存的空间来扩充内存的空间，通过一定的换入换出使得整个系统在逻辑上能够使用一个远远超出其物理内存大小的内存容量。
在换入换出调换页面时会访问外存，导致平均访存时间增加。
十三、简述缺页中断和其它中断的区别
(1) 普通中断是CPU 都是在一条指令执行完后，才检查是否有中断请求到达。然而缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。
(2) 缺页中断一条指令在执行期间，可能产生多次缺页中断。
十四、为什么要引入虚拟内存？
在物理扩展内存相对有限的条件下，应尝试以一些其他可行的方式在逻辑上扩充内存。
十五、描述段页式存储管理方式中地址的变换过程
1、根据逻辑地址分出段号、页号和页内偏移量。
2、判越界，比较段号和段表长度，若越界则产生越界中断。
3、根据 段表项地址=段表始址+段号段表项长度 查找段表得到页表长度c和页表始址d，比较偏移地址与c的大小判断是否越界。
4、若不越界则b根据 页表项地址=页表始址d+页号*页表项长度 查找页表得到物理块号b。
5.根据物理块号b和页内偏移量计算出物理地址。
十六、为什么说分段系统比分页系统更易于实现信息的共享和保护？
分页系统的每个页面是分散存储的，为了实现信息共享保护需要建立大量的页 表项；而分段系统的每个段都从0编址，并采用一段连续的地址空间，在实现共享和保护时，只需为要共享和保护的程序设置一个段表项，将其中的基址与内存一一对应就能够实现。
十七、虚拟存储器有哪些特征？其中最本质的特征是什么？
答：虚拟存储器有多次性、对换性、虚拟性三大特征。最本质的特征是虚拟性。
十八、请求分页中地址变换的过程是什么

第四章 文件管理
一、创建文件的基本步骤
①在文件系统中为文件找到空间。
②在目录中为新文件创建条目
二、文件的打开与关闭
操作系统维护一个包含所有打开文件信息的表，当用户需要一个文件操作时，可通过该表的一个索引指定文件。操作OPEN会根据文件名搜索目录，并将目录条目复制到文件打开表，OPEN通常返回一个指向文件打开表中的一个条目的指针，通过使用该指针进行所有I/O操作，以简化步骤并节省资源。
三、什么是文件的逻辑结构，文件的逻辑结构如何分类?
文件的逻辑结构是指从用户的观点出发看到的文件的组织形式。
文件的逻辑结构可以分为记录式文件（顺序文件、索引文件、索引顺序文件）和流式文件。
四、什么是文件控制块？
文件控制块是用来存放控制文件需要的各种信息的数据结构，以实现按名存取。
FCB主要包括基本信息、存取控制信息、使用信息。
五、文件的共享有哪几种方式？
1.基于索引节点的共享方式（硬链接）：硬链接是多个指针指向一个索引结点，保证只要还有一个指针指向索引节点，索引节点就不能删除。
2.利用符号链实现文件共享（软链接）：软连接就是把到达共享文件的路径记录下来，当要访问文件时，根据路径寻找文件。
六、什么是文件的物理结构，文件的物理结构如何分类，各有什么优缺点？
文件的物理结构是指文件在物理存储设备上是如何分配和组织的。
分为连续分配、链接分配、索引分配
连续分配：
优点：速度快，可以随机访问
缺点：要求连续的存储空间，容易产生碎片，不利于文件扩充
链接分配：
优点：易于文件扩充，不要求连续空间
缺点：只适合顺序访问，不适合随机访问
索引分配：
优点：既支持顺序访问，又支持随机访问
缺点：索引表会占用一定空间
七、文件存储空间管理方法
空闲表法、空闲链表法、位示图法、成组链接法。
八、磁盘读写时间的组成
磁盘读写时间由寻找时间、延迟时间、传输时间组成。
寻找时间：活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间。
延迟时间：磁头定位到某一次到扇区所需要的时间，Tr=1/2r
传输时间：从磁盘读出或向磁盘写入数据经过的时间。Tr=b/rN
九、何谓数据项、记录和文件？

1. 数据项分为基本数据项和组合数据项。基本数据项描述一个对象某种属性的字符集，具有数据名、数据类型及数据值三个特性。组合数据项由若干数据项构成。
2. 记录是一组相关数据项的集合，用于描述一个对象某方面的属性。
3. 文件是具有文件名的一组相关信息的集合。

第五章 输入、输出管理
一、常见的四种I/O控制方式是什么？分别介绍
常见的I/O控制方式有程序直接控制方式、中断驱动方式、DMA方式、通道控制方式。
1.程序直接控制方式：计算机从外部设备读取数据到存储器，对于每次读入的数据，CPU都要对外设状态进行状态检查，以确定该字已在I/O设备控制器的数据寄存器中。
2.中断驱动方式：允许I/O设备主动打断CPU的运行并请求服务，从而解放CPU，使得其向I/O控制器发送读命令后可以继续做其他有用的工作
3.DMA方式：在I/O设备和内存之间开辟直接的数据通路，传输数据块，彻底接放CPU
4.I/O通道方式：I/O通道是专门负责输入/输出的处理机，可以将CPU对数据块的读（或写）及有关控制和管理减少为以组为单位的干预。
二、什么是I/O调度？
通过I/O调度改善系统的整体性能，使得进程之间公平共享设备访问，减少I/O完成所需要的平均等待时间。
三、缓冲区的作用（什么是缓冲区）
为了缓解CPU与设备的速度不匹配的矛盾、提高CPU与I/O设备之间的并行性、减少对CPU的中断频率。
四、SPOOLING技术的目的是什么？
缓和CPU与I/O的速度差异矛盾。
五、SPOOLING系统的工作过程是什么？
工作过程：
输入进程：将用户要求的数据从输入机通过输入缓冲区送到输入井中，当CPU需要数据时，直接将输出井中的数据送入内存
输出进程：将用户要求输出的数据先送到输出井中，待输出设备空闲时，再将输出井中的数据通过输出缓冲区送到输出设备。
六、什么是独占设备、共享设备、虚拟设备？
独占设备：一个时段只能分配给一个进程
共享设备：可同时分配给多个进程使用的设备
虚拟设备：采用某种技术处理将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用。
七、什么是设备独立性，好处是什么？如何实现设备的独立性？
应用程序独立于具体使用的物理设备，应用程序以逻辑设备名请求使用某类设备。
优点：
①设备分配时灵活。
②易于实现I/O重定向。
八、有哪些常见的缓冲模式？
单缓冲、双缓冲、循环缓冲、缓冲池
九、通道采用交叉连接的原因是什么？
通道采用交叉连接是为了缓解通道不足引起的“瓶颈”现象，增加I/O与主存之间的通路，既解决瓶颈现象，又提高系统的可靠性。
十、通道与一般处理机的区别是什么？
1、通道类型单一，只局限于I/O操作有关的指令。
2、通道没有自己的内存。
十一、RAID的优点有什么？
1.可靠性高。
2.磁盘I/O速度高。
3.性价比高。
十二、说明DMA的工作流程。
①向磁盘控制器发送读/写命令，放入命令寄存器CR中。
②发送读入/写入的数据的内存起始目标地址，送入内存地址寄存器MAR。
③发送读入/写入的数据的字节数，送入数据计数器DC。
④将磁盘中的源地址直接送至DMA控制器的I/O控制逻辑上。
⑤启动DMA控制器进行数据传输，cpu去处理其他任务。
十三、为什么要引入高速缓冲？何谓高速缓冲？
为提高磁盘I/O的速度，便引入了磁盘高速缓冲。
磁盘高速缓冲是指利用内存中的存储空间，暂存从磁盘中读出的一系列盘块中的信息。
十四、廉价磁盘冗余阵列是如何提高对磁盘的访问速度和可靠性的？
廉价磁盘冗余阵列RAID是利用一台磁盘阵列控制器，统一管理和控制一组（几台到几十台）磁盘驱动器，组成高度可靠快速大容量的磁盘系统。
用户数据和系统数据可分布在阵列的所有磁盘中，并采取并行传输方式，大大减少数据传输时间和提高了可靠性，

操作系统简答题补充：
1、文件的几种操作
创建文件：
①为新文件分配必要的外存空间。
②在文件系统的目录中，为之建立一个目录项。
删除文件
①系统应 先从目录中找到要删除文件的目录项，使之成为空项。
②然后回收该文件所占用的存储空间。
读、写文件：
先查找目录，找到指定文件的目录项，再利用目录中的指针进行读/写操作。
2、什么是隐式连接分配，什么是显式链接分配？
隐式连接分配：在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针，且在每个盘块中都含有一个指向下一个盘块的指针。
显式链接分配：把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。

3、什么是索引块？
索引分配方式为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。
4、什么是文件控制块FCB？
为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为FCB. 文件管理程序可借助于文件控制块中的信息，对文件施以各种操作。
在文件控制块中，通常应含有三类信息，
即基本信息、存取控制信息及使用信息。
5、什么是目录？
文件目录是文件控制块的有序集合。
6、什么是索引节点？
使文件描述信息单独形成一个称为索引结点的数据结构， 简称为i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i 结点的指针所构成。

7、常用的目录结构形式有哪些？
常用的目录结构形式有单级目录、两级目录和多级目录。
8、目录的实现方式有哪几种？
①线性结构：使用存储文件名和数据块指针的线性表。
②哈希表：根据文件名得到一个值，然后返回一个指向线性列表中元素的指针。
9、文件存储空间的管理方法有哪几种？
空闲表法、空闲链表法、位示图法、成组链接法。
空闲表法：系统为空闲区建立一张空闲盘块表存放每个空闲区第一个盘块号、该区的空闲盘块数等信息。
空闲链表法：将所有的空闲盘区拉成一条空闲链。
位示图法：用二进制来表示一个盘快的使用情况，每一个盘块都有一个二进制位与之对应。
成组链接法：

第三章 内存管理
1、内存的连续分配方法和回收方法

2、如何将一个用户源程序变为一个在内存中执行的程序？
①编译：将用户的源代码编译成若干个目标模块。
②链接：将一组目标模块以及他们所需要的库函数链接在一起，形成一个完整的装入模块。
③装入：由装入程序将装入模块装入内存。
3、什么是“紧凑”，紧凑操作之后要注意什么？
通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，
在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
第二章
1、程序顺序执行时的特征和并发执行的特征？
顺序执行：顺序性、封闭性、可再现性。
并发执行：间断性、失去封闭性、不可再现性。
2、信号量机制
①整型信号量
wait(S)： while S<=0 do no-op；
S:=S-1；
signal(S)： S:=S+1；
②记录型信号量

（以下部分只需理解）

③AND型信号量

3.消息缓冲队列的通信机制

计算机网络部分

计算机网络面试题
IP和mac的区别？
IP是网络层地址，MAC是数据链路层且地址是全球唯一的。
登陆baidu.com,简述协议过程
1、解析baidu.com域名对应的ip地址（ARRP(获得网关地址) - DNS（获得IP地址））
2、得到baidu.com对应的IP后，客户端会发送TCP的三次握手，进行连接；
3、连接成功后，使用HTTP协议发送请求数据包给WEB服务器；
4、web服务器受到数据请求后，通过查询自己的服务器的到对应的结果，并将结果原路返回给浏览器；
5、浏览器收到数据后，通过浏览器的渲染结果来显示网页；
6、浏览器关闭TCP，即四次挥手离别。

hub,switch,router属于OSI哪一层？
hub是集线器属于物理层，交换机是数据链路层，router是路由器网络层的，负责不同网络结合。
子网掩码和IP地址怎么理解？

在国际互联网(Internet)上有成千百万台主机（host），为了区分这些主机，人们给每台主机都分配了一个专门的“地址”作为标识，称为IP地址。子网掩码的作用是用来区分网络上的主机是否在同一网络段内。子网掩码不能单独存在，它必须结合IP地址一起使用。子网掩码只有一个作用，就是将某个IP地址划分成网络地址和主机地址两部分。
ipv4,ipv6的区别？

IPV6更安全，更大的存储空间。

XML和HTML区别?

跨平台的标记语言，重在储存数据。HTML重在存储界面显示内容

OSI模型全称？

Opening System Interconnection - Reference Model
DNS工作过程？

应用层协议，使用UDP。分为迭代查询和递归查询。采用分布式集群的工作方式，防止单点故障，增加通信容量。
迭代：主机访问本地域名服务器，若缓存没有IP则本地域名服务器进一步向其他根域名服务器查询。
递归：主机分别向多个服务器发出查询请求。

UDP的优点？

发送前无需连接，减少了开销和时延，首部开销小，无拥塞控制，方便实时应用，不保证可靠交付，无需维持连接状态表。UDP的可靠性要通过应用层来控制。

Q：拥塞控制和流量控制都是什么，两者的区别？
流量控制是端到端的控制，例如A通过网络给B发数据，A发送的太快导致B没法接收(B缓冲窗口过小或者处理过慢)，这时候的控制就是流量控制，原理是通过滑动窗口的大小改变来实现。
拥塞控制是A与B之间的网络发生堵塞导致传输过慢或者丢包，来不及传输。防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不至于过载。拥塞控制是一个全局性的过程，涉及到所有的主机、路由器，以及与降低网络性能有关的所有因素。
Q：谈谈对TCP/IP协议的理解

简述计算机网络分层的好处
计算机网络是一个复杂的系统，采用层次化结构的方法来描述它，可以将复杂的网络间题分解为许多比较小的、界线比较清晰简单的部分来处理；
一灵活性好。
二 各层之间是独立的。
三易于实现和维护。
四能促进标准化工作。
十五.简述你对面向连接服务的理解?

在面向连接服务中， 通信前双方必须先建立连接， 分配相应的资源（如缓冲区）， 以保证通
信能正常进行， 传输结束后释放连接和所占用的资源。因此这种服务可以分为连接建立、数据传
输和连接释放三个阶段。例如TCP就是一种面向连接服务的协议。

在无连接服务中， 通信前双方不需要先建立连接， 需要发送数据时可直接发送，把每个带有
目的地址的包（报文分组） 传送到线路上， 由系统选定路线进行传输。这是一种不可靠的服务。
这种服务常被描述为“尽最大努力交付" (Best-Effort-Delivery), 它并不保证通信的可靠性。例如
IP、UDP就是一种无连接服务的协议。

十六简述你对客户服务器工作方式的理解

互联网应用系统采用客户/服务器模式的主要原因是网络资源分布的不均匀性

十七什么是 MAC 地址和 IP 地址，分析他们的区别和两者之间的转换机制。

1.对于IP地址，相信大家都很熟悉，即指使用TCP/IP协议指定给主机的32位地址。IP地址由用点分隔开的4个8八位组构成，

2　对于MAC地址，由于我们不直接和它接触，所以大家不一定很熟悉。MAC地址也叫物理地址、硬件地址或链路地址，由网络设备制造商生产时写在硬件内部。这个地址与网络无关，也即无论将带有这个地址的硬件（如网卡、集线器、路由器等）接入到网络的何处，它都有相同的MAC地址，MAC地址一般不可改变，不能由用户自己设定。
TCP协议是面向连接的,但TCP使用的IP协议却是无连接的.这两种协议都有哪些主要的区别.

IP协议提供的是不可靠的,面向非连接的服务
TCP协议提供的是可靠的,面向连接的服务
TCP协议实现的是主机应用程序之间的通信,IP协议只实现主机间的通信
TCP协议是以IP协议为基础实现的,给应用层提供服务;IP协议为TCP协议提供服务.
简单来说,IP协议负责将数据从一台主机传输到另一台主机,而TCP协议保证传输的正确性.

假定所有的路由器和主机都正常工作,所有软件也都正常运行.那么是否还有可能会把分组投递到错误的目的地址?

有可能.因为分组在传输过程中可能遭到破坏,分组的校验和并不能检查出所有的差错.如果分组的目的地址字段在传输过程中改变,但整个分组的校验和检验仍然正确,分组将会被投递到错误的目的地址,并可能被接收为正确的分组.尽管这种可能性很小,但仍可能发送.

应用层的协议如HTTP,FTP,SMTP,POP3分别使用的是运输层的什么协议?Why?

都是运行在TCP协议上的.因为它们都需要数据传输的可靠性,而TCP协议提供了面向连接的可靠数据传输服务,这样使得高层协议不需要考虑数据传输的可靠性问题.如果采用无连接,不可靠的UDP协议(例如TFTP高层协议),高层协议就需要采取比较复杂的机制来进行确认,重传以保证数据传输的可靠性.

单工、半双工、全双工

单工：又称为单向通信，即只能有一个方向的通信而没有反方向的交互。例：无线电广播，电视广播
半双工：又称为双向交替通信，即通信的双方都可以发送信息，但不能双方同时发送（当然也就不能同时接受）
全双工：又称为双向同时通信，即通信的双方可以同时发送和接受信息。
单工只要一条信道，而半双工和全双工需都需要两条信道（每个方向各一条）。

频分复用 时分复用 波分复用 码分复用

频分复用：给每个信号分配唯一的载波频率并通过单一媒体来传输多个独立信号的方法。
时分复用：把多个信号复用到单个硬件传输信道，它允许每个信号在一个很短的时间使用信道，接着再让 下一个信号使用。
波分复用：就是光的频分复用。用一根光纤同时传输多个频率很接近的光载波信号。
码分复用：码分复用是用一组包含互相正交的码字的码组携带多路信号。每一个用户可以在同样的时间使 用同样的频带进行通信。由于各用户使用经过特殊挑选的不同码型，各用户之间不会造成干扰，因此这种 系统发送的信号有很强的抗干扰能力。
频分复用如何避免各路信号间的干扰

频分复用要求总频率宽度大于各个子信道频率之和，同时为了保证各子信道中所传输的信号互不干扰，应在各子信道之间设立隔离带（也就是保护频带，即插入一些 空白的频段 ），这样就保证了各路信号互不干扰

CSMA/CD 协议 如果两端同时发送信息会出现什么情况，为什么？
两端都检测到冲突，均停止发送数据，等待一个随机时间再重发

连接两个局域网需要用什么设备，在哪一层

首先，来区分以下几个常见设备：

物理层设备：中继器，集线器 —— 均不能隔离冲突域和广播域

中继器（RP repeater）：是工作在物理层上的连接设备。适用于完全相同的两个网络的互连，主要功能是通过对数据信号的重新发送或者转发，来扩大网络传输的距离。 中继器是对信号进行再生和还原的网络设备，设计的目的是给你的网络信号以推动，以使它们传输得更远。

集线器(Hub)：“Hub”是“中心”的意思，集线器的主要功能是对接收到的信号进行再生整形放大，以扩大网络的传输距离，同时把所有节点集中在以它为中心的节点上。它可以视作多端口的中继器，若它侦测到碰撞，它会提交阻塞信号。

链路层设备：网桥，交换机 —— 隔离冲突域不能隔离广播域

网桥（Bridge） : 是早期的两端口二层网络设备，用来连接不同网段。网桥的两个端口分别有一条独立的交换信道，不是共享一条背板总线，可隔离冲突域。网桥比集线器（Hub）性能更好，集线器上各端口都是共享同一条背板总线的。后来，网桥被具有更多端口、同时也可隔离冲突域的交换机（Switch）所取代。

网桥（Bridge）像一个聪明的中继器。中继器从一个网络电缆里接收信号， 放大它们，将其送入下一个电缆。相比较而言，网桥对从关卡上传下来的信息更敏锐一些。网桥是一种对帧进行转发的技术，根据MAC分区块，可隔离碰撞。网桥将网络的多个网段在数据链路层连接起来。

网桥也叫桥接器，是连接两个局域网的一种存储/转发设备，它能将一个大的LAN分割为多个网段，或将两个以上的LAN互联为一个逻辑LAN，使LAN上的所有用户都可访问服务器。

扩展局域网最常见的方法是使用网桥。最简单的网桥有两个端口，复杂些的网桥可以有更多的端口。网桥的每个端口与一个网段相连。

交换机（Switch） 意为“开关”是一种用于电（光）信号转发的网络设备。它可以为接入交换机的任意两个网络节点提供独享的电信号通路。最常见的交换机是以太网交换机。其他常见的还有电话语音交换机、光纤交换机等。

交换是按照通信两端传输信息的需要，用人工或设备自动完成的方法，把要传输的信息送到符合要求的相应路由上的技术的统称。交换机根据工作位置的不同，可以分为广域网交换机和局域网交换机。广域的交换机就是一种在通信系统中完成信息交换功能的设备，它应用在数据链路层。交换机有多个端口，每个端口都具有桥接功能，可以连接一个局域网或一台高性能服务器或工作站。实际上，交换机有时被称为多端口网桥。

网络交换机，是一个扩大网络的器材，能为子网络中提供更多的连接端口，以便连接更多的计算机。随着通信业的发展以及国民经济信息化的推进，网络交换机市场呈稳步上升态势。它具有性价比高、高度灵活、相对简单和易于实现等特点。以太网技术已成为当今最重要的一种局域网组网技术，网络交换机也就成为了最普及的交换机。

网路层设备：路由器 —— 隔离冲突域和广播域

路由器 又可以称之为网关设备。对不同的网络之间的数据包进行存储、分组转发处理，其主要就是在不同的逻辑分开网络。而数据在一个子网中传输到另一个子网中，可以通过路由器的路由功能进行处理。在网络通信中，路由器具有判断网络地址以及选择IP路径的作用，可以在多个网络环境中，构建灵活的链接系统，通过不同的数据分组以及介质访问方式对各个子网进行链接。路由器在操作中仅接受源站或者其他相关路由器传递的信息，是一种基于网络层的互联设备。

比如你买了个路由器，有2台电脑，在路由器的这边你家就是一个局域网，而在路由器的那边却是一个互联网，所以路由器可以连接两个不同类型的网络。

综上可得，连接两个局域网，即连接两个同类型网络，需要使用网桥或者交换机，工作在数据链路层

什么是滑动窗口协议

滑动窗口协议，是TCP使用的一种流量控制方法。该协议允许发送方在停止并等待确认前可以连续发送 多个分组。由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输。

流量控制在哪些层实现

流量控制就是要控制发送方数据传输的速率，使接收方来得及接收

传输层

TCP流量控制，利用滑动窗口机制控制发送方的速度
数据链路层/传输层

ARQ停等协议

IPV4和IPV6的位数

IPV4是32位；IPV6是128位

IPv4地址缺乏的解决办法(替代方案)

NAT 网络地址转换：根据NAT转换表，NAT路由器将 专用网上的IP地址 和 因特网上的外部全球唯一IP地址 进行转化
CIDR 无分类编址，构成超网：CIDR消除了传统的A类、B类和C类地址以及划分子网的概念，融合子网地址和子网掩码，方便子网划分，把网络前缀都相同的连续IP地址组成一个CIDR地址块
IPv4和IPv6如何相互通信？

32位的IPV4地址空间已分配殆尽，CIDR、NAT治标不治本，IPV6从根本上解决地址耗尽问题。

IPV4向IPV6过渡的策略：

双栈协议：同时启用IPV4和IPV6协议栈
隧道技术：将其他协议的数据帧或包重新封装然后通过隧道发送

为什么要三次握手，两次为什么不行？
如果只有两次：客户机首先请求与服务器连接；服务器同意连接同时准备内存资源，并发报文给客户机，万一这个报文中途丢失，客户机一直不给服务器响应，基于两次握手，服务器认为已经成功建立连接，就一直等待，实际上根本没通。所以需要三次握手才靠谱

有哪些交换技术？

电路交换
优点：传输时延小、没有冲突、实时性强；
缺点：独占式信道利用率低、建立连接时间长、灵活性差。

报文交换
优点：无需建立连接、信道利用率高；
缺点：转发时延长、要求的缓存空间大。

分组交换（无连接的数据报、面向连接的虚电路）
优点：无需建立连接、信道利用率高、简化了存储管理、加速了传输；
缺点：存在发送时延、可能会存在分组失序、丢失、重复。

虚电路和数据报有什么区别？

虚电路技术

主要特点：在数据传输之前必须通过虚呼叫设置一条虚电路，可靠由网络来保证，它适用于两端之间长时间的数据交换。 有连接。分组均按同一路由进行转发。分组按顺序到达。当接电出故障，所有通过故障结点的虚电路均不能工作。

优点：可靠、保持顺序；

缺点：如有故障，则经过故障点的数据全部丢失.

数据报

特点：在数据报方式中，每个分组被称为一个数据报，在目的地需要重新组装报文，可靠性由用户主机来保证。 无连接。分组独立选择路由进行转发。分组到达顺序不一定。接电

优点：如有故障可绕过故障点。

缺点：不能保证按顺序到达，丢失不能立即知晓。

从单独的通信网来说,采用有连接的虚电路方式,或是采用无连接的数据报方式都是可以的。但是对于网间互联或IP业务,则是采用数据报方式有利。因为数据报方式可以最大限度地节省对网络节点的处理要求,不需要采取可靠性措施或流量控制,不需要预先建立逻辑的连接路径。

它在遇到网内拥塞等情况时,可以迅速改变路由,因而适用于各种不同类型的网络。在国际计算机互联网(因特网)中,用的就是数据报方式。虚电路适合于交互式通信,数据报方式更适合于单向地传送短信息。
TCP中的流量控制和拥塞控制

注：tcp协议如何保证传输的可靠性

流量控制主要针对的是端到端传输中控制流量大小并保证传输可靠性（未收到ack就不滑动）。流量控制往往是指点对点通信量的控制，所要做的是抑制发送端发送数据的速率。

拥塞控制主要是一个全局性过程，涉及到所有主机，路由器，以及与降低网络传输性能有关的所有因素。防止过多的数据注入到网络中。如果有发生丢包则通过拥塞控制减小窗口，确定出合适(慢启动 拥塞避免 快重传 快恢复)的拥塞窗口（增性加乘性减）。

注：
1). 慢启动：不要一开始就发送大量的数据，先探测一下网络的拥塞程度，也就是说由小到大逐渐增加拥塞窗口的大小;

2). 拥塞避免：拥塞避免算法让拥塞窗口缓慢增长，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍，这样拥塞窗口按线性规律缓慢增长。

3). 快重传：快重传要求接收方在收到一个 失序的报文段 后就立即发出 重复确认（为的是使发送方及早知道有报文段没有到达对方）而不要等到自己发送数据时捎带确认。快重传算法规定，发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段，而不必继续等待设置的重传计时器时间到期。

4). 快恢复：快重传配合使用的还有快恢复算法，当发送方连续收到三个重复确认时，就执行“乘法减小”算法，把ssthresh门限减半，但是接下去并不执行慢开始算法：因为如果网络出现拥塞的话就不会收到好几个重复的确认，所以发送方现在认为网络可能没有出现拥塞。所以此时不执行慢开始算法，而是将cwnd设置为ssthresh的大小，然后执行拥塞避免算法。

5 TCP可靠传输

TCP可靠传输
使用机制：校验、序号、确认、重传

校验：TCP的校验机制和UDP相同；

序号：TCP首部的序号字段用来保证数据能有序提交到应用层（只保证有序发送，不保证有序到达）；

确认：TCP采用累积确认，确认号是期望收到对方下一个报文段的数据的第一个字节的序号；

重传：导致TCP重传的两种事件：超时和冗余ACK

6 Get与POST的区别

GET与POST是我们常用的两种HTTP Method，二者之间的区别主要包括如下五个方面：

(1). 从功能上讲，GET一般用来从服务器上获取资源，POST一般用来更新服务器上的资源；

(2). 从REST服务角度上说，GET是幂等的，即读取同一个资源，总是得到相同的数据，
而POST不是幂等的，因为每次请求对资源的改变并不是相同的；
进一步地，GET不会改变服务器上的资源，而POST会对服务器资源进行改变；

(3). 从请求参数形式上看，GET请求的数据会附在URL之后，即将请求数据放置在HTTP报文的 请求头 中，以?分割URL和传输数据，参数之间以&相连
。特别地，如果数据是英文字母/数字，原样发送；否则，会将其编码为 application/x-www-form-urlencoded MIME 字符串(如果是空格，转换为+，如果是中文/其他字符，则直接把字符串用BASE64加密，得出如：%E4%BD%A0%E5%A5%BD，其中％XX中的XX为该符号以16进制表示的ASCII)；
而POST请求会把提交的数据则放置在是HTTP请求报文的 请求体 中。

(4). 就安全性而言，POST的安全性要比GET的安全性高，因为GET请求提交的数据将明文出现在URL上，而且POST请求参数则被包装到请求体中，相对更安全。

(5). 从请求的大小看，GET请求的长度受限于浏览器或服务器对URL长度的限制，允许发送的数据量比较小，而POST请求则是没有大小限制的。

C++

C++面试题
C++

c++和c中字符串区别？

c++是类，c中是基本类型函数。

C++的特点是什么？

封装，继承，多态。支持面向对象和面向过程的开发。

C++的异常处理机制？

抛出异常和捕捉异常进行处理。（实际开发）

c和c++，java的区别?

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

纯虚函数？

被virtual修饰的成员函数，再基类不能实现，而他的实现放到派生类中实现。

什么是内存泄漏？

内存泄漏（Memory Leak）是指程序中己动态分配的堆内存由于某种原因程序未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果。

指针和引用的区别？

指针是一个存储地址的变量，该地址为内存的一个存储单元；引用是原变量的一个别名；
指针可以为空，而引用不能为空；
指针可以有多级，而引用只能有一级；
指针可以重新赋值，而引用只能初始化一次
sizeof引用得到的是变量大小，而sizeof指针得到的是指针本身大小
将引用作为函数返回值的好处是？
在内存中不会产生被返回值的副本，同时不能返回局部变量的引用，因为随着调用结束局部变量会被销毁。

三种传参方式？

值传递
传递的是实参的一个拷贝，修改形参不会改变实参值。
地址传递
传递的是实参地址的一个拷贝，修改形参会改变实参值。
引用传递
传递的是实参的一个别名，修改形参会导致改变实参。
被调用函数的形参只有在被调用时才会临时分配存储单元，一旦调用结束则释放内存。

const作用？

被const修饰符修饰的变量不能被修改。const *x表明x数据是常量，不能修改；*const x表明指针本身是常量，x的指针不能指向其他内存地址，x本身可被修改；*const *x表明x本身数据和地址都不能被修改。

static作用？

被static修饰符修饰的变量在整个文件中都是可见的，而在文件外是不可见的。该变量在全局数据区分配内存。C++中由程序运行new出的动态数据存放在堆区，而函数内部局部变量存放在栈区。
静态局部变量：在函数内部定义static变量，第一次运行到这里初始化，存储到全局数据区，下一次执行到这里不会再重新初始化。
static变量如果没有显式初始化，默认初始值为0。
静态函数不能被其他函数所调用。

面向对象的三个要素(基本特征)？

1、封装：将客观事物封装成类，隐藏实现细节，模块化代码。
2、多态：实现多态的两种方式——覆盖(重写)和重载。
覆盖是子类重新定义父类的虚函数，与多态真正相关。当子类重新定义了父类的虚函数后，父类指针根据赋给它的不同的子类指针，动态的调用属于子类的该函数，这样的函数调用在编译期间是无法确定的（调用的子类的虚函数的地址无法给出）。因此，这样的函数地址是在运行期绑定的（晚绑定）。
重载是存在多个同名函数，但是函数的参数个数不同。这些函数实际上成为了不同的函数，对它们的调用在编译期间就已经确定，属于早绑定，与多态无关。
3、继承：子类继承父类功能，对父类功能进行扩展。

结构体和联合有什么区别？

结构和联合都是由多个不同的数据类型成员组成, 但在任何同一时刻, 联合中只存放了一个被选中的成员（所有成员共用一块地址空间）, 而结构的所有成员都存在（不同成员的存放地址不同）。
对于联合的不同成员赋值, 将会对其它成员重写, 原来成员的值就不存在了, 而对于结构的不同成员赋值是互不影响的。
C++是不是类型安全的语言？

不是。不同类型间指针可以强制互转。

const与#define区别？

const修饰常量受到强制保护，程序更健壮，而且const修饰的常量有数据类型，有类型安全检查。

基类的析构函数为什么是虚函数？

为了防止派生类析构函数未执行，造成资源泄露。

#include尖括号和双引号区别？

<>是标准头文件，“”是非系统头文件

为什么有了指针，还要使用引用？

为了支持运算符的重载。更加方便。

如何避免野指针？

声明指针记得初始化，暂时不用就指向NULL；使用malloc分配内存，必须经过显式释放(free)，避免内存泄漏。

STL
什么是STL？
STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。
STL有什么特点？
STL的一个重要特点是数据结构和算法的分离。
例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组；
STL另一个重要特性是它不是面向对象的。

JAVA

Java面试题
Java

java的特点？

一次编译到处运行，没有指针，完全对象化，面向对象（封装、继承、多态）。

java常用术语

JavaEE：Java Platform Enterprise Edition，是Sun公司为企业级应用推出的标准平台。
J2EE：Java 2 Platform，Enterprise Edition，是JavaEE以前的叫法。
JDBC：Java DataBase Connectivity，Java数据库连接。
JNDI：Java Naming and Directory Interface，提供一个目录系统，使得开发人员可以通过名称来访问资源。
EJB：Enterprise JavaBean，用来构建一个可以管理的服务器组件。
Servlet：Java编写的服务端程序，可以动态修改web内容。
JSP：Java Server Pages，Sun主导的一种动态网页技术标准，JSP部署于网络服务器上，可以响应客户端请求，并返回相应内容。
RMI：Remote Method Invocation，使得客户端可以像调用本地对象一样调用远程服务器上的方法。和RPC(Remote Procedure Call Protocol)不同，RMI只适用于Java，返回结果也有区别。RML在文件传输时，需要进行序列化serial,转换为二进制才能被servlet传输
XML：Extensible Markup Language，用于传输和存储数据
JMS：Java Message Service，Java平台面向消息中间件的一个服务，用于在分布式系统或应用程序间传递服务。
JTA：Java Transaction API，事务管理组件。
Weblogic：Oracle公司推出的商业化JavaEE服务器

java怎么处理对象分配和释放的？

java把内存分为堆栈空间存储，在堆中new的空间不用自己收回，自动垃圾收回。

JVM

不同于C++需要编程人员手动释放内存，Java有虚拟机，因此Java不需要程序员主动去释放内存，而是通过虚拟机自身的垃圾回收器(Garbage Collector-GC)来进行对象的回收。Java语言由于有虚拟机的存在，实现了平台无关性，在任意平台都是通过将代码转换为字节码文件，从而在平台下的虚拟机中运行代码的。

名词解释：

内存区域分布
虚拟机栈：存放每个方法执行时的栈帧，一个方法调用到完成就对应栈帧在虚拟机栈中入栈和出栈的过程。

本地方法栈：和虚拟机栈类似，不过是为Java中native方法服务的。平时所说的“栈内存”指的就是虚拟机栈和本地方法栈的合称。

程序计数器：当前线程执行字节码的行号指示器，字节码解释器工作依赖于它。占用较小的内存空间，不会出现OOM。

堆：即所谓的“堆内存”。JVM所管理最大的一块内存，被所有线程共享。唯一作用就是给对象实例分配内存空间，在分代回收算法中的新生代老年代就在于堆中。

方法区(也称为永久代)：不在堆中，被各个线程共享，存储已被JVM加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。其中包括常量池。

另：直接内存，不属于JVM内存区域，与NIO联系紧密，不受JVM内存大小限制。

JVM垃圾回收机制

何时进行垃圾回收？

GC本质上是一道守护进程(Daemon Thread)，不停的检测堆中是否有不可达对象并释放内存，因此GC在何时发生其实我们是无法预测的。GC通过调用对象的finalize()方法来摧毁对象。

不可达对象的判定：根搜索算法。JVM中有一系列设定的GC Roots，当一个对象到任意一个GC Root都没有引用链时，则说明此对象不可达。

JVM中的垃圾回收算法

1、标记-清除算法

最基础的算法，GC会判断堆中对象是否不可达，如果满足清理条件（查看该对象是否有必要执行finalize()方法，有无必要的标准是该对象有没有被调用过finalize方法或该对象有没有覆盖finalize()方法，因为finalize()只能被调用一次），则给这个对象进行标记，将对象放在F-queue队列。此时除非对象在finalize()方法中重新获得了引用，否则它就会被清除掉。

2、复制算法

将内存分为大小相等的两块，当对象不可达后并不是及时清理，而是等待正在使用的内存满了之后，将该内存内还存活的对象整体复制到另一块内存中，复制结束后再清理掉原内存块中的所有内容。这种方法的优点是快速，但牺牲了一半的内存。方法的改进版(事实上也是虚拟机的做法)是只在新生代空间使用复制算法，并且由于新生代对象生命周期往往很短，因此又将新生代区域分为Eden和Survivor空间。其中Eden分配的空间又比Survivor大出很多，从而节省内存空间。如果存活对象过多，使得Survivor区也满，那么就会转移Survivor区对象到老年代。

3、标记-整理算法

标记过程与1一样，将1中的清除过程换成了整理，即将内存中存活的对象归拢到一边，使得内存更“紧凑”一些，整理之后将边界之外的对象清理掉。这种算法是为了防止2算法中出现存活率100%的极端情况，那么复制就没有止境了。

4、分代算法

新生代采用2算法，老年代采用1或3算法。这是由他们的特点决定的，新生代注定了其中很多对象生命周期转瞬即逝，因此复制算法移动的存货对象并不是很多。而老年代存活率较高，只能采用1、3来执行，提高效率。

JVM参数相关

可以调整堆内新生代老年代比例
可以调整对象移入老年代的年龄
可以调整堆内存大小
可以设置每个栈大小
可以设置堆内分区大小
可选择垃圾回收方式

JVM类加载机制

双亲委派模型。

类加载器(ClassLoader)用来实现类的加载动作。JVM中只存在两种不同的类加载器：启动类加载器和其他类加载器。

启动类加载器：即Bootstrap ClassLoader。由C++编写，在JVM内部。其他类加载器都由Java编写，在JVM外部，全部继承于抽象类java.lang.ClassLoader。

类加载器之间的层次关系，称为双亲委派模型。

顶层为启动类加载器，下边为扩展类加载器，再下为应用程序类加载器，其中包含多种自定义类加载器。

如果一个类加载器收到了加载类的请求，它首先不会自己去加载，而是委派给它的父加载器去执行。层层委派之后，到了顶层由启动类加载器加载，只有当父加载器反馈无法加载此请求，才会让子加载器去加载。这种结构使得Java类型体系中的加载机制清晰准确，不易造成混乱。

有一种双亲委派模型的异常情况，即类似启动类加载器这种基础的类加载器，本应默认为所有类适用的加载器，但由于一些环境下调用SPI(Service Provider Interface)，绕过双亲委派模型的层次结构使得父加载器委派子加载器去完成类加载动作。

还有一种情况，即为了实现模块的动态性、热部署，不再使用双亲委派模型，而是使用更加复杂的网状结构。OSGi技术即是类加载器网状结构的一个最佳实践。

如何判断当前系统内是否存在死锁？

可以打印当前的内存快照，可以看到快照中有deadLock对象，所在的方法，请求被锁的资源，从而进一步分析死锁原因。

ThreadLocal

ThreadLocal，很多地方叫做线程本地变量，也有些地方叫做线程本地存储，其实意思差不多。可能很多朋友都知道ThreadLocal为变量在每个线程中都创建了一个副本，那么每个线程可以访问自己内部的副本变量。示例：

class ConnectionManager {

private static Connection connect = null;

public static Connection openConnection() {
if(connect == null){
connect = DriverManager.getConnection();
}
return connect;
}

public static void closeConnection() {
if(connect!=null)
connect.close();
}
}
假设有这样一个数据库链接管理类，这段代码在单线程中使用是没有任何问题的，但是如果在多线程中使用呢？很显然，在多线程中使用会存在线程安全问题：第一，这里面的2个方法都没有进行同步，很可能在openConnection方法中会多次创建connect；第二，由于connect是共享变量，那么必然在调用connect的地方需要使用到同步来保障线程安全，因为很可能一个线程在使用connect进行数据库操作，而另外一个线程调用closeConnection关闭链接。

ThreadLocal的应用场景

最常见的ThreadLocal使用场景为 用来解决数据库连接、Session管理等。

编译原理

编译原理简答题整理

1.说明LR（0）、SLR（1）、LR（1）、LALR（1）四类文法之间的关系。
LR(1)>LALR(1)>SLR(1)>LR(0)
2.如何判断一个上下文无关文法是否是LR(0)？
①构造项目集规范族。
②检查是否有移进-规约冲突或归约-归约冲突。
③若每个状态中都不存在移进-规约冲突或归约-归约冲突则该项目是LR（0）文法，否则，不是LR(0)文法。
3.如何判断一个上下文无关文法是否是SLR(1)？
①构造项目集规范族。
②检查是否有移进-规约冲突或归约-归约冲突。
③若某个状态I中存在移进-规约冲突或归约-归约冲突，则可通过引入FOLLOW集的方法解决，（例如{X->A · bB，A->c · ，B->d · }
首先满足FOLLOW（A）∩FOLLOW（B）=∅且FOLLOW（A）∩{b}=FOLLOW（B）∩{b}=∅,
则：
在状态I中面临输入符a的动作可由下面决策：
若a∈FOLLOW（A），则利用归约
若a∈FOLLOW（B），则利用归约
若a=b，则移进
其他情况报错。）
即在构造LR分析表时，只需要遇到规约项目时，只需要在该项目左边非终结符的FOLLOW集元素列置归约标记。
④若这样构造出来的LR分析表不存在冲突，则是SLR1文法，否则不是SLR1文法。
4.如何判断一个上下文无关文法是否是LR(1)？
①构造项目集规范族。
②检查是否有移进-规约冲突或归约-归约冲突。
③若某个状态中存在移进-规约冲突或归约-归约冲突但这些冲突都可以通过项目所带的向前搜索符号集来解决（构造LR分析表时，只在该项目所带的向前搜索符号集元素列置rj，如果这样构造出的分析表不存在冲突），则是LR(1)。
5. 如何判断一个上下文无关文法是否是LALR(1)？
①构造项目集规范族。
②检查是否有移进-规约冲突或归约-归约冲突。
③若某个状态中存在移进-规约冲突或归约-归约冲突但这些冲突都可以通过项目所带的向前搜索符号集来解决（根据合并同心集之后的LR1规范集族构造LR分析表时，只在该项目所带的向前搜索符号集元素列置rj，如果这样构造出的分析表不存在冲突），则是LALR(1)。
6.算符优先分析法的优缺点是什么？
优点：在确定句柄时只考虑终结符之间的优先关系，而与非终结符无关，这使得算符优先分析法具有效率高的优点。
缺点：由于去掉了单非终结符之间的归约，有可能将错误的句子识别为正确的。
7.什么是代码优化？代码优化的原则有哪些？
代码优化实质上是对代码进行等价变换，使得变换后的代码运行结果和变换钱的代码运行结果相同，但运行速度或占用的存储空间情况得到改善，生成更加有效的目标代码。
代码优化的原则有等价原则、有效原则、合算原则
8. 代码优化的分类有哪些？常用的优化技术有哪些？
代码优化分为局部优化、循环优化和全局优化。
局部优化的技术有：删除公共子表达式、删除无用赋值、合并已知量、交换语句位置、临时变量改名等。
循环优化的技术有：代码外提、强度削弱、删除归纳变量。

11.预处理的目的是什么？预处理主要做哪些工作？
预处理的目的是为了降低编译程序的处理负担。
预处理的主要工作是对源程序进行格式方面的规范化处理。
12.自上而下语法分析的基本思想是什么？
【解答】自上而下语法分析的基本思想是：从文法起始符号出发，不断使用文法的产生式进行推导，如果最终能够推导出待分析的终结符号串，则该终结符号串是文法的合法句子，否则该终结符号串不是文法的合法句子。
13.自上而下与自下而上的语法分析策略有什么区别？
【解答】自上而下语法分析是从文法起始符号出发，不断使用文法的产生式进行推导，
分析成功的标志是推导出待分析的终结符号串。
而自下而上语法分析是从待分析的终结符号串出发，使用产生式规则，对当前的符号串（开始时是待分析的终结符号串），寻找其中的子串B，利用规则 A>B，将B替换成A，得到新的符号串。分析过程的主要操作是归约。分析成功的标志是从给定的终结符号串出
发，经过不断归约，得到文法起始符号。
14.自上而下语法分析的关键问题是什么？
【解答】自上而下语法分析存在的关键问题有两点：
如果文法存在公共左因子，那么在对该终结符进行推导时，不能确定到底应该选择哪个候选式。
如果文法中存在左递归，可能会导致推导的过程会无休止地进行下去，语法分析过程永远不会停止。
15.什么是LL(1）文法？一个文法是LL（1）文法的充分必要条件是什么？

16. 递归下降分析程序的设计思想是什么？
    递归下降分析程序的设计思想是：
    针对文法的每个非终结符设计一个子程序，完成相应非终结符的扩展，通过所有子程序的相互调用，完成整个终结符号串的分析，分析开始时，文法起始符号所对应的子程序首先被调用。
17. 算符优先分析时，使用优先函数有什么优点和缺点？
    优点：使用优先函数减小了优先关系表的尺寸，节省了存储空间；同时通过数值表达终结符之间的优先关系，提高了比较终结符之间优先关系的效率。
    缺点：在优先关系表中，某些终结符之间不存在优先关系，但是变成优先函数后，由于任意数值之间都可比较，会导出任意终结符对都存在优先关系的结论，这样就产生了新问题。
18. 简述自下而上语法分析的基本思想，基本过程和基本操作。
    【解答】自下而上语法分析的基本思想是从待分析的终结符号串出发，反向使用产生式规则，将产生式规则右部的符号串归约为左部的非终结符。通过一系列这样的归约，最终能归约出文法的起始符号。
    分析过程有4种基本动作：
    移进、归约、接受、出错
    19.自下而上语法分析的关键问题是什么？
    【解答】自下而上语法分析的关键问题是寻找可归约串，即对于待分析的符号串，应
    该选择其中的哪个子串进行归约。
    20.什么是属性文法？什么是综合属性？什么是语义属性？
    【解答】属性文法，是指为上下文无关文法中的文法符号赋予一定的属性，以便描述与文法符号相关的信息，利用这些信息为每个产生式规则配上语义子程序，在语义子程序中进行属性计算等工作。
    综合属性：对于文法非终结符，如果其某个属性的计算依赖于其产生式规则右部符号的属性，则该属性称为综合属性。
    继承属性：是指届性的计算依赖于其兄弟节点和父节点的属性，称为继承属性。
    21.简述语法制导翻译的基本思想。
    【解答】所谓语法制导翻译，是为语言的文法规则配上相应的语义子程序，在语法分析过程中，当某条规则被用来扩展一个文法非终结符（自上而下的分析），或者被用来归约可归约串（自下而上的语法分析）时，执行相应的语义子程序，完成属性的计算和中间代码的生成。
    22.LL1算法描述
    #，S入栈
    Do{
    X=当前栈顶符号；a=当前输入符号；
    If(X∈VT ∪ {#}){
    IF(X==a){
    If(X!=#){
    将X弹出，且前移输入指针；
    }
    Else error();
    }
    Else{
    If(M[X,a] == Y1Y2…Yk){
    将X弹出；
    依次将YK…Y2Y1压入栈；
    }
    Else error；
    }while（X！=#）；
    23.LR1算法描述
    设S是栈顶状态，a是输入指针ip所指向的当前符号。
    1)：
    令ip指向输入串的第一个符号
    将#压入符号栈，将开始状态0压入状态栈。
    2）：
    重复执行如下过程：
    If(action[S,a]==sj){
    把符号a压入符号栈；
    把状态j压入状态栈；
    }
    Else if(action[S,a]==rj){
    从符号栈栈顶弹出第j条规则又不串长|β|个符号；
    把按第j条规则归约得到的非终结符 A压入符号栈；
    将goto[S,A]的值j压入状态栈；
    并输出规则A->β；
    }
    Else if(action[S,a]==acc){
    Return;//分析成功
    }
    Else{
    Error();
    }

什么是表格管理程序？
编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作涉及到构造、查找或更新有关的表格，因此需要有表格管理工作。
什么是出错处理程序？
编译过程中，发现源程序有错误，编译程序应报告错误的性质和出错的地点，使得编译程序能够继续向下进行分析和处理。
简述一下分析和综合
分析阶段：词法分析、语法分析、语义分析，只对程序进行识别和检查，没作实质翻译
综合阶段：中间代码的生成，代码优化，目标代码生成，对源程序进行翻译，生成目标代码
什么是句型，什么是句子，什么是语言？
句型：从文法的起始符号开始，经过有限步推导能够推导出来的符号串。
句子：只有终结符构成的句型
语言：所有句子的集合
什么是文法？乔姆斯基把文法分成几种类型？
文法可以表示成四元组
0型短语文法 没有任何限制
1型上下文有关文法 右侧式子的长度要大于左侧的
2型上下文无关文法 非终结符的替换可以不考虑上下文。
3型正规文法 每一个非终结符都推出非终结符+终结符或者直接推出终结符
3.高级语言、汇编语言、机器语言之间的区别是什么？
高级语言是一种面向算法、方便程序员编程的语言。
汇编语言是一种符号语言。
机器语言是一种二进制代码。
高级语言需要翻译成汇编语言，再汇编成机器语言才能被理解和执行。
4.中间代码主要有哪几种形式？
逆波兰式、三元式、四元式
5.在编译的各个阶段都涉及到的工作是什么？
表格管理和出错处理
6.出错处理中的错误一般分为哪两类？
语法错误和语义错误
7.什么叫做遍？
所谓遍就是指对源程序或者源程序的中间结果从头到尾的扫描一次，并做有关的加工处理，生成新的中间结果或目标程序。
8.什么是编译前端？什么是编译后端？
前端主要是指与源语言有关的部分。词法分析、语法分析、语义分析和中间代码的产生。
后端主要是指与目标机有关的部分。代码优化、目标代码的产生。
9.自动编译工具
LEX自动产生词法分析器。
YACC自动产生语法分析器。
10.什么是二义性？
如果一个文法存在某个句子对应两棵不同的语法树，那么这个问法就是二义性的
短语、直接短语、句柄、素短语、最左素短语分别是什么？

句柄：最左直接短语
素短语：至少含有一个终结符的短语并且除自身外不包含更小的素短语
最左素短语：句型中最左边的素短语
什么是算符优先文法？
对于任意的终结符对a b,最多存在三种优先关系之一，则称该算符文法为算符优先文法。
算符优先分析法分析句子成功的标志是什么？
堆栈中为‘#’和文法的起始符号，缓冲区中的指针指向符号‘#’
LR1的含义
L自左向右扫描输入串
R表示最右推导的逆过程
1表示向前看一个符号

移进归约接受出错分别是什么？

需要构造哪些表

什么是first follow firstvt lastvt

软件工程

软件工程面试题整理
软件测试的层次？
软件测试可以分为单元测试、集成测试、系统测试
单元测试：对程序单元进行正确性检验的测试工作。
集成测试：测试多个单元接口。
系统测试：测试全部单元接口，关注整个系统行为。
黑盒测试和白盒测试？
黑盒测试：把测试对象看成一个黑盒子，完全基于输入和输出数据来判定测试对象的正确性。
黑盒测试常用方法：等价类划分、边界值分析、决策表、状态转换
白盒测试：将测试对象看作透明，按照测试对象内部的程序结构来设计测试用例进行测试。
白盒测试常用方法：语句覆盖、条件覆盖、路径覆盖
白盒测试和黑盒测试的优缺点？
白盒测试的优点是覆盖率较高，缺点是测试开销大不能检验需求规格
黑盒测试的优点是测试效率高，缺点时是覆盖率低。

设计模式总结
什么是设计模式？
设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。
设计模式如何分类？

工厂模式

抽象工厂模式

策略模式

观察者模式

单例模式

迭代器模式

面向对象的设计原则有哪些？

软件开发模型整理
常见的模型：瀑布模型、快速原型模型、增量模型、螺旋模型
瀑布模型：将软件生命周期划分为制定计划、需求分析、软件设计、程序编写、软件测试和运行维护等六个基本活动，并且规定了它们自上而下、相互衔接的固定次序，如同瀑布流水，逐级下落。
快速原型模型：快速原型模型的第一步是建造一个快速原型，实现客户或未来的用户与系统的交互，用户或客户对原型进行评价，进一步细化待开发软件的需求。通过逐步调整原型使其满足客户的要求，开发人员可以确定客户的真正需求是什么；第二步则在第一步的基础上开发客户满意的软件产品。
增量模型：在增量模型中，软件被作为一系列的增量构件来设计、实现、集成和测试，每一个构件是由多种相互作用的模块所形成的提供特定功能的代码片段构成。
螺旋模型：以原型为基础沿螺线旋转、每转一圈都经过计划/风险分析/实施/评估等过程且得到相应新版本、经过若干次螺旋上升得到最终版本。

排序算法专题

排序算法面试专题
插入排序
描述一下插入排序？
每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列中。
O(N^2) 稳定排序
描述一下希尔排序？
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
O(N^1.3) 不稳定排序
交换排序
描述一下冒泡排序？
从后往前两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完。
O(N^2) 稳定排序
描述一下快速排序？

1. 在数组中选一个元素作为基准（通常选用数组第一个元素作为基准）；
2. 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；
3. 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。
   O(nlog2N) 不稳定排序
   平均性能最优的排序算法 当初始表基本有序的情况下时间复杂度最差，为O(N^2)。
   选择排序
   描述一下简单选择排序？
   每一趟在后面N-I+1个元素中选取关键字最小的元素与第i个元素交换，直到n-1趟做完。
   O(N^2) 不稳定排序
   描述一下堆排序？
   首先建初堆，将其调整成大根堆。
   将堆顶元素输出，然后重新调整堆使其保证大根堆性质。
   再输出堆顶元素。
   重复此过程，直到堆中只剩一个元素为止。
   O(nlog2N) 不稳定排序
   描述一下归并排序？
   把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
   O(nlog2N) 稳定排序
   描述一下基数排序？
   是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
   O(n*k) 稳定排序