[考研类试卷]计算机专业（基础综合）模拟试卷62及答案与解析.doc

1、计算机专业（基础综合）模拟试卷 62 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下列说法中，正确的是( )。假设某有序表的长度为 n，则可以在 1(n+1)的位置上插入元素在单链表中，无论是插入还是删除操作，都必须找到其前驱结点删除双链表的中间某个结点时，只需修改两个指针域将两个各有 n 和 m 个元素的有序表(递增)归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n 一 1（A）仅、（B） 、（C）仅 、（D）仅、2 下列关于栈的说法中，正确的是( )。若进栈顺序为 a、 b、c ，则通过

2、出栈操作可能得到 5 个 a、b、c 的不同出栈序列链式栈的栈顶指针一定指向栈的链尾两个栈共享一个向量空间的好处是减少存取时间（A）仅（B）仅 、（C）仅 （D）仅、3 若将 n 阶上三角矩阵 A 按照列优先顺序存放在一维数组 B0，1，n(n+1)2-1中，第一个非零元素 a(1，1)存放于 B0中，则存放到 Bk中的非零元素a(i，j)(1in，1jn)的下标 i、j 与 k 的对应关系是 ( )。（A）k=i(i+1)2+j（B） k=i(i-1)2+j 一 1（C） k=j(j+1)2+i（D）k=j(j 一 1)2+il4 下列说法中，正确的是( )。利用孩子兄弟链存储树，根结点的右

3、指针指向最左孩子树的后根遍历序列等同于该树对应的二叉树的前序遍历序列若一个具有 N 个顶点、K 条边的无向图是一个森林(且 NK)，则森林中必有 NK 棵树（A）仅、（B）仅 、（C）仅 （D）、5 设某赫夫曼树的高度为 5，若已对两个字符编码为 1 和 01，则最多还可以对( )个字符编码。（A）3（B） 4（C） 5（D）66 下列说法中，正确的是( )。在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n22e若邻接表中有奇数个边表结点，则该图一定是有向图对于采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历使用队列实现广度优先遍历算法，则每个顶点进队列的次数可

