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

1、计算机专业（基础综合）模拟试卷 61 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下列叙述中，正确的是( )。非空循环单链表 head 的尾结点 p 满足 pnext=head带头结点的循环单链表的头指针为 head，如果 headnextnextnext=head成立，则该单链表的长度为 3静态链表中的指针表示的是下一个元素在数组中的位置将长度为 n 的单链表链接在长度为 m 的单链表之后的算法时间复杂度为O(1)（A）仅、（B） 、（C）仅 、（D）仅、2 利用栈求表达式的值时，需设立运算数栈 S。假

2、设栈 S 只有两个存储单元，在下列表达式中，不发生溢出的是( )。（A）A-B*(CD)（B） (AB)*C-D（C） (AB*C)一 D（D）(AB)*(CD)3 设有一个 n 阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B 口中，A11 存放到 B1中(假定不用 0 下标)，那么 Bk存放的元素的行号是( ) 。4 某完全二叉树的结点个数为 4N+3，则该树的叶子结点个数为 ( )。（A）2N（B） 2N1（C） 2N 一 2（D）2N+25 下列说法中，正确的是( )。 具有 10 个叶子结点的二叉树中有 9 个度为 2 的结点 设高度为 5 的二叉树上

3、只有度为 0 和度为 2 的结点，则该二叉树中所包含的结点数至少为 9 一棵完全二叉树上有 1001 个结点，则可知叶子结点的个数为 501 个 高度为 h 的完全二叉树最少有 2h 个结点（A）仅、（B）仅 、（C）仅 、（D）仅、6 某二叉树有 n 个结点，并且高度为 n，则此类二叉树一共有( )种。（A）log 2n（B） n2（C） n（D）2 n-17 下列关于无向图的说法中，正确的是( )。无向图中某个顶点的度是指图中与该顶点连通的顶点数在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 n 一 1 条边无向图的邻接矩阵是对称矩阵具有 n 个顶点的无向图，最多有 n 个连通分

4、量（A）仅、（B）仅 、（C）仅 （D）、8 下列关于强连通图的说法中，正确的是( )。n 个顶点构成的强连通图至少有 n 条边强连通图是任何顶点到其他所有顶点都有边完全有向图一定是强连通图（A）仅、（B）仅 、（C）仅 、（D）、9 假设初始为空的散列表的地址空间为(010)，散列函数为 H(key)=key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字 37、95、27、14、48，则最后一个关键字值 48 的插入位置是( )。（A）4（B） 5（C） 6（D）810 设待排序元素序列所有元素的排序码都相等，则下列排序方法中排序速度最慢的是( )。（A）直接插入排序（B）起

5、泡排序（C）简单选择排序（D）基数排序11 设线性表中每个元素有两个数据项 K1 和 K2，现对线性表按下列规则进行排序：先看数据项 K1，K1 值小的在前，大的在后；在 K1 值相同的情况下，再看数据项K2，K2 值小的在前，大的在后。满足这种要求的排序方法是( )。（A）先按 K1 值进行直接插入排序，再按 K2 值进行简单选择排序（B）先按 K2 值进行直接插入排序，再按 K1 值进行简单选择排序（C）先按 K1 值进行简单选择排序，再按 K2 值进行直接插入排序（D）先按 K2 值进行简单选择排序，再按 K1 值进行直接插入排序12 下列说法中，错误的是( )。设浮点数的基数为 4，尾

6、数用原码表示，则 0000010 为规格化数浮点数运算中，运算结果超出尾数表示范围则表示溢出任何情况下，浮点数的右规操作最多只会进行一次（A）仅、（B）仅 、（C）仅 、（D）、和13 下列关于定点数原码一位乘法的描述中，错误的是( )。符号位不参加运算，根据数值位的乘法运算结果确定结果的符号位 在原码一位乘算法过程中，所有移位均是算术移位操作 假设两个 n 位数进行原码一位乘，部分积至少需要使用 n 位寄存器（A）仅、（B）仅 、（C）仅 、（D）、14 下列( ) 刷新方式存在死时间。集中刷新 分散刷新 异步刷新（A）I、（B）仅 、（C）仅 、（D）、15 现有一 64K2 位的存储器芯

