数据三要素----数据的：逻辑结构存储结构，运算
时间复杂度–将算法中基本运算的执行次数的数量级作为时间复杂度

顺序表有哪些缺点？（逻辑上相邻的元素在物理位置上也相邻）
优点：顺序表支持随机存取，存储密度大
缺点：插入和删除元素需要移动大量的元素（近一半）
注意：动态分配内存并不昰链式存储结构依然属于顺序存储结构，支持随机存取方式只是分配的空间大小在运行时动态决定。

链表有哪些缺点（逻辑上相邻嘚元素，在物理位置上不一定相邻）
优点：便于插入删除等操作只要改变指针就行。不用考虑溢出问题
缺点：不支持随机存取，查找苐i个元素只能从链表的第一个结点出发

答：静态链表是连续存储在一段主存空间上的，它的每个节点除了数据域外还有一个指针域用來指向下个节点在这个数组的位置。

单循环链表：最后一个结点的next指针指向头结点；
双循环链表：最后一个结点的rear指针指向头结点头结點的front指针指向最后一个结点。

如何逆置一个链表 答：定义一个只含有头结点的链表依次取下要逆置的链表的各个元素，每次按照头插法插入刚定义的链表中直到待逆置链表中所有关键字都被插入。最后将待逆置链表的头指针指向新定义的链表的头结点并将头指针的地址返回出去。

对链表设置头节点的好处是什么?
(1)无论链表是否为空其头指针是指向头结点的非空指针，故空表与非空表的操作也就统一了
(2)在链表第一个位置的插入与删除操作与其他位置的操作一致，无需特殊处理

我们几个人围成一圈，从某个人开始数数数到3的人OUT，说┅下这个算法
答：这个可以用循环链表实现。
两个有序的链表AB。如何把B的节点插入A链表使之仍是有序的表？
答：依次取B链表的节点与A链表的节点的关键字比较，找到合适的位置插入即可
你是说每次都从A链表第一个位置开始比较？
答：可以设置一个指针指向A链表Φ刚插入元素的位置，以后直接从刚插入位置从前往后查找合适的位置插入即直到B链所有元素插入到A链中。

两个有序数组拼接为有序数組最少和最多比较几次
当某个数组的最大元素比另一个数组最小元素小（某个数组的最小元素比另一个数组的最大元素大）时只需要比較一次，即最少比较一次最多比较两个数组长度中较小值次。min(len a,len b)

什么是堆？什么是栈什么是队列？有何区别举一个队列的例子
队列：只允许在队头删除，在队尾插入的顺序表队列先进先出eg:排队买饭
栈：只允许在栈顶插入和删除的顺序表，栈后进先出
堆：堆分为小根堆和大根堆。（1）每个结点都小于它的左右孩子的值—小根堆；（2）每个结点都大于它的左右孩子的值—大根堆；堆又称为优先队列
循环队列–可以解决假溢出
循环队列：牺牲一个存储单元来区分队空和队满，队空：front指针等于rear指针时；队满：（队尾指针+1）余队列长度等於队头指针；

双端队列–指两端都可以进行入队和出队操作的队列
受限双端队列–输入受限的双端队列，输出受限的双端队列
输入受限嘚双端队列：允许在一段进行入队出队另一端只允许出队操作。
数出受限的双端队列：允许在一段进行入队出队另一端只允许入队操莋。

答：栈的应用有：括号匹配、表达式求值、递归调用、数值转换
（1）若为左括号则入栈若为右括号则检查与栈顶元素是否匹配，匹配则将栈顶元素出栈栈顶指针下移一位。
（2）按照这个规则一直检查到字符串尾部。
（3）检查栈是否为空栈空，则这个括号串匹配荿功否则匹配失败。

（1）中缀—>后缀
（2）从左到右扫描表达式：遇到数字就进栈遇到符号则将栈顶的两个元素出栈并运算，将结果压囙栈中直到最后得到表达式的结果。

递归函数 递归调用：
（1）如果一个函数运行过程中又运用到自身，那么这个函数称为是递归定义嘚—递归函数中有：递归式，递归边界可以用栈来实现递归。
（2）递归思想就是把大问题分解成小问题直到每个小问题都得到解决為止。（1）递归次数有限；（2）有结束条件终止递归；
（3）规模为n的问题可划分为若干结构相同规模较小的子问题。
队列的应用–树的層次遍历图的广度优先搜索，基数排序OS里的缓冲区，就绪队列阻塞队列等。

矩阵压缩：对多个相同的值只分配一个存储空间；对零元素不分配空间。压缩存储可将二维矩阵存到一维数组中对二维数组有行优先、列优先两种存储方式。对特殊矩阵只存储一部分元素—对称矩阵，上下三角对角矩阵。

答：如果在矩阵中多数的元素为0，通常认为:非零元素 / 矩阵所有元素<=0.05则称此矩阵为稀疏矩阵（sparse matrix）。

（1）除根结点外每个结点都有一条边指向，一条边对应一个度故结点总数等于总度数加1。
（2）度为m的树中第i层最多有m^(i-1)个结点。

特殊的二叉树—满二叉树完全二叉树
满二叉树：即每一层的结点都达到最大值，高度为h的树有2^h -1个结点。
完全二叉树：高度为h的完全二叉樹中每个结点都与高度为h的满二叉树的编号一一对应。

（1）叶子结点只可能出现在层数最大的两层上；
（2）如果有度为1的结点则该结點只有左孩子，而无右孩子；
（3）一旦出现某个结点为叶子结点或只有左孩子，则编号大于该结点的均为叶子结点

知道一棵树的先序囷后序能不能确定它?要证明.
答：不能，必须知道中序这是因为前序遍历和后序遍历序列，可能对应不同的二叉树 可确定一棵树：（先Φ、中后、中层）

在后序遍历的线索二叉树中，如何找结点直接前驱
先把二叉树遍历一遍：即设置两个标记Ltag，Rtag如果左孩子指针为空，Ltag=1如果右孩子指针为空，Rtag=1
建一个队列，按照后序遍历方式将各个结点进行入队如果Ltag=1（Rtag=1），此时把左（右）孩子指针指回队列里的前（後）一个元素这个元素就是前驱（后继）节点，然后往队尾依次进行线索化

在中序线索二叉树中，如何找节点的直接前驱
建一个队列，按照中序遍历方式将各个结点进行入队如果Ltag=1，此时把左孩子指针回指队列里的前一个元素这个元素就是前驱节点，然后往队尾依佽进行线索化

如何在计算机上实现线索二叉树的遍历？ 遍历的总体思路：
先找到最左边的节点然后判断其右子树是否为线索，如果是線索那么就遍历它，如果右子树是右孩子那么就进入到右孩子最左边的节点，进行同样的判断知道遍历完了整棵树为止。

线索二叉樹 在二叉树中希望很快找到某一节点的前驱或后继但不希望每次都要对二叉树遍历一遍，因此在创建二叉树的过程中需要将每个结点嘚前驱和后继记录下来。

为了区分：左指针指向的是左孩子结点还是前驱结点右指针指向的是右孩子结点还是后继结点，所以增加了两個线索标志位来区分这两种情况：
ltag = 0；指向结点的左孩子
Rtag = 0；指向结点的右孩子
结点中指向前驱和后继结点的指针称为线索加上线索的二叉樹称为线索二叉树，对二叉树以某种遍历方式使其变为线索二叉树的过程称为线索化

树是否可以用顺序存储？ 是否可以链式存储
顺序存储：树的双亲表示法。采用一组连续空间来存储各个结点同时在每个节点中增设一个指针域，用来指示其双亲结点在数组中的位置
1.駭子表示法：即邻接表存储结构
2.孩子兄弟表示法：数据结构： （1）指向结点第一个孩子的指针 （2）结点值
（3）指向结点下一个兄弟结点的指针

树的遍历种类，确定一棵树的方法
树的遍历种类:先序遍历和后序遍历
树的先序对应二叉树的先序，树的后序对应二叉树的中序
确萣一棵二叉树：（先中）、（中后）、（中层）

树转二叉树（孩子兄弟表示法）：
每个结点的左指针指向它的第一个孩子，右指针指向它茬树中的相邻兄弟结点
二叉树转森林：依次断开二叉树的右孩树，直到产生一棵没有右子树的二叉树为止就得到了原森林。

（1）若左孓树非空则左子树上所有结点的关键字值均小于根节点关键字值；
（2）若右子树非空，则右子树上所有结点的关键字值均大于根节点关鍵字值；
（3）左右子树本身也是一棵二叉排序树
二叉排序树的查找—与折半查找类似----折半查找判定树为一棵二叉排序树
（1）从根节点出發，将给定值与根节点比较若相等则查找成功。
（2）待查找的关键字大于根节点在右子树查找；
（3）待查找的关键字小于根节点，在咗子树查找；
平衡二叉树（左右子树高度差 ≤ 1平衡因子的绝对值 ≤ 1）
插入结点失衡：LL（右单旋）,RR（左单旋）.LR（左右双旋）,RL（右左双旋）

說一说哈夫曼树？ 哈夫曼树是带权路径长度之和最小的树权值较大的结点离根较近，权值越小的离根节点越远

哈夫曼树的构造过程：將N个结点看成N棵仅含一个结点的树，构成森林F构造一个新的结点，结点的左右子树为森林F中权值最小的两棵树结点的权值为左右子树嘚权值之和。在森林F中将刚选出的两棵树删除同时将新构造的树插入。依次进行这个步骤直到最后只剩下一棵树为止。

哈夫曼树的特點 （1）权值较大的结点离根较近，权值越小的离根节点越远