4、能大于 1（A）仅、（B）仅 、（C）仅 、（D）仅、7 下列关于生成树的说法中，正确的是( )。（A）最小生成树是指权值之和为最小的生成树，且唯一（B）某图的广度优先生成树的高度一定大于等于深度优先生成树的高度（C） Prime 算法和 Kruskual 算法构造的最小生成树一定相同（D）Prime 算法适用于求边稠密的图的最小生成树8 下列关于 m 阶 B+树的说法中，正确的是 ( )。具有 n 个关键字的结点至少含有 n+1 棵子树 所有叶子结点包含全部关键字 B+ 树支持随机索引 IVB+树可用于文件的索引结构（A）仅、IV（B）仅 、（C）仅 、（D）仅、9 利用逐点插入建立序列(5

5、0，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 需进行( )次元素问的比较。（A）4（B） 5（C） 6（D）710 用直接插入排序对下面 4 个序列进行递增排序，元素比较次数最少的是( )。（A）94，32，40，90，80，46，21，69（B） 32，40，21，46，69，94，90，80（C） 21，32，46，40，80，69，90，94（D）90，69，80，46，21，32，94，4011 在外部排序算法中，最佳归并树主要的作用是( )。（A）产生初始归并段（B）完成归并排序（C）对归并排序进行优化（D）增大归并路树12 下列说

6、法中，错误的是( )。时钟频率和 CPI 成反比关系数据字长等于 MDR 的位数A 主机的 CPU 主频高于 B 主机的 CPU 主频，则前者运算能力将会高于后者（A）仅、（B）仅 、（C）仅 、（D）、13 假定采用 IEEE 754 单精度浮点数格式表示一个数为 45100000H，则该数的值是( )。（A）(+1125)2 10（B） (+1125)2 11（C） (+0125)2 11（D）(+0125)2 1014 一个 8 位的二进制整数，若采用补码表示，且由 3 个“1”和 5 个“0” 组成，则最小值为( ) 。（A）一 127（B）一 32（C）一 125（D）一 315 一

7、台 8 位微机的地址总线为 16 条，其 RAM 存储器容量为 32KB，首地址为4000H，且地址是连续的，可用的最高地址为( )。（A）BFFFH（B） CFFFH（C） DFFFH（D）EFFFH16 有效容量为 128KB 的 Cache，每块 16B，8 路组相联。字节地址为 1234567H的单元调入该 Cache，其 Tag 应为( )。（A）1234H（B） 2468H（C） 048DH（D）12345H17 在单发射、按序流动的普通流水线中，可能出现下列( )数据相关问题。写后读相关 RAW 读后写相关 WAR 写后写相关 WAW（A）仅（B）仅 、（C）仅 （D）仅、18

8、下列关于 CISC 和 RISC 计算机的叙述中，错误的是 ( )。（A）RISC 机器指令比 CISC 机器指令简单（B） RISC 扣通用寄存器比 CISC 多（C） RISC 中的寻址方式比 CISC 少（D）CISC 比 RISC 机器可以更好地支持高级语言19 CPU 响应中断时需要保护断点，断点指的是( )。（A）中断服务程序的入口地址（B）程序计数器(PC) 的内容（C） CPU 内各寄存器的内容（D）指令寄存器(IR) 的内容20 下列说法中，正确的是( )。（A）所有指令的取指操作的时间都是相同的（B）中断周期是在指令执行完成后出现的（C）微命令发生器的作用是产生控制时序（D

9、）所有指令的间址操作都是一样的21 总线宽度只与下列( )选项有关。控制线根数 地址线根数 数据线根数（A）仅（B）仅 、（C）仅 （D）、22 在主机和外设的信息传送中，( )没有使用程序控制方式。（A）程序查询方式（B）程序中断方式（C） DMA 方式（D）通道方式23 引入多道程序技术的前提条件之一是系统具有( )。（A）多个 CPU（B）多个终端（C）通道（D）分时功能24 在有一个 CPU 和两台外设 D1 和 D2，且能够实现基于优先级的抢占式调度算法的多道程序环境中，同时进入优先级由高到低的 P1、P2 、P3 的 3 个作业，每个作业的处理程序和使用资源的时间如下： P1：D2

10、(30ms)，CPU(10ms)，D1(30ms) ，CPU(10ms)。 P2 ：D1(20ms)，CPU(20ms) ，D2(40ms)。 P3 ：CPU(30ms)，D1(20ms)。 假设对于其他辅助操作时间忽略不计，CPU 的利用率是( ) 。（A）478（B） 578（C） 678（D）77825 以下程序中有两个并发进程，且假设这两个并发进程可以任何相对速度执行，变量 amount 的值只有被单独的机器指令装入寄存器后才能被增值。BEGINamount：integer；amount：=0；COBEGINprocess Plnl：integer；BEGINfor n1：=1 to

11、10 do amount：=amount+2；END；process P2n1：integer；BEGINfor n1：=1 to 10 do amount：=amount+3；END；COENDwrite(amount)；END；以上程序输出的共享变量 amount 的上下界为( )。（A）20 ，30（B） O，20（C） 20，50（D）30 ，5026 系统的资源分配图在下列情况中，无法判断是否处于死锁的情况是( )。出现了环路没有环路每种资源只有一个，并出现环路每个进程结点至少有一条请求边（A）、（B）仅 、（C）仅 、（D）都能判断27 下列存储管理方式中，会产生内部碎片的是( )

12、。分段虚拟存储管理分页虚拟存储管理 段页式分区管理固定式分区管理（A）仅、Ill（B）仅 、（C）仅 （D）仅、28 下列程序设计技术和数据结构中，适合虚拟页式存储系统的有( )。堆栈Hash 函数索引的符号表顺序搜索二分法查找纯代码矢量操作间接寻址矩阵操作（A）、（B） 、（C） 、（D）、29 下面关于文件的叙述中，错误的是( )。打开文件的主要操作是把指定文件复制到内存指定的区域对一个文件的访问，常由用广访问权限和用户优先级共同限制文件系统采用树形目录结构后，对于不同用户的文件，其文件名应该不同为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件（A）仅（B）仅 、（C）仅

13、、（D）、30 在 PC-DOS 中，某磁盘文件 A 与 B，它们所占用的磁盘空间如下所示。试问A、B 文件在磁盘上各占( )簇。（A）3，3（B） 4，5（C） 5，3（D）5，431 某磁盘盘组共有 10 个盘面，每个盘面上有 100 个磁道，每个磁道有 32 个扇区，假定物理块的大小为 2 个扇区，分配以物理块为单位。若使用位图(Bitmap)管理磁盘空间，则位图需要占用的空间大小是( )。（A）2000B（B） 12000B（C） 6000B（D）16000B32 下列不属于 DMA 控制器的是( )。（A）命令状态寄存器（B）内存地址寄存器（C）数据寄存器（D）堆栈指针寄存器33 如

14、图 7-1 所示的是某 IP 网络连接拓扑结构，共有 ( )。（A）5 个冲突域，1 个广播域（B） 3 个冲突域，3 个广播域（C） 4 个冲突域，2 个广播域（D）6 个冲突域，2 个广播域34 以下 4 种以太网中，只能工作在全双工模式下的是( )。10BASE T 以太网 100BASE-T 以太网 吉比特以太网 10吉比特以太网（A）仅、IV（B）仅 （C）仅 、IV（D）、35 CSMACD 中，一旦某个站点检测到冲突，它就立即停止发送，其他站点( )。（A）都处于待发送状态（B）都会相继竞争发送权（C）都会接收到阻塞信号（D）仍有可能继续发送帧36 某端口的 IP 地址为 172

15、16713126，则该 IP 地址所在网络的广播地址是( )。（A）172167255（B） 172167129（C） 172167191（D）17216725237 下列关于 ARP 的说法中，错误的是( )。ARP 的请求报文是单播的ARP 的响应报文是单播的如果局域网 A 的主机 1 想和局域网 B 的主机 2 通信，但是主机 1 不知道主机 2 的物理地址，主机 1 通过发送 ARP 报文就可以解决（A）仅（B）仅 （C）仅 、（D）仅、38 一个网段的网络号为 1989010027，子网掩码固定为255255255224，最多可以分成( )个子块，而每个子块最多具有( )个有效的 I

16、P 地址。（A）8，30（B） 6，30（C） 16，14（D）32，639 A 和 B 建立 TCP 连接， MSS 为 1KB。某时，慢开始门限值为 2KB，A 的拥塞窗口为 4KB，在接下来的一个 RTT 内，A 向 B 发送了 4KB 的数据(TCP 的数据部分)，并且得到了 B 的确认，确认报文中的窗口字段的值为 2KB，那么，请问在下一个 RTT 中，A 最多能向 B 发送( )数据。（A）2KB（B） 4KB（C） 5KB（D）8KB40 在进行域名解析的过程中，由( )获取的解析结果耗时最短。（A）主域名服务器（B）辅域名服务器（C）缓存域名服务器（D）转发域名服务器二、综合应

17、用题41-47 小题，共 70 分。40 有如图 34 所示的带权有向图 G，试回答以下问题。41 给出图 G 的邻接表。42 给出从顶点 1 出发的深度优先遍历序列和广度优先遍历序列。43 给出 G 的一个拓扑序列。44 判断该图是否为强连通图。45 若用三元组存储邻接矩阵的数据，每个三元组占 3B，求共需多大空间?若用邻接矩阵存储时每个元素占 1B，试比较哪种存储更省空间。45 假设输入，一句英语句子：“I am a student”，要求输出“studenta am I”。也就是说以单词为基本单位将句子中的所有单词翻转过来。请实现一个时间和空间上尽可能高效率的算法，将句子中所有的单词翻转

18、过来。要求：46 给出算法的基本设计思想。47 根据设计思想，采用 C、C+或 Java 语言描述算法，关键之处给出注释。48 说明你所设计算法的时间复杂度和空间复杂度。48 有 5 个中断源 D1、D2、D3、D4 和 D5，它们的中断优先级从高到低分别是 1级、2 级、3 级、4 级和 5 级。这些中断源的中断优先级，正常情况下的中断屏蔽码和改变后的中断屏蔽码如表 33 所示。每个中断源有 5 位中断屏蔽码，“O”表示该中断开放，“1”表示该中断被屏蔽。49 当使用正常的中断屏蔽码时，处理机响应各中断源的中断服务请求的顺序是什么?实际的中断处理顺序是什么?50 当使用改变后的中断屏蔽码时，

19、处理机响应各中断源的中断服务请求的顺序是什么?实际的中断处理顺序是什么?51 当 D1、D2、D3、D4、D5 这 5 个中断源同时发出中断请求时 (采用改变后的中断屏蔽码)，试画出处理机响应中断源的中断服务请求和实际运行中断服务过程的示意图。52 假设从处理机响应中断源的中断服务请求开始，到运行中断服务程序中第一次开中断所用的时间为 1 个单位时间，处理机运行中断服务程序的其他部分所用的时间为 4 个单位时间。当处理机在执行主程序时，中断源 D3、D4 和 D5 同时发出中断服务请求，经过 3 个单位时间后，中断源 D1 和 D2 同时发出中断服务请求。采用改变后的中断屏蔽码，画出处理机响应

20、各中断源的中断服务请求和实际运行中断服务程序过程的示意图。52 某微程序计算机具有 12 条微指令 v1V12，每条微指令所包含的微命令信号如表 34 所示。表 34 中，an 分别对应 14 种不同的微命令，假设一条微命令长 20 位，其中操作控制字段为 8 位，控存容量为 1K20 位。要求：53 采用“不译法 ”与“分段直接编码法”混合设计此机微指令的操作控制字段格式，并为每个微命令分配编码。54 采用“增量 ”与“下址字段”相结合的方式设计此机微指令的顺序控制字段格式，若要使微程序可在整个控存空间实现转移，则该微指令的顺序控制字段可直接表示出几个转移条件?55 画出此机微指令的完整格式

21、图，并标出每个具体字段所需的二进制位数。55 假设有一个进程拥有两个线程(编号为 0 和 1)需要去访问同一个共享资源，为了避免竞争状态的问题，必须实现一种互斥机制，使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码：int flag2；*flag 数组，初始化为 FALSE*Enter_critical_section(int my_thread_id)，int other_thread_id)while (flagother_thread-id=TRuE)； *空循环语句*flagmy_thread_id=TRUE；Exit_Critical_Seetion(int my_t

22、hread_id)，int other_thread_id)flagmy_thread_id=FALSE；当一个线程想要访问临界资源时，就调用上述的这两个函数。例如，线程 0 的代码可能是这样的：Enter_Critical_Section(0，1)；使用这个资源Exit_Critical_Section(0， 1)，做其他的事情试问：56 该共享资源可以是( )。57 以上的这种机制能够实现资源互斥访问吗?为什么?58 如果把 Enter Critical Section()函数中的两条语句互换一下位置，结果会如何 ?58 设一作业共有 5 页(04)，其中程序占 3 页(02 页)，常数占