7、片，欲设计具有同样存储容量的存储器，有( )种方法可以合理地安排地址线和数据线引脚的数目，且使两者之和最小。（A）2（B） 3（C） 4（D）516 在各种寻址方式中，指令的地址码字段可能的情况有( )。寄存器编号 设备端口地址 存储器的单元地址 数值（A）仅、（B）仅 、（C）仅 、（D）、17 与本指令的地址有关的寻址方式是( )。（A）寄存器寻址（B）直接寻址（C）相对寻址（D）间接寻址18 CPU 的设计中，需要( )。指令寄存器 指令译码器 数据缓冲寄存器 地址译码器（A）仅、（B）仅 、（C）仅 、（D）仅、19 将微程序存储在 RAM 中的控制器是( )。（A）动态微程序（B）静

8、态微程序（C）毫微程序（D）水平型微程序20 微指令的组成部分不可能包含( )。微操作控制字段 外部条件字段 操作码字段 下地址字段（A）仅（B）仅 、（C）仅 、（D）仅、21 在计数器定时查询方式下，若每次计数从n2开始，则( )。（A）设备号小的优先级高（B）每个设备使用总线的机会相等（C）设备号大的优先级高（D）以上说法都不正确22 以下 4 个步骤在通道过程中的正确顺序是( )。 组织 IO 操作 向 CPU 发出中断请求 编制通道程序 启动IO 通道（A）（B） （C） （D）23 提高单机资源利用率的关键技术是( )。（A）SPOOLing 技术（B）虚拟技术（C）交换技术（D）

9、多道程序技术24 假设系统中所有进程是同时到达，则最不利于短作业的进程调度算法是( )。（A）FCFS（B） SPF（C） RR（D）高响应比优先25 试问下列同时运行多个进程 Pi，可能会出现的错误是( )。Pi()Lock(m mutex)； 含义为获取互斥信号量a=new int100； 开辟一个大小为 100 的整型数组空间，并用全局指针变量 a 保存空间地址UnLock(m_mutex)；free(a)； 释放数组空间，且 a 的值不改变有多个优先级相同的进程 Pi。（A）内存泄露（B）内存越界访问（C）内存泄露和内存越界访问（D）无26 生产者进程和消费者进程代码如下。生产者进程有

10、一个局部变量nextProduced，以存储新产生的新项：while(1)/*produce an item in nextProduced*/while(in+1)%BUFFER_SIZE=out；/*do nothing*/bufferin=nextProduced；in=(in+1)%BUFFER_SIZE；消费者进程有一个局部变 nextConsumed，以存储所要使用的项：while(1)while(in=out)；*do nothing*nextConsumed=bufferout，out=(0ut+i)BUFFER_SIZE；/*consume the item in nextC

11、onsumed*/当 in=out 和(in+1) BUFFER_SIZE=out 条件成立时，缓冲区中 item 数目各是( )。（A）0，BUFFER_SIZE（B） 0，BUFFER_SIZE-1（C） BUFFER_SIZE-1，0（D）BUFFER_SIZE，027 设主存的分配情况如图 6-1 所示，当有一个进程需申请 45KB 的存储区时，若采用最佳适应法，则所分到的分区首地址为( )。（A）100KB（B） 190KB（C） 330KB（D）410KB28 某请求分页管理系统中，页表保存在内存中。若有一个可用的空闲或被置换的页未被修改，则它处理一个缺页中断需要 8ms(1ms=

12、106ns)，这种情况占缺页中断事件的 30；若被置换的页已被修改，则处理一缺页中断因增加写同外存的时间需要 20ms，一次内存的存取时间为 1ns。为保证有效访问时间不超过 12ns，可接受的最大缺页率是( ) 。(结果保留两位有效数字)（A）6110 -5（B） 1210 -5。（C） 6110 -6（D）1210 -629 在页式虚拟管理系统中，假定驻留集为 m 个页帧 (初始所有页帧均为空)，在长为 p 的引用串中具有 n 个不同页号(nm)，对于 FIFO、LRU 两种页面替换算法，其缺页中断的次数的范围分别为( )。（A）m ，p和n，p（B） m，n和n ，p（C） n，p 和m

