前言

本文为博主考研期间准备的知识点，涵盖本科大部分内容，其中大部分在复试期间准备的。复试非常非常重要，准备的越充分越好，希望大家重视。本文内容为本人自己总结及从其他地方看到的一些资源。格式凌乱，后续会慢慢整理，祝各位前程似锦！

前沿知识

1. 你对人工智能有什么了解？强人工智能可能实现吗？

   人工智能的研究领域很宽泛，包括机器人、图像识别、专家系统、语言识别、自然语言处理等。

   强人工智能：各方面和人类一样得心应手，可以和人类比拟，目前还做不到。（人类连自己都不了解自己，又怎么能创造和人类一样的“生物”呢）

   超人工智能：所有领域都比最聪明的人类聪明的多，这也是总是出现永生、灭绝危机的来源。

   人工智能是什么？

2. 什么是机器学习？讲讲具体的算法。

   机器学习是人工智能的一个分支。它研究计算机怎么模拟和实现人类的学习行为，以获取新的知识和技能，重新组织已有的知识结构（不断完善自身的性能，或者达到操作者特定的要求）

   

3. 你认为本科学的数学有哪些会用到机器学习中？

   搞清楚这些数学原理，可以帮助我们：选择正确的算法、选择参数设置和验证策略、通过理解偏差-方差权衡，识别欠拟合和过拟合、估算正确的置信区间和不确定性。

   统计学是核心，微积分告诉我们怎样学习和优化模型，线性代数使得算法能在超大型数据集上运行，概率论帮我们预测某个事件发生的可能性。那么我们举个简单的栗子来告诉大家这四块是如何在机器学习中起作用的。

4. 什么是大数据？你接触到的最大的数据有多大?

5. 什么是数据挖掘？

6. 大数据和机器学习之间有什么联系？

   可以认为大数据、数据挖掘和机器学习是三个平行的概念。大数据侧重描述数据，数据挖掘侧重描述应用，机器学习侧重描述方法。

   （1）大数据就是许多数据的聚合；（2）数据挖掘就是把这些数据的价值发掘出来；（3）数据挖掘就是把这些数据的价值发掘出来

7. 什么是云计算？

   云计算的道理是简单的，说白了，就是把计算机资源集中起来，放在网络上。

   阿里云、华为云、腾讯云都是。按需要资源付费，随时使用。

8. 什么深度学习？

   深度学习的基础，叫做神经网络，这本身就是一种机器学习算法。深度学习的强大是有数学原理支撑的，这个原理叫做“万能近似定理”。这个定理的道理很简单 —— 神经网络可以拟合任何函数，不管这个函数的表达是多么的复杂。但是，哪有免费的午餐，深度学习的强大也带来了对应的问题 —— 黑箱化。黑箱的意思是，深度学习的中间过程不可知，深度学习产生的结果不可控。

操作系统

操作系统

1.什么是操作系统，目标和功能是什么，特征是什么？

操作系统是指控制和管理整个计算机的硬件和软件资源，合理的组织调度计算机的工作和资源的分配，提供给用户和其他软件方便的接口和环境的程序集合。他是一个系统软件。

目标：方便性，有效性，可扩充性，开放性。

功能：作为计算机系统资源的管理者（处存文设），作为用户和硬件系统之间的接口(命令接口和程序接口)，用作扩充机器。

特征：并发，共享，虚拟，异步，其中并发和共享是最两个基本的特征。

并发是两个或多个事件在同一时间间隔内发生。

共享即资源共享，是指系统的资源可供内存中多个并发执行的进程共同使用。

虚拟是把一个物理上的实体变为若干个逻辑上的对应物。

异步是指进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进。

2.何谓批处理操作系统？

批处理系统指用户的作业成批的处理，作业建立、处理、完成都自动由系统成批完成。引入批处理系统的目的是要解决人机矛盾及CPU与I/O设备之间速度不匹配，提高设备的利用率，提高系统吞吐量。

3.什么是单道批处理系统，主要特征是什么？

单道批处理系统：系统对作业的处理是成批进行的，但内存中始终保持一道作业

自动性：磁带上的一批作业能自动的逐个依次运行，而无需人工干预。

顺序性：磁道上的各道作业是顺序地进入内存，各道作业的完成时间与他们进入内存的顺序基本一致

单道性：内存中仅有一道程序运行。

4.什么是多道程序设计技术？基本特征是什么？引入技术哪些好处？需要解决什么问题？

多道程序技术就是同时把多个程序放入内存，允许它们交替在CPU中运行，共享系统资源。当一道程序因I/O请求而暂停运行时，CPU便立即转向运行另一道程序。

多道程序运行的特征（特点）

多道：计算机内存中同时存放多道相互独立的程序。

宏观上并行：同时进入系统的多道程序都处于运行过程中，即先后开始了各自的运行，但都未运行完毕。

微观上串行：内存中的多道程序轮流占有CPU，交替执行。

优点是：资源利用率高（多道程序共享计算机资源，从而使各种资源得到充分利用），系统吞吐量大（CPU和其他资源保持忙碌状态）。

需要解决处理机，内存，设备分配情况，如何组织和存放大量的程序和数据，以便用户使用和保证其安全性与一致性。

5.什么是分时技术？什么是分时系统？最关键的问题？基本特征？

分时技术：处理器的运行时间分成很短的时间片，按时间片轮流把处理器分配给各联机作业使用。

分时系统：多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时与主机进行交互操作而不互相干扰。

最关键的问题：是如何使用户能与自己的作业进行交互，即当用户在自己的终端上输入命令时，系统应能及时接收并及时处理该命令，再将结果返回用户。

同时性：也叫多路性，指允许多终端用户同时使用一台计算机。

交互性：用户能方便地与系统进行人机交互。

独立性：系统中的多个用户可以彼此独立的进行操作，互不干扰。

及时性：用户请求能在很短时间内获得响应。

6. 批处理系统和分时系统和实时操作系统各有什么特点？

批处理操作系统：用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行，交互能力差，系统响应时间长。

分时操作系统：多个用户同时使用计算机，人机交互能力强，具有每个用户独立地使用计算机的独占性，系统响应时间及时。

实时操作系统：能对控制对象作出及时反应，可靠性高，响应及时，但是资源利用率低。

7. 为什么要处理器为什么要区分核心态和用户态两种操作方式？在什么情况下进行两种方式的切换？用户态转向核心态的例子？

管态：当执行操作系统程序时，处理机所处的状态

目态：当执行普通用户程序时，处理机所处的状态

区分执行态的主要目的是保护系统程序。用户态到和核心态的转换发生在中断产生时而核心态到用户态的转换则发生在中断返回到用户程序时。

系统调用，发生一次中断，用户程序产生错误状态和企图执行以条特权指令，执行特权指令。

8.试说明访管指令、特权指令和原语

访管指令是一类机器指令，执行访管指令可以引起访管中断

特权指令是计算机中不允许用户直接使用的指令。

系统调用是用户在程序中调用操作系统所提供的一些子功能，是提供编程人员的接口。

原语是指由若干条机器指令构成，并用于完成特定功能的一段程序，在执行期间不可分割。主要特点是不可分割性。基本特点：最底层最接近硬件的部分，具有原子性——其操作只能一气呵成，运行时间短和调用频繁。

9.什么是系统调用？执行过程？与一般调用有什么区别？

所谓系统调用是用户在程序中调用操作系统所提供的一些子功能，是提供编程人员的接口。

通过系统调用命令，中断现行程序而转去执行相应的子程序，以完成特定的系统功能。完成后，又返回到发出系统调用命令之后的一条指令，被中断的程序将继续执行下去。

系统调用与一般过程调用不同，其主要区别是：

运行的状态不同。在程序中的过程一般或者都是用户程序，或者都是系统程序，即都是运行在同一个系统状态的（用户态或系统态）。进入的方式不同。一般的过程调用可以直接由调用过程转向被调用的过程。而执行系统调用时，由于调用过程与被调用过程是处于不同的状态，因而不允许由调用过程直接转向被调用过程，通常是通过访问管中断（即软中断）进入，先进入操作系统，经分析后，才能转向相应的命令处理程序。返回方式的不同。代码层次不同。一般过程调用中的被调用程序是用户级程序，而系统调用是操作系统中的代码程序，是系统级程序。

9.什么是中断？中断处理的一般过程分为哪几个阶段？用哪几种？

所谓中断是指CPU对系统发生的某个事件（中断源）作出的一种反应：CPU暂停正在执行的程序，保留现场后自动地转去执行相应的处理程序，处理完该事件后再返回断点继续执行被“打断”的程序。中断处理的一般过程分为以下阶段：保存现场，分析原因，处理中断，返回断点。

中断：也称外中断，指来自于CPU执行指令以外的事件发生，如设备发出的I/O结束中断。

异常：也称内中断，例外或陷入，指来自于CPU执行指令内部的事件发生。

10.为什么说直到出现中断和通道技术后 , 多道程序概念才变为有用的 ?

道程序并发执行是指有的程序正在CPU上执行，而另一些程序正在I/O设备上进行传输。在时间上的重叠必须有中断和通道技术支持其原因如下：1.通道是一种控制一台或多台外部设备的硬件机构，它一旦被启动就独立于CPU运行，因而做到了I/O设备与CPU并行工作。但早期CPU通过向通道发出询问指令来了解通道工作是否完成。若未完成则主机就循环询问直到通道工作结束为止。因此这种询问方式是无法真正做到并行工作的。 2)在硬件上引入了中断技术。所谓中断是指CPU对系统发生的某个事件（中断源）作出的一种反应：CPU暂停正在执行的程序，保留现场后自动地转去执行相应的处理程序，处理完该事件后再返回断点继续执行被“打断”的程序。 因此通道技术和中断技术结合起来就可以实现并行工作。即CPU启动通道传输数据后便去执行其他程序的计算工作而通道则进行输入/输出操作；当通道工作结束时再通过中断机构向CPU发出中断请求CPU则暂停正在执行的操作对出现的中断进行处理处理完后再继续原来的工作。这样就真正做到了CPU与I/O设备并行工作。此时多道程序的概念才变为现实。

进程管理

11.什么是进程？为什么引入进程？进程和程序的区别？

答：进程是具有独立功能的程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位。在多道程序环境下，允许多个程序并发执行，此时他们将失去封闭性，并具有间断性和不可再现性的特征。为此引入了进程的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性。引入进程的目的就是为了是程序能与去其他进程的程序并发执行，以提高资源利用率。

进程是动态，程序是静态的；

进程是独立运行的单位，程序不能作为运行单位；

进程间在并发执行过程中会产生相互制约关系，而程序由于是静态的，所以不存在异步特征。

12.进程的最主要的特征有哪些？

动态性：进程是程序的一次执行， 他有着创建、 活动、暂停、终止等过程，具有一定的生命周期，是动态的产生、变化和消亡的。 动态性是进程最基本的特征

并发性：多个进程实体，同存于内存中，能在一段时间内同时运行

独立性：指进程实体是一个能独立运行、独立获得资源和独立接收调度的基本单位。

异步性：每个进程都以其相对独立、不可预知的速度向前推进

结构性：每个进程有一个控制块PCB

13.什么是进程实体？什么是PCB？为什么要引入PCB？为什么说PCB是进程唯一存在的标志?PCB包含哪些内容？

进程实体由程序段、相关数据段和PCB三部分组成。

进程控制块 (PCB)是记录进程的动态执行情况的一种数据结构。为了使参与并发执行的程序能独立的运行，必须为之配置一个专门的数据结构。

每个被创建的进程都由惟一的PCB来标识，操作系统根据 PCB对进程实施控制和管理；当一个进程完成它的工作被系统撤销时，它的PCB也被撤销。因此， PCB是进程存在的惟一标志，进程的动态、并发等特征都是通过 PCB表现出来的。

PCB 主要包括：进程描述信息、进程控制和管理信息、资源分配清单和处理器相关信息等。

14.说明进程在三个基本状态之间转换的典型原因。

A.处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态变为执行状态.

B.当前进程因发生某事件而无法执行，如访问已被占用的临界资源，就会使进程由执行状态转变为阻塞状态.

C.当前进程因时间片用完而被暂停执行，该进程便由执行状态转变为就绪状态.

15.什么是进程控制？什么是原语？进程控制原语主要有哪些？

进程控制的主要功能是对系统中所有进程实施有效地管理，她具有创建新进程、撤销已有进程、实现进程状态转换等功能。原语是指由若干条机器指令构成，并用于完成特定功能的一段程序，在执行期间不可分割。主要特点是不可分割性。基本特点：最底层最接近硬件的部分，具有原子性——其操作只能一气呵成，运行时间短和调用频繁。

创建原语，撤销原语，挂起原语，激活原语，阻塞原语，唤醒原语。

16.创建原语过程？终止原语过程？

创建原语：为新进程分配一个唯一的进程标识号，并申请一个空白的 PCB 。

为进程分配资源。为新进程的程序和数据，以及用户栈分配必要的空间。

初始化PCB。主要包括初始化标志信息、初始化处理器状态信息和初始化处理器控制信息，以及设置进程的优先级。

1）如果进程就绪队列能够接纳新进程，就将新进程插入到就绪队列，等待被调度运行。

终止原语：据被终止进程的标识符，检索 PCB ，从中读出该进程的状态。

2） 若被终止进程处于执行状态， 立即终止该进程的执行，将处理器资源分配给其他进程。

3） 若该进程还有子进程，则应将其所有子进程终止。

4） 将该进程所拥有的资源、或归还给父进程或归还给操作系统。

5） 将该 PCB 从所在队列（链表）中删除。

17.进程的切换是什么？过程是怎么样的？

进程切换是指处理机从一个进程的运行转到另一个进程运行。

保存处理器上下文，包括程序计数器和其他寄存器。更新 PCB 信息。把进程的 PCB 移入相应的队列，如就绪、在某时间阻塞等队列。选择另一个进程执行， 并更新其 PCB 。更新内存管理的数据结构。恢复处理器的上下文。

18.为什么需要系统调用来实现通信？什么是进程的通信？进程通信有哪些？

每个进程有自己相互独立的地址空间。在操作系统和硬件的地址机构保护机制下，进程无法访问其他进程的地址空间，所以必须借助于操作系统的系统调用函数实现进程之间的通信。

进程通信就是进程之间的数据交换。低级通信方法和高级通信方法。高级通信方法可分为共享存储、消息传递和管道

共享存储：在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行读/写操作实现进程之间的信息交换。在对共享空间进行操作时，需要使用同步互斥工具（如P操作、V操作）共享存储又分为两种：低级方式的共享是基于数据结构的共享；高级方式则是基于存储区的共享。

消息传递：在消息传递系统中，进程间的数据交换是以格式化的消息(Message)为单位的。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。

1. 直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。

2. 间接通信方式：发送进程把消息发送到某个中间实体中，接收进程从中间实体中取得消息。这种中间实体一般称为信箱。

管道：消息传递的一种特殊方式。所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道提供输入的写进程，以字符流形式将大量的数据送入管道；而接收管道输出的读进程，则从管道中读数据。为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步和确定对方的存在。

19．什么是线程？为什么引入线程？线程和进程的比较？

线程是进程的一个实体,是系统独立调度和分派的基本单位，线程自己不拥有系统资源（只拥有一点在运行中必不可少的资源）但线程可以访问其隶属进程的系统资源。

而引入线程，则是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

调度性。传统操作系统中，拥有资源和调度的基本单位是进程。在引入线程的 OS中，进程是拥有资源的基本单位，线程是调度的基本单位。

并发性。引入线程的 OS中，进程可以并发，一个进程的多个线程也可以并发，不同进程的线程也可以并发。

拥有资源。不管传统操作系统还是有线程的操作系统进程都是拥有资源的基本单位， 线程不拥有系统资源（只拥有一点在运行中必不可少的资源），但线程可以访问其隶属进程的系统资源。

开销。创建和撤消进程时，必须为之分配和回收资源，因而付出的开销要明显大于线程

10.什么是作业调度，进程调度，内存调度？什么是作业？

作业调度：用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行

进程调度：用来决定就绪队列中的哪个进程应获得处理机。

内存调度：又称中级调度，主要任务是按照给定的原则和策略，将处于外存对换区中的重新具备运行条件的进程调入内存，或将内存中暂时不能运行的进程交换到外存对换区。

作业：用户在一次上机过程中要求计算机系统所做工作的集合

引起进程调度：有进程运行完毕，进程调用阻塞原语，p操作时资源不足，v操作激活等待队列的进程，时间片用完（分时系统），优先级跟高的进程到来（抢占式调度）

11. 非抢占式和可抢占式高优先级调度算法的区别是什么? 调度的准则是什么？

最高优先级调度算法原则上总是调度就绪队列中优先级最高的那个进程。采用非抢占式最高优先级调度算法，当就绪队列中某进程的最高优先级高于正在处理器中运行的进程的最高优先级时，并不会让正在运行的进程退出处理器，而是将高优先数的排在就绪队列的首部。而采用抢占式最高优先级进程调度算法，则高优先数的进程会抢占处理器，让正在处理的进程处于就绪队列。

CPU 利用率

系统吞吐量（表示单位时间内 CPU 完成作业的数量）

周转时间（是指从作业提交到作业完成所经历的时间）

等待时间（进程处于等处理器状态时间之和）

响应时间（指从用户提交请求到系统首次产生响应所需的时间）

12. 典型的调度算法优缺点？

先来先服务(FCFS)：是一种最简单的调度算法，即可用于作业调度，也可用于进程调度。按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度。算法简单，但效率低。比较有利于长作业，而不利于短作业。有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

短作业优先调度算法（SJF）是从队列中选出一个估计运行时间最短的作业优先调度，即可用于作业调度，也可用于进程调度。对长作业不利。严重的是，若一长作业进入系统的后备队列，由于调度程序总是优先调度那些短作业，将导致长作业长期不被调度——饥饿 。完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理 。由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

非抢占式和可抢占式高优先级调度算法

静态优先权是在创建进程时确定，且在进程的整个运行期间保持不变。

动态优先权是在进程运行过程中根据进程的情况变化的动态调整优先级。

高响应比优先调度算法：既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。优点是等待时间相同的作业，则要求服务的时间愈短，其优先权愈高，对短作业有利。要求服务的时间相同的作业，则等待时间愈长，其优先权愈高，是先来先服务。长作业优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机，对长作业有利。是一种折中，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。 缺点：要进行响应比计算，增加了系统开销

简单的时间片轮转法：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片；当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首；时间片的大小从几ms到几百ms

缺点：紧迫任务响应慢。 时间片选取 太小，会频繁发生中断、进程上下文切换，增加系统开销，但利于短作业。太大，退化成FCFS 。

13.为什么说多级反馈队列能够较好的满足要求？

对于终端型用户来说，提交的大多数都是较小的交互型，通常可在第一队列规定的时间片内让其完成工作，使终端型用户都感到满意；对短批处理作业用户来说，在第一队列执行一个时间片或至多只在第二队列和第三队列各执行一个时间片即可完成，周转时间仍然很短。对长批处理作业用户，只要将作业依次在第1,2…n队列中运行 ，然后按轮转方式运行，用户不必担心作业长期得不到处理。

1.什么是进程的同步与互斥？什么是临界资源？什么是临界区？临界资源的访问过程有哪些？

进程互斥：也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问此临界资源。

进程同步：也称相互制约关系，指多个相关进程在协调他们的工作次序上而产生的制约关系。

临界资源是在一段时间内，只允许一个进程访问的资源。每个进程中访问临界资源的那段程序称为临界区。

临界资源的访问过程分为四个部分。进入区，临界区，退出区，剩余区。

2.简述信号量S的物理含义。

S＞0时，S表示可使用的资源数；或表示可使用资源的进程数；S＝0时，表示无资源可供使用；或表示不允许进程再进入临界区；S＜0时，－S表示等待使用资源的进程个数；或表示等待进入临界区的进程个数；当S＞0时，调用P（S）的进程不会等待；调用V（S）后使可用资源数加1或使可用资源的进程数加1；

当S＜0时，调用P（S）的进程必须等待；调用V（S）后将释放一个等待使用资源者或释放一个等待进入临界区者。

3.什么是管程？管程的组成部分？基本特性？为什么引入？

管程是一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块

1） 局部与管程的共享结构数据说明

2） 对该数据结构进行操作的一组过程

3） 对局部于管程的共享数据设置初始值的语句

管程的基本特性

1）局部于管程的数据只能被局部于管程内的过程访问。

2）一个进程只有通过调用管程内的过程才能进入管程访问共享数据。

3）每次仅允许一个进程在管程内执行某个内部过程。

解决临界区分散所带来的管理和控制问题。

4. 什么是死锁?死锁的四个必要条件是什么?以及原因？

死锁是指多个进程由于竞争资源而造成的一种僵局（互相等待），若无外力作用，它们都将无法推进下去。

原因：系统资源的竞争和进程推进顺序非法。

必要条件：互斥条件，不剥夺条件，请求和保持条件，循环等待条件。

进程对所分配到的资源进行排它性的使用，即在一段时间内某资源仅为一个进程使用

进程已获得的资源在未使用完之前不能被剥夺

进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有

在发生死锁时，必然存在一个进程资源的循环等待链，已获得的资源被下一个进程所请求。5.简述解决死锁问题的三种方法。

① 死锁的预防。系统按预定的策略为进程分配资源，这些分配策略能使死锁的四个必要条件之一不成立，从而使系统不产生死锁。

② 死锁的避免。系统动态地测试资源分配情况，仅当能确保系统安全时才给进程分配资源。

（安全状态是指系统能按某种进程推进顺序，为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺序的完成）

③ 死锁的检测与解除。对资源的申请和分配不加限制，只要有剩余的资源就呆把资源分配给申请者，操作系统要定时判断系统是否出现了死锁，当有死锁发生时设法解除死锁。

6.死锁的预防四个方法？

破坏互斥条件：允许系统资源都能共享使用。

破坏不剥夺条件：当一个以已保持了某些不可剥夺资源的进程，请求新的资源时得不到满足，必须释放已经保持的所有资源，待以后需要时再重新申请。

破坏请求和保持条件：使用预先静态分配方法， 即进程在运行前一次申请完他所需要的全部资源，在他的资源未满足前，不把它投入运行。一旦运行后，这些资源就一直归它所有，也不再提出其他资源请求，不会发生死锁，但是系统资源严重浪费，而且还会导致“饥饿”现象。

破坏循环等待条件：使用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。

7.死锁的解除有几种方法？

资源剥夺法。 挂起某些死锁进程， 并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源时，而处于资源匮乏的状态。

进程撤销法。强制撤销一个或一部分进程并剥夺这些进程的资源。撤销的原则可以按进程的优先级和撤销进程代价的高低进行。

进程回退法。让一个或多个进程回退到足以回避死锁的地步，进程回退时资源释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

8.同步机制应遵循哪些准则？

空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程进入临界区。

忙则等待：当已有进程进入临界区，其他试图进入临界区的进程必须等待。

有限等待：对请求访问的进程，应保证能在有限时间内进入临界区。

让权等待：当进程不能进入临界区时应立即释放处理机，防止进程忙等待。

9.何谓用户级线程和内核支持线程？有有什么区别？

答：（1）用户级线程：仅存在于用户空间中的线程，无须内核支持。

（2）内核支持线程：在内核支持下运行的线程。

系统型线程依赖内核；用户型线程不依赖内核。

系统型线程是由操作系统内核完成创建和撤销的线程；用户型线程是由应用程序利用线程库提供创建，同步，调度和管理线程函数来控制的线程。

当一个系统型线程因I/O操作阻塞时，不会影响其他进程的运行；由于操作系统不了解用户级线程的存在，所以当一个线程阻塞时，整个进程必须等待。

存储管理

1.在虚拟段式存储系统中，引入了段的动态连接。

a 试说明为什么引入段的动态链接。

b 请给出动态连接的一种实现方法。

(1)在程序运行之前,先将各目标模块及它们所需的库函数链接成一个完整的可执行程序， 以后不再拆开。称为静态链接。静态链接常常因为目标模块个数多而花费大量的 CPU时间，而实际运行时又常常只用到其中的部分模块，因而也造成了存储空间的浪费。动态链接是作业运行时先装入主程序，运行过程中需要某模块时，再将该模块的目标程序调入内存并进行链接，它克服了静态链接的不足。

(2) 分段存储管理就是最典型的动态链接。分段管理允许用户将作业按逻辑关系进行自然分段 ,各段的大小可以不同。逻辑段内的地址是由两部分组成的 (s: 段号 ,d ：段内位移量 ), 即分段地址空间是用户定义的二维空间。 内存分配以段为单位 , 段可以在作业运行过程中根据请求而动态链接和装入。

2.何为静态链接？何谓装入时动态链接和运行时动态链接？

静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。

装入时动态链接：将用户源程序编译后所得到的一组目标模块，再装入内存时，采用边装入变链接的方式。

运行时动态链接 ：对某些目标模块的连接，是在程序执行中需要该目标模块时，才对她进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

3.绝对装入方式？

绝对装入 ：在编译时，如果知道程序将驻留在内存的某个位置，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际地址完全相同，故不需对程序和数据的地址进行修改。绝对装入方式只适用于单道程序环境。另外，程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。