23、 1 页(第 3 页)，工作单元占 1 页(第 4 页) ，它们依次放在外存的 45、46 页和 98、99、100 页。现在为程序段先分配内存，主存分配情况的位示图如图 35 所示(0 表示未分配，1 表示已分配)。 请回答下述问题：59 页表应包含哪些项目?若按空闲块顺序依次分配，请给出为程序段分配完内存后的页表。目前常数区和工作区尚未获得内存。若现在先为工作区分配内存，则页表如何变化?60 在运行中，因需要使用常数而发生中断，操作系统应如何处理?页表又发生什么变化?【页面置换算法为 FIFO】60 TCP 的拥塞窗口 cwnd 大小与传输轮次 n 的关系如表 35 所示。61 试画出拥塞

24、窗口与传输轮次的关系曲线。62 指明 TCP 工作在慢开始阶段的时间间隔及其 TCP 工作在拥塞避免阶段的时间间隔。63 在第 16 轮次和第 22 轮次之后发送方是通过收到 3 个重复的确认还是通过超时检测到丢失了报文段?64 在第 1 轮次、第 18 轮次和第 24 轮次发送时，门限 ssthresh 分别被设置为多大?65 假定在第 26 轮次之后收到了 3 个重复的确认，因而检测出了报文段的丢失，那么拥塞窗口 cwnd 和门限 ssthresh 应设置为多大?计算机专业（基础综合）模拟试卷 62 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选