13、 ，n（D）n ，p和n，p30 设有一个记录式文件，采用链接分配方式，逻辑记录的同定长度为 100B，记录类型是英文文本(例如：WelcOmE to TiaNqin!)，在磁盘卜存储时采用成组分解技术。盘块长度为 512B。如果该文件的目录项已经读入内存，用户现在需要规范第 22 个逻辑记录中的大小写格式，该操作共需启动硬靠的次数为( )。（A）1（B） 2（C） 5（D）631 考虑一个有如表 6-1 所示参数的磁盘：估计访问一个磁盘扇区的平均时间 Taccess 约为( )。（A）4ms（B） 8ms（C） 13ms（D）17ms32 下列关于设备驱动程序的叙述中，正确的是( )。与设备

14、相关的中断处理过程是由设备驱动程序完成的由于驱动程序与 IO 设备(硬件)紧密相关，故必须全部用汇编语言书写磁盘的调度程序是在设备驱动程序中运行的一个计算机系统配置了 2 台同类绘图机和 3 台同类打印机，为了正确驱动这些设备，系统应该提供 5 个设备驱动程序（A）仅、（B）仅 、（C）仅 、（D）、33 透明网桥的 MAC 电址表要记录的信息有( )。目的站 MAC 地址 源站 MAC 地址 端口号 帧到达时间 帧转发标记（A）仅、（B）仅 、V（C）仅 、（D）仅、34 下列说法中，错误的是( )。假设帧序号有 3 位，采用连续 ARQ 协议，发送窗口的最大值为 4对于窗口大小为 n 的滑

15、动窗口，最多可以有 n 帧已发送但没有确认在后退 N 帧协议中，如果发送窗口的大小是 16，那么至少需要 4 位的序列号才能保证协议不出错（A）仅、（B）仅 （C）仅 、（D）、35 假设某网络最远的两个站点长度为 10km，数据传输率为 10Mbits 的CSMACS 以太网，信号传播速度为 200ms。那么该网络的最小帧长为( )。（A）20bit（B） 200bit（C） 100bit（D）1000bit36 图 6-2 是网络地址转换 NAT 的一个实例，根据图 62 中的信息，标号为 的方格中的内容应为( ) 。（A）S=135211，80 D=202 011，5001（B） S=1

16、35211，80 D=19216811，3342（C） S=202011，5001 D=135211，80 （D）S=19216811，3342 D=135 21 1，8037 在一条点对点的链路上，为了减少地址的浪费，子网掩码应该指定为( )。（A）255255255252（B） 255255255248（C） 255255255240（D）25525525519638 在 IP 分组的传输过程中，以下 IP 分组首部中的字段保持不变的是( )。总长度 头部检验和 生存时间 源 IP 地址（A）仅、（B）仅 （C）仅 、（D）仅、39 TCP 为了实现可靠的服务，采用超时重传、确认捎带技术。

17、其中，在确认信息中捎带( ) 的序号以减少通信量。（A）上一个已接收的报文（B）下一个希望接收的报文（C）正在发送的报文（D）下一个将要发送的报文40 某网络允许的最大报文段的长度为 128B，序号用 8bit 表示，报文段在网络中的寿命为 30s，则每一条 TCP 连接所能达到的最高数据率为 ( )。（A）46kbits（B） 189kbits（C） 87khits（D）256khits二、综合应用题41-47 小题，共 70 分。40 有人提出这样的一种从图 G 中顶点 u 开始构造最小生成树的方法。假设 G=(V，E)是一个具有 n 个顶点的带权连通无向图，T=(U，TE)是 G 的最小

18、生成树，其中 U 是 T 的顶点集，TE 是 T 的边集，则由 G 构造从起始顶点 u 出发的最小生成树 T 的步骤如下：41 初始化 U=u。以 u 到其他顶点的所有边为候选边。42 重复以下步骤 n1 次，使得其他 n 一 1 个顶点被加入到 U 中。 从候选边中挑选权值最小的边加入到 TE，设该边在 V-U 中的顶点是 v，将 v 加入 U 中。考查顶点 v，将 v 与 V-U 顶点集中的所有边作为新的候选边。 若此方法求得的 T 是最小生成树，请予以证明。若不能求得最小生成树，请举出反例。42 设一个字符串除字符串结束符之外，共包含 n(n1)个字符，设计一个在时间和空间两方面尽可能高