4.为什么要引入动态重定位？如何实现？

答：静态重定位是地址变换在链接装入时一次完成的，但它要求连续的一片区域，且重定位后不能移动，不利于内存空间的有效使用，所以要引入动态重定位。动态重定位是在程序运行过程中要访问数据时再进行逻辑地址与物理地址的变换它是靠硬件地址变换部分实现的，通常采用重定位寄存器等实现

5.什么是逻辑地址？什么是物理地址？逻辑地址空间与物理地址空间？什么是地址重定位？什么是碎片？

逻辑地址指由程序产生的与段相关的偏移地址部分。

物理地址是在存储器里以字节为单位存储信息，为正确地存放或取得信息，每一个字节

地址重定位：把逻辑地址转变为内存的物理地址的过程。在装入时对目标程序中指令和数据的修改过程。

逻辑地址空间：一个目标程序所限定的地址范围。

物理地址空间实质内存中物理单位的集合，它是地址转换的最终地址。

碎片是指内存中很多容量太小、无法被利用的空闲块。

6. 什么是覆盖技术？什么是交换？什么是换入和换出？

覆盖技术是指一个程序的若干程序段或几个程序的某些部分共享某一个存储空间。

交换的基本思想是：把处于等待状态的进程从内存移到辅存，把内存空间腾出来，这一过程又叫换出；把准备好竞争 CPU 运行的进程从辅存移到内存，这一过程又称为换入。

交换技术主要是在不同进程之间进行，而覆盖则用于同一个程序中。

7.覆盖技术与虚拟存储技术有何本质不同 ?交换技术与虚存中使用的调入 / 调出技术有何相同

覆盖技术与虚拟存储技术最本质的不同在于覆盖的程序段的最大长度要受到物理内存容量的限制 , 而虚拟存储器的最大长度不受物理内存容量的限制 , 只受计算机地址结构的限制。交换技术与虚存中使用的调入/调出技术的主要区别在于 : 交换技术换进换出整个进程, 因此一个进程的大小受物理存储器的限制 : 而虚存中使用的调入/调出技术在内存和外存之间来回传递的是存储页或存储段 , 而不是整个进程 , 从而使得进程的地址映射具有了更大的灵活性 , 且允许进程的大小比可用的物理存储空间大得多。

8.什么是虚拟存储器？虚拟存储器基本特征是什么?虚拟存储器的容量主要受到什么限制?试着举一例子？

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

基本特征：多次性（作业无需一次装入内存，分为多次调入内存运行），

对换性（作业运行时不必一直常驻内存，允许换入和换出。），

虚拟性（逻辑上扩充了容量，使用户看到的内存容量，远大于实际的内存容量。）

虚拟存储器的容量与物理主存大小无关，而受限于计算机的地址结构。

例如在请求分页存储管理系统中，用户作业的所有页面并不一定都在实存，在作业运行过程中再请求调入所用的虚页。为了实现从逻辑地址空间到物理地址空间的变换，在硬件上必须提供一套地址变换机构 , 动态地址变换机构自动地将所有的逻辑地址划分为页号和页内地址两部分，并利用页表将页号代之以块号，把块号和页内地址拼接就得到了内存的物理地址 , 从而实现了虚拟存储器。

7. 简述固定分区和可变分区在管理方式上的区别？和优缺点 ？

答：单一连续分配方式:将内存分为系统区和用户区，系统区供操作系统使用，用户区供用户使用，是最简单的一种存储方式，但只能用于单用户单任务的操作系统中

固定分区是一种最简单的多道程序存储管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术使用内存空间。主存利用率低，当程序小于固定分区大小时，也占用了一个完整的内存空间，会有内部碎片。

可变分区是一种动态划分内存的分区方法。不预先将内存划分，而是在作业装入内存时，根据作业的大小动态的建立分区，并使分区的大小正好适合作业的需要。分区的大小数目可变

引入可变分区方法，使内存分配有较大的灵活性，也提高了内存利用率。但是可变分区会引起碎片的产生。

9.分区存储管理中常采用哪些分配策略？比较它们的优缺点

分区存储管理中常采用的分配策略有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法。
首次适应算法的优缺点：保留了高址部分的大空闲区，有利于后到来的大型作业的分配；低址部分不断被划分，留下许多难以利用的、小的空闲区，且每次分区分配查找时都是从低址部分开始，会增加查找时的系统开销。
循环首次适应算法的优缺点：使内存中的空闲分区分布得更为均匀，减少了查找时的系统开销；缺乏大的空闲分区，从而导致不能装入大型作业。
最佳适应算法的优缺点：每次分配给文件的都是最适合该文件大小的分区；内存中留下许多难以利用的小的空闲区。
最坏适应算法的优缺点：给文件分配分区后剩下的的空闲区不至于太小，产生碎片的几率最小，对中小型文件分配分区操作有利；使存储器中缺乏大的空闲区，对大型文件的分区分配不利。

10.分段和分页的主要区别是什么 ?

页是信息的物理单位；而段是信息的逻辑单位；

页的大小固定且由系统决定；而段的长度却不固定，段含有一组意义相对完整的信息，决定于用户所编写的程序。

分页的作业地址空间是一维的；而分段的作业地址空间是二维的。

分页是出于系统管理的需要，分段是为了满足用户的需要

分页中有内碎片，无外碎片。分段无内碎片，有外碎片。

11.为什么说分段系统较之分页系统更易于实现信息共享和保护?

a.对于分页系统，每个页面是分散存储的，为了实现信息共享和保护，则页面之间需要一一对应起来，为此需要建立大量的页表项；

b.而对于分段系统，每个段都从0开始编址，并采用一段连续的地址空间，这样在实现共享和保护时，只需为所要共享和保护的程序设置一个段表项，将其中的基址与内存地址一一对应起来即可。

12.何为页表和快表？它们各起什么作用？

页表指出逻辑地址中的页号与所占主存块号的对应关系。快表是具有并行查找能力的高速缓冲存储器，又称联想寄存器 TLB ，用以存放当前访问的若干页表项。

作用：页式存储管理在用动态重定位方式装入作业时，要利用页表做地址转换工作。

由于采用页表做地址转换，读写内存数据时CPU要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

补充：段页式存储器管理存取一次数据须经过3次对内存的访问？

首先通过段表查到页表起始地址，然后通过页表找到帧号，最后形成物理地址。

13.在有快表的情况下地址转换过程？

在具有快表的分页机制中，地址的变换过程：CPU 给出有效地址后，由硬件进行地址转换，并将页号送入高速缓存寄存器，并将此页号与快表中的所有页号同时进行比较。

如果有找到匹配的页号，说明索要访问的页表项在快表中，则可以直接从中读出该页对应的页框号，送到屋里地址寄存器。这样存取数据可以直接一次访存实现。

如果没有找到，则需要访问主存中的页表，在读出页表项后，应同时将其存入快表中， 以供后面可能的再次访问。但是如果快表已满，就必须按照一定的算法对其中旧的页表项进行替换。 注意，有些处理器设计为快表和主存同时查找，如果在快表中匹配成功则终止主存中的查找

13.虚拟存储器的基本特征是什么?虚拟存储器的容量主要受到什么限制?

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

基本特征：多次性（作业无需一次装入内存，分为多次调入内存运行），

对换性（作业运行时不必一直常驻内存，允许换入和换出。），

虚拟性（逻辑上扩充了容量，使用户看到的内存容量，远大于实际的内存容量。）

虚拟存储器的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。

14.请求页式存储管理的优缺点

答：优点：

(1)虚存量大，适合多道程序运行，用户不必担心内存不够的调度操作。动态页式管理提供了内存与外存统一管理的虚存实现方式。

(2)内存利用率高，不常用的页面尽量不留在内存。

(3)不要求作业连续存放，有效地解决了“碎片”问题。与分区式比，不需移动作业；与多重分区比，无零星碎片产生。注：分区式分配包括:固定式分配,可变分区分配,可重定位分区分配和多重分区分配四种。

缺点：

(1)要处理页面中断、缺页中断处理等，系统开销较大。

(2)有可能产生“抖动”。注：刚刚换出的页面马上又换入内存，刚刚换入的页面马上又换出内存，这种频繁的调度行为叫做抖动

(3)地址变换机构复杂，为提高速度采用硬件实现，增加了机器成本。

15.什么是缺页中断？缺页中断之后需要怎么处理？与一般的中断有什么区别？

在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。

过程：缺页中断处理程序根据页面在外存的位置将其调入内存。在此过程中，内存中如果有空闲空间，则缺页中断处理程序会将该页面调入任一空闲存储快，还需对页表的其他表项做修改，如物理块号等。如果没有空闲空间，必须淘汰某些页面，如果被淘汰的页面之前被修改过，要将其写回内存。

区别：在指令执行期间产生和处理中断信号，而非一条指令执行完后。一条指令在执行期间，可能产生多次缺页中断。

16 试说明改进型Clock置换算法的基本原理。

基本原理：在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它写回磁盘上。在改进型算法中，除需考虑页面的使用情况外，还须再增加一个因素，即置换代价，这样，选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。

17.什么是抖动？引起抖动的原因有哪些？

刚刚换出的页面马上又换入内存，刚刚换入的页面马上又换出内存，这种频繁的调度行为叫做抖动。产生抖动的原因是由于CPU的利用率和多道程序度的对立统一矛盾关系引起的，为了提高CPU利用率，可提高多道程序度，但单纯提高多道程序度又会造成缺页率的急剧上升，导致CPU的利用率下降，而系统的调度程序又会为了提高CPU利用率而继续提高多道程序度，形成恶性循环，我们称这时的进程是处于"抖动"状态。

18. 什么是固定分配局部置换 ，可变分配全局置换，可变分配局部置换？

固定分配局部置换它为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发现缺页，则只能从该进程在内存的页面中选出一个换出，然后再调入需要的页面。实现这种策略难以确定为每个进程应分配的物理块数量： 太少会频繁出现缺页中断， 太多又会使 CPU和其他资源利用率下降。

可变分配全局置换 。这是最易于实现的物理块分配和置换策略，为系统中的每个进程分配一定数量的物理块，操作系统自身也保持一个空闲物理块队列。当某进程发现缺页时，系统从空闲物理块队列中取出物理块分配给该进程，并将于调入的页装入其中。

可变分配局部置换 。它为每个进程分配一定数目的物理块，当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其他进程的运行。如果进程在运行中频繁的换页，系统需再为该进程分配若干附加物理块，直至该进程缺页率趋于适当程度为止；反之，若一个进程在运行过程中缺页率特别低，则此时可适当减少该进程的物理块。

19.什么是预调页策略，请求调页策略？

预调页策略。根据局部性原理，一次调入若干个相邻的页可能比一次调入一页更高效。但如果调入的一批页面中大厦多数都未被访问，则又是低效的。所以就需要采用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存。 但目前预调页的成功率仅约 50% 。股这种策略主要用于进程的首次调入时，有程序员指出应该先调入哪些页。

请求调页策略。进程在运行中需要访问的页面不在内存而提出的请求，由系统将所需页面调入内存。这种策略调入的页一定会被访问，且这种策略比较易于实现，故在目前的虚拟存储器中大多采用此策略。它的缺点在于每次调入一页，会花费过多的 IO 开销。

20.什么是分段的共享和保护？

分段的共享通过共享段来实现，每一个表项都是共享段的信息，记录了共享此段的每个进程情况。

分段的保护越界检查：短号超过段表长度或段内偏移超过段长时越界中断处理。存取控制检查：段表项中存取控制字段规定了对该段的访问方式，比如只读、读写等。环保护机构：一个程序可以访问驻留在相同环或较高特权环中的数据；一个程序可以调用驻留在相同环或较高特权环中的服务。

文件管理

1.对目录管理的主要要求是什么？

实现“按名存取”；提高对目录的检索速度；文件共享；允许文件重名。

2.什么是按名存取？

按名存取即用户不必考虑文件存储在哪里，怎样组织输入、输出等工作，只要使用文件名，操作系统通过查找目录，就能对存储介质上的信息进行相应的操作。

3.什么是绝对路径和相对路径名和索引节点

绝对路径：从根目录出发的路径。

相对路径：进程对各文件的访问都是相对于当前目录进行的。

索引节点：在检索文件时只用到文件名，也就是说，在检索目录的时，文件的其他信息时不会被用到的，也不会被调入内存。因此有些系统采用了文件名和文件描述信息分开的方法，将文件的描述信息单独形成一个索引节点。

磁盘高速缓存是利用内存中的部分存储空间来暂存从磁盘中读出的盘快内容。物理上是驻留在内存的盘快，逻辑上属于磁盘。

4.什么是文件？什么是文件系统？基本操作有哪些？

文件是以计算机硬盘为载体存储在计算机的信息的集合，文件可以是文本文档，图片，程序等等。操作系统负责管理和存储文件信息的软件机构成为文件管理系统，简称文件系统。文件系统由三部分组成：与文件管理有关软件，被管理文件以及实施文件管理所需的数据结构。

最基本的文件操作包括创建文件，删除文件，读文件，写文件，截断文件，文件重定位

文件重定位：按某条件搜索目录，将当前文件位置设为给定值，并且不会读写文件。

截断文件：允许文件所有属性不变，并删除文件内容，即将长度设为0并释放空间。

补充：记录是一组相关的数据项集合，用于描述一个对象在某方面的属性， 如一个考生报名记录包括考生姓名、 出生日期、报考学校代号、身份证号等一系列域。

5. 为什么在大多数OS中都引入”打开“这一文件系统调用？打开的含义是什么？

当用户要求对一个文件实施多次读/写或者其他操作时，每次都要从检索目录开始。为了避免多次重复检索目录，在大多数OS中都引入了”打开“这一文件系统调用，当用户第一次请求对某文件进行操作时，须先利用open系统调用将该文件打开。所谓”打开“，是指系统将指名文件的属性（包括该文件在外存上的物理位置），从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称索引号）返回给用户。换而言之，”打开“，就是在用户和指定文件之间建立起一个连接。此后，用户通过该连接直接得到文件信息，从而避免了再次通过目录检索文件，即当用户再次向系统发出文件操作请求时，系统根据用户提供的索引号可以直接在打开文件表中查找到文件信息。这样不仅节省了大量的检索开销，也显著提高了对文件的操作速度。如果用户已不再想要对该文件实施相应的操作，可利用”关闭“系统调用来关闭此文件，即断开此连接，OS将会把该文件从打开文件表中的表目上删除掉。

6. 什么是文件的逻辑组织和物理组织？文件的逻辑结构有几种形式？

文件的逻辑结构是从用户的观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于物理特性。文件的物理结构， 又称为文件的存储结构， 是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所在外存的分配方式有关。按逻辑结构，文件有无结构文件和有结构文件两种类型，文件的有结构文件有顺序文件、索引文件、索引顺序文件，散列文件。

7.什么是FCB？为什么引入FCB？

为了能对一个文件进行正确的存取，操作系统必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块（FCB）”。为实现目录管理，操作系统中引入了文件控制块的数据结构。

8.简述文件的二级目录组织形式。欲实现文件共享如何处理？

把记录文件的目录分成主文件目录和由其主管的若干个子目录，各子目录的位置由主目录中的一项指出。应用中常设一个主文件目录，而为系统中每一个用户设立一张主文件目录MFD，每个用户的所有文件均设立一个用户文件目录UFD，作为MFD中的一项。用以描述UFD的文件名和物理位置，即UFD是用户全部文件的文件控制块的全体。
在二级文件目录中，欲共享文件需给出一个文件的全路径名。由系统从根目录开始检索；或者用户将其当前目录指向另一用户的子目录上，以实现共享访问。

9.文件目录和目录文件各起什麽作用？目前广泛采用的目录结构形式是哪种？它有什麽优点？

文件目录记录文件的名字、文件长度、文件存放在外存上的物理地址，以及文件属性和文件建立时间、日期等信息也称之为文件控制块。目录文件是文件系统把同一卷上的若干文件的文件目录组成一个独立的文件，这个全部由文件目录组成的文件称目录文件。文件目录和目录文件是两个不同的概念，文件目录记录文件的管理信息，它用于对单个文件的控制；目录文件是由全部文件目录组成的文件，它用于整个文件系统的管理。目前广泛采用的目录结构是树形目录结构，它的主要优点是：检索效率高，允许文件重名，确切反映了信息的层次结构，并且可以利用层次结构实现文件共享和保护

10.文件物理结构中的顺序结构、链接结构与索引结构三者之间相比各有什么优缺点？

顺序结构优点：存储管理简单，且容易实现。支持顺序存取和随机存取。顺序存取速度快。所需的磁盘寻道次数和寻道时间最少。缺点不利于文件的动态增长，需要为每个文件预留连续的空间以满足文件动态增长。

链式结构优点是提高了磁盘利用率，不需要为每个文件预留物理块。有利于文件插入和删除。有利于文件动态增长。缺点存取速度慢，不适于随机存取，当物理块间的连接指针出错时，数据丢失。更多的寻道次数和寻道时间。链接指针占用一定的空间，降低了空间利用率。

索引结构优点是不需要为每个文件预留物理块。既能顺序存取，又能随机存取。满足了文件动态增长需要。

缺点较多的寻道次数和寻道时间。索引表本身带来了系统开销。如内存空间，存取时间等

11.在磁盘上进行一次读写操作需要那几部分时间？其中哪部分时间最长？

寻道时间：磁头移动到指定磁道所需要的时间

延迟时间：磁头定位到某磁道的扇区（块号）所需要的时间

传输时间：从磁盘读出或向磁盘写入数据所需要的时间。

一般来说，寻道时间因为要移动磁臂，所以占用时间最长。

12.FCFS，SSTF，SCAN，C-SCAN算法的优缺点

FCFS–优点：公平，简单 缺点：平均寻道时间长，仅应用在磁盘I/O较少的场合

SSTF—优点：性能比“先来先服务”好，减少了平均寻道时间 缺点：不能保证平均寻道时间最短，可能会出现 “饥饿”现象

SCAN—优点：寻道性能较好，可避免“饥饿”现象。缺点：不利于远离磁头一端的访问请求

C-SCAN-优点：消除了两端磁道请求的不公平。缺点：无

13.文件保护？

文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令保护和加密保护是为了方式用户文件被他人存取或盗取，而访问控制则用于控制用户对文件的访问方式

解决访问控制最常用的方法是根据用户身份进行控制。最普通的方法是为每个文件和目录增加一个访问控制列表，以规定每个用户名及其所允许访问的类型。这种方法的优点是可以使用复杂的访问方法。其缺点是长度无法预期并且可能导致复杂的空间管理，使用精简的访问列表可以解决这个问题。

精简的访问列表采用拥有者、组合其他三种用户类型。

1）拥有者：创建文件的用户。

2）组：一组需要共享文件且具有类似访问的用户。

3）其他：系统内的所有其他用户。

设备管理

1.设备管理的目标和功能是什么？

设备管理的目标：
(1) 向用户提供外部设备的方便、统一的接口，控制设备工作，完成用户的输入输出请求；
(2) 充分利用中断技术、通道技术和缓冲技术，提高CPU与设备、设备与设备之间的并行工作能力，以充分利用设备资源，提高外部设备的使用效率；
(3) 设备管理就是要保证在多道程序环境下，当多个进程竞争使用设备时，按照一定的策略分配和管理设备，以使系统能有条不紊地工作。
设备管理的功能：
(1) 设备分配和回收；
(2 )管理输入/输出缓冲区；
(3) 设备驱动，实现物理I/O操作；
(4) 外部设备中断处理；
(5) 虚拟设备及其实现。

2.什么是块设备？什么是字符设备？

块设备由于信息的存取总是以数据块为单位，所以存储信息的设备称为块设备。它属于有结构设备，如磁盘等。磁盘设备的基本特征是传输速率高，以及可寻址，即对它可随机地读写任意块。

用于数据输入输出的设备为字符设备，因为其传输的基本单位是字符。它属于无结构类型，如打印机等。他们的传输速率低、不可寻址、并且在输入输出时常采用中断驱动方式。

3.程序直接控制方式、I/O中断方式

（1）程序直接控制方式。其特点是主机与I/O串行工作。CPU启动I/O后，时刻查询I/O是否准备好，若设备准备就绪，CPU便转入处理I/O与主机间传送信息的程序；若设备未做好准备，则CPU反复查询，“踏步”等待直到I/O准备就绪为止。可见这种方式CPU效率很低

（2）程序中断方式。其特点是主机与I/O并行工作。CPU启动I/O后，不必时刻查询I/O是否准备好，而是继续执行程序，当I/O准备就绪时。向CPU发中断请求信号，CPU在适当时候响应I/O的中断请求，暂停现行程序为I/O服务。这种方式消除了“踏步”现象，提高了CPU效率

4.什么是通道？与DMA方式有什么区别？

通道是专门负责输入/输出的处理机。进一步减少对CPU 的干预，即把对一个数据块的读或写为单位的干预，减少为对一组数据块的读或写及有关的控制和管理为单位的干预。同时，又可以实现 CPU 、通道和 IO 设备三者的并行操作，从而更有效的提高整个系统的资源利用率。

IO 通道和一般处理器的区别是：通道指令的类型单一，没有自己的内存，通道所执行的通道程序释放在主机内存中的，也就是说通道与 CPU 共享内存。

（1）DMA方式是通过 DMA控制器控制总线，在设备和主存之间直接实现 I/O传送。；通道控制方式类似也是以内存为中心实现设备与主存直接交换数据的控制方式。

（2）通道控制方式通过执行通道程序进行 I/O 操作的管理。

（3）与DMA控制方式相比通道控制方式所需的CPU干预更少，而且DMA控制器通常只控制一台或多台同类的高速设备； 而通道可控制多台同类或不同类的设备。

5.什么是DMA方式? 它与中断控制方式的主要区别是什么?

DMA（直接存储器存取）是一种不经过CPU而直接从内存存取数据的数据交换模式.特点是传输的基本单位是数据块，所传送的数据，是从设备直接送入内存，或者相反。仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在DMA控制器的控制下完成的。

中断控制方式在每个数据传送完成后中断CPU，而DMA控制方式则是在所要求传送的一批数据全部传送结束时中断CPU。中断控制方式的数据传送在中断处理时由CPU控制完成，而DMA控制方式则是在DMA控制器的控制下完成。不过。在DMA控制方式中，数据传送的方向，存放数据的内存始址及传送数据的长度等仍然由CPU控制。中断控制方式以CPU为核心，DMA以存储器为核心。因此DMA方式能与CPU并行工作。DMA方式传输批量的数据，中断控制方式传输则以字节为单位。

6.设备驱动程序是什么?为什么要有设备驱动程序?写出设备驱动程序的处理过程?

设备驱动程序与硬件直接相关，负责具体实现系统对设备发出的操作命令，驱动I/O设备工作的驱动程序。是I/O进程与设备控制器之间的通信程序，常以进程的形式存在。

设备驱动程序是控制设备动作的核心模块，向上层用户程序提供一组接口，设备的具体区别被设备驱动程序封装，且处理用户进程发出的I/O请求，如read和write操作。

用户进程使用设备驱动程序时，设备驱动程序的处理过程为：将抽象的I/O请求转换为具体的请求，检查I/O请求的合法性，读出和检查设备的状态，传送必要的参数，设置设备工作方式，启动I/O设备。

7.什么是设备独立性？为什么引入？如何实现？

设备独立性是指应用程序独立于具体使用的物理设备。为了提高设备分配时的灵活性和设备的利用率、易于实现IO 重定向， 因此引入设备独立性。为了实现设备独立性，应引入逻辑设备和物理设备概念。在应用程序中使用逻辑设备名来请求使用某类设备，系统执行时是使用物理设备名。为了实现设备独立性，必须在驱动程序上设置一层设备独立性软件， 还需在系统中设置一张逻辑设备表（ LUT ），用于将逻辑设备名映射为物理设备名。 LUT 表项包括逻辑设备名、物理设备名和设备驱动程序入口地址；

8.引入缓冲技术（缓冲区）的主要目的？有哪几种？

缓和CPU与I/O设备速度不匹配的矛盾；减少对CPU的中断频率；提高CPU与I/O设备之间的并行性。根据系统设置缓冲区的个数分为单缓冲，双缓冲，循环缓冲以及缓冲池。

单：在设备和处理机之间设置一个缓冲区。设备和处理机交换数据时，先把被交换数据写入缓冲区，然后需要数据的设备或处理机从缓冲区取走数据。

双：双缓冲区机制又称缓冲对换。I/O设备输入数据时先输入到缓冲区 1，直到缓冲区 1 满后才输入到缓冲区 2，此时操作系统可以从缓冲区 1 中取出数据放入用户进程处理，并由 CPU 计算。双缓冲的使用提高了处理机和输入设备的并行操作的程度。

循环：包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区，最后一个缓冲区指针指向第一个缓冲区，多个缓冲区构成一个环形。

缓冲池：由多个系统共用的缓冲区组成，缓冲区按其使用状况可以形成三个队列：空缓冲队列、装满输入数据的缓冲队列（输入队列）和装满输出数据的缓冲队列（输出队列）。还应具有四种缓冲区：用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区、用于收容输出数据

的工作缓冲区、用于提取输出数据的工作缓冲区。