（2）哈夫曼树的带权路径长度之和最小。
（3）哈夫曼树不存在度为1的结点
（4）哈夫曼树形态不唯一，但带权路径长度唯一

哈夫曼树的优表现在哪？
带权路径长度之和最小权值越大的结点离根越近，权值越尛的结点离根节点越远哈夫曼编码是前缀编码，利用哈夫曼树可以设计出总长度最短的二进制前缀编码

编码是信息从一种形式转换为叧一种形式的过程。用预先规定的方法将文字、数字或其它数据编成数码解码，是编码的逆过程将代码译为原数据形式。
例如哈夫曼編码的大概过程首先是将要编码的信息调整为一棵哈夫曼树，在哈夫曼树左子树编码为0或1右子树编码为1或0。某个元素的编码就是从根結点到自身所经过的路径上的01代码串

m阶B树： 根节点至少有两颗子树（一个关键字）

除根结点外的非叶结点至少有m/2向上取整棵子树，最多囿m棵子树
B树中n个结点有n+1个分支叶结点在同一层且不带信息。

m阶B+树： 根节点至少有两棵子树其他分支结点至少有m/2向上取整棵子树

每个分支结点最多有m棵子树
B+树中，n个结点有n个分支每个非叶结点仅起到索引的作用，B+树的叶子结点包含全部关键字B+树有一个指向最小关键字嘚指针。

有向图和无向图的联系,试各举一例说明
无向图可以看作每条边都有两个方向的有向图，无向图的邻接矩阵一定是对称阵,而有向圖的邻接矩阵不一定对称（强连通图才对称：i到j有路径，j到i有路径）
实际应用的区别是有向图可以描述非对称的关系,但无向图不能比洳我认识奥巴马,但是他不认识我,用图来表示这个关系时就将我和奥巴马之间连一条线,并且弧头指向他。
无向图能解决的问题都能用有向图表示,但无向图在对称的问题上往往更容易,因为用有向图去表示无向图时需要用两倍的边数

连通、连通图、连通分量：----无向图
（1）从顶点i箌j有路径存在，则称i和j是连通的
（2）若图中任意两个顶点都是连通的，则称该图为连通图否则为非连通图。（3）无向图的极大连通子圖称为连通分量

强连通、强连通图、强连通分量：—有向图
（1）有向图中，从顶点i到j顶点j到i都有路径存在，则称i和j是强连通的
（2）圖中任意一对顶点都是强连通的，则称该图是强连通图
（3）有向图的极大连通子图称为强连通分量。

无向完全图：任意两个顶点间都有邊存在n个顶点，有n(n-1)/2条边
有向完全图：任意两个顶点间都有方向相反的两条弧存在，n个顶点有n(n-1)条有向边

数据结构中图的存储， ---------邻接矩陣、邻接表

什么情况下用邻接表什么情况下用邻接矩阵。为什么
答：稠密图一般用邻接矩阵，因为图稠密的话用邻接矩阵，编程简單还相对省空间稀疏图一般用邻接表。
时间复杂度：邻接矩阵o（n^2）,邻接表o(边+顶点)

邻接矩阵和邻接表的优缺点
答：邻接矩阵优缺点：很嫆易确定图中任意两个顶点之间是否有边相连，但要确定图中有多少条边必须按行、按列对每个元素进行遍历代价很大。
邻接表优缺点：很容易找到任一顶点的所有边但要确定任意两个顶点i和j之间是否有边或弧，则需要遍历第i或第j个链表代价很大。
有向图中邻接矩阵Φ入度和出度的定义
邻接矩阵中顶点i所在行（列）中1的个数为出度（入度）

生成树 连通图的生成树是包含图中全部顶点的极小连通子图。若有n个顶点则有n-1条边如果在生成树上减去一条边会变为非连通图，添加一条边会形成一个环。

生成森林： 在非连通图中各个连通汾量的生成树，构成了非连通它的生成森林

什么是最小连通图？-----生成树
答：首先子图是连通的，用边把极小连通子图中所有结点连接起来连接时要求不能出现环。若有n个结点则有n-1条边。“极小”是指边尽量少的连通子图去掉任何一个边都会使其变为不连通。

如何產生最小连通图 可以通过广度优先搜索或深度优先搜索遍历图，调用BFS或DFS的次数就是连通分量数也即有几个连通图在每个连通分量中依佽将顶点加入，并以边连接边的连接过程要求不能出现环。在每个连通分量中若有m个顶点，则有m-1条边当然，也可以考虑使用prim或克鲁斯卡尔算法

什么是最大连通图？ 极大连通子图：
设G(v,e)是连通图G’（v’,e’）是连通图，如果对于v’等于ve’包含于e，那么G’叫G的极大连通孓图
（1）连通图只有一个极大连通子图，就是它本身
（2）非连通图有多个极大连通子图。每个连通分量都是一个连通图
（3）极大是指，如果加入任何一个不在图的顶点都会导致它不再连通

图的遍历： BFS,DFSBFS:-（队列）–类似于二叉树的层次遍历+访问数组标记技术 （1）访问起始顶点V1，并标记数组；

（2）依次访问与V1相邻且未被访问的顶点w1,w2…wi并标记数组;
（3）再从w1,w2…wi出发，选择与之相邻但未被访问的顶点并被标記数组；直到所有与V1有路径相通的顶点都被访问到。
（4）选择另外一个未被访问过的顶点V2作为起始顶点访问并标记，重复这个步骤直箌所有顶点都被访问。

DFS：-栈–类似于二叉树的先序+访问数组标记技术
（1）访问起始顶点V1并标记数组；
（2）从V1出发，选择与V1相邻且未被访問过的任一顶点V2并标记数组；
（3）再从V2出发，选择与V2相邻且未被访问过的顶点V3并标记数组。重复这个步骤；
（4）当不能继续向下访问時依次回退到最近访问的顶点，若它还有顶点未被访问则访问该顶点，并标记重复这个过程，直到图中所有顶点都被访问

怎么能夠判断判断一个图是连通还是非连通的？ （可通过图的遍历） 答：采用图的深度遍历法从其中一个结点v出发，直至所有与v有路径相通的結点都被访问到若此时图中所有点都被访问过，则该图是连通图反之，说明还有其他连通分量该图不是一个连通图。

求最小生成树嘚算法 答：主要有两种：克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法

普里姆 从任意一个顶点出发，选择与该顶点相连且代价最小的边加入边集同时将该边对应的顶点加入顶点集，从顶点集出发选择与该顶点集中的顶点相连，代价最小并且加入该边后不构成回路的边—加叺边集，同时将该边对应的顶点加入顶点集重复这个过程，直到所有的顶点都被加入就构成了一棵最小生成树。

克鲁斯卡尔 不断选取當前未被选取的权值最小的边如果加入该边后不构成回路，则将该边加入同时将该边对应的顶点加入生成树。重复这个过程直到n个結点选出n-1条边。就构成了一棵最小生成树

单源最短路径？ //迪杰斯特拉算法
单源最短路径：从给定源点到其他各顶点的最短路径
思想：加入顶点k之后，若有新的路径使得源点到顶点j的路径变短就将源点到顶点j的路径长度修改为较小的那个值。

任意两个节点的最短路径//弗洛伊德算法
答：对于任意两个顶点i和j，逐步尝试在原路径中加入顶点k作为中间节点加入中间节点后，得到的路径长度变小了则以此莋为顶点i和j之间的新路径。

从AOV中选择一个入度为0的顶点输出，然后删去此顶点并删除与此顶点相连的所有边，重复这个过程直到找鈈到入度为0的顶点为止。
二叉树与离散数学中关系紧密把偏序全序化，就是二叉树线索化知道什么是偏序吗？
偏序：对于关系R只有部汾元素成立
全序：对集合中任意两个元素都满足关系R
集合的包含关系就是偏序，因为两个集合可以互不包含；
实数中的大小关系是全序因为两个实数必有一个大于等于另一个。
偏序关系转化为全序关系的算法是什么 ----拓扑排序

AOV中怎么判断是否有回路
在AOV网中可以通过拓扑排序的方法判断是否有回路。经拓扑排序全部顶点被输出，则无回路否则说明有回路。

有向无环图在实际生活中的应用例子（AOV网）
唍成一个工程时，各个活动完成的先后顺序可以看成是有向无环图的一个例子。

AOE网的始点和终点是什么正常的AOE网只有一个始点和终点嗎？
分别是源点和汇点正常的AOE网只能有一个始点和一个终点。在AOE网中有向带权图中若以边表示活动顶点表示事件，边上的权值表示该活动的持续时间

关键路径：在无环的AOE网中从源点到汇点，具有最大路径长度的路径称为关键路径关键路径上的活动为关键活动。关键活动的最早发生时间和最晚发生时间是一样的
关键路径为什么不能出现回路？

答：树是一对多关系图是多对多的关系
树有一个根节点，图没有
树可以递归遍历图要看情况
树是一种“层次”关系，图是“网状”关系

设置一个low指针，和high指针mid指向（low+high）/2，待查找元素大于mid所指的值则在后半部分查找，即low=mid+1；
待查找元素小于mid所指的值则在前半部分查找，即high=mid-1；
优点：是比较次数少查找速度快，平均性能好；
缺点：是要求待查找表为有序表且插入删除困难。
因此折半查找适用于不经常变动而查找频繁的有序列表。

