[计算机类试卷]原国家四级笔试章节练习试卷6及答案与解析.doc

《[计算机类试卷]原国家四级笔试章节练习试卷6及答案与解析.doc》由会员分享，可在线阅读，更多相关《[计算机类试卷]原国家四级笔试章节练习试卷6及答案与解析.doc（24页珍藏版）》请在麦多课文档分享上搜索。

1、原国家四级笔试章节练习试卷 6及答案与解析 1 对包含 n个元素的散列表进行检索，平均检索长度为 ( )。 （ A）不直接依赖于 n （ B） O(n2) （ C） O(n) （ D） O(log2n) 2 栈 S最多能容纳 4个元素。现有 6个元素按 1， 2， 3， 4， 5， 6的顺序进栈，则下列哪一个序列是可能的出栈序列 ?( ) （ A） 5， 4， 3， 2， 1， 6 （ B） 2， 3， 5， 6， 1， 4 （ C） 3， 2， 5， 4， 1， 6 （ D） 1， 4， 6， 5， 2， 3 3 用链接方式存储的队列，在进行删除运算时，下面操作 正确的是 ( )。 （ A）

2、仅修改头指针 （ B）仅修改尾指针 （ C）头、尾指针都要修改 （ D）头、尾指针可能都要修改 4 设仅包含根结点的二叉树的高度为 0，则高度为 k的二叉树的最大结点数为( )。 （ A） 2k+1 （ B） 2k+1-1 （ C） 2k+1+1 （ D） 2k+1 5 下列关于二叉树周游的叙述中，正确的是 ( )。 （ A）若一个结点是某二叉树的后序最后一个结点，则它必是该二叉树的根结点 （ B）若一个结点是某二叉树的前序最后一个结点，则它必是该二叉树的中序最后一个结 点 （ C）若一个结点是某二叉树的中序最后一个结点，则它必是该二叉树的前序最后一个结点 （ D）若一个树叶是某二叉树的前序最

3、后一个结点，则它必是该二叉树的中序最后一个结点 6 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是 ( )。 （ A）直接插入排序 （ B）堆排序 （ C）二路归并排序 （ D）起泡排序 7 下面序列是堆的是 ( )。 （ A） 97， 56， 38， 66， 23， 42， 12 （ B） 23， 86， 48， ?3， 35， 39， 42 （ C） 05， 56， 20， 23， 40， 38， 29 （ D） 05， 23， 16， 68， 94， 72， 71， 73 8 下面关于有向图的叙述中，哪个 (些 )是正确的 ?( ) 求有向图结点的拓扑序列，其结果必定是惟一的

4、 求两个指向结点间的最短路径，其结果必定是惟一的 求事件结点网络的关键路径，其结果必定是惟一的 （ A）只有 （ B） 和 （ C）都正确 （ D）都不正确 9 对以下序列 22， 86， 19， 49， 12， 30， 65， 35， 18进行排序，排序过程如下： (1) 22， 86， 19， 49， 12， 30， 65， 35， 18 (2) 18， 12， 19， 22， 49， 30， 65， 35， 86 (3) 12， 18， 19， 22， 35， 30， 49， 65， 86 (4) 12， 18， 19， 22， 30， 35， 49， 65， 86 则可以认为使用了 (

5、 )排序方法。 （ A）选择排序 （ B）起泡排序 （ C）快速排序 （ D）插入排序 10 用堆排序方法，最坏情况下，所需时间为 ( )。 （ A） O(n) （ B） O(n2) （ C） O(log2n) （ D） O(nlog2n) 11 若二叉树前序周游访问结点顺序为 ABCDEFG，中序周游访问结点顺序为CBDAFGE，则其后序周游访问结点顺序为 ( )。 （ A） CDBAGFE （ B） CDBGFEA （ C） CDBFAGE （ D） CDGFEAB 12 图的广度优先周游类似于树的 ( )。 （ A）先序遍历 （ B）中序遍历 （ C）按层遍历 （ D）后序遍历 13 一