9.设备分配的总原则是什么？设备分配时应考虑的因素有哪些？分配方式有哪两种？

既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开。（1）I/O设备的固有属性（2）I/O设备的分配算法（3）I/O设备分配的安全性（4）I/O设备的独立性

静态分配：主要用于独占设备的分配，它在用户作业开始执行前，由系统一次性分配该作业所要求的全部设备，控制器（如通道等）。一旦分配后，就一直为该作业所占有，直到作业被撤销。静态分配虽然不会出现死锁，但设备的使用效率低。

动态分配：是在进程执行过程根据执行需要进行。当进程需要设备时，通过系统调用命令向系统提出设备请求，由系统按照事先规定的策略给进程分配所需要的设备，I/O控制器，一旦用完后，便立即释放。有利于提高设备的利用率。可能会进程死锁。

10.用于设备分配的数据结构有哪些？他们之间的关系是什么？

用于设备分配的数据结构有系统设备表(SDT)、设备控制表(DCT)、控制器控制表(COCT)和通道控制表(CHCT)。SDT整个系统中只有一张记录系统中全部设备的情况，是系统范围的数据结构。每个设备有一张DCT，系统为每一个设备配置一张DCT以记录本设备的情况。每个控制器有一张COCT，系统为每一个控制器都设置一张用于记录本控制器情况的COCT。系统为每个通道配置一张CHCT，以记录通道情况。SDT中有一个DCT指针，DCT中有一个COCT指针，COCT中有一个CHCT指针。

11.为什么引入SPOOLing技术？什么是 SPOOLing技术？什么是SPOOLing系统？其系统由什么组成？它的功能与特点是什么？

答：为了缓和CPU的高速性和I/O设备低速性之间的矛盾。SPOOLing技术是是一种外围设备同时联机操作技术,是操作系统采用的一种将独占设备改造为共享设备的技术。它是关于慢速字符设备如何与计算机主机交换信息的一种技术，又亦称为假脱机操作。

SPOOLing系统是指在通道技术和中断技术的支持下，在主机的控制之下，完成 I/O的软件系统。其系统组成：输入井和输出井；输入缓冲区和输出缓冲区；输入进程和输出进程

在磁盘上的两个存储空间，输入井模拟脱机输入时的磁盘，暂存I/O设备输入的数据，输出井模拟脱机输出时的磁盘，暂存用户程序输出的数据。

输入缓冲区用于暂存由输入设备送来的数据，以后在传送到输入出缓冲区用于暂存从输出井送来的数据，以后再传送给输出设备。

输入进程模拟脱机输入时的外围控制机；输出进程模拟脱机输出时的外围控制机

功能与特点：提高了I/O的速度；将独占设备改造为共享设备；实现了虚拟设备功能。

12.SPOOLing技术如何使一台打印机虚拟成多台打印机？优点是？（对用户）

（1）系统对于用户的打印输出，并不真正把打印机分配给该用户进程，而是由输出进程在输出井中申请一个空闲磁盘块区，并将要打印的数据送入其中。

（2）输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入，再将该表挂到请求打印队列上。

（3）若打印机空闲，输出程序从请求打印队列队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。

优点是在多用户情况下，每一个用户使用打印机就好象自己拥有一台打印机。不会产生打印机“忙”而等待。

13.什么是独享设备？共享设备？设备分配技术？设备管理的主要功能？

独享设备：即不能共享的设备， 一段时间只能由一个作业独占。 如打印机。

共享设备：可由若干作业同时共享的设备， 如磁盘机等

设备分配技术主要有： 独占分配、 共享分配和虚拟分配。 独占分配适用于独占设备，系统效率低；共享分配适用于高速、大容量直接存储的共享设备，设备的利用率较高； 虚拟分配技术利用共享设备去实现独占设备的功能， 从而使独占设备“感觉上”成为可共享的、快速的 I/O 设备。设备管理的主要功能包括 实现外围设备的分配与回收 、 实现虚拟设备 和 实现对磁盘的驱动调度 。

数据结构

1.逻辑结构和物理结构

逻辑结构是元素之间的逻辑关系。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构。集合，树，图是典型的非线性结构。

存储结构是指数据结构在计算机中的表示，也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储，链式存储，索引存储和散列存储。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，元素之间的关系由存储单元的邻接关系来体现。优点：可以随机存取，每个元素占用最少的存储空间。缺点：只能使用相邻的一整块存储单元，可能产生较多的外部碎片。

链接存储：不要求逻辑上相邻的单元在物理上也相邻。借助指示元素存储地址的指针表示元素之间的逻辑关系。优点：不会出现碎片现象，充分利用所有存储单元。缺点：每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。

索引存储：在存储信息的同时，还建立其附加的索引表。索引表的每一项成为索引项，索引项的一般形式是：（关键词，地址）。其优点是检索速度快，缺点是增加了附加的索引表，占用较多的存储空间。在删除和增加数据时要修改索引表，会花费较多的时间。

散列存储：根据元素的关键字直接计算出该元素的存储地址，也称HASH存储。优点是检索，增加，删除节点的速度都很快。缺点：如果散列函数不好可能会出现元素存储单元的冲突，解决冲突需要增加时间和空间开销

数据的运算指施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构：指出运算的功能，运算的实现是针对存储结构：指出运算的具体步骤。

2.什么是算法？有几个特性？目标是什么？

算法是对特定问题求解步骤的一种描述。

1.有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷的时间内完成。

2.确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。对于相同的输入只能产生相同的输出。

3.可行性：一个算法是可行的。算法中描述的操作都是可以通过已经实现的基本运算执行有限次实现。

4.输入：一个算法有零个或多个输入。输入取自于某个特定的对象的集合。

5.输出：一个算法有多个或一个输出。输出是同输入有着某种特定关系的量。

好的算法应该考虑如下目标1.正确性2.可读性3.健壮性：对输入非法数据，也要能做出适当反应或进行处理。4.效率于低存储量需求

Linux常用命令

进程管理

1. 操作系统的三个作用：

   1. 控制和管理计算机系统的软硬件资源
   2. 组织和调度计算机工作和资源分配
   3. 提供给用户和其他软件方便的接口和环境。

2. 层次结构：操作系统的各项功能分别设置再不同的层次上。一些与硬件关联比较紧密的模块，如时钟管理、中断管理等。上面的这两部分

3. 如果原语的原子性被破坏会被怎样？

   ​ 原语操作是指一个操作中的所有操作，要么成功完成，

4. 为什么要有系统调用？

5. 线程、管程和协程的区别。

   **协程：**是一种用户态的轻量级线程。协程的调度由用户控制，拥有自己独立的寄存器上下文和栈，协程切换的效率比线程还要高。

   协程和线程的区别：

   1. 线程由CPU调度，而协程由用户调度。
   2. 线程存在安全问题，而协程更为安全。
   3. 线程使用同步机制，而协程使用异步机制。

6. 进程调度是什么？

7. 优先级反转是什么？怎么解决优先级反转这个问题？

   解决办法：

   1. 优先级继承：让占用资源的低优先级任务的优先级提升到需要改]该资源的任务的优先级。
   2. 优先级天花板：申请某资源的任务的优先级提升到可能访问该资源的最大优先级(不释放CPU）。
   3. 两者区别：当只有一个任务访问资源时，没有区别；而优先级天花板，无论是否发生阻塞，都会提升，即拿到资源的任务的优先级都会提升至最高。

8. 介绍银行家算法。

内存管理

1. 存储器管理应具有的功能：
   1. 内存分配和回收
   2. 地址映射
   3. 内存保护
   4. 内存扩张：覆盖技术、交换技术、虚拟存储技术
2. 将用户程序变为可执行程序的过程：
   1. 编译：
   2. 链接：
   3. 装入
3. 内存管理有哪些方法？
4. 多级存储系统的作用：
   1. 从CPU看：整体速度接近于cache和寄存器的速度，容量是辅存的容量，每位价格接近辅存的价格。从而很好的解决了存储器中的速度、容量、价格三者之间的矛盾。
   2. 从存储层次看：在计算机系统中存储层次可分为高速缓冲存储器、主存、辅存三级。高速缓存用来解决CPU和主存速度不匹配的问题，辅存用来解决主存容量不足的问题。
5. 叙述clock置换算法。
6. 操作系统中表示内存已被占用的数据结构是什么？
7. CPU如何处理外部中断？

文件管理

1. 一个文件在磁盘上，怎么访问到该文件？

2. 磁盘调度的算法：FCFS、SSTF、SCAN、C-SCAN

3. 访问位A和修改位M可以组成一下四种类型的页面。

   1类(A =0, M = 0)：表示该页面最近既未被访问，又未被修改，是最佳淘汰页。

   2类(A =0, M = 1)：表示该页面最近未被访问，但已被修改，并不是很好的淘汰页。

   3类(A =1, M = 0)：表示该页面最近已被访问，但未被修改，该页有可能再被访问。

   4类(A =1, M = 1)：表示该页最近已被访问且被修改，该页可能再被访问。

   从指针所指示的当前位置开始，扫描循环队列，寻找第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A.

   如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0.

   如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始位置，并将所有访问位复0.返回第一步。

   ————————————————
   版权声明：本文为CSDN博主「Mirants」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
   原文链接：https://blog.csdn.net/u012432778/article/details/46519709

计算机网络

1. 什么是计算机网络？

   是指在地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路链接起来，在网络操作系统、网络管理软件及通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。

2. 网络的7/5/4层协议。

3. 网络每一层的作用。

4. 访问一个网络的过程：

   1. 利用DNS浏览器分析链接，指向页面URL，查询到网络对应的IP地址
   2. 浏览器与对应网络的服务器利用TCP建立连接
   3. 浏览器利用http的get方法向服务器发送资源请求
   4. web服务器发送回应信息
   5. TCP释放连接
   6. 浏览器解释回应信息，并以图形化的方式显示。

5. 浏览一个网页用到了哪些协议？

   1. 应用层：HTTP（www访问协议，实现了应用层浏览器客户端与web服务器之间会话与数据传输）、DNS
   2. 传输层：TCP（客户和服务器之间建立可靠的连接进行数据传输）
   3. 网络层：IP（进行路由选择和IP包传输）、ICMP（提供网络传输中的差错检验）、ARP（将目的IP地址转换成物理MAC地址）
   4. 数据链路层：
      1. 网络接口层：LLC子层（逻辑联络控制协议，实现点到点之间的可靠数据传输）
      2. MAC子层：介质访问控制协议，实现介质的有序访问。
   5. 端到端的通信和点到点之间的通信的区别。
   6. http1.0和http1.1的区别：
      1. http1.1是长连接的，在一个TCP连接上可以传送多个HTTP请求和响应，减少了建立和关闭连接的消耗和延迟。
      2. HTTP1.1的请求消息和响应消息都应支持Host头域，因为虚拟机技术导致了一个物理服务器有多个虚拟服务器。
      3. 带宽优化，允许一个对象的部分传输。
   7. 三次握手和四次挥手。

物理层

1. 虚电路
2. 非归零编码和归零编码的区别，曼彻斯特编码是归零编码还是?
3. 模拟数据–>数字信号：抽样、量化、编码

数据链路层

功能：为网络层提供服务、链路管理、帧定界、帧同步与透明传输、流量控制和差错控制。

1. 编码、信道的含义？

   信道一般是用来表示某一个方向传送信息的媒体。

2. 流量控制的常见方式。

3. 停止-等待协议、连续ARQ，选择重传机制。

4. 码分分多址、频分多址、时分多址、波分多址

5. RARP的作用，相应的协议是什么，以及地址解析过程。

6. 无线局域网WLAN的定义

7. 5G的特点，5G并不是那么热门。

8. 谈谈NAT技术，给定两台主机在不同的局域网，采用NAT技术怎么进行通信？

9. 集线器和交换机的不同。

10. MAC英文意思：Medium Access Control，译为媒体访问控制，或者物理地址，用于定义网络设备的位置。

11. MAC地址是用来做什么的？为什么还需要IP地址？

    MAC地址由网络设备制造商生产时写在硬件内部，与网络无关。路由器要知道每个MAC地址所在子网所需要的内存太大，故此需要IP地址。IP地址和地域有关，同一个子网的前缀是相同的，这样路由器只需要记住每个子网的位置即可。设备环境不同，他们使用不同的硬件地址，要让这些网络能够互相通信就需要非常复杂的硬件转换工作，让用户和用户主机来完成这项工作几乎不可能。

12. 有哪些路由选择算法：

    全局式路由选择算法、分散式路由选择算法。

13. 什么是蜂窝网？

    蜂窝网，又称移动网络，它属于一种移动通信硬件架构，分为模拟蜂窝网和数字蜂窝网两种。他是由于构成网络覆盖的各个通信基地台的信息覆盖呈六边形，从而使整个网络像一个蜂窝而得名。

14. 网关的作用：通过它可以访问外网。

15. ipconfig的作用：显示当前ip/tcp配置的信息。

16. 百度IP和电脑IP的区别。

17. IPV4和IPV6的区别。

18. 各个硬件：中继器（集线器）、网桥（交换机、数据链路层）、路由器

传输层

1. 多路复用：从源主机的不同套接字中收集数据块，并为每个数据块封装上首部信息（这将在多路分解时使用）从而生成报文段，然后将报文段传递到传输层的工作称为多路复用。

   多路分解：将运输层报文段中的数据交付到正确的套接字的工作称为多路分解。

2. 什么是流水线技术？

3. 怎么实现进程寻址：IP地址+端口号

4. 什么是套接字？

   进程通过一个叫套接字的软件接口，向网络发送报文和从网络接受报文。前提：套接字要有唯一的标识符，报文段要有特殊字段指示要交付到哪个套接字。

5. TCP的拥塞控制。

6. TCP的三次握手和四次挥手。

7. TCP的可靠性如何保证？

   • 校验和
   • 序列号
   • 确认应答
   • 超时重传
   • 连接管理
   • 流量控制
   • 拥塞控制

8. TCP对应的协议和UDP对应的协议。

   1. TCP对应的协议：
      1. FTP：文件传输协议，端口21
      2. Telnet：远程登陆
      3. SMTP：简单邮件传输，端口25
      4. POP3：用于接受文件
      5. HTTP：web服务器传输超文本到本地浏览器
   2. UDP协议：
      1. DNS：53端口
      2. SNMP：简单网络管理协议。用来管理网络设备。
      3. TFTP：简单文件传输协议。

应用层

1. 什么是B/S模式？

   B/S是Brower/Server的缩写。客户端只需要安装浏览器，服务器安装数据库。浏览器就可以通过web服务器与数据库交互。

2. C/S模式和B/S模式的区别：

3. Session和Token的区别：Session一般在cookie中传递，而token一般在header中。

4. cookie的原理。

5. DHCP协议的作用及过程。

   1. 作用：是应用层协议，使用C/S模式，客户端和服务端通过广播方式进行交互，基于UDP。DHCP提供提供即插即用联网的机制，主机可以从服务器动态获取IP地址、子网掩码、默认网关、DNS服务器名称与IP地址、允许地址重用，支持移动用户加入网络，支持在所用地址续租。

   2. 过程：

      1. 主机广播DHCP发现报文。

      2. DHCP服务器广播提供报文

      3. 主机广播请求报文

      4. 服务器广播确认报文

6. 设计web服务器。

7. http、https的区别。

   1、https协议需要到ca申请证书，一般免费证书较少，因而需要一定费用。

   2、http是超文本传输协议，信息是明文传输，https则是具有安全性的SSL加密传输协议。

   3、http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。

   4、http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。

8. 常见的http返回码。

9. http中get和post的区别。

   1. get是从服务器获取数据，post是向服务器传送数据。
   2. 最直观的区别就是GET把参数包含在URL中，POST通过request body传递参数。
   3. GET在浏览器回退时是无害的，而POST会再次提交请求。
   4. GET产生的URL地址可以被Bookmark，而POST不可以。
   5. GET请求会被浏览器主动cache，而POST不会，除非手动设置。
   6. GET请求只能进行url编码，而POST支持多种编码方式。
   7. GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。
   8. GET请求在URL中传送的参数是有长度限制的，而POST没有。
   9. 对参数的数据类型，GET只接受ASCII字符，而POST没有限制

10. 计网实验软件：wireshark

11. 防火墙的port防护：指的是通过防火墙的port开关设置，关闭一些非必须port，达到一定安全防护目的的行为。

12. 结合现实生活，说明计算机网络未来的发展趋势或应用：

    超高清视频、AR、VR、智能家居、远程医疗、智慧城市、智能制造、万物互联、万物智联

数据结构

树

前序、中序构造二叉树

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){int     i           = 0;int     iRootval    = 0;int     iLeftNum    = 0;int     iRightNum   = 0;struct TreeNode*     pTreeNode  = NULL;//1,结束条件if((0 == preorderSize) || (0 == inorderSize)) return NULL;if((NULL == preorder) || (NULL == inorder)) return NULL;if(preorderSize != inorderSize) return NULL;//2,初始化pTreeNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));memset(pTreeNode, 0x00, sizeof(struct TreeNode));iRootval = preorder[0];//3,计算左支节点数，右支节点数for(i = 0; i < inorderSize; i++){if(iRootval == inorder[i]){break;}iLeftNum += 1;}iRightNum = inorderSize - iLeftNum - 1;//4,递归处理左支、右支pTreeNode->val = iRootval;pTreeNode->left = buildTree(&preorder[1], iLeftNum, &inorder[0], iLeftNum);pTreeNode->right = buildTree(&preorder[1 + iLeftNum], iRightNum, &inorder[1 + iLeftNum], iRightNum);return pTreeNode;
}

中序、后序构造二叉树

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){int i = postorderSize - 1;int iRootval = postorder[i];int iLeftNum = 0, iRightNum = 0;struct TreeNode* pTreeNode = NULL;// 1.结束条件if (0 == inorderSize || 0 == postorderSize) return NULL;if (inorderSize != postorderSize) return NULL;if (postorder == NULL || inorder == NULL) return NULL;// 2.初始化pTreeNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));memset(pTreeNode, 0x00, sizeof(struct TreeNode));pTreeNode->val = iRootval;//return NULL;// 3.计算左右子树的节点数for ( ; i > 0; i--) {if (inorder[i] == iRootval)break;iRightNum++;}iLeftNum = inorderSize - iRightNum - 1;// 4. 递归左右子树pTreeNode->left = buildTree(&inorder[0], iLeftNum, &postorder[0], iLeftNum);pTreeNode->right = buildTree(&inorder[1 + iLeftNum], iRightNum, &postorder[0 + iLeftNum], iRightNum);return pTreeNode;
}

哈夫曼树

波兰式和逆波兰式

树的非递归遍历

中序遍历

void InOrder(BiTree T) {InitStack(S); BiTree p = T; // 初始化栈，p是遍历指针while(p || !IsEmpty(S)) {// 栈不空或者指针不空的时候循环if (p) { // 一路向左Push(S, p);p = p->left;} else {Pop(S, p); visit(p);p = p->rchild;}}
}

前序遍历

void PreOrder(BiTree T) {InitStack(S); BiTree p = T;while(p || !IsEmpty()) {if (p) {visit(p);p = p->left;} else {Pop(s,p);p = p->right;}}
}

后序遍历

void PostOrder(BiTree T) {InitStack(S); BiTree p = T, last = null; // last 表示最近访问的节点while(p || !IsEmpty()) {if (p) {p = p->left;Push(S, p);} else{Pop(S, p);if (p->rchild && p->rchild != last) { // 右子树存在且还未遍历右孩子Push(S, p);p = p->right;} else { visit(p);last = p; // 记录最近访问过的节点p = null; //访问过p需要回退}}// else }// while
}

完全二叉树节点的个数

int getDepth(struct TreeNode* root) {// 通过不断访问左子树获取完全二叉树的高度int depth = 0;while(root) {depth++;root = root->left;}return depth;
}int countNodes(struct TreeNode* root){// 利用二叉树的性质作题if (root == NULL) return 0;int ld = getDepth(root->left);int rd = getDepth(root->right);if (rd == ld) return (1 << ld) + countNodes(root->right); // 左子树是满二叉树， 1 << ld 是左子树加根节点的个数else return (1 << rd) + countNodes(root->left);
}

线索二叉树

存储结构：

typedef struct ThreadNode{int data;struct ThreadNode *lchild, *rchild;int ltag, rtag; // 0 表孩子， 1 表示线索
}ThreadNode, *ThreadTree;

中序遍历对二叉树进行线索化

