数据结构考试复习提要及习题(全).doc

第1章复习提要及习题【复习提要】1、 冯.诺依曼对计算机研究的贡献与影响。2、 计算机系统的组成及各部件功能。3、 计算机体系结构的定义，层次性，与计算机组成、计算机实现的关系。4、 计算机硬件与软件逻辑功能的等价性。5、 计算机的性能指标。6、 加快计算机性能指标的原则。【复习提要】 一、选择题 1.计算机按“存储程序，逐条执行” 方式进行工作，这一方案是由（ B ）提出。 A.图灵 B. 冯.诺依曼 C.杨振宁 D.康托尔 2.下列观点不是冯.诺依曼提出的是（ C ）A.程序和信息采用二进制存储 B. 存储程序，逐条执行C.问题的可计算性 D.计算机由运算器、控制器等五大部件组成 3.CPU不包括（ D ）A.运算器 B.总线 C.寄存器 D.存储器 4.下列说法正确的是（ A ）A.控制器由指令控制部件、地址形成部件、定时部件及微操作部件等组成。B.PC寄存器称为程序计数器，存放当前执行的指令。下一条指令的地址C.IR为指令寄存器，其功能是译码产生相应的控制信号。保存当前正在执行的指令D.微操作就是计算机执行一条指令所完成的操作。计算机各部件在一个节拍能完成的基本操作 5.计算机体系结构是指（ C ）A.计算机系统的逻辑实现。 B.计算机组成的物理实现C.程序员所看到的计算机属性，即概念性结构和功能特性。D.计算机的基本构成和工作原理。 6.“如何实现计算机系统结构所体现的属性”是（ B ）探讨的范围。A.计算机体系结构 B.计算机组成 C.计算机实现 D.计算机原理 7.经典意义上的计算机体系结构是指（ A ）看到的计算机属性。 A.机器语言程序员 B.C语言程序员 C.高级程序设计员 D.普通人员二、填空题 1.冯氏计算机的工作原理是 “存储程序，然后逐条执行” 。2.计算机系统由 硬件 系统和 软件 系统构成。3.计算机硬件系统包括：控制器 、 运算器 、 存储器 、输入输出设备 和 输入设备 。4.运算器能完成的运算有 算术运算 和 逻辑运算 。5.计算机的主要性能指标有 机器字长 、 存储容量 和 运算速度 。6.改进计算机性能指标的基本原则有 大概率事件优先原则 、 程序局部性原理 和 Amdahl定律 。7.计算机实现是指 计算机组成的物理实现 。三、简答题1、 如何理解软硬件之间的等效性？ 计算机系统的功能由硬件或软件实现，在逻辑功能上是等价的。换言之，用硬件实现的功能，在原理上可以用软件来实现；同样，用软件实现的功能，在原理上也可以由硬件来完成。2、如何理解计算机体系结构的层次性，经典意义上的计算机体系结构涉及那些内容？ 第六级：应用语言虚拟机第五级：高级语言虚拟机第四级：汇编语言虚拟机第三级：操作系统虚拟机第二级：机器语言（传统机器）第一级：机器语言（微程序机器）经典意义上的计算机体系结构包括：数据表示、寻址规则、寄存器定义、指令集、中断系统、机器工作状态定义和切换、存储系统、信息保护、I/O结构等。3、 如何理解程序局部性原理？ P12 程序局部性原理包括时间局部性和空间局部性。时间局部性是指计算机访问过的程序在不久的将来有可能又可能再次被访问；空间局部性是指计算机访问的地址空间往往是局限在一块地址连续的区域内第2章 复习提要与习题【复习提要】1、 定点符号数的表示2、 浮点数的表示3、 计算机的指令格式4、 常见寻址方式及原理5、 指令格式设计方式6、 复杂指令计算机与精简指令计算机【复习提要】 一、选择题1、指令 MOV AX，（BX）中，源操作数的寻址方式为（ C ） A.立即寻址 B.直接寻址 C.间接寻址 D.变址寻址2.指令，MOV AX，（BX）中，源操作数在（ B ） A.寄存器 B.内存单元 C.立即数 D.Cache3.二、填空题1.数据在计算机中的表示可分为 定点表示 和 浮点 表示。2.向量具有三种属性，它们是： 起始地址 、 向量长度 和 向量间距 。3.计算机指令由 操作码 和 操作数 组成，其中前者指明计算机将要执行的任务，后者是要处理对象的来源。4.长度为计算机字长一半的指令称为 半字长指令 。5.按CPU内部存储单元类型分类，计算机指令集合结构可分为 堆栈型指令结构 、 累加器型指令结构 和 通用寄存器型指令集结构。通用寄存器型机器可分为 寄存器寄存器型 、 寄存器存储器型 和 存储器-存储器型。6.所谓的寻址技术是指从形式地址 产生 有效地址 的方法。7.指令MOV （AX），2000H 的源操作数和目的操作数的寻址方式分别是 立即数寻址 、 寄存器间接寻址 。三、简答题 1、精简指令计算机系统和复杂指令计算机系统有什么区别？P47P49与CISC结构比较，RISC结构的主要优点有：1、 充分利用了VLSI芯片的面积2、 提高了机器的运算速度3、 易于设计，实现成本降低，提高了可靠性4、 对高级语言的支持第3章 复习提要及习题【复习提要】1、 数值与数值转换2、 数的机器表示：原码、反码、补码和移码3、 补码加减法运算电路及运算4、 一位补码乘法运算5、 补码浮点数的加法运算6、 控制器的实现原理7、 流水线的基本思想和特点8、 流水线的相关性与解决方式。【复习提要】一、选择题1.100010001.01 与下列（ C）等价。A.237.25 B.111.1H C.111.4 D.273.4H2.下列不是机内码的是（ D ） A.原码 B.补码 C.移码 D.二进位码3.-3的补码是（ D ） A.7CH B.83H C.0FCH D。0FDH 4.下列用来存放当前正在执行的指令的是( D ) A.MAR B.MDR C.PC D.IR5.下列流水线中,”堵塞”与”断流”并存的是( D )6.关于流水线相关性,下列说法正确的是（ A ）. A.流水线相关主要分为结构性相关、数据相关和控制相关。 B.为解决数据相关，通常可以通过把的指令cache和数据cache分离的方式得以解决。 C.控制相关可进一步分为写后读相关、写后写相关和读后写相关。 D. 产生结构相关的原因是PC寄存器冲突。二、填空题1.数据在计算机内部的表示称为 机器数 ，有符号数在计算机通常用 补 码表示。2.-27的补码是 E5 H，移码是 65 H。3.微指令 P：AAB 表示 逻辑或微操作，P=1时，A、B两个寄存器对应位实现逻辑或微操作，结果送A寄存器 。4.为提高浮点数的精度，通常需要对浮点数进行 规格化 。5.浮点数加法运算的步骤通常为： 判零 、 对阶 、 求和 、 规格化 和舍入。6.在异步控制方式中，部件之间通信协调通过 咨询应答 。7.在同步时钟控制系统中，部件之间的控制与通信是在相同的 时钟周期 控制下完成。8控制器中的各部件必须能相互协调，控制器对这些器件之间的协调可采用 同步 和 异步 方式。9.控制器对指令译码产生控制时序信号的方式有 组合电路控制方式 和 微程序控制方式。 10. 流水线相关主要分为 结构相关 、 数据相关 和控制相关。三、简答题1.下图为什么电路？试叙述其工作原理。此电路为补码加减法运算电路，电路有一个半加器，若干个全加器和若干个异或门组成，M为加减法控制器，当M=0是【B】补与0异或仍为【B】补 所以电路执行【A】补+【B】补=【A+B】补 为加法运算器；当M=1时，【B】补与1异或得【-B】补，电路执行【A】补+【-B】补=【A-B】补，为减法运算器2.CPU有那些功能？试画出其结构图并进行说明。3.什么是流水线相关？流水线相关的种类及其主要处理方法有哪些？流水线技术可以提高处理的效率，但这也有可以避免种类：结构相关、数据相关、控制相关处理方法：结构相关采用流水化功能单元的方法或资源重复的方法数据相关采用定向(旁路或短路)的简单技术来解决控制相关“冻结”(freeze)或“排空”(flush)流水线方法四、计算题1、 已知 X=-44，Y=-53， 求 X+Y补和 X-Y补 X=-00101100 y=-00110101x补=11010100 y补=11001011 -y补=00110101x+y补=10011111 x-y补=000010012、 已知 X=0.625，Y=-0.5625， 用双符号位法求 X+Y补并判断有无溢出。X=0.101 Y=-0.1001X补=00.101 Y补=11.0111X+Y补=00.0001双符号位相同，结果正常3、 已知X补=0.1101，Y补=1.0101，按一位补码乘法运算方式计算（XY）补的值。（写出计算过程）4、 已知X=2010.1101，Y=211（-0.1010），求X+Y的值。（其中阶码为4位二进制真值，包含阶符；尾数为7位二进制真值，包含尾符）第4 复习提要及习题【复习提要】1. 存储器的分类与特点。2. 存储器的层次性结构及其实现原理。3. cache的结构与工作原理4. cache的置换算法与地址映像规则。5. cache的数据一致性问题6. cache的效率分析7. 主存的结构及功能8. 内存的扩展技术。9. 虚拟存储器的目的与原理。【复习提要】一、选择题 1.下列说法中，不正确的是（ C ）A.按存储介质，存储器可分为半导体存储器、磁表面存储器、磁芯存储器和光盘存储器。B.按访问方式，存储器可分为随机存储器、只读存储器和顺序存储器。C.所有的半导体存储器都属于易失性存储器。D.RAM可分为静态RAM 和动态RAM，其中动态RAM需要定期刷新。 2.关于存储系统的层次结构说法正确的是（ B ）A.层次性结构主要指“寄存器主存”和“主存辅助存储器”两级结构。B.Cache的引入是为了加快CPU对存储器的访问速度。C.虚拟存储器的主要目的是加快提高系统吞吐量。D.可以直接建立“cache辅助存储器”的层次关系。 3.已知一存储系统提供34根地址线，如果按字节编址，则该存储系统的最大存储容量可为（ D ）A.34MB B.34GB C.4GB .D.16GB4.有一容量为1MB容量的存储器，字长为32位，如果按半字进行编址，则地址寄存器、数据寄存器各为多少位？（ C ） A.20，8 B.16，16 C.19，16 D.18，325.要构造一个容量为16K32位的存储器，可如下选择芯片（ B ）。 A. 8片4K4 B.32片16K1 C.4片4K8 D.56片1K4二、填空题 1.在存储系统中，离运算器最近的是 寄存器 。 2.引入Cache的目的是 加快CUP对存储器的访问速度 ，Cache引入的直指导理论是 程序局部性原理 ，引入虚拟存储器的目的是 扩大存储空间 。 3.Cache的映像规则有 直接映像 、 全相联映像 和 组相联映像 。 4.存储容量的扩展方式有 位扩展 、 字扩展 和 字位扩展 。 5存储芯片的译码方式有 线选法 、 全译码 和 局部译码 。三、简答题 1.简述Cache的原理。当CPU访问数据时，先在Cache中查找数据，如果找到（命中），则直接访问数据；如果找不到，则到主存储器中去查找，并根据一定的置换算法 将数据读到cache中，然后在访问数据，被调入的数据继续保存在cache中，等待下一依次访问，（对于写操作，必须保证cache一致性）。 2.Cache置换主要有那些算法？试述各算法的置换原理。1、随机置换为了均匀使用一组中的各块，这种方法随机的选择被替换的块2、先进先出置换选择最早调入的块作为被替换的块3、最近最久未使用优先置换选择最久没有被访问过的块作为被替换的块四、计算题 1.已知CPU访问存储器的周期为20ns，访问Cache的周期为5ns，系统采用LRU置换算法，其中Cache页面数n=5，现有如下页面地址流：2，1，3，1，4，2，5，3，2，1，2，3，4，1，5计算cache的命中率和性能比。五、应用题1、设CPU提供16位地址线，8位数据线，（低电平有效）为访问控制信号，为读/写控制信号，现有可选ROM芯片：2K8Bit、4K4bit、8K8bit；RAM芯片1K4Bit、2K8bit、4K8bit和74138（3-6译码器），要求设计一存储系统，使系统程序区占用低4K地址空间，用户程序区占用4096-16383地址范围。（1）试指出系统应选择的芯片类型及数量。解：根据题意，系统要求构造一个16KB的存储系统，其中，ROM为4KB，占用低地址，RAM为12KB，占用高地址。 如果选用2K8Bit的ROM，则需要2片，片内地址为11根； 如果选用4K4Bit的ROM，则需要2片，片内地址为12根； 8K8bit的ROM不符合要求，不能使用。 如果选用1K4Bit的RAM，则需要24片，片内地址为10根；如果选用2K8Bit的RAM，则需要6片，片内地址为11根；如果选用4K8bit的RAM，则需要3片，片内地址为12根；由此，可有两种选择方案：（1）选用2片2K8Bit的ROM和6片2K8Bit的RAM。（2）选用2片4K4Bit的ROM和3片4K8bit的RAM。（2）画出系统的逻辑连线图。现选用方案（2），其连接电路如下ROM1ROM2D7d4D3D0ram1ram2ram33-8D7D0第5 章 复习提要及习题 【复习提要】10. 标量处理机与向量处理机对向量数据醋栗的区别11. 。向量处理的方式及特点。12.【复习提要】一、选择题 1. 下列说法正确的是( C ).A.专门处理向量数据的处理机称为向量处理机.B.标量处理机不能处理向量数据.C.向量处理机中，CPU数据带宽统称为存储带宽的1/3D.要处理向量数据，向量处理机必须设置向量寄存器。二、填空题1.向量处理的方法有 横向处理方式 、 纵向处理方式 和 纵横处理方式 。第7 章 复习提要及习题【复习提要】13. 并行性的定义14. 并行计算的实现方法15. 并行处理机的结构类型【复习提要】一、选择题 1下列说法正确的是（ D ）。A 并行性分同时性并行和并发性并行，其中并发性并行要求采用重复资源结构。B 在并发实现技术中，分时系统属于时间重叠型；分布式系统属于资源重复型。C 向量处理机也属于并行处理，它采用资源重复技术得以实现。D 多处理机和机群技术多属于资源重复型的并行处理系统。二、填空题1 并行技术有 资源重复 、 时间重复 和 资源共享 三种实现方式。2并行处理机可分为 分布存储器并行处理机 和 共享存储并行处理机 两种基本结构。3并行处理机主要用于高速 向量 和 矩阵 运算。三、简答题1 向量处理机与并行处理机有什么区别？并行处理机依靠的并行措施主要是资源重复，而不像向量机是时间的重叠并行处理机使用的多处理单元通过互联网络连接在一起第8 章 复习提要及习题【复习提要】16.【复习提要】一、选择题 1下列属于时间重叠型并行性的是（ A ）E 向量处理机 B并行处理机 C多处理机系统 D机群系统2按富林克兰分类法，下列属于SIMD的是（ B ） A向量处理机 B并行处理机 C多处理机系统 D机群系统3下列资源重复建立在CPU级别上的是（ C ）A向量处理机 B并行处理机 C多处理机系统 D机群系统二、填空题1按系统的耦合紧密程度，机群系统属于 松散耦合 型多处理系统。SMP系统为 对称 型多处理系统。2解决并行处理机中的Cache一致性问题可采用的方法有：一、 监听高速缓存一致性协议 ，二、 基于目录的协议 。第9章 复习提要及习题【复习提要】1、 接口电路引入的原因。2、 接口电路的作用。3、 输入输出系统的特点。4、 基本输入输出方式的原理与特点。5、 中断系统的构成，中断系统的工作原理，工作响应过程。6、 直接存储存取（DM）方式的原理、过程与特点。7、 通道处理机的工作原理、类型及工作方式。8、 输入输出处理机的原理与特点9、 总线的作用、分类。【复习提要】一、 选择题1、以下不是引入接口电路原因的是（ D ） A.CPU与外设速度不匹配 B.负载不匹配 C.数据格式与电平逻辑不匹配 D.设备类型不匹配2、为使CPU与外设速度匹配，通常接口电路要设置（B ） A.频率加速器 B.暂存缓冲区 C.功率放大部件 D.A/D转换部件3、下列输入输出方式中，CPU效率最低的是（ A ） A.查询方式 B.中断方式 C.DMA方式 D.通道方式4.下列输入输出方式中，CPU不参与数据传输的是（D ） A.直接方式 B.查询方式 C.中断方式 D.DMA方式5. 输入输出方式中，CPU运行与外设到存储器之间数据传输可并发执行（D ） A.查询方式 B.中断方式 C.DMA方式 D.通道方式7.下面是输入输出处理机具有的特性或功能的是（C ） A.数据格式转换和数据校验由CPU完成。 B.具有文件管理功能。 C.接受来自CPU的程序，并由CPU激活。 D.对自身处理自身的故障。二、 填空题1.解决CPU与外设之间的速度匹配的有效办法是在接口上设置 端口寄存器 。2.输入输出系统具有：异步性 、 实时性 和设备无关的特点。3.基本的输入输出方式有直接输入输出方式 、 查询方式 、 中断方式 和DMA方式。4.中断源的识别方法有 软件查询法 和 硬件菊花链法 。5.利用DAM方式传输数据时，总线控制权由 DMA 控制，数据传输完毕后，总线控制权交还 CPU 。6.通道可分为： 字节多路通道 、 选择通道 和数组多路通道。7.总线按位置级别可分为： 内部总线 、 系统总线 和外部总线。按传输的数据类型可分为： 数据总线 、 地址总线 和控制总线。8.总线的连接方式有：单总线结构 、 双总线结构 和三总线方式。9.屏蔽中断的方法有: 设置中断屏蔽标志位 和 改变处理机优先 两种方法.三、 简答题1、 主机与外设之间的连接为什么要设置借口电路？为解1、速度不匹配 2、时序不匹配 3、信息格式不匹配 4、信息类型与电平不匹配 这四种问题，实现主机与外设之间的通信，必须使用接口设备2、 接口电路的功能是什么？即I/O接口电路的功能1、为计算机提供输入输出通道2、缓冲、暂存信息、，协调主机与外设之间的数据传送3、实现主机与外设的信息匹配3、 计算机与外设的数据交换有哪些方式？各自的工作原理和特点是什么？方式：直接方式 、查询方式 、 中断方式、 DMA通道方式、 输入输出处理方式原理及特点：直接方式在需要进行输入输出操作时，直接（无条件）用输入输出指令进行输入输出操作。查询方式在需要进行输入输出操作前，先从特定端口中读取数据信息，了解外围设备转台信息（这一过程称为检测），在条件具备时才通过执行输入输出指令进行输入输出操作，检测过程往往是循环进行的。 特点：电路简单；CPU以独占方式工作，利用率低中断方式系统使用中断控制器件。当外部设备已经准备就绪或系统需要进行I/O时，由中断控制器向系统提出请求，系统根据情况响应，暂时停止当前任务，转二执行输入输出请求，待I/O结束，再继续原来的工作。 特点：电路复杂；CPU以被动形式响应，利用率高DMA通道方式系统设置专门的输入输出硬件器件，负责I/O工作，系统需要进行I/O时，DMAC向CPU提出中断请求，CPU响应后，把系统总线控制全交给DMAC，（此时CPU不能工作），DMAC拿到BUS控制权后，利用总线进行高速的数据传输，直到数据传输完毕才把BUS控制权交换CPU（CPU才开始工作）。 特点：电路复杂； CPU不参与数据传输，数据传输速度快，适合大批量数据传输。输入输出处理方式系统设置有能够独立工作输入输出处理机，在系统启动时，由CPU激活输入输出处理机，之后输入输出处理机便可以独立的进行I/O工作，不再需要CPU的支持与控制。 特点：电路复杂； CPU不参与数据传输，输入输出处理机能独立完成工作，CPU与输入输出处理机可并行处理任务，系统吞吐量大。4、 中断系统由哪些部分组成？A 中断源 B 中断控制器 C 中断向量表 D 中断服务子程序5、 中断方式的工作原理如何？有什么特点？6、 简述中断响应的过程。 接受中断请求信号 计算中断类型号判断中断优先级和中断控制允许位计算中断服务程序地址保留现场执行中断服务子程序恢复现场返回主程序 7、 屏蔽中断有什么作用? （1）改变中断源的中断服务顺序。（2）决定设备是否采用中断方式工作。（3）在多处理机系统中，不对外围设备的服务分配到不同处理机中。 8、 DMA方式的工作原理如何？有什么特点？ 系统需要进行I/O时，DMAC向CPU提出中断请求，CPU响应后，把系统总线控制全交给DMAC，（此时CP