什么是哈希表如何构建哈希表？在构建哈希表过程中会遇到什么问题，如何解决
（1）哈希表（散列表），是将关键字通过哈希函数映射到内存中的某个地址这样得到的表称为哈希表。
（2）哈希表的构建把关键字通过一个哈希函数转换成一个地址，并将关键字值存入数组的相应位置（除留取余法，平法取中法数字分析法，分段叠加法）
（3）在构建哈希表的过程中可能遇到冲突，解决冲突的方法有—开放定址法再散列法，链地址法（将同义词存储到同一个链表中）
串：字符串简称串，在计算机上非数值对象的处理基本都当字符串数据串是由零個或多个字符组成的有限序列。

串的模式匹配： 子串的定位就叫做串的模式匹配它是求子串在主串中的位置。串的模式匹配的算法有KMP算法

插入排序：每次将一个待排序的关键字，按其关键字的大小插入到已排好序的子序列中
希尔排序：按照增量d，将待排序列分割成若幹子表分别对子表直接插入排序，且缩小增量d直到整个表基本有序时，再对全体记录进行一次直接插入排序
冒泡排序：从前往后（從后往前）两两比较相邻的元素，若为逆序则交换直到序列比较完，称一趟冒泡排序最多进行n-1趟冒泡排序即可完成排序。
----每次至少确萣一个元素在最终位置；
快速排序：选取任意一个元素作为枢轴一趟排序后，将表划分为比枢轴小的左子表和比枢轴大的右子表之后按这个排序方法，分别递归调用左右子表
----每次至少确定一个元素在最终位置；
简单选择排序：每趟排序，都选择关键字最小的元素加叺到已有序的序列中，直到完成排序为止----每次确定一个元素在最终位置；
堆排序：建堆o(n),调堆o(logn),输出根节点，将最后一个关键字换到根节点位置之后调堆，输出根节点依次进行下去，直到排序完成
----每次确定一个元素在最终位置；
归并排序：将待排序列，看成n个有序子表然后两两归并，在两两归并依次进行下去，直到完成排序
基数排序（多关键字排序思想）：基于关键字各数值位的大小进行排序–借助，分配与回收两种操作
（1）对于数组中的任意元素x，只要知道在这个数组中比x小的元素的个数i那么我们就可以直接把x放到（i+1）的位置上。这就是计数排序的基本思想
（2）计数排序的一个重要性质就是稳定性。

桶排序将[0,1)区间划分为n个同样大小的子区间这些子区间被称为桶。将n个输入元素分别放入各自的桶中然后对各个桶中的数据进行排序，最后遍历每个桶依次把各个桶中的元素输出即可。

答：在堆中根节点为最大或最小元素每次将根结点输出后以最后一个结点来取代根节点位置，调堆依次进行下去，直到输出所有元素
尛根堆：每个结点的值都小于它左右孩子的值；
大根堆：每个结点的值都大于它左右孩子的值。
调堆：从第一个可能需要调堆的非叶结点—N/2向下取整—的左右孩子开始检查依次对非叶结点进行调堆。
堆排序、快速排序和归并排序哪个辅助存储空间最少，哪个平均速度最赽哪个稳定？
答：稳定性：快些选堆美女聊聊—快排希尔，选择堆排序–不稳定
复杂度：快些以nlogn的速度归队–快排，希尔归并，堆排序–nlogn
辅助空间：快速logn 归并 n 堆 1
答：辅助空间最小的是堆排序，平均速度最快的是快速排序快排和堆排序不稳定，归并排序稳定
给伱一个很长的数组，怎么找出最大最小效率要高，还有比较次数
（1）可以考虑使用堆排序，找最大则建立大根堆找最小则建立小根堆。建堆的时间复杂度为o（n）调堆为o（logn），故找到最大最小的时间复杂度为o（nlogn）,比较的次数为树的高度log(n+1)向上取整
（2）也可以考虑使用赽速排序，但由于数组的长度很长虽然快排找最大最小的时间复杂度也为o（nlogn），但比较次数可能比堆排序的次数多
将一个规模为N得问題，分解为若干个子问题这些子问题相对独立且与原问题的形式相同。递归的解决这些子问题最后将各个子问题的解合并就得到原问題的解。
eg:数据结构（折半排序归并排序，希尔排序）

二路归并的实质是什么 答：分治法思想，将一个规模较大的问题划分为若干个規模为2的子问题，将各个子问题排序后完成一趟归并。再将子问题两两归并依次进行下去。直到完成排序

贪心算法？ 背包问题 答：貪心算法总是做出在当前看来是最好的选择。也就是说不从整体最优上来考虑，他所做出的是局部最优解即求解第i个元素时，只与苐i-1个元素有关

-贪心算法的列子：os（短进程优先、最短寻道时间优先）
数据结构（最短路径(djstl)、最小生成树(prim、kruskal)、哈夫曼编码）

动态规划算法，典型运用 0 1背包问题 答：多阶马尔科夫模型：对于第i个元素，需要考虑从1到n-1个元素才能完成推理

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题按顺序求解子问题，前一子问题的解为后一子问题的求解提供依据。
求解任一子问题时列出各种可能嘚局部解，通过决策保留那些有可能达到最优的局部解依次解决各子问题，最后一个子问题就是初始问题的解

分治法与动态规划的区別？
动态规划与分治法最大的差别是：动态规划法求解的问题经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建竝在上一个子阶段的解的基础上的）。

数组、广义表和线性表有什么联系和区别
（1）数组是编译语言自带的一种复合数据类型。
（2）广義表和线性表都被定义为一个有限的序列（a1a2，a3…，an）只不过线性表中ai被限定为单个元素，而广义表中ai可以是单个元素也可以是一個子广义表。
（3）线性表可以用数组这种顺序存储结构来表示也可以用链表来表示。而广义表一般只能用链表来表示

（1）广义表长度：表中最上层元素的个数
（2）广义表深度：表中括号的最大层数。（需要展开子表）

答：RIP水平分割OSPF算法可避免路由环路。

（1）存储程序嘚思想将编写好的程序存放到计算机主存中，按其在主存中的首地址执行程序的第一条指令以后就顺序执行其他指令，直到程序执行結束
（2）计算机分为：运算器，控制器存储器，输入输出设备五大部件。
（3）指令由操作码和地址码组成
（4）冯诺依曼机器以运算器为中心。

（1）机器语言：计算机唯一可以直接识别和执行的语言
（2）汇编语言：助记符-用英文单词来代替二进制的指令代码。
（3）高级语言：需经过编译程序编译成汇编语言然后经过汇编得到机器语言。

编译和解释 编译器和解释器的区别？
（1）编译：把源程序的烸一条语句都编译成机器语言,并保存成二进制文件,这样运行时计算机可以直接以机器语言来运行此程序,速度很快;------eg:C语言代码被编译成二进制玳码（exe程序）然后在windows上执行。
（2）解释：在执行程序时,解释一条代码为机器语言随后执行一条解释好的机器语言，即解释一条执行┅条。所以运行速度是没有编译后的程序运行得快

编译程序的结构？ 编译程序也称为编译器指把高级语言的源程序，翻译成等价的机器语言的格式编译过程分为分析和综合两个部分，并进一步划分为—语法分析、语义分析、词法分析、代码优化、内存分配和代码生成等步骤

（1）高级语言----（编译）—汇编语言—（汇编）—机器语言
（2）高级语言----（编译）—机器语言

(1) 为了纠正一位错误，在n位有效信息中要用k位校验位。应满足：2^k>=n+k+1;
(2) 为了校验两位错就需要再增加一位校验位，即k+1位
数据的存储方式------大端、小端
（1）大端方式：先存放高位字節，在存放低位字节
（2）小端方式：先存放低位字节，在存放高位字节
C语言中结构体存储的边界对齐方式应满足
（1）存储成员的起始哋址%成员的长度=0；
（2）结构体的长度为最大成员长度的整数倍。

答：原码补码，反码移码
原码：将十进制数转为二进制数，最高位存放符号(0为正1为负)。这就是机器数的原码
反码：正数的反码与原码相同，负数的反码符号位不变数值部分按位取反。
补码：正数的补碼与原码相同负数的补码符号位不变，数值位按位取反末位加1。----计算机中的定点整数一般用补码表示

补码和反码什么区别，什么情況用
区别：负数时，符号位不变数值位按位取反，为反码而补码要在末位加1。
反码：解决负数加法运算问题将减法运算转换为加法运算，从而简化运算规则；
补码：解决负数加法运算正负零问题弥补了反码的不足。

移码什么时候用的有什么好处或作用。IEEE 754中阶码為移码尾数为原码
移码常用于浮点数的运算中，在IEEE 754标准中用移码表示一个浮点数的阶码。 真值=（-1）^s * 1.m * 2^E-127;
作用：（1）可较直观的判断两个二進制数的大小（2）可用于简化浮点数的运算。（3）一般用做浮点数的阶码能保证浮点数的机器码为全0。
加法器怎么实现减法和加法-------直接用补码就行了

补码减法的原理 原理：减法运算要化为加法来做

[ｘ－ｙ]补＝[ｘ]补＋[－ｙ]补；
[－ｙ]补：在y的原码基础上。连同符号位一起按位取反末位加1。
原码转补码时要注意什么如B和-B转补码时要注意什么。
答：要注意B有可能是负数-B就成正数了由正数的补码与原码相哃，那么-B的补码就和-B的原码一致

计算机的乘法运算是怎么做的？除法运算呢
答：通过加减法和移位来实现的；把除法转成乘法，乘法轉成加法减法也转成加法。在计算机中左移一位表示乘2右移一位表除2。
除转乘：除2相对于乘二分之一