void InThread(ThreadTree &p, ThreadTree &pre) {if (p) {InThread(p->lchild, pre); // 递归if (p->lchild == NULL) { // 左孩子线索化p->lchild = pre;p->ltag = 1;}if (pre && pre->rchild == NULL) { // 给前去节点建立右线索pre->rchild = p;pre->rtag = 1;}pre = p;InThread(p->rchild, pre);}// if
}
void CreatInThread(ThreadTree T) {ThreadTree pre = NULL;if (T) {InThread(T, pre);pre->rchild = NULL; // 处理最后一个节点pre->rtag = 1;}
}

中序线索二叉树的遍历

// 求中序的第一个顶点
ThreadNode *Firstnode(ThreadNode *p) {while(p->tag == 0) p = p->lchild;return p;
}
// 求节点p的后继
ThreadNode *Nextnode(ThreadNode *p) {if (p->rtag == 0) return Firstnode(p);else return p->rchild;
}
void Inorder(ThreadNode *T) {for (ThreadNode *p = Firstnode(T); p; p = Nextnode(p))visit(p);
}

打印值为x节点的所有祖先

非递归后序遍历

typedef struct{BiTree t;int tag; // 0表示左子树访问过， 1表示左右子树都访问过
}stack;
void Search(BiTree bt, int x) {stack s[MAX];top = 0;while(bt || top > 0) {while(bt && bt->data != x) { // 节点入栈s[++top].t = bt;s[top].tag = 0;bt = bt->lchild;}if (bt->data == x) { // 找到x节点for (int i = 1; i <= top; i++) printf("%d ", s[i].data);exit(1);}while(top != 0 && s[top].tag == 1) { // 左右子树都找过不是，退栈top--;}if (top != 0) { // 向右子树遍历s[top].tag = 1;bt = s[top].t->rchild;}}
}

递归

int func(BiTree bt, int x) {if (bt == null) return 0;if (bt->data == x) return 1;if (func(bt->lchild) || func(bt->rchild)){printf("%d ", bt->data);return 1;}return 0;
}

找指针p和q最近祖先

算法思想：不失一般性，设p在q左边。采用后序非递归遍历，则必先遍历p，此时栈中的元素均是p的祖先，将其存储到辅助栈中，然后再遍历q时，用栈中的节点依次和辅助栈中的节点去匹配，第一个即是最近祖先。

typedef struct{BiTree t;int tag; // 0表示左子树访问过， 1表示左右子树都访问过
}stack;
stack s[], s1[]; // 栈和辅助栈，空间足够大
BiTree Ancestor(BiTree root, BiNode* p, BiNode *q) {top = 0; bt = root;while(bt && top > 0) {while(bt) {s[++top] = bt;bt->tag = 0;bt = bt->lchild;}while(top != 0 && s[top].tag == 1) { // 左右子树都遍历完毕if (s[top].t == p) { // 先找到p，将栈中元素放进辅助栈中for (int i = 1; i <= top; i++) {s1[i] = s[i];}top1 = top;}if (s[top].t == q) { // 后找到qfor (int i = top; i ; i--) {for (int j = top1; j; j--) if (s[i].t == s1[j].t) // 找到最近祖先return s[i].t;}}//iftop--; // 不是二者的公共祖先，退栈}//whileif (top != 0) { // 遍历右子树s[top].t->tag = 1;bt = bt->rchild;}}//whilereturn null; // 没有公共祖先
}

二叉树转化为等价的中缀表达式（自己再推广下）

算法思想：采用中序遍历递归算法，除了根节点和叶节点外，遍历到其他节点时在遍历其左子树之前要加上坐括号，遍历其右子树之后要加右括号。

typedef struct node {char data[10];struct node *left, *right;
}BTree;
void BtreeToE(BTree *root) {BtreeToExp(root, 1); // 调用，根节点的高度是1
}
void BtreeToExp(Btree *root, int deep) {if (root == null) return ;if (root->lchild == null && root->rchild == null) {//叶子节点printf("%s",root->data); // 输出操作数，不加括号} else {if (deep > 1) printf("(") ; // 有子表达式BtreeToExp(root->lchild, deep + 1);printf("%s",root-data);BtreeToExp(root->rchild, deep + 1);if (deep > 1) printf(")");}
}

二叉排序树

插入操作：

int BST_Insert(BiTree &T, int k) {// 传引用，因为后面会改变的if (T == NULL) {T = (BiTree)malloc(sizeof(BSTNode));T->key = k;T->lchild = T->rchild = null;return 1;}if (T->key == k) return 0;if (T->key < k) {return BST_Insert(T->rchild, k);} else {return BST_Insert(T->lchild, k);}
}
// 构造二叉排序树
void Creat_BST(BiTree &T, int str[], int n) {T == null;int i = 0;while(i < n) {BST_Insert(T, str[i++]);}
}

判断是不是二叉排序树

int pre = -32767;
int JudgeBST(BiTree bt) {int b1, b2;if (bt == null) return 1;b1 = JudgeBST(bt->lchild);if (b1 == 0 || pre > bt->data) return 0;pre = bt->data; // 保存当前节点的值b2 = JudgeBST(bt->rchild);return b2; // 返回右子树的结果
}

图

图的遍历+生成树

存储结构

图的邻接矩阵：

#define MaxVertexNum 100 //顶点数目的最大值
typedef char Vertextype; // 顶点的数据类型
typedef int EdgeType; //带权图中边上的数据类型
typedef struct {char Vex[100]; //顶点表int Edge[100][100]; / 邻接矩阵，边表int vexnum, arcnum; //图的当前的定点数和弧数
}MGraph;

图的邻接表表示法：

typedef struct ArcNode{ // 边表节点int adjvec;			// 该弧所指向的顶点的位置struct ArcNode* next; // 指向下一条弧的指针
}ArcNode;
typedef sturct Vnode { // 顶点表节点char data; 		//顶点信息ArcNode *first; // 只想第一条依附该节点的弧的指针
}VNode, AdjList[100];
typedef struct {AdjList vertices; // 邻接表int vecnum, arcnum; //图的当前的定点数和弧数
}

广度优先搜索

bool visited[100];
void BFStraverse(Graph G) {for (int i = 0; i < G.vecnum; i++) visited[i] = false;InitQueue(Q);for (int i = 0; i < G.vecnum; i++) if (!visited[i])BFS(G, i);
}
void BFS(Graph, int v) {visit(v); //访问visited[v] = true;Enqueue(Q, v);while(!Empty(Q)) {DeQueue(Q, v);for (w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w)) {//检测v的所有邻接点if (!visited[w]) {visit[w];visited[w] = true;EnQueue(Q,w);}//if}//for}//while
}
/*
FirstNeighbor(G,v):返回顶点v的第一个邻接点,无则返回-1
NextNeighbor(G,v,w)：返回顶点v除w的下一个邻接点，无则返回-1
*/

广搜求单源最短路径

//d[i] 表示从u到i的最短路径
for(int i = 0; i < G.vecnum; i++) d[i] = MAX;
visited[u] = true; d[u] = 0;
EnQueue(Q, u);
while(!IsEmpty(Q)) {DeQueue(Q,u);for (w = FirstNighbor(G,u); w >= 0; w = NextNighbor(G, u, w)) {if(!visited[w]) {visited[w] = true;d[w] = d[u] + 1;EnQueue(Q, w);}// if }//for
}

深度优先搜索

bool visited[100];
void DFSTraverse(Graph G){for (v = 0; v < G.vexnum; v++) visited[v] = false;for (v = 0; v < G.vexnum; v++) {if (!visited[v]) {DFS(G, v);}}
}
void DFS(Graph g, int v) {visit(v);visited[v] = true;for (w = FirstNeighbor(g,v); w >= 0; w = NextNeighbor(g, v, w)) {if (!visited[w])DFS(g, w);}//for
}

u到v的所有最短路径

void FindPath(AGraph *G, int u, int v, int path[], int d) {int w, i;ArcNode *p;d++; // 路径长度加1，初始为-1；path[d] = u; // 将当前节点加入路径中去visited[u] = 1;if (u == v) // 找到一条路径print(path)p = G->adjlist[u].firstarc; // p 指向u的下一个相邻节点while(p) {w = p->adjvec; // 若顶点w未被访问过，则递归访问if (visited[w] == 0)FindPath(G, w, v, path, d);p = p->nextarc; // p指向u的下一个相邻节点}visited[u] = 0; //恢复节点，该位置可再次被其他路径访问 (该点不访问)
}

拓扑排序

bool TopologicalSort(Graph G) {IniStack(S); // 初始化栈，存储入度为0的顶点for(int i = 0; i < G.vexnum; i++) {if (indegree[i] == 0)Push(S, i);	//将所有入度为0的顶点入栈}int count = 0; // 将所有入读为0的顶点入栈while(!IsEmpty(S)) {Pop(S,i);print[count++] = i; // 输出顶点ifor (p = G.vertices[i].firstarc; p; p = p->nextarc) {// 将i指向的顶点度数减一，并且将度为0的顶点入栈v = p->adjec;if(--indgree[i] == 0)Push(S,v);}}//whlieif(count < G.vexnum)return false;elsereturn true; // 拓扑有序
}

迪杰斯特拉

#define MAXSIZE 20
#define PLACENUM 12
#define INF 9999           // 此处定义999为无穷大struct
{int vexnum,arcnum;  //节点数和边数int vexs[MAXSIZE];      // 节点名int arcs[MAXSIZE][MAXSIZE];   //俩个节点之间的值
} net;
/*补充的结构体net,2019.7.3*/void Dijkstra(int x,int y)      // x为源点，y为终点
{int i,j,k;int min;int u;   //下一个放入集合p的点int dis[net.vexnum];   //  最短路径int mark[net.vexnum];   //   被mark的便是已经遍历,未被mark的便是未遍历/*首先进行最短路径初始化*/for(i=0; i<net.vexnum; i++){mark[i] = 0;dis[i] = net.arcs[x][i];}mark[x]=1;          // 标记源点for(k=0; k<net.vexnum; k++)          // for 大循环{min = INF;   //  min初始化最大值，便于后来数据替换（每一个点的出度入度判断）/*寻找遍历到点联通路径（与之相连线的点）中权值最小的一条； 标记遍历点；*/for(i=0; i<net.vexnum; i++){if(mark[i]==0&&min>dis[i])      //判断未遍历点 且 被赋值的最短路径（dis[i]<INF），未被赋值的点     //                                                     应当min==dis[i]=INF{min = dis[i];             //在已知赋值最短路径中，寻找权值最小的点并将他作为下一个遍历 u=i;                            //点u点}}mark[u]=1;      //标记u点，下面u修正将会以最短路径进行辐射/*修正最短路径*/for(i=0;i<net.vexnum;i++){if(!mark[i]&&dis[i]>dis[u]+net.arcs[u][i]) // ！mark[i]判断不去走回头路,dis[i]>dis[u]+net.arcs[u]{dis[i] = dis[u] + net.arcs[u][i];     //若A->C比A->B->C更长那么A->B->C则是到C的最短路径         }//if}}//forprintf("最短路径值为：%d",dis[y]);
}

弗洛伊德

#include <iostream>
#include <cstring>
using namespace std;int n, m, s, arr[1005][1005];int main() {memset(arr, 0x3F, sizeof(arr));cin >> n >> m >> s;for (int i = 1; i <= n; i++) {arr[i][i] = 0;}for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;arr[a][b] = min(arr[a][b], c);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);}}}for (int i = 1; i <= n; i++) {if (i != 1) {cout << " ";}if (arr[s][i] == 0x3F3F3F3F) {cout << -1;} else {cout << arr[s][i];}}return 0;
}

链表

复制带随机指针的链表

原地处理，将克隆结点放在原结点后面，在原链表上处理克隆结点的random指针，最后分离两个链表.

class Solution {public Node copyRandomList(Node head) {if(head == null){return head;}// 空间复杂度O(1)，将克隆结点放在原结点后面Node node = head;// 1->2->3  ==>  1->1'->2->2'->3->3'while(node != null){Node clone = new Node(node.val,node.next,null);Node temp = node.next;node.next = clone;node = temp;}// 处理random指针node = head;while(node != null){// ！！node.next.random = node.random == null ? null : node.random.next;node = node.next.next;}// 还原原始链表，即分离原链表和克隆链表node = head;Node cloneHead = head.next;while(node.next != null){Node temp = node.next;node.next = node.next.next;node = temp;}return cloneHead;}
}

排序

TOP-K问题

int quickSelect(int *num, int l, int r) {int key = num[l];while(l < r) {while(l < r && num[r] <= key) r--;num[l] = num[r];while(l < r && num[l] >= key) l++;num[r] = num[l];}num[l] = key;return l;
}int findKthLargest(int* nums, int numsSize, int k){int l = 0, r = numsSize - 1;k -= 1;while(l < r) {int ind = quickSelect(nums, l , r);if (ind == k) return nums[ind];if (ind < k) l = ind + 1;else r = ind - 1;}return nums[l];
}

堆排序

void BulidMaxHeap(int A[], int len) {//建立大根堆for (int i = len >> 1; i > 0; i--) { // 从最后一个有子树的节点开始调整HeadAdjust(A, i, len);}
}void HeadAdjust(int A[], int k, int len) {// 将元素k为根的子树进行调整 A[0] = A[k]; // 暂存子树的根节点for (int i = k * 2; i <= len; i++) {if (i < len && A[i] < A[i + 1]) // 沿着数大的方向交换i++;if (A[0] > A[i]) break;else {A[k] = A[i];k = i;}}A[k] = A[0]; // 将被筛选节点的值放入最终结点中
}
void HeapSort(int A[], int len) {// 堆排序BuildMaxHeap(A, len);for (int i = len; i > 0; i--) { //n-1趟交换和建堆的过程swap(A[1], A[i]); // 输出堆顶元素，放到合适位置HeadAdjust(A, 1, i - 1); // 对交换后的堆进行调整}
}

判断是否是小顶堆

算法思想：扫描所有分支节点，遇到孩子节点的值小于根节点关键字的值的时候，返回false，扫描完返回true。

归并排序

void merge_sort(int *num, int l, int r) {if (r - l <= 1) {if (r - l == 1 && num[l] > num[r]) {swap(num[l], num[r]); // 只剩两个元素的时候}return;}int mid = (l + r) >> 1;merge_sort(num, l, mid); // 递归对左侧数组进行归并排序merge_sort(num, mid + 1, r); // 递归对右侧数组进行归并排序int *temp = (int *)malloc(sizeof(int) * (r - l + 1)); // 有序的数组进行合并int p1 = l, p2 = mid + 1, k = 0;while(p1 <= mid || p2 <= r) {if (p2 > r || (p1 <= mid && num[p1] < num[p2])) { //从左侧数组取值temp[k++] = num[p1++];} else {temp[k++] = num[p2++];}}memcpy(num + l, temp, sizeof(int) * (r - l + 1));free(temp);return ;
}

快排

void quick_sort(int *num, int l, int r) {while (l < r) { // 终止条件，对整个大的分组全部完成快排int x = l, y = r, temp = num[(l + r) >> 1]; //基准值do {while (x <= y && num[x] < temp) x++; // 找到左侧第一个大于基准值的数字while (x <= y && num[y] > temp) y--;// 找到右侧第一个小于基准值的数字if (x <= y) {swap(num[x], num[y]); // 交换位置x++, y--;}} while (x <= y); // 基准值右侧全是大于它的数，第一次快排结束quick_sort(num, x, r); // 对右侧的区间递归块排r = y; // 对左区间进行块排（此时 l ！= r）}return ;
}

希尔排序

void ShellSort(int A[], int n) {// A[0]只是暂存单元，不是哨兵，当j<=0的时候，插入位置已到for (dk = n / 2; dk >= 1; dk /= 2) { // 步长为dkfor (i = dk + 1; i <= n; i++) {if (A[i] < A[i - dk]) {	//将A[i]存放到有序增量子表中A[0] = A[i];for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) {A[j + dk] = A[j];}A[j + dk] = A[0];//插入}//if}}
}

其他

背包问题

01背包

for (int i = 1; i <= n; i++)
{for (int j = V; j >= 0; j--){if (j >= w[i]){f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);}else{f[i][j] = f[i - 1][j];}}
}

一般背包

按照性价比从高到底进行排序，最后一个可分割。

完全背包

#include <iostream>
#define read(x,y) scanf("%d%d",&x,&y)using namespace std;const int maxn=1010,maxv=1010;
int v[maxn],w[maxn];
int dp[maxn][maxv];//N行V列，0行0列初始为0int main() {int N,V;read(N,V);for (int i=1;i<=N;i++) read(v[i],w[i]);for (int i=1;i<=N;i++)for (int j=0;j<=V;j++) "已经初始化第0列为0了，所以不管j从1还是从0开始，都一样"for (int k=0;k*v[i]<=j;k++)dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);//转移方程printf("%d",dp[N][V]);return 0;
}

并查集

#include <stdio.h>
#include <stdlib.h>#define swap(a, b) {\__typeof(a) __temp = a;\a = b; b = __temp;\
}typedef struct UnionSet {int *father, *size;int n;
} UnionSet;UnionSet *init(int n) {UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));u->father = (int *)malloc(sizeof(int) * (n + 1));u->size = (int *)malloc(sizeof(int) * (n + 1));u->n = n;for (int i = 1; i <= n; i++) {u->father[i] = i;u->size[i] = 1;}return u;
}int find(UnionSet *u, int x) {return u->father[x] = (u->father[x] == x ? x : find(u, u->father[x]));
}int merge(UnionSet *u, int a, int b) {int fa = find(u, a), fb = find(u, b);if (fa == fb) return 0;//if (u->size[fa] < u->size[fb]) swap(fa, fb);u->father[fb] = fa;//u->size[fa] += u->size[fb];return 1;
}void clear(UnionSet *u) {if (u == NULL) return ;free(u->father);free(u->size);free(u);return ;
}int main() {int n, m;scanf("%d%d", &n, &m);UnionSet *u = init(n);for (int i = 0; i < m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);switch (a) {case 1: merge(u, b, c); break;case 2: printf("%s\n", find(u, b) == find(u, c) ? "Yes" : "No"); break;}}clear(u);return 0;
}

线性表

1. 结构体：是一种将多个数据结构组合起来的数据结构。
2. 线性表。
3. 头指针和头节点的区别。

串

模式匹配是数据结构中字符串的一种基本运算，给定一个字串，要求在某个字符串中找出与该字串相同的所有字串，这就是模式匹配。

KMP算法。

文本串、模式串、前缀表。

前缀：不包含尾部字母的前面的字串。后缀同理。

求最长相等前后缀。

整体减一的next数组：

void getNext(int *next, cosnt string& s) {int j = -1;next[0] = -1;for (int i = 1; i < s.size(); i++) {// i 从1开始while(j >= 0 && s[i] ! = s[j+1]) {j = next[j];// j 向前回退}if (s[i] == s[j + 1]) { //找到相同的前后缀j++;}next[i] = j; // 将 j （前缀的长度）赋值给next[i]}
}
例如：[a, b, c ,d, e, f]
next[-1， -1，-1， -1，-1，-1]

那么使用next数组，用模式串匹配文本串的整体代码如下：

int j = -1; // 因为next数组里记录的起始位置为-1
for (int i = 0; i < s.size(); i++) { // 注意i就从0开始while(j >= 0 && s[i] != t[j + 1]) { // 不匹配j = next[j]; // j 寻找之前匹配的位置}if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动j++; // i的增加在for循环里}if (j == (t.size() - 1) ) { // 文本串s里出现了模式串treturn (i - t.size() + 1);}
}

树

1. 树的存储结构：

   1. 双亲表示法：用一组连续的空间存储每个节点，同时每个节点中增设一个伪指针指向双亲的位置。
   2. 孩子表示法：将每个节点的孩子节点连接成一条链。
   3. 孩子兄弟表示法。

2. 最小生成树：连通图中包含所有节点的最小联通子图，n-1条边。可以用克鲁斯卡尔法或者普利姆算法。

3. 哈夫曼树：由n个带权叶子节点构成所有二叉树中带权路径长度最短的二叉树。用于数据压缩。

4. 二叉排序树的插入和删除。

5. 红黑树

   红黑树的特性:
   （1）每个节点或者是黑色，或者是红色。
   （2）根节点是黑色。
   （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
   （4）如果一个节点是红色的，则它的子节点必须是黑色的。
   （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

   特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

   一棵含有n个节点的红黑树的高度至多为2log(n+1).

图

1. 图结构的存储：邻接矩阵、邻接表、临界多重表（无向图）、十字链表（有向图）
2. 深度搜索形成森林或树。
3. 深搜和广搜的区别。
4. 普利姆算法：O（n^2) 克鲁斯卡尔算法： O(eloge)
5. 迪杰斯特拉算法和弗洛伊德算法。

查找

1. B树和B+树
2. 哈希表
3. 开放地址法如何删除一个关键字？并不真正的删除，防止截断后面的数据。

排序

1. 在有序的情况下进行快排的时间复杂度是多少？

   O（n^2),因为会形成一颗单支树。

2. 排序方法的选择：

   1. 若n比较小：采用直接插入排序和简单选择排序。
   2. 若数组基本有序，则选择冒泡排序或者直接插入排序。
   3. 若n很大，采用快排、堆排、归并排序
   4. 若n非常大，可以采用基数排序

3. 桶排序：桶排序，也叫作箱排序，是一个排序算法，也是所有排序算法中最快、最简单的排序算法。其中的思想是我们首先需要知道所有待排序元素的范围，然后需要有在这个范为。除了对一个桶内的元素做链表存储，我们也有可能对每个桶中的元素继续使用其他排序算法进行排序，所以更多时候，桶排序会结合其他排序算法一起使用。时间复杂度就是 O(n+m)，其中，n 为待排序的元素的个数，m 为桶的个数。这是相当快速的排序算法，但是对于空间的消耗来说有点太大了。

4. 排序的应用。排序分为比较排序和非比较排序，比较排序不会低于O(nlogn)

5. 稳定排序的优势：对一些按照key值排列的对象进行排序，保证各对象之间的关系不被破坏。

6. 电商产品利润最大采用哪种排序？

排序算法	平均时间复杂度	最好	最坏	空间	排序方式	稳定性
冒泡	O(n^2)	O(n)	O(n^2)	O(1)	内部排序	稳定
选择	O(n^2)	O(n^2)	O(n^2)	O(1)	内部排序	不稳定
插入	O(n^2)	O(n)	O(n^2)	O(1)	内部排序	稳定
希尔	O(nlogn)	O(nlog^2n)	O(nlog^2n)	O(1)	内部	不稳定
归并	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	外部	稳定
快排	O(nlogn)	O(nlogn)	O(n^2)	O(nlogn)	内部	不稳定
堆排	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	内部	不稳定
计数	O(n + k)	O(n + k)	O(n + k)	O(k)	外部	稳定
基数	O(n * k)	O(n * k)	O(n * k)	O(n + k)	外部	稳定
桶排序	O(n + k)	O(n + k)	O(n ^ 2)	O(n + k)	外部	稳定

组成原理

第1章：计算机系统概论

1、计算机系统由哪两部分组成？计算机系统性能取决于什么？

计算机系统是由“硬件”和“软件”组成。衡量一台计算机性能的优劣是根据多项技术指标综合确定的，既包括硬件的各种性能指标，又包括软件的各种功能。

1）计算机系统由硬件和软件两部分组成。
2）计算机系统性能由硬件和软件共同决定。

2、计算机系统5层层次结构从下到上由哪五层组成？哪些是物理机，哪些是虚拟机？
1）微程序机器、传统机器、操作系统机器、汇编语言机器、高级语言机器
2）微程序机器和传统机器是物理机，其他是虚拟机。

3、在计算机系统结构中，什么是翻译？什么是解释？
1）翻译：将一种语言编写的程序全部翻译成另一种语言，然后再执行；
2）解释：将一种语言编写的程序的一条语句翻译成另一种语言的一条或多条语句，然后执行，执行完这条语言后，再解释下一条。

4、什么是计算机体系结构？什么是计算机组成？以乘法指令为例说明二者区别。
1）计算机体系结构是指那些能够被程序员看到的计算机的属性。如指令集、数据类型等；
2）计算机组成是指如何实现计算机体系结构所体现出来的属性；
3）以乘法指令为例，计算机是否有乘法指令，属于体系结构的问题。乘法指令是采用专用的乘法器，还是使用加法器和移位器构成，属于计算机组成的问题。

5、冯诺依曼机器的主要特点？
1）计算机由运算器、存储器、控制器、输入设备和输出设备五大部分组成；
2）指令和数据存储在存储器中，并可以按地址访问；
3）指令和数据均以二进制表示；
4）指令由操作码和地址码构成，操作码指明操作的性质，地址码表示操作数在存储器中的位置；
5）指令在存储器内按顺序存放，通常按自动的顺序取出执行；
6）机器以运算器为中心，I/O设备与存储器交换数据也要通过运算器。（因此，后来有了以存储器为中心的计算机结构）

7、什么是存储单元、存储字、存储字长、存储体？
存储单元：存储一个存储字并具有特定存储地址的存储单位；
存储字：一个存储单元中存放的所有的二进制数据，按照某个地址访问某个存储单元获取的二进制数据。
存储字长：存储字中二进制数据的位数，即按照某个地址访问某个存储单元获取的二进制数据的位数；
存储体：由多个存储单元构成的存储器件。

8、主存储器中，什么是MAR，什么是MDR，存储器的最大容量由什么决定？
1）MAR：存储地址寄存器，保存需要访问的存储单元地址。反映存储单元的个数。
2）MDR：存储数据寄存器，缓存读出/写入存储单元的数据。反映存储字长。
3）存储器的最大容量由MAR寄存器的位数和MDR寄存器的位数决定。

9、什么是机器字长，什么是存储字长？
机器字长：CPU一次能够处理的二进制数据的位数。
存储字长：按照某个地址访问某个存储单元获取的二进制数据的位数。

10、假设MAR寄存器的位数为16位，MDR寄存器的位数为16位，存储器的最大容量是多少？
1）MAR寄存器的位数为16位，能表示的地址个数为2的16次方，为64K；
2）MDR寄存器的位数为16位，说明存储字长为16位，也即2个字节；
3）存储器的最大容量为64K * 2B = 128K Byte

------------------------------------------------------------------------------------------------------

第三章 系统总线

1、为什么要使用总线？
在冯诺依曼结构中，各个部件之间均有单独连线，不仅线多，而且导致扩展I/O设备很不容易。即扩展一个I/O设备，需要连接很多线。
因此，引入了总线连接方式，将多个设备连接在同一组总线上，构成设备之间的公共传输通道。

2、总线的两大基本特征是什么？
1）共享：多个部件连接在同一组总线上，各个部件之间都通过该总线进行数据交换。
2）分时：同一时刻，总线上只能传输一个部件发送的信息；

3、系统总线按照传输信息的不同，分成哪几类？是单向的，还是双向的？
1）分成数据总线、地址总线以及控制总线。
2）数据总线：各个功能部件之间传送数据信息，双向传输；
3）地址总线：用来指明数据总线上，源数据或目的数据所在的主存单元的地址。单向：由CPU发出
4）控制总线：用来发送各种控制信号。对于控制总线中的单根线，是单向的，即只能由一个部件发向另一个部件。而一组控制总线中，有输入也有输出，因此，控制总线也可以看成是双向的。

3、什么是总线宽度、总线带宽、总线复用、信号线数？
1）总线宽度：数据总线的根数，一般是8的倍数。是衡量计算机系统性能的重要指标；
2）总线带宽：即总线数据传输速率，总线上每秒能够传输的最大字节量。
3）总线复用：一条信号线上分时传送两种信号。例如数据总线和地址总线的分时复用；
4）信号线数：地址总线、数据总线和控制总线三种总线的线数之和。

4、假设总线的工作频率为33MHz，总线宽度为32位，则它最大的传输速率是多少？
33 * （32/8） = 132 MB/s

5、简要说明单总线结构的概念及缺点？（现代计算机为什么要采用多总线结构？）
在单总线结构中，所有的部件（CPU、主存、I/O设备）都连接在一组总线上。
但所有的信息传送都要通过这组总线，同时只能有一个部件向总线上发送信息，导致总线成为系统的瓶颈。
因此，发展出来了多总线结构，其基本思想均是将速度相近的设备挂接在同一组总线上，总线之间通过总线控制器相连。
例如CPU和Cache之间、I/O设备之间等。

6、集中式总线判优控制有哪三种方式，哪种方式的优先级不能改变？
1）链式查询、计数器定时查询、以及独立请求。
2）链式查询的优先级不能改变，离控制器最近的优先级最高。

7、简述链式查询、计数器定时查询以及独立请求三种方式的工作原理。
（略）

8、什么是总线周期，分为哪几个阶段？
1）总线周期：总线上两个部件完成一次完整且可靠的数据传输时间；
2）分为四个阶段：
申请分配阶段：申请总线
寻址阶段：发出地址及有关命令
传数阶段：进行数据交换
结束：从总线上撤除信号，让出总线

9、什么是总线通信控制，总线通信控制有哪几种？
1）总线通信控制：解决通信双方如何获知传输开始和传输结束，以及如何协调配合；
2）同步通信、异步通信、半同步通信、分离式通信

10、什么是同步通信？其优点和缺点？
１）同步通信：总线上各个部件由统一的时钟信号控制；在总线周期中，每个时钟周期各个部件如何动作都有明确的规定。
２）优点：速度快，各个模块间配合简单。
３）缺点：以总线上最慢的部件来设计公共时钟，影响总线效率，效率低。

11、什么是异步通信？异步通信分为哪几种类型？
1）异步通信：总线上各部件没有统一的时钟标准，采用应答式通信；（主模块发出请求后，一直等到从模块反馈回来应答信号之后才开始通信）
2）不互锁、半互锁、全互锁。（需要了解各种方式的含义）

12、什么是波特率？什么是比特率？（需要掌握如何计算波特率、比特率）
波特率：单位时间内传送的二进制数据数据的位数，单位bps
比特率：单位时间内传送的有效的二进制位数。

13、异步通信时，常规需要设置的参数有哪些？
波特率、停止位（1/2/1.5）、校验位（奇校验、偶校验、无校验）

14、简述半同步通信的基本原理。
半同步通信结合同步通信和异步通信。
同步通信：采用统一的时钟，规定了在一定的时钟周期干什么事情；
异步通信：如果从模块没有准备好，增加一个“等待响应”信号。

15、简述分离式通信的基本原理。
主模块发出地址和命令之后，放弃总线，在从模块准备数据期间，使得总线可以被其他设备所用。提高总线利用率。
但是，这种方式控制比较复杂。

16、奇偶校验可以纠错吗？汉明码可以纠错码？
1）奇偶校验只能检错，不能纠错。
2）汉明码可以纠错。

-----------------------------------------------------------------------------------------------------------------------------------------

第四章 存储器

1、存储器按存取方式，可以分成哪四类？哪些属于随机访问存储器，哪些属于串行访问存储器？
1）可以分为随机存储器、只读存储器、顺序存储器和直接存储器；
2）随机存储器和只读存储器属于随机存储器，即存取时间与物理地址无关；
3）顺序存储器（典型的如磁带）和直接存储器（典型的如磁盘）属于串行存储器，即存取时间与物理地址有关。

2、衡量存储器使用哪三个指标？寄存器、缓存、主存中，哪个速度最快？哪个最便宜？
1）速度、容量、位价格。
2）寄存器速度最快，主存最便宜。

3、常见的存储系统层次结构有哪两种？透明性如何？各自用来解决什么问题的？
1）缓存-主存层次：用来缓解CPU和主存速度不匹配的问题，由硬件来完成，对所有的程序员完全透明。
2）主存-辅存层次：用来解决主存容量不够的问题，由操作系统和硬件共同完成，对应用程序设计者透明，对系统程序设计者不透明。

（现在一般存储器都即能按字访问，也能按照字节访问，因此，存储器编址时，每个字节都有一个独立的地址。）
4、字在存储单元中有两种存储方式，大端方式和小端方式。各是什么含义？x86采用的是哪种存储方式？
1）大端方式：字的低位存在内存的高地址中，而字的高位存在内存的低地址中；
2）小端方式：字的低位存在内存的低地址中，而字的高位存在内存的高地址中。
3）x86CPU采用的是小端方式。

5、主存的三个主要技术指标
存储容量、存取速度和存储带宽

6、什么是存取时间？什么是存取周期？哪个大？
1）存取时间：启动一次存储器完成本次操作（读或写）所需的时间；
2）存取周期：连续两次启动存储器所需要的最小间隔时间；
3）存取周期包含存取时间；

7、什么是存储器带宽？（要了解如何计算存储器带宽）
单位时间内存储器存取的信息量；

8、半导体存储芯片译码驱动包含哪两种方式，请简要说明。
1）线选法：所有的地址芯片通过一个译码器译码，选择一个存储单元的各位，适合于存储容量不大的芯片；
2）重合法：将地址分为两组，每组通过一个译码器译码，选择行或列，行、列交叉处就是要访问的存储位。

9、随机存储器包含哪两大类？哪个需要刷新？请从速度、容量、价格等方面进行简要比较。
1）静态RAM：采用锁存器原理实现；
2）动态RAM：采用电容原理实现，需要刷新。
3）相比于动态RAM，静态RAM的速度快、容量小、价格高，一般用于缓存，而动态RAM一般用于内存。

SRAM：读写速度快，生产成本高，多用于容量较小的高速缓冲存储器。

DRAM：读写速度较慢，集成度高，生产成本低，多用于容量较大的主存储器。

动态存储器的定期刷新：在不进行读写操作时，DRAM 存储器的各单元处于断电状态，由于漏电的存在，保存在电容CS 上的电荷会慢慢地漏掉，为此必须定时予以补充，称为刷新操作

10、只读存储器有哪几种？
1）掩模ROM（MROM）：出厂后内容不能被更改。
2）PROM：可编程只读存储器，可以进行一次性编程；
3）EPROM：可擦除只读ROM，用紫外线照射；
4）EEPROM：电可擦除只读ROM。
6）FLash Memory：采用EEPROM的非易失性存储器。

11、单片存储器芯片的容量有限，很难满足实际需要，因此必须将若干存储芯片连接在一起才能组成足够容量的存储器。
存储器的扩展通常有位扩展和字扩展，什么是字扩展，什么是位扩展？请举例简要说明
1）位扩展：增加存储器的字长，例如两个1K * 4位的存储芯片构成1个1K*8位的存储器；
2）字扩展：增加存储器的字数，例如两个1K * 8位的存储芯片构成1个2K * 8位的存储器；
通常字扩展和位扩展两种方式混合使用。

12、熟虑掌握存储器的扩展，包括地址空间分配、地址线的连接、数据线的连接、片选信号的产生及连接等；
参看P94页，例4.1

13、假设欲检测的二进制代码为n位，为了使其具有1位的纠错能力，需添加K位检测位，组成n+k位的代码。问，应添加多少位检测位？
应添加的检测位位数：2的k次方大于等于n+k+1。
因为要使其有1位的检测能力，必须使用k位来说明n+k位到底哪一位出现了错误，k位能表达的数量为2的k次方，而n+k位到底哪一位
出现了错误或者是全部正确，共有n+k+1种状况，因此，k的取值需要满足：2的k次方大于等于n+k+1

14、对于汉明码，应熟练掌握汉明码的编码方式（按照配偶或配奇的原则），以及给出汉明码，得到要传送的原始信息（包括纠错过程）。

15、提高访存速度的三种方式。
1）采用高速元器件；
2）采用存储层次结构：cache-主存结构；
3）调整主存结构：包括单体多字，多体并行两种方式。

16、简述单体多字的存储系统的工作原理，及其优点。
1）单体多字存储系统一次访存取出多个CPU字，即存储字为CPU字的n倍（假设一次访存取出n个cpu字）。
2）优点是：显著提高了存储器带宽。

17、多体并行系统有哪两种编址方式？请简要说明其编址方式及其优点。
1）高位交叉编址方式：存储体的编址方式为顺序存储，即一个存储体存满后，再存入下一个；存储单元地址的高位为存储体的编号。
高位交叉编址并不能提高单次访存速度，但能使多应用并行访存，提高系统的并发性。

2）低位交叉编址方式：存储体的编址方式为交叉存储。即程序连续存放在相邻的存储体之中。存储单元地址的低位为存储体的编号。
低位交叉编址能显著提高单次访存速度。

19、在四位低位交叉编址中，假设存取周期为T，总线传输周期为τ，为了实现流水线方式存储，应满足什么条件？如果连续读取四个字，所需要的时间是多少？
1）T= 4τ
2）连续读取四个字，所需要的时间为T + （4-1）τ
注意：假设不是低位交叉编址，而是高位交叉编址，连续读取四个字所需要的时间仍然为4T。

20、需要大家掌握多体并行存储器在高位交叉编址（顺序存储）和低位交叉编址（交叉存储）的情况下，存储器带宽的计算方式。

21、在CPU和内存之间引入cache的原因。
1）避免cpu空等I/O访存；
2）缓解CPU和主存速度不匹配的问题。

22、什么是程序的局部性原理。
CPU从主存取指令或数据，在一定时间内，只是对主存局部地址区域访问。

23、Cache命中率、平均访问时间以及访问效率的计算。

24、Cache写操作有哪两种方式？
1）写直达法：写操作既写入Cache又写入主存；
2）写回法：只把数据写入Cache而不写入主存，当Cache中数据被替换出去之后才写入主存。

25、将主存地址映射到Cache地址称为地址映射，常见的Cache映射方式有哪几种？
直接映射、全相联映射、组相联映射。

26、直接映射的优缺点？
优点：地址变换速度快。缺点：cache利用率不高，块冲突率高；

27、全相联映射的优缺点？
优点：cache利用率高，块冲突率低。缺点：地址变换复杂，需要较多的硬件。

28、需要大家掌握各种映射方式之下，写出主存地址格式、cache地址格式，以及主存地址向cache地址的转换。

29、Cache常用的替换算法有哪些？哪个命中率最高？
1）先进先出、近期最少使用算法和随机替换算法；
2）命中率最高的是近期最少使用算法；

30、磁盘的三地址结构包括哪些？
柱面、磁头号和扇区号

---------------------------------------------------------------------------------------------------------

第五章 输入输出系统

1、I/O系统的发展大致可以分为哪4个阶段？
1）早期（分散连接、串行工作、程序查询）
2）接口模块和DMA阶段（总线连接、并行工作、中断及DMA）
3）通道阶段（通道是具有特殊功能的处理器）
4）I/O处理机阶段
I/O系统的发展实际上是逐步将CPU从繁重的I/O工作中解放出来的过程；

2、I/O设备编址有哪两种方式？各有什么优缺点？
1）统一编址方式：和存储器统一编址，I/O地址作为存储器地址的一部分；无须用专用的I/O指令，但占用存储器空间。
2）独立编址方式：和存储地址分开编址，需用专用的I/O指令。

3、I/O设备与主机的联络方式有哪几种？
I/O设备与主机间交互信息时必须了解彼此的状态。根据I/O设备工作速度的不同，可以分为3类：
1）立即响应：不管其状态（认为其时刻准备好），适用于慢速设备。
2）应答信号：通过应答信号来进行交互；
3）同步时标：采用统一的时钟信号。

4、I/O总线包括哪四类？
数据线、设备选择线、状态线、命令线

5、I/O设备通常使用D触发器（完成触发器）和B触发器（工作触发器）来标识设备所处的状态。
D=0，B=0：暂停状态；
D=0，B=1：准备状态
D=1，B=0：就绪状态

6、程序查询的基本工作原理。
cpu不断去查询I/O设备状态，导致CPU和I/O设备串行工作。

7、什么是中断？
计算机在执行程序过程中，当出现异常清空或特殊请求时，计算机停止现行程序的运行，转去处理这些异常清空或特殊请求，处理结束后，再返回现行程序的间断处，继续执行原程序，即为中断。

8、中断服务程序的基本流程包括哪四部分？
1）保护现场
2）中断服务
3）恢复现场
4）中断返回

9、什么是单重中断和多重中断？
1）单重中断：不允许中断现行的中断服务程序；
2）多重中断：允许级别更高的中断源中断现行的中断服务程序，也称为中断嵌套；

10、CPU响应中断的时机？
当前指令执行完毕后，cpu发出中断查询信号，也就是说，中断响应一定是在每条指令执行结束之后进行的，不可能在指令执行过程中响应中断。

11、什么是DMA？
DMA：直接内存访问。在主存和I/O设备之间建立独立的总线连接。

12、在DMA方式中，由于DMA接口与CPU共享主存，可能会出现两者争用主存的冲突，为解决冲突，DMA和主存交换数据时，通常采用哪三种工作方式？
1）停止CPU访问主存：DMA访存优先级高；
2）周期挪用（窃取）：DMA挪用存储或窃取总线使用权一个或几个主存存取周期；
3）DMA和CPU交替访问：将CPU工作周期分成两部分，一部分供DMA访存，一部分供CPU访存。

13、DMA工作过程包括哪三部分？
1）预处理
2）数据传输
2）后处理

第六章 计算机的运算方法

1、掌握有符号数的原码计算方法，以及通过原码求真值；

2、掌握补码计算的方法，以及通过补码求原码，然后求真值的方法。
1）通过原码求补码：符号位不变，各位取反，末位加1；
2）通过补码求原码：符号位不变，各位取反，末位加1；

3、原码中0有2种表示方法（正零和负零），补码中0只有一种表示方法（正零和负零的表示方法一致）

4、假设有符号数的位数为8（包括符号位），补码能表示的真值的范围？
补码能表示的真值范围为-128~+127（参见补码定义）

5、掌握求反码以及移码的方法。

6、什么是定点表示？什么是浮点表示？
１）定点表示：小数点固定在某一位置的数为定点数；
２）浮点表示：小数点位置可以浮动的数。

7、浮点数在机器中的表示形式，由哪几部分组成？
由尾数、数符、阶码、阶符四部分组成。

8、掌握规格化浮点数的表示范围（最大正数、最小正数、最大负数、最小负数）的计算方法。

9、IEEE754标准规定的浮点数由哪几部分组成？
由数符、阶码（含阶符）以及尾数组成。

10、IEEE754标准规定的浮点数中，阶码和尾数用什么形式表示？
阶码用移码表示，其偏移量是2^(n-1)，尾数用原码表示。

11、float占多少位？double占多少位？
float为短实数，占32位，其中阶码8位，尾数23位。
double为长实数，占64位，其中阶码占11位，尾数为52位。

12、对正数进行算术移位，当正数采用源码、补码、反码时，左移或右移时，低位或高位添补什么代码？
对于正数，其源码、补码、反码均等于真值，左移时，低位添补0，右移时，高位添补0。

13、对负数进行算术移位，当负数采用源码、补码、反码时，左移或右移时，低位或高位添补什么代码？
对于源码，左移或右移时，低位或高位均添补0；
对于补码：左移时，低位添补0，右移时高位添补1
对于反码：左移或右移时，低位或高位均添补1；

14、什么是逻辑移位？
逻辑移位是对无符号数的移位，由于无符号数不存在符号位，左移时，高位移丢，低位补零。右移时，低位移丢，高位补零。

15、加法和减法时，什么情况下可能发生溢出？如何简单判断发生溢出？
1）正数加正数，正数减负数，负数加负数，负数减正数时，可能会发生溢出。
2）如果参加操作的两个数符号相同（转换成补码的加法），其结果与源操作数符号不同，即为溢出。
3）如果补码采用1位符号位，如果最高有效位的进位和符号位的进位不同，则发生溢出。

16、定点乘法运算可以使用加法和移位来实现吗？
可以。

17、浮点加减运算基本按照哪几步来进行？
1）对阶：使小数点对齐；
2）尾数求和：将对阶后的两个尾数按照定点加减运算规则求和；
3）规格化：尾数规格化；
4）舍入：尾数右规时，丢失数值位；
5）溢出判断：判断结果是否溢出。

18、如何判断浮点运算结果是否溢出？
阶码是否超出了其表示范围。（使用2个符号位判溢出）

第七章 指令系统

1、什么是机器指令？什么是指令系统？

1）机器指令：每一条机器语言的语句； 2）指令系统：全部机器指令的集合。

2、一条指令包含哪两个主要部分？请简要说明各部分作用。
1）操作码：指明指令要完成的操作；
2）地址码：指明指令要操作的数据或数据来源；

3、操作码长度有固定长度和可变长度两种，各自有什么优点？
1）固定长度：便于硬件设计，指令译码时间短；
2）可变长度：压缩了操作码平均长度；

4、指令中地址码中的地址可以是哪些设备的地址？
可以是主存地址、寄存器地址或I/O设备的地址；

5、指令中地址的个数可以有几个？
四地址、三地址、二地址、一地址以及零地址。

6、假设指令中有四个地址、三个地址、两个地址以及一个地址，各自需要访存几次？
1）四地址：访存4次；
2）三地址：访存4次；
3）两地址：访存3次；
4）一地址：访存2次；

7、当使用寄存器代替指令字中的地址码字段后，有哪些优点？
1）扩大指令字的寻址范围；
2）缩短指令字长；
3）减少访存次数

8、数据在存储器中存储时，为什么要按照边界对齐？
减少访存次数。

9、寻址方式包括哪两类？
1）指令寻址：下一条将要执行的指令的指令地址；
2）数据寻址：确定本指令的操作数地址。

10、什么是形式地址？什么是有效地址？
1）形式地址：指令的地址码字段通常都不代表操作数的真实地址，成为形式地址，记为A；
2）有效地址：操作数的真实地址，记为EA，由寻址特征和形式地址共同决定；

11、了解各种寻址方式的概念及根据形式地址形成有效地址的方式。
立即寻址、直接寻址、隐含寻址、间接寻址、寄存器寻址、寄存器间接寻址、基址寻址（隐式或显式）、变址寻址、相对寻址、堆栈寻址

系统概述

1. C语言的编译步骤：

   1. 预处理
   2. 编译
   3. 汇编
   4. 连接

2. 计算机的主要性能指标

3. 计算机为什么发展多核

4. cache和寄存器区别？

   寄存器是暂时存储的CPU组成部分，cache用来做高度CPU和低速的主存之间加速带。

5. 指令系统集。

   CISC复杂指令集，RISC是精简指令集。

6. 流水线：

   将重复性的过程分为若干个子过程来完成。

7. 总线和IO

   总线是指数据通信的连接线，有地址，数据，控制指令。

   I/O的方式有程序性，中断性，通道,DMA。

数据的表示和运算

1. 单精度和多精度浮点数的区别。

   单精度4个字节，1位符号位，8位指数位，23位小数位。

   双精度8个字节，1位符号位，11位指数位，52位小数位。

2. 什么是上溢和下溢？

3. 语法分析应该遵循构词规则。

4. 计算机如何实现乘除？

   乘法：举例说明：5*3

   1. 3=0011（不用分解，计算机就是这么存储的）
   2. 3的第0位1,5左移0位仍为0；
   3. 3的第一位为1，5左移1位为5*2 = 10
   4. 然后将其累加，得到最后结果15.

   除法：

   计算机计算除法的过程与人类计算的过程很类似，只是选择范围变成了0或1.
   还以51/3为例说明（51：110011；3:11）

   从第一位开始为1，小于11，结果位置0；余数为1
   从第二位开始，余数2+1=11，等于11，结果位置1，余数为0；
   从第三、四位开始，余数2+0=0<011,结果位置0，余数为0
   从第5位开始，余数2+1=1<11，结果置0，余数为1
   从第6位开始，余数2+1=11=11，结果置1，余数为0.
   此时将结果位相连，恰好是10001（17）

5. 计算机如何实现加减？（减法转换成加法，采用补码用加法器来计算）

6. 设计减法器

7. 设计加法器

存储系统

1. cache
2. 存储器结构
3. 寄存器和存储器的区别。

指令系统

1. 流水线
2. 寻址方式

中央处理器

CPU的功能

流水线越多，并行度越高，指令执行越快？

数据库

数据库博客1

数据库博客2

1. 事务及ACID特性(原子性、一致性、隔离性、持久性)

2. 分布式事务：指的是允许多个独立的事务资源参与一个全局的事务中。事务资源通常是关系型数据库系统，但也可以是其他类型的资源。分布式事务由一个或多个资源管理器、一个事务管理器以及一个应用程序组成。

3. 范式的定义？

   改造关系模式，通过分解关系模型来消除其中不合适的数据依赖，以决绝插入异常，删除异常，数据用余。

4. 并发一致性：

   1. 问题：丢失数据、读取脏数据、不可重复读、幻影读
   2. 解决方法：并发控制（用户通过加锁）、数据库管理系统提供“隔离级别”

5. 封锁粒度：行级锁、表级锁。（封锁应该尽可能的小，提高并发度）

6. 数据库有几种锁？

   1. 读写锁：又叫共享锁和排他锁
   2. 意向锁：其目的主要是为了在一个事务中揭示下一行将被请求的锁的类型。（表级锁）

7. 封锁协议。

8. 两段锁协议：生长阶段（加锁）和衰退阶段（解锁）。事务开始后就处于加锁阶段，一直到执行rollback和commit都是。

9. 锁升级：是指将当前锁的粒度降低。举例来说：数据库可以把一个表的1000个行锁升级为一个页锁，或者将页锁升级为表锁。

   （1）由一条单独的SQL语句在一个对象上持有的锁的数量超过了阈值可能会发生锁升级。

   （2）锁资源占用的内存超过了激活内存的40%时，就会发生锁升级。

   InnoDB存储引擎不存在锁升级的问题。在InnoDB存储引擎中，1个锁的开销与1000个锁是一样的，都没有开销。

10. 异常：冗余数据、修改异常、删除异常、插入异常。

11. 数据库的范式。

12. 数据库的主键和外键。（分别对应主表和从表）

13. E-R图。

14. 索引：

    1. b+树，b-树
    2. hash索引
    3. 全文索引
    4. 空间数据索引

15. 索引的优缺点、设计原则、优化策略、使用场景。

16. 聚集索引一个表只能有一个，而非聚集索引一个表可以存在多个。聚集索引存储记录是物理上连续存在，物理存储按照索引排序，而非聚集索引是逻辑上的连续，物理存储并不连续，物理存储不按照索引排序。

17. 数据库的sql语句。（查询语句）

18. 什么是数据库的数据完整性？有哪些数据完整性？

    1. 数据完整性即一组完整性规则的集合。完整性规则是数据及其联系所具有的制约和依存规则，用以保证数据的正确性、有效性、相容性，使数据系统值和现实系统状态一致。
    2. 包括实体完整性、参照完整性、用户定义的完整性。

19. 数据库的模型有哪些？

20. 常用的数据库：MySQL、Oracle、sqlserver、neo4j、navicate、studio 3T、sqlite等。

数据库技术发展

1. 第一代数据库系统：层次模型和网状模型（都是格式化模型）共同点：
   1. 支持三级模式（外模式、模式、内模式）
   2. 用存取路径表示数据之间的联系。数据库不仅存储数据，还存储数据之间的联系。
   3. 独立的数据定义语言。
   4. 导航的数据操作语言。
   5. 优点：小路高；缺点：编程繁琐、可移植性差、数据的逻辑独立性差。
2. 第二代数据库系统：关系数据库系统。优点：模型简单清晰、理论基础好、数据独立性强、数据库语言非过程化和标准化。
3. 第三代数据库系统：新一代数据库系统。
   1. 支持数据管理、对象管理、知识管理。
   2. 保持和继承第二代数据库系统的技术。
   3. 对其他系统开放。

数据、应用需求、计算机硬件技术是推动数据库发展的三个主要动力。

大数据给数据管理、数据处理、数据分析带来了全面的挑战。传统的关系数据库在系统的伸缩性（按需分派资源）、容错性（保证分布系统的可用性）和可扩展性（满足数据量增长的需要）难以满足。

NoSQL是指非关系性的、分布式的、不保证满足ACID特性的一类数据库管理系统。其具有以下特点：

1. 对数据进行划分，通过大量节点的并行处理获得高性能，采用的是横向扩展的方式。
2. 放松对数据的ACID一致性约束，允许数据暂时出现不一致的情况，接受最终一致性。
3. 对各个数据分区进行备份（一般是三份），应对节点可能的失败。

分布型NoSQL计数的主要代表是MapReduce技术。

大数据管理

大数据：一般指无法在可容忍的时间内用现有的IT技术和软硬件对其进行感知、获取、管理、处理和服务的数据集合。通常被认为是PB（10^{3TB)或EB（10}6TB）或更高数量级的数据，包括结构化的、半结构化的和非结构化的数据。

