- 计算机组成原理
- 计算机组成原理和计算机体系结构有什么区别
计算机体系结构是指那些被程序员看到的计算机系统的属性，这些属性通常被机器语言编程的程序员和汇编语言程序设计者以及汇编程序设计者看到（三者都对计算机系统中的传统机器M1熟悉）。这些属性包括指令集，存储器寻址技术，I/O机理等
计算机组成是指如何实现计算机体系结构所体现的属性。简而言之就是实现计算机体系结构包含的属性。
两者的关系：
存在两台机器体系结构相同，而组成不同。即结构与组成为一对多关系。
- 什么是存储程序原理，按此原理，计算机应具有哪几大功能
“存储程序”原理：将指令以代码的形式事先输入计算机的主存储器，然后按其在存储器中的首地址执行程序的第一条指令，以后就按该程序的规定顺序执行其他指令，直至程序执行结束。
5大功能：数据传送功能、数据存储功能、数据处理功能、操作控制功能、操作判断功能
- 计算机系统层次结构
1）微程序机器层：硬件层，由机器硬件直接执行微指令
2）传统机器层：机器层，由微程序解释机器指令系统
3）操作系统层
4）汇编语言层
5）高级语言层
微程序机器和传统机器是物理机，其他是虚拟机
- 介绍一下cache、cache写策略、cache替换策略
基于程序访问的局部性原理，把程序中正在使用的部分存放在一个高速的、容量较小的cache中，使CPU的访存操作大多数针对cache进行，从而大大提高程序的执行速度。
1）cache和主存映射方式：直接映射、全相联映射、组相联映射
2）cache中主存块的替换算法：随机算法、先进先出算法、近期最少使用算法、最不经常使用算法
3）cache写策略：全写法、写回法；写分配法、非先分配法
- 计算机储存单元
1）存储单元：存储一个存储字并具有特定存储地址的存储单位；
2）存储字：一个存储单元中存放的所有的二进制数据，按照某个地址访问某个存储单元获取的二进制数据。
3）存储字长：存储字中二进制数据的位数，即按照某个地址访问某个存储单元获取的二进制数据的位数；
4）存储体：由多个存储单元构成的存储器件。
- 提高访存速度的三种方式
1）采用高速元器件
2）采用存储层次结构：cache-主存结构
3）调整主存结构：单体多字，多体并行
- 定长和扩展操作码指令格式
定长操作码对于简化计算机硬件设计，提高指令译码和识别速度很有利。
扩展操作码：操作码的长度随地址码的减少而增加，不同地址数的指令可具有不同长度的操作码，从而在满足需要的前提下，有效缩短指令字长。但译码复杂，控制器设计难度增大。
- DRAM和刷新策略
- 集中刷新：指在一个刷新周期内，利用一段固定的时间，进行刷新
- 分散刷新：把每对每行刷新分散对各个工作周期中
- 异步刷新：最大刷新间隔2ms除以行数，得每隔相应时长产生一次刷新请求。
- 数组存储“边界对齐”和“边界不对齐”的区别
边界对齐：减少访存次数，浪费存储空间
边界不对齐：节约存储器空间，但增加访存次数，对多字节数据存在调整高低字节位置的问题
- CPU的组成与功能
组成：1）控制器：负责协调并控制计算机各部件执行程序的指令序列，包括取指令、分析指令和执行指令；2）运算器：对数据进行加工。
功能：指令控制、操作控制、时间控制、数据加工、中断处理。
- 控制器的功能和分类
功能：1）从主存中取出一条指令，并指出下一条指令在主存中的位置
2）对指令进行译码或测试，产生相应的操作控制信号，以便启动规定的动作
3）指挥并控制CPU、主存、输入和输出设备之间的数据流动方向
分类：硬布线控制器、微程序控制器
- 硬布线控制器
原理：根据指令的要求、当前的时序及外部和内部的.状态，按时间的顺序发送一系列微操作控制信号，他由复杂的组合逻辑门电路和一些触发器构成，因此又称组合逻辑电路。
控制单元CU的的输入信号来源：
1）经指令译码器译码产生的指令信息
2）时序系统所产生的机器周期信号和节拍信号
3）来自执行单元的反馈信息即标志。
- CPU控制方式
1）同步控制方式：系统有一个统一的时钟，所有的控制信号均来自这个统一的时钟信号。控制电路简单，但运行速度慢。
2）异步控制方式：不存在基准时标信号，各部件按自身固有的速度工作，通过应答方式进行联络。运行速度快，但控制电路比较复杂。
3）联合控制方式：同步和异步相结合，这种方式对各种不同的指令的微操作实行大部分同步、小部分异步的方法。
- 微程序控制器
原理：微程序采用存储逻辑实现，也就是把微操作信号代码化，使每条机器指令转化成为一段微程序并存入一个专门的存储器（控制存储器）中，微操作控制信号由微指令产生
微指令的编码方式：1）直接编码方式：简单、直观、执行速度快，操作并行性好；缺点是微指令字长过长，造成控制存储器容量极大。
2）字段直接编码方式：缩短了微指令的长度，但执行速度稍慢。
3）字段间接编码方式：进一步缩短了微指令字长，但削弱了并行控制能力。
微指令地址形成方式：
1）直接由微指令的下地址字段指出
2）根据机器指令的操作码形成
微指令的格式：1）水平型微指令：优点是微程序短，执行速度快；缺点是微指令长，编写微程序较麻烦。
2）垂直型微指令：优点是微指令短、简单、规整，便于编写微程序；缺点是微程序长，执行速度慢。
3）混合型微指令
- 什么是raid
RAID(廉价冗余磁盘阵列)：是指将多个独立的物理组成一个独立的逻辑盘，数据在多个物理盘上分割上交叉存储、并行访问，具有更好的存储性能、可靠怀和安全性。
RAID技术主要有以下三个基本功能：
(1)通过对磁盘上的数据进行条带化，实现对数据成块存取，减少磁盘的机械寻道时间，提高了数据存取速度。
(2)通过对一个阵列中的几块磁盘同时读取，减少了磁盘的机械寻道时间，提高数据存取速度。
(3)通过镜像或者存储奇偶校验信息的方式，实现了对数据的冗余保护。
- 指令流水线
影响流水线的因素：
1）结构相关（资源冲突）：由于多条指令在同一时刻争用同一资源而形成的的冲突
2）数据相关（数据冲突）：在一个程序中，存在必须等前一条指令执行完才能执行后一条指令的情况
3）控制相关（控制冲突）：当流水线遇到转移指令和其他改变PC值得指令而造成的断流时，会引起控制相关。
- 总线基础知识
总线的特点：分时、共享
总线特性：机械特性、电气特性、功能特性、时间特性
总线分类：
1）片内总线
2）系统总线：数据总线、地址总线、控制总线
3）通信总线
总线仲裁：
1）集中仲裁：链式查询方式、计数器定时查询方式、独立请求方式
2）分布仲裁
总线周期：申请分配阶段、寻址阶段、传输阶段、结束阶段
- 同步定时方式与异步定时方式
同步定时：系统采用统一的时钟信号来协调发送和接收双方的传送定时关系。
优点：传送速度快，具有较高的传输速率；总线控制逻辑简单。
缺点：主从设备属于强制性同步；不能及时进行数据通信的有效性检验，可靠性较差。适用于总线长度较短及总线所接部件的存取时间比较接近的系统。
异步定时：没有统一的时钟，也没有固定的时间间隔，完全依靠传送双方相互制约的“握手”信号来实现定时控制。
优点：总线周期长度可变，能保证两个工作速度相差很大的部件或设备之间可靠地进行信息交换，自动适应时间的配合。
缺点：比同步控制方式稍复杂一些，速度比同步定时方式慢。
分类：不互锁、半互锁、全互锁
- I/O接口
I/O接口是主机和外设之间的交接界面，通过接口可以实现主机和外设之间的信息交换。是主机和I/O设备之间设置的一个硬件电路及其相应的软件控制。端口是指接口电路中的一些寄存器。
I/O接口的功能：
1）实现主机和外设的通信联络控制。
2）进行地址译码和设备选择
3）实现数据缓冲
4）信号格式的转换
5）传送控制命令和状态信息
I/O设备编址方式：
1）统一编址：端口占用存储空间，减少了主存容量，但无需专用的I/O指令
2）独立编址：不占用存储空间，故不影响主存容量，但需设I/O指令
- 中断基本概念
中断：程序中断是指计算机在执行现行程序的过程中，出现某些急需处理的异常情况或特殊请求，CPU暂时中止现行程序，而转去对这些异常情况或特殊请求进行处理，在处理完毕后CPU又自动返回到现行程序的断点处，继续执行原程序。
CPU在统一的时刻即每条指令执行阶段结束前向接口发出中断查询信号，也就是说CPU响应中断的时间是在每条指令执行阶段的结束时刻，中断作用：
1）实现CPU与I/O设备的并行工作
2）处理硬件故障和软件错误
3）实现人机交互，用户干预机器需要用到中断系统
4）实现多道程序、分时操作，多道程序的切换需借助于中断系统
5）实时处理需要借助中断系统来实现快速响应
6）实现应用程序和操作系统的切换，称为“软中断”
7）多处理器系统中各处理器之间的信息交流和任务切换
CPU响应中断的条件：
1）中断源有中断请求
2）CPU允许中断及开中断
3）一条指令执行完毕，且没有更紧迫的任务
中断隐指令的任务：
1）关中断
2）保存断点：即程序计数器PC的内容。可以存入堆栈，也可以存入主存特定的单元
3）引出中断服务程序：取出中断服务程序的入口地址并传送给程序计数器PC。软件查询法、硬件向量法。中断向量是中断服务程序的入口地址，中断向量地址是指中断服务程序的入口地址的地址。
中断处理过程：
关中断→保存断点→引出中断服务程序→保存现场和屏蔽字→开中断→执行中断服务程序→关中断→恢复现场和屏蔽字→开中断→中断返回
- DMA方式基本概念
DMA是一种完全用硬件进行成组信息传送的控制方式，它具有程序中断的优点，即在数据准备阶段，CPU与外设并行工作。适用于磁盘机、磁带机等高速设备大批量数据的传送，它的硬件开销比较大。在DMA方式中，中断的作用仅限于故障和正常传送结束时的处理。
DMA控制器：
在DMA方式中，对数据传送过程进行控制的硬件称为DMA控制器（DMA接口）。DMA与CPU访问主存的方式：
1）停止CPU访存
2）DMA与CPU交替访存
3）周期挪用
- DMA与程序中断的联系区别
中断方式:外部设备每进行一个数据的输入/输出， 都要通过“中断申请要求CPU进行处理。CPU通过执行一段“中断服务程序完成数据的传输。
DMA方式: CPU通过对DMAC的初始化，启动一个数据块的传输操作。之后的数据传输通过信号的联络，在外设接口和存储器之间进行，CPU只需简单地让出总线，而无需其他操作。
根据上述比较，可以得到DMA工作方式的如下特点:
优点:
1) 对于CPU而言，它的任务仅仅是在一个数据块传输之前对DMAC进行初始化，CPU用于传输控制的操作达到最小(不考虑与通道10处理器方式的比较)，CPU的效率最高。CPU与外设“并行”工作。
2)外部设备一个数据输入输出完成后， 向DMAC申请进行数据传输，响应时间仅为DMAC的1 ~3个时钟周期。响应速度达到最快，可以满足高速传输的需要。
缺点:
1)实现DMA控制需要增加DMA控制器和总线控制逻辑，增加了系统的复杂性。
2) DMA传输需要占用总线，并且具有较高的“优先级"。这使得系统对其他设备的响应速度不能得到明确的保证。
- cpu响应中断需要满足哪些条件
1.有中断源发出的中断请求;
2.中断总允许位EA=1,即CPU开中断;
3.申请中断的中断源的中断允许位为1,即中断没有被屏蔽;
4.无同级或更高级中断正在被服务;
5.当前的指令周期已经结束
- 数据寻址方式？
1）隐含寻址：有利于缩短指令字长，缺点是需增加存储操作数或隐含地址的硬件
2）立即（数）寻址：指令在执行阶段不访问主存，指令执行时间最短；缺点是立即数大小受长度限制，灵活性较差。
3）直接寻址：指令在执行阶段仅访问一次主存，不需要做地址计算，简单直观，但寻址范围受地址码位数限制。
4）间接寻址：优点是可扩大寻址范围，便于编制程序；缺点是指令在执行阶段要多次访存，速度慢。
5）寄存器寻址：指令在执行阶段不访问主存，只访问寄存器，因寄存器数量较少，对应地址码长度较小，使得指令字短且因不用访存，所以执行速度快，支持向量/矩阵运算。缺点是寄存器价额昂贵，个数有限。
6）寄存器间接寻址比一般间接寻址速度快，指令执行阶段需要访问主存。
7）相对寻址：EA = (PC) + A。优点是操作数地址不固定，随PC值变化而变化，且与指令地址之间总是相差一个固定值，因此便于程序浮动。相对寻址广泛应用于转移指令。
8）基址寻址：EA = (BR) + A。基址寄存器BR的内容不变，面向操作系统，内容由操作系统或管理程序确定，主要用于解决程序逻辑空间和存储器物理空间的无关性。形式地址A可变。优点是可扩大寻址范围。用户不必考虑自己的程序存于主存的哪个空间区域，故有利于多道程序设计，并可用于编制浮动程序，单偏移量A位数较短。
9）变址寻址：EA = (IX) + A。变址寄存器面向用户，内容可由用户改变作为偏移量，形式地址A不变作为基地址。优点是扩大寻址范围，主要用于处理数组问题，适合编制循环程序。
10）堆栈寻址：硬堆栈即为寄存器堆栈；软堆栈是在主存中划出一段区域来做堆栈。读写单元的地址由堆栈指针SP给出。
- 什么是指令，时钟，总线周期，它们之间有什么关系?
- 指令周期：执行一条指令所需的时间。不同指令的指令周期长短是不同的，一个指令周期由几个总线周期组成。
- 时钟周期：CPU的时钟频率的倒数，也称为T状态。它是微处理器的最小动作单位时间。
- 总线周期：806CPU中，BIU完成一次访问存储器或I/O端口操作所需要的时间。每个总线周期至少包含4个时钟周期（T1~T4）,一般情况下，在总线周期的T1状态传送地址，T2~T4状态传送数据。
- 操作数的来源及对应寻址方式的指令执行速度有什么差异？
- 操作数的来源有4种：
- 立即数：参与操作的数据直接在指令中。
- 寄存器操作数：参与操作的数据存放在寄存器中。
- 存储器操作数：参与操作的数据存放在存储器中。
- I/O操作数：参与操作的数据来源于I/O端口
- 操作数在寄存器中的指令执行速度最快，因为它们可以在CPU内部立即执行。立即数寻址指令可直接从指令队列中取数，所以它们的执行速度也较快。而操作数在存储器中的指令执行速度较慢，因为它要通过总线与CPU之间交换数据，当CPU进行读写存储器的操作时，必须先把一个偏移量送到BIU，计算出20位物理地址，再执行总线周期去存取操作数，这种寻址方式最为复杂
- 存储器的分类有哪些？
存储器可以分为内部存储器和外部存储器。
内部存储器也称为内存，是主存储器，位于计算机主机的内部，用来存放系统软件和当前正在使用的或者经常使用的程序和数据，CPU可以直接对它们进行访问。内部存储器主要是半导体存储器，存取速度较快。内存的容量大小受到地址总线位数的限制，例如806CPU有20条地址总线，可以寻址空间为1MB。内部存储器按照存储器类别又可以分为随机存取存储器RAM和只读存储器ROM。RAM可以随机读写，断电后，所有存储数据全部消失。按照集成电路内部结构的不同，RAM又分为动态RAM和静态RAM两种。ROM只能读岀已存储的内容，不能随意写入，已存储的内容由厂家或用户预先用设备写入，因此是非易失性的，断电后数据也不会消失。一般来说，ROM中通常存储操作系统的程序或者用户固化的程序。
根据信息写入的方式不同，ROM又可分成下面五种：
- 掩膜型ROM中信息是在芯片制造时由厂家写人的，用户对这类芯片无法进行任何修改。
- 可编程只读存储器PROM是厂家根据用户需求将芯片内二极管烧断而存储其内容，一般固化程序用，写入后不可更改。
- 可擦除可编程只读存储器EPROM用设备写人内容后，可由紫外光照擦除其内容，以便重新写入程序。
- 电可擦除可编程只读存储器EPROM用设备写入内容后，可由加电擦除其内容,芯片可反复使用。
- 闪存(FlashMemory)闪存用设备写入内容后，可由加电擦除其部分内容，芯片可反复使用，闪存允许多线程重写，速度快，灵活性好。
外部存储器简称为外存，是辅助存储器。外存的特点是大容量、所存储的信息既可以修改，也可以保存，但是存取速度较慢，而且需要专门的设备来管理，比如，驱动器、控制芯片等。外存容量不受限制，也称为海量存储器。
外部存储器主要是磁记录存储器，典型的有软盘、硬盘。除此之外，还有光盘，磁带等。
Flash存储器是最近兴起的一种新型存储器。Flash存储器集成度高;是固态的存储介质，没有硬盘那样的机械装置，可靠性好，不易损坏;既有SRAM读写的灵活性和较快的访问速度，又有掉电后不丢失信息的特点。
- 为什么补码便于加减运算？
有了补码表示的被加（减）数和加（减）数,要完成计算补码表示的二数之和或二数之差,只需用二数的补码直接执行加减运算即可,符号位与数值位同等对待,一起参加运算,若运算结果不溢出,即不超出计算机所能表示的范围,则结果的符号位和数值位同时为正确值.此外,
- 运算结果的溢出判断方法？
- 如果运算的结果，超出了计算机能表示的数的范围，会得出错误的结果，这种情况称为溢出。
- 对于字长为n的计算机，那么它能表示的定点补码范围为-２n-1≤Ｘ≤２n-1１，若运算结果小于-２n-1或大于２n-1１，则发生溢出，发生溢出时数值的有效位占据了符号位。
两种方法：
用一位符号位判断溢出
用两位符号位判断溢出
一位符号位：
通常用符号位产生的进位和最高有效位向符号位产生的进位进行异或操作后，按其结果进行判断。—若异或结果为1，则溢出；—若异或结果为0，则没有溢出。
两位符号位：
- 数据存储的顺序？
大端模式：是指数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中，这样的存储模式类似于把数据当作字符串顺序处理：地址由小向大增加，而数据从高位往低位放；这和我们的阅读习惯一致。
小端模式：是指数据的高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址中，这种存储模式将地址的高低和数据位权有效地结合起来，高地址部分权值高，低地址部分权值低。目前Intel的80x86系列芯片是唯一还在坚持使用小端的芯片，ARM芯片默认采用小端，但可以切换为大端；而MIPS等芯片要么采用全部大端的方式储存，要么提供选项支持大端—可以在大小端之间切换。另外，对于大小端模式的处理也和编译器的实现有关，在C语言中，默认是小端（但在一些对于单片机的实现中却是基于大端），Java是平台无关的，默认是大端。在网络上传输数据普遍采用的都是大端。
- 保护模式和实模式？
保护模式:
寻址采用32位段地址和偏移量，最大寻址空间4GB，最大分段4GB(PentiumPre及以后为64GB)。在保护模式下CPU可以进入虚拟806方式，这是在保护模式下的实模式程序运行环境。保护模式下程序的运行:保护模式—从程序运行说起无论实模式还是保护模式，根本的问题还是程序如何在其中运行。因此我们在学习保护模式时应该时刻围绕这个问题来思考。和实模式下一样，保护模式下程序运行的实质仍是“CPU执行指令，操作相关数据”，因此实模式下的各种代码段、数据段、堆栈段、中断服务程序仍然存在，且功能、作用不变。那么保护模式下最大的变化是什么呢?答案可能因人而异，我的答案是“地址转换方式”变化最大。
实模式:
实模式是指寻址采用和806相同的16位段地址和偏移量，最大寻址空间1MB，最大分段64KB。可以使用32位指令。32位的x86CPU用作高速的806。实模式下程序的运行:程序运行的实质是什么?其实很简单,就是指令的执行,显然CPU是指令得以执行的硬件保障，那么CPU如何知道指令在什么地方呢?对了，80x86系列是使用CS寄存器配合IP寄存器来通知CPU指令在内存中的位置.程序指令在执行过程中一般还需要有各种数据,80x86系列有DS、ES、FS、GS、S等用于指示不同用途的数据段在内存中的位置。程序可能需要调用系统的服务子程序，80x86系列使用中断机制来实现系统服务。总的来说，这些就是实模式下一个程序运行所需的主要内容(其它如跳转、返回、端口操作等相对来说比较次要。)两者区别：
保护模式和实模式的根本区别是进程内存受保护与否。可寻址空间的区别只是这一原因的结果。实模式将整个物理内存看成分段的区域,程序代码和数据位于不同区域，系统程序和用户程序没有被区别对待，而且每一个指针都是指向"实在"的物理地址。这样一来，用户程序的一个指针如果指向了系统程序区域或其他用户程序区域，并且改变了值，那么对于这个被修改的系统程序或用户程序，其后果很可能是灾难性的。为了克服这种低劣的内存管理方式，处理器厂商开发出保护模式。这样一来，物理内存地址不能直接被程序访问，程序内部的地址（虚拟地址）要由操作系统转化为物理地址去访问，程序对此一无所知。至此，进程（这时我们可以称程序为进程了）有了严格的边界，任何其他进程根本无法访问不属于自己的物理内存区域；甚至在自己的虚拟地址范围内也不是可以任意访问的，因为有一些虚拟区域已经被放进一些公共系统运行库，这些区域也不能随意修改。CPU启动环境为16位实模式，之后可以切换到保护模式。但从保护模式无法切换回到实模式。
- 虚拟存储器是什么？
程序的互斥性原理：两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥。也就是说，一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。在多道程序环境下，存在着临界资源，它是指多进程存在时必须互斥访问的资源。也就是某一时刻不允许多个进程同时访问，只能单个进程的访问。我们把这些程序的片段称作临界区或临界段，它存在的目的是有效的防止竞争条件又能保证最大化使用共享数据。程序的局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。局部性原理又表现为：时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。
空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。根据程序执行的互斥性和局部性两个特点，我们允许作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，这样以来，在一个小的主存空间就可以运行一个比它大的作业。同时，用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制也就是说，用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说，好像计算机系统具有一个容量很大的主存储器，称为“虚拟存储器”。虚存容量不是无限的，虚拟内存的最大容量是由计算机的地址结构确定的。且虚拟内存只是在逻辑上对内存容量加以扩充，其逻辑容量由内存容量和外存容量之和决定。地址总线结构能决定主存的访问范围。所以即使你的磁盘再大，但是地址寄存器访问主存的范围很小的话，虚拟存储器容量依然是很小的。
- 操作系统
什么是文件系统？文件系统干吗用的？ 我说用来 管理文件、磁盘等，老师说那肯定的啊，我问你干嘛用的！
文件是具有文件名的一组相关信息的集合。由若干个记录组成。文件系统是操作系统中与文件管理有关的软件和数据的集合。功能1实现按文件名存取文件信息2为用户提供统一友好的接口3实施对文件和文件目录的管理4文件存储器空间的分配与回收5提供有关文件的共享和保护。
- 软链接和硬链接的区别？
- 定义不同
- 软链接又叫符号链接，这个文件包含了另一个文件的路径抄名。可以是任意文件或目录，可以链接不同文件系统的文件。
- 硬链接就是一个文件的一个或多个文件名。把文件名和计算机文件系统使用的节点号链接起来。因此我们可以用多个文件名与同一个文件进行链接，这些文件名可以在同一目录或不同目录。
- 限制不同
- 硬链接只能对已存在的文件进行创建，不能交叉文件系统进行硬链接的创建；
- 软链接可对不存在的文件或目录创建软链接；可百交叉文件系统；
- 创建方式不同
- 硬链接不能对目录进行创建，只可对文件创建；
- 软链接可对文件或目录创建；
- 影响不同
- 删除一个硬链接文件并不影响其他有相同 inode 号的文件。
- 删除软链接并不影响被指向的度文件，但若被指向的原文件被删除，则相关软连接被称为死链接（即 dangling link，若被指向路径文件被重新创建，死链接可恢复为正常的软链接）。
- DMA和通道方式的区别是什么？
通道控制（Channel Control）方式与DMA方式类似，也是一种以内存为中心，实现设备和内存直接交换数据的控制方式。
与DMA方式不同的是，在DMA方式中，数据的传送方向、存放数据的内存始址以及传送的数据块长度等都由CPU控制，而在通道方式中，这些都由通道来进行控制。另外，DMA方式每台设备至少需要一个DMA控制器，一个通道控制器可以控制多台设备。
- 什么内部碎片？什么是外部碎片？
- 内存中
- 内部碎片：已经被分配出（能明确指出属于那个进程）却不能被利用的内存空间
- 外部碎片：还没有被分配出的空间，不属于任何进程。
- 硬盘上
- 外部碎片：（一般意义上的磁盘碎片，磁盘碎片清理工具中能清理磁盘上的外部碎片，清除不了磁盘的内部碎片，除非改变文件系统的分配单位即簇的大小，使之是一个文件的大小的整数倍。）实际上指的是一个文件占据那些簇是不连续的，就相当于文件被分割开来，分别存放在相互间断的几段簇上。文件被分割为几个部分就是几个碎片。所以碎片其实是指文件碎片
- 什么是局部性原理？
局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。
- 有哪些文件分配方式？
- 连续分配
- 链接分配
- 索引分配
- 文件存储空间管理有哪些方法？
- 空闲表法
- 成组链接法
- 位图法
- 空闲链表法
- 内存连续分配和非连续分配方式有哪几种？
- 连续分配
- 单一连续分配
- 固定分区分配——内部碎片
- 动态分配——外部碎片——首次、最佳、最坏、邻近适应
- 非连续分配
- 页式存储管理——页面、地址结构、页表、地址变换机构及变换过程、快表
- 段式存储管理——段表、地址变换机构、段的共享与保护
- 段页式存储管理——段表、页表
- 操作系统页表和段表的区别
- 进程有哪些通信方法？
- 共享内存
- 管道通信
- 消息传递
- 编译时候静态编译和动态编译有什么区别。
动态编译的可执行文件需要附带一个的动态链接库，在执行时，需要调用其对应动态链接库中的命令。优点一方面是缩小了执行文件本身的体积，一方面是加快了编译速度，节省了系统资源。缺点一是哪怕是很简单的程序，只用到了链接库中的一两条命令，也需要附带一个相对庞大的链接库；二是如果其他计算机上没有安装对应的运行库，则用动态编译的可执行文件就不能运行。静态编译就是编译器在编译可执行文件的时候，将可执行文件需要调用的对应动态链接库(.so)中的部分提取出来，链接到可执行文件中去，使可执行文件在运行的时候不依赖于动态链接库。编译慢，兼容性好。
- CSMA/CA和CSMA/CD的英文
Carrier Sense Multiple Access with Collision Detection，意思是载波侦听多路访问／冲突检测。 采用该协议要求设备在发送帧的同时要对信道进行侦听，以确定是否会发生信道冲突，若在发送数据过程中检测到冲突，则需要进行冲突处理。整个协议的处理规程如下： 1 监听当前信道上是否有数据再发送，如果信道空闲，直接发送数据，如果信道忙，则按照一定的退避算法进行延时监听。 2 当信道允许发送数据时，发送数据。 3 数据发送过程中，边发送边监听，如果发送过程中检测到冲突，则停止发送数据，并发送阻塞信息，强化冲突，并转入1。Carrier Sense Multiple Access with Collision Avoidance，意思是载波侦听多路访问／冲突避免。 采用该协议要求设备要主动避免冲突而非被动侦测的方式来解决冲突问题。避免冲突的方法主要有两个： 一是监听到信道空闲时，并不是立即发送，而是等待一段时间再发送数据。 二是先发送一个很小的信道侦测帧RTS，如果收到最近的接入点返回的CTS，就认为信道是空闲的，然后再发送数据。 协议的主要流程如下： 1 首先检测信道是否有使用，如果检测出信道空闲，则等待一段随机时间后，才送出数据。 2 接收端如果正确收到此帧，则经过一段时间间隔后，向发送端发送确认帧ACK。 3 发送端收到ACK帧，确定数据正确传输，在经历一段时间间隔后，再发送数据。--------------------- 区别如下:1.两者的传输介质不同,CSMA/CD用于总线式以太网,而CSMA/CA则用于无线局域网802.11a/b/g/n等等； 2.检测方式不同,CSMA/CD通过电缆中电压的变化来检测,当数据发生碰撞时,电缆中的电压就会随着发生变化；而CSMA/CA采用能量检测(ED)、载波检测(CS)和能量载波混合检测三种检测信道空闲的方式。3.CSMA/CD:带有冲突检测的载波监听多路访问，可以检测冲突，但无法“避免”。CSMA/CA：带有冲突避免的载波监听多路访问，发送包的同时不能检测到信道上有无冲突，只能尽量“避免”。
- I/O接口和I/O端口有区别？ I/O 接口的作用是什么？
I/O接口芯片都有一个或几个端口，一个端口对应于接口芯片内部的一个寄存器或一组寄存器，计算机系统要为每个端口分配一个地址，各个端口的地址是唯一的，不能重复专。在信息传送过程中，接口起着数据锁存、数据缓冲、输入/输出、联属络、数据转换、中断管理、时序控制、可编程、电器特征匹配等作用
- 堆栈溢出的原因有哪些？
- 不断的new 一个对象，一直创建新的对象
- 死循环或者是递归太深，递归的原因，可能太大，也可能没有终止。
- 什么是操作系统？操作系统的组成？
- 操作系统是管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作是控件其他程序运行，管理系统资源并为用户提供操作界面的系统软件的集合，是用户与计算机硬件系统之间的接口。操作系统身负诸如配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统的形态非常多样。不同机器安装的OS可从简章到复杂，可从手机的嵌入式系统到超级电脑的大型操作系统。目前微机上常见的操作系统有DOS,os/2,unix,linux,xenix,windows,netware等
- 组成：对cpu的使用进行管理的进程高度程序，对内存分配管理内存管理程序。对输入输出设备进行管理的设备驱动程序。对外存中信息进行管理的文件系统。
- 操作系统有哪些主要功能？
- 进程与处理机管理、
- 作业管理、
- 存储储管理、
- 设备管理、
- 文件管理。
- 系统软件和应用软件分别是什么？
- 系统软件是用于实现对计算机资源管理、控制和维护，方便人们使用计算机而配置的软件，如操作系统，语言的汇编、解释、编译程序，数据库管理程序。
- 应用软件是指用户利用计算机以及系统软件编制的解决实际问题的程序，它包括支撑软件和用户自己编写的程序。支撑软件包括WPS、AutoCAD、Microsft-Ofice等。
- I/O端口的种类有哪些？
CPU与外设通信时，传送的信息主要包括数据信息、状态信息和控制信息。在接口电路中，这些信息分别进入不同的寄存器，通常将这些寄存器和它们的控制逻辑统称为I/O端口，CPU可对端口中的信息直接进行读写。在一般的接口电路中都要设置以下几种端口：
- 数据端口用来存放外设送往CPU的数据以及CPU要输出到外设去的数据。这些数据是主机和外设之间交换的最基本的信息，长度一般为1~2字节。数据端口主要起数据缓冲的作用。
- 状态端口主要用来指示外设的当前状态。每种状态用1位表示，每个外设可以有几个状态位，它们可由CPU读取，以测试或检查外设的状态，决定程序的流程。需要指岀的是，除了状态端口中的内容外，接口电路中往还会有若干状态线,它们用电平的高低来指示外设的当前状态，实现CPU与外设之间的通信联络，它们的名称和电平与状态位之间不一定完全对应。接口电路状态端口中最常用的状态位有：(1)准备就绪位、(2)忙碌位、(3)错误位。
- 命令端口也称为控制端口，它用来存放CPU向接口发出的各种命令和控制字，以便控制接口或设备的动作。常见的命令信息位有启动位、停止位、允许中断位等。接口芯片不同，控制字的格式和内容是各不相同的，常见的控制字有方式选择控制字，操作命令字等。
- I/O端口的寻址方式的特点？
CPU对外设的访问实质上是对I/O接口电路中相应的端口进行访问，因此和存储器那样，也需要由译码电路来形成I/O端口地址。I/O端口的编址方式有两种，分别称为存储器映象寻址方式和I/O指令寻址方式。
- 存储器映像寻址方式
- 定义：该方式是指把I/O端口和存储单元统一编址，即把I/O端口看成是存储器的一部分，一个I/O端口的地址就是一个存储单元的地址。
- 优点：
- CPU访问存储单元的所有指令都可用于访问I/O端口，CPU访问存储单元的所有寻址方式也就是CPU访问I/O端口的寻址方式。
- 不用设置专门的I/O指令，微处理器的指令集中不必包含I/O操作指令，简化了指令系统的设计。
- 能用类型多，功能强的访问存储器指令，对I/O设备进行方便、灵活的操作
- 缺点：
- I/O端口占用了内存空间。
- 是访问存储器还是访问I/O端口，在程序中不能一目了然。
- I/O独立编址方式
- 定义：是指把I/O端口和存储单元各自编址，即使地址编号相同也无妨。
- 优点：
- I/O端口不占用内存空间；
- 访问I/O端口指令仅需两个字节，执行速度快；
- 读程序时只要是I/O指令，即知是CPU访问I/O端口，使得程序清晰，可读性好。
- I/O地址译码电路较简单。
- 缺点：
- 要求CPU指令系统有独立的I/O指令，这些指令的功能没有访问存储器指令强；
- CPU访问I/O端口的寻址方式少。
- CPU还需提供能够区分访问内存和访问I/O的硬件引脚信号。
- 寻找中断源的方法有哪些？
寻找中断源可以用查询中断及矢量中断两种方法。
查询中断是采用软件查询方法，中断响应后启动中断查询程序，依次查询哪个设备的中断请求触发器为1，检测到后，转向此设备预先设置的中断服务程序入口地址。此方法较简,单，但花费时间多，并且后面的设备服务机会少，在806系统中一般采用矢量中断方法。
矢量中断是将每个设备的中断服务程序的入口地址(矢量地址)集中，依次放在中断向量表中。当CPU响应中断后，控制逻辑根据外设提供的中断类型号查找中断向量表，然后将中断服务程序的入口地址送到段寄存器和指令指针寄存器，CPU转入中断服务子程序。这样大大加快了中断处理的速度。矢量中断:是根据CPU响应中断时取得中断处理子程序入口地址的方式而得名的，它是一种寻找中断源的方法。它提供一个矢量，指向中断处理子程序的起始地址。
中断矢量:就是中断处理子程序的起始地址。
中断矢量表：全部矢量放在内存的某一区域中，形成一个中断矢量表。
- 矢量中断中，中断类型号是怎么获取的？
- 对于除法出错，单步中断，不可屏蔽中断NMI，断点中断和溢出中断，CPU分别自动提供中断类型号0~4。
- 对于用户自己确定的软件中断INTn，类型号由n决定。
- 对于外部可屏蔽中断INTR，可用硬件电路(例如，通用并行接口芯片821)设计产生中断类型号。
- 对于外部可屏蔽中断INTR，也可以用可编程中断控制器8259A获得中断类型号。
- 中断的优先级次序是什么？对于可屏蔽中断的优先级设定方法？
优先级从高到低的次序为：内中断(除法错，INTO，INTn)、不可屏蔽中断(NMI)、可屏蔽中断(INTR)、单步中断
对可屏蔽中断的优先级设定有三种方法：
1.软件查询中断优先级
2.硬件查询优先方式—菊花链法
3.矢量中断优先级
- 串行通信和并行通信的区别？
计算机与外部的信息交换称为通信，基本的通信方式有两种，一种是并行通信，另一种是串行通信。
- 并行通信时，数据各位同时传送。这种方式传输数据的速度快，但使用的通信线多，如果要并行传送8位数据，需要用8根数据线，另外还要加上一些控制信号线。随着传输距离的增加，通信线成本的增加将成为突出的问题，而且传输的可靠性随着距离的增加而下降。因此并行通信适用于近距离传送数据的场合。
- 在远距离通信时，一般都采用串行通信方式。它具有需要的通信线少和传送距离远等优点。串行通信时，要传送的数据或信息必须按一定的格式编码，然后在单根线上，按一位接一位的先后顺序进行传送。发送完一个字符后，再发送第二个。接收数据时，每次从单根线上一位接一位地接收信息，再把它们拼成一个字符，送给CPU作进一步处理。当微机与远程终端或远距离的中央处理机交换数据时，都采用串行通信方式。采用串行通信的另一个出发点是，有些外设，如调制解调器(MODEM)、鼠标器等，本身就要用串行方式通信，因为这些设备是以串行方式存取数据的。此外，有些外设，如打印机、绘图仪等，除了使用并行方式外，也可采用串行方式与计算机通信。
- 从电脑开机开始，是如何触发操作系统开始工作的
给主机和其他设备供电—>CPU读取指令跳转到系统BIOS中真正的启动代码处—>硬件自检—>BIOS把控制权转交给下一阶段的启动程序—>BIOS按照"启动顺序"，把控制权转交给排在第一位的储存设备—>硬盘启动—>控制权转交给操作系统后，操作系统的内核首先被载入内存。以Linux系统为例，先载入/bot目录下面的kernl。内核加载成功后，第一个运行的程序是/sbin/it。它根据配置文件（Debian系统是/etc/intab）产生int进程。这是Linux启动后的第一个进程，pid进程编号为1，其他进程都是它的后代。然后，int线程加载系统的各个模块，比如窗口程序和网络程序，直至执行/bin/login程序，跳出登录界面，等待用户输入用户名和密码。
- 论述操作系统中系统调用过程
系统调用提供了用户程序和操作系统之间的接口，应用程序通过系统调用实现其余OS的通信，并取得它的服务。系统调用不仅可供所有的应用程序使用，而且也可供OS本身的其它部分，如命令处理程序。
系统调用的处理步骤（三步）：
首先，将处理机状态由用户态转为系统态；然后由硬件和内核程序进行系统调用的一般性处理，即首先保护被中断进程的CPU环境，将处理机状态字PSW、程序计数器PC、系统调用号、用户栈指针以及通用寄存器内容等压入堆栈；再然后将用户定义的参数传送到指定的地址保存起来。
其次，分析系统调用类型，转入相应的系统调用处理子程序。（通过查找系统调用入口表，找到相应处理子程序的入口地址转而去执行它。）
最后，在系统调用处理子程序执行完后。，应恢复被中断的货设置新进程的CPU现场，然后返回被中断进程或新进程，继续往下执行。
- 死锁的定义（本人复试被问过）
死锁：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
- 硬中断和软中断是什么，区别是什么
软中断：
- 编程异常通常叫做软中断。
- 软中断是通讯进程之间用来模拟硬中断的一种信号通讯方式。
- 中断源发中断请求或软中断信号后,CPU或接收进程在适当的时机自动进行中断处理或完成软中断信号对应的功能。
- 软中断是软件实现的中断,也就是程序运行时其他程序对它的中断;而硬中断是硬件实现的中断,是程序运行时设备对它的中断。
硬中断：
- 硬中断是由外部事件引起的因此具有随机性和突发性；软中断是执行中断指令产生的，无外部施加中断请求信号，因此中断的发生不是随机的而是由程序安排好的。
- 硬中断的中断响应周期，CPU需要发中断回合信号（NMI不需要），软中断的中断响应周期，CPU不需发中断回合信号。
- 硬中断的中断号是由中断控制器提供的（NMI硬中断中断号系统指定为02H）；软中断的中断指令直接给出，无需使用中断控制器。
- 硬中断是可屏蔽的（NMI硬中断不可屏蔽），软中断不可屏蔽。
区别：
- 软中断发生的时间是由程序控制的,而硬中断发生的时间是随机的
- 软中断是由程序调用发生的,而硬中断是由外设引发的
- 硬件中断处理程序要确保它能快速地完成它的任务,这样程序执行时才不会等待较长时间
- 描述中断全过程
中断全过程指的是从中断源发出中断请求开始，CPU响应这个请求，现行程序被中断，转至中断服务程序，直到中断服务程序执行完毕，CPU再返回原来的程序继续执行的整个过程。大体上可以把中断全过程分为5个阶段：中断请求、中断判优、中断响应、中断处理和中断返回。中断处理过程基本上由3部分组成，第一部分为准备部分，其基本功能是保护现场，对于非向量中断方式则需要确定中断源，最后开放中断，允许更高级的中断请求打断低级的中断服务程序；第二部分为处理部分，即真正执行具体的为某个中断源服务的中断服务程序；第三部分为结尾部分，首先要关中断，以防止在恢复现场过程中被新的中断请求打断，接着恢复现场，然后开放中断，以便返回原来的程序后可响应其他的中断请求
- 简述open打开文件的过程
首先,操作系统根据文件名a，在系统文件打开表中查找
第一种情况：
如果文件a已经打开，则在进程文件打开表中为文件a分配一个表项，然后将该表项的指针指向系统文件打开表中和文件a对应的一项;然后再PCB中为文件分配一个文件描述符fd，作为进程文件打开表项的指针,文件打开完成。
第二种情况：
如果文件a没有打开，查看含有文件a信息的目录项是否在内存中，如果不在，将目录表装入到内存中，作为cache；根据目录表中文件a对应项找到FCB在磁盘中的位置；将文件a的FCB装入到内存中的Activeinode中；然后在系统文件打开表中为文件a增加新的一个表项，将表项的指针指向ActiveInode中文件a的FCB；然后在进程的文件打开表中分配新的一项，将该表项的指针指向系统文件打开表中文件a对应的表项；然后在PCB中，为文件a分配一个文件描述符fd，作为进程文件打开表项的指针,文件打开完成。
- 进程与线程的区别
- 调度：线程是独立调度的基本单位，进程是资源拥有的基本单位。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行线程切换，将会引起进程切换。
- 拥有资源：进程是拥有资源的基本单位，而线程不拥有系统资源（除了少量资源，比如栈，程序计数器，寄存器），不过线程可以访问其隶属进程的系统资源。
- 并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且同一个进程内的多个线程之间也可以并发执行，能提高系统的吞吐量，系统的并发性也更好。
- 系统开销：在创建进程和撤销进程时，系统都要为之分配或回收资源，所以操作系统为进程付出的系统开销远大于创建线程或撤销线程的开销。
- 同步和通信：多线程之间的同步和通信容易实现。
- 进程和程序的区别
- 进程是一个动态概念，而程序是一个静态概念。
- 进程具有并行特征，而程序不反映执行所以没有并行特征
- 进程是竞争计算机系统资源的基本单位，而程序不反映执行也就不会竞争计算机系统资源
- 不同的进程可以包含同一程序，只要该程序所对应的数据集不同。
- 常用的存储保护方法
- 界限寄存器
- 上下界寄存器方法
- 基址、限长寄存器方法
- 存储保护键：给每个存储块分配一个单独的存储键，它相当于一把锁。
- 什么是饥饿？与死锁有什么差别？
等待时间给进程推进和响应带来明显影响时成为进程饥饿。饥饿并不代表系统一点死锁，但至少有一个程序的执行被无限期地推迟。
差别：
- 进入饥饿的进程可以只有一个，但是死锁必须大于等于两个；
- 出于饥饿状态的进程可以是一个就绪进程，但是死锁状态的进程必定是阻塞进程。
- 操作系统中的信号量
信号量是一个确定的二元组（s，q），其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目；当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。
信号量分类：
- 整型信号量：所谓整型信号量就是一个用于表示资源个数的整型量
- 记录型信号量（资源信号量）：就是用一个结构体实现，里面包含了表示资源个数的整型量和一个等待队列。
信号量的应用：
- 实现进程同步
- 实现进程互斥
- 存储器管理应具有的功能
存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器，故应具有以下功能：
- 内存的分配和回收：实施内存的分配，回收系统或用户释放的内存空间。
- 地址变换：提供地址变换功能，将逻辑地址转换成物理地址。
- 扩充内存：借助于虚拟存储技术活其他自动覆盖技术，为用户提供比内存空间大的地址空间，从逻辑上扩充内存。
- 存储保护：保证进入内存的各道作业都在自己的存储空间内运行，互不干扰。
- 程序的装入方式有哪些？
- 绝对装入：在编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计。
- 可重定位装入：根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称静态重定位。当操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址。
- 动态运行装入：允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现要依靠硬件地址变换机构。
- 程序的链接方式有哪些？
- 静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开。
- 装入时动态链接：将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式。
- 运行时动态链接：知道程序运行过程中需要一些模块时，才对这些模块进行链接。
- 交换技术，覆盖技术，以及两者的区别。
覆盖技术：把一个大的程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位，把程序执行时并不要求同时装入内存的覆盖组成一组，成为覆盖段，这个覆盖段分配到同一个存储区域，这个存储区域成为覆盖区，它与覆盖段一对应。覆盖段的大小由覆盖段中最大的覆盖来确定。（为了解决内存容量太小的问题，打破了必须将一个程序全部信息装入内存后才能运行的限制）
交换技术：把暂时不用的某个程序及数据部分从内存移到外存中去，以便腾出必要的内存空间；或者把指定的程序或数据从外存读到相应的内存中，并将控制权交给他，让其在系统上运行的一种内存扩充技术。处理器的中级调度就是采用交换技术。
区别：
- 与覆盖技术相比，交换技术不要求程序员给出的程序段之间的覆盖结构；
- 交换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行；
- 覆盖技术只能覆盖于覆盖程序段无关的程序段，交换进程由换出和换入两个过程组成。
- 是什么进程线程树图
进程树是一个形象化的比喻，比如一个进程启动了一个程序，而启动的这个进程就是原来那个进程的子进程，依此形成的一种树形的结构，我们可以在进程管理器选择结束进程树，就可以结束其子进程和派生的子进程。
- 什么是原子操作？什么是PV操作？
原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何contexswitch。P、V操作以原语形式实现，保证了对信号量进行操作过程中不会被打断或阻塞。P操作相当于申请资源，V操作相当于释放资源。P操作和V操作必定成对出现，但未必在同一个进程中。
- 硬实时和软实时
硬实时操作系统中，系统必须在特定的时间内完成指定的应用，具有较强的“刚性”，而分时操作系统则注重将系统资源平均地分配给各个应用，不太在意各个应用的进度如何，什么时间能够完成。不过，就算是实时操作系统，其“刚性”和“柔性”的程度也有所不同，就好像是系统的“硬度”有所不同，因而有了所谓的“硬实时(hardeal-time)”和“软实时(softreal-time)”。硬实时系统有一个刚性的、不可改变的时间限制，它不允许任何超出时限的错误。超时错误会带来损害甚至导致系统失败、或者导致系统不能实现它的预期目标。软实时系统的时限是一个柔性灵活的，它可以容忍偶然的超时错误。失败造成的后果并不严重，例如在网络中仅是轻微地降低了系统的吞吐量。
- 试说明DMA的工作流程。
以从磁盘读入数据为例，说明DMA的工作流程。当CPU要从磁盘读入数据块时，先向磁盘控制器发送一条读命令。该命令被送到命令寄存器CR中。同时还发送本次要读入数据的内存起始目标地址，送入内存地址寄存器MAR；本次要读数据的字节数送入数据计数器DC，将磁盘中的源地址直接送DMA控制器的I/O控制逻辑上。然后启动DMA控制器传送数据，以后CPU便处理其它任务。整个数据传送过程由DMA控制器控制。
- 为何要引入设备独立性？如何实现设备独立性？
现代操作系统为了提高系统的可适应性和可扩展性，都实现了设备独立性或设备无关性。基本含义是应用程序独立于具体使用的物理设备，应用程序以逻辑设备名请求使用某类设备。实现了设备独立性功能可带来两方面的好处：
-
-
-
- 设备分配时的灵活性；
- 易于实现I/O重定向。
-
-
为了实现设备的独立性，应引入逻辑设备和物理设备概念。在应用程序中，使用逻辑设备名请求使用某类设备；系统执行时是使用物理设备名。鉴于驱动程序是与硬件或设备紧密相关的软件，必须在驱动程序之上设置一层设备独立性软件，执行所有设备的公有操作、完成逻辑设备名到物理设备名的转换（为此应设置一张逻辑设备表）并向用户层（或文件层）软件提供统一接口，从而实现设备的独立性。
- 何谓提前读、延迟写和虚拟盘？
提前读是指在读当前盘块的同时，将下一个可能要访问的盘块数据读入缓冲区，以便需要时直接从缓冲区中读取，无需启动磁盘。
延迟写是指在写盘块时，将对应缓冲区中的立即写数据暂时不立即写以备不久之后再被访问，只将它置上“延迟写”标志并挂到空闲缓冲队列的末尾。当移到空闲缓冲队首并被分配出去时，才写缓冲区中的数据。只要延迟写块仍在空闲缓冲队列中，任何要求访问都可直接从其中读出数据或将数据写入其中，而不必去访问磁盘。
虚拟盘又称RAM盘，是利用内存空间仿真磁盘。其设备驱动程序可以接受所有标准的磁盘操作，但这些操作不是在磁盘上而是在内存中，因此速度更快。
- Windows下的内存是如何管理的？
Windows提供了3种方法来进行内存管理：虚拟内存，最适合用来管理大型对象或者结构数组；内存映射文件，最适合用来管理大型数据流（通常来自文件）以及在单个计算机上运行多个进程之间共享数据；内存堆栈，最适合用来管理大量的小对象。Windows操纵内存可以分两个层面：物理内存和虚拟内存。其中物理内存由系统管理，不允许应用程序直接访问，应用程序可见的只有一个2G地址空间，而内存分配是通过堆进行的。对于每个进程都有自己的默认堆，当一个堆创建后，就通过虚拟内存操作保留了相应大小的地址块（不占有实际的内存，系统消耗很小）。当在堆上分配一块内存时，系统在堆的地址表里找到一个空闲块（如果找不到，且堆创建属性是可扩充的，则扩充堆大小），为这个空闲块所包含的所有内存页提交物理对象（在物理内存上或硬盘的交换文件上），这时就可以访问这部分地址。提交时，系统将对所有进程的内存统一调配，如果物理内存不够，系统试图把一部分进程暂时不访问的页放入交换文件，以腾出部分物理内存。释放内存时，只在堆中将所在的页解除提交（相应的物理对象被解除），继续保留地址空间。如果要知道某个地址是否被占用/可不可以访问，只要查询此地址的虚拟内存状态即可。如果是提交，则可以访问。如果仅保留，或没保留，则产生一个软件异常。此外，有些内存页可以设置各种属性。如果是只读，向内存写也会产生软件异常。
- 什么是临界区？如何解决冲突？
每个进程中访问临界资源的那段程序称为临界区，每次只准许一个进程进入临界区，进入后不允许其他进程进入。
- 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入；
- 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待；
- 进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区
- 如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
- 什么是缓冲区溢出？有什么危害？其原因是什么？
缓冲区溢出是指当计算机向缓冲区内填充数据时超过了缓冲区本身的容量，溢出的数据覆盖在合法数据上。危害：在当前网络与分布式系统安全中，被广泛利用的50%以上都是缓冲区溢出，其中最著名的例子是198年利用fingerd漏洞的蠕虫。而缓冲区溢出中，最为危险的是堆栈溢出，因为入侵者可以利用堆栈溢出，在函数返回时改变返回程序的地址，让其跳转到任意地址，带来的危害一种是程序崩溃导致拒绝服务，另外一种就是跳转并且执行一段恶意代码，比如得到shel，然后为所欲为。通过往程序的缓冲区写超出其长度的内容，造成缓冲区的溢出，从而破坏程序的堆栈，使程序转而执行其它指令，以达到攻击的目的。造成缓冲区溢出的主原因是程序中没有仔细检查用户输入的参数。
- 线程的实现方式
线程的实现可分为两大类，用户级线程（user-lvelthread，ULT）和内核级线程（kernl-evlthread，KLT）。后者又称为内核支持的线程或轻量级进程。
1.用户级线程
在一个纯粹的用户级线程软件中，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。使用户级线程而不是内核级线程的优点有：
- 线程切换不需要内核态特权，进程并不需要为了线程管理而切换到内核态
- 可以为应用程序量身定做调度算法而不扰乱底层的操作系统调度程序
- 用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程相比内核级线程，用户级线程有两个明显的缺点：
- 许多系统调用都会引起阻塞，当用户级线程执行一个系统调用时，不仅这个线程会被阻塞，进程中的所有线程都会被阻塞
- 在纯粹的用户级线程策略中，一个多线程应用程序不能利用多处理技术
2.内核级线程
在一个纯粹的内核级线程软件中，有关线程管理的所有工作都是由内核完成的，应用程序部分没有进行线程管理的代码，只有一个到内核线程设施的应用程序编程接口（API）。该方法克服了用户级线程方法的两个基本缺陷：内核可以同时把同一个进程的多个线程调度到多个处理器中；如果进程中的一个线程被阻塞，内核可以调度同一个进程中的另一个线程。相比用户级线程它的主要缺点是：把控制从一个线程传送到进程中的另一个线程时，需要到内核的状态切换。某些操作系统采用组合用户级线程和内核级线程的方法，同一个应用程序中的多个线程可以在多个处理器上并行的运行，某个会引起阻塞的系统调用不会阻塞整个进程。如果设计正确，该方法会结合两种线程的优点，同时减少他们的缺点。
- 说分段和分页
页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要。页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。分页的作业地址空间是一维的，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
- 说出你所知道的保持进程同步的方法?
进程间同步的主要方法有原子操作、信号量机制、自旋锁、管程、会合、分布式系统等。
- 批处理操作系统、分时操作系统和实时操作系统的特点各是什么？
- 批处理操作系统的特点：成批处理，系统吞吐量高，资源利用率高，用户不能直接干预作业的执行。
- 分时操作系统的特点：多路性、独立性、及时性、交互性。
- 实时操作系统的特点：及时响应、快速处理；高可靠性和安全性；不要求系统资源利用率。
- 中断和轮询的特点
对I/O设备的程序轮询的方式，是早期的计算机系统对I/O设备的一种管理方式。它定时对各种设备轮流询问一遍有无处理要求。轮流询问之后，有要求的，则加以处理。在处理I/O设备的要求之后，处理机返回继续工作。尽管轮询需要时间，但轮询要比I/O设备的速度要快得多，所以一般不会发生不能及时处理的问题。当然，再快的处理机，能处理的输入输出设备的数量也是有一定限度的。而且，程序轮询毕竟占据了CPU相当一部分处理时间，因此，程序轮询是一种效率较低的方式，在现代计算机系统中已很少应用。程序中断通常简称中断，是指CPU在正常运行程序的过程中，由于预先安排或发生了各种随机的内部或外部事件，使CPU中断正在运行的程序，而转到为响应的服务程序去处理。轮询—效率低，等待时间很长，CPU利用率不高。中断—容易遗漏一些问题，CPU利用率高。
- 什么是TLB？
TLB的作用是在处理器访问内存数据的时候做地址转换。TLB的全称是TranslationLokasideBufer，可以翻译做旁路缓冲，是一个具有并行查询能力的特殊高速缓冲寄存器。TLB中存放了一些页表文件，文件中记录了虚拟地址和物理地址的映射关系。当应用程序访问一个虚拟地址的时候，会从TLB中查询出对应的物理地址，然后访问物理地址。TLB通常是一个分层结构，使用与Cache类似的原理。处理器使用一定的算法把最常用的页表放在最先访问的层次。
- 什么是微内核？微内核的好处有哪些？
答:微内核(Microkernel)是提供操作系统核心功能的内核的精简版本，它设计成在很小的内存空间内增加移植性，提供模块化设计，以使用户安装不同的接口，如Dos、Workplace0S、WorkplaceUNIX等。IBM、Microsoft、开放软件基金会(OSF)和UNIX系统实验室(USU)等新操作系统都采用了这一研究成果的优点，它能够提供一些必要的服务:其中这些必要的服务包括任务，线程，交互进程通信(IPC,Inter-ProcessCommunication)以及内存管理等等。所有服务(包括设备驱动)在用户模式下运行，而处理这些服务同处理其他的任何一个程序一样。因为每个服务只是在自己的地址空间运行。所以这些服务之间彼此之何都受到了保护。
微内核的好处主要有:
- 提高了可扩展性
- 增强了可靠性
- 增强了可移植性
- 提供了对分布式系统的支持
- 融入了面向对象技术
- 线程/进程空间是什么?
答:线程运行所需要的内存空间，比如线程程序的存储空间，数据空间，运行空间等。逻辑地址和物理地址之间的切换，是由CPU的内存管理单元MUJ完成。Limur内维护每个进程的逻辑地址到物理地址的对照表。当用户空间进程切换时，内核会更新对照着。用户空间也跟随变。每个进程的用户空间都是相互独立的，把同一个程序同时运行10次，会看到10个适程使用的线性地址一模一样但物理内存不一一样。
- 现代操作系统为什么要引入线程?
由于进程是资源的拥有者，所以在创建、撒销、切换操作中需要较大的时空开值，限时了并发程度的进一步提高。为减少进程切换的开销，把进程作为资源分配单位和调度单位这两个属性分开处理，即进程还是作为资源分配的基本单位，但是不作为调度的基本位《服少调度或切换)，把调度执行与切换的责任交给“线程”。这样做的好处不但可以提高案统的并发度，还能适应新的对称多处理机(SMP)环境的运行，充分发挥其性能。
- 什么是生产者-消费者问题?什么是读者-写者问题?什么是哲学家进餐问题
- 生产者-消费者问题:生产者一消费者问题是最著名的进程同步问题。它描述了一组生产者向一如消费者提供消息，它们共享一个有界缓冲池，生产者向其中投放消息，消费者从中取得消息。生产者-消费者问题是许多相互合作进程的一种抽象。例如，在输入时，输入进程时生产者，计算进程时消费者;在输出时，计算进程时生产者，打印进程是消费者
- 读者-写者问题:一个数据文件或记录(统称数据对象)，可被多个进程共享，其中有些进程要求读，而另一些进程要求写或修改。我们把只要求读的进程称为“读者”，其他进程称为“写者”。允许许多个读者同时读一个共享对象，但绝不允许一个写者和其他进程(读者或写者)同时访问共享对象，读者写者问题，是指保证一个写者必须与其他进程互斥地访问共享对象的同步问题。
- 哲学家进餐问题:这是一种典型的同步问题，它是由Dijketra提出并解决的，该问题的描述如下:有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们公司一张圆来，周国放有五张椅子，每人坐一张，在国来上有五个碗和五只筷子，第一个哲学家思考时，他不与同事交谈，机体时便试图取用其左、右最靠近他的筷子，但他可能一点超字不到，只有在他拿到两文换子时方能进餐。餐毕，放下筷子又继埃思考。甘学家进星问题啊以用来解释死锁和资源耗尽的问题。
- 什么是内存?
答:内存是计算机中重要的部件之一，它是与CPU进行沟通的桥梁。计算机中所有程序的运行都是在内存中进行的，因此内存的性能对计算机的影响非常大。内存(Memory)也被称为内存储器，其作用是用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。只要计算机在运行中，CPU就会把需要运算的数据调到内存中进行运算，当运算完成后CPU再将结果传送出来，内存的运行也决定了计算机的稳定运行。内存是由内存芯片、电路板、金手指等部分组成的。
- 什么是数据缓存Cache?
答:高速缓冲存储器(Cache)其原始意义是指存取速度比一般随机存取记忆体(RAM)来得快的一种RAM，一般而言它不像系统主记忆体那样使用DRAM技术，而使用昂贵但较快速的SRAM技术，也有快取记忆体的名称。高速缓冲存储器是存在于主存与CPU之间的一级存储器，由静态存储芯片(SRAM)组成，容量比较小但速度比主存高得多，接近于CPU的速度。主要由三大部分组成:Cache存储体:存放由主存调入的指令与数据块。地址转换部件:建立目录表以实现主存地址到緩存地址的转换。替换部件:在缓存已满时按一定策略进行数据块替换，并修改地址转换部件。
- call和return具体做了哪些工作?
答:它们的作用分别为:
call:参数压栈、返回地址压栈、保护现场.
return:返回地址、恢复现场
- 什么是RAID?
答:RAID是英文RedundantArrayofIndependentDisks的缩写,翻译成中文意思是“独立磁盘冗余阵列”，有时也简称磁盘阵列(DiskArray)。简单的说，RAID是一种把多块独立的硬盘(物理硬盘)按不同的方式组合起来形成一个硬盘组(逻辑硬盘)，从而提供比单个硬盘更高的存储性能和提供数据备份技术。组成磁盘阵列的不同方式成为RAID级别(RAIDLevels)。数据备份的功能是在用户数据一旦发生损坏后，利用备份信息可以使损坏数据得以恢复，从而保障了用户数据的安全性。在用户看起来，组成的磁盘组就像是一个硬盘，用户可以对它进行分区，格式化等等。总之，对磁盘阵列的操作与单个硬盘一模一样。不同的是，磁盘阵列的存储速度要比单个硬盘高很多，而且可以提供自动数据备份。
- 什么是SPOOLing技术?
答:SPOOLing是SimultaneousPeripheralOperation0n-Line(即外部设备联机并行操作)的缩写，它是关于慢速宇符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。SPOLing系统既不同于脱机方式，也不同于直接藕合方式,SPOOLing技术实际上是一种.外围设备同时联机操作技术，又称为排队转储技术。它在输入和输出之间增加了“输入井”和“输出井”的排队转储环节，以消除用户的“联机”等待时间。在系统输入模块收到作业输入请求信号后，输入管理模块中的读过程负责将信息从输入装置中读入输入井缓冲区。当缓冲区满时，由写过程将信息从缓冲区写到外存的输入井中，读过程和写过程反复循环，直到一个作业输入完毕。当读过程读到一个硬件结束标志之后，系统再次驱动写过程把最后一批信息写入外存输入井并调用中断处理程序结束该次输入。然后，系统为该作业建立作业控制块，从而使输入井中的作业进入作业等待队列，等待作业调度程序选中后进入内存运行。系统在管理输入井过程中可以“不断”读入输入的作业，直到输入结束或输入井满而暂停。若系统的某台台行式打印机采用了虚拟设备技术，那么若有进程要求对它打印输出时,SPO0Ling系统并不是将这台打印机直接分配给进程，而是在共享设备(磁盘)上的输出,SPOOLing存储区中为其分配--块存储空间，进程的输出数据以文件形式表示的。各进程的数据输出文件形成了一个输出队列，由输出P0OLing系统控制这台打印机进程，依次将队列中的输出文件实际打印输出。在SPOOLing系统中，实际上并没有为任何进程分配，而只是在输入井和输出井中，为进程分配一存储区和建立一章1/0请求表。这样，便把独占设备改造为共享设备。
将一台独享打印机改造为可供多个用户共享的打印机,是应用SPOOLing技术的典型实例。具体做法是:系统对于用户的打印输出，但并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送入其中;然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。若打印机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。
- 操作系统中用到的数据结构的知识有:
LRU算法:堆栈;
进程调度:队列;
空闲内存:链表;
Fat文件系统:树;
磁盘空余:链;
银行家算法中的数据结构:
1.Available:含有m个元素的二维数组
2.Max:n*m的矩阵
3.Allocation:n*m的矩阵
4.Need:n*m的矩阵
- 计算机和计算器的区别.
答:它们的区别分别有:计算器:具有简单计算功能，有些具有简单存储功能，不能自动工作，而计算机可以通过编程实现程序自动运行。价位便宜。计算机:高速计算的电子计算机，可进行数值计算，逻辑计算，还具有存储记忆功能。自动化程度高于计算器。实际上二者还有另一个本质性的区别。计算器使用的是固化的处理程序，只能完成特定的计算任务;而计算机借助操作系统平台和各类应用软硬件，可以无限扩展其应用领域。也
就是说，是否具有扩展性是二者的本质区别。
- 多级存储器结构主要包含哪两个层次?每个层次分别主要解决什么问题?
存储器结构主要包含:“Cache-主 存”、
“主存-辅存”两个层次。
①“Cache-主 存”层次:增加了一级速度快、但容量较小的高速缓冲存储器，借助于辅
勹硬件，弥补了主存速度不足，缓解了主存和CPU之间速度不匹配的问题;
②“主存辅存”层次:在主存外面增加了一个容量更大，但速度低的存储器，依靠辅助
门软硬件，弥补主存容量不足，实现了虚拟存储器。
- 异步串行通信不需要共同的时钟总线，怎么实现数据同步的? (即两个不同步 的设
备怎么工作? )
异步传输过程没有统一的时标，为实现数据同步，采用的是“应答”机制。即主模块发
出数据后，等待从模块的应答信号，从模块收到数据后，立即向主模块发出应答信号,以这.
种方式实现数据的同步。根据应答的具体方式，异步传输可以分为不互锁、半互锁、全互锁
三种。
- 数据结构
- 什么是哈希冲突？处理冲突的方法？
当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1!=K2，但f(K1)=f(K2),这种现象称为hash冲突，实际中冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。
处理冲突的方法：
- 开放定址法（再散列法）
- 线性探测法
- 平方探测法
- 再散列法
- 伪随机序列法
- 拉链法
- 建立公共溢出区
- 将哈希表分为基本表和溢出表，凡是冲突的都填入溢出表
- 再哈希法
- 不能做switch()参数的是？
- C./C++支持byte,char,short,int,long,bool,int与枚举，不支持float,double，stirng
- 为什么说快速排序是性能最好的算法
从表中看，堆排序应该是最好的排序算法。实际在堆排序（小根堆为例）的时候，每次总是将最小的元素移除，然后将最后的元素放到堆顶，再让其进行自己调整，这样一来，有很多的比较是被浪费的。堆排序的过程中，需要有效的随机存取。比较父节点和字节点的值大小的时候，虽然计算下标会很快完成，但是在大规模的数据中对数组指针寻址也需要一定的时间。而快速排序只需要将数组指针移动到相邻的区域即可。在堆排序中，会大量的随机存取数据；而在快速排序中，只会大量的顺序存取数据。随着数据规模的扩大，这方面的差距会明显增大。在这方面的时间开销来说，快速排序只会线性增长，而堆排序增加幅度很大，会远远大于线性。
在快速排序中，每次数据移动都意味着该数据距离它正确的位置越来越近，而在堆排序中，类似将堆尾部的数据移到堆顶这样的操作只会使相应的数据远离它正确的位置，后续必然有一些操作再将其移动，即“做了好多无用功”。
- 面向对象三大特性有哪些？如何理解
封装：也就是把客观事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏。
继承：它可以使用现有类的所有功能，并在无需重新编写原来的类的情况下对这些功能进行扩展。
实现方式有三类
- 实现继承：使用基类的属性和方法而无需额外编码的能力；
- 接口继承：指仅使用属性和方法的名称、但是子类必须提供实现的能力；
- 可视继承：指子窗体（类）使用基窗体（类）的外观和实现代码的能力。
多态：允许你将父对象设置成为和一个或更多的他的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。简单的说，就是一句话：允许将子类类型的指针赋值给父类类型的指针。
实现方式有两种：
- 覆盖：是指子类重新定义父类的虚函数的做法。
- 重载：是指允许存在多个同名的函数，而这些函数的参数表不同
- 图的相关概念
- 图：由结点的有穷集合V和边的集合E组成。
- 类别：有向图和无向图。
- 顶点的度：出度和入度。
- 有向完全图和无向完全图：若有向图有n个顶点，则最多有n(-1)
- 条边，则称为有向完全图；若无向图有n个顶点，则最多有n(-1)/2
- 条边，则称为无向完全图。
- 路径：相邻顶点序偶所构成的序列。
- 简单路径：序列中的顶点和路径不重复出现的路径。
- 关键路径：事件结点图从源点到终点最长的路径
- 回路：路径中第一个顶点和最后一个顶点相同的路径。
- 连通：无向图中，如果Vi到Vj有路径，则称这两个顶点连通。
- 如果图中任意两个顶点之间都连通，则称改图为连通图。
- 有向图中，如果Vi到Vj有路径，则称这两个顶点连通。如果图中每一对顶点Vi和Vj，从Vi到Vj和Vj到Vi都有路径，则称改图为强连通图。
- 那么现在如何能在不引入多余变量t的条件下就能够交换a,b的值呢？
- 栈实现，入栈后再弹出栈来交换值
- 位运算inta=10.b=12;a=a^b;b=a^b;a=a^b;
- 算术运算inta=10,b=12;a=b-a;b=b-a;a=b+a;指针地址操作。将二者地址交换，同样也是算术运算
- 单链表中，增加一个附加头节点的目的是为了？
方便运算的实现，增加附加信息，标志单链表存在
- 什么是二叉排序树？以及它的原理，算法。（二叉排序树的查找过程）
- 二叉排序树又称二叉查找树，它或者是一颗空树，或者满足一下性质的二叉树：
- ①若左子树不空，则左子树上所有结点的值均小于根节点的值；
- ②若右子树不空，则右子树上所有结点的值均大于根节点的值；
- ③左右子树也分别是二叉排序树。
- 原理步骤：
- 若根结点的关键字值等于查找的关键字，成功。
- 否则，若小于根结点的关键字值，递归查左子树。
- 若大于根结点的关键字值，递归查右子树。
- 若子树为空，查找不成功。
- 含有N个节点的二叉树共有多少种？
- 二叉树和树的主要不同有哪些不同？
a) 树中结点的度多少没有限制，而二叉树结点度最大为2；
b) 二叉树节点有左右之分，而树无；
- 什么是哈夫曼树？
定义：
i. 给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Hufmantre)。
构造方法：
i. 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：
(1)将w1、w2、…，wn看成是有n棵树的森林(每棵树仅有一个结点)；
(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树
特点：
①权值越大的结点，距离根节点越近；
②树中没有度为一的结点。
应用：哈夫曼编码，减少编码的长度。哈夫曼编码就是长度最短的前缀编码
- 希望较快的搜索，又便于线性表动态变化的搜素方法是？
索引顺序查找：该方法索引块内部的数据可以无序，故在块内方便进行数据的删除或增加
- 深度优先搜索遍历和广度优先搜索遍历的过程
深度优先搜索遍历
基本思想：首先访问出发点V，并将其标记为已访问；然后选取与V邻接的未被访问的邻接顶点W，访问W；再选取与W邻接的未被访问的顶点访问，以此类推。当一个顶点所有的邻接顶点都被访问过时，则依次退回最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些顶点中去一个顶点进行上述的过程，直至图中所有顶点都被访问过为止。
广度优先搜索遍历
基本思想：首先访问起始顶点V，然后选取与V邻接的全部顶点w1，w2，….，wn进行访问，再一次访问与w1，w2，…，wn邻接的全部顶点（不包括已访问过的顶点），以此类推，直至所有顶点都被访问过为止。
- 图的深度遍历是否唯一，同问广度遍历
邻接矩阵唯一，邻接链表不唯一。也就是说结点有顺序且按序查找就唯一
- 什么是堆？有什么作用？
堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足：
任何一个非叶节点的值都不大于（或不小于）其左右子树的结点的值。若父亲大孩子小，则为大顶堆，若父亲肖孩子大，则为小顶堆。
作用：应用于堆排序
- 如何实现循环队列？有何好处？
如何实现：把数组弄成一个环，让rea和front指针沿着环走，这样就可以产生循环队列。
好处：循环队列是顺序队列的改进，在顺序队列中，在元素进队的时候，rea要向后移动，元素出队的时候，front也要向后移动，这样经过一系列的出队和入队操作之后，两个指针最后会达到数组的末端，此时虽然队中已经没有元素了，但是还是不能让元素入队，即出现了“假溢出”的现象。循环队列就能避免出现这个现象。
- 堆和栈的区别？请简要说明。
栈区（stack）—由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
堆区（heap）—般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
全局区（静态区）（staic）—全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
文字常量区—常量字符串就是放在这里的。程序结束后由系统释放。
程序代码区—存放函数体的二进制代码。
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。
- Java与c++区别
1、 JAVA的应用在高层，C++在中间件和底层
2、 JAVA离不开业务逻辑，而C++可以离开业务为JAVA们服务
3、 java语言给开发人员提供了更为简洁的语法；取消了指针带来更高的代码质量；完全面向对象，独特的运行机制是其具有天然的可移植性。
4、 java 是运行在JVM上的，之所以说它的可移植性强，是因为jvm可以安装到任何的系统
5、 c++不是不能在其他系统运行，而是c++在不同的系统上运行，需要不同的编码（这一点不如java，只编写一次代码，到处运行）。java程序一般都是生成字节码，在JVM里面运行得到结果。
6、 java 在web 应用上具有c++ 无可比拟的优势
7、 java在桌面程序上不如c++实用，C++可以直接编译成exe文件，指针是c++的优势，可以直接对内存的操作，但同时具有危险性 。（操作内存的确是一项非常危险的事情，一旦指针指向的位置发生错误，或者误删除了内存中某个地址单元存放的重要数据，后果是可想而知的）。
8、 垃圾回收机制的区别。c++用析构函数回收垃圾，java自动回收（GC算法）,写C和C++程序时一定要注意内存的申请和释放。
9、 java 丰富的插件是java 发展如此迅速的原因
10、 java 很大的沿袭了c++的一些实用结构
11、 对于底层程序的编程以及控制方面的编程，c++很灵活，因为有句柄的存在。
- 有哪些常用的字符串匹配算法，它们的算法思想是什么
1.暴力解法（brute force）
2.KMP
3.Sunday
只不过Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。
如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1
- 查找方法总结
- 动态查找表：若在查找的同时还对表做修改运算（动态地插入或删除），则相应的表称之为动态查找表。适合动态查找的方法有：二叉排序查找，二叉平衡树，B+树等改进后的树
- 静态查找表；反之称之为静态查找表。适合静态查找方法有：顺序查找，拆装查找，散列查找等。
- 网络
- 什么是计算机网络
以能够相互共享的方式互联起来的自治计算机系统的集合。
- 计算机网络的组成
1）从组成部分上看：硬件、软件、协议
2）从工作方式上看：边缘部分、核心部分
3）从功能组成上看：通信子网、资源子网
- 计算机网络的功能
1）数据通信
2）资源共享
3）分布式处理
4）提高可靠性
5）负载均衡
- 计算机网络分层的基本原则
1）各层之间相互独立，每层只实现一种相对独立的功能
2）每层之间界面自然清晰，易于理解，相互交流尽可能少
3）各层功能的精确定义独立于具体的实现方法，可以采用最合适的技术来实现
4）保持下层对上层的独立性，上层单向使用下层提供的服务
5）整个分层结构应该能促进标准化工作
- 计算机网络提供的服务的三种分类
1）面向连接服务和无连接服务
2）可靠服务和不可靠服务
3）有应答服务和无应答服务
- ISO/OSI参考模型
全称：开放系统互连参考模型低三层统称为通信子网，它是为了联网而附加的通信设备，完成数据的传输功能；高三层统称为资源子网，它相当于计算机系统，完成数据的处理等功能。传输层承上启下。
1）物理层
任务：在物理媒体上为数据端设备透明地传输原始比特流，传输单位是比特。
功能：定义接口特性、定义传输模式、定义传输速率、比特同步、比特编码。
协议：Rj45、802.3
2）数据链路层
任务：将网络层传来的IP数据包组装成帧，传输单位是帧。
功能：成帧、差错控制、流量控制、访问控制。
协议：SDLC、HDLC、PPP、STP
3）网络层
任务：把分组从源端传到目的端，为分组交换网上的不同主机提供通信服务，传输单位是数据报。
功能：路由选择、流量控制、差错控制、拥塞控制、异构网络互联
协议：IP、IPX、ICMP、IGMP、ARP、RARP、OSPF
4）传输层
任务：负责主机中两个进程的通信，即端到端的通信，传输单位是报文段（TCP）或用户数据报（UDP）。
功能：可靠/不可靠传输、差错控制、流量控制、复用/分用。
协议：TCP、UDP
复用：多个应用层进程可同时使用下面传输层的服务。
分用：传输层把收到的信息分别交付给上面应用层中相应的进程。
5）会话层
任务：向表示层实体/用户进程提供建立连接，并在连接上有序地传输数据。
功能：建立、管理、终止会话进程；数据同步。
协议：ADSP、ASP
6）表示层
任务：处理在两个通信系统中交换信息的表示方式。
功能：数据格式转换、数据加密解密、数据压缩和恢复
7）应用层
任务：用户与网络的界面，为特定类型的网络应用提供访问OSI环境的手段。协议：FTP、SMTP、HTTP
- TCP/IP参考模型与ISO/OSI参考模型的区别
TCP/IP分层：应用层、传输层、网际层、网络接口层
区别：
1）OSI定义三个概念：服务、协议和接口。TCP在这三个概念上没有明确区分。
2）OSI先出现，参考模型先于协议发明，不偏向特定协议，通用性良好。TCP/IP先出现协议，模型是对已有协议的描述。
3）TCP/IP设计之初就考虑到异构网互连问题，将IP作为重要层次。
4）OSI在网络层支持无连接和面向连接的通信，但在传输层仅有面向连接的通信。而TCP/IP认为可靠性是端到端的问题，因此它在网际层仅有无连接的通信模式，但传输层支持无连接和面向连接两种模式。五层参考模型：应用层、传输层、网络层、数据链路层、物理层
- 交换技术
交换技术是指各台主机之间、各通信设备之间或主机与通信设备之间为交换信息所采用的数据格式和交换装置的方式。
1）电路交换网络
在源节点和目的节点之间建立一条专用的通路用于传送数据，包括建立连接、传输数据和断开连接三个阶段。最典型的电路交换网络是传统电话网络。
2）报文交换网络
也称存储转发网络，整个报文先传送到相邻节点，全部存储后查找转发表，转发到下一节点。
3）分组交换网络
将单个分组（报文分组的一部分）传送到相邻节点，存储后查找转发表，转发到下一节点。
- 通信基础知识
数字信号：取值仅允许为有限的几个离散数值的数据（或信号）
模拟信号：连续变化的数据（或信号）
协议：FTP、SMTP、HTTP
- 数字调制的主要形式有哪些？
主要有幅度调制或幅移键控ASK简称“调幅”，频率键移FSK简称“调频”，相位键移PSK简称“调相”和多路载波等几种。幅度调制用改变信号幅度的方法来表示数字信号0和1。频率键移调制用一种频率信号表示数字0，另一种频率信号表示数字
- 通信基础知识
数字信号：取值仅允许为有限的几个离散数值的数据（或信号）
模拟信号：连续变化的数据（或信号）建立连接→数据传输→连接释放
特点：独占资源，用户始终占用端到端的固定传输带宽。适用于远程批处理信息传输或系统间实时性要求高的大量数据传输的情况。
2）报文交换
采用存储转发方式
3）分组交换
将报文分组，采用存储转发方式，限制所传输的数据单位的长度。
方式的选择：
传送数据量大，且传送时间远大于呼叫时，选择电路交换；电路交换传输时延最小。
当端到端的通路有很多段的链路组成，采用分组交换。
从信道利用率上看，报文交换和分组交换优于电路交换，分组交换比报文交换时延小，尤其适用于计算机之间突发式
的数据通路。
- 数据报与虚电路
数据报：面向无连接。在交换节点的处理等候时延较大，适用于突发性通信，不适合长报文，会话式通信；对故障适应性较强；分组要携带源地址和目的地址，到达节点的分组可能乱序，重复和丢失。
虚电路：面向连接。分组不需要携带源地址和目的地址，包含虚电路号，不会乱序、重复或丢失。节点只进行差错检测，不需要进行路由选择；对故障很敏感。
- 物理层设备
1）中继器
将信号整形并放大在转发出去，消除信号的失真和衰减问题，具有5-4-3规则。工作在物理层，不能连接两个具有不同速率的局域网，连接的几个网段仍是一个局域网，两端的网段一定使用同一个协议。
2）集线器
实质上是一个多端口中继器，对信号进行放大后发到其他所有端口。Hub的每个端口连接的网络部分是同一个网络的不同网段，同时Hub也只能在半双工状态下工作，网络的吞吐率因而受到限制。集线器不能分割冲突域。
- 什么是基带信号？什么是宽带信号？
基带信号:将数字信号1或0直接用不同的电压来表示，然后送到电路上去传输。
宽带信号:将基带信号调制后形成的频分复用模拟信号。由于基带信号经过调制，其频谱移动到较高的频率处。由于每一路基带信号的频谱都被移动到不同的频段上，因此合在一起后
并不会互相干扰，这样可以在一条电缆中传送多路的数字信号，因而提高了线路的利用率。
- 简述猫的作用
猫是调制解调器的英文谐音，是一种计算机硬件，它能把计算机的数字信号翻译成
可沿普通电话线传送的脉冲信号，而这些脉冲信号又可被线路另一端的另一个调制解调器接收，并译成计算机可懂的语言。这一简单过程完成了两台计算机间的通信。
计算机内的信息是由“0”和“1”组成数字信号，而在电话线上传递的却只能是模拟电
信号。于是，当两台计算机要通过电话线进行数据传输时,就需要- -个设备负贵數模的转换。
这个数模转换器就是Modem。计算机在发送数据时，先由Modem把数字信号转换为相应的模拟信号，这个过程称为“调制”。经过调制的信号通过电话载波传送到另一台计算机之前,
也要经由接收方的Modem负责把模拟信号还原为计算机能识别的数字信号,这个过程称为“解调”。正是通过这样一个“调制”与“解调”的数模转换过程，从而实现了两台计算机之间的远程通讯。
- 频分复用如何避免各路信号间的干扰?
答:为了防止子信道间的干扰，相邻信道之间需要加入“保护频带”。即在给定信道的
.上下限处留出的未占用窄频带。其目的是确保信道间有足够隔离，防止相邻信道干扰。
- 数据链路层有哪两个子层?
答:逻辑链路控制LLC (Logical Link Control)子层:
LLC负责识别网络层协议，然后对它们进行封装。LLC报头告诉数据链路层一旦帧被
接收到时，应当对数据包做何处理。它的工作原理是这样的:
主机接收到帧并查看其LLC报头，以找到数据包的目的地,比如说，在网际层的IP协议。
LLC子层也可以提供流量控制并控制比特流的排序。
媒体接入控制MAC (Medium Access Control) 子层：
MAC子层的主要功能包括数据帧的封装/卸装，帧的寻址和识别，帧的接收与发送，链路
的管理，帧的差错控制等。MAC子层的存在屏蔽了不同物理链路种类的差异性;在MAC子层的诸多功能中，非常重要的一项功能是仲裁介质的使用权，即规定站点何时可以使用通信介质。与接入到传输媒体有关的内容都放在MAC子层，而LLC 子层则与传输媒体无关，不管采用何种协议的局域网对LLC子层来说都是透明的。
- 数据链路层的功能
1）为网络层提供服务：无确认的无连接服务、有确认的无连接服务、有确认的面向连接服务
2）链路管理：面向连接的服务。连接的建立、维持和释放过程
3）组帧：帧定界、帧同步与透明传输
4）流量控制：限制发送方的数据流量，使发送速率不超过接收方的接收能力。建立连接→数据传输→连接释放
特点：独占资源，用户始终占用端到端的固定传输带宽。适用于远程批处理信息传输或系统间实时性要求高的大量数据传输的情况。
2）报文交换
采用存储转发方式
3）分组交换
将报文分组，采用存储转发方式，限制所传输的数据单位的长度。
方式的选择：
传送数据量大，且传送时间远大于呼叫时，选择电路交换；电路交换传输时延最小。
当端到端的通路有很多段的链路组成，采用分组交换。
从信道利用率上看，报文交换和分组交换优于电路交换，分组交换比报文交换时延小，尤其适用于计算机之间突发式
的数据通路。
- 可靠传输
数据链路层通常使用确认和超时重传两种机制来保证可靠传输
- 信道划分介质访问控制
多路复用技术：当传输介质的带宽超过传输单个信号所需的带宽时，可以通过在一条介质上同时携带多个传输信号的方法来提高传输系统的利用率。实际上就是把一条广播信道，逻辑上分成几条用于两个节点之间通信的互不干扰的子信道，实际就是把广播信道转变为点对点信道。
分类：频分多路复用（FDM）、时分多路复用（TDM）、统计时分多路复用（STDM）、波分多路复用（WDM）、码分多路复用（CDM）
- 随机访问介质访问控制
所有用户可随机发送信息，发送信息时占全部带宽。胜利者通过争用获得信道，从而获得信息的发送权。
1）纯ALOHA协议
不监听信道，不按时间槽发送，随机重发
冲突如何检测：接收方检测出错，不予确认，发送方在一定时间内收不到确认就判断发生冲突
冲突如何解决：超时后等待一个随机时间再重传数据
2）时隙ALOHA协议
把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等待下一个时
间片开始时刻再发送。
3）CSMA协议（载波侦听多路访问）（Carrier Sense Multiple Access）
1-坚持CSMA：
思想：发送帧之前，先监听信道，信道空闲则直接传输，不必等待，信道忙则一直监听，直到空闲马上传输。如果有
冲突，则等待一个随机长的时间再监听，重复上述过程。
优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失。
缺点：若有两个或以上的站点有数据要发送，冲突就不可避免。
非坚持CSMA：
思想：发送帧之前，先监听信道，信道空闲则直接传输，不必等待，信道忙则等待一个随机时间之后再监听。
4）介质访问控制方法：CSMA/CD、令牌总线和令牌环
5）局域网分类：以太网、令牌环网、FDDI网、ATM网、无线局域网
6）MAC子层：介质访问控制子层，与接入传输媒体有关的内容都放在MAC子层，它向上屏蔽对物理层访问的各种差
异，提供对物理层的统一访问接口。主要功能包括组帧和拆卸帧、比特传输差错检测、透明传输。
7）LLC子层：逻辑链路控制子层，与传输媒体无关，负责识别网络层协议，然后对它们进行封装，为网络层提供服
务。他向网络层提供无确认无连接、面向连接、带确认无连接、高速传送4种不同的而连接服务类型。
- 以太网
以太网是基带总线型的局域网标准，使用CSMA/CD技术
特点：造价低廉、比令牌环网和ATM网便宜简单、满足网络速率要求。
以太网的两个标准：DIX Ethernet V2、IEEE802.3
以太网提供无连接不可靠的服务，只实现无差错接收，不实现可靠传输
10BASE-T：传送基带信号的双绞线以太网，T表示采用双绞线，传输速率是10Mb/s，采用曼彻斯特编码
- IEEE802.11无线局域网
介质访问控制方式：CSMA/CA
分类：有固定基础设施无线局域网、无固定基础设施无线局域网的自组织网络
- PPP协议
面向字节的点对点协议
1）PPP提供差错检测但不提供纠错功能，只保证无差错接收。它是不可靠的传输协议，因此也不使用序号和确认机
制。
2）它仅支持点对点的链路通信，不支持多点链路。
3）PPP只支持全双工链路
4）PPP两端可以运行不同的网络层协议，但仍然可使用同一个PPP协议进行通信
5）PPP是面向字节的，当信息段出现和标志字段一致的比特组合时，PPP有两种不同的处理方法：异步线路采用字节
填充法、同步线路采用比特填充。
组成：链路控制协议LCP、网络控制协议NCP、一个将IP数据报封装到串行链路的方法。
- HDLC协议
高级数据链路控制协议，是ISO制定的面向比特的数据链路层协议。该协议不依赖于任何一种字符编码集；数据报文可透明传输，用于实现透明传输的“0比特填充法”易于硬件实现；采用全双工通信，有较高的数据链路传输效率；所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏发或重发，传输可靠性高；传输控制功能与处理功能分离，具有较大的灵活性。
- 数据链路层设备
1）网桥
根据MAC帧的目的地址对帧进行转发和过滤。网桥工作在MAC子层。
网桥的优点：能过滤通信量；扩大了物理范围；可使用不同的物理层；可互连不同类型的局域网；提高了可靠性；性能得到改善。
网桥的缺点：增大了时延；MAC子层没有流量控制功能；需要帧格式转换；可能产生广播风暴。
分类：透明网桥、源路由网桥
2）局域网交换机
本质上是一个多端口网桥，工作在数据链路层
原理：它检测从以太端口来的数据帧的源和目的地的MAC地址，然后与系统内部的动态查找表进行比较，若数据帧的
MAC地址不在查找表中，则将该地址加入查找表，并将数据帧发送给相应的目的端口。
两种交换方式：直通式、存储转发式
直通式：查完目的地址就立刻转发，延迟小，可靠性低，无法支持具有不同速率的端口的交换。
存储转发式：将帧放入高速缓存，并检查是否正确，正确则转发，错误则丢弃。延迟大，可靠性高，可以支持具有不
同速率的端口的交换。
31、中继器、集线器、网桥和交换机的区别与联系
- 中继器工作在物理层，用来连接两个速率相同且数据链路层协议也相同的网段，其功能是消除数字信号在基带传输中
由于经过一长段电缆而造成的失真和衰减，使信号的波形和强度达到所需的要求；其原理是信号再生。集线器（Hub）也工作在物理层，相当于一个多接口的中继器，它可将多个节点连接成一个共享式的局域网，但任何时刻都只能有一个节点通过公共信道发送数据。网桥工作在数据链路层，可以互连不同的物理层、不同的MAC子层及不同速率的以太网。网桥具有过滤帧及存储转发帧的功能，可以隔离冲突域，但不能隔离广播域。交换机工作在数据链路层，相当于一个多端口的网桥，是交换机局域网的核心设备。它允许端口之间建立多个并发连接，实现多个节点之间的并发传输。因此，交换机的每个端口节点所占用的带宽不会因为端口节点数目的增加而减少，且整个交换机的总带宽会随着端口节点的增加而增加。交换机一般工作在全双工方式，有的局域网交换机采用存储转发方式进行转发，也有的交换机采用直通交换方式（即在收到帧的同时立即按帧的目的MAC地址决定该帧的转发端口，而不必先缓存再处理）。
- 网桥和交换机的区别
1）网桥的端口一般连接局域网，而交换机的端口一般直接与局域网的主机相连。
2）交换机允许多对计算机同时通信，而网桥仅允许每个网段上的计算机同时通信。
3）网桥采用存储转发进行转发，而以太网交换机还可以采用直通方式进行转发，且以太网交换机采用了专用的交换
结构芯片，转发速度比网桥快。
- IPv4分组的格式
IP首部：
1）IP的版本，占4位，目前广泛为4；
2）首部长度，占4位，单位4B，最大为60B，最常用20B；
3）总长度，占16位，单位1B
4）标识，占16位，当数据报长度大于MTU时，要分片，同一数据报的分片使用同一标识。
5）标志，占3位，最低位为MF，MF=1表示后面还有分片，MF=0表示最后一个分片。中间一位是DF，DF=0表示允许分
片。
6）片偏移，占13位，单位8B，每个分片的长度一定是8B的整数倍。指出某片在原分组中的相对位置。
7）生存时间，ttl，占8位，数据报在网络中可通过的路由器数的最大值。
8）协议，占8位，指分组的的数据应该交给哪个传输层协议。6表示tcp，17表示udp
9）首部校验和，占16位，IP数据报的首部校验和只检验分组的首部，而不检验数据部分。
10）源地址字段，占4B，标识发送方的IP地址
11）目的地址字段，占4B，标识接收方的IP地址
得到下一跳路由器的IP地址后并不是直接将该地址填入待发送的数据报，而是将该IP地址转换成MAC地址，将其放入
到MAC帧首部中，然后根据这个MAC地址找到下一跳路由器。
在不同网络中传送时，MAC帧中的源地址和目的地址要发生变化，但是网桥在转发帧的时，不改变帧的源地址
- IPv4地址
1）NAT网络地址转换
通过将专用网络地址转换为公用地址，从而对外隐藏内部管理的IP地址。
在因特网中的所有路由器，对目的地址是私有地址的数据包一律不进行转发。
普通路由器在转发IP数据报时，不改变源IP地址和目的IP地址，而NAT路由器在转发IP数据报时，一定要更换IP地址。
普通路由器仅工作在网络层，而NAT路由器转发数据报时需要查看和转换传输层的端口号。
2）子网划分
分类两级IP地址的缺点：IP地址空间的利用率有时很低；两级IP地址不够灵活；给每个物理网络分配一个网络号会使
路由表变得太大而使网络性能变坏。
划分子网只是把IP地址的主机号这部分进行再划分，而不改变IP地址原来的网络号。
子网中主机号全0的地址为子网的网络号，主机号全1的地址为子网的广播地址。
3）子网掩码
为了告诉主机或路由器对一个A,B,C类网络进行了子网划分，使用子网掩码来表达对原网络中主机号的借位。
子网掩码格式：网络号和子网号全1，主机号全0。
子网掩码与IP地址逐位相与，就得到子网网络地址。
路由表内容：目的网络地址，目的网络的子网掩码，下一跳地址
4）无分类域间路由选择CIDR
特点：消除了传统A,B,C类地址及子网划分的概念，从而可以更有效地分配IPv4的地址空间；将网络前缀都想同的连续
IP地址组成“CIDR地址块”。一个CIDR地址块可以表示很多地址，称为路由聚合，或称构成超网。方式为将网络前缀缩
短。
CIDR查找路由表常用的数据结构是二叉线索
5）地址解析协议ARP
无论网络层使用什么协议，在实际网络的链路上传送数据帧时，最终必须使用MAC地址。ARP就是用来完成主机或路
由器IP地址到MAC地址的映射。
ARP请求分组是广播发送，ARP响应分组是普通的单播。ARP请求分组的帧的mac地址为FFFFFFFFFFFF
6）动态主机配置协议DHCP
DHCP是应用层协议，使用客户.服务器方式，客户端和服务器通过广播方式进行交互，基于UDP。DHCP提供即插即用
的联网机制。
步骤：主机广播DHCP发现报文→DHCP服务器广播DHCP提供报文→主机广播DHCP请求报文→DHCP服务器广播DHCP
确认报文
7）网际控制报文协议ICMP
为了更加有效地转发IP数据报和提高交付成功的机会，网际控制报文协议ICMP支持主机或路由器报告差错和异常情
况。ICMP报文作为IP层数据报的数据，加上数据报的首部，组成IP数据报发送出去。ICMP是IP层协议。
ICMP报文分类：ICMP差错报告报文、ICMP询问报文
ICMP差错报告报文：终点不可达、源点抑制、时间超过、参数问题、改变路由（重定向）
ICMP询问报文：回送请求和回答报文、时间戳请求和回答报文、掩码地址请求和回答报文、路由器询问和通告报文
常见应用：分组网间接探测PING（用来测试两个主机之间的连通性，使用ICMP回送请求和回答报文）和
Traceroute（可以用来跟踪分组经过的路由，使用ICMP时间超过报文）
- IPv6
解决IP地址耗尽问题的措施：
1）采用无类别编址CIDR，使IP地址的分配更加合理；
2）采用网络地址转换（NAT）方法以节省全球IP地址；
3）采用具有更大地址空间的新版本的IPv6。
IPv6和IPv4的区别：
1）将地址从32位扩展到128位，具有更大的地址空间。
2）IPv6将IPv4的校验和字段彻底清除，以减少每跳的处理时间。
3）IPv6将IPv4的可选字段移出首部，变成了扩展首部，成为灵活的首部格式，路由器通常不对扩展首部进行检查，大
大提高了路由器的处理效率。
4）IPv6支持即插即用（即自动配置），不需要DHCP协议。
5）IPv6的首部长度必须是8B的整数倍，IPv4的首部长度是4B的整数倍。
6）IPv6只能在主机处分片，IPv4可以在主机处和路由器分片。
7）ICMPv6：附加报文类型“分组过大”
8）IPv6支持资源的预分配，支持实时影像等要求保证一定的带宽和时延的应用。
9）IPv6取消了协议字段，改成下一个首部字段。
10）IPv6取消了总长度字段，改用有效载荷长度字段。
11）IPv6取消了服务类型字段。
IPv6基本地址类型：单播、多播、任播
IPv6系统必须能够接收和转发IPv4分组，并且能够为IPv4分组选择路由
IPv4向IPv6过渡的方式：双协议栈、隧道技术
- 路由器的功能
1）路由选择：按照复杂的分布式算法，根据从各相邻路由器所得到的关于整个网络拓扑的变化情况，动态地改变所
选择的路由。
2）分组转发：指路由器根据转发表将用户的IP数据报从合适的端口转发出去。路由表是根据路由选择算法得出的，
而转发表是从路由表得出的。转发表的结构应当使查找过程最优化，路由表则需要对网络拓扑变化的计算最优化。
- 动态路由算法
1）距离-向量路由算法
所有节点都定期地将他们整个路由选择表传送给所有与之直接相邻的节点。包含：每条路径的目的地和路径的代价。
最常见的距离-向量路由算法：RIP算法，它采用“跳数”作为距离的度量。
2）链路状态路由算法
链路状态路由算法要求每个参与该算法的节点都具有完全相同的网络拓扑信息，他们执行下述两项任务。第一，主动
测试所有邻接节点的状态。两个共享一条链接的节点是相邻节点，他们连接到同一条链路，或者连接到同一广播型物
理网络。第二，定期将链路状态传播给所有其他节点（或称路由节点）。
典型的链路状态路由算法：OSPF算法
三个特征：
a. 向本自治系统中所有路由器发送信息，使用的是泛洪法。
b. 发送的信息是与路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。
c. 只有当链路状态发生变化时，路由器才向所有路由器发送此消息。
3）距离-向量路由算法与链路状态路由算法的比较
在距离-向量路由算法中，每个结点仅与它的直接邻居交谈，它为它的邻居提供从自己到网络中所有其他结点的最低
费用估计。在链路状态路由算法中，每个结点通过广播的方式与其他结点交谈，但它仅告诉它们与它直接相连的链路
费用。相较之下，距离-向量路由算法有可能遇到路由环路等问题。
- 路由协议
一个自治系统内部所使用的路由选择协议称为内部网关协议IGP，也称域内路由选择，具体协议有RIP和OSPF等。
自治系统之间使用的路由选择协议称为外部网关协议EGP，也称域间路由选择，具体协议有BGP。
路由信息协议RIP
一种分布式的基于距离向量的路由选择协议，其最大的优点是简单。RIP是应用层协议，它使用UDP传送数据（端口
520）。
特点：
仅和相邻路由器交换信息；
路由器交换的信息是当前路由器所知道的全部信息，即自己的路由表。
按固定的时间间隔交换路由信息。
优点：实现简单、开销小、收敛过程较快。
缺点：
RIP限制了网络的规模，它能使用的最大距离为15（16表示不可达）；
路由器之间交换的是路由器中的完整路由表，因此网络规模越大，开销也越大；
网络出现故障时，会出现慢收敛现象，即需要较长时间才能将此信息传送到所有路由器，俗称“坏消息传的慢”，使更
新过程的收敛时间长。
2）开放最短路径优先协议OSPF
使用分布式链路状态路由算法的典型代表。
OSPF与RIP相比有以下4点主要区别：
OSPF向本自治系统中的所有路由器发送信息，这里使用的方法是泛洪法。而RIP仅向自己相邻的路由器发送信息。
发送的信息是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。“链路状态”说明本路由
器和哪些路由器相邻及该链路的“度量”（或代价）。而在RIP中，发送的信息是本路由器所知道的全部信息，即整个
路由表。
只有当链路状态发生变化时，路由器才用泛洪法向所有路由器发送次信息，并且更新过程收敛得快，不会出现RIP“坏
消息传的慢”的问题。而在RIP中，不管网络拓扑是否发生变化，路由器之间都会定期交换路由表的信息。
OSPF是网络层协议，它不使用UDP或TCP，而是直接使用IP数据报传送（其IP数据报首部的协议字段是89）。而RIP是
传输层协议，它在传输层使用UDP。
OSPF的五种分组类型：问候分组、数据库描述分组、链路状态请求分组、链路状态更新分组、链路状态确认分组
3）边界网关协议BGP
不同自治系统的路由器之间交换路由信息的协议，采用路径向量路由选择协议。BGP属于应用层协议，它是基于TCP
的。
- NAT技术
将专用网络内部(或内部网络)使用的本地ip地址转换成有效的外部使用(或外部网
络)的全球ip地址，使得整个专用网只需要一-个全球ip地址就可以与英特网联通。此方
法可以解决ip地址紧缺的问题。
静态NAT: 将内部网络中的每个主机都永久映射成外部外部网络中的某个合法的地址。
动态地址:在外部网络中定义了一系列的合法地址，采用动态分配的方法映射到内部网络。
网络地址端口转换:把内部地址映射到外部网络的一个ip 地址的不同端口上。
- CIDR: Class less Inter-Doma in Routing
消除了传统的A类、B类和C类、地址以及划分子网的概念，因而可以更加有效地分
配IPv4的地址空间。这是一种为解决地址耗尽而提出的一种措施。
最长前缀匹配==最长匹配= =最佳匹配:网络前缀越长，其地址块就越小，因为路由就越
具体。
- 传输层的功能
1）传输层提供应用进程之间的逻辑通信，即端到端的通信。
2）复用和分用。
3）传输层还要对收到的报文进行差错检测（首部和数据部分）。网络层只检查IP数据报的首部，不检验数据部分是
否出错。
4）提供两种不同的传输协议，即面向连接的TCP和无连接的UDP。
38、传输层的寻址和端口
逻辑端口/软件端口：传输层的SAP（服务访问点），标识主机中的应用进程，端口号只有本地意义。
端口号分类：服务端使用的端口号、客户端使用的端口号。
服务器使用的端口号分类：熟知端口号、登记端口号。
套接字唯一标识了网络中的一个主机和它上面的一个进程，套接字Socket = （主机IP地址，端口号）。
- UDP协议
UDP只是做了传输协议能够做的最少工作，它仅在IP数据报服务上增加了两个最基本的服务：复用和分用以及差错检
测。UDP常应用于一次性传输较少数据的网络应用。UDP提供尽最大努力的交付，即不保证可靠交付。UDP是面向报
文的。
优点：
1）UDP无须建立连接，减少时延。
2）无连接状态。TCP需要在端系统中维护连接状态。
3）分组首部开销小。TCP有20B的首部开销，而UDP仅有8B的开销。
4）应用层能更好地控制要发送的数据和发送时间。
- TCP协议
TCP协议是在不可靠的IP层之上实现的可靠地数据传输协议，它主要解决传输的可靠、有序、无丢失和不重复问题。
特点：
1）TCP是面向连接的传输层协议。
2）每条TCP连接只能有两个断点，每条TCP连接只能是点对点的（一对一）。
3）TCP提供可靠地交付服务，保证传送的数据无差错、不丢失、不重复且有序。
4）TCP提供全双工通信，允许通信双方的应用进程在任何时候都能发送数据，为此TCP连接的两端都设有发送缓存和
接收缓存，用来临时存放双向通信的数据。发送缓存用来暂时存放一下数据：（1）发送应用程序传送给发送方TCP准
备发送的数据；（2）TCP已发送但尚未收到确认的数据。接收缓存用来暂时存放以下数据：（1）按序到达但尚未被
接收应用程序收取的数据；（2）不按序到达的数据。
5）TCP是面向字节流的。
TCP报文段既可以用来运载数据，又可以用来建立连接，释放连接和应答。
TCP连接的建立：三次握手
在TCP连接建立的过程中，要解决以下三个问题： 1）要使每一方都能够确知对方的存在。
2）要允许双方协商一些参数（如最大窗口值、是否使用窗口扩大选项、时间戳选项及服务质量等）。
3）能够对运输实体资源（如缓存大小、连接表中的项目等）进行分配。
三个阶段：连接建立→数据传送→连接释放
采用客户/服务器方式。
服务端的资源是在完成第二次握手时分配的，而客户端的资源是在完成第三次握手时分配的，这就使得服务器易于受
到SYN洪泛攻击。
TCP连接的释放：四次握手
TCP可靠传输：校验、序号、确认、重传
有两种事件会导致TCP对报文段进行重传：超时和冗余ACK。
TCP采用自适应短发，动态改变重传时间RTTS
TCP规定当发送方收到对同一报文段的3个冗余ACK时，就可以认为跟在这个被确认报文段之后的报文段已经丢失。
TCP流量控制：基于滑动窗口机制实现流量控制。
41、TCP拥塞控制
拥塞控制和流量控制的区别：拥塞控制是让网络能够承受现有的网络负荷，是一个全局性的过程，涉及所有的主机、
所有的路由器，以及与降低网络传输性能有关的所有因素。相反，流量控制往往是指点对点的通信量的控制，即接收
端控制发送端，它所要做的是抑制发送端发送数据的速率，以便使接收端来得及接收。
接收窗口：接收方根据自己接收缓存的大小，动态调整发送方的发送窗口大小。
拥塞窗口：发送方根据其对当前网络拥塞程度的估计而确定的窗口值。
拥塞控制算法：
1）慢开始算法
使用慢开始算法后，每经过一个传输轮次（即往返时延RTT），拥塞窗口就会加倍，即拥塞窗口的大小指数式增长。
这样慢开始一直把拥塞窗口增大到一个规定的慢开始门限阈值，然后改用拥塞拥塞算法。
2）拥塞避免
发送端的拥塞窗口每经过一个往返时延RTT就增加一个MSS的大小，而不是加倍，使拥塞窗口按线性规律缓慢增长
（即加法增大），而当出现一次超时（网络拥塞）时，令慢开始门限等于当前拥塞窗口的一半（即乘法减小）。
3）快重传
快重传技术使用了冗余ACK来检测丢包的发生。同样，冗余ACK也用于网络拥塞的检测（丢了包当然意味着网络可能
出线了拥塞）。快重传并非取消重传计时器，而是在某些情况下可更早地重传丢失的报文段。当发送方连续收到三个
重复的ACK报文时，直接重传对方尚未收到的报文段，而不必等待那个报文段设置的重传计时器超时。
4）快恢复
发送端收到连续三个冗余ACK（即重复确认）时，执行“乘法减小”算法，把慢开始门限设置为出现拥塞时发送方拥塞
窗口的一半。与慢开始（慢开始算法将拥塞窗口设置为1）的不同之处是，他把拥塞窗口的值设置为慢开始门限改变
后的数值，然后开始执行拥塞避免算法（“加法增大”）使拥塞窗口缓慢地线性增大。由于跳过了拥塞窗口从1起始的
慢开始过程，所以被称为快恢复。
总结：当发送方检测到超时的时候，就采用慢开始和拥塞避免，当发送方接收到了冗余ACK时，就采用快重传和快恢
复算法。
- 为何不采用“三次握手”释放连接，且发送最后一次握手报文后要等待2MSL的时
间呢？
原因有两个：
1）保证A发送的最后一个确认报文段能够到达B。如果A不等待2MSL，若A返回的最后确认报文段丢失，则B不能进入
正常关闭状态，而A此时已经关闭，也不可能再重传。
2）防止出现“已失效的连接请求报文段”
。A在发送最后一个确认报文段后，再经过2MSL可保证本连续持续的时间内所
产生的所有报文段从网络中消失。
- 为什么不采用“两次握手”建立连接呢？
这主要是为了防止两次握手情况下已失效的连接请求报文段突然又传送到服务器而产生错误。
应用层
- 网络应用模型
客户/服务器（C/S）模型：
1）服务器：提供计算服务的设备。特点：永久性提供服务，永久性访问地址/域名。
2）客户机：请求计算服务的主机。特点：与服务器通信，使用服务器提供的服务；间歇性接入网络；可能使用动态
IP地址；不与其他客户机直接通信。
3）应用：web，文件传输，远程登录，电子邮件。
P2P模型：
1）不存在永远在线的服务器；
2）每个主机既可以提供服务，也可以请求服务；
3）任意端系统/结点之间可以直接通信；
4）结点间歇性接入网络；
5）结点可能改变IP地址；
6）可扩展性好，网络健壮性强。
- DNS域名解析协议
DNS系统采用客户/服务器模型，其协议运行在UDP之上，使用53号端口。
从概念上可将DNS分为3部分：层次域名空间、域名服务器和解析器。
域名解析是指把域名映射称为IP地址或把IP地址映射为域名的过程。前者称为正向解析，后者称为反向解析。当客户
端需要域名解析时，通过本机的DNS客户端构造一个DNS请求报文，以UDP数据报方式发往本地域名服务器。域名解
析有两种方式：递归查询和递归与迭代相结合的查询。
- FTP文件传输协议
文件传输协议是因特网上使用得最广泛的文件传输协议。FTP提供交互式的访问，允许客户指明文件的类型与格式，
并允许文件具有存取权限。它屏蔽了个计算机系统的细节，因而适合于在异构网络中的任意计算机之间传送文件。
FTP提供以下功能： 1）提供不同种类主机系统（硬、软件体系等都可以不同）之间的文件传输能力。
2）以用户权限管理的方式提供用户对远程FTP服务器上的文件管理能力。
3）以匿名FTP的方式提供公用文件共享的能力。
FTP采用客户/服务器的工作方式，它使用TCP可靠地传输服务。一个FTP服务器进程可同时为对个客户进程提供服
务。FTP服务器进程由两大部分组成：一个主进程，负责接收新的请求；另外有若干从属进程，负责处理单个请求。
其工作步骤如下：
1）打开熟知端口21（控制端口），使客户进程能够连接上。
2）等待客户进程发连接请求。
3）启动从属进程来处理客户进程发来的请求。主进程与从属进程并发执行，从属进程对客户进程的请求处理完毕后
即终止。
4）回到等待状态，继续接受其他客户进程的请求。
FTP在工作时使用两个并行的TCP连接：一个控制连接（端口21），一个数据连接（端口号20）。
- 电子邮件
电子邮件系统组成：用户代理、邮件服务器、协议。
1）SMTP
简单邮件传输协议SMTP是一种提供可靠且有效的电子邮件传输的协议，它控制两个相互通信的SMTP进程交换信息。
由于SMTP使用客户/服务器方式，因此负责发送邮件的SMTP进程就是客户机，而负责接收邮件的SMTP进程就是SMTP
服务器。SMTP用的是TCP连接，端口号为25.SMTP通信有以下三个阶段：建立连接→邮件传送→连接释放。
2）POP3
邮局协议POP是一个非常简单但功能有限的邮件读取协议，现在使用的是它的第三个版本POP3。POP3采用的
是“拉”（pull)的通信方式，当用户读取邮件时，用户代理想邮件服务器发出请求，“拉”取用户邮箱中的邮件。POP也
使用客户/服务器的工作方式，在传输层使用TCP，端口号为110.
- 万维网WWW
WWW是一个资料空间，在这个空间中：一样有用的事物称为一样“资源”，并由一个全域“统一资源定位符”（URL）标
识。这些资源通过超文本传输协议（HTTP）传送给使用者，而后者通过单击链接来获取资源。
万维网的内核部分组成：统一资源定位符URL、超文本传输协议HTTP、超文本标记语言HTML。
万维网以客户/服务器方式工作。
- HTTP超文本传输协议
HTTP定义了浏览器怎样向万维网服务器请求万维网文档，以及服务器怎样把文档传送给浏览器。从层次的角度看，
HTTP是面向事务的应用层协议，它规定了在浏览器和服务器之间的请求和响应的格式和规则，是万维网上能够可靠
地交换文件（包括文本、声音、图像等各种多媒体文件）的重要基础。
HTTP采用TCP作为运输层协议，但HTTP本身是无连接的，通信双方在交换HTTP报文前不需要先建立HTTP连接。
HTTP既可以使用非持久连接，也可以使用持久连接（HTTP/1.1支持）。
持久连接又可以分为非流水线和流水线两种方式。
HTTP是面向文本的，报文分类：请求报文、响应报文。
- 软工
- 软件开发模型
瀑布模型，V模型，喷泉模型，原型化模型，螺旋模型，统一过程，敏捷开发
- 面向对象7大原则
开闭，单一职责，接口隔离，依赖倒置，组合重用，里氏替换，迪米特
- 设计模式(23种)
创建型， 结构型， 行为型
工厂 适配器 观察者
抽象工厂 装饰 中介者
原型 ... ...
单例
...
- 什么是软件生命周期?
一个软件从定义、 开发、使用和维护，直到最终被废弃，要经历一个漫长的时期，通常
把它称为生命周期。概括地说，软件生命周期由软件定义、软件开发和运行维护(也称为软
件维护) 3个时期组成，每个时期又进一步划分成若干个阶段。软件定义时期的任务是:确定软件开发工程必须完成的总目标;确定工程的可行性;导出实现工程目标应该采用的策略及系统必须完成的功能;估计完成该项工程需要的资源和成本，并且制定工程进度表。这个时期的工作通常又称为系统分析，由系统分析员负责完成。
软件定义时期通常进一步划分为3个阶段，即问题定义、可行性研究和需求分析。
开发时期具体设计和实现在前一个时期定义的软件，它通常由下述4个阶段组成:总体设计，详细设计，编码和单元测试，综合测试。其中前两个阶段又称为系统设计，后两个阶段又称为系统实现。
维护时期的主要任务是使软件持久地满足用户的需要。具体地说，当软件在使用过程中发现错误时，应该加以改正:当环境改变时应该修改软件以适应新的环境;当用户有新要求时应该及时改进软件以满足用户的新需要。通常对维护时期不再进一一步划分阶段，但是每一次
维护活动本质.上都是一次压缩和简化了的定义和开发过程。
下面简要介绍软件生命周期每个阶段的基本任务。
(1) 问题定义
这个阶段必须回答的关键问题是:“要解决的问题是什么? ”
(2)可行性研究
这个阶段要回答的关键问题是:“对于 上一个阶段所确定的问题有行得通的解决方法吗?”
(3) 需求分析
这个阶段的任务仍然不是具体地解决问题，而是准确地确定“为了解决这个问题，目标系统必须做什么”，主要是确定目标系统必须具备哪些功能。
(4)总体设计
这个阶段必须回答的关键问题是:“概括地说， 应该怎样实现目标系统?”总体设计又称为概要设计。.
(5)详细设计
这个阶段的任务就是把解法具体化，也就是回答下面这个关键问题:“ 应该怎样具体地实现这个系统呢?”
(6)编码和单元测试
这个阶段的关键任务是写出正确的容易理解、容易维护的程序模块。
(7)综合测试
这个阶段的关键任务是通过各种类型的测试(及相应的调试)使软件达到预定的要求。
(8)软件维护
这个阶段的关键任务是，通过各种必要的维护活动使系统持久地满足用户的需要。
- 什么是软件过程?通常使用哪些模型来描述软件过程?
软件过程是为了获得高质量软件所需要完成的一系列任务的框架，它规定了完成各项任务的工作步骤。
软件过程定义了运用技术方法的顺序、应该交付的文档资料、为保证软件质量和协调软件变化必须采取的管理措施，以及标志完成了相应开发活动的里程碑。通常使用生命周期模型概括地描述软件过程。生命周期模型规定了软件过程包含的各个阶段，以及完成这些阶段的顺序。典型的生命周期模型如下所述。
瀑布模型
传统软件工程方法学的软件过程基本.上可以用瀑布模型来描述。
瀑布模型的主要优点是:
强迫开发人员采用规范的技术方法。
严格地规定了每个阶段必须提交的文档。
每个阶段结束前必须正式进行严格的技术审查和管理复审。
瀑布模型的主要缺点是:在可运行的软件产品交付给用户之前，用户只能通过文档来了解未来的产品是什么样的。开发人员和用户之间缺乏有效的沟通，很可能导致最终开发出的软件产品不能真正满足用户的需求。
快速原型模型
快速原型模型的主要优点是:
使用这种软件过程开发出的软件产品通常能满足用户的真实需求。
软件产品的开发过程基本上是线性顺序过程。
增量模型
使用增量模型开发软件时，把软件产品作为一系列增量构件来设计、编码、集成和测试。每个构件由若千个相互协作的模块构成，并且能够完成相对独立的功能。
螺旋模型
喷泉模型
- 什么叫耦合？什么叫内聚？
耦合：耦合是软件结构中各模块之间相互连接的一种度量，耦合强弱取决于模块间接口的复杂程度、进入或访问一个模块的点以及通过接口的数据。
内聚：内聚是从功能角度来度量模块内的联系，一个好的内聚模块应当恰好做一件事。它描述的是模块内的功能联系；
软件开发要高内聚，低耦合
- 什么是UML
UML是统一建模语言（UML是 Unified Modeling Language的缩写）是用来对软件密集系统进行可视化建模的一种语言。UML为面向对象开发系统的产品进行说明、可视化、和编制文档的一种标准语言。
统一建模语言 (UML)是非专利的第三代建模和规约语言。 UML是在开发阶段，说明，可视化，构建和书写一个面向对象软件密集系统的制品的开放方法。UML展现了一系列最佳工程实践，这些最佳实践在对大规模，复杂系统进行建模方面,特别是在软件架构层次已经被验证有效。
UML可以贯穿软件开发周期中的每一个阶段。被OMG采纳作为业界的标准。
UML最适于数据建模，业务建模，对象建模，组件建模。
UML作为一种模型语言，它使开发人员专注于建立产品的模型和结构，而不是选用什么程序语言和算法实现。当模型建立之后，模型可以被UML工具转化成指定的程序语言代码。
- 数据库
候选码：属性(组)能唯一度的标识一个元组，不含多余属性，可以有多个候选码
超键：属性(组)能唯一度的标识一个元组,可包含多余属性
主键：多个候选码中随便选一个
注：候选码是超键的子集，主键是候选码的子集
主属性：构成某一个候选关键字（候选码）的属性集中的一个属性
非主属性：不包含在任一候选码中的属性
第一范式：每列不可分割
第二范式：属性完全依赖于主键
第三范式：不依赖其他非主属性，即不存在非主属性对候选码的传递函数依赖
BCNF：不存在任何属性对任一候选码的传递函数依赖
- 数据库事务
ACID，指数据库事务正确执行的四个基本要素的缩写。包含：原子性（Atomicity）整个事务中的所有操作，要么全部完成，要么全部不完成，不可能停滞在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。一致性（Consistency）事务必须始终保持系统处于一致的状态隔离性（Isolation）使得在同一时间仅有一个请求用于同一数据。持久性（Durability）在事务完成以后，该事务对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。一个支持事务（Transaction）的数据库，必须要具有这四种特性，否则在事务过程（Transaction processing）当中无法保证数据的正确性，交易过程极可能达不到交易方的要求
常见概念：
DB：数据库，存放数据
DBMS:数据库管理系统,创建和管理DB
SQL:结构化查询语言
ER图：实体-联系图，实体用矩形，属性用椭圆，联系用菱形
- 三级模式
外模式(用户模式)—>模式(概念模式)—>内模式(存储模式)
两级映像：外模式—>模式 ②模式—>内模式
模式（逻辑模式）：是数据库中全体数据的逻辑结构和特征的描述，是数据库系统模式结构的中间层，即不涉及数据的物理存储细节，也与具体应用程序开发工具语言无关。
外模式（用户模式）：是用户能看见和使用的局部数据的逻辑结构和特征描述，是与某一应用有关的数据的逻辑表示，是模式的子集，一个数据库可以有多个外模式。
内模式（存储模式）：数据物理结构和存储方式的描述，是数据在数据库内部的表示方式，如存储方式是按照某个属性升序存储，什么索引等。
外模式模式映像：当模式发生改变，数据库管理员对外模式模式映像作相应改变，可使外模式不变，从而应用程序不用修改。保证数据与程序的逻辑独立性。
模式内模式映像：当数据库的存储结构改变了，由数据库管理员对模式内模式映像作相应改变，可以保持模式不变，从而应用程序也不必改变，保证了数据与程序的物理独立性。
三级模式使用户能逻辑地抽象地处理数据而不关心数据在计算机内具体表示方式与存储方式，两级映像保证了数据库系统中的数据有较高的逻辑独立性和物理独立性。
- 数据库设计六个阶段
需求分析：分析用户，数据，功能和性能需求
概念结构设计：画E-R图
逻辑结构设计：E-R图转换为表
数据库物理设计：为数据库选择存储结构和存储路径
数据库实施：编程，测试，运行
数据库运行和维护：日常维护
索引:创建唯一索引保证数据记录唯一性，可加快数据检索速度，加速多表之间的连接
数据库数据模型：
层次模型：一对多，联系通过指针实现，查找效率高
网状模型
关系模型：二维表，最流行
- 数据库中锁有什么作用？什么是只读锁、什么是只写锁？
一个事物对数据加锁可以保证事物的四个特性，加锁后其他事物不能更新此数据对象，不会产生数据不一致性。
写锁（排他锁/ X锁）：加写锁其他事物不能在对这个数据加任何类型锁，释放之前不能读取和修改。
读锁（共享锁/ S锁）：事物对数据加读锁，其他事物可以读但不可以修改，可以加读锁不能加写锁。
- 数据库恢复有哪些实现方式？
一，建立冗余数据；
建立冗余数据最常用的技术是数据转储和登记日志文件。通常在一个数据库
系统中，这两种方法是一起使用的。
（1）数据转储
转储：DBA 定期地将整个数据库复制到磁带或另一个磁盘上保存起来的过程。这些备用的数据称为后备副本（backup）或后援副本。
A.静态转储：当系统中无运行事务时进行转储，转储开始时数据库处于一致状态，转储期间不允许对数据库的任何存取、修改活动。优点：实现简单。缺点：降低了数据库的可用性—>转储必须等用户事务结束；新的事务必须等转储结束。
D.增量转储：只转储上次转储后更新过的数据。使用海量转储得到的后备副本进行恢复往更方便如果数据库很大，事务处理又十分频繁，则增量转储方式更实用有效。
（2）登记日志文件
1、触发器的作用？触发器是一中特殊的存储过程，主要是通过事件来触发而被执行的。它可以强化约束，来维护数据的完整性和一致性，可以跟踪数据库内的操作从而不允许未经许可的更新和变化。可以联级运算。如，某表上的触发器上包含对另一个表的数据操作，而该操作又会导致该表触发器被触发。
- 什么是存储过程？用什么来调用？
存储过程是一个预编译的SQL语句，优点是允许模块化的设计，就是说只需创建一次，以后在该程序中就可以调用多次。如果某次操作需要执行多次SQL，使用存储过程比单纯SQL语句执行要快。 调用： 1）可以用一个命令对象来调用存储过程。 2）可以供外部程序调用，比如：java程序。
- 存储过程的优缺点？
优点： 1）存储过程是预编译过的，执行效率高。 2）存储过程的代码直接存放于数据库中，通过存储过程名直接调用，减少网络通讯。 3）安全性高，执行存储过程需要有一定权限的用户。 4）存储过程可以重复使用，可减少数据库开发人员的工作量。 缺点：移植性差
- 索引的作用？和它的优点缺点是什么？
索引就一种特殊的查询表，数据库的搜索可以利用它加速对数据的检索。它很类似与现实生活中书的目录，不需要查询整本书内容就可以找到想要的数据。索引可以是唯一的，创建索引允许指定单个列或者是多个列。缺点是它减慢了数据录入的速度，同时也增加了数据库的尺寸大小。
- 什么样的字段适合建索引
唯一、不为空、经常被查询的字段
- 什么叫视图？游标是什么？
视图：是一种虚拟的表，具有和物理表相同的功能。可以对视图进行增，改，查，操作，试图通常是有一个表或者多个表的行或列的子集。对视图的修改会影响基本表。它使得我们获取数据更容易，相比多表查询。 游标：是对查询出来的结果集作为一个单元来有效的处理。游标可以定在该单元中的特定行，从结果集的当前行检索一行或多行。可以对结果集当前行做修改。一般不使用游标，但是需要逐条处理数据的时候，游标显得十分重要。
- 视图的优缺点
优点： 1）对数据库的访问，因为视图可以有选择性的选取数据库里的一部分。 2 ）用户通过简单的查询可以从复杂查询中得到结果。 3 ）维护数据的独立性，试图可从多个表检索数据。 4 ）对于相同的数据可产生不同的视图。 缺点： 性能：查询视图时，必须把视图的查询转化成对基本表的查询，如果这个视图是由一个复杂的多表查询所定义，那么，那么就无法更改数据
- 列举几种表连接方式,有什么区别？
内连接、自连接、外连接（左、右、全）、交叉连接 内连接：只有两个元素表相匹配的才能在结果集中显示。 外连接： 左外连接:左边为驱动表，驱动表的数据全部显示，匹配表的不匹配的不会显示。 右外连接:右边为驱动表，驱动表的数据全部显示，匹配表的不匹配的不会显示。 全外连接：连接的表中不匹配的数据全部会显示出来。 交叉连接： 笛卡尔效应，显示的结果是链接表数的乘积。
- C++
- c语言中怎么分区？
答：分别是
静态存储区：存放全局、局部静态变量
栈区：存放局部变量，函数调用结束会自己释放内存
堆区：申请内存的空间
常量区存放：常量（程序在运行的期间不能够被改变的量 例如：10,‘a’,1.12,“ios”,数组的名字）常量区的内容通常只能读的不能被修改的。
代码区: 代码区的存放：程序中的函数编译后cpu指令
代码区的地址：函数的地址，程序的入口地，程序的名字
程序被操作系统加载到内存的时候，所有可执行的代码（程序代码指令，常量字符串等)都加载到代码区，这块内存在程序运行期间是不变的。代码区是平行的，里面装的就是一堆指令，在程序运行期间是不能改变的，函数也是代码的一部分，故函数都被放在代码区，包括main函数。
- c语言中static关键字的作用有哪些？
最后对static的三条作用做一句话总结。首先static的最主要功能是隐藏，其次因为static变量存放在静态存储区，所以它具备持久性和默认值0。https://blog.csdn/tr_ainiyangyang/article/details/80965574
答：在C中，static主要定义全局静态变量（限制作用域）、定义局部静态变量（改变存储区）、定义静态函数（限制作用域）。（还可以用于定义c++中静态函数和静态成员）
- 不能做switch()参数的是？
答：实型变量（float，double，string），能做switch()参数的是：byte，char，short，int，long，bool，整数类型和枚举类型
- 如果局部变量与全局变量重名会出现什么？
答：函数体内局部变量会屏蔽全局变量，若要使用被屏蔽的全局变量，需要在全局变量前加上::（域运算符）
- 什么是野指针？
答：野指针就是指向一个已删除的对象或者未申请访问受限内存区域的指针
- 字符数组的初始化？字符数组和字符串
答：字符数组的初始化有两种方式，用单个字符列表和用字符串常量；用常量字符串初始化数组时系统在最后一个字符后面加\0。
- 默认构造函数的特点？
答：默认构造函数一个类只能有一个，由不带参数的构造函数，或者为所有的形参提供默认实参的构造函数定义，当类中没有显式定义任何构造函数时，编译器自动生成一个公有的默认构造函数。
- 关于继承方式和可见性
答：public继承方式：
1. 基类中所有public成员在派生类中为public属性；
2. 基类中所有protected成员在派生类中为protected属性；
3. 基类中所有private成员在派生类中不可访问。
protected继承方式：
1. 基类中的所有public成员在派生类中为protected属性；
2. 基类中的所有protected成员在派生类中为protected属性；
3. 基类中的所有private成员在派生类中仍然不可访问。
private继承方式：
1. 基类中的所有public成员在派生类中均为private属性；
2. 基类中的所有protected成员在派生类中均为private属性；
3. 基类中的所有private成员在派生类中均不可访问。
- 面向对象三大特性有哪些？如何理解？
封装：封装是把过程和数据包围起来，对数据的访问只能通过已定义的界面。
继承：使用现有类的所有功能，并在不重写现有类的情况下对这些功能进行扩展。
多态：不同的对象对同一个消息产生不同的响应。静态多态即函数重载和运算符重载，动态多态用虚函数实现，允许将子类类型的指针赋值给父类类型的指针。
- 自增运算符前置和后置，在无编译器优化的情况下，哪个效率更高？
答：自增运算符前置效率更高。因为前置运算符先将自身递增，然后返回自身；后置运算符先创建自身的一个副本，而后自身递增，然后返回副本。
- alloc malloc calloc realloc的区别？
答：alloc向栈申请空间,alloc函数是从栈上分配内存，无需释放。
malloc向堆申请空间，参数为空间大小
calloc和malloc类似，参数为元素数目和大小
realloc是给一个已经分配了地址的指针重新分配空间
- c语言函数参数传递的三种方式？
答：值传递，指针传递，引用传递
- 请你说说C语言参数压栈顺序？
答：从右到左
- 什么是回调函数？
函数指针变量可以作为某个函数的参数来使用的，回调函数就是一个通过函数指针调用的函数。
简单讲：回调函数是由别人的函数执行时调用你实现的函数。
以下是来自知乎作者常溪玲的解说：
你到一个商店买东西，刚好你要的东西没有货，于是你在店员那里留下了你的电话，过了几天店里有货了，店员就打了你的电话，然后你接到电话后就到店里去取了货。在这个例子里，你的电话号码就叫回调函数，你把电话留给店员就叫 登记 回调函数，店里后来有货了叫做触发了回调关联的事件，店员给你打电话叫做 调用 回调函数，你到店里去取货叫做响应回调事件。
原文链接：https://blog.csdn/qq_46163557/article/details/120569344
答：回调函数即定义一个函数，然后把这个函数作为参数传入子程序中，由子程序在运行时通过函数指针来调用的函数。
- const标识符工作在什么阶段？
答：const常量无法修改是在程序编译时期检查的。不能直接修改常量的值，但是可以通过给该常量的地址赋值来达到修改的目的
- 关于指向常量的指针和常指针？
答：1.const T */T const *表示指针指向的内容不能改变，但是指针本身可以改变（常量指针）
2.T* const 表示指针本身的值不能改变，但是指针指向的内容可以改变（指针常量）
3.Const T * const表示两者都不能修改
（注：如果const位于星号的左侧，则const就是用来修饰指针所指向的变量，即指针指向的对象为常量；如果const位于星号的右侧，const就是修饰指针本身，即指针本身是常量）
int * const p =&a;//指针本身值不可以变，a的值可以变 指针常量
const int *p=&a;//指针本身值可以变，a的值不可以变 常量指针（指向常量的指针）
- 什么是const_cast？
答：const_cast强制类型转化，去掉变量的const类型
- 宏定义的特点？
答：宏定义函数会直接将宏定义的东西带入，开销小，但是宏默认没有类型检查
- 什么是内联函数？
答：内联函数inline就是对编译器的建议，减少函数调用时的开销，一定要写在头文件里面
- 引用的特点？
答：引用在定义时必须初始化，不能用常量为引用赋值 常量引用可以用常量初始化 例如：const int & crefN=13；
- 存在二级引用吗？
答：存在二级指针但是不存在二级引用 引用本身也占据空间，该空间记录的就是与该引用相关联的对象的地址 引用的实质就是编译器产生的关联对应的存储器地址常量指针
- 命令空间可以嵌套吗？
答：命名空间可以嵌套，可以取别名
- 函数重载的条件是什么？
答：函数名必须相同，作用域必须相同 函数参数个数不同或者类型不同或者顺序不同 返回值不同不能算函数重载
- 函数重载的调用规则？
答：首先根据函数名找到对应的函数，作为候选函数，再在候选函数中找到可以匹配的函数，匹配函数个数=0，报错，=1则使用该函数，>1则二义性
- 什么是对象？
答： 对象=数据（数据类型）+行为（函数）
- c语言怎么实现封装？
答：用c语言中的函数指针模拟类的封装
- 类定义的对象和类的关系？
答：类里面的数据成员是私有的，各自有各自的地址，成员函数是公有的，同一个类的对象，其成员函数地址是一样的
- 谈一谈this指针？
答：成员函数调用的时候会偷偷传递this指针，通过寄存器ecx传递 ，这种传递方式称为thiscall
- explicit关键字？=delete标识符？=default标识符？
答：explicit：表示只支持显示构造函数，不支持隐式转换 注：支持A a(name) 不支持A a=’name’
=delete:删除默认构造函数
=default:显示指出默认构造函数
- 析构函数的特点？
答：析构函数在对象释放时调用，没有参数和返回值
- 栈上的局部对象调用时机？
答：构造函数：声明对象时调用，用来初始化一个对象
析构函数：对象出作用域时调用
- 全局对象的构造析构函数调用时机？
答：构造函数：进入main函数之前
析构函数：出main函数之后
- 谈一谈拷贝构造函数？
答：本质上也是一种构造函数，当用一个对象创建另一个对象时调用，而不会调用类自带的构造函数
- 什么是浅拷贝？什么是深拷贝？
答：缺省的拷贝构造函数为浅拷贝，两个对象共用一个存储空间
深拷贝就是自己定义拷贝构造函数，需要新建一个内存空间保存数据
（注：当一个对象的成员函数中有某种需要分配的资源，为了防止该资源被多次析构，则需要自定义拷贝构造函数）
- new delete 与malloc free的区别？
答：new：分配空间，调用构造函数
delete：调用析构函数，释放空间
malloc和free不会调用构造和析构
当new和delete一个基本数据类型而不是对象时，不会调用构造和析构
new 和delete要配套使用，特别是申请对象数组时
- 继承中，子类和父类的关系？
答：子类会继承父类的所有变量，所有内存空间会大于父类，因此子类可以转化为父类，父类不能转化为子类
么是面向对象编程：简称OOP，应用程序是许多对象在计算机中相继表现自己，而对象就是一个个程序实体，每个对象都是独立但又能相互作用，当程序功能需要更改时，只需要修改相应的对象就行了。
- 什么是类
类是面向对象编程的基本概念，是具有相同性质和功能的事物的集合，也是对一组具有共性的对象的一种抽象描述。
- 类和对象的区别
类是抽象的概念，用于描述和创建对象；对象是类的实例，是可以单独存在的实体。
5.什么是抽象类：抽象类主要用来提供多个派生类可共享的基类的公共定义。设置类成员访问权限：在java中可以在声明类、成员变量和方法时，使用private、prtected、public和默认不加（default)对其进行修饰，以限制类及其成员的访问权限。6.什么是构造方法：构造方法是在创建指定类型的对象时执行的方法，名称与类相同，且无返回值，通常用于创建类的实例以及必要的初始化操作。7.什么是方法重载：方法重载是在一个类或接口中可以有多个相同名称的方法，但是却具有数量不同或者类型不同的形参。8.什么是接口：接口是对类的抽象描述，只有方法的特征而无方法的实现，因为这的方法可以在不同的地方被不同的类实现，而这些类可以具有不同的行为。9.变量的作用域：局部变量在方法中声明，并且无法被其它方法所使用，方法开始时被创建，结束后被销毁；全局变量在类中作为成员变量声明，并为其它方法所共享，在实例化时被创建（不包括静态变量）。面向对象的优点
- 面向过程与面向对象编程的区别
面向过程就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了；面向对象是把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个事物在整个解决问题的步骤中的行为。可以拿生活中的实例来理解面向过程与面向对象，例如五子棋，面向过程的设计思路就是首先分析问题的步骤：1、开始游戏，2、黑子先走，3、绘制画面，4、判断输赢，5、轮到白子，6、绘制画面，7、判断输赢，8、返回步骤2，9、输出最后结果。把上面每个步骤用不同的方法来实现。如果是面向对象的设计思想来解决问题。面向对象的设计则是从另外的思路来解决问题。整个五子棋可以分为1、黑白双方，这两方的行为是一模一样的，2、棋盘系统，负责绘制画面，3、规则系统，负责判定诸如犯规、输赢等。第一类对象（玩家对象）负责接受用户输入，并告知第二类对象（棋盘对象）棋子布局的变化，棋盘对象接收到了棋子的变化就要负责在屏幕上面显示出这种变化，同时利用第三类对象（规则系统）来对棋局进行判定。可以明显地看出，面向对象是以功能来划分问题，而不是步骤。同样是绘制棋局，这样的行为在面向过程的设计中分散在了多个步骤中，很可能出现不同的绘制版本，因为通常设计人员会考虑到实际情况进行各种各样的简化。而面向对象的设计中，绘图只可能在棋盘对象中出现，从而保证了绘图的统一。
- 面向过程与面向对象的优缺点
面向过程
优点：性能比面向对象高，因为类调用时需要实例化，开销比较大，比较消耗资源，比如单片机、嵌入式开发、Linux/Unix等一般采用面向过程开发，性能是最重要的因素。
缺点：没有面向对象易维护、易复用、易扩展面向对象
优点：易维护、易复用、易扩展，由于面向对象有封装、继承、多态性的特性，可以设计出低耦合的系统，使系统更加灵活、更加易于维护
缺点：性能比面向过程低
更多推荐
复试408总结
发布评论