1、计算机专业（基础综合）模拟试卷 107 及答案与解析一、单项选择题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*(C-D)（B） (A-B)*C-D（C） (A-B*C)-D（D）(A-B)*(C-D)3 设有一个 n 阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B中，A11存放到 B1中(假定不用 0 下标)，那么 Bk存放的元素的行号是( ) 。（A）(k+1)3（B） (k+1) 3（C） (k+2) 3（D）(k+2)34 已知一棵 5 阶 B-树有 53 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( ) 。（A）3（B） 4（C） 5（D）65 下列说法中，正确的是
3、( )。具有 10 个叶子结点的二叉树中有 9 个度为 2 的结点设高度为 5 的二叉树上只有度为 0 和度为 2 的结点，则该二叉树巾所包含的结点数至少为 9一棵完全二叉树上有 1001 个结点，则可知叶子结点的个数为 501 个高度为 h 的完全二叉树最少有 2h 个结点（A）仅、（B）仅 、（C）仅 、（D）仅、6 在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则为使其平衡，应做( )型调整。（A）LL（B） RR（C） RL（D）LR7 下列关于无向图的说法中，正确的是( )。无向图中某个顶点的度是指图
4、中与该顶点连通的顶点数在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 n-1 条边无向图的邻接矩阵是对称矩阵具有 n 个顶点的无向图，最多有 n 个连通分量（A）仅、（B）仅 、（C）仅 （D）、8 下列关于强连通图的说法中，正确的是( )。n 个顶点构成的强连通图至少有 n 条边强连通图是任何顶点到其他所有顶点都有边完全有向图一定是强连通图（A）仅、（B）仅 、（C）仅 、（D）、9 假设初始为空的散列表的地址空间为(010)，散列函数为 H(key)=key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字 37、95、27、14、48，则最后一个关键字值 48 的插
5、入位置是( )。（A）4（B） 5（C） 6（D）810 设待排序元素序列所有元素的排序码都相等，则下列排序方法中排序速度最慢的是( )。（A）直接插入排序（B）起泡排序（C）简单选择排序（D）基数排序11 假设有 5 个初始归并段，每个归并段有 20 个记录，采用 5 路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过( )。（A）20（B） 300（C） 396（D）50012 下列说法中，错误的是( )。设浮点数的基数为 4，尾数用原码表示，则 0000010 为规格化数浮点数运算中，运算结果超出尾数表示范围则表示溢出任何情况下，浮点数的右规操作最多只会进行一次（A）仅、（B）
6、仅 、（C）仅 、（D）、和13 已知两个正浮点数，N 1=2j1S，N 2=2j2S2，当下列 ( )成立时，N 1N2。（A）S 1S 2（B） j1j 2（C） S1 并 S2 均为规格化数，且 j1j 2（D）S 1 和 S2 均为规格化数，且 S1S 214 某容量为 256MB 的存储器由若干 16M8bitDRAM 芯片构成，该 DRAM 芯片的地址引脚和数据引脚总数是( )。（A）20（B） 24（C） 32（D）3615 现有一 64K2bit 的存储器芯片，欲设计具有同样存储容量的存储器，有( )种方法可以合理地安排地址线和数据线引脚的数目，且使两者之和最小。（A）2（B）
7、 3（C） 4（D）516 某计算机有 30 个通用寄存器，采用 32 位定长指令字，操作码字段(不含寻址方式)为 8 位，Add 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则 Add 指令中偏移量的取值范围是( )。（A）-4096 4095（B） -20482047（C） -10231024（D）-3071 307217 与本指令的地址有关的寻址方式是( )。（A）寄存器寻址（B）直接寻址（C）相对寻址（D）间接寻址18 假定执行最复杂的指令需要完成 6 个子功能，分别由对应的功能部件 AF 来完成，每个功能部件所
8、花的时间分别为 80ns、40ns、50ns、70ns 、20ns、30ns ，流水线寄存器延时为 20ns，现把最后两个功能部件 E 和 F 合并，以产生一个五段流水线。该五段流水线的时钟周期至少是( )。（A）70ns（B） 80ns（C） 90ns（D）100ns19 在微程序控制器中，执行指令微程序的首条微指令地址是由( )得到的。（A）程序计数器 PC（B）前条微指令（C） UPC+1（D）指令操作码映射20 指令流水线中出现数据相关时流水线将受阻，( )可解决数据相关问题。（A）增加硬件资源（B）采用旁路电路技术（C）采用分支预测技术（D）AC 都可以21 在计数器定时查询方式下，
9、若每次计数从n2开始，则( )。（A）设备号小的优先级高（B）每个设备使用总线的机会相等（C）设备号大的优先级高（D）以上说法都不正确22 以下 4 个步骤在通道过程中的正确顺序是( )。组织 IO 操作向 CPU 发出中断请求编制通道程序启动 IO 通道（A）（B） （C） （D）23 下列关于批处理技术和多道程序设计技术说法中，正确的是( )。批处理系统的最主要缺点是不能并发执行所谓多道程序设计，是指每一个时刻有若干个进程在执行引入多道程序设计的前提条件之一是系统具有中断功能采用多道程序设计的系统中，系统的程序道数越多，系统的效率越高（A）仅、（B）仅 、（C）仅 （D）仅、24 假设系统
10、中所有进程是同时到达，则最不利于短作业的进程调度算法是( )。（A）FCFS（B） SPF（C） RR（D）高响应比优先25 Pi() Lock(m mutex)； 含义为获取互斥信号量a=new int100； 开辟一个大小为 100 的整型数组空间，并用全局指针变量 a 保存空间地址UnLock(m_mutex)；free(a)； 释放数组空间，且 a 的值不改变有多个优先级相同的进程 Pi。试问下列同时运行多个进程 Pi，可能会出现的错误是( )。（A）内存泄露（B）内存越界访问（C）内存泄露和内存越界访问（D）无26 生产者进程和消费者进程代码如下，生产者进程有一个局部变量nextPr
11、oduced，以存储新产生的新项：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=(out+1)BUFFER SIZE；*consume the item in nextConsumed*当 in=out
12、和(in+1) BUFFER_SIZE=out 条件成立的时候，缓冲区中 item 数目各是( )。（A）0，BUFFER_SIZE（B） 0，BUFFER_SIZE-1（C） BUFFER_SIZE-1，0（D）BUFFER_SIZE，027 某操作系统采用可变分区分配存储管理方法，操作系统占用低地址部分的126KB。用户区大小为 386KB，且用户区始址为 126KB，用空闲分区表管理空闲分区。若分配时采用分配空闲区高地址的方案，且初始时用户区的 386KB 空间空闲，对下述申请序列：作业 1 申请 80KB，作业 2 申请 56KB，作业 3 申请120KB，作业 1 完成并释放空间，作
13、业 3 完成并释放空间，作业 4 申请 156KB，作业 5 申请 80KB。如果用首次适应算法处理上述序列，最后的空闲分区的首地址为( )。（A）126（B） 432（C） 256（D）22028 在分页式系统中，分页由( )实现。（A）程序员（B）编译器（C）系统调用（D）系统29 在页式虚拟管理系统中，假定驻留集为 m 个页帧 (初始所有页帧均为空)，在长为 p 的引用串中具有 n 个不同页号(nm)，对于 FIFO、LRU 两种页面替换算法，其缺页中断的次数的范围分别为( )。（A）m ，p和n，p（B） m，n和n ，p（C） n，p 和m ，n（D）n ，p和n，p30 设有一个记
14、录式文件，采用链接分配方式，逻辑记录的固定长度为 100B，记录类型是英文文本(例如：WelcOmE to TiaNqin!)，在磁盘上存储时采用成组分解技术。盘块长度为 512B。如果该文件的目录项已经读入内存，用户现在需要规范第 22 个逻辑记录中的大小写格式，该操作共需启动硬盘的次数为( )。（A）1（B） 2（C） 5（D）631 考虑一个有如下参数的磁盘：估计访问一个磁盘扇区的平均时间 Taccess 约为( )。（A）4ms（B） 8ms（C） 13ms（D）17ms32 如果 IO 所花费的时间比 CPU 的处理时间短得多，则缓冲区 ( )。（A）最有效（B）几乎无效（C）均衡（
15、D）以上都不是33 透明网桥的 MAC 地址表要记录的信息有( )。目的站 MAC 地址 源站 MAC 地址端口号帧到达时间帧转发标记（A）仅、（B）仅 、（C）仅 、（D）仅、34 下列说法中，错误的是( )。假设帧序号有 3 位，采用连续 ARQ 协议，发送窗口的最大值为 4对于窗口大小为 n 的滑动窗口，最多可以有 n 帧已发送但没有确认在后退 N 帧协议中，如果发送窗口的大小是 16，那么至少需要 4 位的序列号才能保证协议不出错（A）仅、（B）仅 （C）仅 、（D）、35 假设某网络最远的两个站点长度为 10km，数据传输率为 10Mbits 的CSMACS 以太网，信号传播速度为
16、200ms。那么该网络的最小帧长为( )。（A）20bit（B） 200bit（C） 100bit（D）1000bit36 图 6-1 是网络地址转换 NAT 的一个实例，根据图 6-1 中的信息，标号为 的方格中的内容应为( ) 。（A）S=135211，80（B） S=135211，80D=202011，5001 D=19216811，3342（C） S=202011，5001 （D）S=19216811，3342D=135211，80 D=135211，8037 对于 193100600 网络，若子网掩码设置成 255255255192，则每个子网最多可接入( ) 台主机。（A）256（
17、B） 254（C） 62（D）3038 在 IP 分组的传输过程中，以下 IP 分组首部中的字段保持不变的是( )。总长度头部检验和生存时间源 IP 地址（A）仅、（B）仅 （C）仅 、（D）仅、39 有一个 TCP 连接，当其拥塞窗口为 64 个分组大小时超时。假设网络的 RTT 是固定的 3s，不考虑比特开销，即分组不丢失，则系统在超时后处于慢启动阶段的时间是( ) 。（A）12s（B） 15s（C） 18s（D）21s40 某网络允许的最大报文段的长度为 128B，序号用 8bit 表示，报文段在网络中的寿命为 30s，则每一条 TCP 连接所能达到的最高数据率为 ( )。（A）46kb
18、its（B） 189kbits（C） 87kbits（D）256kbits二、综合应用题41-47 小题，共 70 分。40 设哈希函数为：H(key)=key mod 13，其中 key 为关键字，mod 为取模运算，试用关键字序列39，25，15 ，54，26，24，14，21，37，38 构造哈希表。41 用链地址法处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。42 设表地址范围为 013，用线性探测再散列法处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。42 输入一整数数组5，7 ，6，9，1
19、1，10，8 ，该整数序列为图 2-2 所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。要求：43 给出算法的基本设计思想。44 根据设计思想，采用 C、C+或 Java 语言描述算法，关键之处给出注释。45 说明你所设计算法的时间复杂度。45 某字长为 8 位的计算机中，带符号整数采用补码表示，x=-68，y=-80，x 和 v分别存放在寄存器 A 和 B 中，请回答下列问题(最终要求用十六进制表示二进制序列)。46 寄存器 A 和
20、B 中的内容分别是什么?47 若 x 和 y 相加后的结果存放在寄存器 C 中，则寄存器 C 中的内容是什么? 运算结果是否正确? 此时，溢出标志 OF、符号标志 SF 和零标志 ZF 各是什么?加法器最高位的进位 Cn 是什么?48 若 x 和 y 相减后的结果存放在寄存器 D 中，则寄存器 D 中的内容是什么?运算结果是否正确? 此时，溢出标志 OF、符号标志 SF 和零标志 ZF 各是什么?加法器最高位的进位 Cn 是什么?49 若将加法器最高位的进位 Cn 作为进位标志 CF，能否直接根据 CF 的值对两个带符号整数的大小进行比较?49 假定一个计算机系统中有 1 个 TLB 和 1
21、个 L1 Data Cache。该系统按字节编址，虚拟地址 16 位，物理地址 12 位，页大小为 128B，TLB 为 4 路组相连，共有 16个页表项，L1 Data Cache 采用直接映射方式，块大小为 4B，共 16 行。在系统运行到某一时刻时，TLB、页表和 L1 Data Cache 中的部分内容如图 2-3 所示。试回答下列问题：50 虚拟地址中哪几位表示虚拟页号?哪几位表示页内偏移量? 虚拟页号中哪几位表示 TLB 标记? 哪几位表示 TLB 索引?51 物理地址中哪几位表示物理页号?哪几位表示页内偏移量?52 主存(物理) ，地址如何划分成标记字段、行索引字段和块内地址字段
22、?53 CPU 从地址 067AH 中取出的值为多少?说明 CPU 读取地址 067AH 中内容的过程。53 在单 CPU 和两台输入输出设备(11，12)的多道程序设计环境下，同时投入 3个作业 J1、J2 和 J3 运行。这 3 个作业对 CPU 和输入输出设备的使用顺序和时间如下所示。J1：12(30ms)；CPU(10ms)；11(30ms)；CPU(10ms)；12(20ms)J2：11(20ms)；CPU(20ms)；12(40ms)J3：CPU(30ms) ；11(20ms)；CPU(10ms)；11(10ms)假定 CPU、11、12 都能并行工作，J1 优先级最高，J2 次之
23、，J3 优先级最低，优先级高的作业可以抢占优先级低的作业的 CPU，但不抢占 11 和 12。试求：54 3 个作业从投入到完成分别需要的时间。55 从投入到完成的 CPU 利用率。56 I O 设备利用率。56 下列程序实现了矩阵乘法。int A100150；int B150200；int Ci00200；for(i=0；i100 ，i+)for(j=0；j 200；j+)for(k=0；k150；k+)Cij+=Aik*Bkj；假设矩阵 A 和矩阵 B 的初值已经初始化过，矩阵 C 初始化为 0，各矩阵均以页为单位连续存放(且假定是行优先存储)。又假定一个整数占用 1 个字，代码以及变量
24、i、j 和 k 存放在其他页面里，并且存取变量 i、j 和 k 时不存在缺页问题。主存初始为空，在请求分页存储管理中，页面淘汰算法为 FIFO。57 作业分配 10 个页面，每个页面为 100 字，给矩阵 A、B 和 C 使用。问执行上面的程序时，缺页次数是多少?当执行完程序时，留在内存的 10 个页面各属于哪些矩阵?58 当作业分配两个页面，每个页面为 500 字，给矩阵 A、B 和 C 使用。问执行上面的程序时，缺页次数是多少?当执行完程序时，留在内存的 10 个页面各属于哪些矩阵? (注：c+=c+a*b 的执行顺序为：读 a、读 b、计算 ab、读 c、计算 c+ab、写 c)58 假
25、设主机 1(在图 2-4 中网络 1 以太网上)是可以运行 IE 浏览器的某客户机，主机4(在图 2-4 中网络 3 以太网上)为天勤论坛 Web 服务器(IP 地址为 202197115)，主机 5(在图 2-4 中网络 2 的 FDDI 主干网上)为天勤论坛 DNS 服务器，该 DNS 服务器上有天勤论坛 Web 站点的域名地址到 IP 地址解析。其中，路由器 1 以太网端口(a 端口) 的 MAC 地址是 E3，IP 地址是 202197 123，子网掩码是2552552550；路由器 1 的 FDDI 端口(c 端口)的 MAC 地址是 F1，IP 地址是202197101，子网掩码是
26、 2552552550。路由器 2 的以太网端口(b 端口)的 MAC 地址是 E4，IP 地址是 202197114，子网掩码是2552552550；路由器 2 的 FDDI 端口(c 端口)的 MAC 地址是 F3，IP 地址是202197102，子网掩码是 2552552550，其他站点的 IP 地址和 MAC 地址如图 2-4 所示。试问：59 为了使主机 1 能够通过域名访问天勤论坛 Web 服务器，主机 1 上的 IP 地址、子网掩码、默认网关 IP 地址、DNS 服务器地址应该如何配置?60 假设主机 1 使用的 1234 的 UDP 端口与 DNS 服务器通信，使用的 1235
27、 的 TCP端口与 Web 服务器通信，请写出主机 1 发给 DNS 服务器和 Web 服务器的 UDP 报文和 TCP 报文中的源端口号和目的端口号、IP 报文中的源 IP 地址和目的 IP 地址以及在 3 个物理网络中发送的 MAC 帧中的源 MAC 地址和目的 MAC 地址。61 从(2)的分析中，得出了什么结论? 请阐述。计算机专业（基础综合）模拟试卷 107 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 ：非空循环单链表的尾结点指针应该指向链表头，即pnext=head
28、，故正确。：head 指向头结点，headnext 就指向第一个结点。既然headnextnextnext=head，说明此循环链表共有 3 个结点(包含头结点) ，而单链表中增加头结点仅仅是为了更方便地进行插入和删除操作，它并不存储线性表的元素，故不能算为单链表结点，故此单链表的长度为 2，故错误。：静态链表中的指针所存储的不再是链表中的指针域，而是其下一个结点在数组中的位置，即数组下标，故正确。：将链表连接起来只需 O(1)的操作，但找到具有 m 个结点链表的尾结点需遍历该链表，所以时间复杂度应该为 O(m)，故错误。2 【正确答案】 B【试题解析】 利用栈求表达式的值时，需要设立运算符栈
29、和运算数栈，下面仅举一例。例如，求 2(5-3)+62 的过程如表 6-2 所示。从上述的计算过程中，考生可以自行对 A、B、C、D 选项进行练习，运算数栈 S 的大小分别至少为 4、2、3、3，只有B 选项满足条件。3 【正确答案】 B【试题解析】 这种题目最好采用特殊值法，推导过程可能比较繁琐，见表 6-3。从表 6-3 中的规律可得出答案。4 【正确答案】 B【试题解析】 根据 B-树定义，m 阶 B-树除根结点之外，所有非终端结点至少有m2=3 个子树，即至少有 2 个关键字。那么在每个结点的关键字最少的情况下，根结点关键字个数为 1，其他的结点关键字个数都为 2。又第一层有 1 个结
30、点，第二层有 2 个结点，第三层有 23 个结点，第四层有 233 个结点。即：11+22+232+2332=53，根结点加非终端刚好四层，叶子结点那一层不算，故树的深度为 4。5 【正确答案】 D【试题解析】 ：二叉树叶子结点的个数比度为 2 的结点的个数多 1，故 I 正确。 总结：这个性质在选择题中常有体现，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为 n，则树中空指针的个数是多少?我们可以将所有的空指针看作叶子结点，则图中原有的所有结点都成了双分支结点。因此可得空指针域的个数为树中所有结点个数加 1，即 n+1 个。 这个性质还可以扩展，即在一棵度为 m 的树中，度为 1 的
31、结点数为 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(5-1)+1=9。如图 6-4 所示，故正确。 ：由二叉树的性质可知：n 0=n2+1，且完全二叉树度为 1 的结点个数要么为 0，要么为 1。又因为二叉树
32、的总结点个数 n=n0+n1+n2。将 n0=n2+1 代入，可得 n=2n0+n1-1；由于 n=1001，得到 2n0=1002+n1。 当 n1=1 时，无解。 当 n1=0 时，可解得n0=501 故正确。 ：高度为 h 的完全二叉树中，第 1 层第 h-1 层构成一个高度为 h-1 的满二叉树，结点个数为 2h-1-1。第 h 层至少有一个结点，所以最少的结点个数=(2 h-1-1)+1=2h-1，故错误。6 【正确答案】 D【试题解析】 既然最低不平衡结点是 A，则以 A 为根的子树不平衡的情况有 4 种，如图 6-5 所示。 又因为 A 的左孩子的平衡因子为-1，右孩子的平衡因子
33、是 0，只有第 2 个符合，所以应当做 LR 型调整。7 【正确答案】 B【试题解析】 ：无向图顶点的度即为一个顶点所引出边的条数，等价于一个顶点所含有的邻接顶点的个数，而不是与该顶点连通的顶点数(这样就会扩大范围，如图 6-6 所示) ，故错误。 顶点 V2 的度应该是 1，而如果度是按照图 6-6 中与该顶点连通的顶点数来定义，顶点 V2 的度应该是 3，明显错误。：n 个顶点的无向图要连通的话只需每个顶点做一个结点，构成一棵树即可(解题关键)，并且此时是边最少的情况。对于树来说，顶点的个数比边要多 1，故正确。 ：显然，在无向图中，每条边(没有方向)对应于矩阵中与主对角线对称的两个“1”
34、，因此无向图对应的邻接矩阵是对称的，故正确。 ：无向图的连通分量最少只有一个，即其自身；最多有 n 个，即该图没有边，则每个顶点构成一个连通分量，故正确。8 【正确答案】 C【试题解析】 ：强连通图是相对于有向图而言的，即在有向图 G 中，任何两个顶点都存在路径。所以最少的情况应该是 n 个顶点构成一个首尾相连的环，共有 n 条边，故 正确。：这个选项不细心的话很容易误选。在有向图中，边和路径是不同的概念。有向图中顶点 A 和 B 之间存在边，不能说明 A 和 B 是互相连通的，所以说正确的表述应该是强连通图是任何顶点到其他所有顶点都有路径，故错误。：完全有向图肯定是任何顶点到其他所有顶点都有
35、路径，故正确。9 【正确答案】 C【试题解析】 首先通过散列函数 H(key)=key mod 11 的计算得知，37、95、27、14 分别插入到散列表中的 4、7、5、3 的位置。而 48 mod 11=4，但是此时 4 已经有元素了，根据线性探测再散列法处理冲突的原则，依次探测位置 4的下一个地址，直到此地址为空，发现 6 为空则插入，故选 C 选项。10 【正确答案】 C【试题解析】 当所有待排序元素的排序码都相等时，直接插入排序的排序码比较次数为 n-1，元素移动次数为 0；起泡排序的排序码比较次数为 n-1，元素移动个数为 0；简单选择排序的排序码比较次数为 n(n-1)2，元素移
36、动次数为 0；基数排序采用静态链表存储待排序元素，用于分配的桶亦采用链式队列，排序码比较次数为 nd(d 是排序码位数 )，元素移动次数为 0，故排序速度最慢的是简单选择排序。11 【正确答案】 B【试题解析】 假设采用 k 路平衡归并排序算法，则败者树的高度为log 2k+1。在每次调整后，找下一个具有最小排序码记录时，最多做log 2k次排序码比较。由题意可知，总共有 100 个记录，所以总的比较次数不超过 100log25=300。12 【正确答案】 C【试题解析】 ：对于原码表示的基值为 4 的小数，规格化的形式是小数点后 2位不全为 0，故错误。：浮点数的溢出并不是由尾数来判断的，而
37、是规格化后阶码超出所能表示的范围时，才表示溢出，故错误。：在浮点数的运算过程中，尾数如果出现 01XXXX 和 10XXXX，则需要进行右规，并且只需进行一次右规尾数就会变成规格化数，但是左规操作可能不止一次，故正确。13 【正确答案】 C【试题解析】 S 1 和 S2 均为规格化数， 12S 11，12S 21，即S11 2S2 2。 j 1j 2，即 j1j2+1。N 1=2j1S12j2+1S22=2 j2S2=N2。14 【正确答案】 A【试题解析】 很多不了解 DRAM 引脚结构的同学很可能会得出 24+8=32 的结果，其实这是不正确的，在高分笔记当中讲过半导体存储芯片的译码驱动方
38、式，其中介绍了重合法，将存储单元分成行和列，然后分别通过行地址线和列地址线来确定行列地址从而确定一个单元，这里 DRAM 采用引脚复用，将行地址线和列地址线合用作一组，只不过在译码时，需要发送两次地址信号(相当于一次行地址，一次列地址)，从而减少了 DRAM 的引脚总数，便于设计 DRAM：因此这里地址空间是 16M，需要 24 个地址位来标识，分为两次发送，则地址引脚数为 12，故地址引脚和数据引脚总数为 12+8=20。15 【正确答案】 A【试题解析】 不妨设地址线和数据线的数目分别为 x 和 y。 只需要满足2xy=64K2，所以就有如下方案： 当 y=1 时，x=17 ； 当 y=2
39、 时，x=16； 当 y-4时，x=15 ； 当 y=8 时，x=14； 后面的就不要计算了，肯定比前面的引脚数目多。从以上分析可以出看，当数据线分别为 1 或 2 时，地址线和数据线引脚的数目之和为 18，达到最小，并且有两种解答。16 【正确答案】 B【试题解析】 首先可以直接排出 C、D 选项，因为无论偏移量是多少位，由于偏移量是采用补码表示的，根据补码的特性，它比源码表示的数多一位，而且多出来的就是补码的最小值。因此偏移量的最小值一定是一个偶数。操作码占 8 位，两个操作数具有两种不同的寻址方式，则需要 2 位寻址特征位，另外一共有 30 个寄存器，故需要 5 位来标识选择哪个寄存器，
40、所以偏移量的位数=32-8-2-5-5=12，而 12位的带符号的补码所能表示的数的范围为-20482047。17 【正确答案】 C【试题解析】 相对寻址本身就是相对于本指令地址进行上下浮动，所以相对寻址的区间范围和本指令的地址密切相关，其他 3 个选项都与本指令的地址无关。18 【正确答案】 D【试题解析】 指令的各个子功能在不同的部件中是并行执行的，因此执行这条指令的时间一定是各个子功能中所花的最长时间，当前最长时间为 80ns，当合并 E和 F 这两个功能部件之后，合并子功能执行时间为 50ns，因此最长的时间还是80ns，再加上 20ns 的寄存器延迟，所以五段流水线的时钟周期至少是
41、100ns。19 【正确答案】 D【试题解析】 本题问的是微程序中首条微指令的地址，稍不注意就可能误选 B，微程序是用来解释指令的，通过指令操作码的内容来区别指令，然后根据指令操作码映射找到对应解释这个指令的微程序段。因此首条微指令的地址是由指令操作码映射而来的。20 【正确答案】 B【试题解析】 在流水线处理器中处理数据相关问题有两种方法：一种是暂停相关指令的执行，即暂停流水线，直到能够正确读出寄存器操作数为止：另一种是采用旁路电路技术，即采用专门的数据通路，直接把结果送到 ALU 的输入端，也就是把内部数据前推，即不必等待某条指令的执行结果写回到寄存器后，再从寄存器取出结果，而是直接将执行
42、结果通过专用通路送至需要该结果的地方。21 【正确答案】 D【试题解析】 当每次计数从n2开始时，所有设备被分为两部分，设备号为n2到 n 的设备优先级高于设备号为 0 到n2-1 的设备；且在这两部分内，却是设备小的优先级高，故 A、B、C 选项都是错误的。22 【正确答案】 D【试题解析】 通道的工作过程如下：(1)用户程序中使用访管指令进入操作系统的管理程序，由 CPU 通过管理程序组织一个通道程序，并使用 IO 指令启动通道(此后 CPU 就可以并行运行应用程序了)。(2)通道并行执行 CPU 为它组织的通道程序( 通道程序在主存中)，完成指定的数据输入输出工作。(3)通道程序结束后向
43、 CPU 发出中断请求。CPU 响应这个中断请求后，第二次调用管理程序对输入输出中断请求进行处理。这样，每完成一次输入输出工作，CPU 只需要两次调用管理程序，大大减少了对用户程序的打扰。23 【正确答案】 C【试题解析】 错误，批处理系统的最主要缺点是缺乏交互性。的表述肯定是错的，多道批处理系统就可以并发执行多个程序。这里多道是指允许多个进程同时驻留在主存中，按照某种原则分派处理机，逐个执行这些程序。这里其实还考查了并发的概念。并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。错误，多道程序设计是指把多个程序同时存放在内存中，使它们同时处于运行状态。但是
44、，在单处理机环境中，同一时刻只有一个进程在执行。正确，有了中断后才能实现进程间并发，进程间并发才有可能把多个进程装入到内存实现多道程序技术。错误，程序道数如果过多的话，会导致每个程序分配到的内存不够，很多程序所需的程序和代码需要临时从磁盘调入到内存，系统会频繁地处于 IO 状态中，导致系统效率降低。24 【正确答案】 A【试题解析】 本题可用排除法。首先排除 B 选项。因为它是短作业优先算法，肯定是有利于短作业的。然后继续排除 C 选项。RR 兼顾长短作业，一般来说在时间片不是的太长的情况下，对于短作业还是比较公平的。(时间片设的无限长，即变成了 FCFS 算法。)最后排除 D 选项。响应比=
45、作业响应时间作业执行时间=(作业执行时间+作业等待时间)作业执行时间=1+作业等待时间作业执行时间在作业等待时间相同的情况下，短作业的响应比是更高的，所以高响应比优先有利于短作业。综上分析，本题选 A 选项。25 【正确答案】 C【试题解析】 由于 a 为全局指针变量，即属于临界资源，访问 a 的代码都属于临界区，临界区应该在 Lock(m_mutex)和 UnLock(m_mutex)之间，使各个进程互斥访问 a。但由于本题 free(a)在 Lock(m_mutex)和 UnLock(m_mutex)之外，所以是会出现错误的。26 【正确答案】 B【试题解析】 通过阅读代码可知，变量 in
46、 指向缓冲区中下一个空位，变量 out 指向缓冲区中的第一个非空位。BUFFER_SIZE 是缓冲区最大能容纳的 item 数目。buffer 中，非空的位置范围是out，in-1或者out，BUFFER_SIZE-10，in-1，即有如图 6-7 所示的两种情况。当 in=out 时，前一个操作肯定是运行了消费者进程(out 追上了 in)，因为生产者进程中，当遇到 (in+1)BUFFER_SIZE=out 时就忙等，即生产进程无法使 in=out，所以此时缓冲区中itern 数目应该是 0。 当(in+1)BUFFER_SIZE=out 时，即 in 差一个空位就追上out 了，此时缓冲
47、区中 itern 数目应该是 BUFFER_SIZE-1。 所以本题正确答案是B 选项。27 【正确答案】 A【试题解析】 本题需要注意的有，一般首次适应算法是要求空闲分区链以地址递增的次序链接，本题相反，是以地址递减的顺序链接的。为描述方便，本题用“(分区首址，分区长度)”的形式描述系统中的分区。由题中所给条件可知，最初系统中只有一个空闲区，大小为 386KB，始址为 126KB，即(126KB，386KB)。 采用首次适应算法的操作流程如表 6-5 所示。28 【正确答案】 D【试题解析】 分页由操作系统自动实现，对用户透明。29 【正确答案】 D【试题解析】 缺页中断的原因是当前访问的页不在内存，需将该页调入主存。此时不管主存是否己满(已满则先调出一页)，都要发生一次缺页中断。即无论怎么安排，n 个不同的页号在首次进入主存时必须要发生一次缺页中断，总共发生 n 次，这就是缺页中断的下限。虽然不同页号数位 n，小于或等于总长度 p(访问串可能会有一些页重复出现)，但驻留集 mn，所以可能会有某些页进入主存后又被调出主存，当再次访问时又发生一次缺页中断的现象，即有些页可能会出现多次缺页中断。极端情况是每访问一个页号时，该页都不在主存，这样共发生了 p 次故障。所以无论对于 FIFO 或者 LRU 替换算法，其缺页中断的上限均为 p，下限均为