大数据的特征：巨量、多样、快变、价值。

大数据的应用：

1. 感知现在，预测未来——互联网文本大数据管理与发掘
2. 数据服务，实施推荐——基于大数据分析的用户建模

大数据管理系统NoSQL，是以互联网大数据应用为背景发展起来的分布式数据管理系统。NoSQL有两种解释（1）Non-Relational，即非关系数据库（2）Not only Sql，即数据库管理技术不仅仅是SQL。

NoSQL系统支持的数据模型通常分为：

1. Key-Value模型：按照key值存取value值。
2. BigTable模型：按列存储，每一列的每一个数据项都包含一个时间戳属性，一边保存同一个数据项的多个版本。
3. 文档模型：value值支持复杂的结构定义，通常是被转换成json或者类似json的格式化文档。
4. 图模型：记为G（V，E）。

NewSQL数据库是将SQL和NoSQ的优势结合起来，支持ACID特性，又可扩展，支持大数据。

**MapReduce技术：**是一种并行编程模型，它把计算过程分解为两个阶段，即Map阶段和Reduce阶段。执行过程：

1. 首先对输入的数据源进行分块，交给多个Map任务去执行，Map任务会执行Map函数，根据某种规则对数据分类，写入本地硬盘。
2. 然后进入Reduce阶段，Reduce函数将Map阶段具有相同key值的中间结果收集到相同的Reduce节点进行合并处理，并将结果写入本地磁盘。（通常计算节点和存储节点是一个节点）

内存数据库系统

内存数据库系统是指将数据库的全部或者大部分数据放在内存中的数据库系统。

内存数据库与磁盘数据库的区别：

1. 数据常驻内存，消除了磁盘数据库中巨大的输入/输出代价。
2. 实现了处理器对数据的直接访问，算法和代码效率更高。
3. 性能更高。

内存数据库的特性：

1. 高吞吐率和低延迟访问
2. 并行处理能力。
3. 硬件相关性。

数据仓库与联机分析处理技术

数据仓库：是为了构建新的分析处理环境而出现的一种数据存储和组织技术。

数据仓库的重要特征：

1. 主题与面向主题。数据是面向主题的。
2. 数据仓库是集成的。数据仓库从原有的分散的数据库中抽取来的，因此数据在进入数据仓库之前必然要经过加工与集成，统一与集合。
3. 数据仓库是不可更新的（分析处理期间）。数据仓库主要供决策分析之用，所设计的数据操作主要是数据查询，一般情况并不进行修改。
4. 数据仓库是随时间变化的。