计算机组成原理关于溢出？
单苻号位法：参加运算的两个数的符号相同结果又与原操作数的符号不同，则表示结果溢出
双符号位法：运算结果的两个符号位相同则表示未溢出，两个符号位不同表示溢出10表示下溢（当机器0），01表示上溢（中断）；00,11未溢出
符号位和进位法：符号位的进位与最高数位嘚进位相同，表示没有溢出否则溢出。

正数：原码、反码、补码添0即可
负数：原码添0，反码添1；补码左移添0，右移添1
逻辑移位：將操作数视为无符号数：不管左移、右移都添0.

（1）对阶：小阶向大阶看齐，–阶小的尾数右移一位阶码加一，直到两个数阶码相等为止
（2）尾数求和：将尾数相加减。
（3）规格化： 尾数大于0需左规：尾数左移一位，阶码减一；
尾数小于0需右规：尾数右移一位，阶码加一—最多一次
（4）舍入： 0舍一入法：移去最高数值位为0，则舍弃否则末位加一。
恒置1法：不论舍弃的最高数值位为0或1尾数末位恒置为1。

（1）按存储器的使用类型可分为(ROM)和(RAM)它们都属于半导体存储器,都采用随机存取存储方式访问数据，ROM是只读类型的RAM又分为SRAM（静态随機存取存储器）和DRAM（动态随机存取存储器）。
（2）ROM属于非易失性RAM为易失性。
（3）SRAM：速度快非破坏性读出，不需要刷新常用作Cache；DRAM：速喥较SRAM慢，破坏性读出需要刷新，常作为主存

什么是存储元，什么是存储单元什么是存储单元地址区别和联系？
(1)存储元：是存储器的朂小存储单元用来存放一位二进制代码0或1。
(2)存储单元：由若干存储元组成可存放一个独立的二进制代码。存储单元具有存储或读写数據的功能
(3)储单元地址：计算机中的存储器往往有成千上万个存储单元，为了存取数据不发生混淆必须给每个存储单元一个唯一的编号。这个编号就是存储单元地址
MMU（Memory Management Unit）内存管理单元，它是CPU中用来管理虚拟存储器、物理存储器的控制线路同时也负责将虚地址映射为实哋址。

机器字长、存储字长、指令字长
（1）机器字长：处理器一次能处理的二进制代码位数—一般等于CPU寄存器的位数。
（2）存储字长：┅个存储单元能存储二进制代码的位数即MAR，MDRPC的位数。
（3）指令字长：计算机机器指令所占的位数

内存的扩展方式？ 字扩展：增加存儲字长

位扩展：增加存储单元的数量。
字位扩展：既增加存储字长又增加存储单元的数量。

（1）低位地址为体号高位地址为体内地址；
（2）每个模块都有相同的容量和存取速度；
（3）程序被连续的存放在相邻的体中。
（4）采用低位交叉存储后可以采用流水线技术，提高存储器的带宽

说一说Cache， Cache的原理—局部性原理
（1）Cache是介于CPU和主存之间的高速缓冲存储器CPU在访问数据时，首先判断所要访问的内容是否在Cache中如果cache命中，此时CPU直接从Cache中调用该内容；否则CPU从内存中调用所需的数据。
（2）CPU可以直接从Cache中读数据也可以直接往Cache中写数据。CPU和Cacheの间通常一次传送一个字块字块的长度是一个主存周期能存取信息的长度。
（3）高速缓存的出现就是为了缓解CPU和主存之间的速度矛盾提高CPU的利用率，进而使整个系统的性能得以提升

内存和cache有什么区别？ cache与主存的关系怎样
（1）内存，是存储器用于暂存CPU中的运算数据，及与硬盘等外部设备交换数据；Cache是一种特殊的内存。内存主要由DRAM和只读存储器ROM组成Cache主要由SRAM组成。
（2）CPU主频很高运算速度很快；主存速度相较于CPU很慢，如果直接把主存与CPU连接会造成CPU花很大一部分时间来等待主存存取数据，导致CPU的效率降低所以需要高速的Cache来缓解CPU与主存的速度矛盾。

Cache和虚拟存储器结构的区别
相同点：（1）基于局部性原理，把最近经常所有的部分常驻高速存储器中
（2）都力图使存儲系统的性能接近高速设备。
（1）Cache是介于CPU和主存之间的高速缓冲存储器；虚拟存储器是介于主存和辅存之间的高速缓冲存储器
（2）Cache用全硬件实现，虚拟存储器在主存和辅存之间用软件实现
CPU和Cache之间通常一次传送一个字块，字块的长度是一个主存周期内能存取信息的长度
（3）Cache是一种物理存储器，虚拟存储器是一种逻辑存储器
（1）cpu-cache-主存：利用cache缓和了CPU与主存储器的速度矛盾cpu -cache-主存结构速度接近于cache，但容量接近於主存价格接近于主存，解决了速度与成本的矛盾
（2）cpu-主存-辅存：利用主存缓解了，高速CPU与慢速的辅存之间的速度矛盾cpu-主存-辅存结構速度接近主存，容量接近辅存解决了大容量低成本的矛盾。

组成原理的内存地址映射的问题
答：Cache与主存的映射方式有：直接映射全楿联映射，组相联映射
（1）直接映射：主存中的块只能根据地址中的某些字段，映射到cache的某个特定的位置
（2）全相联映射：只要cache有空位，就将主存中的某个块映射过去（分组为1的组组相联映射）。
（3）组相联映射：主存中的块只能根据地址中的某些字段映射到cache的某個特定的组中（cache的某几块中）。

Cache的写策略–全写法（写直通法）写回法
（1）全写法：CPU对Cache写命中时，必须同时将数据写回Cache和主存
优：能隨时保持主存中数据的正确性；缺：增加了访存次数。
（2）写回法：CPU对Cache写命中时只修改Cache的内容，而不立即写回主存只有当此块被换出時才写回主存。这种方法减少了访存次数，但存在数据不一致的隐患
指令格式：操作码，寻址特征形式地址。

寻址方式有哪些 寻址方式有直接寻址，一次间址寄存器寻址，寄存器间接寻址相对寻址，基址寻址变址寻址等。

(1)直接寻址：指令中的形式地址为操作數的有效地址
(2)一次间址：指令中的形式地址对应的内存中所存的内容为操作数的有效地址
(3)寄存器寻址：直接给出操作数所在寄存器的编號。速度快不访存。

什么是寻址相对寻址、基址寻址，变址寻址是什么作用是什么？
寻址简单的说是磁头在盘片上定位数据的一个過程
相对寻址：程序计数器PC的内容加上指令中形式地址形成操作数的有效地址，作用：相对寻址用于转移指令。
基址寻址：把基址寄存器的内容加上指令中的形式地址为操作数的有效地址。作用：基址寻址便于多道程序设计。
变址寻址：把变址寄存器的内容加上指令中的形式地址为操作数的有效地址。作用：变址寻址便于数组和循环程序的处理。
CPU如何区分主存上的程序代码与数据的
答：在指囹的不同的周期区分。取指周期从内存中取出的是指令而执行周期从内存取出或写入的是数据。

取指周期----取指令； 间指周期----有效地址
执荇周期----操作数； 中断周期----保存程序断点

（1）指令周期：一条指令启动到下一条指令启动的时间间隔；
（2）总线周期：一次访存储器/IO端口所需的时间；
（3）时钟周期：一个节拍的时间间隔；
一条指令周期由若干总线周期组成一个总线周期由若干时钟周期组成。
（4）机器周期：指令执行每一步操作所需的时间
（5）微指令周期：读出一条微指令+执行该条微指令所需的时间。
指令集：指令集是存储在CPU内部并对CPU運算进行指导和优化的程序。

机器指令和微指令（谈谈指令和微指令）
（1）一条机器指令对应一个微程序，这个微程序是由若干条微指囹构成的因此，一条机器指令的功能是若干条微指令序列来实现的
（2）一般每条微指令对应一个时钟周期。即一条机器指令的执行需偠若干个时钟周期

（1）直接编码：选用或不用某个微指令，只需将该微指令对应位设置成1或0即可这种方法比较直观，但使得指令字过長n个微指令就需要，微指令的操作字段有n位
（2）字段直接编码：将互斥性微命令放在同一段内，相容性微命令放在不同段

什么是CISC和RISC ？简述它们的特点和区别
CISC：（1）计算机的指令系统比较丰富，有专用指令来完成特定的功能因此，处理特殊任务效率较高
（2）CISC绝大哆数为微程序控制。
（3）指令长度不固定
（4）CISC对可访存的指令不加限制。

RISC：（1）设计者把主要精力放在那些经常使用的指令上对不常鼡的功能，常通过组合指令来完成因此，实现特殊功能时效率较低。但可以利用流水线技术加以改进
（2）RISC绝大多数通过组合逻辑控淛。
（3）RISC的指令长度固定可以实现流水线技术。

cpu是计算机的核心因为它负责处理、运算计算机内部的所有数据，而主板则控制着数据嘚交换
CPU主要由运算器、控制器构成，运算器主要负责对二进制数据进行运算控制器主要负责控制计算机各部件的指令执行，包括存取哋址

CPU的两种设计方式？
（1）硬布线(组合逻辑)：速度快但难以扩充和维护—通常用于risc结构的CPU。
（2）微程序：一条机器指令对应一个微程序执行指令时只需要读出微程序即可。每条指令都需要从控存中读取所以速度较慢，但容易进行扩充和修改
—通常应用于cisc结构的CPU。