19、效的算法，在这个字符串中找到第一个只出现一次的字符。例如字符串为 abcdabd，则输出 c。要求：43 给出算法的基本设计思想。44 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。45 说明你所设计算法的时间复杂度与空间复杂度。45 假设一个主频为 1GHz、CPI 为 5 的 CPU 需要从某个成块传送的 IO 设备读取1 000B 的数据到主存缓冲区中，该 IO 设备一旦启动即按 50KBs 的数据传输率向主机传送 1000B 数据，每个字节的读取、处理并存入内存缓冲区需要 1 000 个时钟周期，则以下 4 种方式下，在 1 000B 的读取过程中，CP

20、U 用在该设备的IO 操作上的时间分别为多少?占整个 CPU 时间的百分比分别是多少?46 采用定时查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。47 采用独占查询方式，每次处理一个字节，一次状态查询至少需要 60 个时钟周期。48 采用中断 IO 方式，外设每准备好一个字节发送一次中断请求。每次中断响应需要 2 个时钟周期，中断服务程序的执行需要 1200 个时钟周期。49 采用周期挪用 DMA 方式，每挪用一次主存周期处理一个字节，一次 DMA 传送完成 1 000B 的传送，DMA 初始化和后处理的时间为 2 000 个时钟周期，CPU和 DMA 之间没有访存冲突。

21、50 如果设备的速度提高到 5MBs，则上述 4 种方式中，哪些是不可行的? 为什么?对于可行的方式，计算出 CPU 在该设备：IO 操作上所用的时间占整个 CPU 时间的百分比。50 硬磁盘共有 4 个记录面，存储区域内半径为 10cm，外半径为 155cm，道密度为 60 道cm，外层位密度为 600bitcm，转速为 6 000rmin。问：51 硬磁盘的磁道总数是多少?52 硬磁盘的容量是多少?磁盘的非格式化容量和格式化容量是一个什么概念，两者之间有什么关系?53 将长度超过一个磁道容量的文件记录在同一个柱面上是否合理?54 采用定长数据块记录格式，直接寻址的最小单位是什么?寻址命令中

22、磁盘地址如何表示?55 假定每个扇区的容量 512B，每个磁道有 12 个扇区，寻道的平均等待时间为105ms ，试计算读出磁盘一个扇区中数据所用的平均时间。55 在一个段式存储管理系统中，逻辑地址为 32 位，其中高 16 位为段号，低 16 位为段内偏移，以下是段表(其中的数据均为十六进制，如表 7-1 所示)。以下是代码段的内容：试问：56 x 的逻辑地址为 10108，它的物理地址是多少?57 栈指针的当前地址是 70FF0，它的物理地址是多少 ?58 第一条指令的逻辑地址和物理地址各为多少?59 push x 指令的执行过程：将 SP(堆栈寄存器) 减 4，然后存储 x 的值。试问

23、x 被存储在什么地方(物理地址)?60 causin 指令的执行过程：先将当前 PC 值入栈，然后在 PC 内装入目标 PC 值。试问哪个值被压入栈了? 新的栈指针的值是多少 ?新的 PC 值是多少?61 语句“mov r2,4+(sp)”的功能是什么?61 有一个文件系统如图 72 所示。其中的方框表示目录，椭圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占 2B，共 4B)。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后 4B

24、供链接地址使用。下级文件在上级目录文件中的次序在图 7-2 中为从左至右。每个磁盘块有 512B，与普通文件的一页等长。 普通文件的文件控制块组织结构如图 7-3 所示，其中每个磁盘地址占 2B，前 10 个地址直接指示该文件前 10 页的地址。第 11 个地址指示一级索引表地址，一级索引表中每个磁盘地址指示一个文件页地址；第 12 个地址指示二级索引表地址，二级索引表中每个地址指示一个一级索引表地址；第 13 个地址指示三级索引表地址，三级索引表中每个地址指示一个二级索引表地址。 当前用户为 admin，当前目录为该用户的用户主目录，试问：62 dat 文件的绝对路径名和相对路径名。63 若

25、要读取顺序文件 a dat 中的某一页，最少启动磁盘多少次，最多启动磁盘多少次?64 如果已知顺序文件 a dat 的大小，试问如果要读取该文件的最后一个记录，是否能预估出启动磁盘的次数?若能，请详述过程。64 设表 7-2 为路由器 R 的不完整的路由表(其中下一跳给出的是路由器的端口)。路由器 R收到下述分别发往 6 个目的主机的数据报。 H1： 2013424578 H2：16611164129 H3：1661113572 H4：16611131168 H5：16611160239 H6： 19236873 试回答以下问题：65 表 7-2 中序号 14 的目的网络属于哪类网络?它们是由