6、个序列中有若干个元素，若只想得到其中第 i个元素之前的部分排序，最好采用什么排序方法 ?( ) （ A）起泡排序 （ B）堆 排序 （ C）插入排序 （ D）归并排序 14 在二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序( )。 （ A）完全相同 （ B）都不相同 （ C）先序和中序相同，而与后序不同 （ D）中序和后序相同，而与先序不同 15 二叉排序树的平均检索长度为 ( )。 （ A） O(n) （ B） O(n2) （ C） O(log2n) （ D） O(n log2n) 16 设有 100个结点，用二分法查找时，最大比较次数是 ( )。 （ A） 25 （ B

7、） 50 （ C） 10 （ D） 7 17 下面的二叉树， ( )是完全二叉树。 （ A） （ B） （ C） （ D） 18 设散列表的存储空间大小为 19，所用散列函数为 H(key) key mod 19，用开地址线性探查法解决碰撞。散列表的当前状态如下： 现要将关键码值 75插入到该散列表中，其地址应为 ( )。 （ A） 0 （ B） 11 （ C） 15 （ D） 17 19 以下 ( )不是队列的基本运算。 （ A）从队尾插入一个新元素 （ B）从队列中删除第 i个元素 （ C）判断一个队列是否为空 （ D）读 取队头元素的值 20 对线性表进行二分法查找，其前提条件是 ( )

8、。 （ A）线性表以顺序方式存储，并且按关键码值排好序 （ B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 （ C）线性表以链接方式存储，并且按关键码值排好序 （ D）线性表以链接方式存储，并且按关键码值的检索频率排好序 21 有向图 G(下图 )的结点可以排成 ( )个不同的拓扑序列。（ A） 3 （ B） 5 （ C） 7 （ D） 9 22 下面哪种情况用直接插入排序方法进行由小到大排序，元素比较次数最少 ?( ) （ A）元素的关键码值按由小到大排列 （ B）元素的关键码值按由大到小排列 （ C）部分元素按由小到大排列 （ D）元素任意排放 23 如下图 G，它的拓扑序列是

9、( )。 （ A） a， c， b， d （ B） a， d， b， c （ C） a， b， d， c （ D） b， a， d， c 24 用快速排序法对包含 n个关键字的序列进行排序，最坏情况下的执行时间为( )。 （ A） O(nlog2n) （ B） O(n2) （ C） O(log2n) （ D） O(n) 25 二叉树的先序遍历和中序遍历如下；先序遍历： EFHIGJK 中序遍历：HFIEJKG 该二叉树根结点的右子树由哪些结点组成 ?( ) （ A） FHI （ B） EFH （ C） JKG （ D） EJKG 26 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，

10、则可采用的方法是 ( )。 （ A）分块法 （ B）顺序法 （ C）二分法 （ D）散列法 27 以下关键码序列用快速排序法进行排序，速度最慢的是 ( )。 （ A） 23， 27， 7， 19， 11， 25， 32 （ B） 23， 11， 19， 32， 27， 25， 7 （ C） 7， 11， 19， 23， 25， 27， 32 （ D） 27， 25， 32， 19， 23， 7， 11 28 一个 nn的带状矩阵 A=aij如下 将带状区域中的元素 aij(|i-j|1)按行序为主序存储在一维数组 B13n-2中，元素 aij在 B中的存储位置是 ( )。 （ A） i+2j-

11、1 （ B） 2i+j-2 （ C） 3i-j+1 （ D） i+j+2 29 设栈 S和队列 Q的初始状态为空，元素 e1、 e2、 e3、 e4、 e5和 e6依次通过栈S，一个元素出栈后即进入队列 Q，若 6个元素出队的顺序是 e2、 e4、 e3、 e6、e5、 e1，则栈 S的容量至少应该是 ( )。 （ A） 3 （ B） 4 （ C） 5 （ D） 2 30 设树 T的度为 4，其中度为 1、 2、 3和 4的结点的个数分别为 4、 2、 1、 1，则T中叶子结点的个数是 ( )。 （ A） 6 （ B） 7 （ C） 8 （ D） 9 31 若待排序序列已基本有序，要使它完全有