25、项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 ：有序表插入的时候是不能指定位置的，因为这样可能使得插入后的表不再是有序表。正确的插入思路是：先通过元素比较找到插入的位置，再在该位置上插入，故错误。：从单链表插入和删除的语句描述可以看出，无论是插入还是删除操作，都必须找到其前驱结点，故正确。：删除双链表的中间某个结点时，需要修改前后两个结点的各一个指针域，共计两个指针域，故正确。：当一个较短有序表中的所有元素均小于另一个较长有序表中的所有的元素，所需比较次数最少。假设一个有序表为 1、3、4，另一个有序表为5、6、7、8、12，这样只需比较 3 次即可，故答案应该是 n

26、 和 m 中较小者，即min(n，m)，故错误。2 【正确答案】 A【试题解析】 ：该选项旨在让考生知道一个公式。对于 n 个不同元素进栈，出栈序列的个数为 可以马上得出，当 n=3 时，出栈序列个数为故正确。 ：链式栈一般采用单链表，栈顶指针即为链头指针。进栈和出栈均在链头进行，每次都要修改栈顶指针，链空即栈空(top=NULL)，故错误。 ：由于栈中数据的操作只有入栈和出栈，且时间复杂度均为 O(1)，因此并没有减少存取时间，故错误。 补充知识点：共享栈 提示：两个栈共享一个数组 A0MaxSize 1的空间，从而构成共享栈。数组 A 的两端是固定的，而栈底也是固定的，为此将下标为 0 的

