[嵌入式]USTB871(DS+CO)

填空题:

1. 计算机系统由硬件和软件两大部分组成。
2. CPU 是运算器和控制器的总称。
3. 总线结构的计算机系统中，总线一般是由地址总线，数据总线，控制总线三大部分组成。
4. 通过执行转移类的指令，可以设计程序计数器的内容。
5. 当指令的形式地址给出操作数所在的存储器单元的地址存放的寄存器时，该种寻址方式为间接寻址。
6. 计算机能处理的语言是机器语言，编程用的语言中最接近机器语言得是汇编语言
7. N 个 cache 块，在组相连映射中，当组数为 n 和组数为 1 时分别变为 直接映射 和 全相连映射
8. 一组微命令构成微指令进而构成微程序
9. 半导体随机存储器中SRAM的原理是双稳态触发器，DRAM的原理是利用存储元电路中栅极电容上的电荷。SRAM 的速度比DRAM 快，但集成度 不如DRAM 高
10. 定点加法运算器中无论采用双符号位还是单符号位，必须有溢出判断电路，用异或门来实现。
11. I/O 设备编制方式有统一编制和独立编制。
12. I/O 有程序查询方式、中断方式、和 DMA 方式。
13. CPU 控制器有微程序控制器和组合逻辑控制器。
14. 浮点数的阶码和位数分别决定了浮点数的范围和精度。
15. 程序员可以操作的地址叫逻辑地址，CPU真正访问的地址叫物理地址。
16. 同步方式是用统一时钟来标记时间，异步方式是用应答方式来标记时间。
17. 微程序控制器的核心部件是控制存储器，它一般用只读存储器构成。
18. CPU 的功能主要是解释计算机指令和处理计算机软件中的数据。
19. CPU 的四大作用分别是处理指令，执行操作，控制时间，处理数据。
20. DMA 的功能:响应外设的请求，向 Cpu 发出总线请求信号；DMA 应能接管总线控制权 ；获得控制权后要往地址总线发送地址信号 ；DMA 期间，应能发读写控制信号
21. 保护断点时保存的是PS和PSW。
22. 在指令周期的取指阶段中取出的是指令，在指令的执行阶段取出的是数据。
23. 存储系统中CPU能直接访问主存和cache，但不能直接访问磁盘和光盘。
24. 中断周期前的CPU工作周期是执行周期，中断中期后的CPU工作周期是取指周期
25. 移码表示法主要用于表示浮点数阶码，以利于在加减运算的对阶操作中比较大小。
26. 寄存器间接寻址方式中，操作数存放在主存，寄存器中存放的是操作数地址
27. CPU 从内存取出一条指令并执行这条指令的时间称为指令周期。
28. 微程序的微指令是指控制存储器中的一个单元的内容。
29. 当前正在执行的指令保存在CPU的指令寄存器中，运算结果等状态标志保存在CPU的状态标志寄存器中。
30. 组合逻辑控制器所采用的三级时序是指机器周期、节指、和脉冲等三级。
31. 提高加法器运算速度的关键是减少进位延迟时间。
32. 减法可以和加法使用同一部件的关键是计算机采用数据的补码形式进行运算
33. 采用扩展操作码技术的目的是既能充分利用指令的各个字段，又能在不增长指令长度的 情况下，扩展操作码位数
34. 在浮点数表示方法中：阶码表示浮点数的表示范围，解码位数越多，该浮点数表示的范围越大。
35. 中断响应过程中，保护程序计数器PC的作用是保证在中断服务程序执行完毕后能正确返回原来的程序。
36. 构成控制信号序列的最小单位是微命令。
37. 数字计算机硬件由五大部分组成，即存储器、运算器、控制器、输入设备和输出设备。
38. 程序计数器PC，一直指示着程序的当前执行的指令，也就是指示控制流的形成
39. 微程序在逻辑功能上讲，它属于硬件的范畴。
40. 总线的数据通路宽度指能一次并行传送的数据位数。
41. 冯诺依曼体质思想的核心是采用存储程序方式，它是将指令存储器和数据存储器合并在一起的存储器结构。
42. 计算机的硬软件在功能上的等价是指同一种功能可以由软件来实现也可以由硬件实现。
43. 计算机总线按任务可分为四种CPU内部总线、部件内总线、系统内总线、外总线。
44. 机器数是指在计算机中使用的连同符号位一起数码化的数据表示形式。
45. DMA 传送方式中的周期挪用方式是当 DMA 请求并获得 CPU 批准后，CPU 让出一个周期 的控制权，由 DMA 控制器控制系统总线，挪用一个存取周期进行这数据传送，传送一个字节或一个字，然后 DMA 控制器将总线控制权交回 CPU。(相应 DMA 请求后，CPU 暂停执行程序下个周期，在这一个 DMA 周期中实现 DMA 传送)
46. 动态存储器的刷新可归纳为集中式、分散式、异步式
47. 微程序中的微命令是指构成控制信号序列的最小单位。
48. 微指令的编码方式有直接控制法、分段直接编译法、分段间接编译法。
49. 指令的寻址方式是指令如何提供提供操作数和操作地址。
50. 立即寻址的操作数是由指令的地址段给出
51. 运算器的基本功能是进行算术运算和逻辑运算
52. PROM 是指一次编程写入存储器
53. EPROM 是指多次紫线可擦除可写入只读存储器