12、序，从关键码比较次数和移动次数考虑，应当使用的排序方法是 ( )。 （ A）归并排序 （ B）直接插入排序 （ C）直接选择排序 （ D）快速排序 32 有关二叉树的下列说法正 确的是 ( )。 （ A）二叉树的度为 2 （ B）一棵二叉树的度可以小于 2 （ C）二叉树中任何一个结点的度都为 2 （ D）任何一棵二叉树中至少有一个结点的度为 2 33 对关键码集合 K=53， 30， 37， 12， 45， 24， 96，从空二叉树开始逐个插入每个关键码，建立与集合 K相对应的二叉排序树，若希望得到最佳二叉排序树，应选择下列 ( )输入序列。 （ A） 45， 24， 53， 12， 37，

13、 96， 30 （ B） 30， 24， 12， 37， 45， 96， 53 （ C） 12， 24， 30， 37， 45， 53， 96 （ D） 37， 24， 12， 30， 53， 45， 96 34 设有向图 G有 n个顶点，它的邻接矩阵为 A， G中第 i个顶点 Vi的度为 ( )。 （ A） （ B） （ C） （ D） 35 在有向图 G的拓扑序列中，如果顶点 Vi在 Vi之前，则在下列情况中一定不可能出现的是 ( )。 （ A） G中有弧 Vi， Vi （ B） G中没有弧 Vi， V(i （ C） G中有一条从 Vi到 Vi的路径 （ D） G中有一条从 Vi到 Vi的

14、路径 36 对无向图 G(下图 )，若从顶点 V1开始，按深度优先搜索法进行遍历 ，则可能的访问顺序是 ( )。 （ A） V1V2V3V4V5V6V7V8 （ B） V1V2V3V5V4V6V7V8 （ C） V1V2V6V3V4V7V8V5 （ D） V1V2V6V3V5V4V7V8 37 下面关于数据结构的叙述中，正确的叙述是 ( )。 （ A）顺序存储方式的优点是存储密度大，且插入、删除运算效率高 （ B）链表中的每一个结点都包含恰好一个指针 （ C）包含 n个结点的二叉排序树的最大检索长度为 log2n （ D）将一棵树转换为二叉树后，根结点没有右子树 38 Assume that

15、an operating system uses a roundrobin scheduler. The processs quantum is 20 msec, and the context switch is 5 msec. What percentage of the CPUs time is spent on administrative overhead? ( ) （ A） 5 . （ B） 15 . （ C） 20 . （ D） 25 . 39 Which UNIX command creates a symbolic link named myfile in the curre

16、nt directory to the file /etc/hosts? ( ) （ A） In s/etc/hosts myfile （ B） In s myfile/etc/hosts （ C） link s/etc/hosts myfile （ D） link s myfile/etc/hosts 40 A virtual memory system has five virtual pages numbered zero through four and three page frames. All the page frames are initially empty. How ma

17、ny page faults are generated with the following access sequence using a FIFO replacement policy? ( ) 0 1 2 3 0 1 4 0 1 2 3 4 （ A） 8 （ B） 9 （ C） 10 （ D） 11 一、论述题（四个论述题可任选其一，并只选其一，多选无效，满分 30分 ) 论述题答题必须用蓝、黑色钢笔或圆珠笔写在论述题答题纸的相应位置上，否则无效。 41 计算机除 CPU和主存以外，其余所有部件均可归人输入 /输出系统，即 1/O系统。所谓 I/O操作是指 1/O设备与主存之间的信息交

