1. 数据结构

1. 递归的概念？

递归的本质是将原问题拆分成具有相同性质的子问题，递归的解法特点有两个，分别是子问题拆分方程和终止条件。递归的调用栈会有深度限制。

2. 迭代？

迭代和递归本质上是一样的，只是我们模拟了递归的调用栈，因此迭代会用到栈结构。

3.什么是分治？

分治的算法特征一般是将原问题拆分成若干子问题（分解），然后再求解子问题（终止条件），最后将各个子问题的解合并，形成原问题的解（合并）。

【在求解一些问题时，有很多重复的子问题，这样会导致算法非常低效，这个时候就可以加缓存，也就是带备忘录的递归解法】

4. 什么是动态规划？

5. 什么是回溯算法？

6. 什么是贪心算法？

7. DFS的基本思想？

8. BFS的基本思想？

9. Kruskal算法的基本思想？

首先构造一个只有n个顶点的没有边的非连通图，给所有边按照值从小到大排序，选择一个最小的权值边，若该边的两个顶点在不同的连通分量上，加到有效边中，否则舍去这条边，重新选择权值最小的边，如此重复下去，直到所有的顶点都在同一条连通分量上。

10.Prim算法的基本思想？

从某一个顶点u0出发，选择与它关联的具有最小权值的边（u0,v），将其顶点加入到生成树的顶点集合U中。每一步从U中挑选一个顶点u,而另一个顶点不在U中的各个顶点中选择权值最小的边(u,v)，把它的顶点加入到U中，直到所有的顶点都加入到生成树的顶点集合U中为止。

11. 简述链表和数组的优缺点？

12. Heap和Stack的概念以及区别？

13. 哈希表最好和最坏情况下的复杂度？

14. 二叉树的直径？

2. 操作系统

1. 进程和线程的区别

根本区别：进程是资源分配的最小单位，线程是程序执行的最小单位；

地址空间：进程有自己独立的地址空间，每启动一个进程，系统都会为其分配地址空间，建立数据表来维护代码段、堆栈和数据段；线程没有独立的地址空间，同一个线程共享本进程的地址空间；

资源拥有：进程之间拥有的资源是独立的，统一进程之间的线程共享本进程的资源；

执行过程：

系统开销：进程执行开销大，线程执行开销小

2. 系统调用的定义

系统调用是 OS 与应用程序之间的接口，它是用户程序取得 OS 服务的唯一途径。它与一般的过程调用的区别：运行在不同的系统状态，调用程序运行在用户态，而被调用的程序运行在系统态，通过软中断机制，先由用户态转为系统态，经核心分析后，才转向相应的系统调用处理子程序；一般的过程调用返回后继续执行，但对系统调用，当调用进程仍具有最高优先权时，才返回到调用进程继续处理，否则只能等被重新调度。

3. 解释一下管程？

管程是由一组局部变量、对局部变量进行操作的一组过程和对局部变量进行初始化的语句序列组成。引入它的目的是因为 Wait/Singal 操作太过分散,对它的维护很麻烦且容易造成死锁。管程的特点是:管程的过程只能访问管程的局部变量,管程的局部变量只能由其过程来访问;任何时刻只能有一个进程进入管程执行;进程只能通管程提供的过程入口进入管程。

4. 在可变分区管理中，需要哪些硬件支持？

采用可变分区方式管理时,一般均采用动态重定位方式装入作业。地址变换要靠硬件支持,主要是两个寄存器:基址寄存器和限长寄存器，限长寄存器存放作业所占分区的长度,基址寄存器则存放作业所占分区的起始地址,这两个值确定了一个分区的位置和大小。
转换时根据逻辑地址与限长值比较,如果不有超过这个值,表示访问地址合法,再加上基址寄存器中的值就得到了绝对地址了,否则形成“ 地址越界” 中断。

5.中断和陷入有什么区别？