27、一端作为栈 1 的栈底，其栈项指针为 top1；将下标为。MaxSize1 的一端作为栈 2 的栈底，其栈顶指针为 top2，如图 74 所示。 栈 l 的四要素如下：栈空条件： top1=一 1。 栈满条件：top1=top2 一 1。 元素 x 进栈：top1+；将元素 x 插入 Atop1处。 出栈元素：弹出 Atop1元素；top1-。 栈2 的四要素如下： 栈空条件： top2=MaxSize。 栈满条件：top2=top1+1。 元素 x 进栈： top2 一；将元素 x 插入 Atop2处。 出栈元素：弹出 Atop2元素；top2+。 注：以上都默认指针指向当前元素的下一个位置

28、。3 【正确答案】 D【试题解析】 对于元素 a(i，j)而言，前面有 j1 列，第 1 列到第 j 一 1 列的元素个数分别为 1j1 个，由等差数列求和公式可算得一共有 j(j-1)2 个元素，故k=j(j 一 1)2+i-1(注意：B 数组是从 O 开始存放元素，因此要减去 1)。4 【正确答案】 C【试题解析】 ：利用孩子兄弟链存储树，根结点的右指针为空，故错误。 ：如表 73 所示，树的后根遍历序列等同于该树对应的二叉树的中序遍历序列，故错误。：设此森林中共有 m 棵树，每棵树具有的顶点数为 vi(1im)，则 V 1+V2+vm=N (V1一 1)+(V21)+(Vm 一 1)=K

29、 联立可得 m=NK，故正确。5 【正确答案】 B【试题解析】 赫夫曼编码遵循的原则为：一个编码不能是任何其他编码的前缀。比如 1 和 10 就不行，因为 1 是 10 的前缀。既然 1 和 01 已经使用了，那么 1 和 01开头的码字不能再使用。又由于赫夫曼树的高度为 5，因此赫夫曼编码的长度不能超过 4，只剩下 0000、0001、0010、0011 这 4 种编码(这种编码方式可得到最多)，故选 B 选项。 注意：本题选的是最多还可以对多少个字符编码，所以不能选取001、000 等编码。若选取 001，就意味着 0010 和 0011 不能使用，这样可编码的字符就少了 1 个。 总结：

30、 (1)有 n 个叶子结点的赫夫曼树的结点总数为 2n1。 (2)高度为 h 的赫夫曼树中，至少有 2h 一 1 个结点，至多有 2h 一 1 个结点。 (3)赫夫曼树中一定没有度为 1 的结点。 (4)赫夫曼树中两个权值最小的结点一定是兄弟结点。(5)赫夫曼树中任一非叶子结点的权值一定不小于下一层任一结点的权值。 补充例题：一棵赫夫曼树共有 215 个结点，对其进行赫夫曼编码，共能得到多少个码字? 提示：求多少个码字就是求有多少个叶子结点，由(1)中的公式可得：2n 一1=215，故叶子结点的个数为 108 个，故可以得到 108 个码字。6 【正确答案】 D【试题解析】 ：总结如下。 对于

31、一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 n2。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，非零元素的个数为 2e。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n22e。 在含有 n 个顶点 e 条边的有向图的邻接矩阵中，非零元素的个数为 e。 在含有 n 个顶点 e 条边的有向图的邻接矩阵中，零元素的个数为 n2-e。 根据，故正确。 ：无向图采用邻接表表示时，每条边存储两次，所以其边表结点个数为偶数，故边表结点为奇数且只能是有向图，故正确。 ：深度优先遍历算法是先访问一个顶点 v，然后是离顶点越远越优先访问，即相当于二叉树的先序遍历，