18、换。请回答下面的问题： (1)I/O方式发展经历了哪些阶段 ? (2)各阶段的工作原理及优缺点是什么 ? 42 通道实质上是主存与 I/O设备之间的 DMA接口在逻辑上的延伸。请回答下面的问题： (1)通道分为哪几种 ?各有什么特点 ? (2)通道程序由哪三种通道命令字组成 ? (3)简述通道的工作原理。 43 (1)从体系结构的观点对指令集进行分类。根据哪五种尺度 ? (2)通常有哪三种指令集体系结构 ?请写出各自的优缺点 ? (3)GRP机分为几类 ?它们的优缺点各是什么 ? 44 (1)Amdahl给计算机体系结构的定义是什么 ? (2)Myres给计算机体系结构的定义是什么 ?请画出虚

19、拟机层次模型 ? (3)计算机体系结构、计算机组织和计算机实现三者的关系是什么 ? 45 (1)对指令格式设计时要优先考虑哪些原则 ? (2)什么叫作指令格 式的优化 ? 46 (1)指令的控制方式有几种 ?优缺点各是什么 ? (2)如何评价流水线的性能 ? (3)一台非流水线机器执行指令时共分五步，所需时间分别为 40ns、 40ns、 50ns、40ns和 40ns。若 采用流水线工作方式，并且由于锁存器而附加了 20ns的延迟，那么该流水线的加速比是多大 ? 47 (1)什么叫并行性 ?并行性分为哪几种 ? (2)高速并行结构分为哪几类 ?每类各举一例。 (3)相联处理机有哪些特点 ?

20、原国家四级笔试章节练习试卷 6答案与解析 1 【正确答案】 A 2 【正确答案】 C 3 【正确答案】 D 4 【正确答案】 B 5 【正确答案】 A 6 【正确答案】 A 7 【正确答案】 D 8 【正确答案】 D 9 【正确答案】 C 10 【正确答案】 D 11 【正确答案】 B 12 【正确答案】 C 13 【正确答案】 B 14 【正确答案】 A 15 【正确答案】 C 16 【正确答案】 D 17 【正确答案】 B 18 【正确答案】 A 19 【正确答案】 B 20 【正确答案】 A 21 【正确答案】 C 22 【正确答案】 A 23 【正确答案】 C 24 【正确答案】 B

21、25 【正确答案】 C 26 【正确答案】 A 27 【正确答案】 C 28 【正确答案】 B 29 【正确答案】 A 30 【正确答案】 C 31 【正确答案】 C 32 【正确答案】 B 33 【正确答案】 D 34 【正确答案】 C 35 【正确答案】 C 36 【正确答案】 B 37 【正确答案】 D 38 【正确答案】 C 39 【正确答案】 A 40 【正确答案】 B 一、论述题（四个论述题可任选其一，并只选其一，多选无效，满分 30分 ) 论述题答题必须用蓝、黑色钢笔或圆珠笔写在论述题答题纸的相应位置上，否则无效。 41 【正确答案】 (1)I/O方式发展经历了如下六个阶段； 程

22、序控制阶段 重叠处理阶段 中断阶段 DMA阶段 通道阶段 I/O处理机阶段 (2) 程序控制阶段 在程序控制阶段， I/O操作完全由 CPU控制，即由 CPU执行启动、控制以及停止I/O操作，第一代计算机就采用了这种方式。在这种结构里，没有 专门的 I/O控制部件和专用的数据通路。每传送一个数据都要由 CPU执行一段程序，通过算术逻辑部件或由 CPU硬件的微操作序列来控制数据的流动。这种方式的优点是控制简单，编程容易。缺点是 CPU要把大量的时间花在琐碎的 I/O操作上，外设和 CPU不能同时工作，各个外设之间也不能同时工作，因此系统的整体性能差，效率很低。 重叠处理阶段 为了提高 CPU的效