26、什么网络划分来的 ?66 假如路由器 R1 端口 1 和路由器 R2 端口 2 的 IP 地址的主机号均为 5(十进制)，请给出它们的 IP 地址。67 基于(2)，试问到目的主机 H1H6 的下一跳 IP 地址是什么? 如果是直接交付，则请写出转发端口。计算机专业（基础综合）模拟试卷 61 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 ：非空循环单链表的尾结点指针应该指向链表头，即pnext=head，故正确。：head 指向头结点，headnext 就指向第一个结点。既然he

27、adnextnextRext=head，说明此循环链表共有 3 个结点(包含头结点)，而单链表中增加头结点仅仪是为了更方便地进行插入和删除操作，它并不存储线性表的元素，不能算为单链表结点，故此单链表的长度为 2，故错误。：静态链表中的指针所存储的不再是链表中的指针域，而是其下一个结点在数组中的位置，即数组下标，故正确。：将链表连接起来只需 O(1)的操作，但找到具有 m 个结点链表的尾结点需遍历该链表，所以时间复杂度应该为 O(m)，故错误。2 【正确答案】 B【试题解析】 利用栈求表达式的值时，需要设立运算符栈和运算数栈，下面仅举一例。例如，求 2(53)+62 的过程如表 63 所示，考生

28、可以自行对A、B、C、D 选项进行练习，运算数栈 S 的大小分别至少为 4、2、3、3，只有 B选项满足条件。3 【正确答案】 B【试题解析】 这种题目最好采用特殊值法，推导过程可能比较繁琐，如表 6-4 所示。 从表 6-4 中的规律可得出答案。 解题技巧：首先，应该先看选项，由于选项都是含有未知数的，由此应该是一个递推的题目。既然是递推的题目，就应该想到使用特殊值法一个个地排除。比如取 N=0，立马可以排除 A、B、C 选项。考生在考场遇到此类递推题千万不要一上来就推导公式。此题只要考生懂得使用特殊值代入法，就可以在最短的时间内选出答案。4 【正确答案】 D【试题解析】 首先，由于该二叉树

29、的结点个数为 4N+3，因此该二叉树一共有4N+2 个分支。其次，因为是完全二叉树，所以不可能同时有两个结点只有一个叶子结点。故 4N+2 个分支就肯定是来自 2N+1 个非叶子结点，总结点数是 4N+3，所以，叶子结点有 2N+2 个。5 【正确答案】 D【试题解析】 ：二叉树叶子结点的个数比度为 2 的结点的个数多 1，故正确。 总结：这个性质在选择题中常有体现(见下面的补充例题)，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为 n，则树中空指针的个数是多少?可以将所有空指针看做叶子结点，则图 6-6 中原有的所有结点都成了双分支结点。因此，可得空指针域的个数为树中所有结点个数加

30、1，即 n+1 个。 这个性质还可以扩展，即在一棵度为 m 的树中，度为 1 的结点数为 n1，度为 2 的结点数为 n2，度为m 的结点数为 nm，则叶子结点数 n0=1+n2+2n3+(m 一 1)nm。推导过程如下： 总结点=n 0+n1+n2+n3+nm 总分支数=1n1+2n2+mnm(度为 m 的结点引出 m 条分支) 总分支数=总结点数一1 将式 和式代入式并化简得 n0=1+n2+2n3+(m 一 1)nm ：最少结点的情况应该是除根结点层只有 1 个结点外，其余 4 层都有 2 个结点，因此结点总数为 2(51)+1=9，如图 6-6 所示，故正确。 总结：设高度为 h 的二

31、叉树只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为 2h1。 ：由二叉树的性质可知：n 0=n2+1，且完全二叉树度为 1 的结点个数要么为 0，要么为 1。又因为二叉树的总结点个数 n=n0+n1+n2。将 n0=n2+1 代入，可得 n=2n0+n1-1：由n=1 001，得到 2n0=1002+n1。 当 n1=1 时，无解。 当 n1=0 时，可解得n0=501。 故正确。 ：高度为 h 的完全二叉树中，第 1 层第 h 一 1 层构成一个高度为 h1 的满二叉树，结点个数为 2h-1-1。第 h 层至少有一个结点，所以最少的结点个数=(2 h-1-1)+1=2h

