2014年计算机考研真题.docx

2014年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。 1下列程序段的时间复杂度是。count=0; for(k=1;k=n;k*=2)for(j=1;j=n;j+)count+; A O(log2n)BO(n) CO(nlog2n)DO(n2)2假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是。 A+(*-B+(-*C/+(*-*D/+-* 3循环队列放在一维数组A0M-1中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是。A队空：end1=end2；队满：end1=(end2+1)modM B队空：end1=end2；队满：end2=(end1+1)mod(M-1)C队空：end2=(end1+1)modM；队满：end1=(end2+1)modMD队空：end1=(end2+1)modM；队满：end2=(end1+1)mod(M-1)4若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是。 Ae、cBe、aCd、cDb、a 5将森林F转换为对应的二叉树T，F中叶结点的个数等于。AT中叶结点的个数 BT中度为1的结点个数 CT中左孩子指针为空的结点个数 DT中右孩子指针为空的结点个数65个字符有如下4种编码方案，不是前缀编码的是。A01,0000,0001,001,1B011,000,001,010,1C000,001,010,011,100D0,100,110,1110,1100 7对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是。A3,1,2,4,5,6 B3,1,2,4,6,5 C3,1,4,2,5,6 D3,1,4,2,6,5 8 用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是 。 A 存储效率 B散列函数 C装填(装载)因子 D平均查找长度 9 在一棵具有15个关键字的4阶B树中，含关键字的结点个数最多是 。 A5 B6 C10 D15 10 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是 。 A2 B3 C4 D5 11 下列选项中，不可能是快速排序第2趟排序结果的是 。 A2,3,5,4,6,7,9 B2,7,5,6,4,3,9 C3,2,5,4,7,6,9 D4,2,3,5,7,6,9 12 程序P在机器M上的执行时间是20秒，编译优化后，P执行的指令数减少到原来的70%，而CPI增加到原来的1.2倍，则P在M上的执行时间是 。 A8.4秒 B11.7秒 C14秒 D16.8秒 13 若x=103，y=-25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是 。 Ax+y B-x+y Cx-y D-x-y 14 float型数据据常用IEEE754单精度浮点格式表示。假设两个float型变量x和y分别存放在32位寄存器f1和f2中，若(f1)=CC90 0000H，(f2)=B0C0 0000H，则x和y之间的关系为 。 A xy且符号相同 Bxy且符号相同 Dxy且符号不同 15 某容量为256MB的存储器由若干4M8位的DRAM芯片构成，该DRAM芯片的地址引脚和数据引脚总数是 。 A19 B22 C30 D3616 采用指令Cache与数据Cache分离的主要目的是 。 A 降低Cache的缺失损失 B提高Cache的命中率 C降低CPU平均访存时间 D减少指令流水线资源冲突 17 某计算机有16个通用寄存器，采用32位定长指令字，操作码字段（含寻址方式位）为8位，Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store指令中偏移量的取值范围是 。 A -32768 +32767 B-32767 +32768 C-65536 +65535 D-65535 +65536 18 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微指令，各指令对应的微程序平均由4条微指令组成，采用断定法（下地址字段法）确定下条微指令地址，则微指令中下址字段的位数至少是 。 A5 B6 C8 D9 19 某同步总线采用数据线和地址线复用方式，其中地址/数据线有32根，总线时钟频率为66MHz，每个时钟周期传送两次数据(上升沿和下降沿各传送一次数据)，该总线的最大数据传输率(总线带宽)是 。 A132 MB/s B264 MB/s C528 MB/s D1056 MB/s 20 一次总线事务中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元读出或写入多个数据。这种总线事务方式称为 。 A 并行传输 B串行传输 C突发传输 D同步传输 21 下列有关I/O接口的叙述中，错误的是 。A 状态端口和控制端口可以合用同一个寄存器 BI/O接口中CPU可访问的寄存器称为I/O端口 C采用独立编址方式时，I/O端口地址和主存地址可能相同 D采用统一编址方式时，CPU不能用访存指令访问I/O端口 22 若某设备中断请求的响应和处理时间为100ns，每400ns发出一次中断请求，中断响应所允许的最长延迟时间为50ns，则在该设备持续工作过程中，CPU用于该设备的I/O时间占整个CPU时间的百分比至少是 。 A12.5% B25% C37.5% D50%23 下列调度算法中，不可能导致饥饿现象的是 。 A 时间片轮转 B静态优先数调度 C非抢占式短作业优先 D抢占式短作业优先 24 某系统有n台互斥使用的同类设备，三个并发进程分别需要3、4、5台设备，可确保系统不发生 死锁的设备数n最小为 。 A9 B10 C11 D12 25 下列指令中，不能 在用户态执行的是 。 A trap指令 B跳转指令 C压栈指令 D关中断指令 26 一个进程的读磁盘操作完成后，操作系统针对该进程必做的是 。A 修改进程状态为就绪态 B降低进程优先级 C给进程分配用户内存空间 D增加进程时间片大小 27 现有一个容量为10GB的磁盘分区，磁盘空间以簇(Cluster)为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位(bit)标识一个簇是否被分配，则存放该位图所需簇的个数为 。 A80 B320 C80K D320K 28 下列措施中，能加快虚实地址转换的是 。 I增大快表(TLB)容量 II让页表常驻内存 III增大交换区(swap) A 仅I B仅II C仅I、II D仅II、III29 在一个文件被用户进程首次打开的过程中，操作系统需做的是 。 A 将文件内容读到内存中 B将文件控制块读到内存中C修改文件控制块中的读写权限 D将文件的数据缓冲区首指针返回给用户进程 30在页式虚拟存储管理系统中，采用某些页面置换算法，会出现Belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Belady异常现象的是 。 ILRU算法 IIFIFO算法 IIIOPT算法 A 仅II B仅I、II C仅I、III D仅II、III 31 下列关于管道(Pipe)通信的叙述中，正确的是 。 A 一个管道可实现双向数据传输 B管道的容量仅受磁盘容量大小限制 C进程对管道进行读操作和写操作都可能被阻塞 D一个管道只能有一个读进程或一个写进程对其操作 32 下列选项中，属于多级页表优点的是 。 A 加快地址变换速度 B减少缺页中断次数 C减少页表项所占字节数 D减少页表所占的连续内存空间 33 在OSI参考模型中，直接为会话层提供服务的是 。 A 应用层 B表示层 C传输层 D网络层 34某以太网拓扑及交换机当前转发表如下图所示，主机00-e1-d5-00-23-a1向主机00-e1-d5-00-23-c1发送1个数据帧，主机00-e1-d5-00-23-c1收到该帧后，向主机00-e1-d5-00-23-a1发送1个确认帧，交换机对这两个帧的转发端口分别是（ ）。A 3和1 B2,3和1 C2,3和1,2 D1,2,3和1 35 下列因素中，不会影响信道数据传输速率的是 。 A 信噪比 B频率宽带 C调制速率 D信号传播速度 36 主机甲与主机乙之间使用后退N帧协议(GBN)传输数据，甲的发送窗口尺寸为1000，数据帧长为1000字节，信道带宽为100Mbps，乙每收到一个数据帧立即利用一个短帧(忽略其传输延迟)进行确认，若甲乙之间的单向传播延迟是50ms，则甲可以达到的最大平均数据传输速率约为 。 A10Mbps B20Mbps C80Mbps D100Mbps 37 站点A、B、C通过CDMA共享链路，A、B、C的码片序列(chipping sequence)分别是(1,1,1,1)、(1,-1,1,-1)和(1,1,-1,-1)。若C从链路上收到的序列是(2,0,2,0,0,-2,0,-2,0,2,0,2)，则C收到A发送的数据是 。 A000 B101 C110 D111 38 主机甲和主机乙已建立了TCP连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认段。若甲在t时刻发生超时时拥塞窗口为8KB，则从t时刻起，不再发生超时的情况下，经过10个RTT后，甲的发送窗口是 。 A10KB B12KB C14KB D15KB 39 下列关于UDP协议的叙述中，正确 的是 。 I提供无连接服务 II提供复用/分用服务 III通过差错校验，保障可靠数据传输 A 仅I B仅I、II C仅II、III DI、II、III 40使用浏览器访问某大学Web网站主页时，不可能使用到的协议是 。 A PPP BARP CUDP DSMTP 二、综合应用题：4147小题，共70分。 41.(13分)二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为： 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求： 1） 给出算法的基本设计思想； 2） 使用C或C+语言，给出二叉树结点的数据类型定义； 3） 根据设计思想，采用C或C+语言描述算法，关键之处给出注释。 42. (10分)某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息(LSI)，题42图是根据题42表及R1的接口名构造出来的网络拓扑。 题42图 R1构造的网络拓扑请回答下列问题:1） 本题中的网络可抽象为数据结构中的哪种逻辑结构？ 2） 针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应题42表的链式存储结构示意图(示意图中可仅以ID标识结点)。 3） 按照迪杰斯特拉(Dijikstra)算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。 43（9分）请根据题42描述的网络，继续回答下列问题。 1）假设路由表结构如下表所示，请给出题42图中R1的路由表，要求包括到达题42 图中子网192.1.x.x的路由，且路由表中的路由项尽可能少。 2） 当主机192.1.1.130向主机192.1.7.211发送一个TTL=64的IP分组时，R1通过哪个接口转发该IP分组？主机192.1.7.211收到的IP分组TTL是多少？ 3） 若R1增加一条Metric为10的链路连接Internet，则题42表中R1的LSI需要增加哪些信息？ 44. （12分）某程序中有如下循环代码段p：:”for(int i = 0; i N; i+) sum+=Ai;”。假设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地址在寄存器R3中。程序段P起始地址为0804 8100H，对应的汇编代码和机器代码如下表所示。 OP为操作码;；Rs和Rd为寄存器编号；OFFSET为偏移量，用补码表示。请回答下列问题，并说明理由。 1） M的存储器编址单位是什么？ 2） 已知sll指令实现左移功能，数组A中每个元素占多少位？ 3） 题44表中bne指令的OFFSET字段的值是多少？已知bne指令采用相对寻址方式，当前PC内容为bne指令地址，通过分析题44表中指令地址和bne指令内容，推断出bne指令的转移目标地址计算公式。 4） 若M采用如下“按序发射、按序完成”的5级指令流水线：IF（取值）、ID（译码及取数）、EXE（执行）、MEM（访存）、WB（写回寄存器），且硬件不采取任何转发措施，分支指令的执行均引起3个时钟周期的阻塞，则P中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1的执行不会因为与指令5的数据相关而发生阻塞？ 45 假设对于44题中的计算机M和程序P的机器代码，M采用页式虚拟存储管理；P开始执行时，(R1)=(R2)=0，(R6)=1000，其机器代码已调入主存但不在Cache中；数组A未调入主存，且所有数组元素在同一页，并存储在磁盘同一个扇区。请回答下列问题并说明理由。 1）P执行结束时，R2的内容是多少？ 2） M的指令Cache和数据Cache分离。若指令Cache共有16行，Cache和主存交换的块大小为32字节，则其数据区的容量是多少？若仅考虑程序段P的执行，则指令Cache的命中率为多少？ 3）P在执行过程中，哪条指令的执行可能发生溢出异常？哪条指令的执行可能产生缺页异常？对于数组A的访问，需要读磁盘和TLB至少各多少次？ 46. 文件F由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入到文件F中，作为其第30条记录。请回答下列问题，并说明理由。 1） 若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块？F的文件控制块内容会发生哪些改变？ 2） 若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块？若每个存储块大小为1KB，其中4个字节存放链接指针，则该文件系统支持的文件最大长度是多少？ 47. 系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量P，V(wait()，signal()操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。2014年计算机学科专业基础综合试题参考答案 一、单项选择题 （一） 单选题答案 1 C 2 B 3 A 4 D 5 C 6 D 7 D 8 D 9 D 10 B11 C 12D 13C 14 A 15 A 16 D 17A 18 C 19 C 20C21D 22B 23A 24 B 25 D 26 A 27A 28 C 29 B 30A 31C 32D 33C 34 B 35 D 36 C 37B 38 A 39 B 40D （二） 单选题答案解析 1 内层循环条件j=n与外层循环的变量无关，每次循环j自增1，每次内层循环都执行n次。外层循环条件为k=n，增量定义为k*=2，可知循环次数为2k=n，即k=log2n。所以内层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)。对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。 2 将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式； 遇到数字时，加入后缀表达式； 遇到运算符时： a. 若为 (，入栈； b. 若为 )，则依次把栈中的的运算符加入后缀表达式中，直到出现(，从栈中删除( ； c. 若为除括号外的其他运算符， 当其优先级高于除(以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。 当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。 由此可知，当扫描到f的时候，栈中的元素依次是+(-*，选B。 在此，再给出中缀表达式转换为前缀或后缀表达式的一种手工做法，以上面给出的中缀表达式为例： 第一步：按照运算符的优先级对所有的运算单位加括号。式子变成了：(a/b)+(c*d)-(e*f)/g) 第二步：转换为前缀或后缀表达式。 前缀：把运算符号移动到对应的括号前面，则变成了：+(/(ab)/(-(*(cd)*(ef)g) 把括号去掉：+/ab/-*cd*efg前缀式子出现。 后缀：把运算符号移动到对应的括号后面，则变成了：(ab)/(cd)*(ef)*)-g)/)+ 把括号去掉：ab/cd*ef*-g/+ 后缀式子出现。 当题目要求直接求前缀或后缀表达式时，这种方法会比上一种快捷得多。 3 end1指向队头元素，那么可知出队的操作是先从Aend1读数，然后end1再加1。end2指向队尾元素的后一个位置，那么可知入队操作是先存数到Aend2，然后end2 再加1。若把A0储存第一个元素，当队列初始时，入队操作是先把数据放到A0，然后end2自增，即可知end2初值为0；而end1指向的是队头元素，队头元素的在数组A中的下标为0，所以得知end1初值也为0，可知队空条件为end1=end2；然后考虑队列满时，因为队列最多能容纳M-1个元素，假设队列存储在下标为0到下标为M-2的M-1个区域，队头为A0，队尾为AM-2，此时队列满，考虑在这种情况下end1和end2的状态，end1指向队头元素，可知end1=0，end2指向队尾元素的后一个位置，可知end2=M-2+1=M-1，所以可知队满的条件为end1=(end2+1)mod M，选A。 注意：考虑这类具体问题时，用一些特殊情况判断往往比直接思考问题能更快的得到答案，并可以画出简单的草图以方便解题。 4 线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列：edbxac，中序遍历中在x左边和右边的字符，就是它在中序线索化的左、右线索，即b、a，选D。 5 将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以F中叶结点的个数就等于T中左孩子指针为空的结点个数，选C。 此题还可以通过一些特例来排除A、B、D选项。 6 前缀编码的定义是在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。D中编码110是编码1100的前缀，违反了前缀编码的规则，所以D不是前缀编码。 7 按照拓扑排序的算法，每次都选择入度为0的结点从图中删去，此图中一开始只有结点3的入度为0；删掉3结点后，只有结点1的入度为0；删掉结点1后，只有结点4的入度为0；删掉4结点后，结点2和结点6的入度都为0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为314265和314625，选D。 8 产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大，选D。 9 关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含4/2-1=1个关键字，所以每个结点中，关键字数量最少都为1个，即每个结点都有2个分支，类似与排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得叶子结点全在第四层，符合B树定义，因此选D。 10 首先，第二个元素为1，是整个序列中的最小元素，所以可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，第1+2个元素4明显比第1个元素9要大，A排除；若增量为3，第i、i+3、i+6个元素都为有序序列(i=1,2,3)，符合希尔排序的定义；若增量为4，第1个元素9比第1+4个元素7要大，C排除；若增量为5，第1个元素9比第1+5个元素8要大，D排除，选B。 11 快排的阶段性排序结果的特点是，第i趟完成时，会有i个以上的数出现在它最终将要出现的位置，即它左边的数都比它小，它右边的数都比它大。题目问第二趟排序的结果，即要找不存在2个这样的数的选项。A选项中2、3、6、7、9均符合，所以A排除；B选项中，2、9均符合，所以B排除；D选项中5、9均符合，所以D选项排除；最后看C选项，只有9一个数符合，所以C不可能是快速排序第二趟的结果。 12 不妨设原来指令条数为x，那么原CPI就为20/x，经过编译优化后，指令条数减少到原来的70%，即指令条数为0.7x，而CPI增加到原来的1.2倍，即24/x，那么现在P在M上的执行时间就为指令条数*CPI=0.7x*24/x=24*0.7=16.8秒，选D。 138位定点补码表示的数据范围为-128127，若运算结果超出这个范围则会溢出，A选项x+y=103-25=78，符合范围，A排除；B选项-x+y=-103-25=-128，符合范围，B排除；D选项-x-y=-103+25=-78，符合范围，D排除；C选项x-y=103+25=128，超过了127，选C。 该题也可按照二进制写出两个数进行运算观察运算的进位信息得到结果，不过这种方法更为麻烦和耗时，在实际考试中并不推荐。 14 (f1)和(f2)对应的二进制分别是(110011001001)2和(101100001100)2，根据IEEE754浮点数标准，可知(f1)的数符为1，阶码为10011001，尾数为1.001，而(f2)的数符为1，阶码为01100001，尾数为1.1，则可知两数均为负数，符号相同，B、D排除，(f1)的绝对值为1.001226，(f2)的绝对值为1.12-30，则(f1)的绝对值比(f2)的绝对值大，而符号为负，真值大小相反，即(f1)的真值比(f2)的真值小，即xy，选A。 此题还有更为简便的算法，(f1)与(f2)的前4位为1100与1011,可以看出两数均为负数，而阶码用移码表示，两数的阶码头三位分别为100和011，可知(f1)的阶码大于(f2)的阶码，又因为是IEEE754规格化的数，尾数部分均为1.xxx，则阶码大的数，真值的绝对值必然大，可知(f1)真值的绝对值大于(f2)真值的绝对值，因为都为负数，则(f1)(f2)，即xy。 154M8位的芯片数据线应为8根，地址线应为log24M=22根，而DRAM采用地址复用技术，地址线是原来的1/2，且地址信号分行、列两次传送。地址线数为22/2=11根，所以地址引脚与数据引脚的总数为11+8=19根，选A。此题需要注意的是DRAM是采用传两次地址的策略的，所以地址线为正常的一半，这是很多考生容易忽略的地方。 16 把指令Cache与数据Cache分离后，取指和取数分别到不同的Cache中寻找，那么指令流水线中取指部分和取数部分就可以很好的避免冲突，即减少了指令流水线的冲突。 17 采用32位定长指令字，其中操作码为8位，两个地址码一共占用32-8=24位，而Store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址，机器中共有16个通用寄存器，则寻址一个寄存器需要log216=4位，源操作数中的寄存器直接寻址用掉4位，而目的操作数采用基址寻址也要指定一个寄存器，同样用掉4位，则留给偏移址的位数为24-4-4=16位，而偏移址用补码表示，16位补码的表示范围为-32768+32767，选A。 18 计算机共有32条指令，各个指令对应的微程序平均为4条，则指令对应的微指令为32*4=128条，而公共微指令还有2条，整个系统中微指令的条数一共为128+2=130条，所以需要log2130=8位才能寻址到130条微指令，答案选C。 19 数据线有32根也就是一次可以传送32bit/8=4B的数据，66MHz意味着有66M个时钟周期，而每个时钟周期传送两次数据，可知总线每秒传送的最大数据量为66M24B=528MB，所以总线的最大数据传输率为528MB/s，选C。 20 猝发(突发)传输是在一个总线周期中，可以传输多个存储地址连续的数据，即一次传输一个地址和一批地址连续的数据，并行传输是在传输中有多个数据位同时在设备之间进行的传输，串行传输是指数据的二进制代码在一条物理信道上以位为单位按时间顺序逐位传输的方式，同步传输是指传输过程由统一的时钟控制，选C。 21 采用统一编址时，CPU访存和访问I/O端口用的是一样的指令，所以访存指令可以访问I/O端口，D选项错误，其他三个选项均为正确陈述，选D。 22 每400ns发出一次中断请求，而响应和处理时间为100ns，其中容许的延迟为干扰信息，因为在50ns内，无论怎么延迟，每400ns还是要花费100ns处理中断的，所以该设备的I/O时间占整个CPU时间的百分比为100ns/400ns=25%，选B。 23 采用静态优先级调度时，当系统总是出现优先级高的任务时，优先级低的任务会总是得不到处理机而产生饥饿现象；而短作业优先调度不管是抢占式或是非抢占的，当系统总是出现新来的短任务时，长任务会总是得不到处理机，产生饥饿现象，因此B、C、D都错误，选A。 24 三个并发进程分别需要3、4、5台设备，当系统只有(3-1)+(4-1)+(5-1)=9台设备时，第一个进程分配2台，第二个进程分配3台，第三个进程分配4台。这种情况下，三个进程均无法继续执行下去，发生死锁。当系统中再增加1台设备，也就是总共10台设备时，这最后1台设备分配给任意一个进程都可以顺利执行完成，因此保证系统不发生死锁的最小设备数为10。 25 trap指令、跳转指令和压栈指令均可以在用户态执行，其中trap指令负责由用户态转换成为内核态。而关中断指令为特权指令，必须在核心态才能执行，选D。 26 进程申请读磁盘操作的时候，因为要等待I/O操作完成，会把自身阻塞，此时进程就变为了阻塞状态，当I/O操作完成后，进程得到了想要的资源，就会从阻塞态转换到就绪态（这是操作系统的行为）。而降低进程优先级、分配用户内存空间和增加进程的时间片大小都不一定会发生，选A。 27 簇的总数为10GB/4KB=2.5M，用一位标识一簇是否被分配，则整个磁盘共需要2.5M位，即需要2.5M/8=320KB，则共需要320KB/4KB=80个簇，选A。 28 虚实地址转换是指逻辑地址和物理地址的转换。增大快表容量能把更多的表项装入快表中，会加快虚实地址转换的平均速率；让页表常驻内存可以省去一些不在内存中的页表 从磁盘上调入的过程，也能加快虚实地址变换；增大交换区对虚实地址变换速度无影响，因此I、II正确，选C。 29 一个文件被用户进程首次打开即被执行了Open操作，会把文件的FCB调入内存，而不会把文件内容读到内存中，只有进程希望获取文件内容的时候才会读入文件内容；C、D明显错误，选B。 30 只有FIFO算法会导致Belady异常，选A。 31 管道实际上是一种固定大小的缓冲区，管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在于内存中。它类似于通信中半双工信道的进程通信机制，一个管道可以实现双向的数据传输，而同一个时刻只能最多有一个方向的传输，不能两个方向同时进行。管道的容量大小通常为内存上的一页，它的大小并不是受磁盘容量大小的限制。当管道满时，进程在写管道会被阻塞，而当管道空时，进程读管道会被阻塞，因此选C。 32 多级页表不仅不会加快地址的变换速度，还因为增加更多的查表过程，会使地址变换速度减慢；也不会减少缺页中断的次数，反而如果访问过程中多级的页表都不在内存中，会大大增加缺页的次数，也并不会减少页表项所占的字节数(详细解析参考下段)，而多级页表能够减少页表所占的连续内存空间，即当页表太大时，将页表再分级，可以把每张页表控制在一页之内，减少页表所占的连续内存空间，因此选D。 补充：页式管理中每个页表项的大小的下限如何决定？ 页表项的作用是找到该页在内存的位置，以32位逻辑地址空间，字节为编址单位，一页4KB为例，地址空间内一共含有232B/4KB=1M页，则需要log21M=20位才能保证表示范围能容纳所有页面，又因为以字节作为编址单位，即页表项的大小20/8=3B。所以在这个条件下，为了保证页表项能够指向所有页面，那么页表项的大小应该大于3B，当然，也可以选择更大的页表项大小以至于让一个页面能够正好容下整数个页表项以方便存储（例如取成4B，那么一页正好可以装下1K个页表项），或者增加一些其他信息。 33 直接为会话层提供服务的即会话层的下一层，是传输层，选C。 34 主机00-e1-d5-00-23-a1向00-e1-d5-00-23-c1发送数据帧时，交换机转发表中没有00-e1-d5-00-23-c1这项，所以向除1接口外的所有接口广播这帧，即2、3端口会转发这帧，同时因为转发表中并没有00-e1-d5-00-23-a1这项，所以转发表会把(目的地址00-e1-d5-00-23-a1，端口1)这项加入转发表。而当00-e1-d5-00-23-c1向00-e1-d5-00-23-a1发送确认帧时，由于转发表已经有00-e1-d5-00-23-a1这项，所以交换机只向1端口转发，选B。 35 由香农定理可知，信噪比和频率带宽都可以限制信道的极限传输速率，所以信噪比和频率带宽对信道的数据传输速率是有影响的，A、B错误；信道的传输速率实际上就是信号的发送速率，而调制速度也会直接限制数据的传输速率，C错误；信号的传播速度是信号在信道上传播的速度，与信道的发送速率无关，选D。 36 考虑制约甲的数据传输速率的因素，首先，信道带宽能直接制约数据的传输速率，传输速率一定是小于等于信道带宽的；其次，主机甲乙之间采用后退N帧协议，那么因为甲乙主机之间采用后退N帧协议传输数据，要考虑发送一个数据到接收到它的确认之前，最多能发送多少数据，甲的最大传输速率受这两个条件的约束，所以甲的最大传输速率是这两个值中小的那一个。甲的发送窗口的尺寸为1000，即收到第一个数据的确认之前，最多能发送1000个数据帧，也就是发送1000*1000B=1MB的内容，而从发送第一个帧到接收到它的确认的时间是一个往返时延，也就是50+50=100ms=0.1s，即在100ms中，最多能传输1MB的数据，因此此时的最大传输速率为1MB/0.1s=10MB/s=80Mbps。信道带宽为100Mbps，所以答案为min80Mbps,100Mbps=80Mbps，选C。 37 把收到的序列分成每4个数字一组，即为(2,0,2,0)、(0,-2,0,-2)、(0,2,0,2)，因为题目求的是A发送的数据，因此把这三组数据与A站的码片序列(1,1,1,1)做内积运算，结果分别是(2,0,2,0)(1,1,1,1)/4=1、(0,-2,0,-2)(1,1,1,1)/4=-1、(0,2,0,2)(1,1,1,1)/4=1，所以C接收到的A发送的数据是101，选B。 38 当t时刻发生超时时，把ssthresh设为8的一半，即为4，且拥塞窗口设为1KB。然后经历10个RTT后，拥塞窗口的大小依次为2、4、5、6、7、8、9、10、11、12，而发送窗口取当时的拥塞窗口和接收窗口的最小值，而接收窗口始终为10KB，所以此时的发送