23、率，可使它与 I/O设备重叠工作，这就导致多道作业 “同时 ”执行。当一个作业进行 I/O操作时， CPU又转向另一个作业进行处理，即让多道作业以一定间隔轮流执行，这称为处理器 重叠 (Processor Overlap)方式。 中断阶段 进一步发展产生了中断 (Interrupt)的概念。这样 CPU就不必定时检测 I/O设备的状态，它只要处理 I/O设备的中断请求即可同时启动多个外部设备同时工作。 中断方式的优点是初步解决了 CPU、主存和外设之间的速度匹配。缺点是中断所需的辅助操作很多，当 I/O设备较多时，中断过分频繁而加重 CPU的负担。 DMA阶段 随着体系结构的发展，在 I/O系

24、统中增设数据寄存器、地址寄存器以及计数器等，使外部设备不必通过 CPU而直接与内存交换信息，这称为 DMA方 式，即直接存储器存取 (Direct Memory Access)方式。为此 I/O设备及其控制器要能形成存储地址，能把数据送人主存总线或从主存总线取得数据。 DMA采用了 “挪用周期 ”(Cycle Stealing)的概念，即在 CPU执行程序期间，由 I/O设备插入使用。 DMA方式的优点是它把部分 I/O控制交给设备控制部分，实现了 CPU与 I/O设备的部分并行。缺点是 CPU仍需启动每个信息块的传输，而且 DMA也增加了设备成本。 通道阶段 通道 (Channel)控制方式

25、是在 DMA基础上发展起来的。通道执行 I/O的过 程是；开始时， CPU进入管理状态，自动形成通道程序并把它放入内存，然后由 CPU启动通道。以后则由通道按照通道程序处理 I/O，而 CPU则返回目的状态继续执行原来的程序，直至整个 I/O过程全部结束再由 CPU做结束处理。一个 I/O过程不论交换多少信息，只打扰 CPU两次。 通道方式的优点是 I/与 CPU有较强的并行操作能力，能充分发挥设备的利用率。缺点是通道还不能完全独立于主机，还需要借助 CPU的某些控制。 I/O处理机阶段 设置外部处理机专门负责 I/O操作，也就是具有更强处理功能的通道，称为 I/O处理机 (I/O Proce

26、ssor，简称 IOP)。一个 IOP不必借助于 CPU就能在主存与多台 I/O设备之间执行独立的数据传输工作。 IOP方式的优点是 CPU几乎移交了对 I/O操作的全部控制， IOP几乎完全独立于主机。缺点只是提高了系统的成本。 42 【正确答案】 (1)通道按传送数据的工作方式可分为三类： 字节多路通道 (Byte Multiplexer Channel) 适合连接大量低速设备，如终端、打印机等。这些低速设备的特点是以字节为单位与内存交换信息，而且各字节之间的空闲时间较长。字节多路通道可以有两种工作模式 ；一种是字节交叉模式 (Byte Interleave Mode)，不同的设备在各自分

27、得的时间片内与通道建立逻辑连接；另一种是突发模式 (Burst Mode)，它允许一次让某一设备占用较长的时间来传送较多的信息。 选择通道 (Selector Channel) 适合连接多台高速设备，但每次只能让一台设备独占通道，只装备一套高速通道硬件而轮流为几个物理设备服务。 数组多路通道 (Block Multiplexer Channel) 又称块多路通道或成组多路通道。它综合了字节多路通道和选择通道的工作方式，适合 连接多个磁盘机、磁带机之类的设备。这类设备的特点是查找数据的时间较长而读写数据的时间较短，因此当 n台设备同时连接时，可让其中一台使用通道传送数据，而让 n-1台设备进行数

28、据查找，这可提高通道的利用率。 (2)通道程序由通道地址字、通道状态字、通道命令字三种通道字组成。 (3)通道的 I/O操作过程可分为五个阶段： 准备阶段 用户程序需要输入输出时，在目态程序中安排一条访管 (Supervisor Call)指令并给出相应的参数，产生自愿访管中断后即转入管理程序。管理程序根据参数要求生成相应的通道程序及通道地址字 。通道程序生成后就存入主存中对应此通道的缓冲区中，并将人口地址 CAW置于主存固定单元中，在准备阶段，没有任何信号送给通道和外部设备。 启动阶段 启动阶段主要是 CPU执行 “STARTI/O”指令的过程。它属于管理指令通道进入设备选择期。 CPU在查