32、-1，故错误。6 【正确答案】 D【试题解析】 对于有 n 个结点，且高度为 n 的二叉树，必定是每一层有一个结点。除了根结点外，每一层的结点都将会有两种选择，即左孩子还是右孩子。根据排列的性质，应该一共有 2n-1 种情况，故选 D 选项。7 【正确答案】 B【试题解析】 ：无向图顶点的度即为一个顶点所引出边的条数，等价于一个顶点所含有的邻接顶点的个数，而不是与该顶点连通的顶点数(这样就会扩大范围，如图 6-7 所示) ，故错误。 顶点 V2 的度应该是 1，而如果度是按照图 6-7 中与该顶点连通的顶点数来定义，顶点 V2 的度应该是 3，明显错误。 ：n 个顶点的无向图要连通的话只需每个

33、顶点做一个结点，构成一棵树即可(解题关键)，并且此时是边最少的情况。对于树来说，顶点的个数比边要多 1，故正确。 ：显然，在无向图中，每条边(没有方向)对应于矩阵中与主对角线对称的两个“1”，因此无向图对应的邻接矩阵是对称的，故正确。 ：无向图的连通分量最少只有一个，即其自身；最多有 n 个，即该图没有边，则每个顶点构成一个连通分量，故正确。8 【正确答案】 C【试题解析】 ：强连通图是相对于有向图而言的，即在有向图 G 中，任何两个顶点都存在路径。所以最少的情况应该是 n 个顶点构成一个首尾相连的环，共有 n 条边，故 正确。：这个选项不细心的话很容易误选。在有向图中，边和路径是不同的概念。

34、有向图中顶点 A 和 B 之间存在边，不能说明 A 和 B 是互相连通的，所以说正确的表述应该是：强连通图是任何顶点到其他所有顶点都有路径，故错误。：完全有向图肯定是任何顶点到其他所有顶点都有路径，故正确。9 【正确答案】 C【试题解析】 首先通过散列函数 H(key)=key mod 11 的计算得知，37、95、27、14 分别插入到散列表中的 4、7、5、3 的位置。而 48 mod 11=4，但是此时 4 已经有元素了，根据线性探测再散列法处理冲突的原则，依次探测位置 4的下一个地址，直到此地址为空，发现 6 为空则插入，故选 C 选项。 补充：如果此题改为使用平方探测法，则又应该选择

35、哪一个选项? 提示：平方探测法的原理是设发生冲突的地址为 d，则平方探测法的探测序列为 d+12，d 一 12，d+2 2，d 一22，位置 4 不空时，下一个探测的位置应该为 5，发现又不空，则下一个探测的位置应该是 3，发现又不空。接着再探测位置 8，发现为空，将元素插入，故选 D选项。 平方探测法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。10 【正确答案】 C【试题解析】 当所有待排序元素的排序码都相等时，直接插入排序的排序码比较次数为 n 一 1，元素移动次数为 0；起泡排序的排序码比较次数为 n 一 1，元素移动

36、个数为 0：简单选择排序的排序码比较次数为 n(n 一 1)2，元素移动次数为0；基数排序采用静态链表存储待排序元素，用于分配的桶亦采用链式队列，排序码比较次数为 nxd(d 是排序码位数)，元素移动次数为 0，故排序速度最慢的是简单选择排序。11 【正确答案】 D【试题解析】 若先按 K1 值排序后，再按 K2 值排序，那么就会打乱原先 K1 值的次序，这不符合题目中 K1 优先的要求，因此排除 A 和 C。于是，需要先进行K2 的排序，在 K1 值相等情况下，要保持原来 K2 值的次序，即要求进行 K1 值排序的算法是稳定的，由于直接插入排序是稳定的，简单选择排序是不稳定的，因此应该先按