32、故错误。 ：采用广度优先遍历算法遍历一个图时，每个顶点仅遍历一次，所以最多只能进队 1 次，故错误。7 【正确答案】 D【试题解析】 A：最小生成树是指权值之和为最小的生成树，但是不唯一，故 A选项错误。 B：由广度优先遍历和深度优先遍历算法可知，深度优先算法构造的生成树的树高大于等于广度优先算法构造的生成树的树高，故 B 选项错误。 C ：当最小生成树不唯一时，这两种算法构造的最小生成树可能相同，也可能不同，故C 选项错误。 D：Prime 算法的时间复杂度为 O(n2)，适合稠密图；Kruskual 算法的时间复杂度为 O(elog2e)，适合稀疏图，故 D 选项正确。8 【正确答案】 B

33、【试题解析】 一棵 m 阶 B+树满足下列条件。每个分支结点至多有 m 棵子树。根结点或者没有子树，或者至少有两棵子树。除根结点外，其他每个分支结点至少有m 2棵子树。具有 n 个关键字的结点含有 n 棵子树。所有叶子结点包含伞部关键字及指向相应记录的指针，而且叶子结点按关键字的大小顺序链接。所有分支结点中仅包含它的各个子结点中最大关键字及指向子结点的指针。B+树中，所有非终端结点可以看成是索引部分，故可用于文件的索引结构。注意：由于 B+树为链式存储结构，因此不支持随机检索。 综上所述，可知、IV 正确，、错误，故 B 选项正确。 补充知识点：很多考生被 B+树和 B-树的基本概念弄混，下面

34、做一个小结。 提示：m 阶 B+树和 m 阶 B-树的主要差异如下。在 B+树中，具有 n 个关键字的结点含有 n 棵子树；而在 B-树中，具有 n 个关键字的结点至少含有(n+1)棵子树。在 B+树中，每个结点(除根结点外)中的关键字个数 n 的取值范围是m2nm，根结点 n 的取值范围是 2nm；而在 B 一树中，除根结点外，其他所有非叶子结点的关键字个数 n 的取值范围是m21nm 一 1，根结点 n 的取值范围是 1nm1。 记忆方式： “B 一”中有个“一”号，自然关键字个数相对于 B+减掉了 1。在 B+树中，所有叶子结点包含了全部关键字，即其他非叶子结点中的关键字包含在叶子结点中

35、：而在 B 一树中，关键字是不重复的。在 B+树中，所有非叶子结点仅仅是起到了索引的作用，即结点中的每个索引项只含有对应子树的最大关键字和指向子树的指针，不含有该关键字对应记录的存储地址。而在 B 一树中，每个关键字对应一个记录的存储地址。在 B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的叶子结点，所有叶子结点链接成一个链表；而在 B 一树中，叶子结点并不会有指针相连。9 【正确答案】 B【试题解析】 由题可以建立出如图 7-5 所示的一棵二叉排序树。 查找元素 30 一次经过比较的元素为 50，43，20，35，30，共有 5 次元素间的比较，因此本题选 B选项。10 【正确答

36、案】 C【试题解析】 对于直接插入排序，原始序列越接近有序，则比较次数越少，观察序列，C 选项最接近有序。说明：本题目测即可，如果要严格来比较，则可用线性代数中求逆序数的方法，序列逆序数越小则越接近有序。对于序列中某个元素 a，其逆序数为序列中 a 之后比 a 小的元素的个数，整个序列的逆序数为所有元素逆序数之和。对于 A，各元素逆序数为94：7；32：1；40：1；90：4；80：3；46：1；21：0；69：0。因此，序列 A 的逆序数为 7+1+1+4+3+1+0+0=17。对于 B，各元素逆序数为32：1；40：1；21：0；46：0；69：0；94：2；90：1；80：0。因此，序列