29、找设备的同时，还取出 CAW以及通道程序把它们放到通道的指令寄存器中通道把命令送往选好的设备，启动阶段完成。 数据传送阶段 在通道数据传送期， CPU与通道分别做各自的工作， CPU继续执行目态程序，不再过问 I/O情况，而通道则控制着设备与主存的数据直接交换。 结束传送阶段 通道程序执行到无链通道指令时数据传送完成，它就转入通道传送结束阶段。设备发出结束服务请求，并将设备状态宇送人通道。通道检查无误后，向 CPU发中断请求。在此之前， CPU仍在执行目态程序，直至响应中断。 结束中断阶段 CPU响应中断，进人中断处理程序。通道进一步查询发出中断请求的设备，检查无误后，发出释放命令将设备释放。

30、 CPU处理完中断以后，返回目态程序，到此全部输入输出过程结束。 43 【正确答案】 从体系结构的观点对指令集进行分类，可以根据下述五种尺度： 操作数在 CPU中的存储方式，即操作 数从主存中取来后要把它保存在什么地方。 显式操作数的数量，即在一条典型的指令中有多少个显式命名的操作数。 操作数的位置，即任一个 ALU指令的操作数能否放在主存中，或者必须把某些操作数甚至全部操作数都放在 CPU的内部存储器中 ?如果某操作数要放在主存中，那么它是如何定位的 ? 指令的操作，即在指令集中提供哪些操作。 操作数的类型与大小，即每个操作数是什么类型、尺寸大小，以及怎样对它规定。以上五条排列的次序大体上反

31、映了它们在区分指令集时所扮演角色的重要程度。次序越靠前就越重要。 (2)通常有三种指令集体系结构，这三类 分别为：堆栈 (Stack)、累加器(Accumulator)和寄存器集 (a set of registers)。它们的优缺点如下：(3)GRP机分为三类，这三类分别是； 寄存器 寄存器 (Regi9terRegister)类 寄存器 存储器 (RegisterMemory)类 存储器 存储器 (MemoryMemory)类 它们的优缺点如下： 44 【正确答案】 Amdah1指出计算机体系结构是站在程序员的角度所看到的计算机属性，即程序员要能编写出可在机器上正确运行的程序所必须了解的概

32、念性结 构和功能特性。 (2)Myres指出传统体系结构就是指硬件与软件之间的界面。虚拟机层次模型如下所示：(3)应对计算机体系结构、计算机组织、计算机实现三者的关系加以区别： 计算机体系结构(Computer Architecture)是指计算机的概念性结构和功能属性。 计算机组织(Computer Organization)是指计算机体系结构的逻辑实现，包括机器内的数据流和控制流的组成以及逻辑设计等。我们平常也把它称为计算机组成原理。 计算机实现 (Computer Implementation)是指计算机组织的 物理实现。 45 【正确答案】 (1)对指令格式 (Instruction

33、Format)的设计有一些优先考虑的原则，可概括如下： 关于指令的长度，短指令要比长指令更节约些。尽管存储器的价格越来越便宜，但设计者还是不愿意浪费它们。显然，一个程序如果采用 m个 16位长的指令，要比采用 m个 32位长的指令节省一半的存储空间。 还要考虑是否有足够的空间表示所有期望的操作。如果一个指令集有 2n个操作，那么指令长度就不应短于 n位。 在 GPR结构中，无论是哪种寄存器与存储器类型，提高存取指令的速度都是应该考虑的一个 重要原则。存储器的存取速率越高，就能给处理机提供更多的指令进行处理。在一定的存取速率下，如果平均指令长度较短，那么存储器就能供应更多的指令。从这个意义上说，