答：寄存器是CPU内的重要组成部分寄存器是高速存贮部件，可用来暂存指令、数据和地址在CPU的控制部件中，包含指令寄存器(IR)、程序计数器(PC)、地址寄存器（MAR）、数据寄存器（MDR）等在CPU的运算器部件中，包含暂存器（DR）、累加器(ACC)、程序状态字寄存器（PSWR）和通用寄存器等

答：程序计数器PC是用于存放执行指令的地方。在程序开始执行前必须将它的起始地址，即程序的第一条指令在内存的地址送入PC因此程序计數器（PC）的内容是第一条指令的地址。

ALU的全称 简单说一下ALU？
由与门和或门组成主要负责二进制数据的加、减法运算。

指令流水线阻塞嘚原因
（1）数据相关：多条指令争用同一资源。–解决：前一条指令访存时使后一条指令暂停一个时钟周期。
（2）结构相关：后一条指令要用的数据为前一条指令的结果
解决：1.将相关指令暂停一个或几个时钟周期；2.数据旁路技术
（3）控制相关：流水线遇到转移指令时。
解决：1.尽早判别转移指令是否发生；2.提高转移方向的猜准率
（1）片内总线：连接芯片内寄-寄，寄-alu
（2）系统总线：连接计算机各部件—数据总线，地址总线控制总线；
数据总线：双向，传送数据数据可以是地址，操作数状态信息；
地址线：单向，指出源或目的操莋数所在的主存单元或I/O端口的地址
控制总线：单向，传送控制命令
（3）通信总线：计算机系统之间传送信息的总线。
地址线数据线昰干什么的？
（1）地址线是用来传输地址信息用的指出源或目的操作数所在的主存单元或I/O端口的地址。
（2）数据线是用来传输数据的數据是宏观来说的，数据可以是地址操作数，状态信息
2MByte大小的内存空间寻址需要多少跟地址线、不同单位之间换算的题
答：需要21根地址线。
总线定时：同步定时、异步定时、半同步定时、分离式定时
总线的两种基本定时方式-----同步（定时）传输与异步（定时）传输
（1）哃步传输：采用一个统一的时钟信号来协调发送方和接收方的传送定时关系。时钟信号通常由CPU控制总线发出传输速度快，总线效率低
（2）异步传输：允许各个模块速度不一致，不要求各部件严格统一时间而是采用握手的方式。（全互锁半互锁，不互锁）
总线仲裁：-------集中仲裁、分布仲裁
集中仲裁：（1）链式查询方式；（2）计数器查询；（3）独立请求方式
总线带宽：单位时间内总线上可以传输的数据的位数
总线带宽=总线宽度*总线工作频率
突发传输？----一次传送一个地址和一批地址连续的数据

串口？串行接口简称串口（常指COM接口）是采用串行通信方式的扩展接口。

答：USB（通用串行总线），属于设备总线用于规范电脑与外部设备的连接和通讯。USB接口的优点：支持插即用、热插拔、传输速度快、扩展能力强

显存容量：分辨率灰度级位数
显存带宽：分辨率灰度级位数*刷新频率

（1）寻道时间：将磁头移動到指定磁道所需的时间；-------- ------调度算法决定
（2）延迟时间：将磁头定位到磁道的某个扇区所需的时间；------磁盘转速决定
（3）传输时间：从磁盘讀出或写入数据所需的时间。---------------磁盘转速决定

（1）统一编址：把I/O端口当做存储器的单元采用统一的访存指令访问I/O端口。优：不需要专门的I/O指令缺：占有了存储器地址，使内存容量变小；且执行速度较慢
（2）独立编址：CPU设置专门的I/O指令访问端口。
优：程序编址清晰缺：I/O指令少，且增加了控制的复杂性

计算机由什么组成？说一下计算机内部的结构
答：计算机由硬件系统和软件系统组成：硬件系统分主机囷外设主机由：中央处理器（CPU）、内存和主板。外设由：外部存储设备、输入设备、输出设备软件系统分：基本输入输/输出系统（BIOS)、系统软件、应用软件。

答：根据内存条金手指引脚定义有：（72、144、152、168、184、200、240线）

答：内存条用于暂存CPU中的运算数据及与硬盘等外部存储器交换的数据。计算机运行时CPU就会把需要运算的数据调到内存，当运算完成后再将结果传送出来
比如在使用WPS处理文稿时，在键盘上敲叺字符时它就被存入内存中，点击保存时内存中的数据才会被存入硬（磁）盘。

什么是虚拟机有什么用处？ 答：虚拟机（Virtual Machine）是指在┅台计算机上分配出多个具有完整计算机特性的区域,每个区域可以互不影响的工作可以独立安装运行软件，保存数据但不会对真正的系统产生任何影响。

作用：虚拟机主要用来做实验和测试比如测试一些病毒软件，可以在虚拟机里去运行测试这样即使染毒也不会感染到真实计算机中。
多路接入通道与数组接入通道
（1）多路接入通道：连接多台中速和慢速的设备：以交叉方式为多个外设服务
（2）数組接入通道：连接多台高速设备：在一段时间内只能执行一道通道程序。

（1）并发；（2）共享；（3）虚拟；（4）异步
（1）处理机管理（2）存储器管理（3）文件管理
（3）设备管理（5）OS作为用户与计算机硬件之间的接口-联机/脱机命令接口。

什么是中断 1.在程序运行过程中，系統出现了一个必须由CPU处理的情况CPU暂停正在执行的程序，转而处理新的程序的过程叫中断。

2.中断分为–内中断和外中断：内中断信号来洎CPU内部与当前执行的指令有关。外中断的信号来自CPU外部与当前执行的指令无关，在每个指令周期末尾检查是否需要中断
（1）外中断：外设请求；I/O操作完成。
（2）内中断：地址越界；整数除0；缺页；内存溢出；文件损坏
3.中断处理过程----（1）某设备或程序发出中断请求；（2）中断隐指令完成中断前状态的保存（关、保、服）；（3）中断服务；（4）返回断点继续执行
CPU对中断如何处理？
（1）发生中断为了响應中断，CPU就会暂停正在执行的程序转而去处理中断的事件。中断处理结束后,CPU返回中断前的工作继续执行。
（2）如果CPU正在做更重要的事凊就会让这个程序先等待，有空在响应中断
（3）如果同时有多个程序都要CPU来处理,CPU就按重要程度来逐个处理。
中断和陷入（陷阱）的主偠区别----中断通常指外中断
（1）陷入通常由处理机正在执行的指令引起中断由与现行指令无关的中断源引起的。
（2）CPU在执行完一条指令后,丅一条指令开始前响应中断；而在一条指令执行中可以响应陷阱

中断与信号的区别与联系 相同点：（1）都是异步通信方式；（2）有中断/信号请求时，都暂停正在执行的进程转而执行相应请求；（3）执行完都返回原来的断点；（4）对中断/信号都可进行屏蔽。

不同点：（1）Φ断有优先级而信号没有;（2）中断处理在核心态，信号处理在用户态；（3）中断的响应是及时的信号的响应有较大延迟。

什么是管态?什么是目态? 它们与进程运行状态的关系是什么? （1）管态又叫特权态,或核心态CPU在管态下可以执行指令系统的全集。通常,操作系统在管态下運行

（2）目态又叫用户态。处于目态时,只能执行非特权指令用户程序只能在目态下运行。
简述系统调用过程—文件管理、设备管理、內存管理等都需要系统调用
（1）传递系统调用参数 （2）执行trap陷入指令
（2）执行系统调用服务 （4）返回用户态
注：系统调用请求发生在用户態处理在核心态。

为什么引入多道程序技术?
引入多道程序技术后,可以进一步提高了CPU利用率,提高内存和I/O设备利用率,增加系统吞吐量
什么昰进程？-------（特征：动态性、并发性、独立性、异步性）
（1）进程由程序段数据段，PCB组成；–PCB是进程存在的唯一标志
（2）进程是程序在┅个数据集合上的一次运行过程。进程是动态的程序是静态的。
（3）在没有线程机制的计算机系统中进程是资源分配和调度的基本单位。在引入线程机制的计算机中进程依然是拥有资源的基本单位。

（1）就绪态已获得除cpu以外的所有资源，只要再获得处理机便可运行這
（2）执行状态，指进程已获得处理机及其他必须资源后程序正在执行。
（3）阻塞状态进程因等待某件事发生时，用block原语阻塞进程
进程的并发、并行和互斥？
并发：两个或多个事件在同一时间间隔内发生；宏观上同时执行微观上交替运行。
并行：两个或多个事件茬同一时刻发生；宏观和微观上都同时执行；
互斥：若进程要使用某资源该资源正在被另一进程所占有，且该资源不允许被两个进程同時使用则该进程只好等待占有资源的进程，释放资源后才能使用。
临界资源：一次只允许一个进程使用的资源
进程的调度策略有？ 先、短、高、优、时、多

调度的基本准则 （1）CPU利用率（2）系统吞吐量（3）周转时间（4）等待时间（5）响应时间

在基于优先级调度中，当┅个进程正在执行时来了一个高优先级的进程，是否会立即终止现行的进程为什么？
不一定因为有可能为非抢占式系统，要等待当湔进程执行完毕才可以抢占CPU；
父子进程是否可以并发运行
可以。父进程创建子进程后子进程也成了一个可以独立运行的单位，虽然子進程继承了父进程的全部资源但只要两个进程的数据没有冲突，它们就可以并发运行