37、K2 值进行简单选择排序，再按 K1 值进行直接插入排序。12 【正确答案】 C【试题解析】 ：对于原码表示的基值为 4 的小数，规格化的形式是小数点后 2位不全为 0，故错误。 最“笨”的解题思路：基数 r=4，由于 1rM 1，即尾数的十进制绝对值为 0251。而(0000 010) 2=003125，故不是规格化数。 ：浮点数的溢出并不是由尾数来判断的，而是规格化后阶码超出所能表示的范围时，才表示溢出，故错误。 ：在浮点数的运算过程中，尾数如果出现01XXXX 和 10XXXX，则需要进行右规，并且只需进行一次右规尾数就会变成规格化数，但是左规操作可能不止一次，故正确。13 【正确答案】

38、 D【试题解析】 ：在原码一位乘算法过程中，符号位是不参加运算的，结果的符号位是被乘数的符号位和乘数的符号位异或的结果，故错误。：在原码一位乘算法过程中，由于参与操作的数是真值的绝对值，因此没有正负可言，故在原码一位乘法中运算过程中所有移位均是逻辑移位操作，即在高位添加 0，故错误。：由于在部分积相加中，可能导致两个小数相加大于 1，因此部分积至少需要使用 n+1 位寄存器，故错误。14 【正确答案】 A【试题解析】 采用分散刷新方式时，机器的存取周期中的一段用来读写，另一段用来刷新，故不存在死时间，但是存取周期变长了。异步刷新缩短了死时间，但死时间仍然存在。集中刷新是肯定有死时间，不需多解释

39、。15 【正确答案】 A【试题解析】 不妨设地址线和数据线的数目分别为 x 和 y。 只需要满足2xy=64K2，所以就有如下方案： 当 y=1 时，x=17； 当 y=2 时，x=16； 当 y=4 时，x=15； 当 y=8 时，x=14； 后面的就不必计算了，肯定比前面的引脚数目多。从以上分析可以看出，当数据线分别为 1 或 2 时，地址线和数据线引脚的数目之和为18，达到最小，并且有两种解答。16 【正确答案】 D【试题解析】 ：例如采用寄存器寻址的时候，指令的地址码字段就是寄存器编号。：例如 IO 指令的地址码就是设备端口地址。：例如直接寻址时，指令的地址码就是存储器的单元地址。：例

40、如立即数寻址时，指令的地址码就是数值本身。17 【正确答案】 C【试题解析】 相对寻址本身就是相对于本指令的地址进行上下浮动，所以相对寻址的区间范围和本指令的地址密切相关，其他 3 个选项都与本指令的地址无关。18 【正确答案】 A【试题解析】 CPU 主要由控制器和运算器两部分构成。控制器由程序计数器(PC)、指令寄存器(IR) 、指令译码器、时序产生器和操作控制器组成；运算器由算术逻辑单元(ALU)、累加器寄存器(AC) 、数据缓冲寄存器 (DR)和状态条件寄存器(PSW)组成，故没有地址译码器。可能的疑问点：有很多考生询问这个数据缓冲寄存器(DR)和主存数据缓冲寄存器(MDR)是不是同一

41、个寄存器，因为有些教材上的说法不是很严谨，MDR 和 DR经常混用。提示：其实 MDR 和 DR 是包含的关系。只是 DR 在主存里，所以才被叫做主存数据缓冲寄存器。19 【正确答案】 A【试题解析】 具体参考以下总结。(1)动态微程序：在一台微程序控制的计算机中，假如能根据用户的要求改变微程序，那么这台机器就具有动态微程序设计功能。动态微程序设计需要可写控制存储器的支持，否则难以改变微程序的内容，故需要将微程序存储在 RAM 中。 (2)静态微程序：对应一台计算机的机器指令只有一组微程序，而且这一组微程序设计好之后，一般无须改变而且也不好改变，故用 ROM 存储即可。(3)毫微程序：在普通的

42、微程序计算机中，从主存取出的每条指令是由放在控制存储器中的微程序来解释执行的，通过控制线对硬件进行直接控制。如果微程序并不直接控制硬件，而是通过存放在第 2 级控制存储器中的毫微程序来解释执行的，这个第 2 级控制存储器称为毫微存储器，而控制存储器是只读存储器。(4)水平型微程序：水平型微程序属于微程序，当然存储在控制存储器。20 【正确答案】 A【试题解析】 操作码字段是属于机器指令的一部分，不属于微指令的组成部分，其他 3 个选项很容易判断。21 【正确答案】 D【试题解析】 当每次计数从-n2开始时，所有设备被分为两部分，设备号为n2到 n 的设备优先级高于设备号为 0 到n/2一 1