外中断时指来自处理机和内存外部的中断,如 I/O 中断、定时器中断、外部信号中断等。狭义上也叫中断;
内中断主要指在处理机和内存内部产生的中断,也称陷入,如校验错、页面失效、溢出、除数为零等。
中断和陷阱的主要区别:
(1) 陷入通常由处理机正在执行的现行指令引起,而中断则是由与现行指令无关的中断源引起的。
(2) 陷阱处理程序提供的服务为当前进程所用,而中断处理程序提供的服务则不是为了当前进程的。
管理时,一般均采用动态重定位方式装入作业。地址变换要靠硬件支持,主要是两个寄存器:基址寄存器和限长寄存器,限长寄存器存放作业所占分区的长度,基址寄存器则存放作业所占分区的起始地址,这两个值确定了一个分区的位置和大小。转换时根据逻辑地址与限长值比较,如果不有超过这个值,表示访问地址合法,再加上基址寄存器中的值就得到了绝对地址了,否则形成“ 地址越界” 中断。

6. 中断和系统调用有什么区别？

中断：解决处理器速度和硬件速度不匹配，是多道程序设计的必要条件。每个中断都有自己的数字标识，当中断发生时，指令计数器 PC 和处理机状态字 PSW中的内容自动压入处理器堆栈，同时新的 PC 和 PSW 的中断向量也装入各自的寄存器中。这时， PC 中包含的是该中断的中断处理程序的入口地址，它控制程序转向相应的处理，当中断处理程序执行完毕，该程序的最后一条 iret（中断返回），它控制着恢复调用程序的环境。
中断和系统调用的区别: 中断是由外设产生,无意的, 被动的系统调用是由应用程序请求操作系统提供服务产生, 有意的,主动的。要从用户态通过中断进入内核态。
（联系）
中断过程：中断请求中断响应断点保护执行中断服务程序断点恢复中断返回
系统调用过程：应用程序在用户态执行时请求系统调用，中断，从用户态进入内核态，在内核态执行相应的内核代码。

7. 操作系统的特点？

共享：资源可被多个并发执行的进程使用
并发：可以在同一时间间隔处理多个进程，需要硬件支持
虚拟：将物理实体映射成为多个虚拟设备
异步：进程执行走走停停，每次进程执行速度可能不同，但 OS 需保证进程每次执行结果相同

8. 进程的组成？

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

9. 并发和并行的区别？

并发：同一间隔并行：同一时刻

10. 进程切换的过程？

保持处理机上下文 -> 更新 PCB -> 把 PCB 移入相应队列(就绪、阻塞) ->选择另一个进程并更新其 PCB -> 更新内存管理的数据结构 -> 恢复处理机上下文

11. 进程通信的方式？

1、低级通信方式
PV 操作（信号量机制）。
– P： wait(S)原语，申请 S 资源
– V： signal(S)原语，释放 S 资源
2、高级通信方式：以较高效率传输大量数据的通信方式
– 共享存储（使用同步互斥工具操作共享空间）
– 消息传递（进程间以格式化的消息进行数据交换，有中间实体，分为直接和间接两种，底层通过发送消息和接收消息两个原语实现）
– 管道通信（两个进程中间存在一个特殊的管道文件，进程的输入输出都通过管道，半双工通信）

12. 死锁的必要条件？

– 互斥条件：资源在某一时刻只能被一个进程占有
– 不剥夺条件：进程所持有的资源在主动释放前不能被其他进程强行夺走
– 请求和占用条件：死锁进程必然是既持有资源又在申请资源的

– 循环等待条件：存在等待链，互相申请，互不释放

13. 死锁与饥饿的区别？

都是资源分配问题
死锁是等待永远不会释放的资源，而饥饿申请的资源会被释放，只是永远不会分配给自己
一旦产生死锁，则死锁进程必然是多个，而饥饿进程可以只有一个
饥饿的进程可能处于就绪状态，而死锁进程一定是阻塞进程

14. FCB包括什么？