数据仓库的组织形式：早期细节级、当前细节级、轻度综合级、高度综合级。

联机分析处理是以海量数据为基础的复杂分析技术。

多维数据模型是数据分析时用户的数据视图，是面向分析的数据模型，用于给分析人员提供多种观察的视角和面向分析的操作。

数据挖掘是从大量数据中发现并提取隐藏在内的、人们事先不知道的但有可能有用的信息和知识的一种新技术。

数据挖掘和传统分析方法的本质区别是数据挖掘在没有明确的假设的前提下去挖掘信息，发现知识。

“聚类和分类的区别还在于：聚类事先没有类表，完全是按照样本间的相似度来进行，即先有样本后有类；而分类则是基于某种预定的类表，将类表中的条目赋给样本，即先有类后有样本。”

数据挖掘的功能：

1. 概念描述。归纳总结出数据的某些特征。
2. 关联分析。
3. 分类和预测。
4. 聚类。
5. 孤立点的检测。孤立点是指数据中的整体表现行为不一致的数据集合。
6. 趋势和演变分析。

大数据分析平台需要具备的特性：高度可扩展、高性能、高度容错性、支持异构环境、较低的分析延迟、易用且开放接口、较低成本、向下兼容性。

InnoDB

首先给大家推荐一本复习MySQL的书《MySQL技术内幕InnoDB存储引擎》，可以说整个找工作的过程中，这本书我一直都在翻看，整本书有10个章节，如果你只是想突击面试的话，只需要着重看以下几个章节：第二章 InnoDB存储引擎、第五章 索引与算法、第六章 锁 、第七章 事务，这四个章节的内容在面试中是比较高频出现的。如果你想详细的学习MySQL，那么建议全文阅读学习。

InnoDB存储引擎

B+树的特性决定了非聚集索引插入的离散性。

插入缓冲：InnoDB开创性的设计了插入缓冲，对于非聚集索引的插入或更新操作，不是每一次直接插入索引页中。而是先判断插入的非聚集索引页是否在缓冲池中。如果是，则直接插入；如果不在，则放入到一个插入缓冲区中，然后以一定的频率执行插入缓冲和非聚集索引页子节点的合并操作，这是通常将多个插入合并到一个操作中（因为在一个索引页中）。

插入缓冲的条件：（1）索引是辅助索引。（2）索引不是唯一的。

**两次写：**在应用重做日志前，我们需要一个副本，当写入失效发生时，先通过副本来还原该页，在进行重做。

自适应哈希索引：监控对表上索引的查找，如果观察到建立哈希索引可以带来速度的提升，则建立哈希索引，所以称之为自适应的。

根据缓冲池的B+树建造，所以会很快。并且只会对某些页建立索引。

新版本的功能：

1. 快速索引重建
2. 更好的多核性能。
3. 新的页结构。
4. 页压缩功能。
5. 更好的BLOB处理能力。

索引与算法

如果索引太多，应用的性能就会受到影响；如果索引太少，对查询的性能也会产生影响。

常见索引：B+树索引、哈希索引。

B+树根据键值快速找到数据，且并不能找到具体的行，而是找到数据行所在的页，然后数据库通过把页读入内存，再在内存中进行查找，最后得到查找到的数据。

B+树索引在数据库中有一个特点就是其高扇区性，因此在数据库中B+树的高度一般在2-3层。

其分为聚焦索引和非聚焦索引，其区别是叶节点存放的是否是一整行的信息。

聚焦索引

聚焦索引就是按照每张表的主键构造一棵B+树，并且叶节点中存放着整张表的行记录数据，因此也让聚集索引的叶节点成为数据页。（每个数据页都通过一个双向链表链接）由于实际的数据也只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。

数据页上存放的是完整的行记录，而在非数据页的索引页中，存放的仅仅是键值以及指向数据页的偏移量，而不是一个完整的行记录。

聚集索引的存储并不是物理上的存储，而是逻辑上的存储，页之间和页内的记录存储都是双向链表链接。

非聚焦索引（辅助索引）

叶级别不包含行的全部数据。叶节点除了包含键值以外，每个叶级别中的索引行中还包含一个书签，该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。该书签就是对应行数据的聚集索引键。

辅助索引的存在并不影响聚集索引，故一张表可以有多个辅助索引。

B+树索引的管理

软件工程

软件工程博客

1.软件重用？

同一个函数重复用。

2.软件测试类型？

单元，集成，黑盒，白盒。

3.软件工程步骤

需求，设计，开发，测试。

4.UML

系统流程建模工具

5软件工程的认识？

运用工程化的方法管理软件开发。

开发步骤

1. 可行性研究
2. 需求分析（软件需求规格说明书）
3. 总体设计
4. 详细设计
5. 软件测试
6. 维护。

编译原理

编译原理博客

编译器概述

翻译器：能够完成将一种语言到另一种语言的保语义变换的软件。

编译器是一种翻译器，他的特点是目标语言比源语言低。

编译的各个阶段。

1. 词法分析器。（input：字符流）
2. 语法分析器。（记号流）
3. 语义分析器。（语法树）
4. 中间代码生成器（语法树）
5. 代码优化器（中间表示）
6. 代码生成器（中间表示）
7. 依赖于机器的代码优化器。（目标机器代码）

解释器是不同于编译器的另一种语言处理机器。解释器不想编译其那样通过翻译来生产目标程序，而是直接执行源程序所指定的计算。

词法分析

宏定义的预处理是在此阶段实现的。

不确定的有限自动机（NFA）有多个接收状态。

语法分析

上下文无关文法：字符V总可以被W替换，而无需考虑V的上下文。

最左推导：每一步都是代换句型中的最左侧非终结符的推导。

二义性：一个文法，如果存在某个句子不止一颗分析树与之对应，则称为这个文法是二义的。

消除二义性：消除左递归，消除左因子。

乔姆斯基（Chomsky)把文法分成四种类型，即0型，1型，2型和3型。0型的描述能力最强。

1. 0型文法也称短语文法，其能力相当于图灵机。
2. 1型文法也称上下文有关文法。
3. 2型即上下文无关文法。
4. 3型即正规文法。

自上而下分析的一般方法：即从文法开始符号（根节点）出发，自上而下，从左到右地输入串建立分析树。或者说，为输入串寻找最左推导。

LL（1）：其中第一个L表示从左到右，第二个L表示最左推导，1表示分析器每步动作向前查看一个字符。满足下面两个条件：

First集合、Follow集合。

句柄：句型的句柄是该句型中和一个产生式右部匹配的字串，归约中的一步字串。

栈的预测分析、移位-归约分析。

系统结构

基础+并行性开发

计算机系统结构和计算机组成的区别：

1. 作用不同。
   1. 系统结构是对计算机系统中各级界面的定义及其上下的功能分配，每一级都有自己的系统结构。
   2. 计算机组成指的是系统结构的逻辑实现。
2. 特征不同。
   1. 计算机体系结构是程序员看到的计算机的属性。
   2. 计算机组成着眼于各部件的功能和部件之间的联系。
3. 功能不同。
   1. 计算机体系结构主要研究软硬件功能分配和软硬件分界。
   2. 计算机组成要解决的是性能和价格的问题。

计算机实现指的是计算机组成的物理实现。

结论：计算机系统结构设计的任务就是进行软硬件功能的分配，确定传统机器级的 软硬件界面，但是作为“计算机系统结构”这门学科来讲，实际包括了体系结构和组成两个方面。

软件的可移植性：是指软件不修改或者只经过少量修改就可以由一台机器转移到另外一台及其上运行，同一软件可以运行到不同的环境中。主要技术有：统一高级语言、系列机（保证向后兼容，力争向上兼容）、模拟和仿真。

并行性的不同等级：

1. 指令内部
2. 指令之间
3. 任务或进程之间
4. 作业或程序之间

并行性的开发途径：时间重叠（指令分段）、资源重复（设置硬件）、资源共享（软件方法，如分时系统）。

数据表示、寻址方式和指令系统

数据表示：机器硬件识别和引用的数据类型。

下溢的处理方法：截断法、舍入法、恒置1法、查表舍入法。

寻址方式面向主存、寄存器、堆栈。

指令操作码的优化：定长码、可扩展码、哈夫曼编码

标量处理机

加快标量处理机的机器语言的解释是计算机组成设计 的基本任务。可以从两方面实现：（1）通过选用更高速的器件，更好的运算方法，提高指令内各微操作的并行程度。（2）通过控制机构同时解释两条、多条或整段程序的方式。流水和重叠是其中常用的方式。

指令的重叠解释是在解释第K条指令的操作结束之前，就可以开始解释第K+1条指令。（取指令、分析、执行）

推迟“分析k+1”和设置“相关专用通路”是解决重叠方式相关处理的两种基本方法。前者以降低重叠方式为代价，后者以增加设备为代价。

流水的分类：

1. 按照处理的级别：部件级、处理机级、系统级
2. 按具有功能的多少：单功能和多功能流水线
3. 多功能的连接方式：静态流水线和动态流水线。
4. 机器所具有的数据表示：标量流水线、向量流水机。
5. 各功能段是否有反馈：线性流水和非线性流水。

流水线中经过的最长子过程成为瓶颈子过程。

解决方法：（1）瓶颈子过程再细分（2）瓶颈子过程并联。

加速比：非流水时间/流水总时间

效率：面积的比值。

语言和算法基础

可以出一道面试题：栈里面的元素在内存中是连续分布的么？

这个问题有两个陷阱：

• 陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
• 陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

C++读取带空格的字符串：‘getline(cin, s)’

基本认知