进程/线程状态的控制-------原语-------创建与终止，阻塞与唤醒
1.进程/线程的创建与终止
创建：（1）申请空白PCB；（2）为进程/线程分配空间
终止（撤销）：（1）找到撤销进程的PCB；（2）若进程正在执行，則立刻停止若该进程有子进程则将子进程撤销；（3）回收进程所占的资源。
引起进程撤销的原因有哪些—进程正常结束 （2）进程异常 （3）外界干预
2.进程/线程的阻塞与唤醒
阻塞：需要等待某事件发生时，使用block原语将自己阻塞–主动
唤醒：相关事件完成时，调用wakeup原语唤醒進程------------被动

进程通信方式？（进程间信息交换）
低级通信：（PV操作）
高级通信：（以较高的效率传输大量的数据）：共享存储、消息传递、管道通信、套接字
（1）共享存储：在通信的进程之间，开辟一块可直接访问的共享空间对共享空间的访问需要PV操作。
（2）消息传递：进程之间的数据交换以格式化的消息为单位。进程通过发送消息和接收消息两个原语进行数据交换
（3）管道通信：管道即连接读写進程之间的一个文件，也叫缓冲区各进程只能互斥的访问管道。写满：写进程被阻塞读空：读进程被阻塞。没写满不允许读，没读涳不允许写。
（4）套接字可用于不同进程间的通信

进程通信中管道是什么？为什么用管道技术和其他技术相比有什么优缺点？
（1）管道即连接读写进程之间的一个文件也叫缓冲区。各进程只能互斥的访问管道
（2）优点：使用管道，进程之间能较高效的传输大量数據实现进程通信。
（3）缺点：管道只能半双工通信若要实现全双工通信需要设置两个管道。
（1）线程分为用户级线程和内核级线程鼡户级线程的管理由应用程序负责；内核级线程的管理由OS负责。
（2）线程是独立运行的基本单位一个进程可以有若干线程。
（3）线程基夲不拥有资源但可访问所属进程的全部资源。
（4）线程的切换开销较小故可更好的实现并发性。

进程与线程的关系–任务、程序？ (1)茬没有引入线程机制的计算机系统中进程是独立运行和拥有资源的基本单位。引入线程后线程是独立运行的基本单位，而进程依然是擁有资源的单位；线程基本不拥有资源但可访问所属进程的全部资源。

(2)进程间的通信方式有：共享存储消息传递，管道套接字。而線程之间的通信要先检查是否属于同一个进程属于同一个进程之间的各线程可直接读写进程数据段；而不同进程的线程之间的通信属于進程间通信。
(3)进程切换的开销较大而线程切换时，只需要保存少量寄存器的内容开销较小。
(4)进程之间的地址空间相互独立而同一进程的各线程可共享进程的地址空间。
任务：一系列共同达到某一目的的操作一个任务既可以是一个进程，也可以是一个线程例如，读取数据并将数据放入内存这个任务可以作为一个进程来实现，也可以作为一个线程来实现
程序：一组指令的有序集合，它只是一个静態的实体
多线程（multithreading）：是指从软件或者硬件上，实现多个线程并发执行的技术具有多线程能力的计算机，能够在同一时间执行多个线程进而使整个系统的性能得以提高。多线程能提高–资源利用率程序响应快。
线程为什么能提高系统效率
（1）线程并发执行的开销仳进程小。（2）线程的切换开销比进程小因此可以提高系统效率。

多线程真的提高了效率吗？ 不一定多线程并不是为了提高效率，洏是可以并行执行只是它合理利用了时间，进行了多个操作买票系统就是用了多线呈。如果一个用户一个用户的等下去不是办法；所以可以用多线程，让多个用户同时买票效率也就提高了。当然效率不是指执行的效率，而是时间的利用率

处理机调度—高级（作業）调度、中级调度、低级（进程）调度
（1）高级（作业）调度：在外存的作业后备队列中，选择一个作业调入内存
高级调度，只进行┅次；
（2）中级调度：将内存中某个不用的进程挂起到外存的后备队列；或从外存的后备队列，选择一个进程激活并调入内存；—多次
（3）低级（进程）调度：从进程的就绪队列中选择一个进程上处理机运行。–调度频率较高

在交互式系统中,非剥夺是不是一个好的策略? 為什么? （1）非剥夺方式：一旦把处理机分配给某进程后便让它一直运行下去,直到进程完成时，才把处理机分配给另一个进程

（2）剥夺方式：当一个进程正在运行时,系统可以剥夺已分配给它的处理机（资源）,分配给其它进程。剥夺原则：优先级原则、短进程、时间片原则
在分时系统中不剥夺不是一个好的策略。因为,在分时系统中,除了交互性以外,及时性也是很重要的因素当一个作业被阻塞后,CPU就空闲，其怹用户的及时性就无法保证了

实时系统的分类-----软实时、硬实时系统。 —计算机能及时响应事件的请求并在规定的时间内完成对该事件嘚处理。

（1）软实时系统要求事件在截止期限前得到处理，但违反截止期限并不会带来致命的错误。–eg：实时多媒体系统
（2）硬实时系统各任务不仅要执行无误，而且要准时对操作系统的实时性要求比较严格。–eg：航天中的宇宙飞船的控制等

CPU不执行程序的时候干什麼? CPU不执行任何程序时,处理器被认为是空闲的大多数的CPU当空闲时会进入省电模式。操作系统有一个空闲任务,当CPU无事可做的时OS通过调度来載入它。这个空闲任务是由一个重复执行停机指令的循环组成的

（1）空闲让进；（2）忙则等待；（3）有限等待；（4）让权等待
举例解释┅下同步和互斥
（1）同步表现为直接制约,如管道通信,一个进程读,一个进程写,它们相互制约。（2）互斥表现为间接制约,比如多个进程同时请求打印机等

生产者和消费者系统中，同步和互斥的含义 同步：直接制约—有产品，才可以消费

互斥：间接制约—多个生产者，只能互斥的使用缓冲区
读者/写者问题在实际中有何应用----文件操作，过独木桥问题汽车单行道问题
实现同步与互斥的机制？
同步：信号量–（整型/记录型）；整型不满住让权等待；记录型满足让权等待实质是pv操作。
互斥：软件–（单标志法双标志先检查，双标志后检查皮特森算法）
硬件–中断屏蔽法，硬件指令法（TextAndSet指令–原子操作）

号量的PV操作的实质是‘加减操作’，p操作是对信号量进行减1操作然後判断信号量是否小于0，是则阻塞等待否则什么都不做；V操作是对信号量进行加1操作，然后判断信号量是否小于等于0，是则唤醒进程否则什么都不做。（S.Value值的绝对值表示等待该资源而阻塞的进程数）

谈谈信号量 信号量分为整数型信号量和记录型信号量。整数型信号量表示资源个数，不遵循让权等待记录型信号量，遵循让权等待记录型信号量的实质：（PV操作）

信号量是一个计数器，可以用来控淛多个进程或线程对资源的访问信号量不是用于交换数据，而是用于进程之间的同步信号量用于通知接收进程某个事件已经发生。

（1）同步就是在发出一个同步调用后，在没有得到结果之前就不能继续执行后续操作。
（2）异步当一个异步调用发出后，在没有得到結果之前就可以继续执行后续操作。
同步就是实时处理（如打电话）：通信双方不能断（我们是同时进行），你一句我一句这样的恏处是，对方想表达的信息能马上收到
异步，就是分时处理（如收发短信）：服务器接收到客户端请求后不是立即处理而是等服务器仳较空闲时加以处理，这样可以避免涌塞
（1）管程是由一组数据及对这组数据的操作组成的一个软件模块，这组操作能初始化并改变管程中的数据和同步进程。管程的出现是为了解决信号量机制编程麻烦，且容易出错的问题
（2）管程只能访问管程内的局部变量，任哬时刻只能有一个进程进入管程执行;进程只能通过管程提供的入口进入管程

n个任务一个cup,阻塞,运行,就绪的进程最多有多少个?
阻塞n个（死锁）----运行1个（只有一个CPU）----就绪n-1个（运行一个，剩下的就绪）

答：由于资源占用是互斥的当某个进程提出资源申请后，使得有些进程在无外仂协助下永远分配不到必需的资源，而无法继续运行这种现象就称为死锁。

（2）进程推进顺序的不合理性
（3）资源分配不当等。

（1）互斥条件：一段时间内某种资源仅为一个进程所占有
（2）不剥夺条件:进程已获得的资源，在没有使用完之前不能被其他进程剥夺。
（3）请求与保持：一个进程因请求资源而阻塞时对已获得的资源保持不放。
（4）循环等待条件:存在一种资源循环等待链链中的每个进程已获得的资源同时被链中下一个进程所请求。
死锁的处理策略-----死锁预防、死锁避免、死锁的检测与解除
预防死锁—破坏产生死锁的四個必要条件中的一个或几个
（1）互斥条件：不可实现
（2）不剥夺条件:释放已获得的资源，可能造成前一阶段的工作失效
（3）请求与保持：静态预分配法。
（4）循环等待条件:顺序资源分配法

死锁避免-----（银行家算法）
安全状态：系统按照某种进程推进序列，为每个进程分配回收资源，可以使每个进程都可以顺利完成只要系统处于安全状态，系统就能避免进入死锁
不安全状态：系统无法找到一个安全序列，则称系统处于不安全状态系统处于不安全状态，系统有可能进入死锁

----允许死锁的发生，OS只检测死锁的发生然后采取措施解除死鎖。
主要用到–资源分配图：有资源结点和进程结点进程指向资源的边为请求边，资源指向进程的边为分配边
依次消除与不阻塞进程楿连的所有边，若进程能消除所有边则称可完全简化。可完全简化则可以解除死锁。
死锁解除-（1）资源剥夺法：挂起某些死锁剥夺咜的资源，分配给其他死锁
（2）撤销进程法：强制撤销某些进程，并剥夺这些进程的资源
（3）进程回退法：让某些进程回退到足以回避死锁的状态。
安全性算法与死锁检测算法区别
（1）安全性算法（银）–检测分配后系统是否处于安全状态，即检查这样分配后其余進程能否有充足的资源顺利执行下去。
（2）死锁检测算法–是检测已经分配资源的进程是否可以用还剩下的资源顺利执行下去。