43、的设备；且在这两部分内，是设备号小的优先级高，故 A、B、C 选项都是错误的。22 【正确答案】 D【试题解析】 通道的工作过程如下：(1)用户程序中使用访管指令进入操作系统的管理程序，由 CPU 通过管理程序组织一个通道程序，并使用 IO 指令启动通道(此后 CPU 就可以并行运行应用程序了)。(2)通道并行执行 CPU 为它组织的通道程序( 通道程序在主存中)，完成指定的数据输入输出工作。(3)通道程序结束后向 CPU 发出中断请求。CPU 响应这个中断请求后，第二次调用管理程序对输入输出中断请求进行处理。这样，每完成一次输入输出工作，CPU 只需要两次调用管理程序，大大减少了对用户程序的

44、打扰。 补充：在采用通道结构的系统中，也需要使用 IO 指令，但这种 IO 指令比较简单，它并不直接控制具体 IO 操作，只是负责通道的启动和停止、查询通道或设备的状态，从而控制通道去完成 IO 操作。23 【正确答案】 D【试题解析】 SPOOling 技术是为了解决独占设备问题，排除 A 选项。虚拟技术概念比较宽泛，在存储器管理中可以扩大主存容量，交换技术也是如此，排除 B 和 C。多道程序技术由于同时在主存中运行多个程序，提高了系统资源利用率。24 【正确答案】 A【试题解析】 本题可用排除法。 首先排除 B 选项。因为它是短作业优先算法，肯定是有利于短作业的。 然后排除 C 选项。RR

45、 兼顾长短作业，一般来说在时间片不是太长的情况下，对于短作业还是比较公平的。(时间片设的无限长，即变成了FCFS 算法) 最后排除 D 选项。 响应比=作业响应时间作业执行时间 =( 作业执行时间+作业等待时间)作业执行时间=1+作业等待时间作业执行时间 在作业等待时间相同的情况下，短作业的响应比是更高的，所以高响应比优先有利于短作业。 综上分析，本题选 A 选项。 知识点回顾： 表 65 给出了几种常见的进程调度算法特点，考生要在理解的基础上识记。25 【正确答案】 C【试题解析】 由于 a 为全局指针变量，即属于临界资源，访问 a 的代码都属于临界区，临界区应该在 Lock(m mutex

46、)和 UnLock(m mutex)之间，使各个进程互斥访问 a。但由于本题 free(a)在 Lock(m mutex)和 UnLock(m mutex)之外，因此是会出现错误的。举例：假设有进程 P1 和 P2，P1 进程申请的数组空间地址赋给 a 之后，还没有free 掉。P2 进程又申请了新的数组空间又把地址赋给 a，导致 P1 进程申请的空间地址丢失(即内存泄露) 。然后 P1 进程继续执行，P1 进程执行 free 操作，将 P2 进程中请的空间释放掉了，P2 进程继续执行，P2 进程执行 free 操作，free 操作访问了不属于 P2 进程的空间(之前已经被 P1 释放掉了)，

47、会发生内存越界访问。 知识点扩展 内存泄露：当以前分配的一片内存不再需要使用或无法访问时，但是并没有释放它，那么对于该进程来说，会因此导致总可用内存的减少，这时就出现了内存泄漏。内存越界访问：简单地说，进程访问了不属于该进程的内存空间。26 【正确答案】 B【试题解析】 通过阅读代码可知，变量 in 指向缓冲区中下一个空位，变量 out 指向缓冲区中的第一个非空位。BUFFER SIZE 是缓冲区最大能容纳的 item 数目。buffer 中，非空的位置范围是out，in1或者out，BUFFER SlZE10，in1，即有如图 68 所示的两种情况。 当 in=out 时，前一个操作肯定是运行了消费者进程(out 追上了 in)，因为生产者进程中，当遇到(in+1)BUFFER_SIZE=out 时就忙等，即生产进程无法使in=out，所以此时缓冲区中 item 数目应该是 0。 当(in+1) BUFFER_SlZE=out时，即 in 差一个空位就追上 out 了，此时缓冲区中 item 数目应该是BUFFER_