文章目录
-
- 填空题:
- 数据结构简答题：
- 简答：计算机组成原理：
- 历年
-
- 2021
填空题:
- 计算机系统由和两部分组成。
- CPU 是和的总称。
- 在总线结构的计算机系统中，总线通常是由三部分组成。
- 通过执行，可以设计的内容。
- 当指令的形式地址给出存储在操作数所在存储单元地址的寄存器时，这种搜索方式是。
- 计算机能处理的语言是，编程语言中最接近机器语言的语言是
- N 个 cache 块，在组相连映射中，
- 一组构成进而构成
- 在半导体随机存储器中SRAM的原理是触发器，DRAM的原理是。SRAM 的比DRAM 快，但 不如DRAM 高
- 无论是双符号位还是单符号位，定点加法运算器都必须有，用。
- I/O 设备准备方法有。
- I/O 有。
- CPU 控制器有。
- 浮点数的浮点数分别决定。
- 程序员能操作的地址叫做，CPU真正访问的地址叫。
- 用统一时钟标记时间，用回应来标记时间。
- 微程序控制器的核心部件是，它通常由只读存储器组成。
- CPU 主要功能是。
- CPU 四大功能是。
- DMA 的功能:
- 在保护断点时保存。
- 在指令周期取指阶段取出，在指令执行阶段取出。
- 存储系统中CPU能直接访问，但不能直接访问。
- 中断周期前CPU工作周期是，中断后CPU工作周期是
- 移码表示法主要用于表示，有利于加减操作操作中比较大小。
- 存储在寄存器间接搜索模式中的操作数，寄存器中存放的是
- CPU 从内存取出指令并执行指令的时间称为。
- 微程序的微指令是指。
- 目前正在执行的指令保存在CPU的中间保存了运算结果等状态标志CPU的中。
- 组合逻辑控制器使用的三级时序是指等三级。
- 提高加法器运行速度的关键是。
- 减法和加法使用相同部件的关键是
- 扩展操作码技术的目的是
- 浮点数表示方法：。
- 中断响应过程中，保护程序计数器PC的作用是。
- 构成控制信号序列的最小单位是。
- 数字计算机硬件由五部分组成，即。
- 程序计数器PC，
- 就逻辑功能而言，微程序属于的范畴。
- 总线数据通路宽度是指。
- 冯诺依曼体质思想的核心是采用，它是。
- 计算机硬软件的功能等价是指。
- 根据任务，计算机总线可分为四种类型。
- 机器数是指在。
- DMA 传输方式中的周期挪用是。(相应 DMA 请求后，CPU 暂停执行程序的下一个周期 DMA 周期中实现 DMA 传送)
- 动态存储器的刷新可以概括为
- 微程序中的是指构成控制信号序列的最小单位。
- 微指令的编码方法有。
- 指令的寻址方式是。
- 立即寻址的操作数是由
- 运算器的基本功能是执行
- PROM 是指
- EPROM 是指
数据结构简答题：
直接插入排序。当序列基本有序时，最有效的排序算法是插入排序，其次是泡沫排序。
拓扑排序通常用于确定依赖关系集中和事物发生的顺序。 例如，在日常工作中，项目可以分为 A、B、C、D 四个子部分来完成，但是 A 依赖 于 B 和 C，C 依赖于 D。 为了计算项目的顺序，可以对关系集进行拓扑排序，得到线性序列， 前面的任务是需要先完成的任务。 关键路径通常是决定项目工期的活动序列。 这是项目中最长的路径，即使是很小 移动也可能直接影响整个项目的最早完成时间。 关键路径的工期决定了整个工程的工期， 浮动时间是任何关键路径上终端元素的延迟 0 或者负数会直接影响项目的预期完成时间。 原理:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可 以递归进行，以此达到整个数据变成有序序列。
快速排序的优点在于平均性能好，缺点在于初始序列有序或基本有序时，其时间复杂度降为 O(n*n)。
在有序或逆序的情况下最不利于发挥其长处。
度为 2 的树要求每个节点最多只能有两颗子树，并且至少有一个节点有两颗子树。
二叉树的要求是度不超过 2，就是说度也可以是 1 或者 0。
而且二叉树还有一个重要特点就是左右子树不一样，普通树不分左右子树。
5、。
6、三个的内排序方法:
7、三个的内排序:
8、如何根据拓扑排序方法判断一个有向图是否存在回路?
图中全部顶点都在相应的拓扑序列中，则相应图不存在环，否则存在。
9、一颗 h 层的 k 叉树最大结点数是 S = k n − 1 k − 1 S = \frac{k^n - 1}{ k - 1} S=k−1kn−1
10、求一个有向无环图的拓扑序列时，其结果为何不唯一?
在同一时刻可能有多个无前驱的订点，这时可选择任何一个输出。
11、在构造一个哈希表的过程中，简述如何用链地址法来解决冲突?
将所有关键字为同义词的记录存储在同一线性链表中
12、线性表，栈，队列，树，图各自的特点和使用场合?
线性表特点:
在非空的线性表，有且仅有一个开始结点，它没有直接前驱，而且仅有一个直接后继;
仅有一个终端结点，它没有直接后维，仅有一个前驱；
其余内部结点都有一个直接前驱和一个直接后继
栈:后进先出的结构，在cpu内部有提供栈这个机制，可以调用函数和返回。
栈限定在表尾进行插入和删除的线性表。
队:先进先出的结构，限定在表的一端进行插入， 在另一端进行删除的线性表。
树:非线性结构，点与点是一对多的关系，有父节点，孩子节点，兄弟节点。
图:非线性结构，点与点是多对多的关系，之间是平等的，没有父节点、兄弟、孩子之分。
计算机组成原理简答题:
1、有几种 I/o 控制方式?区别是什么?
程序查询：一种程序直接控制方式，这是主机与外设间进行信息交换的最简单方式，
输入和输出完全是通过 CPU 执行程序来完成。
程序中断：主机启动外设后，无须等待查询，外设在做好输入输出准备时，向主机发出中断请求
主机接到请求后就暂时中止原来执行的程序，转去执行中断服务程序对外部请求进行处理，
中断处理完毕后返回原来的程序继续执行。
DMA 方式：在主存和外设之间开辟直接的数据通路，可以进行基本上不需要 CPU 介入的主存和外设之间的信息传送。
通道：前两种更依赖于 CPU 中程序指令的执行。
2、窃取是指利用什么周期?
周期窃取又叫周期挪用：是指利用 CPU 不访问存储器的那些周期来实现 DMA 操作的
此时 DMA 可以使用总线而不用通知 CPU，也不会妨碍 CPU 的工作，
周期挪用并不减慢 CPU 的操作，但可能需要复杂的时序电路，
而且数据传送过程是不连续和不规则的。
DMA 方式中，DMA 控制器中的数据缓存器写满数据后，申请主存的总线控制权，
申请成功后，将缓存器中数据通过主线传给主存。这个过程中 CPU 一直在做自己的事情，
DMA 占据的只是贮存的一个存取周期，用来传输数据。
所以周期窃取是窃取的主存的一个至多个存取周期。
3、指令周期，机器周期，时钟周期，存储周期的关系和区别是?
指令周期：取出并执行一条指令的时间
总线周期：也就是一个访存储器或 I/O 端口操作所用的时间。
时钟周期：处理操作的基本单位，主频的倒数。是 CPU 中最小的时钟元素。
关系：一个指令周期由若干个总线周期组成，
而一个总线周期时间又包含有若干个时钟周期。
一个总线周期包含一个或多个机器周期。
4、CPU 的功能有哪些?
指令控制、操作控制、时间控制、数据加工、中断处理
5、写出微程序控制的原理图中各部位的功能?
控制存储器(CM)：微程序控制器的核心部件，用来存放微程序。
微指令寄存器(uIR)：用来存放 CM 中取出的微指令，它的位数同微指令字长相等。
微地址形成部件：用来产生初始微地址和后继微地址，以保证微指令的连续执行。
微地址寄存器(uMAR)：接受微地址形成部件送来的微地址，为在 CM 中读取微指令做准备。
6、时间局部性原理： 7、空间局部性原理： 这是因为程序中大部分指令是顺序存储、顺序执行的。 8、定点溢出的三种判断:
采用一个符号位: 当 X s = Y s = 0 , S s = 1 X_s=Y_s=0 , S_s=1 Xs=Ys=0,Ss=1时，产生正溢，当 X s = Y s = 1 , S s = 0 X_s=Y_s=1, S_s =0 Xs=Ys=1,Ss=0时产生负溢 溢出= X s ˉ Y s ˉ S s + X s Y s S s ˉ \bar{X_s}\bar{Y_s}S_s+X_sY_s\bar{S_s} XsˉYsˉSs+XsYsSsˉ
采用进位位: 两数运算时，产生的进位为 C s C 1 C 2 ⋅ ⋅ ⋅ C n C_sC_1C_2···C_n CsC1C2⋅⋅⋅Cn其中 C s C_s Cs为符号位产生的进位， C 1 C_1 C1为最高数值位产生的进位。 溢出= C s ˉ C 1 + C s C 1 ˉ = C s ⊕ C 1 \bar{C_s}C_1 +C_s\bar{C_1}=C_s\oplus C_1 CsˉC1+CsC1ˉ=Cs⊕C1
采用变形补码: 一个符号位只能表示正负两种情况，当产生溢出时，符号位的含义就会发生混乱。如 果将符号位扩充为两位( S s 1 和 S s 2 S_{s1}和S_{s2} Ss1和Ss2) 溢出= S s 1 ⊕ S s 2 S_{s1} \oplus S_{s2} Ss1⊕Ss2
9、如何在时间和空间两个层面区分指令和数据?
在指令周期的取指阶段中取出的是指令，在指令的执行阶段取出的是数据。
10、说明软件和硬件的特点，并解释说明两者的等价性并举出例子?
计算机的硬件和软件在逻辑上是等价的，
也就是说,由软件实现的操作，在原理上可以由硬件来实现，
同样，由硬件实现的许多操作在原理上也是可以由软件的模拟来实现。
例子:乘除法既能用乘除法实现，也可以在寄存器的支持下有程序实现。
控制器即可以由硬联逻辑实现，也可以由微程序实现。
11、DMA 的功能?什么是 DMA?
响应外设的请求，向 CPU 发出总线请求
DMA 应能接管总线控制权
获得控制权后要往地址总线发送地址信号
DMA 期间，应能发读写控制信号
DMA:直接依靠硬件在主存与 I/O 设备间进行直接的数据传送，在传送期间不需要 CPU 干预。
13、当指令系统和数据通路结构确定后，给出组合逻辑控制器的设计步骤?比较组合逻辑控制器和微程序控制器的特点?
步骤:
1)画出指令流程图，根据CPU数据通路和指令功能，排列出每条指令的微操作控制序列，
在不影响逻辑正确的原则下，尽量把共性的操作安排在相同的控制时序阶段中。
2)编排微操作时序表，根据指令流程图分解各操作为微操作，按时间列出机器应进行的微操作。
3)对微操作时序进行逻辑综合，化简。
4)电路实现。
比较:
组合逻辑控制型：其控制单元是由门电路组成的复杂树形网络，
优点：是速度快
缺点：是结构不规整，使得设计维修调试比较困难，难以实现设计自动化。
存储程序型：采用存储逻辑来实现，
也就是把微操作信号代码化，使得每条机器指令转化为一段微程序存入一个专门的存储器中，
微操作控制信号由微指令产生
优点：设计规整，调试维修以及更改扩充指令方便
缺点：是执行速度慢。
14、比较中断方式和 DMA 方式的特点?
DMA和中断的区别：
1.中断方式是程序切换，需要保护和回复现场，而DMA方式除了开始和结尾时，不占用CPU的任何资源。
2.对中断请求的响应只能发生在每条指令执行完毕时，而对DMA请求的响应可以发生在每个机器周期结束时。
3.中断传输过程需要CPU的干预，
而DMA传送过程不需要CPU的干预，故数据传送速率非常高，适合于高速外设的成组数据传送。
4.DMA请求的优先级高于中断请求。
5.中断方式具有对异常事件的处理能力，而DMA方式仅局限于完成传送信息块的具体IO操作。
15、简述层次存储系统中块表的组成和作用?中断屏蔽字的作用?
快表组成:虚页号、装入位、实页号
作用:存放慢表中较为常用的副本，提高访问页表的速度
中断屏蔽字作用:改变中断处理顺序。
16、集中刷新方式和分散刷新方式的区别?
1)集中刷新方式是在允许的最大刷新时间间隔内， 按照存储器芯片容量大小集中安持若干个刷新周期，刷新时停止读写操作。 分散刷新是把刷新操作分散到每个存储周期内进行， 此时系统的存取周期被分为两部分，前一部分进行读写操作或保持，后一部分进行刷新操作 2)集中刷新方式刷新周期等于存取周期， 分散刷新方式将存取周期分为两部分 3)集中刷新方式有死区 分散刷新方式没有死区
17、更新 cache 内容的替换算法有 FIFO 和 LRU，写出 LRU 的基本思想?
LRU 是把 CPU 最近最少使用的块作为被替换的块，
他需要随时记录 Cache 中各块的使用情况，以便确定那个块近期最少被使用
18、写出微指令编码方式的类型?
①直接译码法：操作控制字段的每一个独立的二进制位代表一个微命令，
该位为“1”表示这个微命令有效，为“0”表示无效。
这种方法结构简单，并行性强，操作速度快，
但微指令字太长，若微命令的总数为N个，则微指令字的操作控制字段就要有N位。
②最短编码法:将所有微命令统一编码， 每条微指令只定义一个微命令。
若微命令总数为N,操作控制字段的长度为L，则 L<=Log2N 这种方法同一时刻只能产生一个微命令，
不能充分利用机器硬件所具有的并行性，使得机器指令对应的微程序变得很长。
19、写出向量中断的响应方式?
当中断源向CPU发出中断请求信号之后，CPU进入一定的判优处理，
若决定响应，这个中断请求，则向中断源发出中断响应信号，
中断源接到信号后，就通过自己的向量地址形成部件向CPU发送向量地址，
CPU接收该向量地址之后可转入相应的中断服务程序。
11、I/O 接口指什么?应具有哪四种功能?
主机与外围设备或其他外部系统之间的接口逻辑
功能: 寻址 ; 数据传送与缓冲数据格式变换 ; 电平变换等预处理 ; 控制逻辑
12、什么是中断?写出中断响应的过程?
中断:在计算机运行过程中，如果发生某种随机事态，CPU将暂停执行现行程序，
转去执行中断处理程序，并在服务完毕后自动回复原程序的执行。
过程:当有外部中断请求时， CPU若满足中断是允许的，该中断级别最高，并且在一条指令执行完毕的情况下，
相应中断即暂停当前执行的程序，并关闭中断，
将中断处理程序的入口地址送入PC,进入终端处理程序后，保存断电，
在中断处理程序的最后安排一条中断返回指令，
当中断处理程序执行完毕后，该指令按照PC内容恢复PC,从而返回被中断的程序继续执行。
13、叙述冯。诺依曼体制计算机的特点?
采用二进制形式表示数据和指令。
由控制器、运算器、存储器、输入、输出五大部分组成。
14、说明高速缓存、虚拟存储器的功能以及他们在存储体系的位置?
Cache:主要解决 CPU 与主存速度匹配问题，位于 CPU 与主存之间
虚拟存储器:解决存储容量问题，位于内存和外存之间。
15、说明静态存储器和动态存储器在使用时的主要区别?
静态存储器：存取速度快，但集成度低，功耗也大，一般用来组成高速缓冲存储器和小容量内存
动态存储器：集成度高，功耗小，但存取速度慢，一般用来组成大容量内存。
历年
2021
- CPU的四个主要功能是：
- CPU相应中断时需要保存当前现场，这里的现场指的是寄存器和寄存器的内容，他们被保存到中
- 在小数定点机中采用一位符号位，若寄存器内容为1000 0000，当他分别表示为原码、补码、反码时，其对应的真值分别是
- 在组合逻辑控制器中微操作控制信号由决定
- 有二进制D4 D3 D2 D1，奇校验码P=_________，偶校验码 P = D 4 ⊕ D 3 ⊕ D 2 ⊕ D 1 P=D4\oplus D3\oplus D2\oplus D1 P=D4⊕D3⊕D2⊕D1，奇校验码只能检验，无法检测
- 一个较完善的指令系统，应当由类指令
- 设由S、E、M三个域组成的一个32位二进制字所表示的非零规格化数X，真值表示为 X = ( − 1 ) S ∗ ( 1. M ) ∗ 2 E − 128 X=(-1)^S*(1.M)*2^{E-128} X=(−1)S∗(1.M)∗2E−128。他所能表示的规格化最大正数是 [ 1 + ( 1 − 2 − 23 ) ] ∗ 2 127 [1+(1-2^{-23})]*2^{127} [1+(1−2−23)]∗2127，规格化最大正数是