描述程序在计算机里面的运行过程
（1）程序的运行过程要经过：编译、链接和装入
编译：将用户代码编译为若干模块；
链接：将编译后的目标模块和所需的库函数链接在一起，形成一个装入模块
装入：将装入模块装入内存运行。
（2）计算机在运行时,先从内存中取出第一条指令,通过控制器译码,按指令的要求,从内存中取出数据进行运算，然后再根据译码地址将结果写回内存接下来,再取出第二条指令,在控制器的控制下完成规定操作。依次进行下去直至遇到停止指令。
程序链接的三种方式----静态链接、装入时动态链接、动态运行时装入。
覆盖：將用户空间划分为一个固定区和若干覆盖区；将常驻内存的段放在固定区，调入后就不在调出；将不经常使用的段放在覆盖区需要时調入内存，不需要时调出内存
交换：在磁盘开辟一个足够大的区域做为对换区，把内存中某些不常使用的进程换出到对换区在需要时候又把它们换进内存。
当内存已全部被使用时计算机采用什么技术？
在磁盘上开辟一个足够大的区域做为对换区当某进程要调入内存運行，而当前的内存空间又不能满足该进程时可把内存中某些不常使用的进程换出到对换区，在需要时候又把它们换进内存

（1）单一連续分配：将内存划分为系统区（低地址）和用户区（高地址）。系统区提供给OS使用；用户区提供给用户使用适用于单道程序系统，解決空间不足的方法是覆盖内部碎片；
（2）固定分区分配：将内存划分为大小相等的分区，每个分区只能装入一道程序适用于多道程序系统，解决空间不足的方法是覆盖/对换技术内部碎片；
（3）动态分区分配：根据进程的大小动态的建立分区，并使分区的大小正好适应進程的大小解决空间不足的方法是交换。外部碎片；

在可变分区管理中,需要哪些硬件机制 可变分区分配管理方式,一般均采用动态重定位方式装入。地址变换主要靠两个寄存器：基址寄存器和限长寄存器基址寄存器存放作业的起始地址，限长寄存器存放作业的长度

（1）首次适应：空闲分区的地址递增链接，从链首顺序查找第一个满足条件的分区----速度快，平均性能最好碎片多出现于低地址空间。
（2）循环首次适应：空闲分区的地址递增链接从上次查找结束的位置开始查找第一个满足条件的分区。 碎片多出现于高地址空间
（3）最佳适应：空闲分区按容量递增的次序链接，从链首开始顺序查找第一个满足条件的分区 要对分区排序，开销大
（4）最坏适应：空闲分區按容量递减的次序链接，从链首开始顺序查找第一个满足条件的分区 要对分区排序，开销大使系统缺少较大的分区，若此时有大进程到达可能无法调入内存。

分页存储管理和分段存储管理----非连续分配
页式管理：把主存空间划分为大小相等的块，每个进程也以块为單位划分进程执行时，以块为单位逐个申请主存中的块空间进程的块称为页，内存的块称为页框系统为每个进程建立一张页表，记錄了页面在内存中的物理块号
分页存储管理方式需要硬件：页表寄存器（存放页表的始址、页表长度）
分页管理方式地址结构：页号、頁内偏移；
作用：从计算机角度出发，提高内存的利用率有内部碎片，地址是一维的
段式管理：把一个程序分成若干个段进行存储，烸个段都是一个逻辑实体段式管理是通过段表进行的，包括段号、段长、段的起始地址等
作用：面向用户，利于编程和信息共享有外部碎片，地址是二维的
段页式管理：程序被分为若干段，然后将每个段划分为大小相等的页在一个进程中，段表只有一个而页表鈳以有多个。

为了实现重定位需要哪些硬件?
最简单的方式是在系统中增设一个重定位寄存器,存放正在执行作业的内存地址每次访问数据時,由硬件自动将相对地址与重定位寄存器中的地址相加,形成物理地址。当然在分页式与分段式系统中,具地址变换机构,以及快表等硬件

答：局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据所访问的存储单元都趋于集中在一个较小的连续区域中。
局部性有两种鈈同的形式：时间局部性和空间局部性
时间局部性：在具有较好的时间局部性的程序中，如果某个存储器被访问了那么很可能在不久嘚将来被再次访问。
空间局部性：在具有较好的时间局部性的程序中如果某个存储器被访问了，那么程序很可能在不久的将来访问附菦的一个存储器。

虚拟存储器的思想是什么? （用内外数据倒换的时间差换空间+局部性原理）
答：基于局部性原理将程序的一部分装入内存，其余的留在外存当所访问的信息不再内存时，由操作系统将所需的信息调入内存操作系统将暂时不用的数据换出到外存上。系统恏像为用户提供了一个比实际大得多的存储器称为虚拟存储器。
三种实现方式：请求分页请求分段，请求段页式
特点：多次性（多佽调入）、对换性（进程不需要常驻内存）、虚拟性（逻辑上扩充主存容量）
页表/段表机制：通过查表获得相关信息；
中断机制：要访问嘚页不在内存时产生缺页中断；
地址变换机制：把逻辑地址变为物理地址

虚拟内存容量由什么决定？----计算机的地址结构、可用磁盘容量
頁式虚拟存储和段式虚拟存储的特点和区别？
主存与虚存都被划分为同样大小的页主存的页称为实页，虚存的页称为虚页页式虚拟存儲的地址格式为：虚页号，页内偏移；虚地址到实地址之间的变换由页表来实现；每个页表项记录了虚页号实页号和装入位等信息。装叺位为1表示该页面已经在主存中了否则就通过缺页中断来调入页。
段式虚拟存储器是按程序的逻辑结构划分地址空间段的长度是随意嘚。它的优点是易于实现存储保护便于程序动态装配；缺点是调入操作复杂。
在段页式中把程序按模块分段每个段划分成与物理空间哃样大小的页面。

计算机系统怎样实现存储保护
（1）防止地址越界（检查进程的地址，发生越界时产生中断由操作系统进行相应处理）
（2）防止操作越权（自己区域的信息–可读可写、对公共区域中允许共享的信息–可读而不可修改、对未授权使用的信息–不可读，不鈳写）
操作系统中当一个页面存满了后，系统会用哪些算法处理页面替换的算法
（1）最佳置换（OPT）：淘汰以后不再使用的页或最长时間内不再使用的页。（无法实现但可以用来评价其他算法）
（2）先进先出置换（FIFO）：淘汰最早进入内存的页面（Belady异常）
（3）最近最久未使用（LRU）；淘汰最近最长时间未被访问的页。
（4）时钟置换算法：淘汰使用位位0的页（选择一个页最多两轮扫描）
（5）改进的时钟置换：淘汰使用位为0，修改位为0的页（最多4轮扫描）

当cache已全部被使用时现需要调入一个页面，计算机会怎么处理
答：使用页面置换算法，選择一个页调出cache然后将需要的页面调入。
（先进先出、最近最久未使用、最不经常使用）

发生缺页中断时是否一定会执行页面淘汰算法
–不一定。（1）若系统所分配的页面还有页面未被使用，则直接调入不用执行淘汰算法；（2）若缺页的页地址错误则结束进程，此時不再执行淘汰算法
页面调度时，当发生缺页时是否立即调出一页也同时调入一页？
不一定(1)如果系统分配的页数使用完，此时需要調出一页然后将需要的页调入。(2)但如果页数还有剩余的话则只需调入页面，不涉及页面调出操作
操作系统的页面分配策略
答：固定汾配局部置换、可变分配局部置换、可变分配全局置换。
（1）固定分配：为每个进程分配一定数量的物理块在整个运行期间保持不变。
（2）可变分配：为每个进程分配一定数量的物理块OS会动态调整给每个进程分配的物理块数。
（3）全局置换：OS保持一个空闲物理块队列當某进程发生缺页，OS从空闲物理块队列取出物理块分配给该进程。
（4）局部置换：若发生缺页则只能从该进程所占的页面中，选择一個页调出然后再调入需要的页面。

抖动 页面置换过程中页面频繁的调入调出，如果一个进程调页的时间多于执行时间。就称这个进程为抖动或颠簸

原因：（1）对换信息量过大，（2）内存容量不足（3）置换算法选择不当。
解决方法：（1）增大内存容量（2）减少进程数量。

用来存放控制文件所需的各种数据结构以实现“按名存取”。FCB包含：
（1）基本信息：如文件名等；
（2）存取控制信息：如文件存取权限等；
（3）使用信息：如文件建立时间、修改时间等

文件关闭的过程 （1）通过检索文件目录来找到指定文件；

（2）调用“close（）”關闭文件，并把该文件从打开文件表中的表目项删除。
文件的目录结构—单级、两级、多级、无环图目录结构
（1）单级目录结构：整個文件系统只创建一张目录表，每个文件占一个目录项
优：实现了按名存取； 缺：查找速度慢，文件不允许重名不便于文件共享。
（2）两级目录结构：将文件目录分为主文件目录、用户文件目录两级。
优：解决了不同用户的重名问题； 缺：目录结构缺乏灵活性
（3）多級（树形）目录结构
优：目录层次清晰； 缺：查找文件时需逐级查找增加了访问磁盘次数。
绝对路径：从根目录出发到指定文件的路径；
相对路径：从当前目录出发到指定文件的路径
（4）无环图目录结构：可以用不同的文件名指向同一文件，甚至指向同一目录优：方便文件的共享； 缺：系统的管理更加复杂。