文件指针：上次读写位置。
文件打开数：多少个进程打开了此文件。
文件磁盘位置。
文件的访问权限：创建、只读、读写等。

15. 页面置换算法？

最佳置换算法 OPT
先进先出置换算法 FIFO
最近最久未使用算法 LRU
时钟算法 LOCK
改进型时钟算法

16. 批处理作业调度算法？

先来先服务 FCFS
最短作业优先 SJF
最高响应比优先 HRN
多级队列调度算法

17.进程调度算法？

先进先出 FIFO
时间片轮转算法 RR
最高优先级算法 HPF
多级队列反馈算法

18.磁盘调度算法？

先来先服务 FCFS
最短寻道时间优先 SSTF
扫描算法 SCAN
循环扫描算法 C-SCAN

19.局部性原理？

程序的时间局部性是指程序在运行时呈现出局部性规律,在一段时间间隔内,程序的执行是局限在某个部份,所访问的存储空间也只局限在某个区域。
程序的空间局部性是指若一个存储单元被访问,那么它附近的单元也可能被访问,这是由于程序的顺序执行引起的。

20. fork一个进程和生成一个线程有什么区别？

当你 fork 一个进程时，新的进程将执行和父进程相同的代码，只是在不同的内存空间中。
但当你在已有进程中生成一个线程时，它会生成一个新的代码执行路线，但共享同一个内存空间。

3. 计算机网络

1. IP层的协议有哪些？

ICMP 协议： ICMP 协议是指英文全称（Internet Control Message Protocol），就是网际控制信息协议。主要是用于补充 IP 传输数据报的过程中，发送主机无法确定数据报是否到达目标主机。 ICMP 报文分为出错报告报文和查询报文两种。若数据报不能到达目标主机， ICMP 出错报告报文可以以回送信息的方式，向源主机发去信息，并不能纠抄正数据报中的任何出错。除了出错报告， ICMP 还可以诊断出某些网络问题，这就是 ICMP 的查询报文。
IGMP 协议： IGMP 协议是指英文全称（Internet Group Management Protocol），网络组管理协议。主要用于建立和管理多播组，对 IP 分组广播进行控制

2. 简述网卡的功能？

1、网卡要进行串行/并行转换：网卡和局域网之间的通信是通过电缆或双绞线以串行传输方式进行的。而网卡和计算机之间的通信则是通过计算机主板上的 I/O 总线以并行传输方式进行。
2、网卡能实现以太网协议：在安装网卡时必须将管理网卡的设备驱动程序安装在计算机的操作系统中。这个驱动程序以后就会告诉网卡，应当从存储器的什么位置上将局域网传送过来的数据块存储下来。
3、网卡能处理正确的帧：当网卡收到一个有差错的帧时，它就将这个帧丢弃而不必通知它所插入的计算机。当网卡收到一个正确的帧时，它就使用中断来通知该计算机并交付给协议栈中的网络层。当计算机要发送一个 IP 数据包时，它就由协议栈向下交给网卡组装成帧后发送到局域网。

3. TCP和UDP的区别？

TCP 可靠， UDP 不可靠。
TCP 只支持点对点服务， UDP 可以一对一、一对多、多对一和多对多。
TCP 面向连接， UDP 无连接。
UDP 有较好的实时性，工作效率比TCP 高。
TCP 对系统资源要求多， UDP 则无。

4. UDP的优点？

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

5. RIP和OSPF

RIP(Routing Information Protocol)在应用层，最大站点数为 15
OSPF(Open Shortest Path First)网络层，洪泛法，迪杰斯特拉算法

6. DNS的工作过程

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

7. 解释TCP/IP三次握手

step1：首先客户机 TCP 向服务器 TCP 发送连接请求报文，报文中 SYN=1,随机发送一个序号 seq=x；
step2：服务器 TCP 接收到连接请求报文后，若同意连接，则返回确认报文，且为该 TCP 连接分配 TCP 变量和资源，确认报文中 SYN=1， ACK（确认位字段） =1,ack
（确认号字段） =x+1， seq=y;
step3：客户机接收到服务器的确认连接报文后，同样返回确认报文，且为该 TCP连接分配 TCP 变量和资源，确认报文中， ACK=1， ack=y+1， seq=x+1。

