1、计算机专业（基础综合）模拟试卷 69 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下列程序段的时间复杂度是( )。int i，j；for(i=m+l；iAi；j-)Aj+1=Aj；（A）O(m 2)（B） O(n2)（C） O(m*n)（D）O(m+n)2 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。（A）单链表（B）带有头指针的单循环链表（C）双链表（D）带有尾指针的单循环链表3 将一个 A1，50，1，50的三对角矩阵，按行优先存入
2、一维数组B1，148中，A 中元素 A33,32(即该元素下标 i=33，j=32)，在 B 数组中的位置k 为( )。（A）98（B） 95（C） 97（D）964 已知一棵二叉树的前序序列为：A，B，D，G，J ，E ，H ，C，F，I，K，L ；中序序列为：D，J，G，B，E，H，A，C，K，J，L ，F 。该二叉树的后序序列为( )。（A）J，H，E，B，G，D，K，L，I，F，C，A（B） J，G，E，B ，K ，L，D，H，I，F，C，A（C） J，C，D，H，E ，B，K，L，I，F，C ，A（D）J，C ，D，H，E，B，K，L，I，F，A，C5 二叉树若用顺序方法存储，则下列
3、四种算法中运算时间复杂度最小的是( )。（A）先序遍历二叉树（B）判断两个指定位置的结点是否在同.层上（C）层次遍历二叉树（D）根据结点的值查找其存储位置6 利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行元素间的比较次数是( )。（A）4（B） 5（C） 6（D）77 以下关于图的说法正确的是( )。I在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧若一个有向图的邻接矩阵中对角线以下元素均为 0，则该图的拓扑序列必定存在在 AOE 网中一定只有一条关键路径（A）I、（B） 、（C） I、（
4、D）仅有8 已知有向图 G=(V，A)，其中 V=a，b，c，d，e，A=， ， ，对该图进行拓扑排序，下面序列中不是拓扑排序的是( )，（A）a，d， c，h，e（B） d，a，b，c ，e（C） a，h，d，c ，e（D）a，b， c，d，e9 假设有 10 个关键字互为同义词，若用线性探查法把这 10 个关键字存入，至少要进行的探查次数是( ) 。（A）9（B） 1 0（C） 1 1（D）6610 设关键字序列为：3， 7，6，9，7，l，4，5，20，对其进行排序的最小交换次数是( ) 。（A）4（B） 5（C） 6（D）711 设有 5 个初始归并段，每个归并段有 20 个记录，采用
5、 5 路平衡归并排序，若采用败者树最小的方法，总的比较次数是( )。（A）20（B） 300（C） 396（D）50012 下列选项中，描述浮点数操作速度的指标是( )。（A）MIPS（B） CPI（C） IPC（D）MFLOP13 某浮点机的字长 8 位，尾数和阶码都采用补码形式，且运算过程中数符和阶符都采用双符号位，基数为 2。则浮点加减运算过程中，当出现下列( )情况时，需要左舰。（A）尾数相加后，数符为“01”（B）尾数相加后，数符为“10”（C）尾数相加结果为“001”（D）尾数相加结果为“1 11”14 计算机的加法器采用并行进位的原因是( )。（A）增强加法器功能（B）简化加法器
6、设计（C）提高加法器的运算速度（D）保证加法器可靠性15 下列火于主存储器的描述中，正确的是( )ICPU 访存时间由存储器容量决定ROM 和 RAM 在存储器中是统一编址的ROM 中任意一一个单元可以随机访问DRAM 是破坏性读出，因此需要读后重写（A）I 和（B） 和（C） 和（D）、和16 某计算机的存储系统由 Cache 一主存系统构成，Cache 的存取周期为 10 ns，主存的存取周期为 50 ns。在 CPU 执行一段程序时，Cache 完成存取的次数为 4 800次主存完成的存取次数为 200 次，该 Cache 一主存系统的效率是( )。（A）0856（B） 0862（C）
7、0958（D）0.9617 设指令中的地址码为 A，变址寄存器为 X，程序计数器为 PC，则变址间接寻址方式的操作数有效地址 EA 是( )。（A）(PC)+A)（B） (X)+A)（C） (X)+(A)（D）(X)+A18 以下叙述中，不符合 RISC 指令系统特点的是( )。（A）指令长度固定，指令种类少（B）寻址方式种类丰富，指令功能尽量增强（C）设置大量通用寄存器，访问存储器指令简单（D）选取使用频率较高的一些简单指令19 通常所说的 32 位微处理器是指( )。（A）地址总线的宽度为 32 位（B）处理的数据长度只能为 32 位（C） CPU 字长为 32 位（D）通用寄存器数目为
8、32 个20 在单发射、按序流动的普通流水线中，可能出现下列哪种数据相关问题( )。（A）写后读相关 RAW（B）读后写相关 WAR（C）写后写相关 WAW（D）以上都有可能21 “总线忙”信号由( ) 建立。（A）获得总线控制权的设备（B）发出 “总线请求” 的设备（C）总线控制器（D）CPU22 CPU 的工作周期为 20 ns，主存存取周期为 10 ns，此时 DMA 接口适合采用( )方式与 CPU 共享主存。（A）停止 CPU 访问主存（B）周期挪用（C） DMA 与 CPU 交替访存（D）以上无正确选项23 提高单机资源利用率的关键技术是( )。（A）Spooling 技术（B）虚
9、拟技术（C）交换技术（D）多道程序设计技术24 临界区是指并发进程访问共享变量段的( )。（A）管理信息（B）信息存储（C）数据（D）代码程序25 一个正在访问临界资源的进程由于申请等待 IO 操作而被中断时，它是( )。（A）可以允许其他进程进入与该进程相关的临界区（B）不允许其他进程进入任何临界区（C）可以允许其他进程抢占处理机，但不得进入该进程的临界区（D）不允许任何进程抢占处理机26 利用银行家算法进行安全序列检查时，不需要的参数是( )。（A）系统资源总数（B）满足系统安全的最少资源数（C）用户最大需求数（D）用户已占有的资源数27 在请求页式虚拟存储系统中，假设系统为某个进程分配了
10、 4 个物理页框，页面的引用串号为 0，1，2，4，5，2，3，4，3，0，1，4，5，3，采用固定分配局部置换，当采用 LRU 算法时会产生的缺页中断次数是( )。（A）8（B） 9（C） 10（D）1128 页式虚拟存储管理的主要特点是( )。（A）不要求将作业装入主存的连续区域（B）不要求将作业同时全部装入主存的连续区域（C）不要求进行缺页中断处理（D）不要求进行页面置换29 下面的叙述中，属于分段式虚拟存储管理的优点的是( )。（A）没有内零头（B）便于处理在进程执行过程中堆栈尺寸的增长问题（C）便于共享内存中数据（D）只需将进程的一部分调入内存，进程即可运行30 在 UNIX 系统中
11、，将一个文件卷复制到另一个磁盘上。只复制文件数据，包括目录之后( )。（A）文件数据能够被访问（B）文件目录能够被访问（C）文件数据和目录都能被访问（D）文件数据和目录都不能访问31 在某文件系统中，一个文件控制块的大小为 128 B，一个盘块大小为 1 KB，采用一级目录。假定文件目录中有 1 600 个目录项，则查找一个文件平均需要( )次访问磁盘。（A）50（B） 100（C） 200（D）30032 中断向量的地址是( )。（A）子程序入口地址（B）中断服务例行程序入口地址（C）中断服务例行程序入口地址的地址（D）例行程序入口地址33 在 OSI 参考模型中，服务定义为( )。（A）各
12、层向下层提供的一组原语操作（B）各层间对等实体间通信的功能实现（C）各层向上层提供的一组功能（D）和协议的含义是一样的34 有一条无噪声的 8 KHz 信道，每个信号包含 8 级，每秒采样 24 K 次，那么可以获得的最大传输速率是( )。（A）24 Kbps（B） 32 Kbps（C） 48 Kbps（D）72 Kbps35 连接在透明网桥上的一台计算机把一个数据帧发往网络上不存在的一个设备，网桥将( ) 。（A）丢弃该帧（B）扩散该帧（C）停止接收其他帧（D）暂存该帧等收到地址信息再转发36 以太网交换机中的端 HMAC 地址映射表是( )。（A）由交换机的生产厂商建立的（B）交换机在数据
13、转发过程中通过学习动态建立的（C）由网络管理员建立的（D）由网络用户利用特殊的命令建立的37 在 IP 数据报的传递过程中，IP 数据报报头中保持不变的域是( )。（A）标识和片偏移（B）标志和头部校验和（C）标识和目的地址（D）标志和生存周期38 组播路由过程中( ) 技术可以避免路由环路。（A）采用了水平分割技术（B）构造组播转发树（C）采用 IGMP 协议（D）通过生存期(TTL)字段39 UDP 与 IP 都是不可靠的通信协议，在 IP 协议的基础上封装 UDP 报文的原因是( )。（A）UDlP 能够进行流量控制（B） UDP 能够进行拥塞控制（C） UDP 能够实现路由转发（D）U
14、DP 能够实现端口功能40 FTP 协议中，客户进程与服务器的连接过程需要打开( )个端口（A）28（B） 26（C） 23（D）21二、综合应用题41-47 小题，共 70 分。41 如下图所示的 AOE 网，求： (1)每项活动 ai 的最早开始时间 e(ai)和最迟开始时间 l(ai)。 (2)完成此工程最少需要多少天(设边上权值为天数)? (3)哪些是关键活动? (4)是否存在某项活动，当其提高速度后能使整个工程缩短工期?42 设将 n(n，1) 个整数存放到一维数组 R 中，试设计一个在时间和空间两方面尽可能有效的算法，将 R 中保有的序列循环左移 P(0P n)个位置，即将 R 中
15、的数据由(X 1， X2，X n)变换为 (XP，X P+1，X N，X 1，X P-1)，要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 JAVA 语言表述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。43 已知主机 A 的主频为 40 MHz，现在用这台主机运行一组标准测试程序 A，A 中包含的各种指令和响应所需要的时间如下表所示：请回答以下问题： (1)求主机有效的 CPI。 (2)求主机的 MIPS。 (3)假设程序 A 在计算机上运行的时间为 100 s，其中 90 s 用于 cPu，其余时间为 IO 时间。现在CPU 的
16、速度提高了 50，IO 速度不变，那么 A 的运行耗费了多长时间?44 下图是某模型机 CPU 的组成框图。设该 CPU 采用同步控制逻辑，分取指周期、取第一操作数周期、取第二操作数周期、执行周期四个机器周期，每个机器周期有T0，T 1，T 2 三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。 ADD R0，(R 1)完成功能(R 0)+(R1)R 045 一个系统采用段页式存储方式，有 16 位虚地址空间，每个进程包含两个段，并且一页大小为 212 字节。段表和页表如下表所示(所有的值为二进制，并且段长以页为单位)。下列哪些二进制虚地址会产生缺段中断或缺页中断?哪些二进制虚地址能
17、转换为物理地址? 如果可以转换，请写出物理地址。 (1)0001010001010111(提示：产生缺段中断，或缺页中断?) (2)1110010011111111(提示：转换后的物理地址是什么?) (3)l111010011000111(提示：产生缺段中断，或缺页中断 ?) (4)001100101100011l(提示：转换后的物理地址是什么 ?) (5)请问该系统最大物理内存是多少?46 某银行的营业厅有多个柜员窗口，可以同时办理业务。银行的营业厅中安排有门张座倚供储户休息等候。每个储户在进入营业厅时会在排队机上取得一个号码，若此前没有客户，则排队机就会唤醒一个柜员为储户服务，当没有储户时
18、柜员便可以休息。若储户较多，则所有柜员均会参与服务，当排队储户数超过柜员数时，没有被服务的储户便会在座椅上休息，并等候叫号。当座位满时，再进入营业厅的储户不再从排队机上获取号码，会离开去找另外的营业厅。若将银行的柜员和储户的行为看成是不同类型的进程，请设一个程序，利用信号量来完成上述操作，用类C 语言写出程序。47 如下图所示有一个移动主机，原来的 IP 地址是 16080402016，为了移动到其他网络，它将 160804026 设置为本地代理。之后它移动到了179560016 的网络中，设置 1795601 为外部代理，并且获得了新的IP 地址 179567869。请问： (1)如果这时候
19、该主机和其他主机通信，对端需要把数据发给什么地址? (2)当一个 160804020 到达 160800016 网络后，会有主机响应该 ARP 清求吗? (3)本地代理需要将发送给移动主机的分组发送到哪个地址?计算机专业（基础综合）模拟试卷 69 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 时间复杂度由 m，n 共同决定，最坏情况 F 的时间复杂度为 O(mn)。2 【正确答案】 D【试题解析】 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指
20、针的单循环链表，双链表郁不合适，考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是 O(1)，所以答案是 D。3 【正确答案】 D【试题解析】 根据三对角对阵压缩方法： 将 A1，n1，n 压缩至B0，3n 一 3时，a ij 与 bk 的对应关系为：k=2i+i 一 3； 将 A1，n1， ，n压缩至 B0，3n-2时，a ij 与 bk 的对应关系为： k=2i+j 一 2。 根据题目，A 中元素 A33,32 在 B 数组中的位置 k 为：k=2i+j 一 2=233+322=96。4 【正确答案】 C【试题解析】 三叉树的形式如下图所示： 后序序列为J，G，D，H，E，B ，K
21、，L，I ，F ，C，A。5 【正确答案】 B【试题解析】 选项 A、C、D 运算的时问复杂度都是 O(n)，而选项 JE的运算的时间复杂度为 O(1)，因为对于指定位置 p 和 q 的两个结点，判断是否在同一层上，只需判断两者log 2p=log2q是否成立。6 【正确答案】 B【试题解析】 利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素 30 的比较次数为 5 次。7 【正确答案】 D【试题解析】 说法 I 是错误的。在一个有向图的拓扑序列中，若顶点 a 在顶点 b之前，只能说明顶点 a 到顶点 b
22、 有一条路径。 说法是错误的。AOE 网中可能有不止一条关键路径，它们的路径长度相同。 说法是正确的。任意 n 个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为 v0，v 1，v n-1，证明此时的邻接矩阵 A 为上三角矩阵，可用反证法证明。假设此时的邻接矩阵不是上三角矩阵，那么，存在下标 i 和 J(ij)，使得 Aij不等于 O，即图中存在从 vi 到 jj 的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，v i 的位置一定在 vj 之前，而上述拓扑序列 v0，v 1，v n-1 中，由于 ij ，即 vi 的位置在 vj 之后，导致矛盾。因此说法是正确的。8 【正确答案】 D
23、【试题解析】 对 AOV 网进行拓扑排序的方法和步骤是： (1)从 AOV 网中选择一个没有前驱的顶点(该顶点的入度为 0)，并且输出它； (2)从网中删去该顶点，并且删去从该顶点发出的全部有向边； (3)重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。 本题按照拓扑排序方法对该图进行拓扑排序便可得到结果。在本题中，给出的有向图如下所示： 进行拓扑排序的过程如下图所示：9 【正确答案】 D【试题解析】 假设有 k 个关键字互为同义词，若用线性探查法把这 k 个关键字存入，探查次数最少的情况是第 1 个关键字通过 1 次比较后插入，第 2 个关键字通过2 次比较后插入，第 k 个关键字通
24、过 k 次比较后插入。总的比较次数=1+2+k=k(k+1)2，将 k=10 代入得到总的比较次数为 66。10 【正确答案】 B【试题解析】 由于关键字序列数较小，采用直接插入排序或简单选择排序，直接插入排序的交换次数更多，选择简单选择排序，最小交换次数为 5。11 【正确答案】 B【试题解析】 采用败者树时，5 一路归并意味着败者树的外结点有 5 个，败者树的高度 h 为 log25 向上取整，结果为 3。每次在参加比较的记录中选择一个关键字最小的纪录，比较次数不超过 h，总共 100 个记录，需要的比较次数不超过 1 003=300 次，故选 B。12 【正确答案】 D【试题解析】 衡量
25、计算机系统速度的指标中，CPI 表示每条指令平均所需的时钟周期数；IPC 表示每个时钟周期平均执行的指令条数； MIPS 表示每秒百万条指令数；MFLOP 常用于衡量浮点运算速度，表示每秒百万条浮点运算数。13 【正确答案】 D【试题解析】 当尾数运算结果为非规格化形式时，需要左规；基数为 2 的补码的规格化形式下最高数值位应与符号位相反，故当尾数相加结果为“111”时，尾数需要左规。14 【正确答案】 C【试题解析】 与串行进位相比，并行进位可以提高运算速度。15 【正确答案】 D【试题解析】 兼容性微操作是指那些可以同时产生，共同完成某一任务的微操作，而互斥性微操作是指在机器中不允许同时出
26、现的微操作。一条机器指令可以分解成一个微操作序列，这些微操作是计算机中最基本的、不可再分解的操作。微操作有兼容性和互斥性之分。在同一 CPU 周期中，可以并行执行的微操作称为兼容性微操作，不可以并行执行的微操作称为互斥性微操作。所谓兼容和互斥都是相对的，一个微操作可以和一些微操作兼容，和另一些微操作互斥。对于单独一个微操作，谈论其兼容和互斥都是没有意义的。16 【正确答案】 B【试题解析】 在一个程序执行期间，设 N1 为访问 M1 的命中次数，N 2 为访问 M2的次数。 ，两级存储层次的等效访问时间 TA。根据主存的启动时间有：假设 Cache 访问和主存访问是同时启动的，T A=HTA1
27、+(1 一 H)TA2，假设 Cache不命中时才启动主存 TA=HTA1+(1 一 N)(TA1+TA2)=TA1+(1 一 H)TA2，存储层次的访问效率 e=TA1T A。命中率=4 800(4 800+200)=O96，平均访问时间=0 9610+(1096)50=116 ns，效率：10116=0862。先求出命中率，接着求出平均访问时间，最后求出 Cache 一主存系统的效率。17 【正确答案】 B【试题解析】 变址间接寻址方式就是先变址后间接寻址。在 4 个选项中，选项A：(PC)+A)为相对寻址；选项 B：(X)+A) 变址间接寻址；选项 C：(X)+(A)为间接变址寻址；选项
28、 D：(X)+A 为变址寻址。18 【正确答案】 B【试题解析】 RISC 即精简指令系统计算机，选项 B 显然不符合 RISC 的特点。RISC 的中心思想是要求指令系统简化，尽量使用寄存器寄存器操作指令，指令格式力求一致，大部分 RISC 具有下列特点：(1)指令总数较少 (一般不超过 100 条) ；(2)基本寻址方式种类少 (一般限制在 23 种) ；(3)指令格式少 (一般限制在 23 种) ，而且长度一致；(4)除取数和存数指令 (LoadStore) 外，大部分指令在单周期内完成；(5)只有取数和存数指令能够访问存储器，其余指令的操作只限于在寄存器之间进行；(6)CPU 中通用寄
29、存器的数目应相当多 (32 个以上，有的可达上千个)；(7)为提高指令执行速度，绝大多数采用硬连线控制实现，不用或少用微程序控制实现；(8)采用优化的编译技术，力求以简单的方式支持高级语言。19 【正确答案】 C【试题解析】 通常所说的 32 位微处理器是指 CPU 字长为 32 位。通常将运算器和控制器合称为中央处理器(CPU) 。在由超大规模集成电路构成的微型计算机中，往往将 CPU 制成一块芯片，称为微处理器。CPU 按照其处理信息的字长可以分为：8 位 CPU，16 位 CPU，32 位 CPU 以及 64 位 CPU 等。选项 A，B，D 均与微处理器的位数无关。20 【正确答案】
30、A【试题解析】 指令取操作数的动作一定在写回结果之前，故在按序流动的单发射(普通标量) 普通流水线中，先进入流水线的指令取操作数和写回结果的动作一定位于后续指令写同结果的动作之前，故不可能出现 WAR 和 WAW；唯一可能的数据相关问题是后续指令在前一指令写回结果之前读相关的操作数，即 RAw，写后读相关。而在非按序流动的流水线中，允许后进入流水线的指令超过先进入流水线的指令而先流出流水线，故三种数据相关问题都可能出现。21 【正确答案】 A【试题解析】 在总线控制机制中，准备使用总线的设备向总线控制器发出“总线请求”由总线控制器进行裁决。如果经裁决允许该设备使用总线，就由总线控制器向该设备发
31、出一个“总线允许”信号。该设备接收到此信号后，发出一个“总线忙”信号用来通知其他设备总线已被占用。当该设备使用完总线时，将“总线忙”信号撤销，释放总线。因此“总线忙”信号是由获得总线控制权的设备建立的。22 【正确答案】 C【试题解析】 由于 CPU 工作周期为主存周期的 2 倍，故可将其分为两个分周期，其中一个供 DMA 接口访存，另一个供 CPU 访存，即 DMA 与 CPU 交替访存，这样可以在不影响 CPU 效率的前提下充分利用主存带宽。23 【正确答案】 D【试题解析】 本题考查操作系统的特性。并发性是操作系统的一个最主要的特性，其他特性都是基于该特性的。多道程序设计技术是实现并发性
32、的基础，由于采用了多道技术，系统实现了并发，从而提高了资源利用率。而 Spooling 技术是为解决独占设备的问题，虚拟技术主要应用在存储管理中来扩大存储空间，交换技术也是用于存储管理。24 【正确答案】 D【试题解析】 本题考查对临界区的理解。所谓临界区，并不是指临界资源，例如共享的数据、代码或硬件设备等，而是指访问这些临界资源的那段代码程序，例如PV 操作、加减锁等。操作系统中对临界区的访问关心的就是临界区的操作过程，对临界资源作何具体操作是应用程序的事，操作系统并不关心。25 【正确答案】 C【试题解析】 进程进入临界区必须满足互斥条件，当进程进入临界区但是尚未离开时就被迫进入阻塞是可以
33、的，系统中经常有这样的情形。在此状态下，只要其他进程在运行过程中不寻求进入该进程的临界区，就应该允许其运行。该进程所锁定的临界区是不允许其他进程访问的，其他进程若要访问，必定会在临界区的“锁”上阻塞，期待该进程下次运行时可以离开并将临界区交给它。所以正确选项为 C。26 【正确答案】 B【试题解析】 安全性检查一般要用到进程所需的最大资源数，减去进程占用的资源数，得到进程为满足进程运行尚需要的可能最大资源数，而系统拥有的最大资源数减去已经分配掉的资源数得到剩余的资源数。比较剩余的资源数是否满足进程运行尚需要的可能最大资源数可以得到当前状态是否安全的结论。而满足系统安全的最少资源数并没有这个说法
34、。27 【正确答案】 C【试题解析】 本题考查 LRU 算法。对于页面置换类的题目，一般只要理解了置换算法的执行过程，那么计算相对是比较简单的，一般采用表格的方法，以堆栈的顺序来计算比较方便。如下表所示：经过计算，缺页次数为 10。28 【正确答案】 B【试题解析】 本题考查页式存储的概念。29 【正确答案】 C【试题解析】 如果系统正在向非易失性存储器件硬盘写数据，此时，系统崩溃，写的数据可能会丢失，或者存储信息不完整。30 【正确答案】 D【试题解析】 UNIx 系统中每个文件卷需要经过安装后才能使用。所以只复制文件数据，包括目录后，是都不能访问的。即使物理介质本身在工作，但若其上的文件卷
35、没有安装好，系统也无法存取其中的信息。uNIx 需要安装文件卷后才可以被访问。31 【正确答案】 B【试题解析】 l 600 个目录项占用的盘块数=1 600128 B1 KB=200 个。一级目录的平均访盘数为 12 盘块数，所以平均访问磁盘的数目为 100 次。32 【正确答案】 C【试题解析】 中断向量包括两个字：一个是中断处理程序的入口地址；另一个是中断处理程序的程序状态字。那么显然，中断向量地址就是中断处理程序的入口地址的地址了。33 【正确答案】 C【试题解析】 本题考查 OSI 参考模型中，服务的定义。34 【正确答案】 C【试题解析】 无噪声的信号应该满足奈奎斯特定理，即最大数
36、据传输率=2Hlog2V(位秒)。将题目中的数据代入，得到答案是 48 kHz。注意：题目中给出的每秒采样 24 kHz 是无意义的，因为超过了 2H，所以 D 是错误答案。35 【正确答案】 B【试题解析】 网桥不知道网络上是否存在该设备，它只知道在其转发表中没有这个设备的 MAC 地址。因此，当网桥收到这个目的地址未知的帧时，它将扩散该帧，即把该帧发送到所连接的除输入网段以外的所有其他网段。36 【正确答案】 B【试题解析】 本题考查交换机中地址映射表的原理。主要与路由器的路由表进行区分，路由表可以由认为配置静态路由，也可以通过动态协议建立，而对于交换机，映射表只能在数据转发中进行动态学习
37、建立，并且没有表项都有定时器，因此答案为 B。37 【正确答案】 C【试题解析】 本题考查 IPv4 报文格式和传输特性。在数据报传递过程中，如果遇到长度超过网络 MTU 的时候，必须分片。因此，片偏移和标志是变化的，生存时间是随着数据报传递发生变化的。对于校验和，每经过一个结点都要进行重新计算，因此只有目的地址和标识是不变的。注意：标识是一个计算器，即使发生分片的情况下，其会把这个值复制到分片后的标识字段，因此答案为 C。38 【正确答案】 B【试题解析】 由于树具有不存在环路的特性，因此构造一个组播转发树，通过该转发树既可以将主播分组传送到组内每台主机，又能避免环路。39 【正确答案】 D
38、【试题解析】 UDP 与 IP 的最大区别是 UDP 能够实现端到端的通信，即只是在IP 的基础上增加了端口功能。40 【正确答案】 D【试题解析】 FTP 打开熟知端口(端口号为 21)，使客户进程能够连接上。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 (1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)=5 Ve(3)=6 Ve(4)=maxve(2)+3，ve(3)+6=12 Ve(5)=maxve(3)+3 ， ve(4)+3=15 Ve(6)=ve(4)+4=16 Ve(7)=ve(5)+1=16 Ve(8)=Ve(5)+4=19 Ve(9)=maxve(
39、7)+5，Ve(8)+2=21 Ve(10)=maxve(6)+4，Ve(9)+2=23 所有事件的最晚发生时间如下： V1(10)=23 V1(9)=V1(10)-2=21 V1(8)=vl(9)-2=19 V1(7)=V1(9)-5=16 V1(6)=V1(10)-4=19 VI(5)=minV1(7)-1，V1(8)-4=15 V1(4)=minV1(6)-4，V1(5)-3=12 V1(3)=rainV1(4)-6，V1(5)-3=6 V1(2)=V1(4)-3=9 Vl(1)=minVl(2)-5，V1(3)-6=0 因此，所有活动 Ai 的 e()，1()，d()如下：A1：e(1
40、)=Ve(1)：0，1(1)=V1(2)-5=4，d(1)=4A2：e(2)=Ve(1)：0，1(2)=V1(3)-6=0，d(2)=0A3：e(3)=Ve(2)=5，1(3)=V1(4)-3=8，d(3)=3 A4：e(4)=Ve(3)=6，1(4)=V1(4)-6=6 ，d(4)=0A5 ：e(5)=Ve(3)=6 ，1(5)=V1(5)-3=12，d(5)=6A6 ： e(6)=Ve(4)=12，1(6)=V1(5)-3=12，d(6)=0A7：e(7)=Ve(4)=12，1(7)=V1(6)-4=15，d(7)=3A8 ：e(8)=Ve(5)=15，1(8)=V1(7)-1=15，d(
41、8)=0A9：e(9)=Ve(5)=15 ，1(9)=V1(8)-4=15 ，d(9)=0A10：e(10)=Ve(6)=16 ，1(10)=V1(9)-5=16，d(10)=0A11：e(11)=Ve(7)=19，1(11)=V1(9)-2=19，d(10)=0A10：e(12)=Ve(8)=16 ，1(12)=V1(10)-4=19 ，d(10)=3A10：e(13)=Ve(9)m=21， 1(13)=V1(10)-2=21，d(10)=0(2)经过上面的计算，可以得出：完成此工程最少需要 23 天。 (3)从以上计算可知，关键活动为a2，a 4，a 6，a 8，a 9，a 10，a 11
42、，a 13。这些活动构成两条关键路径即：a2，a 4，a 6，a 8，a 10，a 13 和 a2，a 4，a 6，a 9，a 11，a 13。 (4)存在 a2，a 4，a 6，a 13，活动，当其提高速度后能使整个工程缩短工期。42 【正确答案】 (1)基本设计思想： 将数组a 1，a 2，a 3， a p，a p+1，a n先进行全部逆转，然后分别对a p，a n-1，a n a1，a 2，a 3，a p进行再次逆转。(2)算法描述： void sift_left(int a，int n，int p) Reverse(a，0，n-1)；移动了3n2 次数据； Reverse(a ，0，n
43、-p-1)；移动了 3(n-p)2 次数据； Reverse(a，n-p，n-1)；移动了 3p2 次数据； void Reverse(int A，int left，intright) int n=right-left+1；设置一个辅助空间； if(n43 【正确答案】 (1)计算机的 CPI 包括四种指令，那么 CPI 就是这四种指令的数学期望：CPI=061+0182+0124+018=224。(2)MIPS=40CPI=17 9。(3)程序 A 在计算机上运行的时间为 100 s，90 s 用于 CPIJ，那么用于 I0 的时间为 10 ms 不会发生改变。CPU 的速度提高了 50。程
44、序 A 的 CPJ 时间变为9015=60 s ，A 的运行耗费了 60 s+10 s=70 s。44 【正确答案】 各机器周期的微操作命令及节拍安排如下： (1)取指周期 T0：PC总线 MAR 主存，微操作命令形成部件发读信号到主存 T 1：M(MAR)MDR，微操作命令形成部件发+1 信号到 PC T2：MDR总线IR，OP(IR)微操作命令形成部件 (2)取第一操作数周期 T 0：R 0总线FIRST (3)取第二操作数周期 T 0：R1总线MAR主存，微操作命令形成部件发读信号到主存； T1：M(MAR)MDR ； T 2：MDR总线SECOND。 (4)执行周期 T 0：FIRST
45、 总线Y； T 1：微操作命令形成部件发Add 信号到 ALU，(Y)+(SECOND)ALUZ T 2：z 总线R 0。45 【正确答案】 由题意可得逻辑地址各字段为：段号为 0，页号为 001，查看页表 0 中的 001，号页的状态，其状态为 0，说明此页尚未调入内存。故发生缺页中断。(2)段号为 1，页号为 110，段表长度为 6，查看页表 1 中的 110 号页的状态，其状态为 1，说明此页面已调入内存。则相应的物理地址为：000101010011111111(3)段号为 1，页号为 111，段表长度为 6，发生越界。所以发生缺页中断。(4)段号为 0，页号为 111，查看页表 0 中
46、的 011 号页的状态，其状态为 1，说明此页面已调入内存。则相应的物理地址为：100110010011111111。(5)由题可见，内存最多可以放 8 页，每页 212 字节，故系统最大物理内存是 23212=215=32 K。46 【正确答案】 此类题目在考试中也比较多见，类似的还有睡眠的理发师等。因此，掌握此类题目的基本要点是解决此类题目的关键。本题从读者和写者的基本原理出发，对等候的储户数加以限制。从资源角度看，柜员是资源，座椅也是资源。那么，设置柜员的信号量为 teller，初始为 0，柜员一上岗则作 V 操作，以提供资源。储户的信号量为 customer，初始为 0，表示储户尚未进
47、入营业厅。mutex 为排队机，也是座椅的互斥量，柜员和储户均可以对此操作。设信号量 teller，customer和 mutex 其中 waiting 是整型量，表示排队的储户数，其初始为 O，最大不超过 n#define CHAIRS=N 座椅数，也是最多排队的储户数typecief int semaphore； 定义信号量 semaphore teller=O； 等待储户的柜员数semaphore cLlstomer=0； 等待服务的储户数semaphore mutex=0； 对排队机操作的互斥量 int waiting=O； 等待的储户数void teller()while(TRUE)
48、并发调度P(customer)； 杏看有无储户P(mutex)； 需要获得排队机的控制权waiting=waiting-1； 将等候的顾客数减 1V(teller)； 提供 1 个可服务的柜员V(mutex)； 释放排队机service()； 为储户服务void customer() 储户进程P(mutex)； 先获得排队机if(wailingCHAIRS) 若还有座椅则取号waiting=waiting+l； 取号，占用座椅等待叫号V(mstomet)； 告知系统储户加 1V(nmtex)； 释放排队机P(teller)； 看是否有空闲柜员Serviced()； 进入窗口被服务else 若没有座椅了，则不取号V(mutex)； 不取号，释放排队机 离开注意：本题中，柜员是具有循环的。即 while(TRUE)的语句，储户就没有，原因是储户是随时到达的，柜员是等候储户到来并服务的，如果储户进程也采用并发调度，则顾客就不可能为 0，这与实际情况不同，所以在此是不需要的。对于柜员来说，当开启一个窗口即会调用一次柜员进程，所以，柜员应该一直运行，直到其下班(下班作为边界条件在此