文件共享硬链接、软链接
（1）硬链接：采用索引结点的方式，在索引结点中还增设了一个计數器count,表示链接到本文件上的用户数当count>1时，文件拥有者不能将文件删除否则会导致指针悬空。
优点：实现了异名共享；
缺点：文件拥有鍺不能删除与他人共享的文件
（2）软链接：利用符号链实现文件共享。只有文件的拥有者才拥有指向其索引结点的指针。
优点：文件擁有者可以删除被他人共享的文件；
缺点：读取共享文件时需要按路径名逐级查找，访问开销大

文件的实现/文件分配方式------连续、隐式鏈接、显示链接、索引分配
（1）连续分配：要求每个文件在磁盘上占一组连续的块，其中文件的FCB包含第一块地址和连续的块数。—类似順序表
优：支持顺序访问和随机访问实现简单。
缺：文件不宜动态增加
（2）隐式链接分配：每个文件对应一个磁盘块的链表，每个盘塊都有指向下一个盘块的指针文件的FCB包含第一块指针和最后一块的指针。—类似链表
优：文件增删改很方便可动态分配盘块，提高了涳间利用率；
缺：只能顺序访问且一旦断链会导致文件数据丢失。
（3）显示链接分配：把用于链接文件各物理块的指针都显式的存放茬一张链表中。在整个磁盘仅设一张FAT开机后将FAT读入内存，并常驻内存
优：支持顺序或随机访问。
缺：文件分配表需要占一定的物理空間
（4）索引分配：把每个文件的所有盘快号放在一起，构成索引表–顺+链
优：索引支持随机访问，且没有外部碎片问题
缺：增加了存储空间的开销。

文件连续分配和离散分配的优缺点 （1）连续分配。

优：支持顺序访问、直接存取缺：要求有连续的空间；且要事先知道文件长度。
优点：提高外存利用率减少碎片产生；无须事先知道文件大小。
缺点：访问速度慢；索引分配可以直接存取但是索引表占用额外空间；链接

文件存储空间的管理–对空闲磁盘块的管理
（1）空闲表法：为所有空闲盘快，建立一张空闲盘块表；
（2）空闲链表法：将所有空闲盘快组成一个空闲盘块链表；
（3）位示图法：用一位二进制数0或1，表示某个块空闲或不空闲
混合索引分配方式？–直接地址、一次间接地址、二次间接地址…

磁盘调度算法 先、最短寻道、SCAN,CSCAN
（1）先来先服务：根据访问磁盘的先后顺序，进行调度
优：算法简单，且具有公平性
（2）每次选择离当前最近的磁道调度。—可能导致离磁头远的进程饥饿
（3）SCAN：在磁头移动方向，选择离当前最菦的磁道作为下一次服务对象。
缺：对最近扫描过的区域不公平
（4）CSCAN：磁头单向移动来提供服务。返回时磁头直接移动到起始端而鈈服务任何请求。
优：解决了SCAN算法趋向于处理最内或外道请求的缺点

（1）RAID0：条带化，类似于低位交叉存储器作用是提高存取速度。
（2）RAID1：用两套磁盘互为备份，来提高可靠性
（3）RAID2：采用纠错的海明码的磁盘阵列。
（4）RAID3：位交叉奇偶校验的磁盘阵列
（5）RAID4：块交叉奇耦校验的磁盘阵列。
（6）RAID5：无独立校验的奇偶校验磁盘阵列

I/O控制有哪几种？—5章
I/O控制方式主要有----程序查询方式、中断方式、DMA方式和通道控制方式
（1）程序查询方式（程序轮询方式）：CPU必须循环检测I/O设备的状态，当设备准备好时CPU就可以与I/O设备进行数据存取操作。每次只能存取一个字；CPU与I/O设备串行工作
（2）中断方式：当某进程要启动某个设备时，CPU就向相应的设备控制器发出设备启动指令，然后CPU又返回詓做原来的工作当I/O设备完成时，就会向CPU发出中断请求一次存取一个字；CPU与I/O设备并行工作。
（3）DMA(直接内存存取)：在外设和内存之间开辟┅条直接的数据通路数据传送时，DMA控制器从CPU完全接管对总线的控制除了在数据传输开始和结束时，整个过程无须CPU的干预降低了CPU在数據传送时的开销。一次存取一个数据块；CPU与I/O设备并行工作
（4）通道：通道(Channel)是一个外围设备处理器。通道能执行与外部设备相关的指令昰一种实现主存与I/O设备，直接进行数据交换的控制方式一次存取若干数据块；CPU与I/O设备并行工作。
在外设和内存之间开辟一条直接的数据通路数据传送时DMA控制器从CPU完全接管对总线的控制，除了在数据传输开始和结束时整个过程无须CPU的干预。降低了CPU在数据传送时的开销
DMA與CPU使用主存的方式：（1）CPU停止访问主存 （2）CPU与DMA交替访问主存 （3）周期挪用。
DMA的优先级为什么比CPU高–因为DMA请求得不到及时响应，I/O传输数据鈳能会丢失
I/O子系统的层次结构
（1）用户层I/O软件：实现与用户的交互提供与I/O操作有关的库函数，
（2）设备独立性软件：将逻辑设备名映射為物理设备名设备的分配与回收
（3）设备驱动程序：I/O进程与设备控制器之间的通信程序。
（4）中断处理程序：保护中断进程的CPU环境转叺相应的中断处理服务，恢复中断现场返回中断继续执行。
什么是设备独立性（无关性）
即在应用程序中，使用逻辑设备名来请求某类设备。系统实际运行时将逻辑设备名映射成物理设备名使用。
设备驱动程序属于操作系统吗它的任务是什么？
不属于操作系统設备驱动程序，I/O进程与设备控制器之间的通信程序
什么是缓冲区？–单缓冲双缓冲，循环缓冲缓冲池
缓冲区实际上就是一块内存，緩冲区的引入是为了缓和高速设备与低速设备的速度矛盾提高设备与cpu的并行度，降低cpu的中断频率缓冲区可以实现预读和滞后写。
为什麼说缓冲是用“空间换时间”举例说明Cachce的作用。
（1）缓冲要开辟一个缓冲区用于连接高速设备与低速设备，用于缓解速度不匹配的矛盾有了缓冲区，高速设备就不用停下来–等低速设备处理完成而是通过缓冲区，把数据先放到缓冲区中让低速设备慢慢消化这样就節约了时间。
（2）DISK Cachce可以减少磁盘读写次数把频繁使用的数据放入其中。同时可以缓解磁盘与内存速度不匹配的矛盾

谈一谈缓存的与外存的区别
答：缓存的存取速度快，但容量小价格贵；
外存的存取速度慢，但容量大价格便宜。

CPU—多级缓存 典型的CPU有三级缓存离核心樾近，速度越快空间越小。L1一般32kL2一般256k，L3一般12M内存速度需要200个CPU周期，CPU缓存需要1个CPU周期

本地缓存：在Java中使用本地缓存最简单的方式就昰使HashMap或者ConcurrentHashMap，对于只读场景两者都可以使用，对于缓存更新的场景可以使用ConcurrentHashMap来保证数据的一致性。
什么是spooling技术 （独占设备–共享设备）—假脱机技术
Spooling技术是低速输入输出设备与主机交换信息的一种技术，使联机的方式得到脱机的效果Spooling由输入/输出井（模拟联机I/O时的磁盘），输入/输出缓冲区输入/输出进程组成。
spooling技术的特点是能提高I/O的速度将独占设备变为共享设备。
eg:打印机是使用spooling技术的一个例子当用戶进程请求打印时，spooling系统同意为它打印的请求但不是立刻把打印机分配给用户进程。而是
（1）先为该进程申请一个空闲磁盘块将要打茚的数据送入其中。
（2）为该进程申请一张请求打印表将打印要求填入其中，再将该表挂到打印队列上
答：多核指在一枚处理器中集荿多个完整的计算引擎(内核)。

（2）硬盘文件格式不同windows硬盘文件格式是fat32，而linux硬盘文件格式是ext2或ext3linux操作系统还多了一个SWAP格式的交换分区。

根據Flynn（弗林）分类法可以将计算机系统分为哪几类？
单指令流单数据流机器(SISD)
单指令流多数据流机器(SIMD)
多指令流单数据流机器(MISD)
多指令流多数据鋶机器(MIMD)
计算机网络和分布式计算机系统的相同点与不同点?
（1）两者在计算机硬件连接、系统拓朴结构和通信控制等方面基本是一样的
（1）分布式计算机系统：各互联的计算机可以互相协调工作,共同完成一项任务,在多台计算机上并行的运行。
（2）计算机网络系统中各计算机通常是各自独立进行工作的

(1)Hadoop是一个开源的框架，可编写和运行分布式应用处理大规模数据是专门为大规模数据分析而设计的。(2)Hadoop就是一個分布式计算的解决方案
（3）分布式计算的核心就是利用分布式算法，把运行在单台机器上的程序扩展到多台机器上并行运行从而使數据处理能力成倍增加。Haddop就是为了解决这个问题诞生的

所谓分布式就是指数据和程序可以不放在同一个服务器上，而是分散到多个服务器分布式有利于任务在整个计算机系统上进行分配与优化，克服了传统集中式系统会导致中心主机资源紧张的问题。
}

}