目录
知道关键点，能用自己的话描述即可。
1.数据结构
2.计算机网络
3.计算机组成原理
4.操作系统
知道关键点，能用自己的话描述即可。
1.数据结构
什么是数据结构：
数据结构是计算机科学中用于存储和组织数据的方式，它包括集合、线性、树形、图状等逻辑结构，以及顺序、链式、索引、散列等存储结构，还定义了插入、删除、查找等一系列操作。
介绍一下普利姆算法：
普利姆算法是一种求无向连通带权图最小生成树的贪心算法，从任意顶点开始，将其加入已访问集合，每次都选择与已访问顶点相邻的未访问顶点中权值最小的边及对应顶点加入最小生成树，直到所有顶点都被加入，可用于网络设计、物流配送、计算机图形学等领域，不同数据结构下时间复杂度有所不同。
补充：
Kruskal：
Kruskal 算法是一种用于求解无向连通带权图最小生成树的贪心算法，它将图中所有边按权值从小到大排序，从权值最小的边开始依次选取，若选取的边不会与已选边构成环，则将其加入最小生成树的边集合中，直到选取的边能连接图中所有顶点为止。最短路径：
Dijkstra 算法是一种经典的单源最短路径算法，用于在带权有向图或无向图中，计算从一个源顶点到其他所有顶点的最短路径。它以起始顶点为中心，采用贪心策略，每次从未确定最短路径的顶点中选择距离源点最近的顶点，将其加入已确定集合，并以此更新其他顶点到源点的距离，直到所有顶点的最短路径都被确定。Floyd 算法用于求任意两点间最短路径的算法。该算法利用动态规划的思想，通过一个三重循环，依次以每个顶点作为中间节点，对图中所有顶点对之间的距离进行松弛操作，不断更新任意两个顶点之间的最短路径长度，最终得到包含所有顶点对之间最短路径的距离矩阵。
DFS 的基本思想和 BFS 的基本思想：
DFS （深度优先搜索）类似于二叉树的先序遍历，它的基本思想是首先访问出发点并将其标记为已访问，然后选取与起始点邻接的未被访问的任意一个顶点标记并递归访问，再选择与上一标记顶点邻接的未被访问的顶点标记并递归访问， 以此重复进行。当一个顶点的所有邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个并重复上述递归访问过程， 直到途中所有的顶点都被访问过为止。
BFS（广度优先搜索） 类似于树的层序遍历， 需要使用队列这一数据结构， 它的基本思想是首先访问起始顶点入队并标记为已访问，当队列不空时循环执行访问操作，即出队并依次检查出队顶点的所有邻接顶点，访问没有被访问过的邻接顶点并将其入队。当队列为空时跳出循环，广度优先搜索即完成。
B树和B+树的区别：
① 在 B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。
② B+树的非叶子节点仅存储索引信息，而所有实际数据都存储在叶子节点中。
B+树的应用：
B+树相比于B树而言，更适合用于数据库：
① B+树的非叶子节点仅存储索引信息，而所有实际数据都存储在叶子节点中。这使得B+树的查询效率更加稳定，因为每次查询都必须从根节点走到叶子节点，路径长度相同。
② B+树的叶子节点通过指针连接，形成一个有序链表。这使得范围查询和排序操作更加高效，只需遍历叶子节点即可。
③ 由于B+树非叶子节点不存储数据，所以一个节点可以存储更多索引，从而在相同高度下覆盖更大的索引范围，减少查找路径的长度，降低IO次数。
解释一下KMP算法：
KMP算法的关键是利用匹配失败后的信息（已经匹配的部分中的对称信息），尽量减少模式串（待搜索词）与文本串的匹配次数以达到快速匹配的目的。
KMP归纳：根据模式串的对称信息来获得一个next数组，在文本串遍历过程中，当发生对比字符失败时，根据当前next数组的值来移动相应的距离，使匹配效率提高。
各种排序算法总结：
不稳定算法：快（快速）些（希尔）选（选择）堆。（记住，面试时才能临场发挥出来）
时间复杂度O（nlogn）算法：快（快速）归（归并）队（堆）。
希尔排序：
希尔排序是对插入排序的优化，它将待排数组按特定增量序列分组，每组内执行插入排序，增量不断递减，直至为 1。在分组时，元素依增量间隔被划分到不同子序列，组内排序让元素逐步靠近最终位置。
冒泡排序：
冒泡排序是一种简单的排序算法，它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。在每一轮走访中，最大（或最小）的元素会像气泡一样 “浮” 到数列的一端。
快速排序：
快速排序是一种高效的排序算法，采用分治策略。它先从待排序序列中选一个基准元素，将序列分成两部分，使左边部分元素都小于等于基准，右边部分元素都大于基准，此过程叫分区操作。接着分别对左右两部分递归地进行同样的快速排序操作，直至各部分只有一个元素或为空，最终让整个序列有序。
堆排序：
堆排序是一种基于堆这种数据结构的高效排序算法，采用选择排序的思想。首先，它会将待排序序列构建成一个堆（大顶堆或小顶堆），以大顶堆为例，每个节点的值都大于或等于其子节点的值，此时堆顶元素就是最大值。然后，将堆顶元素与堆的最后一个元素交换，把最大值放到序列末尾，接着对剩余元素重新调整成大顶堆，不断重复这个过程，依次找出次大值、第三大值等，最终使整个序列有序。
基数排序：
将整数按位数切割成不同的数字，然后按每个位数分别比较。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
哈希表的冲突及解决方法：
哈希表：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。
冲突：关键字不同的元素可能会映像到哈希表的同一地址上；
解决方法：
（1）开放寻址法：线性探测法、平方探测法、双散列函数探测法、伪随机探测法；
（2）拉链法（相同时挂到一个单链表下）；
（3）再哈希法（相同时再用另外一个哈希函数）。
外部排序的优化方法：
①增加归并路数
②减少归并段数量，即增加初始归并段长度(置换-选择排序)
③减少各归并段在内存中的关键字比较次数(败者树)
2.计算机网络
码元和比特的关系：
如果一个“信号周期”内可能出现K种信号，则：
说几个物理接口的特性：
CSMA/CD与CSMA/CA的区别：
CSMA/CD 通过检测到冲突后发送阻塞信号并随机退避来解决冲突；CSMA/CA 则通过 RTS/CTS 控制帧和随机退避避免冲突发生。
CSMA/CD 适用于有线网络（如以太网），依赖物理层直接检测冲突；CSMA/CA 适用于无线网络（如 Wi-Fi），因无线信号隐蔽终端问题无法直接检测冲突。CSMA/CD 需要硬件支持冲突检测；CSMA/CA 无需硬件检测，通过软件协商避免冲突。
简述网卡的功能
网卡要进行串行/并行转换：网卡和局域网之间的通信是通过电缆或双绞线以串行传输方式进行的。而网卡和计算机之间的通信则是通过计算机主板上的 I/O 总线以并行传输方式进行。
网卡能实现以太网协议：在安装网卡时必须将管理网卡的设备驱动程序安装在计算机的操作系统中。这个驱动程序以后就会告诉网卡，应当从存储器的什么位置上将局域网传送过来的数据块存储下来。
网卡能处理正确的帧：当网卡收到一个有差错的帧时，它就将这个帧丢弃而不必通知它所插入的计算机。当网卡收到一个正确的帧时，它就使用中断来通知该计算机并交付给协议栈中的网络层。当计算机要发送一个 IP 数据包时，它就由协议栈向下交给网卡组装成帧后发送到局域网。
RIP和OSPF的区别：
RIP（路由信息协议）和 OSPF（开放最短路径优先）是两种不同的动态路由协议，主要区别在于：RIP 是基于距离矢量算法的协议，通过跳数衡量路径，定期广播完整路由表，收敛速度慢，适合小型网络；而 OSPF 是基于链路状态算法的协议，通过带宽计算最短路径，仅发送链路状态变化的触发更新，支持 VLSM 和层次化区域划分，收敛快且扩展性强，适用于大型复杂网络。RIP在应用层，最大站点数为 15。OSPF在网络层，洪泛法，迪杰斯特拉算法。
为什么要TCP三次握手：
TCP 进行三次握手，一是为了防止历史连接初始化，避免旧的延迟数据包导致服务器误建立无效连接，因为客户端可在第三次握手时判断是否为历史连接并中止；二是为了避免资源浪费，防止因只有两次握手时客户端重发 SYN 导致服务器建立多个无效连接而占用资源；三是为了同步双方初始序列号，通过三次交互双方能可靠地确认彼此的初始序列号，为后续按序、可靠的数据传输做好准备。
TCP 和 UDP 的区别：
TCP 可靠， UDP 不可靠。
TCP 只支持点对点服务， UDP 可以一对一、一对多、多对一和多对多。
TCP 面向连接， UDP 无连接。
UDP 有较好的实时性，工作效率比TCP 高。
TCP 对系统资源要求多， UDP 则无。
UDP 的优点：
发送前无需连接，减少了开销和时延，首部开销小，无拥塞控制，方便实时应用，不保证可靠交付，无需维持连接状态表。 UDP 的可靠性要通过应用层来控制。
TCP保证可靠传输的方法？
确认应答机制、超时重传机制、滑动窗口机制，流量控制机制，拥塞控制机制
DHCP的工作流程：
DNS的工作流程：
本地 DNS 服务器会在其缓存中查找该网址对应的 IP 地址，若能找到则直接返回给用户，完成解析；若缓存中没有，本地 DNS 服务器会向根域名服务器发起查询，根域名服务器告知其负责该顶级域名的顶级域名服务器地址。接着，本地 DNS 服务器向顶级域名服务器查询，顶级域名服务器又指向负责该二级域名的权威域名服务器。最后，本地 DNS 服务器向权限域名服务器查询，权限域名服务器将该网址准确的 IP 地址返回给本地 DNS 服务器，本地 DNS 服务器缓存该 IP 地址后再返回给用户，用户的设备就能依据这个 IP 地址与目标服务器建立连接，获取相应的网络资源 。
3.计算机组成原理
说几个计算机的性能指标：
指令和数据放在一起存储的，计算机是如何区分指令和数据的：
方式一：通过不同时间段来区分指令和数据，即在取指令阶段（或取值微指令）取出的为指令，在执行指令阶段（或相应微程序）取出的即为数据。
方式二：通过地址来源区分，由 PC 提供存储单元地址的取出的是指令，由指令地址码部分提供存储单元地址的取出的是操作数。
SRAM，DRAM和ROM的特点：
冯诺依曼结构：
主要由运算器、控制器、存储器、输入设备和输出设备组成。运算器负责算术与逻辑运算，对数据进行各类操作；控制器作为指挥中心，从存储器提取指令并译码，据此向各部件发控制信号以协调工作；
CPU的组成：
CPU的功能有哪些：
指令控制：取指令，分析指令，执行指令
操作控制：CPU管理并生成操作信号，并把操作信号送往各个部件，完成指令控制。
时间控制：对各种操作加以时间上的控制。
数据加工：对数据进行算术和逻辑运算。
中断处理：对异常和特殊请求进行处理。
哪些寄存器对用户是透明的：
CISC与RISC的区别：
流水线堵塞的分类：
结构相关（资源冲突）：多条指令在同一时刻争用同一资源。
解决方法：
1.前一个指令访存时，令后续指令暂停一个时钟周期；2.单独设置数据存储器和指令存储器。
数据相关：在一个程序中，下一条指令会使用当前指令的结果。
解决方法：
1.将后续指令暂停几个时钟周期，直至数据相关问题得到解决；2.设置相关专用通路，使得不用等到前一条指令把计算结果写回寄存器，而是直接将结果当做下一个指令的输入数据。
控制相关：当前流水线遇到了分支指令，如执行转移，会改变PC值，容易引起断流，引起控制冒险。
解决方法：
1.对转移指令进行分支预测，尽早生成转移目标地址。
流水线的性能指标：
1）吞吐量：单位时间内流水线完成的任务数量
2）加速比：不使用流水线所用的时间与使用流水线所用的时间之比
3）效率：流水线的设备利用率
总线性能指标：
I/O端口的编址：
硬件多线程：
同步定时与异步定时：
同步定时
采用一个统一的时钟信号，来协调发送方和接收方的传递定时关系优点：传送速度快，具有较高的传递速率，逻辑简单
缺点：不能及时进行数据通信的有效性检验，可靠性较差
异步定时
没有统一的时钟信号，也没有固定的时间间隔，完全依靠双方相互制约的“握手”信号来实现控制。优点：总线周期长度可变，能保证可靠的信息交换，自动适应时间的配合。
缺点：比同步定时复杂，速度慢。
不互锁
主设备发出请求信号后，不必等到接到从设备的“回答”信号，而是经过一段时间自动撤销信号
从设备在接到“请求”信号后，发出“回答”信号，经过一段时间之后，自动撤销信号
半互锁主设备发出请求信号后，必须等到接到从设备的“回答”信号，才能撤销信号
从设备在接到“请求”信号后，发出“回答”信号，经过一段时间之后，自动撤销信号
全互锁主设备发出请求信号后，必须等到接到从设备的“回答”信号，才能撤销信号
从设备发出回答信号后，必须等到接到主设备的“请求”信号撤销后，才能撤销
FLASH的特点：
SSD固态硬盘与固态硬盘相比的特点：
磁盘操作时间受什么影响：
RAID：
4.操作系统
程序运行的基本原理：
什么是系统调用：
系统调用是用户程序与操作系统内核之间进行交互的接口。当用户程序执行到需要使用系统服务的代码时，会触发一个特殊的指令（通常是中断指令），使 CPU 从用户态切换到内核态。进入内核态后，操作系统内核接管程序的执行，根据系统调用的编号和参数来执行相应的内核代码，完成用户所请求的功能。完成后，操作系统会将结果返回给用户程序，并将 CPU 从内核态切换回用户态，让用户程序继续执行后续代码。
管程：
将共享资源及其操作封装，保证同一时刻仅一个进程能进入执行过程，实现互斥访问。通过引入条件变量处理进程同步，让进程可因条件不满足阻塞，条件满足时被唤醒。
进程通信方式：
1、低级通信方式
PV 操作（信号量机制）。
– P： wait(S)原语，申请 S 资源
– V： signal(S)原语，释放 S 资源
2、高级通信方式：以较高效率传输大量数据的通信方式
– 共享存储（使用同步互斥工具操作共享空间）
– 消息传递（进程间以格式化的消息进行数据交换，有中间实体，分为直接和间接两种，底层通过发送消息和接收消息两个原语实现）
– 管道通信（两个进程中间存在一个特殊的管道文件，进程的输入输出都通过管道，半双工通信）
中断和子程序调用的区别：
中断的类型：
中断的过程：
操作系统的特点：
共享：资源可被多个并发执行的进程使用
并发：可以在同一时间间隔处理多个进程，需要硬件支持
虚拟：将物理实体映射成为多个虚拟设备
异步：进程执行走走停停，每次进程执行速度可能不同，但 OS 需保证进程每次执行结果相同
死锁的条件：
死锁和饥饿的区别：
– 都是资源分配问题
– 死锁是等待永远不会释放的资源，而饥饿申请的资源会被释放，只是永远不会分配给自己
– 一旦产生死锁，则死锁进程必然是多个，而饥饿进程可以只有一个
– 饥饿的进程可能处于就绪状态，而死锁进程一定是阻塞进程
解释一下抖动现象：
页面置换算法：
1.最佳置换算法 2.先进先出算法 3.最近最久未使用算法 4.时钟置换算法 5.改进型时钟置换算法
Cache替换策略：
Cache写策略：
Cache写不命中时：
写分配法：当CPU对Cache写不命中时，把主存中的块调入Cache，在Cache中修改。通常搭配写回法使用。
非写分配法：
当CPU对Cache写不命中时只写入主存，不调入Cache。搭配全写法使用。
Cache映射方式：
直接映射，组相联映射，全相联映射
处理机调度方法：
动态分区分配算法：
FCB包含什么：
文件名，文件物理地址，文件打开书，文件的存取权限（规定不同用户或用户组对文件的读、写、执行等权限），文件的物理结构（连续结构、链接结构、索引结构），逻辑结构（记录式结构或流式结构）
文件分配方式：
磁盘调度算法：
文件共享：
I/O软件层次：
SPOOLing技术：
Spooling 技术的原理是利用高速大容量外存（如磁盘）模拟多个低速输入输出设备，输入时输入进程将输入设备的数据预读到磁盘的输入井，进程需要数据时直接从输入井获取，输出时进程把要输出的数据先写入磁盘的输出井，再由输出进程按规则将数据从输出井输出到输出设备。SPOOLing技术实现了将独占设备改造成共享设备，可让多个作业共享一台独占设备。
)
