先序序列和中序序列的关系：先序序列入栈，以中序序列出栈。
1.基于比较排序，关键字中间的两两比较至少为：
2.最佳归并树（严格K叉树）：每个节点（叶子节点）都恰好有 k 个子节点。
K：K路归并；n0初始归并段的个数
(n0-1)%(k-1) = U，说明其中有U个是多余的。故需要补充K - U - 1个空归并段
3.排序
补充：折半插入排序和简单选择排序与序列的初始状态无关
空间复杂度：常数个辅助空间：直接插入、冒泡、简单选择、希尔、堆排序
快速排序需要：
适用于顺序存储：折半插入、希尔、快速、堆排序
既适用于顺序，又适用于链式：直接插入、冒泡、简单选择、归并、基数排序
每趟都能产出最大或最小值：冒泡排序、简单选择排序、堆排序
快速排序一趟至少能确定一个元素的最终位置
若关键字已基本有序，则选用直接插入或冒泡排序。
4.平均查找长度
1.中断驱动方式下，第一个字符输出后，剩余的字符由中断服务程序完成
2.三态门的作用，用于控制移位器与总线之间数据通路的连接与断开
3.在IEE754中
阶码（看成无符号数） = 阶码真值 + 偏移量
4.USB (通用串行总线）的特点有： 1>即插即用；2>热插拔；3>有很强的连接能力，采用菊 花链形式将众多外设连接起来；4>有很好的可扩充性，一个USB控制器可扩充高达127个外部 USB设备；5>高速传输， 速度可达480Mbps。6>USB是串行总线
5.I/O接口与CPU之间的I/O总线有数据线、控制线和地址线。控制线和地址线都是单向传输的，从CPU传送给I/O接口，而I/O接口中的命令字、状态字以及中断类型号均是由I/O接口发往CPU的，故只能通过I/O总线的数据线传输。
6.在响应外部中断的过程中，中断隐指令完成的操作包括：1>关中断；2>保护断点；3>引出 中断服务程序（形成中断服务程序入口地址并送PC)。保存通用寄存器的内容是在进入中断服务程序后首先进行的操作。
7.USB是一种连接外部设备的 I/0 总线标准， 属于设备总线，是设备和设备控制器之间的接口。
8.用于提高RAID可靠性的措施有：磁盘镜像、奇偶校验
9.DRAM采用地址复用技 术， 地址线是原来的1/2, 且地址信号分行、 列两次传送。
10.独立编址是一种计算机系统中对输入 / 输出（I/O）设备进行编址的方式。在这种方式下，内存地址空间和 I/O 设备地址空间是相互独立的。也就是说，I/O 设备有自己专门的地址范围，这些地址与内存地址完全分开。
统一编址，也称为存储器映射 I/O（Memory - Mapped I/O），是将 I/O 设备和内存看作是一个统一的地址空间进行编址。在这种方式下，I/O 设备的寄存器被映射到内存地址空间中，就好像它们是内存的一部分。
11.大端存储（便于人类阅读）：低地址存高位，高地址存低位。
小端存储（便于机器处理）：低地址存低位，高地址存高位。
12.程序计数器的位数等于指令的个数；指令寄存器的位数等于指令字长。
13.交叉多模块启动方式：轮流启动和同时启动。
若一次性并行读写的总位数等于系统总线中的数据线数，即为同时启动方式。
轮流启动：模块之间存在明显的时间先后顺序。
同时启动：多个模块在同一时刻或者非常接近的时刻启动。
14.时间局部性：是指如果一个存储单元被访问，那么在不久的将来，它很可能会被再次访问。
空间局部性：指程序在访问内存时，倾向于访问在存储空间上相邻的数据。也就是说，当一个存储单元被访问后，其附近的存储单元在短时间内也很可能被访问。
16.指令的寻址方式
指令寻址方式有两种：一种是顺序寻址，另一种是跳跃寻址。
基址寻址：以程序的起始存放地址作为‘’起点“
相对寻址：以程序计数器PC所指地址作为“起点”
变址寻址：程序员自己决定从哪里作为“起点”
变址寻址：适应于数组；优点：在数组处理过程中，可设定形式地址A为数组首元素地址，不断改变变址寄存器IX的内容，便于形成数组中任一数据的地址。特别适用于编写循环程序。
堆栈寻址：堆栈既可用于寄存器组（称为硬堆栈）来实现，也可利用主存的一部分空间作堆栈（称为软堆栈）。
硬堆栈不访存，软堆栈访存一次。
17.看到按字节编址，则一定为8的倍数。同理按字编址一定是字的倍数。
控制存储器(CS)用来存放实现指令系统的所有微指令，是一种只读型存储器，机器运行时只读不写， 在CPU的控制器内。
CS按微指令的地址访问
20.五阶段流水线可分为取指(IF)、译码／取数(ID)、执行(EXC)、存储器读(MEM)、写回 (Write Back)。数字系统中， 各个子系统通过数据总线连接形成的数据传送路径称为数据通路， 包括程序计数器、算术逻辑运算部件、通用寄存器组、取指部件等， 不包括控制部件。
指令流水线数据通路由组合逻辑电路和时序逻辑电路组合而成。
21.在多总线结构中，总线之间必须通过桥接器相连。
22.I/O指令实现的数据传送通常发生在通用寄存器和I/O端口之间。
23.系统将数据从磁盘读取到内存的过程：
DMA的传送过程分为：预处理、数据传送、后处理三个阶段。
预处理阶段：由CPU初始化DMA控制器中的有关寄存器、设置传送方向、测设并启动设备等。
数据传送阶段：完全由DMA控制，DMA控制器接管系统总线。以数据块为单位传送。
后处理阶段：DMA控制器向CPU发出中断请求，CPU执行中断服务程序做DMA结束处理。
24.对于多周期CPU，每个指令周期（包含若干时钟周期）执行一条新指令；对于流水线CPU，只有在理想情况下才能实现每个时钟周期执行一条新指令。
25.指令译码器(ID)的作用：对操作码字段进行译码，向控制器提供特定的操作信号。在取数及执行阶段用不到。
26.无符号数乘法和有符号数乘法判断溢出
27.Cache和TLB均由SRAM组成。
28.I/O中断：响应I/O中断时允许中断触发器EINT的值为“1”
处理过程：中断请求、中断判优、中断响应、中断服务、中断返。
中断响应CPU所做的工作：关中断、保护断点。
- 中断I/O需要CPU执行中断处理程序来处理数据的传送。
- 外设准备数据的时间应大于中断处理时间（原因：假设外设准备时间需要1天，中断处理时间是1年，那么在处理第一个数据时，后续数据就会到达，没有处理的数据就会被覆盖）
29.DMA方式中，DMA与CPU共享主存，会有争用主存的情况。为有效的分时适用主存，DMA有以下三种方式访问主存。
1）停止CPU访存。优点：控制简单，适用于数据传输率很高的I/O设备实现成组数据的传送。
2）周期挪用(周期窃取)。比较适合于I/O设备的读/写周期大于主存周期。
DMA控制器挪用一个或几个主存周期来访问主存，传送完一个数据字后立即释放总线，是一种单字传送方式，每个字传送完后CPU可以访问主存。
3）DMA与CPU交替访问。适合于CPU的工作周期比主存存取周期长。
30.浮点操作次数单位;FLOPS：每秒执行多少次浮点运算
31.汇编程序员可见的寄存器：基址寄存器、PSW、PC、通用寄存器
- PSW（条件转移需要用到，程序员使用CMP指令的时候也需要用到所以是对用户可见）
- PC（跳转指令需要使用PC+n ，所以对用户可见）
- 通用寄存器（程序员写指令可以使用到通用寄存器R）
- 通用寄存器：包括(数据寄存器、地址指针寄存器、变址寄存器)
对所有用户（所有程序员）透明：MAR，MDR，IR，Cache, 微程序结构和功能，控制存储器，锁存器/暂存器
32.数据通路：指令执行过程中数据经过的路径，包括路径上的部件
33.同步总线：总线通信的双方采用同一个时钟信号，但是一次事务总线不一定在一个时钟周期内完成。
异步总线：采用握手的方式进行通信，每次握手的过程完成一次通信，一次通信会交换多位数据。
34.CPU执行时间和MIPS
MIPS：每秒执行多少百万条指令
35.指令集体系结构ISA内容：1）定义指令的行为 2）指令集的语义，但并不关注内部实现细节 3）软件和硬件接口（eg.指令寄存器个数和位数。）
36.将高级语言转换为可执行目标文件的过程：预处理、编译、汇编、链接
37.并行处理技术
1.启动系统时，首先运行ROM中代码引导块。为执行某个分区的操作系统的初始化程序，需要先执行磁盘引导程序以指示引导到哪个分区，然后执行该分区的引导程序，用于引导该分区的操作系统。
2.磁盘扇区的划分是在磁盘的物理格式化操作中完成的。
3.文件系统根目录的建立是在逻辑格式化操作中完成的。
4.进程切换属于系统调用执行过程中的事件，只能发生在核心态。
系统调用是操作系统提供给用户程序的接口，系统调用发生在用户态，被调用程序在核心态下执行。
外部中断是用户态到核心态的“门”，也发生在用户态，在核心态完成中断过程。
缺页产生后，在用户态发生缺页中断，然后进入核心态执行缺页中断服务程序
5.子程序调用只需保存程序断点，即该指令的下一条指令的地址；中断调用子程序不仅要保 护断点(PC 的内容），而且要保护程序状态字寄存器的内容PSW。
6.设备管理软件一般分为四个层次：用户层、与设备无关的系统调用处理层、设备驱动程序 以及中断处理程序。
7.用户进程通过read系统调用读取一个磁盘文件中的数据的过程
当所读文件的数据不在内存时，产生中断（缺页中断）， 原进程进入阻塞状态，直 到所需数据从外存调入内存后，才将该进程唤醒。read系统调用通过陷入将CPU 从用 户态切换到核心态， 从而获取操作系统提供的服务。
要读一个文件首先要用open系 统调用打开该文件。open中的参数包含文件的路径名与文件名， 而read只需要使用open返回 的文件描述符，并不使用文件名作为参数。
read要求用户提供三个输入参数：＠文件描述符fd; @buf缓冲区首址；＠传送的字节数n。read的功能是试图从fd所指示的文件中读入n个字节 的数据， 并将它们送至由指针buf所指示的缓冲区中。
8.计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的
9.系统开机后，操作系统的程序会被自动加载到内存中的系统 区，这段区域是RAM。
10.关中断必须在核心态执行。
11.只有FIFO算法才会导致Belady异常。
12.多级页表优点：减少页表所占的连续内存空间。
13.存取时间 = 寻道时间 + 延迟时间 + 传输时间
14.在程序中断I/0方式中，CPU和打印机直接交换，打印字符直接传输到打印机的 I/0端口， 不会涉及主存地址，而 CPU和打印机通过I/0端口中状态口和控制口来实现交互。
检测异常由CPU (包括控制 器和运算器）实现的。
中断请求一般来自CPU以外的事件，异常一般发生在 CPU内部。
特殊情况， 如除数为零和自行中断(INT)都会自动跳过中断指令， 不会返回到发生异常的指令继续执行。
外部中断有：定时器到时、网络数据包到达
16.死锁预防，采用破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。
银行家算法是最著名的死锁避免算法。
死锁的检测和解除，系统为进程分配资源时不采取任何措施，但提供死锁的检测和解除的手段。
17.内存分配策略：1）固定分配局部置换 2）可变分配全局置换 3）可变分配局部置换
可变分配全局置换：只要缺页就给分配新的物理块
可变分配局部置换：根据发生缺页的频率来动态的增减或减少进程物理块
18.判断处于死锁状态的进程使用资源分配图。
19.需要进行互斥操作的是对临界资源的访问，也就是不同线程对同一进程内部的共享变量的访问，才有可能需要互斥。
不同进程的线程，代码段或变量不存在互斥访问的问题。同一线程内部的局部变量也不存在互斥访问问题。
20.设备与输入／输出井之间数据的传送是由系统实现
21.执行系统调用的过程：正在运行的进程先传递系统调用参数，然后由陷入(trap) 指令负责将用户态转化为内核态，并将返回地址压入堆栈以备后用，接下来 CPU执行相应的内 核态服务程序，最后返回用户态。
22.磁盘逻辑格式化程序：一个新的磁盘是一个空白版，必须分成扇区以便磁盘控制器能读和写，这个过程称为低级格式化（或物理格式化）。低级格式化为磁盘的每个扇区采用特别的数据结构，包括校验码。为了使用磁盘存储文件，操作系统还需要将其数据结构记录在磁盘上。这分为两步。第 一步是将磁盘分为由一个或多个柱面组成的分区，每个分区可以作为一个独立的磁盘。 在分区之后，第二步是逻辑格式化（创建文件系统）。在这一步，操作系统将初始的文件系统数据结构存储到磁盘上。这些数据结构包括空闲和已分配的空间和一个初始为空的目录。
中断向量表也在操作系统初始化时创建。
23.文件共享的方式：1）有向无循环图DAG 2）索引节点(硬链接) 3）利用符号链接(软链接)
2）索引节点(硬链接) ：每个用户的文件目录中，都设置有指向共享文件的索引节点指针
3）符号链接(软链接)：允许一个文件或主目录有多个父目录，但只有主文件才拥有指向其索引结点的指针。
其他用户只有该文件的路径名（这种方式被称为符号链接）。
24.处理机调度问题
高级调度又称为长程调度或作业调度。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才会撤销PCB。
低级调度又称为进程调度或短程调度。进程调度的频率很高，一般为几十毫秒一次。
中级调度又称为内存调度。
25.处理机调度算法的共同目标
1）资源(CPU)利用率 2）公平性 3）平衡性 4）策略强制执行
26.批处理系统的目标
1）平均周转时间短。周转时间 = 作业完成时间 - 作业提交时间
带权周转时间
2）系统吞吐量
3）处理机利用率
27.高响应比优先调度算法：不会导致饥饿（非抢占式算法）
28.系统将CPU分配给高优先权进程，进程会进入就绪态。
29.同一时刻，管程中只允许有一个进程执行。、
30.时钟中断的主要工作是处理和时间有关的信息以及决定是否执行调度程序，和时间有关的所有信息，包括时间、进程的时间片、延时、CPU的使用时间，各种定时器。
31.用户级线程是在用户空间中实现的。对于线程的创建、撤销、同步与通信等功能，都无需内核的支持。即用户级线程与内核无关。当一个用户级线程被阻塞，整个都会阻塞。
32.只有内核级线程才是处理机的分配单位
33.系统调用：1）执行系统调用服务程序的过程中，CPU处于内核态。2）操作系统通过提供系统调用避免用户程序直接访问外设。
34.传统文件管理空闲磁盘的方法包括空闲表法、空闲链表法、位示图和成组链接法。
35.分段系统的一个突出优点是易于实现段的共享。不同进程共享段实际上是在共享段表中的段表项。
36.死锁的预防能确保系统不发生死锁。
37.最佳适应算法最容易产生内部碎片。
40.大题：计算柱面号，磁头号，扇区号
41.父进程可与子进程共享一部分资源，但不能共享虚拟地址空间，在创建子进程时，CPU会为子进程分配资源，如虚拟地址空间等。
42.具有设备独立性的系统，用户使用逻辑设备名来访问物理设备，需要建立逻辑设备与物理设备之间的映射关系。经过驱动程序来控制物理设备。若更换物理设备，只需更换驱动程序。
43.实现临界区互斥必须遵循的准则
1）空闲让进 2）忙则等待 3）有限等待 4）让权等待（原则上应该遵循，但非必须）
44.在内核态下，CPU 可执行任何指令， 在用户态下 CPU 只能执行非特权指令， 而特权指令只能在内核态下执行。 常见的特权指令有： 1）有关对I/O设备操作的指令；2）有关访问程序状态的指令； 3）存取特殊寄存器指令；3）其他指令。
45.页置换，进程调度均是由操作系统独立完成。创建进程需要系统调用完成。
46.产生系统调用时， CPU执行陷入 (Trap) 指令，检测到 “内中断” 后，由CPU负责保存断点 (PC) 和程序状态字，并将CPU模式改为内核态，然后执行操作系统内核的系统调用入口程序，该内核程序负责保存通用寄存器的内容，再调用某个特定的系统调用服务例程。
由操作系统完成的就是：操作系统内核的系统调用入口程序，该内核程序负责保存通用寄存器的内容，再调用某个特定的系统调用服务例程。
47.系统启动过程
1.以太网的MAC协议提供的是无连接不可靠服务
2.OSI提供流量控制的有：数据链路层、网络层、传输层；
数据链路层是相邻结点之间的流量控制；网络层是整个网络中的流量控制；传输层是端到端的流量控制。
拥塞控制的有：网络层、传输层
3.以太网使用的是曼彻斯特编码。曼彻斯特是中间发生跳变。差分曼彻斯特是边界发生跳变。
曼彻斯特编码：编码速率是码元速率的2倍。比特率：波特率 = 1:2 。发送一个比特需要两个信号周期。
非归零NRZ编码（串行编码）：高电平表示1，低电平表示0；反向非归零NRZI编码：电平在边界跳变表示0 、电平保持不变表示1。
4.ARP协议的功能：根据IP地址查询MAC地址。
5.直通交换在输入端口检测到一个数据帧时，检查帧首部，获取帧的目的地址，启动内部的 动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据帧直通到相应的端口， 实现交换功能。
直通交换方式只检查帧的目的地址，共6B, 所以最短的传输延迟是 6x8bit/100Mbps = 0.48µs。
6.SMTP只支持传输7比特ASSCII码内容（一个字符占7位）
7.后退N帧协议（GBN），从发送第一帧开始到收到第一帧的确认帧的这段时间内，可将序号落在发送窗口内的所有数据帧全部发送出去。
8.POP3协议接受文件时，使用的传输层服务类型是有连接的可靠传输服务
10.HTTP请求报文：Connection：连接方式，Close表示非持续连接方式，keep-alive表示持续连接方式。Cookie方法表示曾经访问过此网站。
11.争用期：以太网的端到端往返时间2τ（一个τ为单程传播时延）；争用期包含信号端到端的传播时延和Hub再生比特流的时间。
最短帧长：争用期内可发送的数据长度。以太网规定最短帧长为64B即512bit
最短帧长 = 总线传播时延 数据传输速率 2
12.主机向本地域名服务器查询都采用递归查询。
本地域名服务器向其他域名服务器（根域名服务器、顶级域名服务器、权限域名服务器）采用递归查询或迭代查询
13.比特率 = 波特率 单个调制对应的二进制位数
14.对正确接收到的数据帧进行确认的MAC协议是CSMA/CA。
15.IEEE802.11数据帧F的各地址
16.FTP协议
FTP协议使用控制连接和数据连接，控制连接存在于整个FTP会话过程中，数据连接在每 次文件传输时才建立，传输结束就关闭。
默认情况下 FTP协议使用TCP 20 端口进行数据连接，TCP 21端口进行控制连接。 但是是否使用TCP 20端口建立数据连接与传输模式有关，主动方式使用TCP20端口， 被动方式由服务器和客户端自行协商决定。
17.DNS在TCP/IP应用层使用传输层无连接服务。
18.停止等待协议（stop-and-wait）是数据链路层中实现可靠传输的基本方法之一。它要求发送方在发送完一个数据帧后，必须停下来等待接收方的确认。只有在收到确认后，发送方才能继续发送下一个数据帧。这种协议能够确保数据不因丢包或包乱序而丢失，是自动重传请求（ARQ）方法中最简单的形式。
19.运输层使用不同的端口号来区分不同进程。
故TCP、UDP协议实现分用时所依据的头部字段是目的端口号。
20.TCP规定当发送方收到对同一个报文段的3个重复确认时，就可以确认这个被确认报文段之后的报文已丢失，立即执行快速重传算法。
21.虚电路是逻辑上的连接，并不是一条物理上的连接，故不需要为每条虚电路预分配带宽。
22.信道利用率
：包括发送数据帧的发送时延
23.UDP首部有8B，TCP最短首部有20B。
24.理想低通信道下的极限数据传输速率 =
信道的极限数据传输速率 = ；信噪比 = 单位dB
25.SDN体系结构
SDN控制器与其下面的数据层面中的受控设备的通信接口叫南向API
SDN控制器与其上面的控制层面中的网络控制应用程序的接口叫北向API
数据链路层协议：SDLC、HDLC、PPP、STP等。
网络层协议：IP、IPX、ICMP、ARP、RARP、RIP、OSPF等。
传输层：TCP、UDP
应用层：FTP、SMTP、HTTP、DNS等。
ISO/OSI参考模型在网络层支持无连接和面向连接的通信，在传输层仅支持面向连接的通信。
TCP/IP参考模型在网络层仅支持无连接通信，在传输层支持无连接和面向连接的通信。