文档内容
数据结构要点
第一章 概 论
数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。
数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。
·链式存储结构：如链表。
·索引存储结构：·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·数据运算。·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
************************************************************************
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。·原子类型：由语言提供。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
************************************************************************
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。
************************************************************************
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：·算法是正确的；
·执行算法的时间；
·执行算法的存储空间（主要是辅助存储空间）；
·算法易于理解、编码、调试。
************************************************************************
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 空间复杂度：是某个算法的空间耗
费，它是该算法所求解问题规模n的函数。
算法的时间复杂度和空间复杂度合称算法复杂度。
第二章 线性表
************************************************************************
线性表是由n≥0个数据元素组成的有限序列。n=0是空表；非空表，只能有一个开始结点，有且只能有一个终端结
点。
************************************************************************
线性表上定义的基本运算：·构造空表：Initlist(L)
*************************************************
顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和
逻辑结构中各结点相邻关
系是一致的。地址计算：LOCa(i)=LOCa(1)+(i-1)*d；（首地址为1）
在顺序表中实现的基本运算： ·插入：平均移动结点次数为n/2；平均时间复杂度均为O(n)。
·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O(n)。
************************************************************************
Created by cherish58，20110线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同，为了能正确表示结点间的逻辑关系，在存储每个
结点值的同时，还存储
了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。 一个单链表由头指针的名字来命
名。
************************************************************************
单链表运算：·建立单链表·头插法：s->next=head；head=s；生成的顺序与输入顺序相反。平均时间复杂度均为
O(n)。
·尾插法：head=rear=null；if(head=null) head=s;else r->next=s;r=s; 平均时间复杂度均为O(n)
·加头结点的算法：对开始结点的操作无需特殊处理，统一了空表和非空表。
·查找·按序号：与查找位置有关，平均时间复杂度均为O(n)。
·按值：与输入实例有关，平均时间复杂度均为O(n)。
·插入运算：p=GetNode(L,i-1)；s->next=p->next；p->next=s；平均时间复杂度均为O(n)
·删除运算：p=GetNode(L,i-1)；r=p->next；p->next=r->next；free(r)；平均时间复杂度均为O(n)
************************************************************************
单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指
针或尾指针。
采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(1)，不用遍历
整个链表。
************************************************************************
双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向
的链。由头指针head惟一
确定。
双链表也可以头尾相链接构成双(向)循环链表。
双链表上的插入和删除时间复杂度均为O (1)。
************************************************************************
顺序表和链表的比较：·基于空间： ·顺序表的存储空间是静态分配，存储密度为1；适于线性表事先确定其大小
时采用。
·链表的存储空间是动态分配，存储密度＜1；适于线性表长度变化大时采用。
·基于时间： ·顺序表是随机存储结构，当线性表的操作主要是查找时，宜采用。
·以插入和删除操作为主的线性表宜采用链表做存储结构。
·若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。
第三章 栈和队列
************************************************************************
栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中
无元素时为空栈。栈
的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out)。通常栈有顺序栈和链栈两种存储
结构。
************************************************************************
栈的基本运算有六种： ·构造空栈：InitStack(S)
·判栈空: StackEmpty(S)
·判栈满： StackFull(S)
·进栈： Push(S,x)
·退栈： Pop(S)
·取栈顶元素：StackTop(S)
Created by cherish58，20120************************************************************************
队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头
(front)，允许插入的
一端称为队尾(rear) ,队列的操作原则是先进先出的，又称作FIFO表(First In First Out) 。队列也有顺序存储
和链式存储两种存储结
构。
************************************************************************
队列的基本运算有六种： ·置空队：InitQueue(Q)·判队空：QueueEmpty(Q)·判队满：QueueFull(Q)· 入队：
EnQueue(Q,x)·出队：DeQueue(Q)·取队头元素：QueueFront(Q)
************************************************************************
顺序队列的"假上溢"现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上
溢"现象。
为了克服"假上溢"现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种： ·一种是另设一个布尔变量来判断；
·第二种是少用一个元素空间，入队时先测试（(rear+1)%m = front）? 满：空；
· 第三种就是用一个计数器记录队列中的元素的总数。
************************************************************************
队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，
在表尾增加一个尾指
针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法
中，要注意当原队中只
有一个结点时，出队后要同进修改头尾指针并使队列变空。
第四章串
************************************************************************
串的基本运算有： · 求串长strlen(char*s)
·串复制strcpy(char*to,char*from)
·串联接strcat(char*to,char*from)
·串比较charcmp(char*s1,char*s2)
·字符定位strchr(char*s,charc)
************************************************************************
.串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。
顺序串又可按存储分配的不同分为： ·静态存储分配：直接用定长的字符数组来定义。优点是涉及串长的操作速度
快，但不适合插入、
链接操作。
·动态存储分配：是在定义串时不分配存储空间，需要使用时按所需串的长度分配存储单元。
************************************************************************
串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结
点数据域为单个字符。
为了解决"存储密度" 低的状况，可以让一个结点存储多个字符，即结点的大小。
************************************************************************
第五章多维数组和广义表
数组一般用顺序存储的方式表示。存储的方式有： · 行优先顺序，也就是把数组逐行依次排列。PASCAL、C
·列优先顺序，就是把数组逐列依次排列。FORTRAN
************************************************************************
Created by cherish58，20130地址的计算方法： ·按行优先顺序排列的数组：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d。
·按列优先顺序排列的数组：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d。
************************************************************************
矩阵的压缩存储：为多个相同的非零元素分配一个存储空间；对零元素不分配空间。
特殊矩阵的概念：所谓特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。
稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。
************************************************************************
稀疏矩阵的压缩存储方式用三元组表把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点
组成的一个线性表来表示
。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置，即带行表的
三元组表。
************************************************************************
广义表是n(n≥0) 个元素的有限序列，其中的元素是原子或者是一个广义表。
第六章树
************************************************************************
树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子
树。
根是开始结点；结点的子树数称度；度为0的结点称叶子(终端结点)；度不为0的结点称分支结点(非终端结点)；除
根外的分支结点称内部
结点；
有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m 个互不相交的树的集合；
树的四种不同表示方法：· 树形表示法；· 嵌套集合表示法；·凹入表示法· 广义表表示法。
************************************************************************
二叉树的定义：是n≥0个结点的有限集，它是空集(n=0)或由一个根结点及两棵互不相交的分别称作这个根的左子
树和右子树的二叉树组
成。
二叉树不是树的特殊情形，与度数为2 的有序树不同。
二叉树的4 个重要性质： ·. 二叉树上第i层上的结点数目最多为2^(i-1)(i≥1).；
·深度为k的二叉树至多有(2^k)-1个结点(k≥1) ；
·.在任意一棵二叉树中，若终端结点的个数为n0, 度为2的结点数为n2 ，则n0=n2+1；
·.具有n个结点的完全二叉树的深度为int(log2n)+1 。
满二叉树是一棵深度为k ，结点数为(2^k)-1 的二叉树；完全二叉树是满二叉树在最下层自右向左去处部分结点；
************************************************************************
二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全
二叉树）
树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode 类型的结点，加上一
个指向根结点的BinTree
型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。共有2n个指针域，
n+1个空指针。
************************************************************************
根据访问结点的次序不同可得三种遍历：先序遍历(前序遍历或先根遍历)，中序遍历(或中根遍历)、后序遍历(或后
根遍历)。时间复杂度
为O(n).
************************************************************************
Created by cherish58，20140利用二叉链表中的 n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就
称为 "线索"，加上线索的
二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后
序后继并没有什么作用
。
************************************************************************
树和森林及二叉树的转换是唯一对应的。
转换方法： · 树变二叉树：兄弟相连，保留长子的连线。
·二叉树变树：结点的右孩子与其双亲连。
·森林变二叉树：树变二叉树，各个树的根相连。
************************************************************************
树的存储结构：·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指
定结点的孩子及后代
。
·孩子链表表示法：为树中每个结点data | next 设置一个孩子链表firstchild，并将data | firstchild存
放在一个向量中。
· 双亲孩子链表表示法：将双亲链表和孩子链表结合。
·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和
右邻兄弟的指针域。
************************************************************************
树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。
************************************************************************
树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为最优二叉树（即
哈夫曼树）。
在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。
哈夫曼树有 n个叶结点，共有2n-1 个结点，没有度为1的结点，这类树又称为严格二叉树。
************************************************************************
变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、
01、0001 这三个码无法
在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码
（其实是非前缀码）。
哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码
的构造很容易，只要画
好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的
序列就是该结点的最优
前缀码。
第七章图
************************************************************************
图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。
图 GraphG=(V,E)，V 是顶点的有穷非空集合，E是顶点偶对的有穷集。
有向图 Digraph：每条边有方向；无向图Undigraph ：每条边没有方向。
有向完全图：具有 n*(n-1) 条边的有向图；无向完全图：具有n*(n-1)/2 条边的无向图；
有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重
合的简单路径；
Created by cherish58，20150网络：是带权的图。
************************************************************************
图的存储结构：·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。 ·无向图：邻接矩阵
是对称的。
· 有向图：行是出度，列是入度。
建立邻接矩阵算法的时间是O(n+n^2+e),其时间复杂度为O(n^2)
·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存
放邻接表头指针。
·邻接表：用头指针确定。 ·无向图称边表；
· 有向图又分出边表和逆邻接表；
·邻接表结点结构为 adjvex | next，
时间复杂度为 O(n+e). ，空间复杂度为O(n+e).。
图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。
·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。
************************************************************************
生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构
成的子图称作该图的生
成树。
最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树
(MST)。
构造最小生成树的算法： ·Prim算法的时间复杂度为 O(n^2) 与边数无关适于稠密图。
·Kruskal 算法的时间复杂度为O(lge),主要取决于边数，较适合于稀疏图。
************************************************************************
最短路径的算法：·Dijkstra算法，时间复杂度为O(n^2).· 类似于prim算法。
************************************************************************
拓扑排序：是将有向无环图G 中所有顶点排成一个线性序列，若∈E(G)，则在线性序列u在v之前，这种线性
序列称为拓扑序列。
拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序
列即拓扑序列。
· 无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。
第八章排序
************************************************************************
记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。
排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作：比较关键字大小；改变指向记录的指针
或移动记录。
· 存储结构：顺序结构、链表结构、索引结构。
经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不
稳定的。
排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序)，反之，若存在数据的内外存交换，则称之为
外排序。
内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。
************************************************************************
Created by cherish58，20160插入排序：·直接插入排序： ·逐个向前插入到合适位置。
·哨兵(监视哨) 有两个作用： ·作为临变量存放R[i]
·是在查找循环中用来监视下标变量j 是否越界。
·直接插入排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为(n+2)(n-1)/2；移动次数为(n+4)(n-1)/2；
·希尔排序： · 等间隔的数据比较并按要求顺序排列，最后间隔为1。
· 希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25)，比较次数为(n^1.25) ；移动次数为(1.6n^1.25)；
交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后
自上向下确定最重的
一个。
· 冒泡排序是就地的稳定排序。时间复杂度为O(n^2) ，比较次数为n(n-1)/2 ；移动次数为3n(n-1)/2；
·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直
到排序完成。
· 快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n) ，比较次数为n(n-1)/2；
选择排序：·直接选择排序： · 选择最小的放在比较区前。
·直接选择排序就地的不稳定排序。时间复杂度为O(n^2) 。比较次数为n(n-1)/2；
·堆排序 ·建堆：按层次将数据填入完全二叉树，从int(n/2)处向前逐个调整位置。
·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。
·堆排序是就地不稳定的排序，时间复杂度为O(nlog2n) ，不适宜于记录数较少的文件。。
归并排序： ·先两个一组排序，形成(n+1)/2 组，再将两组并一组，直到剩下一组为止。
·归并排序是非就地稳定排序，时间复杂度是O(nlog2n),
分配排序：· 箱排序： · 按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。
·箱排序的平均时间复杂度是线性的O(n).
·基数排序：·从低位到高位依次对关键字进行箱排序。
· 基数排序是非就稳定的排序，时间复杂度是O(d*n+d*rd)。
各种排序方法的比较和选择： ·.待排序的记录数目 n；n较大的要用时间复杂度为O(nlog2n) 的第九章查找
************************************************************************
查找的同时对表做修改操作 (如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。
衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL).
************************************************************************
线性表查找的方法： ·顺序查找：逐个查找，ASL=(n+1)/2;
·二分查找：取中点int(n/2)比较,若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层
数））/N。
·分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的最大关键字及其位置建立有序
索引表。
************************************************************************
二叉排序树(BST)定义是：二叉排序树是空树或者满足如下性质的二叉树： ·若它的左子树非空，则左子树上所有
结点的值均小于根结点
的值；
· 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
·左、右子树本身又是一棵二叉排序树。
二叉排序树的插入、建立、删除的算法平均时间性能是O(nlog2n) 。
二叉排序树的删除操作可分三种情况进行处理： ·*P是叶子，则直接删除*P，即将*P 的双亲*parent 中指向*P 的
指针域置空即可。
·*P只有一个孩子*child,此时只需将*child和*p的双亲直接连接就可删去*p.
Created by cherish58，20170·*p 有两个孩子,则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。
************************************************************************
关于B-树(多路平衡查找树)。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式
是从下向上拱起。
************************************************************************
散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。
常见的散列函数构的造方法： ·.平方取中法：hash=int((x^2)%100)
·. 除余法：表长为m，hash=x%m
·. 相乘取整法：hash=int(m*(x*A-int(x*A))；A=0.618
·. 随机数法：hash=random(x)。
************************************************************************
处理冲突的方法：·开放定址法： ·一般形式为hi=(h(key)+di)%m1≤i≤m-1，开放定址法要求散列表的装填因子
α ≤1。
· 开放定址法类型： ·线性探查法：address=(hash(x)+i)%m ；
·二次探查法：address=(hash(x)+i^2)%m；
· 双重散列法：address=(hash(x)+i*hash(y))%m ；
· 拉链法： · 是将所有关键字为同义词的结点链接在同一个单链表中。
· 拉链法的优点： ·拉链法处理冲突简单，且无堆积现象；
· 链表上的结点空间是动态申请的适于无法确定表长的情况；
·拉链法中α可以大于 1，结点较大时其指针域可忽略，因此节省空间；
· 拉链法构造的散列表删除结点易实现。
· 拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。
第十章文件
************************************************************************
文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字
段或者属性。
文件 ·逻辑结构是一种线性结构。
· 操作有：检索和维护。并有实时和批量处理两种处理方式。
文件 · 存储结构是指文件在外存上的组织方式。
· 基本的组织方式有：顺序组织、索引组织、散列组织和链组织。
·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。
评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。
检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。
************************************************************************
顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件
否则称顺序无序文件。
一切存储在顺序存储器(如磁带)上的文件都只能顺序文件，只能按顺序查找法存取。
顺序文件的插入、删除和修改只能通过复制整个文件实现。
************************************************************************
索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主
文件一起构成索引文件。
索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。
若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。
Created by cherish58，20180索引顺序文件常用的有两种： ·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。
·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据
集组成。
************************************************************************
散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。
散列文件 ·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。
·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。
************************************************************************
多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、
次关键字作为索引表的索引项。
倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。
计算机组成原理
第1章 概论
一、名词解释：
历年真题：
名词解释题：
（2002年）1．主机：由CPU、存储器与I/O接口合在一起构成的处理系统称为主机。
（2003年）16．主机：由CPU、存储器与I/O接口合在一起构成的处理系统称为主机。
（2004年）18．ALU算术逻辑运算单元，负责执行各种算术运算和逻辑运算。
（2005年）21．应用软件：完成应用功能的软件，专门为解决某个应用领域中的具体任务而编写 。
近4年都考了名称解释，所以第一章的名称解释是考试的重点，这里给大家列出了名词解释大家要熟悉一下，
这都是本章的基本概念，也有利于做选择题及填空题。
1．主机：由CPU、存储器与I/O接口合在一起构成的处理系统称为主机。
2．CPU：中央处理器，是计算机的核心部件，由运算器和控制器构成。
3．运算器：计算机中完成运算功能的部件，由ALU和寄存器构成。
4．ALU：算术逻辑运算单元，负责执行各种算术运算和逻辑运算。
5．外围设备：计算机的输入输出设备，包括输入设备，输出设备和外存储设备。
6．数据：编码形式的各种信息，在计算机中作为程序的操作对象。
7．指令：是一种经过编码的操作命令，它指定需要进行的操作，支配计算机中的信息传递以及主机与输入输出
设备之间的信息传递，是构成计算机软件的基本元素。
8．透明：在计算机中，从某个角度看不到的特性称该特性是透明的。
9．位：计算机中的一个二进制数据代码，计算机中数据的最小表示单位。
10．字：数据运算和存储的单位，其位数取决于具体的计算机。
11．字节：衡量数据量以及存储容量的基本单位。1字节等于8位二进制信息。
12．字长：一个数据字中包含的位数，反应了计算机并行计算的能力。一般为8位、16位、32位或64位。
13．地址：给主存器中不同的存储位置指定的一个二进制编号。
14．存储器：计算机中存储程序和数据的部件，分为内存和外存。
15．总线：计算机中连接功能单元的公共线路，是一束信号线的集合，包括数据总线．地址总线和控制总线。
16．硬件：由物理元器件构成的系统，计算机硬件是一个能够执行指令的设备。
17．软件：由程序构成的系统，分为系统软件和应用软件。
18．兼容：计算机部件的通用性。
19．软件兼容：一个计算机系统上的软件能在另一个计算机系统上运行，并得到相同的结果，则称这两个计算
机系统是软件兼容的。
Created by cherish58，2019020．程序：完成某种功能的指令序列。
21．寄存器：是运算器中若干个临时存放数据的部件，由触发器构成，用于存储最频繁使用的数据。
22．容量：是衡量容纳信息能力的指标。
23．主存：一般采用半导体存储器件实现，速度较高．成本高且当电源断开时存储器的内容会丢失。
24．辅存：一般通过输入输出部件连接到主存储器的外围设备，成本低，存储时间长。
25．操作系统：主要的系统软件，控制其它程序的运行，管理系统资源并且为用户提供操作界面。
26．汇编程序：将汇编语言程序翻译成机器语言程序的计算机软件。
27．汇编语言：采用文字方式（助记符）表示的程序设计语言，其中大部分指令和机器语言中的指令一一对应，
但不能被计算机的硬件直接识别。
28．编译程序：将高级语言程序转换成机器语言程序的计算机软件。
29．解释程序：解释执行高级语言程序的计算机软件，解释并立即执行源程序的语句。
30．系统软件：计算机系统的一部分，进行命令解释、操作管理、系统维护、网络通信、软件开发和输入输出管理
的软件，与具体的应用领域无关。
31．应用软件：完成应用功能的软件，专门为解决某个应用领域中的具体任务而编写。
32．指令流：在计算机的存储器与CPU之间形成的不断传递的指令序列。从存储器流向控制器。
33．数据流：在计算机的存储器与CPU之间形成的不断传递的数据序列。存在于运算器与存储器以及输入输出
设备之间。
34．接口：计算机主机与外围设备之间传递数据与控制信息的电路。计算机可以与多种不同的外围设备连接，
因而需要有多种不同的输入输出接口。
选择题没有考过
二、填空题：
（2000年）系统软件主要包括：＿＿＿和＿＿＿及诊断程序等。
操作系统 语言处理程序
（2005年）18．构成中央处理器的两大部件是＿＿＿和＿＿＿。
运算器 控制器
三、改错题：
（2000年）1．运算器的功能就是执行加、减、乘、除四则运算。
运算器的功能就是算术运算和逻辑运算
（2005年）18．构成中央处理器的两大部件是＿＿＿和＿＿＿。
硬盘的存储容量常用 GB 表示，1GB=1024MB
三、数据编码：
定点数编码：
（2000年）2．如果X为负数，由[X]补求[-X]补是将（ ）。
A．[X]补各值保持不变
B．[X]补符号位变反，其它各位不变
C．[X]补除符号位外，各位变反，未位加1
D．[X]补连同符号位一起各位变反，未位加1
【分析】：不论X是正数还是负数，由[X]补求[-X]补的方法是对[X]补求补，即连同符号位一起按位取反，末位
加1。
【答案】：D
（2001年）2．若x补 =0.1101010 ，则 x 原=（ ） 。
A．1.0010101 B．1.0010110 C．0.0010110 D．0.1101010
【分析】：正数的补码与原码相同，负数的补码是用正数的补码按位取反，末位加1求得。此题中X补为正数，则
Created by cherish58，201100X原与X补相同。
【答案】：D
（2002年）2．若x=1011,则[x]补=( )。
A．01011 B．1011 C．0101 D．10101
【分析】：x为正数，符号位为0,数值位与原码相同，结果为01011。
【答案】：A
（2003年）8．若［X］补=1.1011 ，则真值 X 是（ ）。
A．-0.1011 B．-0.0101 C．0.1011 D．0.0101
【分析】：[X] 补=1.1011，其符号位为 1，真值为负；真值绝对值可由其补码经求补运算得到，即按位取后得
0.0100再末位加1 得0.0101，故其真值为-0.0101。
【答案】：B
（2004 年）13．设有二进制数 x=－1101110，若采用 8 位二进制数表示，则［X ］补（ ） 。
A．11101101 B．10010011 C．00010011 D．10010010
【分析】：x=－1101110为负数，负数的补码是将二进制位按位取反后在最低位上加1，故[x] 补 =10010010。
【答案】：D
（2005年）1 ．若[X]补 =0.1011，则真值X=（ ）。
A．0.1011 B ．0.0101 C．1.1011 D．1.0101
【分析】：[X]补 =0.1011 ，其符号位为 0 ，真值为正；真值就是0.1011。
【答案】：A
由上可见，有关补码每年都考。同学也要注意一下移码。
（2001）3 ．若定点整数 64 位，含 1 位符号位，补码表示，则所能表示的绝对值最大负数为（ ）。
A．-264 B ．-（264-1 ） C．-263 D．-（263-1）
【分析】：字长为64 位，符号位为1位，则数值位为 63 位。当表示负数时，数值位全0 为负绝对值最大，为-263。
【答案】：C
（2002年） 3 ．某机字长8 位，含一位数符，采用原码表示，则定点小数所能表示的非零最小正数为（ ）
A ．2-9 B．2-8 C．1- D．2-7
【分析】：求最小的非零正数，符号位为0,数值位取非0中的原码最小值，此8位数据编码为：00000001，表示的值是：
2-7 。
【答案】：D
第3章 存储系统
一、名词解释：
历年真题：
（2001年）2 ．DRAM ：动态随机访问存储器，利用电容电荷存储信息。
（2001 年）6．逻辑地址：程序员编程所用的地址以及CPU通过指令访问主存时所产生的地址。
（ 2001年）10．随机存取方式：可按地址访问存储器任一编址单元，其访问时间相同且与地址无关。
六年以来就考了这3 个名称解释，而且近4年都没有考，所以第三章的名称解释不是考试的重点，这里给大家
列出了名词解释大家要熟悉一下，这都是本章的基本概念，有利于做选择题及填空题。
1．RAM：随机访问存储器，能够快速方便的访问地址中的内容，访问的速度与存储位置无关。
2 ．ROM ：只读存储器，一种只能读取数据不能写入数据的存储器。
3 ． SRAM ：静态随机访问存储器，采用双稳态电路存储信息。
4．DRAM ：动态随机访问存储器，利用电容电荷存储信息。
5．EDO DRAM：增强数据输出动态随机访问存储，采用快速页面访问模式并增加了一个数据锁存器以提高数据传
输速率。
6 ．PROM：可编程的 ROM，可以被用户编程一次。
Created by cherish58，2011107．EPROM：可擦写可编程的ROM，可以被用户编程多次。靠紫外线激发浮置栅上的电荷以达到擦除的目的。
8．EEPROM：电可擦写可编程的ROM，能够用电子的方法擦除其中的内容。
9．SDRAM：同步型动态随机访问存储器，在系统时钟控制下进行数据的读写。
10．快闪存储器：一种非挥发性存储器，与EEPROM类似，能够用电子的方法擦除其中的内容。
11．相联存储器：一种按内容访问的存储器，每个存储单元有匹配电路，可用于是cache中查找数据。
12．多体交叉存储器：由多个相互独立、容量相同的存储体构成的存储器，每个存储体独立工作，读写操作重叠
进行。
13．访存局部性：CPU的一种存取特性，对存储空间的90%的访问局限于存储空间的10%的区域中，而另外10%的
访问则分布在90%的区域中。
14．直接映象：cache的一种地址映象方式，一个主存块只能映象到cache中的唯一一个指定块。
15．全相联映象：cache的一种地址映象方式，一个主存块可映象到任何cache块。
16．组相联映象：cache的一种地址映象方式，将存储空间分成若干组，各组之间用直接映象，组内各块之间用
全相联映象。
17．全写法（写直达法）：cache命中时的一种更新策略，写操作时将数据既写入cache又写入主存，但块变更时
不需要将调出的块写回主存。
18．写回法：cache命中时的一种更新策略，写cache时不写主存，而当cache数据被替换出去时才写回主存。
19 ．按写分配：cache 不命中时的一种更新策略，写操作时把对应的数据块从主存调入cache。
20．不按写分配：cache 不命中时的一种更新策略，写操作时该地址的数据块不从主存调入cache 。
一般写回法采用按写分配法，写直达法则采用不按写分配法。
21．虚拟存储器：为了扩大容量，把辅存当作主存使用，所需要的程序和数据由辅助的软件和硬件自动地调入
主存，对用户来说，好像机器有一个容量很大的内存，这个扩大了的存储空间称为虚拟存储器
22．层次化存储体系：把各种不同存储容量、不同访问速度、不同成本的存储器件按层次构成多层的存储器，并
通过软硬件的管理将其组成统一的整体，使所存储的程序和数据按层次分布在各种存储器件中。
23．访问时间：从启动访问存储器操作到操作完成的时间。
24 ．访问周期时间：从一次访问存储的操作到操作完成后可启动下一次操作的时间。
25．带宽：存储器在连续访问时的数据吞吐率。
26．段式管理：一种虚拟存储器的管理方式，把虚拟存储空间分成段，段的长度可以任意设定，并可以放大或缩
小。
27．页式管理：一种虚拟存储器的管理方式，把虚拟存储空间和实际存储空间等分成固定容量的页，需要时装
入内存，各页可装入主存中不同的实际页面位置。
28 ．段页式管理：一种虚拟存储器的管理方式，将存储空间逻辑模块分成段，每段又分成若干页。
29．固件：固化在硬件中的固定不变的常用软件。
30．逻辑地址：程序员编程所用的地址以及CPU 通过指令访问主存时所产生的地址。
31．物理地址：实际的主存储器的地址称为“真实地址” 。
二、选择填空题：
历年真题评析：
2000 年：
5．动态半导体存储器的特点是（ ）。
A．在工作中存储器内容会产生变化
B．每次读出后，需要根据原存内容重新写入一遍
C．每隔一定时间，需要根据原存内容重新写入一遍
D．在工作中需要动态地改变访存地址
【分析】：动态半导体存储器是利用电容存储电荷的特性记录信息，由于电容会放电，必须在电荷流失前对电容
充电，即刷新。方法是每隔一定时间，根据原存内容重新写入一遍。
Created by cherish58，201120【答案】：C
8．地址线A15～A0（低），若选取用16K×1存储芯片构成64KB存储器则应由地址码 译码产生片选信号。
【分析】：用16K×1芯片构成64KB的存储器，需要的芯片数量为：(64K×8)/(16K×1)=32，每8片一组分成4组，每
组按位扩展方式组成一个16K×8位的模块，4个模块按字扩展方式构成64KB的存储器。存储器的容量为64K=216，
需要16位地址，选用A15-A0为地址线；每个模块的容量为16K=214需要14位地址，选用A13-A0为每个模块提供地
址；A15、A14通过2-4译码器对4个模块进行片选。
【答案】：Al5，A14
9．有静态RAM与动态RAM可供选择，在构成大容量主存时，一般就选择（ ）。
【分析】：静态RAM特点是存取速度快，单位价格（每字节存储空间的价格）较高；动态RAM则是存取速度稍慢，
单位价格较低。所以考虑价格因素，在构成大容量的存储器时一般选择动态存储器。
【答案】：动态RAM
2001年：
11．高速缓冲存储器 Cache 一般采取（ ）。
A．随机存取方式
B．顺序存取方式
C．半顺序存取方式
D．只读不写方式
【分析】：Cache是为提高存储器带宽而在主存储器和CPU之间增加的存储器，目的是用来存储使用频繁的数据
和指令，存取方式应与主存储器相同，均为随机存取方式。
【答案】：A
12．若存储周期 250ns ，每次读出 16 位，则该存储器的数据传送率为（ ）。
A．4 × 10 6 字节 / 秒 B．4M 字节 / 秒
C．8 × 10 6 字节 / 秒 D．8M 字节 / 秒
【分析】：存储周期250ns，换算为250×10-9秒；每个存储周期可读出16位，为两个字节，则数据传送率为：2字节
／（250×10-9）秒，即8×106字节／秒。
【答案】：C
13．半导体静态存储器 SRAM 的存储原理是（ ）。
A．依靠双稳态电路 B．依靠定时刷新
C．依靠读后再生 D．信息不再变化
【分析】：半导体静态存储器SRAM是由双稳态电路构成，并依靠其稳态特性来保存信息；动态存储器DRAM是利
用电容器存储电荷的特性存储数据，依靠定时刷新和读后再生对信息进行保存，而ROM中的信息一经写入就不再变
化。
【答案】：A
2002年：
6．一般来讲，直接映象常用在（ ）。
A．小容量高速Cache B．大容量高速Cache
C．小容量低速Cache D．大容量低速Cache
【分析】：直接映象的地址转换速度快，但块的冲突概率较高。在大容量高速Cache系统中使用直接映象方式，
即可以发挥Cache的高速度，又可以减少块的冲突概率。
【答案】：B
7．下列存储器中，（ ）速度最快。
A．硬盘 B．光盘 C．磁带 D．半导体存储器
【分析】：由于存储器原理和结构的不同，各种存储器的访问速度各不相同。以上存储器中访问速度由快到慢的
顺序为：半导体存储器、硬盘、光盘、磁带。
Created by cherish58，201130【答案】：D
2003年：
15．在下列 Cache 替换算法中，一般说来哪一种比较好（ ）。
A．随机法 B．先进先出法
C．后进先出法 D．近期最少使用法
【分析】：在Cache替换算法中，随机法是随机地确定替换的存储单元，先进先出法是替换最早调入的存储单元，
它们都没有根据程序访存局部性原理，命中率较低；近期最少使用法比较正确地利用了程序访存局部性原理，替换
出近期用得最少的存储块，命中率较高，是一种比较好的替换算法。而后进先出法不是Cache所使用的替换算法，此
法在堆栈存储结构中使用。
【答案】：D
2004年：
8． 表示主存容量的常用单位为（ ）。
A．数据块数 B．字节数 C．扇区数 D．记录项数
【分析】：表示主存容量的常用单位字节B，是基本单位。此外还有KB、MB、GB、TB。
【答案】：B
11． 存储器的随机访问方式是指（ ） 。
A．可随意访问存储器
B．按随机文件访问存储器
C．可对存储器进行读出与写入
D．可按地址访问存储器任一编址单元，其访问时间相同且与地址无关
【分析】：存储器的随机访问方式是指可按地址访问存储器任一编址单元，其访问时间相同且与地址无关。
【答案】：D
2005年：
6．动态存储器的特点是（ ）。
A．工作中存储内容会产生变化
B．工作中需要动态改变访存地址
C．工作中需要动态地改变供电电压
D．需要定期刷新每个存储单元中存储的信息
【分析】：此题与2000年考题基本相同。动态半导体存储器是利用电容存储电荷的特性记录信息，由于电容会
放电，必须在电荷流失前对电容充电，即刷新。方法是每隔一定时间，根据原存内容重新写入一遍。
【答案】：D
7．组相联映象和全相联映象通常适合于（ ）。
A．小容量Cache B．大容量Cache
C．小容量ROM D．大容量ROM
【分析】：直接映象的地址转换速度快，但块的冲突概率较高。在大容量高速Cache系统中使用直接映象方式，
即可以发挥Cache的高速度，又可以减少块的冲突概率。组相联映象和全相联映象速度较低，通常适合于小容量
Cache。
【答案】：A
第4章 指令系统
一、名词解释：
历年真题：
2001年
3．堆栈：数据的写入写出不需要地址，按先进后出的顺序读取数据的存储区。
4．立即寻址方式：操作数直接在指令中给出。
Created by cherish58，201140六年以来就考了这2个名称解释，而且近4年都没有考，所以第四章的名称解释不是考试的重点，这里给大家
列出了名词解释大家要熟悉一下，这都是本章的基本概念，有利于做选择题、改错题和填空题。
1．指令系统：计算机中各种指令的集合，它反映了计算机硬件具备的基本功能。
2．计算机指令：计算机硬件能识别并能直接执行操作的命令，描述一个基本操作。
3．指令编码：将指令分成操作码和操作数地址码的几个字段来编码。
4．指令格式：指定指令字段的个数，字段编码的位数和编码的方式。
5．立即数：在指令中直接给出的操作数。
6．指令字长度：一个指令字所占有的位数。
7．助记符：用容易记忆的符号来表示指令中的操作码和操作数。
8．汇编语言：采用文字方式（助记符）表示的程序设计语言，其中大部分指令和机器语言中的指令一一对应，但
是不能被计算机的硬件直接识别。
9．伪指令：汇编语言程序所提供的装入内存中的位置信息，表示程序段和数据段开始信息及结束信息等。且不
转换成2进制机器指令。
10．大数端：当一个数据元素的位数超过一个字节或者一个字的宽度，需存储在相邻的多个字节的存储位置时，
将数据的最低字节存储在最大地址位置的存储方式。
11．小数端：当一个数据元素的位数超过一个字节或者一个字的宽度，需存储在相邻的多个字节的存储位置时，
将数据的最低字节存储在最小地址位置的存储方式。
12．操作数寻址方式：指令中地址码的内容及编码方式。
13．系统指令：改变计算机系统的工作状态的指令。
14．特权指令：改变执行特权的指令，用于操作系统对系统资源的控制。
15．自陷指令：特殊的处理程序，又叫中断指令。
16．寻址方式：对指令的地址码进行编码，以得到操作数在存储器中的地址的方式。
17．相对转移：转移到的目标指令的地址与当前指令的地址有关，是用当前指令的PC与一个偏移量相加，和为
目标指令的PC。
18．绝对转移：转移到的目标指令的地址与当前指令的地址无关，指令中给定的目标地址即为目标指令的PC。
19．无条件转移：一种转移指令类型，不管状态如何，一律进行转移操作。
20．条件转移：一种转移指令类型，根据计算机中的状态决定是否转移。
21．RISC：精简指令系统计算机，即指令系统中的指令数量少，且指令功能相对简单。
22．CISC：复杂指令系统计算机，即指令系统中的指令数量多，且指令功能相对较强。
23．堆栈：数据的写入写出不需要地址，按先进后出的顺序读取数据的存储区 。
二、选择填空题：
历年真题
2000年：
3．在堆栈寻址中，设 A为累加器，SP为堆栈指示器，Msp为SP指示的栈顶单元。如果进栈操作顺序是：
（SP）-1→SP，（A）→Msp；那么出栈操作的顺序应是（ ）。
A．（Msp）→A，（SP）+1→SP
B．（SP）+1→SP，（Msp）→A
C．（SP）-1→SP，（Msp）→A
D．（Msp）→A，（SP）-1→SP
【分析】：堆栈是按特定顺序进行访问的存储区，其访问方式是后进先出，即先存入的数据后读出。对堆栈的操
作有入栈和出栈两种，两者的操作完全相反，包括功能和顺序均相反。
【答案】：A
6．在按字节编址的存储器中，每个编址单元中存放（ ）。
A．1位 B．8位 C．16位 D．32位
Created by cherish58，201150【分析】：在按字节编址在存储器中，每个编址单元的容量为一个字节，一个字节由8位二进制数组成，一个字
节存储单元可以存放8位二进制位。
【答案】：B
4．在CPU的状态寄存器中，常设置以下状态位：零标志位（Z），负标志位（N），（ ）和（ ）。
【分析】：在CPU中专门设置有一个存储计算机状态的寄存器，称为状态寄存器SR,其中通常包括如下标志位：
零标志位（Z）、负标志位（N）、溢出标志位（V）、进位或借位标志位（C）等。
【答案】：溢出标志位（V）、进位或借位标志位（C）
5．如指令中给出形式地址为D，则间接寻址方式获得操作数的有效地址为 。
【分析】：在存储器间接寻址方式中，操作数的地址在主存储器中，其存储器地址在指令中给出。也就是说在指
令中给出的既不是操作数，也不是操作数的地址，而是操作数地址的地址，则有效地址为以形式地址D为地址的存
储单元的内容。
【答案】：以D为地址的存储单元的内容
13．如果说变址寻址方式主要是面向用户的，那么基址寻址一般是面向（ ）的。
【分析】：变址寻址方式是面向用户的，常用于访问字符串、向量数据结构和循环程序设计；而基址寻址方式是
面向系统的，对由逻辑地址空间到物理地址空间的变换提供支持，用以解决程序在存储器中再定位和扩大寻址空间
等问题。
【答案】：系 统
2001年：
9．为了缩短指令中某个地址段的位数，有效的方法是采取（ ）。
A．立即寻址 B．变址寻址
C．间接寻址 D．寄存器寻址
【分析】：由于计算机中寄存器的数量一般很少，采用寄存器寻址时可用少量的代码来指定寄存器，这样可以减
少对应地址段的代码位数，也可减少整个指令的代码长度。
【答案】：D
10．堆栈指针 SP 的内容是（ ）。 A．栈顶单元内容 B．栈顶单元地址 C．栈底单元内容 D．栈底单元地址
【分析】：堆栈是按特定顺序进行访问的存储区，其访问方式是后进先出，即先存入的数据后读出。对堆栈的访
问由堆栈指针寄存器SP控制，其内容为堆栈中栈项单元的地址，即入栈时数据保存在SP指向的单元，出栈时将SP
指向单元的内容取出。
【答案】：B
2002年：
8．采用直接寻址方式，则操作数在（ ）中。
A．主存 B．寄存器 C．直接存取存储器 D．光盘
【分析】：直接寻址方式是指在指令中直接给出操作数在存储器中的地址，操作数在主存储器中，指令中的地址
直接作为有效地址，对存储器进行访问即可取得操作数。
【答案】：A
9．零地址指令的操作数一般隐含在（ ）中。
A．磁盘 B．磁带 C．寄存器 D．光盘
【分析】：零地址指令只有操作码，没有操作数。这种指令有两种情况：一是无需操作数，另一种是操作数为默认
的（隐含的），默认为操作数在寄存器中，指令可直接访问寄存器。
【答案】：C
2003年：
3．假设寄存器 R 中的数值为 200 ，主存地址为 200 和 300 的地址单元中存效的内容分别是 300 和 400 ，则什
么方式下访问到的操作数为 200（ ）。
A．直接寻址 200
Created by cherish58，201160B．寄存器间接寻址（R）
C．存储器间接寻址（200）
D．寄存器寻址 R
【分析】：直接寻址200的操作数为300,寄存器间接寻址(R)的操作数300,存储器间接寻址（200）的操作数为
400，寄存器寻址R的操作数为200。
【答案】：D
5．单地址指令（ ）。
A．只能对单操作数进行加工处理
B．只能对双操作数进行加工处理
C．无处理双操作数的功能
D．既能对单操作数进行加工处理，也能在隐含约定另一操作数（或地址）时，对双操作数进行 运算
【分析】：单地址指令既能对单操作数进行加工处理，也能对双操作数进行运算。当处理双操作数时，一个操作
数在指令中给出，另一个操作数则是隐含约定的，例如堆栈操作指令中的入栈指令PUSH,指令中只给出源操作数，
而目的操作数则由计算机中的堆栈指针（SP）确定，在指令中不需要指定。
【答案】：D
2004年：
14．反映计算机基本功能的是（ ）。
A．操作系统 B．系统软件 C．指令系统 D．数据库系统
【分析】：指令系统：计算机中各种指令的集合，它反映了计算机硬件具备的基本功能。
【答案】：C
2005年：
8．在大多数情况下，一条机器指令中是不直接用二进制代码来指定（ ）。
A．下一条指令的地址
B．操作的类型
C．操作数地址
D．结果存放地址
答案：A
9．在存储器堆栈中，若栈底地址为A，SP指针初值为A-1，当堆栈采用从地址小的位置向地址大的位置生成时，弹出
操作应是（ ）。
A．先从堆栈取出数据，然后SP 指针减1
B．先从堆栈取出数据，然后SP 指针加1
C．SP指针先加1 ，然后从堆栈取出数据
D．SP指针先减1，然后从堆栈取出数据
【分析】：堆栈是按特定顺序进行访问的存储区，其访问方式是后进先出，即先存入的数据后读出。对堆栈的访
问由堆栈指针寄存器SP控制，当堆栈采用从地址小的位置向地址大的位置生成时，入栈操作是SP指针先加1，然后
将数据存入堆栈，从堆栈取出弹出操作是先从堆栈取出数据，然后SP 指针减 1。
【答案】：A
10．转移指令执行结束后，程序计数器 PC 中存放的是（ ）。
A．该转移指令的地址
B．顺序执行的下条指令地址
C．转移的目标地址
D ．任意指令地址
【分析】：转移指令执行过程中，将转移指令所指的子程序的起始地址装入PC，因此转移指令执行结束后，程序
计数器 PC 中存放的是转移的目标地址。
Created by cherish58，201170【答案】：C
三、改错题：
3．在寄存器寻址方式中，指定寄存器中存放的是操作数地址。2（000 ）
【分析】：在寄存器间接寻址方式中，指定寄存器中存放的是操作数地址；而在寄存器寻址方式中，指定寄存器
中存放着操作数。
【答案】：在寄存器寻址方式中，指定寄存器中存放着操作 数。
1．在计算机中，各指令周期的时间长度是相同的。（2002 ）
【分析】：在计算机中，由于指令的种类不同，功能不同，执行每条指令时机器所进行的操作可能就不同，所需要
的时间长短也可能不相同，所以各指令周期的时间长度不一定相同。
【答案】：一般说，由于各指令功能的不同，它们的指令周期有长有短，不一定相 同。
22．转移指令执行结束后，目标地址可放在任意寄存器中。（2004 年）
【分析】：转移指令执行过程中，将转移指令所指的子程序的起始地址装入PC，因此转移指令执行结束后，程序
计数器 PC中存放的是转移的目标地址。
【答案】：转移指令执行结束后，目标地址放在程序计数器PC中。
第5章 控制器
一、名词解释：
历年真题：
（2001年）6．逻辑地址：程序员编程所用的地址以及CPU通过指令访问主存时所产生的地址。 与内存物理地址
无固定对应关系的地址。
（2001年）7．微程序控制器：将执行指令所需要的微命令以代码形式编成微指令序列（微程序），存入一个控制
存储器，需要时从该存储器中读取。按这种方式工作的控制器为微程序控制器。
（2002年）3．控制存储器（CPU内的） ：CPU内用于存放实现指令系统全部指令的微程序的只读存储器称为控制
存储器。
（2004 年）20．垂直型微指令：一种微指令类型，设置微操作码字段，采用微操作码编码法，由微操作码规定微
指令的功能。
（ 2005年）23．微程序控制器：将执行指令所需要的微命令以代码形式编成微指令序列（微程序），存入一个控
制存储器，需要时从该存储器中读取。按这种方式工作的控制器为微程序控制器。
近年以来每年考本章的名词解释，所以第五章的名称解释是考试的重点。这里给大家列出了本章的名词解释，
大家要熟悉一下，这都是本章的基本概念，有利于做名称解释、选择题、改错题和填空题。
1 ．指令周期：从一条指令的启动到下一条指令的启动的间隔时间。
2．机器周期：指令执行中每一步操作所需的时间。
3．指令仿真：通过改变微程序实现不同机器指令系统的方式，使得在一种计算机上可以运行另一种计算机上的
指令代码。
4．指令模拟：在一种计算机上用软件来解释执行另一种计算机的指令。
5．硬连线逻辑：一种控制器逻辑，用一个时序电路产生时间控制信号，采用组合逻辑电路实现各种控制功能。
6 ．微程序：存储在控制存储中的完成指令功能的程序，由微指令组成。
7．微指令：控制器存储的控制代码，分为操作控制部分和顺序控制部分。
8．微操作：在微程序控制器中，执行部件接受微指令后所进行的操作。
9．微地址：微每时令在控制存储器中的存储地址。
10．控制存储器：CPU内用于存放实现指令系统全部指令的微程序的只读存储器称为控制存储器。
11 ．相容性微操作：在同时或同一个CPU周期内可以并行执行的微操作。
12．相斥性微操作：不能在同时或不能在同一个CPU 周期内并行执行的微操作。
二、选择题和填空题：
2000年：
Created by cherish58，2011804．在取指周期中，是按照（ ）的内容访问主存，以读取指令。
A．指令寄存器IR B．程序状态寄存器PS
C．存储器数据寄存器MDR D．程序计数器PC
【分析】：每一条指令的执行都是从取指令开始，需要对主存储器进行访问。程序计数器PC是用来存放将要读
取并执行的指令在主存储器中的地址，对主存储器访问时所需要的地址由程序计数器PC来提供，即需要按程序计
数器PC的内容来访问主存储器。
【答案】：D
7．在微程序控制中，一个节拍中所需要的一组微命令，被编成一条（ 。
【分析】：控制部件通过控制总线向执行部件发出的控制命令称为微命令，它是计算机中最基本的、不可再分的
命令单元。在一个节拍中，一组实现一定功能的微命令的组合构成一条微指令。
【答案】：微指 令
2002年：
10．微程序存放在（ ）。
A．主存中 B．堆栈中 C．只读存储器中 D．磁盘中
【分析】：微程序控制的基本思想是把指令执行所需的所有控制信号存放在存储器中，需要时从这个存储器中
读取。由于每一条微指令执行时所发出的控制信号是事先设计好的，不需要改变，故此存放所有控制信号的存储器
应为只读存储器，并将其集成到CPU内，称其为控制存储器。
【答案】：C
11．在微程序控制方式中，机器指令和微指令的关系是（ ）。
A．每一条机器指令由一条微指令来解释执行
B．每一条机器指令由一段（或一个）微程序来解释执行
C．一段机器指令组成的工作程序可由一条微指令来解释执行
D．一条微指令由若干条机器指令组成
【分析】：在微程序控制方式中，控制部件通过控制总线向执行部件发出的各种控制命令称为微命令，在一个
CPU周期中，一组实现一定功能的微命令的组合构成一条微指令，有序的微指令序列构成一段微程序。微程序的作
用是实现一条对应的机器指令，即每一条机器指令是由一段（或一个）微程序来解释执行的。
【答案】：B
2003年：
7．下列说法中，合理的是（ ）。
A．执行各条指令的机器周期数相同，各机器周期的长度均匀
B．执行各条指令的机器周期数相同，各机器周期的长度可变
C．执行各条指令的机器周期数可变，各机器周期的长度均匀
D．执行各条指令的机器周期数可变，各机器周期的长度可变
【分析】：机器周期是指令执行中每一步操作所需要的时间，一般以CPU中完成一个运算操作所需的时间作为机
器周期的基本时间，其长度是均匀的，而各种指令的功能不同，因而各指令执行时所需的机器周期数是可变的。
【答案】：C
10．微地址是指微指令（ ）。
A．在主存的存储位置 B．在堆栈的存储位置
C．在磁盘的存储位置 D．在控制存储器的存储位置
【分析】：微程序控制的基本思想是：把指令执行所需要的所有控制信号存放在控制存储器中，需要时从这个存
储器中读取，即把操作控制信号编成微指令，存放在控制存储器中。一条机器指令的功能通常用许多条微指令组成
的序列来实现，这个微指令序列称为微程序。微指令在控制存储器中的存储位置称为微地址。
【答案】：D
2004年：
Created by cherish58，2011905．在微程序控制中，把操作控制信号编成（ ）。
A．微指令 B．微地址 C．操作码 D．程序
【分析】：微程序控制的基本思想是：把指令执行所需要的所有控制信号存放在控制存储器中，需要时从这个存
储器中读取，即把操作控制信号编成微指令，存放在控制存储器中。一条机器指令的功能通常用许多条微指令组成
的序列来实现，这个微指令序列称为微程序。微指令在控制存储器中的存储位置称为微地址。
【答案】：A
6．从一条指令的启动到下一条指令的启动的间隔时间称为（ ）。
A．时钟周期 B．机器周期 C．工作周期 D．指令周期
【分析】：指令周期：从一条指令的启动到下一条指令的启动的间隔时间。机器周期：指令执行中每一步操作所
需的时间，又称CPU周期。时钟周期：计算机主频周期。
【答案】：D
2005年：
11．通常，微指令的周期对应一个（ ）。
A．指令周期 B．主频周期 C．机器周期 D．工作周期
【分析】：指令周期：从一条指令的启动到下一条指令的启动的间隔时间。机器周期：指令执行中每一步操作所
需的时间，又称CPU周期。时钟周期：计算机主频周期。微指令周期等于读出一条微指令加上执行该微指令的所需时
间。通常微指令周期与指令的机器周期相等。
【答案】：C
19．在微程序控制器中，控制存储器由（ ）构成，用于存放 。
【分析】：CPU内用于存放实现指令系统全部指令的微程序的只读存储器称为控制存储器。
【答案】：只读存储器 微程 序
三、改错题：
历年真题：
（2000年）9．单总线结构系统是指：各大功能部件之间用一根信号线连接。
【答案】：单总线结构系统是指各寄存器及ALU之间的数据通路只用一条总线构成。
（2002年）2．CPU只是计算机的控制器。
【分析】：计算机硬件系统是由运算器、控制器、存储器、输入设备和输出设备等五大部分组成，其中将运算器和
控制器合在一起称为中央处理器，简称为CPU。
【答案】：CPU是由控制器和运算器组成的。
（2003年）21．硬连线方式是用时序电路产生时间控制信号，用存储逻辑电路实现各种控制功能。
【分析】：在采用组合逻辑和时钟信号相结合的硬连线控制器中，时间控制信号是由时序电路产生，而各种控制
功能则是由组合逻辑电路实现。
【答案】：硬连线方式是用时序电路产生时间控制信号，用组合逻辑电路实现各种控制功能。
（2004年）21．在一条微指令中，顺序控制部分的作用是发出指挥全机工作的控制信号。
【分析】：在一条微指令中，控制字部分的作用是发出指挥全机工作的控制信号；顺序控制部分的作用是产生后
继微指令的地址。
【答案】：在一条微指令中，顺序控制部分的作用是产生后继微指令的地址。
四、简答题：
历年真题：
（2000 年）4．在CPU中，哪些寄存器属于控制用的指令部件？它们各起什么作用？（5 分）
【答案】：
（1）程序计数器PC，提供取指地址，从而控制程序执行顺序。
（2）指令寄存器IR，存放现行指令，作为产生各种微操作命令的基本逻辑依据。
（3）程序状态寄存器PS，记录程序运行结果的某些特征标志，或用来设置程序运行方式与优先级，参与形
Created by cherish58，202100成某些微操作命令。
（2001年）1．硬连线控制器如何产生微命令？产生微命令的主要条件是哪些？
【答案】：
硬连线控制器依靠组合逻辑电路产生命令；（1分）
组合逻辑电路的输入是产生微命令的条件，主要有：① 指令代码；② 时序信号；③ 程序状态信息与标志
位；④ 外部请求信号。（4分）
（2002年）3．微程序控制器怎么产生操作控制信号，这种控制器有何优缺点？
【答案】：
操作控制信号的产生：事先把操作控制信号以代码形式构成微指令，然后存放到控制存储器中，取出微指
令时，其代码直接或译码产生操作控制信号。
优点：规整、易于修改和扩展。
缺点：速度较慢。
（2003年）26．当读取并执行一条指令时，控制器的主要功能是什么？
【答案】：
① 从主存取指令，并计算下一条指令在主存中的地址；
② 对指令进行译码，产生相应的操作控制信号；
③ 控制指令执行的步骤和数据流动的方向。
（2004年）28．与硬连线控制器相比，微程序控制器有哪些优缺点？
【答案】：与硬连线控制器相比，微程序控制器的优点是设计规整、易于修改和扩展。缺点是比硬连线控制器速
度慢。
（2005年）28．硬连线控制器主要由哪几部分构成？它是如何产生控制信号的？
【答案】：硬连线控制器主要由时钟源、环形脉冲发生器、控制信号编码器电路和指令译码器电路构成。硬连线
控制器采用组合逻辑与时钟信号结合的方式产生控制信号。
由上可见，每年都会考本章的简答题。考试的两个重点：一个是硬连线控制器的有关知识，另一个是微程序控
制器有关内容。这两方面大家一定重点掌握。
下面一些知识也要求大家了解
微程序控制器的构成：控制存储器、微指令寄存器μIR、微地址寄存器μAR、地址转移逻辑等。
微指令控制字编码的方式：微指令编码的3种方式分别是：直接表示法、编码表示法、混合表示法。
直接表示法是将每个控制信号都作为微指令中的一个位。这种方法的特点是简单直观，其输出直接用于控制，
但编码效率低。
编码表示法是将微指令进行分组编码，将不同时出现的相斥信号分在一个组中，然后将其编码成较短的代码。
这种方法减少了控制存储器所需要的存储器的代码的数量，但是编码的指令代码需要译码器译码，增加了控制信号
的延迟，影响CPU的工作频率。
混合表示法是把直接表示法与编码方法相结合使用，即采用部分直接表示部分编码的方法，将一些速度要求较
高，或与其他控制信号都相容的控制信号以直接方式表示，而将剩余信号以编码方式。混合表示法便于综合考虑指
令字长、灵活性和执行速度方面的要素。
微地址的形成方法：（微指令中顺序控制字段的编码）微地址的形成方法有三种方式：计数器方式、断定方式和结合
方式。
计数器方式，又称增量方式。用微程序计数器μPC来产生指令的微地址，将微程序中的各条微指令按顺序安排
在控制存储器中，后继地址由现行微地址加上一个增量形成。
断定方式，根据机器状态决定下一条微指令的地址，下一条微指令的地址包含在当前微指令的代码中。
结合方式，是将计数器方式和断定方式相结合。
中央处理器的基本功能：计算机的中央处理器（CPU）具有以下4个方面的基本功能：
（1）指令控制，即对程序运行的控制；
Created by cherish58，202110（2）操作控制，即对指令内操作步骤的控制；
（3）数据运算，即对数据进行算术运算和逻辑运算，这是CPU的最基本功能；
（4）异常处理和中断处理，如处理运算中的溢出等错误情况以及处理外部设备的服务请求等 此外，CPU还
具有存储管理、总线管理、电源管理等扩展功能
第6章 总线系统
一、名词解释：
历年真题：
（2001年）5．总线：计算机中连接功能单元的公共线路，是一束信号线的集合，包括数据总线、地址总线和控制
总线。
（2001年）8．同步通信方式：采用这种方式的总线传输中，所有的设备都从一个公共的时钟信号中获得定时信
息。
（2002年）4．主设备：获得总线控制权的设备。
（2003年）19．猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式 。
（2004年）16．总线的同步通信方式：采用这种方式的总线传输中，所有的设备都从一个公共的时钟信号中获得
定时信息。
（2005年）24．总线从设备：被主设备访问的设备。
近年以来每年考本章的名词称解释，所以第五章的名称解释是考试的重点。这里给大家列出了本章的名词解释
大家要熟悉一下，这都是本章的基本概念，有利于做名称解释、选择题、改错题和填空题。
1、猝发转输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式。
2、四边沿协议（全互锁）：全互锁的总线通信异步方式，就绪信号和应答信号的上升边沿和下降边沿都是触发
边沿。
3、码元：信息传输通道中，携带数据信息的信号单元。
4、波特率：码元传输速率，每秒通过信道传输的码元数。（传的是信号）
5、比特率：信息位传输速率，每秒钟通过信道传输的有效信息量。（传的是信息）
6、UART：通用异步接收器/发送器，一种典型的集成电路异步串行接口电路。
7、主设备：获得总线控制权的设备。
8、从设备：被主设备访问的设备。
9、总线事务：从总线的请求到完成总线的使用的操作序列。
10、总线协议：总线通信同步方式规则，规定实现总线数据传输的定时规则。
11、总线访问延迟：是主设备为获得总线控制权而等待的时间。
12、总线周期：是主设备占用总线的时间。
13、总线裁决方式：决定总线由哪个设备进行控制的方式。
14、系统总线：是用来连接系统内各大功能模块或设备，实现系统种各电路板的连接。
15、数据帧：串行数据传输的位格式，包括起始位，数据位，校验位，结束位和空闲位。
16、同步通信：所有的设备都从一个公共的时钟信号中获得定时信息。
17、异步通信：使用一个在CPU和设备之间的"握手"信号，去除了公共的时钟信号，从而使得操作变成异步的。
非互锁、半互锁、全互锁。
18、链式查询方式（菊花链方式）：各申请总线的设备合用一条总线作为请求信号线，而总线控制设备的响应信
号线则串接在各设备间。
19、计数器定时查询方式：集中式总线裁决方式之一，设备要求使用总线时通过一条公用请求线发出，总线控
制器按计数的值对各设备进行查询。
20、独立请求方式：集中式总线裁决方式之一，每一个设备都有一个独立的总线请求信号线送到总线控制器，
控制器也给各设备分别发送一个总线响应信号。
Created by cherish58，20212021、串行传输：是指数据的传输在一条线路上按位进行。（只需一条数据传输线，线路的成本低，适合于长距离
的数据传输）
22、并行传输：每个数据位都需要单独一条传输线，所有的数据位同时进行传输。（在采用并行传输方式的总线
中，除了有传输数据的线路外，还可以具有传输地址和控制信号的线路，地址线用于选择存储单元和设备，控制线
用于传递操作信号）
23、复合传输：又称总线复用的传输方式，它使不同的信号在同一条信号线上传输，不同的信号在不同的时间
片中轮流地身总线的同一条信号线上发出。（它与并串传输的区别在于分时地传输同一数据源的不同信息。）
24、消息传输方式：总线的信息传输方式之一，将总线需要传送的数据信息、地址信息、和控制信息等组合成一
个固定的数据结构以猝发方式进行传输。
25、总线：一组可由多个部件分时共享的信息传输线 。
二、选择填空题：
历年真题：
2000年：
8．“总线忙”信号由（ ）建立。
A．获得总线控制权的设备 B．发出“总线请求”的设备
C．总线控制器 D．CPU
【分析】：在总线控制机制中，准备使用总线的设备向总线控制器发出“总线请求”由总线控制器进行裁决。如
果经裁决允许该设备使用总线，就由总线控制器向该设备发出一个“总线允许”信号。该设备接收到此信号后，发
出一个“总线忙”信号用来通知其他设备总线己被占用。当该设备使用完总线时，将“总线忙”信号撤销，释放总
线。
【答案】：A
12．系统总线是用来连接（ ）的总线。
【分析】：按总线的连线类型不同，总线可分为：① 芯片级总线（CPU内部总线）：连接CPU内部运算器、控制器、
寄存器等的数据通路。② 扳级总线：连接主板中的CPU和主存等部件，也称局部总线。③ 系统总线是用来连接系统
内各大功能模块或设备。
【答案】：系统内各大功能模块或设 备
14．并行接口与I/O设备之间同时传送的位数，大多是 （ ）位。
【分析】：并行接口与I/O设备之间同时传送的8位数（1个字节）
【答案】：8
2001年：
14．在不同速度的设备之间传送数据，（ ）。
A．必须采用同步控制方式
B．必须采用异步控制方式
C．可以选用同步方式，也可选用异步方式
D．必须采用应答方式
【分析】：在不同速度的设备之间进行数据传送，既可以使用同步方式，也可以使用异步方式。异步方式主要是
用于在不同的设备之间进行通信，而如果两种速度的设备使用同一个时钟信号进行控制，采用同步的数据传送方式
同样可以进行数据的传送，只是快速设备的速度性能发挥不出来。
【答案】：C
15．挂接在总线上的多个部件（ ）。
A．只能分时向总线发送数据，并只能分时从总线接收数据
B．只能分时向总线发送数据，但可同时从总线接收数据
C．可同时向总线发送数据，并同时从总线接收数据
D．可同时向总线发送数据，但只能分时从总线接收数据
Created by cherish58，202130【分析】：为了使总线上的数据不发生“碰撞”，挂接在总线上的多个设备只能分时地向总线发送数据，即每一
个时刻只能有一个设备可以向总线传送数据，而从总线上接收数据的设备可有多个，因为接收数据的设备不会对总
线产生“干扰”。
【答案】：B
2002年：
12．异步传送方式常用于（ ）中，作为主要控制方式。
A．微型机的CPU内部控制
B．硬连线控制器
C．微程序控制器
D．串行I/O总线
【分析】：异步传输方式主要用于控制两种速度有一定差别的设备的信息传送，一般用在快速CPU与慢速的外设
之间进行串行通信的场合。
【答案】：D
13．串行总线主要用于（ ）。
A．连接主机与外围设备
B．连接主存与CPU
C．连接运算器与控制器
D．连接CPU内部各部件
【分析】：串行通信方式由于其信息传送速度慢、信息传送的距离较长、所使用的信号线数量较少等特点，主要
用于连接主机和慢速的外围设备，例如主机与串行鼠标之间的信息传送。
【答案】：A
2003年：
4．下列说法中正确的是（ ）。
A．半双工总线只能在一个方向上传输信息，全双工总线可以在两个方向上轮流传输信息
B．半双工总线只能在一个方向上传输信息，全双工总线可以在两个方向上同时传输信息
C．半双工总线可以在两个方向上轮流传输信息，全双工总线可以在两个方向上同时传输信息
D．半双工总线可以在两个方向上同时传输信息，全双工总线可以在两个方向上轮流传输信息
【分析】：根据总线上信号的传递方向，总线可分为单向传输（单工）总线和双向传输（双工）总线，而双工总线又
可分为半双工总线和全双工总线。其中单工总线只能向一个方向传递信号，半双工总线可以在两个方向上轮流传递
信号，全双工总线可以在两个方向上同时传递信号。 【答案】：C
9．在总线上，同一时刻（ ）。
A．只能有一个主设备控制总线传输操作
B．只能有一个从设备控制总线传输操作
C．只能有一个主设备和一个从设备控制总线传输操作
D．可以有多个主设备控制总线传输操作
【分析】：总线上的设备要控制总线必须先获得总线的控制权，获得总线控制权的设备称为主设备，被主设备访
问的设备称为从设备。在总线上信息的传输由主设备启动，一条总线上可以有多个设备能成为主设备，但在同一时
刻只能有一个主设备控制总线的传输操作。
【答案】：A
2004年：
4．系统级的总线是用来连接（ ）。
A．CPU 内部的运算器和寄存器
B．主机系统板上的所有部件
C．主机系统板上的各个芯片
Created by cherish58，202140D．系统中的各个功能模块或设备
【分析】：按总线的连线类型不同，总线可分为：① 芯片级总线（CPU内部总线）：连接CPU内部运算器、控制器、
寄存器等的数据通路。② 扳级总线：连接主板中的CPU和主存等部件，也称局部总线。③ 系统总线是用来连接系统
内各大功能模块或设备。
【答案】：D
15．总线从设备是（ ） 。
A． 掌握总线控制权的设备
B．申请作为从设备的设备
C． 被主设备访问的设备
D．总线裁决部件
【分析】：主设备：获得总线控制权的设备。从设备：被主设备访问的设备。
【答案】：C
2005年：
12．波特率表示传输线路上（ ）。
A．信号的传输速率
B．有效数据的传输速率
C．校验信号的传输速率
D．干扰信号的传输速率
【分析】：波特率是码元传输速率，每秒通过信道传输的码元数。（传的是信号）。比特率是信息位传输速率，每秒
钟通过信道传输的有效信息量。（传的是信息）
【答案】：A
13．不同信号在同一条信号线上分时传输的方式称为（ ）。
A．总线复用方式
B．并串行传输方式
C．并行传输方式
D．串行传输方式
【分析】：串行传输是指数据的传输在一条线路上按位进行。并行传输是每个数据位都需要单独一条传输线，所
有的数据位同时进行传输。不同信号在同一条信号线上分时传输的方式称为总线复用方式。
【答案】：A
17．按照传输定时的方法划分，总线数据通信方式可分为（ ）和 （ ）两类。
【分析】：按照传输定时的方法划分，总线数据通信方式可分为：① 同步通信：所有的设备都从一个公共的时钟
信号中获得定时信息。② 异步通信：使用一个在CPU和设备之间的“握手”信号，去除了公共的时钟信号，从而使
得操作变成异步的，有非互锁、半互锁、全互锁三种方式。
【答案】：同步通信 异步通信
三、改错题：
历年真题：
（2002年）3．按时序控制方式分，总线可分为串行总线和并行总线。
【分析】：对总线的分类有不同的分类标准：按传送格式分为：串行总线、并行总线；按时序控制方式分为：同步
总线（含同步扩展总线）、异步总线；按功能分为：系统总线、CPU内部总线、各种局部总线。
【答案】：按时序控制方式分，总线可分成同步总线和异步总线。
（2003年）23．串行通信只能采用异步方式。
【分析】：串行通信是指数据的传输是在一条传输线路上按位进行，它可以采用异步方式，也可以采用同步方式。
采用异步方式时，发送与接收设备之间采用“握手”信号来进行同步，而采用同步方式时，发送与接收设备都从同
一个公共的时钟信号中获得定时信息。
Created by cherish58，202150【答案】：串行通信可以采用异步方式，也可以采用同步方式。
（2004年）23．总线周期是指：任意总线设备为获取总线控制权而等待的时间与占用总线的时间之和。
【分析】：总线访问延迟：是主设备为获得总线控制权而等待的时间。总线周期：是主设备占用总线的时间。
【答案】：总线周期是指主设备占用总线的时间。
四、简答题：
历年真题：
（2000年）1．何谓存储总线？何谓I/O总线？各有何特点？（4分）
【答案】：
存储总线是连接CPU和主存储器之间的专用总线，速度高。
1/O总线是连接主机（CPU）与1/O设备之间的总线，可扩展性好。
（2001年）4．总线的分类方法主要有哪几种？请分别按这几种法说明总线的分类。
【答案】：① 按传送格式分为：串行总线、并行总线；② 按时序控制方式分为：同步总线（含同步扩展总线）、异
步总线；③ 按功能分为：系统总线、CPU内部总线、各种局部总线。
（2002年）4．何谓串行传输，有何优缺点?适用什么场合？
【答案】：
串行传输是指数据的传输在一条线路上按位进行。
优点：线路成本低。
缺点：传送速度慢。
适用场合：主机与低速外设间的传送、远距离通信总线的数据传送、系统之间的数据传送 。
（2003年）28．总线的同步通信方式与异步通信方式有什么区别？各适用于哪些场合？
【答案】：
同步通信方式中：数据传送操作由统一的时序信号同步定时控制，有严格的时钟周期划分，总线操作有固
定的时序，设备之间没有应答信号。适合各设备速度固定且一致（或差异不大）的场合。
异步通信方式中：数据传送操作所需时间视需要而定，总线操作周期时间不固定，没有时钟周期划分，设
备之间采用握手信号的应答方式。适合：各设备速度差异较大的场合。
（2004年）29．串行总线和并行总线有何区别? 各适用于什么场合？
【答案】：
串行总线的数据传输是在一条线路上按位进行。线路成本低，传送速度慢。 适用场合：主机与低速外设间
的传送、远距离通信总线的数据传送、系统之间的数据传送。
并行总线的每个数据位都需要单独一条传输线，所有的数据位同时进行传输。线路成本高，传送速度快。
适用场合：短距离的高速数据传输。
（2005年）29．系统总线接口有哪几项基本功能？
【答案】：① 控制：传递总线上的控制信息，主设备会通过总线接口向从设备发出控制信息。② 数据缓存：在总
线传递信息时，在总线接口中临时存放数据。③ 状态设置通过总线和转换从设备的工作信息，便于主设备了解从设
备的信息。④ 数据转换：某些总线接口需要对传递的数据进行转换。⑤ 整理：对接口本身进行调整。⑥ 程序中断。
由上可见，每年都会考本章的简答题。考试的两个重点：一个是串行总线和并行总线相关内容，另一个是同步
通信方式与异步通信方式有关内容。这两方面大家一定重点掌握。
下面一些知识也要求大家了解
1．什么是总线裁决？总线裁决有哪几种方式？
【答案】：
总线裁决就是决定总线由哪个设备进行控制。
总线裁决方式可分为集中式裁决和分布式裁决两种。
集中式裁决将总线的控制功能用一个专门的部件实现，这个部件可以位于连接在总线的某个设备上。当一
个设备需要向共享总线传输数据时，它必须先发出请求，在得到许可时才能发出数据。裁决部件接收来自各个设备
Created by cherish58，202160的总线使用请求信号，向其中某一个设备发出总线许可信号。
分布式裁决将控制功能分布在连接在总线上的各设备中，一般是固定优先级的。每个设备分配一个优先号
发出总线请求的设备将自己的优先号送往请求线上，与其他设备的请求信号构成一个合成信号，并将这个合成裁决
信号读入以判断是否有优先级更高的设备申请总线。这样可使得优先级最高的设备获得总线使用权。
2．集中式裁决有哪几种方式：
【答案】：
链式查询方式（菊花链方式）：各申请总线的设备合用一条总线作为请求信号线，而总线控制设备的响应
信号线则串接在各设备间。
计数器定时查询方式：集中式总线裁决方式之一，设备要求使用总线时通过一条公用请求线发出，总线控
制器按计数的值对各设备进行查询。
独立请求方式：集中式总线裁决方式之一，每一个设备都有一个独立的总线请求信号线送到总线控制器，
控制器也给各设备分别发送一个总线响应信号。
独立请求方式可以和链式查询方式结合，构成分组链式查询方式。
3．提高总线速度的措施。
【答案】：从物理层次：1．增加总线宽度；2．增加传输的数据长度；3．缩短总线长度；4．降低信号电平；5．采用差
分信号；6．采用多条总线。从逻辑层次：1．简化总线传输协议；2．采用总线复用技术；3．采用消息传输协议。
4．什么是串行接口？什么是并行接口？他们与系统总线及I/O设备之间的传递格式分别是什么？
【答案】：串行接口和并行接口都是总线与设备之间的接口部件，但与设备间的数据格式不同。串行接口与外设
之间串行，与系统总线之间并行。并行接口与外设之间并行，与系统总线之间并行。
（2001年）9．DMA 方式：直接存储器访问，直接依靠硬件实现主存与外设之间的数据直接传输，传输过程本身不需
CPU程序干预。
（2002年）5．I/O接口：是指连接主机和外围设备的逻辑部件。
（2003年）20．中断屏蔽：CPU处理一个中断的过程中，对其他一些外部设备的中断进行阻止。
（2004年）17．统一编址：将输入输出设备中控制寄存器、数据寄存器、状态寄存器等与内存单元一样看待，将
它们和内存单元联合在一起编排地址，用访问内存的指令来访问输入输出设备接口的某个寄存器，从而实现数据的
输入输出。
（2005年）25．通道程序：通道命令构成通道程序。在通道程序的控制下，通道对外围设备进行数据传输控制。
近年以来每年考本章的名词称解释，所以第五章的名称解释是考试的重点。这里给大家列出了本章的名词解释
大家要熟悉一下，这都是本章的基本概念，有利于做名称解释、选择题、改错题和填空题。
1．统一编址：将输入输出设备中控制寄存器、数据寄存器、状态寄存器等与内存单元一样看待，将它们和内存
单元联合在一起编排地址，用访问内存的指令来访问输入输出设备接口的某个寄存器，从而实现数据的输入输出。
2．单独编址：将输入输出设备中控制寄存器、数据寄存器、状态寄存器单独编排地址，用专门的控制信号进行
输入输出操作。
3．单级中断：CPU在执行中断服务程序的过程中禁止所有其他外部中断。
4．多级中断：CPU在执行中断服务程序的过程中可以响应级别更高的中断请求。
5．中断屏蔽：CPU处理一个中断的过程中，对其他一些外部设备的中断进行阻止。
6．DMA：直接存储器访问，直接依靠硬件实现主存与外设之间的数据直接传输，传输过程本身不需CPU程序干预。
7．现场保护：CPU在响应中断请求时，将程序计数器和有关寄存器内容等系统的状态信息存储起来，以使中断
处理结束之后能恢复原来的状态继续执行程序，称为现场保护。
8．中断向量：外设在向CPU 发出中断请求时，由该设备通过输入输出总线主动向CPU发出一个识别代码，这个
识别代码通常称为中断向量。
9．自陷：当CPU 出现有算术操作异常、非法指令、越权操作和访存中的异常等某种内部情况时自己引起的中断
称为自陷。
Created by cherish58，20217010．软件中断：由自陷指令引起的中断称为软件中断，又称为系统调用。
11．通道命令：通道用于执行输入输出操作的指令，也叫通道控制字（CCW）。
二、选择填空题：
历年真题：
2000年：
7．设置中断排队判优逻辑的目的是（ ）。
A ．产生中断源编码
B．使同时提出的请求中的优先级别最高者，得到及时响应
C．使CPU能方便地转入中断服务子程序
D．提高中断响应速度
【分析】：当有多个中断请求同时出现，中断服务系统必须能从中选出当前最需要给予响应的最重要的中断请
求，这就需要预先对所有的中断进行优先级排队，这个工作可由中断优先级判断逻辑来完成，排队的规则可由软件
通过对中断屏蔽寄存器进行设置来确定。
【答案】：B
10．通道程序在内存中的首地址由（ ）给出。
【分析】：CPU使用通道进行一个输入输出操作时，先发出一个通道启动信号。通道收到启动信号后，到指定的内
存单元中取通道地址字，并将其放入通道地址寄存器中。此通道地址字为通道程序在内存中的首地址。
【答案】：通道地址 字
11 ．在不改变中断响应次序的条件下，通过（ ）可以改变中断处理次序。
【分析】：在多重中断系统中，可以通过设置中断优先级来决定各个中断的级别。在实际的计算机系统中是通过
CPU 内部的一个中断屏蔽字寄存器来实现对不同中断的分别禁止的，这个寄存器可在中断处理程序中重新设置，这
样就可以改变原有的中断优先级别。
【答案】：改写中断屏蔽字
2005年：
16．采用DMA 方式传送数据是由 DMA接口来控制数据在 和 之间传输。
【分析】：DMA 是指直接存储器访问，是利用一个专门的接口电路将计算机的主存储器与高速的外设相连接，当
计算机要与外设进行数据传送时，由CPU发出一个控制信号启动DMA之后由DMA来控制完成外设与主存储器之间
的数据传送，其传送方式为数据块 （数据成组）传送，传送过程为连续的，中间没有停止等待的时间，所以数据的传
送速度较高。
【答案】：外设 主存储 器
三、改错题：
历年真题：
（2000年）7 ．对I/O 数据传送的控制方式，可分为程序中断控制方式和独立编址传送控制方式两种。
【分析】：对1/O数据传送的控制方式，可分为程序直接控制方式、程序中断控制方式、DMA 控制方式、通道控制
方式等。程序中断控制方式只是其中的一种方法，独立编址是指对1/O设备的控制寄存器、数据寄存器、状态寄存器
等单独进行地址编排，使用专门的指令对其进行操作，可用在各种数据传送的控制方式中。
【答案】：对1/O数据传送的控制方式，可分为：程序直接控制方式、程序中断方式、DMA 方式、通道控制方式等。
（2002 ）5 ．对外设统一编址是指给每个外设设置一个地址码。
【分析】：CPU与外设之间的信息传送是通过硬件接口来实现的，各种外设的硬件接口上又都包含有多个寄存器，
如控制寄存器、数据寄存器、状态寄存器等。统一编址是将外设接口上的各种寄存器等同于内存储器的存储单元，
通过使用访问内存单元的指令来访问外设接口上的各个寄存器，这样就可以使用访存指令来访问外设，输入输出操
作简单，程序设计比较简便。由于外设接口上的寄存器种类和数量通常不止一个，所以一个外设至少对应一个以上
的内存地址。
【答案】：对外设统一编址是将外设接口上的寄存器等内存单元，给每个外设设置至少一个地址 码。
Created by cherish58，202180（2003年）25 ．在常见的微机系统中，磁盘常采用通道方式与主存交换信息。
【分析】：通道传输方式是采用通道处理器将多个输入输出设备与CPU和主存储器相连接，并控制其信息的传输，
主要用于大型计算机以及网络服务器等含有许多输入输出设备并对输入输出有较高要求的场合；而 DMA方式是采
用DMA 控制器将外围设备与主存储器相连接，并控制其信息的传输，主要用于微型计算机中外设与主存之间需要成
批传输数据的场合，如微机系统中磁盘与主存之间的数据传输。
【答案】：在常见的微机系统中，磁盘常采用DMA方式与主存交换数据。
（ 2004年）25 ．通道就是一组输入输出传送线。
【分析】：通道是一种比DMA更高级的I/O控制部件，具有更强的独立处理数据的输入／输出功能，能同时控制
多台同类型或不同类型的设备。它在一定的硬件基础上，利用通道程序实现对1/O 的控制，更多地免去了CPU 的介
入，使系统的并行性能更高。
【答案】：通道是具有更强的独立处理数据的输入／输出功能，能同时控制多台同类型或不同类型的设备。
四、简答题：
历年真题：
2000 年：
7．以DMA 方式实现传送，大致可分为哪几个阶段？（3分）
【答案】：
① DMA 传送前的预置阶段（DMA初始化）；
② 数据传送阶段（DMA 传送）；
③ 传送后的结束处理。
2001 年：
2．何谓中断方式？它主要应用在什么场合？请举二例。
【答案】：
① 中断方式指：CPU在接到随机产生的中断请求信号后，暂停原程序，转去执行相应的中断处理程序，以
处理该随机事件，处理完毕后返回并继续执行原程序；
② 主要应用于处理复杂随机事件、控制中低速1/O ；
③ 例：打印机控制，故障处理 。
3．在 DMA 方式预处理（初始化）阶段， CPU 通过程序送出哪些信息？
【答案】：
向 DMA控制器及I/O接口（分离模式或集成模式均可）分别送出以下信息：
① 测试设备状态，预置DMA 控制器工作方式；
② 主存缓冲区首址，交换量，传送方向；
③ 设备寻址信息，启动读／写。
6 ．中断接口一般包含哪些基本组成？简要说明它们的作用。
【答案】：
① 地址译码。选取接口中有关寄存器，也就是选择了I/O设备。
② 命令字／状态字寄存器。供CPU 输出控制命令，调回接口与设备的状态信息。
③ 数据缓存。提供数据缓冲，实现速度匹配。
④ 控制逻辑。如中断控制逻辑、与设备特性相关的控制逻辑等 。
2002 年：
5．何谓DAM 方式？说明它的适用场合。
【答案】：
定义：由DMA 控制器控制系统总线，直接依靠硬件实现主存与I/O 设备之间的数据直传，传送期间不需要
CPU 程序干预。
适用场合：高速、批量数据的简单传送。
Created by cherish58，2021906．何谓多重中断？如何保证它的实现？
【答案】：
多重中断：CPU在响应处理中断过程中，允许响应处理更高级别的中断请求，这种方式称为多重中断。
实现方法：在中断服务程序的起始部分用一段程序来保存现场、送新屏蔽字以屏蔽同级别和低级别的中断
请求、然后开中断，这样CPU就可响应更高级别的中断请求，实现多重中断。
2003年：
30．简述外围设备接口的主要功能。（新教材取消了这一内容）
31．试对程序中断方式和 DMA 方式各分别举出二种应用例子。
【答案】：
中断方式常用于打印机输出、键盘输入等；
DMA方式常用于读／写磁盘、读／写磁带等。
2004年：
30．主机与外围设备之间信息传送的控制方式有哪几种？采用哪种方式 CPU 效率最低？
【答案】：主机与外围设备之间信息传送的控制方式有四种：程序查询方式、中断方式、DMA方式和通道方式。程
序查询方式CPU 效率最低。
31．试比较中断方式与 DMA 方式的主要异同，并指出它们各自应用在什么性质的场合。
【答案】：
相同点：这两种方式下，主机和I/O设备都是并行工作。
不同点：中断方式在CPU响应了I/O设备的中断请求后，要暂停现行程序的执行，转为I/O设备服务。DMA
方式直接依靠硬件实现主存与I/O设备之间的数据直传，传送期间不需要CPU程序干预，CPU可继续执行原来的程
序，CPU效率比中断方式。
DMA 方式适用场合：高速、批量数据的简单传送。
中断方式适用场合：处理复杂随机事件、控制中低速1/O设备。
2005年：
30．基本的DMA控制器的主要部件有哪些？
【答案】：基本的DMA控制器的主要部件有：地址寄存器、长度计数器、数据寄存器、标志寄存器、命令寄存器、控
制逻辑等。
31．简述多重中断系统中CPU响应处理一次中断的步骤。
【答案】：① 关中断；② 保存现场信息；③ 判别中断条件；④ 开中断；⑤ 执行中断服务程序；⑥ 关中断；⑦
恢复现场信息；⑧ 开中断。
由上可见，每年都会考本章的两道以上的简答题。考试的两个重点：一个是DMA方式的有关知识（每年都考），另一
个是中断方式有关内容。这两方面大家一定重点掌握。
下面一些知识也要求大家了解
1．中断方式的接口控制器功能：能向CPU发出中断请求信号；能发出识别代码提供提供引导CPU在响应中断请求后
转入相应服务程序的地址； CPU要能够对中断请求进行允许或禁止的控制；能使中断请求参加优先级排队。
2．CPU与外围设备进行通信有三种类型：① CPU向外围设备发出操作控制命令；② 外围设备向CPU提供状态信息；
③ 数据在CPU和外围设备之间传递。
3．中断裁决机制：轮询、菊花链、独立请求。
4．CPU与DMA访问内存冲突的裁决的三种方法：① CPU等待DMA的操作；② DMA乘存储器空闲时访问存储器；③
CPU与DMA交替访问存储器。
5．CPU启动DMA的步骤：① 测试设备状态；② 写存储器地址寄存器；③ 写长度计数器；④ 启动DMA控制逻辑。
6．通道的三种类型：
选择通道：它与设备之间的传输一直维持到设备请求的传输完成为止，然后为其它外围设备传输数据。数据宽
度是可变的，通道中包含一个保存IO数据传输所需的参数寄存器。
Created by cherish58，203100数组多路通道：以数组为单元在若干高速传输操作之间进行交叉复用。
字节多路通道：用于连接多个慢速的和中速的设备，这些设备的数据传送以字节为单位，字节交叉模式、猝发
模式。
7．字节多路通道与数组多路通道的区别：首先数组多路通道允许多个设备同时工作，但只允许一个设备进行传输型
操作，而其它设备进行控制型操作；字节多路通道不仅允许多个设备操作，而且允许它们同时进行传输型操作。其
次，数组多路通道与设备之间的数据传送的基本单位是数据块，通道必须为一个设备传送完一个数据块以后才能为
别的设备传送数据，而字节多路通道与设备之间的数据传送基本单位是字节，各设备之间的数据传送是以字节为单
位交替进行的。
8．通道的功能：① 接受CPU的I/O操作指令，按指令要求控制外围设备；② 从内存中读取通道程序，并执行，即向
设备控制器发送各种命令；③ 组织和控制数据在内存与外设之间的传送操作；④ 读取外设的状态信息，形成整个
通道的状态信息，提供给CPU或保存在内存中；⑤ 向CPU发出IO 操作中断请求，将外围设备的中断请求和通道本
身的中断请求按次序报告CPU。
第 8章 外围设备
历年真题：
2000 年：
9 ．在大多数磁盘中（ ）。
A．各磁道的位密度相同
B．最外圈磁道的位密度最大
C．最内圈磁道的位密度最大
D．写入时选择较高的位密度，以增加记录信息；读出时选择低的位密度，以提高可靠 性
【分析】：位密度是指磁道中单位长度所存储的信息量。在磁盘存储器中，每个磁道所存储的信息是相同的，而
最内圈磁道的长度最小，所以该磁道的位密度最大。
【答案】：C
10 ．在调频制记录方式中，是利用（ ）来写0或1 。
A．电平高低的变化 B ．电流幅值的变化
C．电流相位的变化 D．电流频率的变化
【分析】：在调频制记录方式中，信息的写入是依靠写入电流频率的变化来实现的，写1时的电流变化频率是写
0时电流变化频率的2倍。
【答案】：D
2002 年：
14 ．在常用磁盘中，（ ）。
A．外圈磁道容量大于内圈磁道容量
B．各道容量不等
C．各磁道容量相同
D ．内圈磁道容量大于外圈磁道容量
【分析】：位密度是指磁道中单位长度所存储的信息量。在磁盘存储器中，每个磁道所存储的信息是相同的。
【答案】：C
15．在下列存储器中，（ ）可以作为主存储器。
A．半导体存储器 B．硬盘 C ．光盘 D ．磁带
【答案】：A
2003 年：
1 ．CRT 图形显示器的分辨率表示（ ）。
A．一个图像点（像素）的物理尺 寸
B．显示器一行能显示的最大图像点数与一列能显示的最大图像点数
Created by cherish58，203110C．显示器屏幕可视区域的大小
D．显示器能显示的字符个数
【分析】：CRT图形显示器的分辨率是衡量显示器显示清晰度的指标，是以图像点（像素）的个数为标志，即显示
器一行能显示的最大图像点数与一列能显示的最大图像点数的乘积。
【答案】：B
6．下列各种记录方式中，不具自同步能力的是（ ）。
A．不归零制 B．改进型调频制 MFM
C．调相制PM D．调频制
【分析】：自同步能力是指从读出的数据中自动提取同步信号的能力，其能力大小可用最小磁化翻转间隔与最
大磁化翻转间隔的比值来表示，比值越大，则自同步能力越强。在各种记录方式中，NRZ，NRZ记录方式没有自同步能
力，PM，FM，MFM记录方式具有自同步能力。
【答案】：A
11．在下列存储器中，哪种速度最快（ ）。
A．磁盘 B．磁带 C．主存 D．光盘
【分析】：各种存储器由于存储介质和内部结构的不同，其读写速度也不同。读写速度由快到慢的次序为：高速
缓冲存储器、主存储器、辅助存储器。各种辅助存储器的读写速度由快到慢次序为：硬盘存储器、光盘存储器、磁带
存储器。
【答案】：C
2004年：
2．在下列设备中，属于图形输入设备的是（ ）。
A．键盘 B．条形码阅读机 C．数字化仪 D．显示器
【分析】：图形输入设备有鼠标、数字画仪和触摸屏；文字输入设备有键盘、磁卡阅读机、条形码阅读机、纸带阅
读机、卡片阅读机。图像输入设备有扫描仪、数码相机和摄像头等。
【答案】：C
3．磁表面存储器记录信息是利用磁性材料的（ ）。
A．磁滞回归线特性 B．磁场渗透特性
C．磁场分布特性 D．磁场吸引力特性
【分析】：磁表面存储器记录信息是利用磁性材料的磁滞回归线特性。
【答案】：A
2005年：
14．24针打印机的打印头的针排列是（ ）。
A．24根针排成一列 B．24根针排成2列
C．24根针排成3列 D．24根针排成4列
【分析】：9针打印机的打印头的针排列是单列，24针打印机的打印头的针排列是双列。
【答案】：B
15．在常用磁盘的各磁道中（ ）。
A．最外圈磁道的位密度最大
B．最内圈磁道的位密度最大
C．中间磁道的位密度最大
D．所有磁道的位密度一样大
【分析】：（和2000年题目一样）位密度是指磁道中单位长度所存储的信息量。在磁盘存储器中，每个磁道所存
储的信息是相同的，而最内圈磁道的长度最小，所以该磁道的位密度最大。
【答案】：B
二、填空题：
Created by cherish58，2031202005年：
20．磁盘存储设备主要由磁记录介质、（ ）和（ ）三个部分组成。
【分析】：磁盘存储设备主要由磁记录介质、磁盘控制器和磁盘驱动器三个部分组成。
【答案】：磁盘控制器 磁盘驱动器
三、改错题：
（2000年）8．在计算机系统中，除CPU外的其它部件和设备都称为外围设备。
【分析】：计算机硬件系统是由运算器、控制器、存储器、输入设备和输出设备5个部分组成的，将运算器和控制
器合在一起称为CPU；存储器又分为内部存储器和外部存储器两类，内部存储器与CPU一起组成计算机的主机，外
存储器、输入设备、输出设备等合称为外围设备。
【答案】：在计算机系统中，除CPU和主存之外的其他部件和设备，常被称为外围设备。
（2000年）10．写入硬盘时，若一个文件的长度超出一个磁道的容量，则继续写入同面的相邻磁道中。
【分析】：硬盘存储器一般由多个盘片组成，每个盘片的两个面都用来记录信息（最外层的两个盘片有时只用一
个面），每个盘面中相同磁道号的各个磁道构成一个柱面。硬盘中信息的存储是按柱面顺序，即只有在一个柱面都
被记录上信息后才进入下一个柱面。在柱面内信息的存储是按磁道顺序，即只有在一个磁道都被记录上信息后才进
入下一个相邻面的磁道中。
【答案】：写入硬盘时，若一个文件的长度超过一个磁道的容量，则继续写入同一柱面的相邻面的磁道 中。
（2002年）4．显示适配器中的显示缓冲存储器用于存放显示器将要向CPU输入的信息。
【分析】：显示器是计算机硬件系统中的输出设备，由于CPU的处理速度较快，而显示器显示输出的速度较慢，
为了将两者间的速度差别协调起来，在显示适配器中配置一定容量的显示缓冲存储器，CPU将要显示输出的信息先
送入此缓冲存储器，再由显示适配器控制显示输出，而CPU则可以转去完成其他的任务。由此可见，显示适配器中的
显示缓冲存储器用于存放CPU向显示器输出的信息。
【答案】：显示适配器中的显示缓冲存储器用于存放CPU向显示器输出的信息。
（2003年）24．磁盘是存储器，不是外围设备。
【分析】：磁盘是计算机系统中的辅助存储器，当计算机从磁盘中读出数据信息时，磁盘属于输入设备，而当计
算机向磁盘写入信息时，磁盘又属于输出设备。所以磁盘既是存储器，又属于外围设备。
【答案】：磁盘既是存储器，又属于外围设备。
由上可见，本章的主要考试题型是选择题、填空题和改错题，所占分数约为4分左右。注重对基本知识的考核。其他
要了解的知识：
1．归零制（RZ）：磁表面存储器记录信息时，不论某存储单元的代码是0或者1，在记录下一个信息之前记录电流要
恢复到零电流。在给磁头线圈送入的脉冲电流中，正脉冲表示1，负脉冲表示0。不具有自同步能力
2．不归零制（NRZ）：磁表面存储器记录信息时，磁头线圈上始终有电流，不是正向电流就是反向电流，正向电流代表
1，反向电流代表0。不具有自同步能力
3．调相制（PM）：磁表面存储器记录信息时，在一个磁化元的中间位置，利用电流相位的变化进行写1或者写0，所以
通过磁头中的电流方向一定要改变一次。规定在记录数据1时，磁化翻转的方向是由负变正，记录数据0时磁化翻
转的方向为由正变负。具有自同步能力
4．调频制（FM）：磁表面存储器记录信息时，无论记录的代码是1还是0，或者是连续的1或连续的0在相邻的两个
存储元交界处电流要改变方向。在记录数据1时，还要在位与位之间再翻转一次，写1的电流频率是写0的2倍。具
有自同步能力
5．改进调频制（MFM）：只有连续记录两个或两个以上0时在位周期的起始位置处翻转一次，而不是在每个位周期的
起始处都翻转。
6．RLL码：在高密度磁盘中采用的信息编码技术，将原始数据序列变换成0，1游程长度受限制的代码，然后再用不
归零制方式进行调制和写入。具有自同步能力
7．磁盘访问时间：指从发出读写命令，磁头从某一起始位置移动到新的记录位置，到结束从盘片读出或写入信息所
花的时间。 磁盘访问时间＝寻道时间+旋转延迟+控制延迟+数据传输时间。
Created by cherish58，2031308．寻道时间：是将磁头定位到所要求的磁道上所需的时间。
9．旋转延迟：是找道完成后到磁道上需要访问的信息到达磁头的时间。
10．平均旋转延迟：是磁盘旋转半周的时间，也称磁盘的寻址时间。
数据传输时间取决于读扇区数据时间和传输数据时间，等于两者的最大值。
磁盘数据传输率＝转速/秒＊每道容量
11．磁盘存储设备的主要技术指标：存储密度、存储容量、寻址时间和数据传输等。
12．光盘的结构包括：光盘基片、存储介质和密封层。
13．光盘存储设备有只读型CD-ROM、EORM（写一次读多次）型和可檫写型三种。
操作系统要点
1、简述操作系统的定义。
操作系统是计算机系统的一种系统软件，它统一管理计算机系统的资源和控制程序的执行。
2、在多道程序设计技术的系统中，操作系统怎样才会占领中央处理器？
只有当中断装置发现有事件发生时，它才会中断当前占用中央处理器的程序执行，让操作系统的处理服务程
序占用中央处理器并执行之。
3、简述"删除文件"操作的系统处理过程。
用户用本操作向系统提出删除一个文件的要求，系统执行时把指定文件的名字从目录和索引表中除去，并收
回它所占用的存储区域，但删除一个文件前应先关闭该文件。
4、对相关临界区的管理有哪些要求？
为了使并发进程能正确地执行，对若干进程共享某一变量（资源）的相关临界区应满足以下三个要求 ：
① 一次最我让一个进程在临界区中执行，当有进程在临界区中时，其他想进入临界区执行的进程必须等待 ；
② 任何一个进入临界区执行的进程必须在有限的时间内退出临界区，即任何一个进程都不应该无限逗留在自己的
临界区中；
③ 不能强迫一个进程无限地等待进入它的临界区，即有进程退出临界区时应让下一个等待进入临界区的进程进入
它的临界区。
5、简述解决死锁问题的三种方法。
① 死锁的防止。系统按预定的策略为进程分配资源，这些分配策略能使死锁的四个必要条件之一不成立，从而使系
统不产生死锁。
② 死锁的避免。系统动态地测试资源分配情况，仅当能确保系统安全时才给进程分配资源 。
③ 死锁的检测。对资源的申请和分配不加限制，只要有剩余的资源就呆把资源分配给申请者，操作系统要定时判断
系统是否出现了死锁，当有死锁发生时设法解除死锁。
6、从操作系统提供的服务出发，操作系统可分哪几类？
批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系 统。
7、简述计算机系统的中断机制及其作用。
中断机制包括硬件的中断装置和操作系统的中断处理服务程序。
中断装置由一些特定的寄存器和控制线路组成，中央处理器和外围设备等识别到的事件保存在特定的寄存器
中，中央处理器每执行完一条指令，均由中断装置判别是否有事件发生。
若无事件发生，CPU继续执行；若有事件发生，则中断装置中断原占有CPU的程序的执行，让操作系统的处理
事件服务程序占用CPU，对出现的事件进行处理，事件处理完后，再让原来的程序继续占用CPU执行。
8、选择进程调度算法的准则是什么？
由于各种调度算法都有自己的特性，因此，很难评价哪种算法是最好的。一般说来，选择算法时可以考虑如下
一些原则：
① 处理器利用率；
② 吞吐量；
③ 等待时间；
Created by cherish58，203140④ 响应时间。
在选择调度算法前，应考虑好采用的准则，当确定准则后，通过对各种算法的评估，从中选择出最合适的算法。
9、独占设备采用哪种分配方式？
独占设备通常采用静态分配方式。
即在一个作业执行前，将作业要使用的这类设备分配给作业，在作业执行期间均归该作业占用，直到作业执行结束
才归还。
10、产生死锁的原因是什么？
① 系统资源不足；
② 进程推进顺序不合适。
在早期的系统中，由于系统规模较小，结构简单，以及资源分配大多采用静态分配法，使得操作系统死锁问题的严
重性未能充分暴露出来。但今天由于多道程序系统，以至于数据系统的出现，系统中的共享性和并行性的增加，软
件系统变得日益庞大和复杂等原因，使得系统出现死锁现象的可能性大大增加。
11、何谓批处理操作系统？
用户准备好要执行的程序、数据和控制作业执行的说明书，由操作员输入到计算机系统中等待处理。操作系统
选择作业并按作业说明书的要求自动控制作业的执行。采用这种批量化处理作业的操作系统称为批处理操作系统。
12、对特权指令的使用有什么限制？
只允许操作系统使用特权指令，用户程序不能使用特权指令。
13、影响缺页中断率有哪几个主要因素？
影响缺页中断率的因素有四个：
① 分配给作业的主存块数多则缺页率低，反之缺页中断率就高。
② 页面大，缺页中断率低；页面小缺页中断率高 。
③ 程序编制方法。以数组运算为例，如果每一行元素存放在一页中，则按行处理各元素缺页中断率低；反之，按列
处理各元素，则缺页中断率高。
④ 页面调度算法对缺页中断率影响很大，但不可能找到一种最佳算法。
14、磁盘移臂调度的目的是什么？常用移臂调度算法有哪些？
磁盘移臂调度的目的是尽可能地减少输入输出操作中的寻找时间。
常用的移臂调度算法有：
① 先来先服务算法
② 最短寻找时间优先算法
③ 电梯调度算法
④ 单向扫描算法。
15、常用的作业调度算法有哪些？
① 先来先服务算法
② 计算时间短的作业优先算法
③ 响应比最高者优先算法
④ 优先数调度算法
⑤ 均衡调度算法
16、计算机系统的资源包括哪些？
计算机系统的资源包括两大类：硬件资源和软件资源。
硬件资源主要有中央处理器、主存储器、辅助存储器和各种输入输出设备 。
软件资源有编译程序、编辑程序等各种程序以及有关数据。
17、CPU在管态和目态下工作有何不同？
当中央处理器处于管态时，可以执行包括特权指令在内的一切面器指令，而在目态下工作时不允许执行特权
指令。
Created by cherish58，20315018、何为页表和快表？它们各起什么作用？
页表指出逻辑地址中的页号与所占主存块号的对应关系。
作用：页式存储管理在用动态重定位方式装入作业时，要利用页表做地址转换工作 。
快表就是存放在高速缓冲存储器的部分页表。它起页表相同的作用。
由于采用页表做地址转换，读写内存数据时CPU要访问两次主存。有了快表，有时只要访问一次高速缓冲存储
器，一次主存，这样可加速查找并提高指令执行速度。
19、作业在系统中有哪几种状态？
一个作业进入系统到运行结束，一般要经历进入、后备、运行和完成四个阶段，相应地，作业亦有进入、后备、
运行和完成四种状态。
① 进入状态：作业的信息从输入设备上预输入到输入井，此时称为作业处于进入状态 。
② 后备状态：当作业的全部信息都已输入，且由操作系统将其存放在输入井中，此时称作业处于后备状态。系统将
所有处于后备状态的作业组成后备作业队列，等待作业调度程序的调度。
③ 运行状态：一个后备作业被作业调度程序选中，分配了必要的资源，调入内存运行，称作业处于运行状 态。
④ 完成状态：当作业正常运行完毕或因发生错误非正常终止时，作业进入这完成状态 。
20、用fork创建新进程，它要做哪些工作？
由fork创建新进程的主要工作有：
① 在进程表proc[ ]中为子进程找一个空闲的表项，用来存放子进程的proc结构；
② 为子进程分配一个唯一的标识号；
③ 把父进程中的字段复制到子进程的proc中，并把p - pid置为分配到的进程标识号，把p-pid置为父进程的标
识号，把p-stat置为创建状态；
④ 按父进程中p-size所示的长度为子进程申请分配内存。若有足够的内存，则把父进程的user结构、栈和用户数
据区全部复制到子进程的空间中；若无足够的内存，则在磁盘对换区中分配存储空间，然后复制到对换区中，置于
进程状态为就绪状态。
21、为什么说批处理多道系统能极大地提高计算机系统的工作效率？
① 多道作业并行工作，减少了处理器的空闲时间。
② 作业调度可以合理选择装入主存储器中的作业，充分利用计算机系统的资源。
③ 作业执行过程中不再访问低速设备，而直接访问高速的磁盘设备，缩短执行时间 。
④ 作业成批输入，减少了从操作到作业的交接时间。
23、什么是线程？多线程技术具有哪些优越性？
线程是进程中可独立执行的子任务，一个进程可以有一个或多个线程，每个线程都有一个惟一的标识符。线程
与进程有许多相似之处，往往把线程又称为"轻型进程"，线程与进程的根本区别是把进程作为资源分配单位，而线
程是调度和执行单位。
多线程技术具有多个方面的优越性：
① 创建速度快、系统开销小：创建线程不需要另行分配资源 ；
② 通信简洁、信息传送速度快：线程间的通信在统一地址空间进程，不需要额外的通信机制 ；
③ 并行性高：线程能独立执行，能充分利用和发挥处理器与外围设备并行工作的能力 。
24、UNIX系统中的优先权和优先数有什么关系？如何确定进程的优先权和优先数？
UNIX中每个进程都有一个优先数，就绪进程能否占用处理器的优先权取决于进程的优先数，优先数越小则优
先权越高。
UNIX以动态方式确定优先权，如核心的进程优先权高于进入用户态的进程；降低用完一个时间片的进程的优
先权；对进入睡眠的进程，其等待事件越急优先数越高；降低使用处理器时间较长的进程的优先权。
UNIX中确定进程优先数的方法有两种：设置方法和计算方法。前者对要进入睡眠状态的进程设置优先数，若
等待的事件急迫，则设置较小的优先数；后者用户进程正在或即将转入用户状态运行时确定优先数。
26、共享设备允许多个作业同时使用，这里的"同时使用"的含义是什么？
Created by cherish58，203160"同时使用"的含义是多个作业可以交替地启动共享设备，在某一时刻仍只有一个作业占有。
27、简述"打开文件"操作的系统处理过程。
用户要使用一个已经存放在存储介质上的文件前，必须先提出"打开文件"要求。这时用户也必须向系统提供
参数：用户名、文件名、存取方式、存储设备类型、口令等。系统在接到用户的"打开文件"要求后，找出该用户的文件
目录，当文件目录不在主存储器中时还必须把它读到主存储器中；然后检索文件目录，指出与用户要求相符合的目
录项，取出文件存放的物理地址。
对索引文件还必须把该文件的索引表存放在主存储器中，以便后继的读写操作能快速进行。
28、什么是"前台"作业、"后台"作业？为什么对"前台"作业要及时响应？
批处理操作系统实现自动控制无需人为干预，分时操作系统实现了人机交互对话，这两种操作系统具有各自
的优点。为了充分发挥批处理系统和分时系统的优点，在一个计算机系统上配置的操作系统往往既具有批处理能力
又有提供分时交互的能力。这样，用户可以先在分时系统的控制下，以交互式输入、调试和修改自己的程序；然后，
可以把调试好的程序转交给批处理系统自动控制其执行而产生结果。这些由分时系统控制的作业称为"前台"作业，
而那些由批处理系统控制的作业称为"后台"作业。
在这样的系统中，对前台作业应该及时响应，使用户满意；对后台作业可以按一定的原则进行组合，以提高系
统的效率。
29、存储型设备和输入输出型设备的输入输出操作的信息传输单位有何不同？
存储型设备输入输出操作的信息传输单位是"块"，而输入输出型设备输入输出操作的信息传输单位是"字符"。
32、什么是计算机系统？它由哪几部分组成？
计算机系统是按用户的要求接收和存储信息，自动进行数据处理并输出结果信息的系统。
计算机系统由硬件系统和软件系统组成。硬件系统是计算机系统赖以工作的实体，软件系统保证计算机系统
按用户指定的要求协调地工作。
33、计算机系统怎样实现存储保护？
一般硬件设置了基址寄存器和限长寄存器。
中央处理器在目态下执行系统中，对每个访问主存的地址都进行核对，若能满足：基址寄存器值≤访问地址≤
基址寄存器值＋限长寄存值，则允许访问，否则不允许访问。并且不允许用户程序随意修改这两个寄存器的值。这
就实现了存储保护。
34、给出系统总体上的中断处理过程。
CPU每执行完一条指令就去扫描中断寄存器，检查是否有中断发生，若没有中断就继续执行下条指令；若有中
断发生就转去执行相应的中断处理程序。中断处理过程可粗略的分为以下四个过程：
① 保护当前正在运行程序的现场；
② 分析是何种中断，以便转去执行相应的中断处理程序；
③ 执行相应的中断处理程序；
④ 恢复被中断程序的现场。
35、死锁发生的必要条件有哪些？
发生死锁的必要条件有四点：互斥条件、不可抢占条件、部分分配条件和循环等待条件 。
① 互斥条件：系统中存在一个资源一次只能被一个进程所使用；
② 非抢占条件：系统中存在一个资源仅能被占有它的进程所释放，而不能被别的进程强行抢占 。
③ 占有并等待条件：系统中存在一个进程已占有了分给它的资源，但仍然等待其他资源 。
④ 循环等待条件：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有若干种资源中的某
一种，同时每个进程还要求（链上）下一个进程所占有的资源。
36、用户程序中通常用什么方式指定要使用的设备？为什么？
用户程序中通常用"设备类、相对号"请求要使用的设备，即不具体指定要哪一台设备，而是提出要申请哪类设
备多少台。
Created by cherish58，203170这种方式使设备分配适应性好、灵活性强。
否则若用绝对号来指定设备，如果这台设备已被占用或有故障时，该作业就无法装入主存中 。
37、进程调度中"可抢占"和"非抢占"两种方式，哪一种系统的开销更大？为什么？
可抢占式会引起系统的开销更大。
可抢占式调度是严格保证任何时刻，让具有最高优先数（权）的进程占有处理机运行，因此增加了处理机调度
的时机，引起为退出处理机的进程保留现场，为占有处理机的进程恢复现场等时间（和空间）开销增大。
38、一个含五个逻辑记录的文件，系统把它以链接结构的形式组织在磁盘上，每个记录占用一个磁盘块，现
要求在第一记录和第二记录之间插入一个新记录，简述它的操作过程。
从文件目录中找到该文件，按址读出第一个记录；
取出第一个记录块中指针，存放到新记录的指针位置；
把新记录占用的物理块号填
Created by cherish58，203180