37、 A 的逆序数为 1+1+0+0+0+2+1+0=5。对于 C，各元素逆序数为21：0；32：0；46：1；40：0；80：1；69：0；90：0；94：0。因此，序列 A 的逆序数为 0+0+1+0+1+0+0+0=2。对于 D，各元素逆序数为90：6；69：4；80：4；46：3；21：0；32：0；94：0；40：0。因此，序列 A 的逆序数为 6+4+4+3+0+0+0+0=17。 可以看出 C 选项序列的逆序数最小，即 C 选项最接近有序，所需比较次数最少。11 【正确答案】 C【试题解析】 A：产生初始归并段的工作应该由置换一选择排序完成，故 A 选项错误。 设输入的关键字满足 k

38、1k 2k n，缓冲区大小为 m，用置换一选择排序方法可产生nm 个初始归并段。 B：因为最佳归并树是针对排序之后的初始归并段操作，所以归并排序不可能由最佳归并树完成，故 B 选项错误。 C ：最佳归并树仿照赫夫曼树的构造过程，以初始归并段的长度为权值，构造具有最小带权路径长度的赫夫曼树，可以有效地减少归并过程中的读写记录数，从而加快外部排序的速度，故 C 选项正确。 D：增大归并路数应该是由败者树来完成的，故 D 选项错误。12 【正确答案】 D【试题解析】 ：时钟频率和 CPI 并无关系。时钟频率的提高仅仅是将时钟周期缩短，并没有改变执行一条指令所需要的时钟周期数，故 I 错误。：一般来讲

39、，MDR 的位数和存储字长相等，而数据字长是一次存取数据的长度，可以和 MDR 不相等，故 错误。：CPU 的主频是表示在 CPU 内数字脉冲信号震荡的次数，是衡量 CPU 运算速度的重要参数，但不是唯一的参数，因此不能直接根据主频来比较运算能力，故错误。13 【正确答案】 B【试题解析】 45100000H 的二进制数为 0100 0101 0001 0000 0000 0000 0000 0000，第 1 位为符号位，表示正数，随后 8 位 1000 1010 为用移码表示的阶码，减去 127 得到十进制数 11，而 IEEE 754 中单精度数在阶码不为 0 时隐含 1，所以该数为(1

40、0010) 2=1125。14 【正确答案】 C【试题解析】 8 位补码最小时必为负数，所以第一位(符号位)必须为 1。而负数的数值位绝对值越大，则此负数越小。又负数的补码表示的高位 0 相当于原码表示的1，故当剩下的 2 个“1”在最低位，5 个“0”在数值位的最高位时此负数最小。该负数的补码为 10000011，则原码为 11111101，转换成十进制为-125。15 【正确答案】 A【试题解析】 32KB 存储空间共占用 15 条地址线，若 32KB 的存储地址起始单元为 0000H，其范围应为 00007FFFH，但现在的首地址为 4000H，即首地址后移了，因此最高地址也应该相应后移

41、。故最高地址为 4000H+7FFFH=BFFFH。 归纳总结：32KB 的存储空间是连续的，由于首地址发生变化，末地址也会跟着发生变化。16 【正确答案】 C【试题解析】 因为块的大小为 16B，所以块内地址字段为 4 位；又因为 Cache容量为 128KB，8 路组相联，所以可以分为 1024 组(128KB(816B)=l 024)，对应的组号字段 lO 位；剩下为标记字段。1234567H=0001 001 00011 01 0001 01 0 11 00 1 11，标记字段为高 14 位，0001 001 00011 01=048DH，故选 C 选项。 归纳总结：组相联映像对应的主

42、存地址应包括 3 个部分，即标记(Tag)、组号(Index)和块内地址(Offset)。 解题技巧：首先将主存地址由十六进制变成二进制，其中块内地址字段为最后 4 位，组号字段为中间 10 位，剩下的就是标记字段，将标记字段二进制转换为十六进制，即可得出结果。17 【正确答案】 A【试题解析】 指令取操作数的动作一定在写回结果之前，故在按序流动的单发射(普通标量) 普通流水线中，先进入流水线的指令的取操作数和写回结果的动作一定位于后续指令写回结果的动作之前，故不可能出现 WAR 和 WAW。唯一可能出现的数据相关问题是后续指令在前一手旨令写回结果之前读相关的操作数，即RAW。注：而在非按序流