数据结构简答题:

1、如果一个序列基本有序那么用什么交换排序比较有效?

直接插入排序。当序列基本有序时，效率最高的排序算法是插入排序，其次是冒泡排序。

2、拓扑排序和关键路径能够解决什么问题?(拓扑排序的功能和应用场景)

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。

例如:在日常工作中，可能会将项目拆分成 A、B、C、D 四个子部分来完成，但 A 依赖 于 B 和 C，C 依赖于 D。
为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，
则排在前面的任务就是需要先完成的任务。

关键路径通常是决定项目工期的进度活动序列。
它是项目中最长的路径，即使很小的浮 动也可能直接影响整个项目的最早完成时间。
关键路径的工期决定了整个项目的工期，
任何关键路径上的终端元素的延迟在浮动时间为 0 或负数时将直接影响项目的预期完成时间。

3、简述快速排序的原理?什么情况下不适合用快速排序?

原理:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可 以递归进行，以此达到整个数据变成有序序列。
快速排序的优点在于平均性能好，缺点在于初始序列有序或基本有序时，其时间复杂度降为 O(n*n)。
在有序或逆序的情况下最不利于发挥其长处。

4、一颗二叉树和一颗度为 2 的树的区别?

度为 2 的树要求每个节点最多只能有两颗子树，并且至少有一个节点有两颗子树。

二叉树的要求是度不超过 2，就是说度也可以是 1 或者 0。
	而且二叉树还有一个重要特点就是左右子树不一样，普通树不分左右子树。

5、直接选择排序的时间复杂度永远是 O(n*n)。

6、三个稳定的内排序方法:直接插入、选择、起泡排序

7、三个不稳定的内排序:希尔、快速、堆排序

8、如何根据拓扑排序方法判断一个有向图是否存在回路?

图中全部顶点都在相应的拓扑序列中，则相应图不存在环，否则存在。 

9、一颗 h 层的 k 叉树最大结点数是 $S=\frac{k^n?1}{k?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=1,S_s=0$时产生负溢
溢出=$\overline{X_s}\overline{Y_s}{S}_s+X_s{Y}_s\overline{S_s}$

采用进位位:
两数运算时，产生的进位为$C_s{C}_1{C}_2???C_n$其中$C_s$为符号位产生的进位，$C_1$为最高数值位产生的进位。
溢出=$\overline{C_s}{C}_1+C_s\overline{C_1}=C_s\oplus C_1$

采用变形补码:
一个符号位只能表示正负两种情况，当产生溢出时，符号位的含义就会发生混乱。如
果将符号位扩充为两位($S_{s1}和S_{s2}$)
溢出=$S_{s1}\oplus S_{s2}$

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、说明静态存储器和动态存储器在使用时的主要区别?

静态存储器：存取速度快，但集成度低，功耗也大，一般用来组成高速缓冲存储器和小容量内存
动态存储器：集成度高，功耗小，但存取速度慢，一般用来组成大容量内存。