1. 系统大小端是什么？如何检测
   A: 大端是低地址存高位， 小端是低地址存放低位。网络传输都是采用大字节。

   //大端是从大到小。 big2end .                            //方法一：联合体union判断第一位
   int CheckSystem()
   {union Check{//定义两个变量（i和ch），这两个变量共用同一块地址空间，并且两个变量的首地址是一样的int i;       char ch;}c;// 将1放到i的低位去c.i = 1;//倘若ch的最低位是1，则证明机器为小端存储模式；否则反之return (c.ch == 1);
   }
   

2. 程序编译链接的过程？

   预处理（预处理如 #include、#define 等预编译指令，生成 .i 或 .ii 文件）
   编译（编译器进行词法分析、语法分析、语义分析、中间代码生成、目标代码生成、优化，生成 .s 文件）
   汇编（汇编器把汇编码翻译成机器码，生成 .o 文件）
   链接（链接器对未分配的变量分配绝对地址， 这个过程主要是把各个模块之间相互引用部分处理好，地址对应上。 最后生成 .out 文件）

3. makefile的作用？

   makefile 可以决定程序的编译流程， 通过脚本极大简化的编译的复杂程度。此外单纯的手写makefile还是比较难，因此很多人通过cmake去生成makefile。 但是一些大型开源项目如果有问题一定是要通过makefile去分析问题的。

4. 堆和栈的区别？

   1.申请方式不同。栈由系统自动分配。堆由程序员手动分配。

   2.申请大小限制不同。栈顶和栈底是之前预设好的，大小固定，可以通过ulimit -a查看，由ulimit -s修改。堆向高地址扩展，是不连续的内存区域，大小可以灵活调整。

   3.申请效率不同。栈由系统分配，速度快，不会有碎片。堆由程序员分配，速度慢，且会有碎片.

5. 引用的头文件和库的区别.

   引用的头文件会去库里面找相关的函数定义，如果找不到的话会在本项目中找，如果没有的话就报错。 注意cpp头文件的引用和python的import作用是一样的

6. 程序运行的原理与分区.

   每个程序会在内存中加载为进程， 进程的虚拟地址空间是由大量的准确定义的区构成，linux从低地址到高地址依次为：程序代码和数据；堆；共享库；栈；内核虚拟存储器。不同的程序代码结构相同，只不过这几个地方的内容不一样。
   栈：存放函数的局部变量、函数参数、返回地址等，由编译器自动分配和释放。
   堆：动态申请的内存空间，就是由 malloc 分配的内存块，由程序员控制它的分配和释放，如果程序执行结束还没有释放，操作系统会自动回收。
   全局区/静态存储区（.bss 段和 .data 段）：存放全局变量和静态变量，程序运行结束操作系统自动释放，在 C 语言中，未初始化的放在 .bss 段中，初始化的放在 .data 段中，C++ 中不再区分了。
   常量存储区（.data 段）：存放的是常量，不允许修改，程序运行结束自动释放。
   代码区（.text 段）：存放代码，不允许修改，但可以执行。编译后的二进制文件存放在这里

预处理和头文件

1. 头文件是用来声明函数的， 一些函数需要被其他cpp调用，不能一直都直接在其他cpp里面写吧，所以打包到放到一起，方便调用，也方便让人知道函数是在哪里的。 此外头文件的#pragma one 是防止多次调用的。 或者用ifndef endif 去防止多次调用。 <> 是在标准头文件目录中搜索， " " is search in 自定义的。 cpp 标准库不用加.h， c标准库要加.h 。 注意 < iostream > 和 “iostream.h” 其实是不同的头文件，一个是c++，另外一个是c的。
2. #ifdef _cplusplus是预定义的宏，可以解决c语言不支持重载问题。
3. using namespace 可以防止变量重复。想要直接使用标准库的东西必须启动stl空间。 c语言中的iostream.h 直接是全局的。 cin ,cout 是已经实例化的对象。

设计技巧：

1. 最好不要在头文件里面加那么using namespace, 容易冲突。
2. 宏定义如果是表达式要加（）, 不然可能会出现歧义错误。如果是带参数的宏定义要在每个参数加上（），不然传入参数如果是表达式会得到不一样的答案。
3. 一般解决bug时候先从最前面，因为bug有传递效应，解决一个就编译一下。
4. #ifdef _DEBUG_可以用来定义调试和发行版本， 在发行版本的时候把def __DEBUG__去掉， 不打印debug信息。

面试题：

1. 宏定义和函数有何区别？

   • 宏在编译时完成替换，之后被替换的文本参与编译，相当于直接插入了代码，运行时不存在函数调用，执行起来更快；函数调用在运行时需要跳转到具体调用函数。
   • 宏函数属于在结构中插入代码，没有返回值；函数调用具有返回值。
   • 宏函数参数没有类型，不进行类型检查；函数参数具有类型，需要检查类型。

2. 宏定义和const区别？

   • 宏替换发生在编译阶段之前,是预编译指令，属于文本插入替换；const作用发生于编译过程中。
   • 宏不检查类型；const会检查数据类型。
   • 宏定义的数据没有分配内存空间，只是插入替换掉；const定义的变量只是值不能改变，但要分配内存空间。

3. 头文件和源文件存放标准？

   其实代码完全可以写到一个文件中（cpp, .h），用cpp是为了接口分离。

   include<>的从系统库加载
   include""从当前工作路径加载(失败了再转到系统路径)

C++11

1998 年，C++ 标准委员会发布了第一版 C++ 标准，并将其命名为 C++ 98 标准。

2011 年，新的 C++ 11 标准诞生，用于取代 C++ 98 标准。

变量

1. 在 C++ 中，有两种简单的定义常量的方式：#define和 const。

2. C++ 提供了以下两种类型的字符串:C 风格字符串(字符串数组， 以\0结尾)， 和C++ 引入的 string 类来操作。二者都可以，但是第二个更为方便，第一个要手动或者调用stl实现字符串拼接等功能。字符统计中，strlen不统计\0, 但是sizeof统计。

3. 需要注意有些没有图符的常量，例如转义字符和控制字符。

4. 由于语法的混乱，很多人分不清初始化和赋值，二者其实是不同的，初始化= 创建变量+ 赋值。

5. 大型项目中，变量可以在多个文件extern声明，但是定义只有一次， 这里切记不要重复定义

6. 一个变量只有几种可能的值，可以定义为枚举(enumeration)类型。

   enum color { red, green, blue } c;
   c = blue;
   

7. 左值和右值定义： 左值（l-value）可以出现在赋值语句的左边或者右边，比如变量；右值（r-value）只能出现在赋值语句的右边，比如常量。区分左值右值的关键是看是否能够再现。

8. c++类型限定符 :const。 const 类型的对象在程序执行期间不能被修改，生存周期只在本文件内，非要访问，必须在指定const前加extern。非const变量默认为extern，即可被其它文件extern调用，但要使const变量能够在其它的文件中访问,必有显示指定为extern。

9. C++11新标准规定，允许将变量声明为constexpr类型以便由编译器来验证变量的值是否是一个常量的表达式。

10. static： 不需要在每次它进入和离开作用域时进行创建和销毁。因此，使用 static 修饰局部变量可以在函数调用之间保持局部变量的值。 如果只在本文件使用的全部变量要声明成static， 这样可以防止报错和消耗， 全局变量是很危险和难以阅读的一个变量。 static声明的函数内变量虽然具有全局周期，但是活动范围只能是本文件内部。（类方法）

11. thread_local (C++11) ：说明符声明的变量仅可在它在其上创建的线程上访问。 变量在创建线程时创建，并在销毁线程时销毁。每个线程都有其自己的变量副本。

12. 高级数据结构： 结构体和类是我们常用的。

设计技巧

1. 请注意，把常量定义为大写字母形式。
2. 一般整形计算用int , 浮点运算用float。
3. 建议：初始化所有指针。
4. 多个函数或者类共同计数的变量可以用static， 避免全局变量太多，影响可读性。静态数据成员就是为了让同类的对象通信的。
5. malloc() 函数在 C 语言中就出现了，在 C++ 中仍然存在，但建议尽量不要使用 malloc() 函数。new 与 malloc() 函数相比，其主要的优点是，new 不只是分配了内存，它还创建了对象。
6. 中文的编码要用wchar* 而不是char* 去编码。

面试题

1. 变量声明和定义区别？

   • 声明仅仅是把变量的声明的位置及类型提供给编译器，并不分配内存空间；定义要在定义的地方为其分配存储空间。
   • 相同变量可以再多处声明（外部变量extern），但只能在一处定义。

2. strlen和sizeof区别？

   sizeof是运算符，并不是函数，结果在编译时得到而非运行中获得；strlen是字符处理的库函数。

   sizeof参数可以是任何数据的类型或者数据（sizeof参数不退化）；strlen的参数只能是字符指针且结尾是’\0’的字符串。

   因为sizeof值在编译时确定，所以不能用来得到动态分配（运行时分配）存储空间的大小。

3. 数组和指针的区别？

   数组在传参的时候会退化成指针，无法知道其尺寸。 因此我们还会传另外一个size 到函数中。

   数组名不是真正意义上的指针，可以理解为常指针，所以数组名没有自增、自减等操作。

   当数组名当做形参传递给调用函数后，就失去了原有特性，退化成一般指针，多了自增、自减操作，但sizeof运算符不能再得到原数组的大小了。

4. 请你说一下static , voliate , inline , const ，register 的作用？

   static : C++的static可以修饰类成员（静态成员变量和静态成员函数），静态成员变量和静态成员函数不属于任何一个对象，是所有类实例所共有。还可以延长变量的声明周期到程序结束，还有对于静态全局变量，相对于全局变量其可见范围被缩小，只能在本文件中可见；修饰函数时作用和修饰全局变量相同，都是为了限定访问域。
   static的数据记忆性可以满足函数在不同调用期的通信，也可以满足同一个类的多个实例间的通信。
   未初始化时，static变量默认值为0。
   voliate是不要内存优化， volatile定义变量的值是易变的，每次用到这个变量的值的时候都要去重新读取这个变量的值，而不是读寄存器内的备份。多线程中被几个任务共享的变量需要定义为volatile类型。
   register是将变量声明成寄存器，加速。
   inline是展开函数成语句。作为函数定义的关键字，说明该函数是内联函数。内联函数会将代码块嵌入到每个调用该函数的地方。内联函数减少了函数的调用，使代码执行的效力提高，但是会增加目标代码的大小，最终会使程序的代码段占有大量的内存。

5. malloc和new的区别？

   malloc和free是标准库函数，支持覆盖；new和delete是运算符，并且支持重载。

   malloc仅仅分配内存空间，free仅仅回收空间，不具备调用构造函数和析构函数功能，用malloc分配空间存储类的对象存在风险；new和delete除了分配回收功能外，还会调用构造函数和析构函数。

   malloc和free返回的是void类型指针（必须进行类型转换），new和delete返回的是具体类型指针。

6. delete和delete[]区别？

   • delete只会调用一次析构函数。
   • delete[]会调用数组中每个元素的析构函数。

7. 常量指针和指针常量区别？

   • 常量指针是一个指针，读成常量的指针，指向一个只读变量。如int const * p或const int p。
   • 指针常量是一个不能给改变指向的指针。如int *const p。

8. struct 和 union 的区别

   联合体和结构体都是由若干个数据类型不同的数据成员组成。使用时，联合体只有一个有效的成员；而结构体所有的成员都有效。

表达式和语句

本小结包含运算符的使用， 除了一些基本的运算符， 对于一些非内置数据类型还有一些标准库实现的运算符。

1. 遍历字符串：使用范围for（range for）语句： for (auto c: str)，或者 for (auto &c: str)使用引用直接改变字符串中的字符。（c++11）

2. Lambda 表达式：本质上与函数声明非常类似。为什么要用它呢？

   a. 有些时候函数无法使用的地方，lambda表达式依然可以使用，而且更方便简洁
   b. 函数要起名，但这是一个很困难的事情，而且容易重名，但是lambda表达式就不太是一个问题。
   c. lambda表达式只需要一行，增强了代码的可读性。lambda表达式表示一个可调用的代码单元，可以理解成是一个未命名的内联函数。最简单的 Lambda后面不加 () 的 Lambda 表达式相当于函数指针，加上 () 就相当于调用这个 Lambda 函数。

   int main(void) {
   // Function point
   [](){ cout << "Hello World!" << endl; };
   // Call function
   [](){ cout << "Hello World!" << endl; }();
   return 0;
   }
   

3. 异常可以避免程序的崩溃， 在一些关键的地方可以加入异常处理。

4. for(const auto &iter : m) 相比较for(iter =m.begin(); iter!=m.end();i++ )的区别？

   A： 第一个更为简便一些，auto和foreach都是cpp11的语法。 引用也更为降低空间消耗。 开发中第一个是经常使用的。

函数

1. 如果我们不知道自己传参的具体数量， c++11中提供了initializer_list 去代指后续一系列相同type的数据类型。使用方法如下：

   void err_msg(ErrCode e, initializer_list<string> il){cout << e.msg << endl;for (auto bed = il.begin(); beg != il.end(); ++ beg)cout << *beg << " ";cout << endl;
   }
   err_msg(ErrCode(0), {"functionX", "okay});

2. 有返回值函数: return语句的返回值的类型必须和函数的返回类型相同，或者能够隐式地转换成函数的返回类型。 不要返回局部对象的引用或指针,函数调用结束之后会被销毁。

3. 分离式编译（Separate Compilation）分离式编译允许我们把程序按照逻辑关系分割到几个文件中去，每个文件独立编译。这一过程通常会产生后缀名是*.obj或.o*的文件，该文件包含对象代码（object code）。之后编译器把对象文件链接（link）在一起形成可执行文件。(gcc 的时候把所有文件链接一起即可)

4. 函数指针: 要想声明一个可以指向某种函数的指针，只需要用指针替换函数名称即可。

5. 在参数固定但是类型不同的时候使用函数模板更方便。而不是函数重载

6. 由于函数调用时候是需要跳转的，这样有时候也很费时间，因此函数要是那些重复调用的功能。 此外如果经常调用，要用inline去优化展开。 避免来回跳转。inline函数应该在头文件中定义。

面试题

Q1 : 函数重载和函数模板的区别？

函数模板适用于不同类型，数量相同的函数， 函数重载适用于不同类型的，数量不相同的情景。
Q2 : 形参和实参的区别？

形参是函数调用时候才启动的， 实参是传入给形参的。 如果形参是引用，那么就不用拷贝了。
Q3 . 函数传参的时候要注意什么？

需要注意如果是数组就得传入一下大小， 如果数据量大考虑引用传入， 如果函数不改变其内容一定要使用const传入。
Q 函数调用的过程

比较复杂，here

Q重载、重写、隐藏的区别

• 重写就是多态重写， 隐藏就是继承覆盖

Q : callback 定义？

一般函数:function a(int a, String b):接收的参数是一般类型.特殊函数:function b(function c):接收的参数是一个函数,c这个函数就叫回调函数.你也可以这么理解:本质区别是,一般一个函数调用另一个函数,被调用的函数是出现在方法体当中,而回调函数比较特殊,它是出现在参数列表当中.也就是说,当调用的时候,需要从其他地方拿到这个(回调)函数,以参数的形式传入.一般的函数调用,可以称作是调用.然而另一种,执行时才将某个函数传入再调用的调用方式,就叫**“回调”,**当然,不要纠结于翻译的准不准,主要需要理解本质是什么.
————————————————
版权声明：本文为CSDN博主「今天又是充满希望的一天」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liupeng19970119/article/details/112220840

类

1. 定义在类内部的函数是自动内联的。在类外部定义的成员函数，也可以在声明时显式地加上 inline。
2. 静态成员函数是为了处理静态成员变量， 因为静态成员变量没有this指针。
3. 为了保证封装性， 我们一般是类声明放在.h , 类的成员实现放在另外一个文件， 这样可以做到接口和实现分离。接口是指可以访问到的成员， 实现是指整个类的实现。 我们说的接口和实现分离就是为了让开发者调用类希望展示出来的接口。
4. 类的静态成员函数中只能访问静态成员变量或者静态成员函数，不能将静态成员函数定义成虚函数
5. 空类的大小是一个特殊情况，空类的大小为 1，当用 new 来创建一个空类的对象时，为了保证不同对象的地址不同，空类也占用存储空间。
6. 一个派生继承了所有的基类方法，除了基类的构造函数、析构函数和拷贝构造函数， 基类的重载运算符和友元函数。派生类的构造函数要对基类的成员，新增的数据成员和自己包含的对象成员进行构造。
7. 如果派生类在虚函数声明时使用了’override’描述符，那么该函数必须重载其基类中的同名函数，否则代码将无法通过编译。
8. final 代表这个类不能被继承。
9. 带纯虚函数的类叫抽象类，这种类不能直接生成对象，而只有被继承，并重写其虚函数后，才能使用。抽象类被继承后，子类可以继续是抽象类，也可以是普通类。只含有纯虚函数的类叫做接口类。
10. 类成员函数和构造析构函数是不占用对象的空间的， 他们都是公共的地址。 但是虚函数是占用的。
11. 虚函数指针：在含有虚函数类的对象中，指向虚函数表，在运行时确定。
    虚函数表：在程序只读数据段（.rodata section，见：目标文件存储结构），存放虚函数指针，如果派生类实现了基类的某个虚函数，则在虚表中覆盖原本基类的那个虚函数指针，在编译时根据类的声明创建。
12. 基类通常都应该定义一个虚析构函数，即使该函数不执行任何实际操作也是如此。

面试问题：

Q: public/protected/private的区别？

• public的变量和函数在类的内部外部都可以访问。
• protected的变量和函数只能在类的内部和其派生类中访问。
• private修饰的元素只能在类内访问。

Q2 : 类和结构体的区别？

• 类和结构区别是： 首先struct 默认访问是public, class默认访问是private.
• 在c语言中struct是不能写function, 但是c++语言中可以。

Q: C++空类有哪些成员函数?

• 首先，空类大小为1字节。
• 默认函数有：构造函数 析构函数 拷贝构造函数 赋值运算符

Q： 哪几种情况必须用到初始化成员列表{}？

• 初始化一个const成员。
• 初始化一个reference成员。
• 调用一个基类的构造函数，而该函数有一组参数。
• 调用一个数据成员对象的构造函数，而该函数有一组参数。

Q : 右值引用的作用？

c++11中 右值引用是用来支持转移语义的。转移语义可以将资源 ( 堆，系统对象等 ) 从一个对象转移到另一个对象，这样能够减少不必要的临时对象的创建、拷贝以及销毁，能够大幅度提高 C++ 应用程序的性能。临时对象的维护 ( 创建和销毁 ) 对性能有严重影响。

Q3. 动态多态和静态多态的区别？

• 动态多态是在运行时实现的， 他是通过virtual 。 静态多态在编译时候实现，通过重载。

Q7 : 虚继承和虚函数的区别？

在这里我们可以对比虚函数的实现原理：他们有相似之处，都利用了虚指针（均占用类的存储空间）和虚表（均不占用类的存储空间）。
虚基类依旧存在继承类中，只占用存储空间；虚函数不占用存储空间。
虚基类表存储的是虚基类相对直接继承类的偏移；而虚函数表存储的是虚函数地址。Q Q: 多重继承时会出现什么状况？如何解决？

• 使用虚继承的目的：保证存在命名冲突的成员变量在派生类中只保留一份，即使间接基类中的成员在派生类中只保留一份。在菱形继承关系中，间接基类称为虚基类，直接基类和间接基类之间的继承关系称为虚继承。
• 一个虚基类的引用可以引用一个派生类的对象，反之则不行，无论在强制类型转换中指定什么路径，一个虚基类的指针或引用不能转换为派生类的指针或引用。

————————————————
版权声明：本文为CSDN博主「今天又是充满希望的一天」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liupeng19970119/article/details/112220840

关键字

auto

可以进行自动类型推导。

auto 的一个典型应用场景是用来定义 stl 的迭代器。还可以用在泛型编程中。

限制：

1. 使用 auto 的时候必须对变量进行初始化，这是 auto 的限制之一。
2. auto 不能在函数的参数中使用。
3. auto 不能作用于类的非静态成员变量（也就是没有 static 关键字修饰的成员变量）中。
4. auto 关键字不能定义数组
5. 不能作为模板参数

decltype

auto的补充。

同样是在编译其用来类型推导的。另外，auto 要求变量必须初始化，而 decltype 不要求。

decltype(exp) varname; // exp必须有类型

• 如果 exp 是一个左值，或者被括号( )包围，那么 decltype(exp) 的类型就是 exp 的引用；假设 exp 的类型为 T，那么 decltype(exp) 的类型就是 T&。
• 我们知道，auto 只能用于类的静态成员，不能用于类的非静态成员（普通成员），如果我们想推导非静态成员的类型，这个时候就必须使用 decltype 了。

返回值后置：

template <typename T, typename U>
auto add(T t, U u) -> decltype(t + u)
{return t + u;
}

结合auto用来推导返回值类型。返回值类型后置语法，是为了解决函数返回值类型依赖于参数而导致难以确定返回值类型的问题。(C++参数是前置语法)

using

使用using来定义别名：

// 重定义unsigned int
typedef unsigned int uint_t;
using uint_t = unsigned int;
// 重定义std::map
typedef std::map<std::string, int> map_int_t;
using map_int_t = std::map<std::string, int>;

从上面的对比中可以发现，C++11 的 using 别名语法比 typedef 更加清晰。

C++标准库

STL大体分为六大组件，分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器。

容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据。
算法：各种常用的算法，如sort、find、copy、for_each等
迭代器：扮演了容器与算法之间的胶合剂。 提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。
仿函数：行为类似函数，可作为算法的某种策略。
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
空间配置器：负责空间的配置与管理。 我们可以把这些容器看成python的基本类型， 这样的话使用时候就会有很多通用的思路。

Q1 : map和set是用什么实现的？ 为什么要这样做？

使用红黑树实现的，这样会自动排序。 然后我们去查找插入删除的时候就会非常快。map中所有元素都是pair, pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）所有元素都会根据元素的键值自动排序。 map 是基于红黑树实现的map结构（实际上是map, set, multimap，multiset底层均是红黑树），不仅增删数据时不需要移动数据，其所有操作都可以在O(logn)时间范围内完成。另外，基于红黑树的map在通过迭代器遍历时，得到的是key按序排列后的结果，这点特性在很多操作中非常方便。RBTree本身也是二叉排序树的一种，key值有序，且唯一。必须保证key可排序。
set所有元素都会在插入时自动被排序. set/multiset属于关联式容器，底层结构是用二叉树实现。 set不允许容器中有重复的元素 .multiset允许容器中有重复的元素. 对于自定义数据类型，set必须指定排序规则才可以插入数据.Q: 非关联容器的定义？
哈希函数存储的。

其他

1. C++11 支持为函数模板中的参数设置默认值，在实际使用过程中，我们可以选择使用默认值，也可以尝试由编译器自行推导得到，还可以亲自指定各个模板参数的类型。

2. 智能指针的作用？

   智能指针的作用是管理一个指针，因为存在以下这种情况：申请的空间在函数结束时忘记释放，造成内存泄漏。使用智能指针可以很大程度上的避免这个问题，因为智能指针就是一个类，当超出了类的作用域是，类会自动调用析构函数，析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间，不需要手动释放内存空间。

   unique_ptr<string> p3 (new string ("auto"));   //#4
   unique_ptr<string> p4；                       //#5
   p4 = p3;//此时会报错！！shared_ptr实现共享式拥有概念。多个智能指针可以指向相同对象，该对象和其相关资源会在“最后一个引用被销毁”时候释放。从名字share就可以看出了资源可以被多个指针共享，它使用计数机制来表明资源被几个指针共享。可以通过成员函数use_count()来查看资源的所有者个数。除了可以通过new来构造，还可以通过传入auto_ptr, unique_ptr,weak_ptr来构造。当我们调用release()时，当前指针会释放资源所有权，计数减一。当计数等于0时，资源会被释放。weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用，不会增加对象的引用计数，和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr。
   

   再次强调，weak_ptr 类型指针不会导致堆内存空间的引用计数增加或减少。

3. Q: 说一说c++11中四种cast转换?
   -static_cast, dynamic_cast, const_cast, reinterpret_cast

   1、const_cast用于将const变量转为非const
   2、static_cast用于各种隐式转换，比如非const转const，void*转指针等, static_cast能用于多态向上转化，如果向下转能成功但是不安全，结果未知；
   3、dynamic_cast用于动态类型转换。只能用于含有虚函数的类，用于类层次间的向上和向下转化。只能转指针或引用。向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常。要深入了解内部转换的原理。它通过判断在执行到该语句的时候变量的运行时类型和要转换的类型是否相同来判断是否能够进行向下转换。
   4、reinterpret_cast几乎什么都可以转，比如将int转指针，可能会出问题，尽量少用；
   5、为什么不使用C的强制转换？C的强制转换表面上看起来功能强大什么都能转，但是转化不够明确，不能进行错误检查，容易出错。

   野指针：释放内存的结果只是改变了内存中存储的数据，使得该内存存储的内容变成了垃圾，指向垃圾内存的指针，就被称为野指针。

   C语言的内存映像：

算法

蓄水池算法（公平性）：

1. 假设数据序列的规模为 n，需要采样的数量的为 k。

2. 首先构建一个可容纳 k 个元素的数组，将序列的前 k 个元素放入数组中。

3. 然后从第 k+1 个元素开始，以 k/n 的概率来决定该元素最后是否被留在数组中（每进来一个新的元素，数组中的每个旧元素被替换的概率是相同的）。 当遍历完所有元素之后，数组中剩下的元素即为所需采取的样本。

当处理完每一个数据之后，每蓄水池中的每一个数据都是k/n的概率获得的。

核心代码：

void getRandom(int *num, int k, int n) {if (k >= n) return ;for (int i = k; i < n; i++) {int ind = rand() % i;if (ind < k) num[ind] = num[i];}
}

专业性问题

大数据及数据挖掘

A*算法：

1. 把起点加入 open list 。

2. 如下过程：

   a. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。

   b. 把这个节点移到 close list 。

   c. 对当前方格的 8 个相邻方格的每一个方格:

   ​ ◆ 如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。

   ​ ◆ 如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记 录该方格的 F ， G 和 H 值。

   ​ ◆ 如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。

   d. 停止，当你

   ​ ◆ 把终点加入到了 open list 中，此时路径已经找到了，或者

   ​ ◆ 查找终点失败，并且 open list 是空的，此时没有路径。

3. 保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

openlist:需要（可能）经过的节点。

closelist:不可达的或者已经走过的节点。

F = G + H。

G=表示从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。

H = 从指定的方格移动到终点 B 的估算成本。上下左右的放个代价为10，则斜角的代价为14（勾股定理的近似值）

1. 什么是数据隐藏？

   理解为面向对象中的封装，及对数据和函数操作捆绑一起，只允许对象内部访问，不允许外部访问，提高了安全性。

2. 行列混合存储数据库。

   1. ​ 行式存储数据库及常见的关系数据库。其写入是一次性完成的，消耗时间比列存储少，并且能够保证数据的完整性。缺点是：读取数据时会出现冗余。
   2. 列式存储与行相反，读取时没有数据冗余。每一列是独立存储的，且知道其存储类型，经过特殊处理，可以节省存储空间。其数据就是索引。

3. 常见的存储方式有哪几种，论述以下各自的优劣性。

   关系型和非关系型。

   非关系型数据库：

   1. 性能NOSQL是基于键值对的，可以想象成表中的主键和值的对应关系，而且不需要经过SQL层的解析，所以性能非常高。

   2. 可扩展性同样也是因为基于键值对，数据之间没有耦合性，所以非常容易水平扩展。

   关系型数据库：

   1. 复杂查询可以用SQL语句方便的在一个表以及多个表之间做非常复杂的数据查询。
   2. 事务支持使得对于安全性能很高的数据访问要求得以实现。对于这两类数据库，对方的优势就是自己的弱势，反之亦然。

4. SQL注入:SQL注入是比较常见的网络攻击方式之一，它不是利用操作系统的BUG来实现攻击，而是针对程序员编写时的疏忽，通过SQL语句，实现无账号登录，甚至篡改数据库。

5. 数据挖掘的应用。

图像算法相关

1. 机器人的定义是什么？人工智能是什么？

   机器人（Robot）是一种能够半自主或全自主工作的智能机器。
   

   机器从“特定的”大量数据中总结规律，归纳出某些“特定的知识”，然后将这种“知识”应用到现实场景中去解决实际问题。

   

   1. 人工智能的本质是工具，需要人来用它
   2. 人工智能替代的不是人，而是某些工作环节

2. 人工智能的避障算法算法是什么？

   传统的导航避障方法如可视图法、栅格法、自由空间法等算法对障碍物信息己知时的避障问题处理尚可;

   遗传算法、神经网络算法、模糊算法等(对障碍物信息未知)

3. 栅栏和矢量图的区别。

   栅栏	矢量图
   规则的阵列，各个像元互不影响	一些坐标组成的对象，他们之间联系密切
   又称位图，是像素的集合	与分辨率无关，无限放大不模糊
   优点为数据结构简单，便于空间分析和地表模拟，现势性较强	数据结构复杂，多边形叠加分析比较困难

4. 解释机器学习。

5. 神经网络中的激活函数。

6. 为什么要有激活函数？有哪些激活函数？

7. 过度拟合有哪些解决办法？

   （训练集适合，但是过犹不及，在其他数据上效果不是很好）

   1. 增加数据集。
   2. 添加噪音
   3. 采用合适的模型
   4. 正则化 。又称权重衰减，具体做法是将权值的大小加入到损失函数中，在实际使用中分为 L1 正则与 L2 正则
   5. 可变的学习率。

8. 人脸识别用的是什么技术？

9. K均值的K指的是什么？

   聚类算法，k均值仅限于具有中心（质心）概念的数据。K是K个簇，初试选择质心的数量。

   k均值的基本算法如下：首先，随机选择k个初始质心，其中k即所期望的簇的个数。每个点指派到最近的质心，而指派到一个质心的点集为一个簇。然后，根据指派到簇的点，更新每个簇的质心。重复指派和更新步骤，直到簇不发生变化，或等价地，直到质心不发生变化。

10. 为什么有泰勒展开式？对计算机学科的意义是什么？

    用近似的效果来代替原有无法求得的结果。

11. 特征值是什么？

12. 双聚类启发式搜索k均值聚类。

13. 有监督学习和无监督学习的区别：

    有监督学习和无监督学习

    简单的归纳就是，是否有监督（supervised），就看输入数据是否有*标签*（label）。输入数据有标签，则为有监督学习；没标签则为无监督学习

    监督学习是指数据集的正确输出已知情况下的一类学习算法。因为输入和输出已知，意味着输入和输出之间有一个关系，监督学习算法就是要发现和总结这种“关系”。

    监督算法常见的有：

    • 线性回归
    • 神经网络
    • 决策树
    • 支持向量机
    • KNN(分类算法)
    • 朴素贝叶斯算法

    无监督学习我们基于数据中的变量之间关系利用聚类算法发现这种内在模式或者结构。

    无监督算法有：

    • 主成分分析法（PCA）
    • K-means
    • 异常检测法
    • 自编码算法
    • 深度信念网络
    • 赫比学习法
    • 生成式对抗网络
    • 自组织映射网络

    半监督学习有监督和无监督中间包含的一种学习算法是半监督学习（semi-supervised learning）。对于半监督学习，其训练数据的一部分是有标签的，另一部分没有标签，而没标签数据的数量常常极大于有标签数据数量（这也是符合现实情况的）。

14. 蚁群算法。

15. 计算机视觉的看法。

    人的大脑皮层， 有差不多 70% 都是在处理视觉信息。 是人类获取信息最主要的渠道，没有之一。

    目的：看懂图片里的内容。

    原理：构造多层的神经网络，较低层的识别初级的图像特征，若干底层特征组成更上一层特征，最终通过多个层级的组合，最终在顶层做出分类。

    两大挑战：计算量大、特征难以提取。

    方法：CNN（卷积神经网络）：

    ​ （1）有效的提取图片里的特征（卷积核）

    ​ （2）将海量数据（在不影响特征值提取的情况下）进行降维。

    计算机视觉的八大分类：

    1. 图像分类（人脸识别）
    2. 目标检测（找出目标位置）
    3. 语义分割（理解每个像素是什么）
    4. 实例分割（汽车分类）
    5. 视频分类
    6. 人体关键点检测
    7. 场景文字识别（车牌识别）
    8. 目标跟踪

16. 卷积神经网络（CNN）

    一文看懂卷积神经网络

    典型的 CNN 由3个部分构成：

    1. 卷积层（得到每个小区域的特征值）
    2. 池化层
    3. 全连接层
    4. 卷积层负责提取图像中的局部特征；池化层用来大幅降低参数量级(降维)；全连接层类似传统神经网络的部分，根据不同任务输出我们想要的结果。

    作用：

    1. 图片分类、检索
    2. 目标定位检测
    3. 目标分割
    4. 人脸识别
    5. 骨骼识别

    

17. Hadoop：是一个大数据框架。

    （Hadoop之父Doug Cutting的儿子的玩具大象的名字叫Hadoop，所以其Logo是一个黄色的大象）

    Hadoop的核心，说白了，就是HDFS和MapReduce。HDFS为海量数据提供了存储，而MapReduce为海量数据提供了计算框架。

    

区块链

区块链，就是一个又一个区块组成的链条。每一个区块中保存了一定的信息，它们按照各自产生的时间顺序连接成链条。这个链条被保存在所有的服务器中，只要整个系统中有一台服务器可以工作，整条区块链就是安全的。这些服务器在区块链系统中被称为节点，它们为整个区块链系统提供存储空间和算力支持。如果要修改区块链中的信息，必须征得半数以上节点的同意并修改所有节点中的信息，而这些节点通常掌握在不同的主体手中，因此篡改区块链中的信息是一件极其困难的事。相比于传统的网络，区块链具有两大核心特点：数据难以篡改和去中心化。基于这两个特点，区块链所记录的信息更加真实可靠，可以帮助解决人们互不信任的问题。

特征：

去中心化。区块链技术不依赖额外的第三方管理机构或硬件设施，没有中心管制，除了自成一体的区块链本身，通过分布式核算和存储，各个节点实现了信息自我验证、传递和管理。去中心化是区块链最突出最本质的特征 。

开放性。区块链技术基础是开源的，除了交易各方的私有信息被加密外，区块链的数据对所有人开放，任何人都可以通过公开的接口查询区块链数据和开发相关应用，因此整个系统信息高度透明 。

独立性。基于协商一致的规范和协议(类似比特币采用的哈希算法等各种数学算法)，整个区块链系统不依赖其他第三方，所有节点能够在系统内自动安全地验证、交换数据，不需要任何人为的干预 。

安全性。只要不能掌控全部数据节点的51%，就无法肆意操控修改网络数据，这使区块链本身变得相对安全，避免了主观人为的数据变更 。

匿名性。除非有法律规范要求，单从技术上来讲，各区块节点的身份信息不需要公开或验证，信息传递可以匿名进行。

硬件相关

1. 单片机为什么叫单片机？
2. 单片机的引导过程。
3. PLC和FPGA的中文名称。
4. 放大器的设计原理。
5. 小信号和大信号的区别。
6. 8255如何用？
7. CPU工作模式。
8. 嵌入式系统和普通的系统区别在哪里？
9. 嵌入式系统用什么语言写？什么是嵌入式？
10. DMA控制器是主设备还是从设备。
11. 编译原理相关内容。

AI

NLP

自然语言处理（NLP）就是在机器语言和人类语言之间沟通的桥梁，以实现人机交流的目的

自然语言的五个难点：

1. 语言的多样性
2. 语言的歧义性
3. 语言的鲁棒性（健壮性）
4. 语言的知识依赖
5. 语言的上下文

决策树

这是一种基于 if-then-else 规则的有监督学习算法，决策树的这些规则通过训练得到，而不是人工制定的。

决策树是最简单的机器学习算法，它易于实现，可解释性强，完全符合人类的直观思维，有着广泛的应用。

决策树学习的三个步骤：

特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。

在特征选择中通常使用的准则是：信息增益。

决策树生成

选择好特征后，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。

决策树剪枝

剪枝的主要目的是对抗“过拟合”，通过主动去掉部分分支来降低过拟合的风险。

优点

• 决策树易于理解和解释，可以可视化分析，容易提取出规则；
• 可以同时处理标称型和数值型数据；
• 比较适合处理有缺失属性的样本；
• 能够处理不相关的特征；
• 测试数据集时，运行速度比较快；
• 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

缺点

• 容易发生过拟合（随机森林可以很大程度上减少过拟合）；
• 容易忽略数据集中属性的相互关联；
• 对于那些各类别样本数量不一致的数据，在决策树中，进行属性划分时，不同的判定准则会带来不同的属性选择倾向；信息增益准则对可取数目较多的属性有所偏好（典型代表ID3算法），而增益率准则（CART）则对可取数目较少的属性有所偏好，但CART进行属性划分时候不再简单地直接利用增益率尽心划分，而是采用一种启发式规则）（只要是使用了信息增益，都有这个缺点，如RF）。
• ID3算法计算信息增益时结果偏向数值比较多的特征。

随机森林

随机森林属于 集成学习 中的 Bagging（Bootstrap AGgregation 的简称） 方法。

随机森林是由很多决策树构成的，不同决策树之间没有关联。

当我们进行分类任务时，新的输入样本进入，就让森林中的每一棵决策树分别进行判断和分类，每个决策树会得到一个自己的分类结果，决策树的分类结果中哪一个分类最多，那么随机森林就会把这个结果当做最终的结果。

随即森林的四个步骤

1. 一个样本容量为N的样本，有放回的抽取N次，每次抽取1个，最终形成了N个样本。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。
2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了

优点

1. 它可以出来很高维度（特征很多）的数据，并且不用降维，无需做特征选择
2. 它可以判断特征的重要程度
3. 可以判断出不同特征之间的相互影响
4. 不容易过拟合
5. 训练速度比较快，容易做成并行方法
6. 实现起来比较简单
7. 对于不平衡的数据集来说，它可以平衡误差。
8. 如果有很大一部分的特征遗失，仍可以维持准确度。

缺点

1. 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。
2. 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的

数学

线代

向量

物理：空间中的箭头

计算机：有序的系列表

加法和数乘得到‘所有’向量

线性相关：一个向量可以由其他向量表示出来，对张成空间并没有做出贡献。

向量空间的一组基是张成该空间的一个线性无关向量集。

线性变换以及它和矩阵的关系

线性变换：原点不变、一条直线在变换后还是一条直线。

根据变换后的i，j可以推断原来的向量。

矩阵的每一列对应一个基准向量经过线性变换后得到的坐标值。矩阵即空间变换。

矩阵乘法和线性变换符合

矩阵相乘：两个线性变换相继作用。

行列式

二阶行列式的值表示将原来一个单位面积为1的方格扩大的倍数。（负值表示定向）

行列式为0时，意味着将向量的维度压缩到更低的维度。

矩阵的秩表示变换后的空间维度。（n-r 的维度空间会被压缩到原点）

非方阵：

特征值和特征向量

大部分向量经过矩阵变换都离开了其张成空间，而又个别向量仍然停留在其原来的张成空间，只是长度变化了。

特征基：矩阵变为相似对角化时的基向量的变化。

微积分

概率论

全概率和贝叶斯概率

条件概率公式

全概率公式的意义

贝叶斯公式

贝叶斯公式的意义

协方差就是这样一种用来度量两个随机变量关系的统计量

贝叶斯

通常，事件 A 在事件 B 发生的条件下与事件 B 在事件 A 发生的条件下，它们两者的概率并不相同，但是它们两者之间存在一定的相关性，并具有以下公式（称之为“贝叶斯公式”）：

拉普拉斯方程

看似平淡如水等于0，却位列三大偏微分方程之首，也称椭圆方程，另两个是热方程(Heat equation)与波方程(Wave equation)，也称抛物线方程和双曲线方程。

傅里叶级数

法国数学家傅里叶认为，任何周期函数都可以用正弦函数和余弦函数构成的无穷级数来表示（选择正弦函数与余弦函数作为基函数是因为它们是正交的）

逻辑思维

作者：Li-Xiao-Hu
链接：https://www.nowcoder.com/discuss/807456?type=post&order=recall&pos=&page=1&ncTraceId=&channel=-1&source_id=search_post_nctrack&gio_id=05AAD86CBB03845BCF38C9B1C78E9A99-1646580069335
来源：牛客网

二进制问题

1**.毒药问题**：有1000个一模一样的瓶子，其中有999瓶是普通的水，有1瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有10只小白鼠和1个星期的时间，如何检验出哪个瓶子有毒药？

海明码。需要十只老鼠，如果按顺序编号，ABCDEFGHIJ分别代表从低位到高位每一个位。 每只老鼠对应一个二进制位，如果该位上的数字为1，则给老鼠喝瓶里的药。

2.分金块问题：工人为老板打工，工作七天可以获得一块金子，工人每天可以分得一点金子，老板必须每天发金子，不能多给，也不能少给，把这个金子切两刀，就可以每天给工人发工资，请问怎么切？

利用二进制的特性，二进制位数可组成任意数，将金子分为1/7 、2/7、3/7.

工作第一天 把1/7分给工人；

工作第二天 把2/7分给工人，并要回1/7那块金子，工人有2/7的金子；

工作第三天 把1/7给工人 工人有3/7金子；

工作第四天 把前两块金子要回，给工人4/7的金子 工人有4/7的金子；

工作第五天 把1/7分给工人 工人有5/7的金子；

工作第六天 把2/7分给工人，并要回1/7那块金子，工人有6/7的金子；

工作第七天 把1/7给工人 工人有完整的金子

先手必胜问题

1.抢30必胜策略。抢 30 是双人游戏，游戏规则是：第一个人喊“ 1 ”或“ 2 ”，第二个人要接着往下喊一个或两个数，然后再轮到第一个人。两人轮流进行下去，最后喊 30 的人获胜，问喊数字的最佳策略。

解析： 倒着看，其实，喊 27 时，就决定胜负了。 假设 A 喊了 27，B只能喊 28 或 29 ， 下个回合，A 一定可以喊30。也就是说，喊 27 者必胜。 再倒着看，其实喊 24 时，就定胜负了。假设 A 喊了 24 ，B 只能喊 25 或 26 ， 下个回合 A 一定能喊 27 。 由于喊 27 者必胜，因此喊 24 者也必胜。 同理可以推出：喊 3 的倍数者必胜。

然后就会发现，这个游戏，谁先喊，谁一定输。

2.100本书，每次能够拿1~5本，怎么拿能保证最后一次是你拿？

如果最后一次是我拿，那么上回合最少剩下6本； 只要保持每个回合结束后都剩下6的倍数，且在这个回合中我拿的书和对方拿的书加起来为6本； 第一次我必须先手拿4本(100 % 6 = 4)，这不算在第一回合内。

推理题

1.掰巧克力问题：一块N * M大小的巧克力，每次掰一块的一行或一列，全部掰成 1 * 1 大小的巧克力需要掰多少次？

• N * M - 1次；

不管怎么掰，每次只能把一个大块掰成两个小块，即每次掰只能增加1块巧克力； 那么将1块巧克力掰成N * M块小巧克力就需要掰N * M - 1次。

2.辩论赛问题：1000个人参加辩论赛，每场比赛淘汰一个人，问共需安排多少场比赛？

999场； 每场比赛只能淘汰1人。

3.在24小时里面时针分针秒针可以重合几次

22次。24小时中时针走2圈，而分针走24圈，时针和分针重合24-2=22次， 而只要时针和分针重合，秒针一定有机会重合，所以总共重合22次

概率问题

1.家里有两个孩子，一个是女孩，另一个也是女孩的概率是多少？

1/3.

​ 样本空间为（男男）（女女）（男女）（女男）

​ A＝（已知其中一个是女孩）＝（女女）（男女）（女男）

​ B＝（另一个也是女孩）＝（女女）

​ 于是P（B／A）＝P（AB）／P（A）＝（1／4）／（3／4）＝1／3

2.一条绳子砍两刀，能构成一个三角形的概率？

设绳子总长为L，分成三段为：x，y，L - x - y； 其中x > 0，y > 0， L - x - y > 0，取值范围如图中蓝***域所示；

又因为任意两边之和要大于第三边，故有如下条件： x + y > L - x - y => y > -x + L / 2； x + (L - x - y) > y => y < L / 2; y + (L - x - y) > x => x < L / 2;

该区域为图中绿域，占蓝域的 四分之一；

3.** 一个圆上随机画两条弦，求相交的概率？*

四个点确定两条线，在一个圆上取四个点； 四个点画两条线有三种情况，其中只有一种情况是相交的，故相交概率为 三分之一；

4.犯人猜颜色:

一百个犯人站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色．然后从最后一个犯人开始，每人只能用同一种声调和音量说一个字：”黑”或”白”，如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的答案所有犯人都能听见，是否说对，其他犯人不知道，在这之前，所有犯人可以聚在一起商量策略，问如果犯人都足够聪明而且反应足够快，100个人最大存活率是多少？

1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”，他可能死

2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，黑帽数量减一

3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑”

99人能100%存活，1人50%能活

5.火枪手决斗，谁活下来的概率大？:彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时开枪，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？

参考回答： 一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大；

那么我们先来分析一下各个枪手的策略：

如同田忌赛马一般，枪手甲一定要对枪手乙先。因为乙对甲的威胁要比丙对甲的威胁更大，甲应该首先干掉乙，这是甲的最佳策略。

同样的道理，枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉，乙和丙进行对决，乙胜算的概率自然大很多。

枪手丙的最佳策略也是先对甲。乙的枪法毕竟比甲差一些，丙先把甲干掉再与乙进行对决，丙的存活概率还是要高一些。

我们根据分析来计算一下三个枪手在上述情况下的存活几率：

第一轮：甲射乙，乙射甲，丙射甲。

• 甲的活率为24%（40% X 60%）

• 乙的活率为20%(100% - 80%)

• 丙的活率为100%（无人射丙）

  由于丙100％存活率，因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率：

  情况1：甲活乙死（24% X 80% = 19.2%） 甲射丙，丙射甲：甲的活率为60%，丙的活率为20%。

  情况2：乙活甲死（20% X 76% = 15.2%） 乙射丙，丙射乙：乙的活率为60%，丙的活率为40%。

  情况3：甲乙同活（24% X 20% = 4.8%） 重复第一轮。

  情况4：甲乙同死（76% X 80% = 60.8%） 枪战结束。

  据此来计算三人活率：

• 甲的活率为(19.2% X 60%) + (4.8% X 24%) = 12.672%

• 乙的活率为(15.2% X 60%) + (4.8% X 20%) = 10.08%

• 丙的活率为(19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%

  通过对两轮枪战的详细概率计算，我们发现枪法最差的丙存活的几率最大，枪法较好的甲和乙的存活几率却远低于丙的存活几率。

烧蜡烛问题

两根蜡烛，燃烧完都需要1小时，怎么确定15分钟是多久？

• 点燃第一根的一端，第二根的两端。
• 第二根烧完代表半小时后，点燃第一根另一端，烧完代表15分钟。

赛马问题

1. 25匹马5条跑道找最快的3匹马，需要跑几次？

   将25匹马分成ABCDE5组，假设每组的排名就是A1>A2>A3>A4>A5,用边相连，这里比赛5次

   第6次，每组的第一名进行比赛，可以找出最快的马，这里假设A1>B1>C1>D1>E1 D1，E1肯定进不了前3，直接排除掉

   第7次，B1 C1 A2 B2 A3比赛，可以找出第二，第三名

2. 64匹马8条跑道找最快的4匹马，需要跑几次？

   **第一步：**全部马分为8组，每组8匹，每组各跑一次，然后淘汰掉每组的后四名（需要比赛8场）

   

   **第二步：**取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马，如下图（需要比赛1场）

   

   这个时候总冠军已经诞生，它就是A1，蓝域（它不需要比赛了）。

   而其他可能跑得最快的三匹马只可能是下图中的黄域了（A2,A3,A4,B1,B2,B3,C1,C2,D1，共9匹马）

   

   **第三步：**只要从上面的9匹马中找出跑得最快的三匹马就可以了，但是现在只要8个跑道，怎么办？

   那就随机选出8匹马进行一次比赛吧（需要比赛一场）

   **第四步：**上面比赛完，选出了前三名，但是9匹马中还有一匹马没跑呢，它可能是一个潜力股啊，那就和前三名比一比吧，这四匹马比一场，选出前三名。最后加上总冠军，跑得最快的四匹马诞生了！！！（需要一场比赛）

   最后，一共需要比赛的场次：8 + 1 + 1 + 1 = 11 场

过河/过桥问题

1. 三人三鬼三桥：

   有三个人跟三个鬼要过河,河上没桥只有条小船,然后船一次只能渡一个人和一个鬼,或者两个鬼或者两个人,无论在哪边岸上,只有是人比鬼少的情况下(如两鬼一人,三鬼两人,三鬼一人)人会被鬼吃,然而船又一定需要人或鬼操作才能航行(要有人或鬼划船),问,如何安全的把三人三鬼渡过河对岸?

   先两鬼过去。在一鬼回来。对面有一鬼。这边有三人两鬼。

   再两鬼过去。在一鬼回来。对面有两鬼。这边有三人一鬼。

   再两人过去。一人一鬼回来。对面一人一鬼。这边两人两鬼。

   最后两人过去。一鬼回来。对面三人。这边三鬼。

   剩下的就三个鬼二个过去一个回来在接另外个就OK了。

2. 限时过桥问题：在一个夜晚，同时有4人需要过一桥，一次最多只能通过两个人，且只有一只手电筒，而且每人的速度不同。A，B，C，D需要时间分别为：1，2，5，10分钟。问：在17分钟内这四个人怎么过桥？

   总共是17分钟（尽量让长度相仿的人一起过桥）.

   • 第一步：A、B过花时间2分钟。
   • 第二步：B回花时间2分钟。
   • 第三步：C、D过花时间10分钟。
   • 第四步：A回花时间1分钟。
   • 第五步：A、B再过花时间2分钟。

最优解问题

1. 猴子搬香蕉问题：

   一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，（多了就被压死了），它每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。 （提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。也可以走到n米时，放下一些香蕉，拿着n根香蕉走回去重新搬50根。）

   这种试题通常有一个迷惑点，让人看不懂题目的意图。此题迷惑点在于：走一米吃一根香蕉，一共走50米，那不是把50根香蕉吃完了吗？如果要回去搬另外50根香蕉，则往回走的时候也要吃香蕉，这样每走一米需要吃掉三根香蕉，走50米岂不是需要150根香蕉？

   其实不然，本题关键点在于：猴子搬箱子的过程其实分为两个阶段，第一阶段：来回搬，当香蕉数目大于50根时，猴子每搬一米需要吃掉三根香蕉。第二阶段：香蕉数<=50，直接搬回去。每走一米吃掉1根。

   我们分析第一阶段：假如把100根香蕉分为两箱。一箱50根。

   • 第一步，把A箱搬一米，吃一根。

   • 第二步，往回走一米，吃一根。

   • 第三步，把B箱搬一米，吃一根。

     这样，把所有香蕉搬走一米需要吃掉三根香蕉。

     这样走到第几米的时候，香蕉数刚好小于50呢？ 100-(n3)<50 && 100-(n-13)>50

     走到16米的时候，吃掉48根香蕉，剩52根香蕉。这步很有意思，它可以直接搬50往前走，也可以再来回搬一次，但结果都是一样的。到17米的时候，猴子还有49根香蕉。这时猴子就轻松啦。直接背着走就行。

     第二阶段：走一米吃一根。

     把剩下的50-17=33米走完。还剩49-33=16根香蕉。

2. 高楼扔鸡蛋问题：有14个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

   最优解法是反向思考的经典：如果最优解法在最坏情况下需要扔X次，那第一次在第几层扔最好呢？

   答案是：从X层扔。

   假设最优的尝试次数的x次，为什么第一次扔就要选择第x层呢？

   这里的解释会有些烧脑，请小伙伴们坐稳扶好：

   假设第一次扔在第x+1层：

   如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x层。

   这样一来，我们总共尝试了x+1次，和假设尝试x次相悖。由此可见，第一次扔的楼层必须小于x+1层。

   假设第一次扔在第x-1层：

   如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-2层。

   这样一来，我们总共尝试了x-2+1 = x-1次，虽然没有超出假设次数，但似乎有些过于保守。

   假设第一次扔在第x层：

   如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-1层。

   这样一来，我们总共尝试了x-1+1 = x次，刚刚好没有超出假设次数。

   因此，要想尽量楼层跨度大一些，又要保证不超过假设的尝试次数x，那么第一次扔鸡蛋的最优选择就是第x层。

   那么算最坏情况，第二次你只剩下x-1次机会，按照上面的说法，你第二次尝试的位置必然是X+（X-1）；

   以此类推我们可得：

   x + (x-1) + (x-2) + … + 1 = 100

   这个方程式不难理解：

   左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次，所以这个多项式共有x项。

   右边是总的楼层数100。

   下面我们来解这个方程：

   x + (x-1) + (x-2) + … + 1 = 100 转化为 (x+1)*x/2 = 100

   最终x向上取整，得到 x = 14

   因此，最优解在最坏情况的尝试次数是14次，第一次扔鸡蛋的楼层也是14层。

   最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：

   14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100

   举个栗子验证下：

   假如鸡蛋不会碎的临界点是65层， 那么第一个鸡蛋扔出的楼层是14，27，50，60，69。这时候啪的一声碎了。 第二个鸡蛋继续，从61层开始，61，62，63，64，65，66，啪的一声碎了。 因此得到不会碎的临界点65层，总尝试次数是 6 + 6 = 12 < 14 。

3. 利用空瓶换饮料：1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶？

   第一种思路:

   ​ 拿走3瓶，换回1瓶，相当于减少2瓶。但是最后剩下4瓶的时候例外，这时只能换1瓶。所以我们计算1000减2能减多少次，直到剩下4.（1000-4=996，996/2=498）所以1000减2能减498次直到剩下4瓶，最后剩下的4瓶还可以换一瓶，所以总共是1000+498+1=1499瓶。

   第二种思路:

   • 1000瓶饮料，3个空瓶子能换1瓶饮料，最多可以喝几瓶？

   • 第一种思维：可以考虑成dp思路

   • 初始情况，3个瓶子时将发生一次交换，因此视为特殊情况

   • 之后每增加两个瓶子又可以再换一瓶

   • 即dp[i] = dp[i - 2] + (i - (i - 2)) + 1

   • 由dp[i - 2]可求得dp[i]

   • (i - (i - 2))，即为当前增加的2瓶饮料（写成这样便于理解）

   • 1即为增加了2个空瓶，之后又可以换一瓶饮料

   • 简化为dp[i] = dp[i - 2] + 2 + 1

   public int method(int n) {// n为0/1/2的特殊情况省略了// 定义dp数组int[] dp = new int[n + 1];// 初始状态dp[0] = 0;dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 2] + 2 + 1;}return dp[n];}
   

   • 回归正题

   • 特殊情况：从上面的分析中，留下2个瓶子

   • 剩下998个瓶子相当于每消耗2个瓶子即可获得一瓶，即为499瓶

   • 最后剩下的2个瓶子无法再进行兑换，因此总共为1000 + 499 = 1499

   • 第二种思维：利用借瓶子的思想

   • 因为兑换一瓶饮料需要三个空瓶，这瓶饮料如果是找老板借来的，那么喝完后这个空瓶将会还给他，同时需要附赠给他另外两个空瓶，即每消耗手里两个空瓶就获得一瓶饮料

   • 但是值得注意的是，上面只是一种假设，实际情况老板是不会借给你的，因此我们至少需要保留2个空瓶，这样可以在998个瓶子剩下一个瓶子时，对其进行补足为3个空瓶，从而兑换一瓶新饮料

   • 此时使用998个瓶子进行上述的兑换，将获得499瓶饮料

   • 之前留下的两个瓶子正好无法兑换，最终获得饮料为1000 + 499 = 1499瓶

数字问题

1. 给定随机函数，生成别的随机数：给定生成1到5的随机数Rand5()，如何得到生成1到7的随机数函数Rand7()？

   思路 ：由大的生成小的容易，比如由Rand7()生成Rand5()，所以我们先构造一个大于7的随机数生成函数。 记住下面这个式子：
   $$RandNN=N(RandN()-1)+RandN();//生成1到N^2之间的随机数$$
   可以看作是在数轴上撒豆子。N是跨度/步长，是RandN()生成的数的范围长度，
   RandN()-1的目的是生成0到N-1的数，是跳数。后面+RandN()的目的是填满中间的空隙.

   比如 Rand25= 5( Rand5()-1 ) + Rand5() 可以生成1到25之间的随机数。我们可以只要1到21（3*7）之间的数字，所以可以这么写:

   int rand7(){
   int x=INT_MAX;
   while(x>21){x=5*(rand5()-1)+rand5();
   }
   return x%7+1;
   }
   

重量问题

1. 乒乓球重量问题：8个乒乓球，其中一个重，有一个秤，问至少几次能够找出重的那个乒乓球?

   • ①称3和3，如果一样重，代表重的在2。
   • ②称2个那一堆的。

   或

   • ①称3和3，不一样重，重的在3里面重的那堆。
   • ②3个里面随便取2个，一样重，第三个重，不一样重，重的那个就是。

2. 盐重量问题：有7克、2克砝码各一个，天平一只，如何只用这些物品五次内将140克的盐分成50、90克各一份？

   • 第一次：先分成70和70
   • 第二次：通过7和2砝码将70分成9和61
   • 第三次：通过9克盐和2砝码将61分成50和11

3. 有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？

   2次。

   天平一边放三个砝码，哪边轻就在哪边，一样重就在剩下的三个砝码中；

   现在已经锁定了三个砝码，天平一边放一个，哪边轻是哪个，一样重就是剩下的那个；

4. 十组砝码每组十个，每个砝码都是10g重，但是现在其中有一组砝码每个都只有9g重，现有一个能显示克数的秤，最少称几次能找到轻的那组？

   一次即可。

   将砝码分组编号1~10， 第1组拿1个砝码、第2组拿2个…第10组拿10个，全部放到秤上计算总克数X； Y = (1*10 + 2 * 10 + … + 10 * 10) - X = 550 - X，Y即为轻的那组的编号。

灯泡开关问题

1. 在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分那个开关控制那一盏灯？

   打开一个开关，过10分钟后关掉开关，并打开另一个开关。进屋确认可知：

   • 亮的灯是由第二次打开的开关控制；
   • 摸上去发热的不发亮的灯是由第一次打开的开关控制
   • 剩下的第三盏灯是由未操作过的开关控制。

2. 一个圆环上有 100 个灯泡，灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。设计一种算法，对于任意初始状态，使所有灯泡全亮。

   作者：Li-Xiao-Hu
   链接：https://www.nowcoder.com/discuss/807456?channel=-1&source_id=profile_follow_post_nctrack
   来源：牛客网

   将灯泡编号 1 ~ 100

   步骤一：将灯泡变为全亮或只剩一个为暗

   从 1 循环到 98 ，遇到暗的则按它下一个，使之变亮。循环完毕，1 ~ 98 必然全亮。99 和 100可能为亮亮、暗亮、亮暗、暗暗四种状态。

   • 若为亮亮，皆大欢喜，满足题目要求

   • 暗亮、亮暗，达到只剩一个为暗的状态；

   • 若为暗暗。则按下编号 100 的灯泡，使编号 99 、100 变为亮，编号 1 的灯泡变为暗，从而达到只剩一个为暗的状态。

     步骤二：将灯泡变为全暗

     由于灯泡环形摆放，我们指定暗的灯泡编号为 1 ，将剩下 99 个亮着的灯泡每 3 个为一组。按下每组中间的灯泡后，使得所有灯泡变为暗。

     步骤三：将灯泡变为全亮

     将所有灯泡按一下，灯泡变为全亮;

     扩展:

     对于 N 个灯泡的任意初始状态 ( N > 3 ) ，能否经过若干次操作使得所有灯泡全亮？

     答案：N 个灯泡做分类讨论。

   1. N = 3*k+1一定可以。方法与上述步骤相同，在步骤二中可以将3k个亮的灯泡分为k组。

   2. N = 3*k+2一定可以。将上述步骤一目标状态的只剩一个为暗改成剩两个相邻为暗，其余 3 * k 个灯泡分组按即可。因为，对于任意只剩一个为暗的状态，按下该灯泡左右任意一个就可以变成剩两个相邻为暗的状态！

   3. N = 3*k不一定。如果经过上述步骤一可以将灯泡变成全亮的状态则有解；否则，无解。（该结论有待证明）

      附:

      对于这道题，以下两个状态可以相互转化

      大家可以琢磨下，对理解这道题会有帮助。

   4. 全暗 <=> 全亮。全暗和全亮状态可以相互转化，方法就是将每个灯泡按一次。这样每个灯泡都被改变了 3 次状态，使得全暗变为全亮，全亮也可变为全暗。

   5. 剩一个为暗 <=> 剩两个相邻为暗。剩一个为暗时，按下该灯泡左右任意一个，就变成了剩两个相邻为暗的状态；剩两个相邻为暗时，按下第二个暗，便可变成了剩一个为暗的状态。

蓝眼/疯狗/耳光问题

1. 有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人是蓝眼睛的，只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛？

   有多少个蓝眼睛的人就有多少天。

2. 耳光问题。

   一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？

   答案：有三个人戴黑帽。

   ​ 假设有N个人戴黑帽，当N＝1时，戴黑帽的人看见别人都为白则能肯定自己为黑。于是第一次关灯就应该有声。可以断定N＞1。对于每个戴黑帽的人来说，他能看见N-1顶黑帽，并由此假定自己为白。但等待N-1次还没有人打自己以后，每个戴黑人都能知道自己也是黑的了。所以第N次关灯就有N个人打自己。

三杯水ABC

第一次:A倒一半均分给B C
第二次:B倒一半均分给A C
第三次:C倒一半均分给A B
最后三杯水相等，求原始比例？

倒推即可，设最后三者都为16，则开始是8、14、26。

项目

服务端

(TCP)socket bind listen accept connect

（UDP）socket bind recvfrom() sendto close

存储用户信息：

struct User {char name[20];int online;pthread_t tid;int fd;
}

**fork()**多进程优化服务端: 子进程的返回值是0.

用户登录时，针对其名字来判断是否在线。已经在线则拒绝登录并发送提示信息。

每一个上线的客户分配一个专门的线程。

void *work(void *arg){}
pthread_creat(&tid, NULL, work, (void *)&);

检测用户退出： 收到的信息中的ret_val < 0

并发使用线程,为每个用户创建一个线程，当用户下线的时候，销毁线程，缺点：创建和销毁的开销比较大，可以使用线程池。

用户每次登录会分配一个最小的fd。

客户端

(TCP)socket connect send

(UDP) socket sendto recvfrom

发送的信息：

struct Msg{char from[20];int flag;//0表示私聊、1表示公聊、2表示系统提示信息char message[1024];
}

。

处理ctrl + c进行用户退出，使用signal信号。

子进程发信息，父进程收信息。

将聊天记录写道配置文件中。

线程池

任务队列：

互斥锁：保证一个任务只能被一个线程抢到。

条件变量：告知有任务来了

typedef struct{int sum;int head;int *fd;int tail;pthread_mutext_t mutex;pthread_cond_t cond;
}TaskQueue;
void TaskQueueInit(TaskQueue *q, int sum);
void TaskQueuePush(TaskQueue *q, int fd); //内部加锁和信号
int TaskQueuePop(TaskQueu *q); //如果没有任务则等待信号
void *thread_run(void *arg);//线程处理函数
pthread_create(&tid[i], NULL, thread_run, (void*)&queue);//初始化线程池（即一个数组），让程序开始前，所有的线程都运行起来。

遇见问题

1. 函数封装放在一个专门的配置文件里，容易重复定义
2. 函数使用困难，man手册阅读花力气
3. 对用户退出操作时，使用的是指针，导致名字位置发生错误。

论文

人工智能入门

课程了解

（随机）梯度下降：根据斜率不同来不断调节w. (w = w - a * aloha)

优点： 海量数据每次都能调整参数，且越来越快

缺点：无法并行计算且不容易向全局最优解靠拢

两种调和，每次选取其中部分做梯度下降。

激活函数：Logistic函数（S型函数）sigmoid。可以很好的进行分类，01，在神经网络中摆脱线性的约束，可以模拟任何非线性的函数。（原来再多次矩阵相乘仍然是一个线性的）

S型函数处处有斜率，处理01分类问题的时候仍然可以用梯度下降。（在距离越远的情况下，斜率越接近零，在越深的神经网络，梯度下降越容易为0，权重无法更新。所以经常用relu激活函数（Sigmod函数可以用来结果输出））

我们一般把隐藏层（纵向训练参数）超过3层的神经网络称之为深度神经网络。

卷积神经网络：通过卷积核来提取特征，进行图像识别。

共享参数：提取特征的方式是一样的。

池化层：最大池化层，平均池化层（一般可以在卷积层后面设置）

same模式：在卷积核进行卷积的时候，在原始图像加拖个层0，如28*28,加四层0之后是32*32，卷积之后像素不变(卷积核为5*5， 32 - 5 + 1 = 28)

valid模式：越卷越小。

循环时间网络：用来节约有时间上依赖的问题，如自然语言处理。

附录问题

二氧化碳合成淀粉

植物利用光能效率很低，太阳能发电能达到20%，利用光能发电电解水，H和CO2合成一碳，通过酶合成三疼碳，然后六碳，最后合成淀粉。利用计算机计算，设计了两个规则：（1）能量耗费尽可能小（2）步骤尽可能少。

目前只存在试管，工业化还很难。