43、动的流水线中，允许后进入流水线的指令超过先进入流水线的指令先流出流水线，故 3 种数据相关问题都可能出现。 提醒：直接按照中文翻译的比如“读后写”容易理解为“先读后写”，事实上根据英文的意思，应该是“先写后读”，容易绕晕，注意理顺思路，要反着读。18 【正确答案】 D【试题解析】 参看表 74 所示的总结可知，A、 B、C 选项都是正确的。由于RISC 可以优化，因此能更好地支持高级语言。19 【正确答案】 B【试题解析】 CPU 在一条指令执行结束时响应中断，断点指的是程序计数器(PC)的内容，也就是现行程序下一条将要执行指令的地址。20 【正确答案】 B【试题解析】 A：不同长度的指令，其

44、取指操作的时间可能是不同的。例如双字长指令和三字长指令与单字长指令的取指操作访问主存的次数是不同的，故 A 选项错误。B：取指周期间址周期执行周期中断周期，故 B 选项正确。C：微命令发生器也称为控制单元(CU)，用于产生计算机所需的各种微操作命令，故 C 选项错误。D：指令间址有一次间址、两次间址、多次间址，它们的操作是不同的，故 D 选项错误。21 【正确答案】 C【试题解析】 总线宽度又称为总线位宽，它是总线上能够同时传输的数据位数，通常是指数据总线的根数。22 【正确答案】 C【试题解析】 程序查询方式和程序中断方式显然需要程序的干预，而通道方式也是要编制通道程序来控制，而只有 DMA

45、 方式是靠硬件电路实现的。23 【正确答案】 C【试题解析】 中断和通道是多道程序的硬件基础，多道程序系统需要中断和通道的支持。多道程序设计是指允许多个程序同时进入一个计算机系统的主存储器并进行计算的方法。这些程序共享处理机时间和外部设备及其他资源。当一道程序因某种原因(如 IO 请求)而暂停执行时，CPU 立即转去执行另一道程序。这里必须要解决两个问题，首先必须有相应的机制使运行中的程序暂停执行时，能转到另一个程序去；其次是有必要的硬件支持，使外部设备能与 CPU 并行执行。第一个问题由中断解决，第二个问题由通道解决。多道程序设计技术的实现基础是计算机系统具有处理器和外围设备并行工作的能力。

46、这种能力的出现是在中断和通道技术出现后才有。因此，通道技术和中断技术相结合就可实现 CPU 与 IO 设备并行工作，从而使多道程序技术的概念变为现实。 知识点回顾：通道又称为输入输出处理器，它能完成主存储器和外围设备之间的信息传送，与中央处理器并行地执行操作。采用通道技术主要解决了输入输出操作的独立性和各部件工作的并行性。由通道管理和控制输入输出操作，减少了外围设备和中央处理器的逻辑联系，从而把中央处理器从琐碎的输入输出操作中解放出来。此外，外围设备和中央处理能实现并行操作；通道和通道之间能实现并行操作；各通道上的外围设备也能实现并行操作。中断是指某个事件(如电源掉电、浮点运算溢出、外部设备传

47、输完成或出错等)发生时，由相应的中断机构中止现运行程序的执行，引出处理事件程序对相应事件进行处理，处理完毕后返回断点继续执行。24 【正确答案】 D【试题解析】 抢占式优先级调度算法，3 个作业执行的顺序如图 76 所示。(还可以有一种画法，即按照进程来考虑，纵坐标为 P1、P2 、P3。)每小格表示10ms，3 个作业从进入系统到全部运行结束，时间为 90ms。CPU 与外设都是独占设备，运行几寸问分别为各作业的使用时间之和：CPU 运行时间为(10ms+10ms)+20ms+30ms=70ms。故利用率为 7090=77 8 提示： 对于本题中作业执行的顺序可以这样得到，由于采用的是基于优

48、先级的抢占式调度算法，也就是优先级高的作业优先调度，并且可以抢占任何资源使用，故在画设备利用情况表时，我们可以让优先级高的作业一次性完成，再考虑低一级的作业，最后考虑级别最低的作业。25 【正确答案】 C【试题解析】 当进程 P1 和 P2 按顺序执行，即在执行过程中不发生进程切换时，amount 可以达到最大值 50。现在考虑如下情况：每次当进程 P1 执行完一个amount+2，但还没来得及更新 amount 的值时，发生了进程切换，切换到进程P2，进程 P2 也执行完一个 amount+3，这时，amount 的值更新发生在 P1 中，最后 amount 的值为 20。26 【正确答案】 C【试题解析】 首先要注