34、较短的指令意味着较快的处理速度。 机器字长 (Word Length)应该是字符长度 (Character Length)的整数倍。否则，在存储字符时就会造成浪费，而且也会造成寻址困难。 寻址字段长度的选择。 (2)所谓指令格式的优化就是从整个指令系统的利用率角度出发，尽量设法减少指令中的冗余信息量，以便用最少的位数提供足够的操作信息和地址信息。 46 【正确答案】 指令控制方式有三种：顺序方式、重叠方式、流水方式。 顺序方式是指各条机器指令之间顺序串行地执行，执行完一条指令后才取下一条指令，而且每条机器指令内部的各个微操作也是顺序串行地执行。这种方式的优点是控制简单。缺点是速度上不去，机器各

35、部件的利用率低。 重叠方式是指在解释第 K条指令的操作完成之前，就可开始解释第 K+1条指令。通常采用的是一次重叠，即在任何时候，指令分析部件和指令执行部件都只有相邻两条指令在重叠解释。这种方式的优点是速度有所提高，控制也不太复杂。缺点是会出现冲突、转移、相关进入等问题 ，在设计时必须想办法解决。 流水方式是模仿工业生产过程的流水线(如汽车装配线 )而提出的一种指令控制方式。流水 (Pipelining)技术是把并行性或并发性镶嵌到计算机系统里的一种形式，它是一种把重复的顺序处理过程分解为若干子过程，每个子过程能在专用的独立模块上有效地并发工作的技术。 (2)衡量流水处理机性能的主要指标是吞吐

36、率、效率、流水深度以及加速比等。 吞吐率(Throughput Rate)是指单位时间内能处理的指令条数或者能输出的信息量。 效率(Efficiency)是指流水线的设备利用率。即在整个运 行时间里，流水线的设备有多少时间是真正用于工作的。由于流水线有初始的建立时间和结束的排空时间，因此在连续完成 n个任务的时间里，各段并不总是满负荷的。 流水深度 (Deep)是指流水线充满时，同时能够解释的指令数，也就是流水线的段数 m。 加速比 (Speedup)是指采用流水方式后，执行指令的速度提高的程度，也就是流水方式和等效的非流水线顺序串行方式相比，其速度提高的比值。 (3)根据加速比的定义可知：显

37、然，分子应该是 (40+40+50+40+40)ns，即210ns，而分母应该选择最慢的子过程 50ns并加上延迟 时间 20ns，即 70ns，所以加速比为： Sp=210/70 3(倍 ) 47 【正确答案】 (1)我们把问题求解中能够同时处理的性质称为并行性(Parallelism)，或称平行性。 并行性可分为同时性和并发性两种。同时性 (Simultaneity)是指两个以上的事件在同一时刻发生。例如一个字的各位同时进行存取、 CPU和通道同时工作、各处理单元同时处理同一指令的；同数据。并发性 (Concurrency)是指两个以上的事件在同一时间间隔内发生，例如在多位并行加法器中，由

38、于低位向高位的进位时间延迟，各位的运算 不是在同一时刻进行的，而是在一个时间间隔内完成的，因此各位运算之间存在并发关系。 (2)高速并行结构共分为六类： 专用多功能单元，代表是脉动阵列技术。 相联处理机，代表是 STARAN机。 阵列处理机，代表是 ILLIAC IV机。 数据流计算机，代表是 MIT机。 函数式编程语言处理机，代表是 MAGO机。 多处理机系统，代表是 C. mmp机。 (3)相联处理机有三个特点： 采用按内容访问的相联存储器，即按所给信息内容的部分或全部特征，将内容与该特征相符的所有存储单元在一次访存中都检索出来。因此，存 储操作是并行的，这种处理机当然也是并行的。 来自控制器的一条指令能对许多数据同时进行算术和逻辑运算，从而它是典型的SIMD并行处理机。 运算速度提高，程序编制简化，出错减少。相联处理机的缺点是硬件成本很高。