8. 虚电路和数据报的区别

4. 计算机组成原理

1. 为了实现重定位需要哪些硬件？

最简单的方式是在系统中增设一个重定位寄存器，用来存放正在执行作业的内存地址，每次访问数据时，由硬件自动将相对地址和重定位寄存器中的起始地址相加，形成实际的物理地址。当然在分页式与分段式系统中，还有地址变换机构，以及块表等方式。

2. 指令和数据放在一起存储的，计算机是如何区分指令和数据的？

方式一：通过不同时间段来区分指令和数据，即在取指令阶段（或取值微指令）取出的为指令，在执行指令阶段（或相应微程序）取出的即为数据。
方式二：通过地址来源区分，由 PC 提供存储单元地址的取出的是指令，由指令地址码部分提供存储单元地址的取出的是操作数。

5. 数据库

1. 数据库系统和文件系统相比的优点？

1.安全性高，可靠性高
2.查询检索速度快
3.可以保证数据的有效性完整性和约束检查
4.有效的解决并发操作的问题
5.编程简单，操作方便。

2.ACID

原子性（Atomicity）：事务中所有操作是不可再分割的原子单位。事务中所有操作要么全部执行成功，要么全部执行失败。
一致性（Consistency）：事务执行后，数据库状态与其它业务规则保持一致。如转账业务，无论事务执行成功与否，参与转账的两个账号余额之和应该是不变的。
隔离性（Isolation）：隔离性是指在并发操作中，不同事务之间应该隔离开来，使每个并发中的事务不会相互干扰。
持久性（Durability）：一旦事务提交成功，事务中所有的数据操作都必须被持久化到数据库中，即使提交事务后，数据库马上崩溃，在数据库重启时，也必须能保证通过某种机制恢复数据。

3. 数据库的三范式

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

4. 数据库表插入 100 个数据和 100 万个数据有何区别？

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

5. 数据库数据可以无限插入吗？

可以。大小受到主机内存的制约。数据量大时要先删索引。减少提交次数，即减少 IO 次数

6. group by having， having 和 where 的区别？

WHERE 子句用来筛选 FROM 子句中指定的操作所产生的行。
GROUP BY 子句用来分组 WHERE 子句的输出。
HAVING 子句用来从分组的结果中筛选行。
在查询过程中聚合语句(sum,min,max,avg,count)要比 having 子句优先执行.而where 子句在查询过程中执行优先级别优先于聚合语句(sum,min,max,avg,count)。

6. 程序设计基础

1. 重载与重写的区别

方法的重载和重写都是实现多态的方式，区别在于前者实现的是编译时的多态性，而后者实现的是运行时的多态性。
重载发生在一个类中，同名的方法如果有不同的参数列表（参数类型不同、参数个数不同或者二者都不同）则视为重载；重写发生在子类与父类之间，重写要求子类被重写方法与父类被重写方法有相同的参数列表，有兼容的返回类型，比父类被重写方法更好访问，不能比父类被重写方法声明更多的异常（里氏代换原则）。重载对返回类型没有特殊的要求，不能根据返回类型进行区分。

2. 两个栈模仿一个队列

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

3. 如何判断链表是否有环？

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

4. 如何判断环连环表的入口

1、将遍历过的结点都入 set，如果当前结点在 set 里有，则此结点即为入口。
2、快慢指针重合后，重置 fast 指针，此时 fast 每次走一步，再次重合结点即
为入口。

5. 栈应用括号匹配

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

6. 汉诺塔问题

void Hanoi(char src, char des, char via, int n) {
	Hanoi(src, via, des, n - 1);
	Move(src, des, n); //把第n个盘子直接从src移动到des
	Hanoi(via,des, src, n - 1);
}