1、全国硕士研究生入学统一考试计算机学科专业基础综合真题 2010 年及答案解析(总分：148.97，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.若元素 a，b，c，d，e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是( )（分数：2.00）A.dcebfaB.chdaefC.dbcaefD.afedcb2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是( )（分数：2.00）A.bacdeB.dbaceC.dhcaeD.ecbad3.下列线索二又树中(用虚线表示线索)，符合后序线索
2、树定义的是( )（分数：2.00）A.B.C.D.4.在下列所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树，在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是( )（分数：2.00）A.B.C.D.5.在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为1 的结点，则树 T 的叶结点个数是( )（分数：2.00）A.41B.82C.113D.1226.对 n(n 大于等于 2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( )（分数：2.00）A.该树一定是一棵完全二叉树
3、B.树中一定没有度为 1 的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一任一结点的权值7.若无向图 G(V，E)中含 7 个顶点，为保证图 G 在任何情况下都是连通的，则需要的边数最少是( )（分数：2.00）A.6B.15C.16D.208.对下图进行拓补排序，可以得到不同的拓补序列的个数是( )（分数：2.00）A.B.C.D.9.已知一个长度为 16 的顺序表 L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是( )（分数：2.00）A.4B.5C.6D.710.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙
4、述中，正确的是( )（分数：2.00）A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区处理顺序无关11.对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88则采用的排序方法可能是( )（分数：2.00）A.起泡排序B.希尔排序C.归并排序D.基数排序12.下列选项中，能缩短程序执行时间的措施是( )提高 CPU 时钟频率优化数据通路结构对程序进
5、行编译优化（分数：2.00）A.仅和B.仅和C.仅和D.，13.假定有 4 个整数用 8 位补码分别表示 r1=FEH，r 2=F2H，r 3=90H，r 4=F8H，若将运算结果存放在一个 8 位的寄存器中，则下列运算会发生溢出的是( )（分数：2.00）A.r1r2B.r2r3C.r1r4D.r2r414.假定变量 i，f，d 数据类型分别为 int，float 和 double(int 用补码表示，float 和 double 分别用IEEE754 单精度和双精度浮点数据格式表示)，已知 i=785，f=1.5678，d=1.5。若在 32 位机器中执行下列关系表达式，则结果为真是( )
6、()i=(int)(float)i()f=(float)(int)f()f=(float)(double)f()(d+f)-d=f（分数：2.00）A.仅和B.仅和C.仅和D.仅和15.假定用若干个 2K4 位芯片组成一个 8K8 位存储器，则地址 081FH 所在芯片的最小地址是( )（分数：2.00）A.0000HB.0600HC.0700HD.0800H16.下列有关 RAM 和 ROM 的叙述中，正确的是( )RAM 是易失性存储器，ROM 是非易失性存储器RAM 和 ROM 都是采用随机存取的方式进行信息访问RAM 和 ROM 都可用作 CacheRAM 和 ROM 都需要进行刷新（
7、分数：2.00）A.仅和B.仅和C.仅，D.仅，17.下列命令组合情况中，一次访存过程中，不可能发生的是( )（分数：2.00）A.TLB 未命中，Cache 未命中，Page 未命中B.TLB 未命中，Cache 命中，Page 命中C.TLB 命中，Cache 未命中，Page 命中D.TLB 命中，Cache 命中，Page 未命中18.下列存储器中，汇编语言程序员可见的是( )（分数：2.00）A.存储器地址寄存器(MAR)B.程序计数器(PC)C.存储器数据寄存器(MDR)D.指令寄存器(IR)19.下列不会引起指令流水阻塞的是( )（分数：2.00）A.数据旁路B.数据相关C.条件
8、转移D.资源冲突20.下列选项中的英文缩写均为总线标准的是( )（分数：2.00）A.PCI、CRT、USB、EISAB.ISA、CPI、VESA、EISAC.ISA、SCSI、RAM、MIPSD.ISA、EISA、PCI、PCI-Express21.单级中断系统中，中断服务程序执行顺序是( )保护现场；开中断；关中断；保存断点；中断事件处理恢复现场；中断返回。（分数：2.00）A.、B.、C.、D.、22.假定一台计算机的显示存储器用 DRAM 芯片实现，若要求显示分辨率为 16001200，颜色深度为 24 位，帧频为 85Hz，显示总带宽的 50%用来刷新屏幕，则需要的显存总带宽至少约为
9、( )（分数：2.00）A.245MbpsB.979MbpsC.1958MbpsD.7834Mbps23.下列选项中，操作 OS 提供的给应用程序的接口是( )（分数：2.00）A.系统调用B.中断C.库函数D.原语24.下列选项中，导致创进新进程的操作是( )用户成功登陆 设备分配 启动程序执行（分数：2.00）A.仅和B.仅和C.仅和D.，25.设与某资源相关联的信号量初值为 3，当前值为 1，若 M 表示该资源的可用个数，N 表示等待资源的进程数，则 M，N 分别是( )（分数：2.00）A.0，1B.1，0C.1，2D.2，026.下列选项中，降低进程优先权级的合理时机是( )（分数：
10、2.00）A.进程的时间片用完B.进程刚完成 I/O，进入就绪队列C.进程长期处于就绪队列中D.进程从就绪状态转为运行态27.进行 P0 和 P1 的共享变量定义及其初值为boolean flag2; int turn=0; flag0=faulse; flag1=faulse; 若进行 P0 和 P1 访问临界资源的类 C 代码实现如下：Void P0( )/进程 p0 Voicl P1( )/进程 p1while(TuRE) while(TURE)Flag0=TURE； Flag1=TuRE；turn=1； turn=0；While(flag1 int turn=0; flag0=faul
11、se; flag1=faulse; 若进行 P0 和 P1 访问临界资源的类 C 代码实现如下：Void P0( )/进程 p0 Voicl P1( )/进程 p1while(TuRE) while(TURE)Flag0=TURE； Flag1=TuRE；turn=1； turn=0；While(flag1&(turn=1) While(flag0%&(turn=0)； ；临界区； 临界区；Flag0=FALSE； Flag1=FALSE；则并发执行进程 P0 和 P1 时产生的情况是：（分数：2.00）A.不能保证进程互斥进入临界区，会出现“饥饿”现象B.不能保证进程互斥进入临界区，不会出现
12、“饥饿”现象C.能保证进程互斥进入临界区，会出现“饥饿”现象D.能保证进程互斥进入临界区，不会出现“饥饿”现象 解析：解析 考查进程间通信与 Peterson 算法。算法实现互斥的主要思想在于设置了一个 turn 变量，用于进程间的互相谦让。如果进程 P0 试图访问临界资源，flag0=true，表示希望访问。此时如果进程 P1 还未试图访问临界资源，则 flag1在进程上一次访问完临界资源退出临界区后已设置为 false。所以进程 P0 在执行循环判断条件时，第一个条件不满足，进程 P0 可以正常进入临界区，且满足互斥条件。我们需要考虑的是两个进程同时试图访问临界资源的情况。注意 turn
13、变量的含义：进程在试图访问时，首先设置自己的 flag 变量为 true，表示希望访问；但又设置 turn 变量为对方的进程编号，表示谦让，因为在循环判断条件中 turn 变量不是自己编号时就循环等待。这时两个进程就会互相“谦让”一番，但是这不会造成“饥饿”的局面，因为 turn 变量会有一个最终值，所以必定有进程可以结束循环进入临界区。实际的情况是，先作出“谦让”的进程先进入临界区，后作出“谦让”的进程则需要循环等待。其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“您走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，
14、所以先客套的人请完对方，就等着对方请自己，然后光明正大进门。28.某基于动态分区存储管理的计算机，其主存容量为 55MB(初试为空间)，采用最佳适配(Best fit)算法，分配和释放的顺序为：分配 15MB，分配 30MB，释放 15MB，分配 8MB，分配 6MB，此时主存中最大空闲分区的大小是( )（分数：2.00）A.7MBB.9MB C.10MBD.15MB解析：解析 考查动态分区分配。最佳适配算法是指：每次为作业分配内存空间时，总是找到能满足空间大小需要的最小的空闲分区给作业。可以产生最小的内存空闲分区。下图显示了这个过程的主存空间的变化：*上图中，灰色部分为分配出去的空间，白色部
15、分为空闲区。容易发现，此时主存中最大空闲分区的大小为9MB。29.某计算机采用二级页表的分页存储管理方式，按字节编制，页大小为 210字节，页表项大小为 2 字节，逻辑地址结构为（分数：2.00）A.B. C.D.解析：解析 考查非连续分配的分页存储管理方式。页大小为 210字节，页表项大小为 2 字节，采用二级页表，一页可存放 29个页表项，逻辑地址空间大小为216页，要使表示整个逻辑地址空间的页目录表中包含的的个数最少，则需要 216/29=27=128 个页面保存页表项，即页目录表中包含的个数最少为 128。本题中的二级页表结构，如下页图示：*30.设文件索引节点中有 7 个地址项，其中
16、 4 个地址项为直接地址索引，2 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4 字节，若磁盘索引块和磁盘数据块大小均为 256 字节，则可表示的单个文件的最大长度是( )（分数：2.00）A.33KBB.519KBC.1057KB D.16513KB解析：解析 考查磁盘文件的大小性质。因每个磁盘索引块和磁盘数据块大小均为 256 字节。所以 4 个直接地址索引指向的数据块大小为 4256字节。2 个一级间接索引共包括 2(256/4)个直接地址索引，既其指向的数据块大小为 2(256/4)字节。1 个二级间接地址索引所包含的直接地址索引数为(256/4)(2
17、56/4)256，即其所指向的数据块大小为(256/4)(256/4)256 字节。其结构如下页图所示：*即 7 个地址项所指向的数据块总大小为4256+2(256/4)256+(256/4)(256/4)256=1082368 字节=1057KB。31.设置当前工作目录的主要目的是( )（分数：2.00）A.节省外存空间B.节省内容空间C.加快文件的检索速度 D.加快文件的读写速度解析：解析 绝对路径名(全路径名)：从根目录开始到达所要查找文件的路径。除了绝对路径名以外，系统为每个用户设置一个当前目录(又称工作目录)，访问某个文件时，就从当前目录开始向下顺次检索。因此，系统设置当前工作目录的
18、主要目的是加快文件的检索速度。节省外存空间，节省内容空间，加快文件的读写速度都与设置当前工作目录无关。32.本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是( )（分数：2.00）A.命令解释程序B.中断处理程序 C.系统调用程序D.用户登录程序解析：解析 考查中断处理。键盘是典型的通过中断 I/O 方式工作的外设，当用户输入信息时，计算机响应中断并通过中断处理程序获得输入信息。33.下列选项中，不属于网络体系结构中所描述的内容是( )（分数：2.00）A.网络的层次B.每一层使用的协议C.协议的内部实现细节 D.每一层必须完成的功能解析：解析 考查计算机网络体系结构的基本概念。我们把
19、计算机网络的各层及其协议的集合称为体系结构。因此 A、B、D 正确，而体系结构是抽象的，它不包括各层协议及功能的具体实现细节。34.在下图所示的采用“存储-转发”方式分组的交换网络中，所有链路的数据传输速度为 100Mbps，分组大小为 1000B，其中分组头大小 20B，若主机 H1向主机 H2发送一个大小为 980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从 H1发送到 H2接收完为止，需要的时间至少是( )（分数：2.00）A.B.C. D.解析：解析 考查存储转发机制。由题设可知，1000-20=980B：分组携带的数据长度为 980B；文件长度为 980000B，需
20、拆分为 1000 个分组，加上头部后，每个分组大小为 1000B，总共需要传送的数据量大小为 1MB。980000B/980B=1000(个分组)；由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过 2 个分组交换机。当 t=1M/100Mbps=80ms 时，H1 发送完最后一个 bit；*由于传输延时，当 H1发完所有数据后，还有两个分组未到达目的地，其中最后一个分组，需经过 2 个分组交换机的转发，在两次转发完成后，所有分组均到达目的主机。每次转发的时间为t0=1K/100Mbps=0.08ms。*所以，在不考虑分组拆装时间和等待延时的情况下，当 t=8
21、0ms+2t0=80.16ms 时，H 2接收完文件，即所需的时间至少为 80.16ms。答案为 C。35.某自治系统采用 RIP 协议，若该自治系统内的路由器 R1收到其邻居路由器 R2的距离矢量中包含信息net 1，16，则可能得出的结论是( )（分数：2.00）A.R2可以经过 R1到达 net1，跳数为 17B.R2可以到达 net1，跳数为 16C.R1可以经过 R2到达 net1，跳数为 17D.R1不能进过 R2到达 net1 解析：解析 考查 RIP 路由协议。R1在收到信息并更新路由表后，若需要经过 R2到达 net1，则其跳数为 17，由于距离为 16 表示不可达，因此 R
22、1不能经过 R2到达 net1，R 2也不可能到达 net1。B、C 错误，D 正确。而题目中并未给出 R1向 R2发送的信息，因此 A 也不正确。36.若路由器 R 因为拥塞丢弃 IP 分组，则此时 R 可以向发出该 IP 分组的源主机发送的 ICMP 报文件类型是( )（分数：2.00）A.路由重定向B.目的不可达C.源抑制 D.超时解析：解析 考查 ICMP 协议。ICMP 差错报告报文有 5 种：终点不可达、源点抑制、时间超过、参数问题、改变路由(重定向)。其中源点抑制是当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道应当把数据报的发送速率放慢。因此答案为 C
23、。37.某网络的 IP 地址为 192.168.5.0/24，采用长子网划分，子网掩码为 255.255.255.248，则该网络的最大子网个数，每个子网内的最大可分配地址个数为( )（分数：2.00）A.32，8B.32，6 C.8，32D.8，30解析：解析 考查子网划分与子网掩码、CIDR。由于该网络的 IP 地址为 192.168.5.0/24，如下图所示：*因此其网络号为前 24 位。第 2532 位为子网位+主机位。而子网掩码为 255.255.255.248，其第 2532 位的 248 用二进制表示为11111000，如下图所示：*因此后 8 位中，前 5 位用于子网号，后 3
24、 位用于主机号。IP 地址格式如下图所示：*对 IPv4 地址进行子网划分时，子网号不能为全 1 或全 0，但随着无分类域问路由选择 CI-DR 的广泛使用，现在全 1 和全 0 的子网号也可以使用了，但一定要谨慎使用，要弄清路由器所用的路由选择软件是否支持全 0 或全 1 的子网号这种用法。不论是分类的 IPv4 地址还是无分类域问路由选择 CIDR，其子网中的主机号均不能为全 1 或全 0。因此该网络空间的最大子网个数为 25=32 个，每个子网内的最大可分配地址个数为 6 个。38.下列网络设备中，能够抑制网络风暴的是( )中继器 集线器 网桥 路由器（分数：2.00）A.仅和B.仅C.
25、仅和D.仅 解析：解析 考查网络设备与网络风暴。广播域是指网段上所有设备的集合。这些设备收听送往那个网段的所有广播。*冲突域：在同一个冲突域中的每一个节点都能收到所有被发送的帧；冲突域是基于第一层(物理层)；广播域是基于第二层(链路层)；中继器和集线器属于第一层设备，所以分割不了冲突域；物理层设备中继器和集线器既不隔离冲突域也不隔离广播域；交换机和网桥属于第二层设备，所以能分割冲突域；网桥可隔离冲突域，但不隔离广播域；路由器属于第三层设备，所以既能分割冲突域又能分割广播域。VLAN(即虚拟局域网)也可隔离广播域。对于不隔离广播域的设备，它们互连的不同网络都属于同一个广播域，因此扩大了广播域的范
26、围，更容易产生网络风暴。39.主机甲和主机乙之间已建立一个 TCP 连接，TCP 最大段长度为 1000 字节，若主机甲的当前拥塞窗口为4000 字节，在主机甲向主机乙连接发送 2 个最大段后，成功收到主机乙发送的第一段的确认段，确认段中通告的接收窗口大小为 2000 字节，则此时主机甲还可以向主机乙发送的最大字节数是( )（分数：2.00）_解析：解析 考查 TCP 流量控制与拥塞控制。发送方发送窗口的上限值应该取接收窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为 min4000，200040.如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机本地域名服
27、务器发送的域名请求条数分别为( )（分数：2.00）A.1 条，1 条 B.1 条，多条C.多条，1 条D.多条，多条解析：解析 考查 DNS 系统域名解析过程。递归查询的过程如下页图所示：*当采用递归查询的方法解析域名时，如果主机所询问的本地域名服务器不知道被查询域名的 IP 地址，那么本地域名服务器就以 DNS 客户的身份，向其他根域名服务器继续发出查询请求报文，这种方法中用户主机和本地域名服务器发送的域名请求条数均为 1 条，答案为 A。二、综合应用题(总题数：7，分数：69.00)将关键字序列(7、8、11、18、9、14、30)散列存储到散列列表中，散列表的存储空间是一个下标从 0
28、开始的一个一维数组散列函数维：H(key)=(key3)MOD T，处理冲突采用线性探测再散列法，要求装填(载)因子为 0.7。问题：（分数：10.00）(1).请画出所构造的散列表；（分数：5.00）_正确答案：(7，数据总数 7 个存储空间长度为 10P=10所以，构造的散列表为：H(7)=(73)MOD 10=1H(8)=(83)MOD 10=4H(11)=(113)MOD 10=3H(18)=(183)MOD 10=4H(9)=(93)MOD 10=7H(14)=(143)MOD 10=2H(30)=(303)MOD 10=0散列地址 0 1 2 3 4 5 6 7 8 9关键字 30
29、 7 14 11 8 18 . 9 . .探测次数 1 1 1 1 1 2 1)解析：(2).分别计算等概率情况下，查找成功和查找不成功的平均查找长度。（分数：5.00）_正确答案：(查找成功的 ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的 ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2)解析：设将 n(n1)个整数存放到一维数组 R 中，试设计一个在时间和空间两方面尽可能有效的算法，将 R 中保有的序列循环左移 p(0pn)个位置，即将 R 中的数据由(X 1X2Xn)变换为(X pXp+1XnX1Xn-1)要求：（分数：9.00）_解析：_解析：(3).
30、说明你所设计算法的时间复杂度和空间复杂度。（分数：3.00）_正确答案：(算法的时间复杂度和空间复杂度：算法的时间复杂度为 O(n)；算法的空间复杂度为 O(1)；)解析：某计算机字长为 16 位，主存地址空间大小为 128KB，按字编址，采用字长指令格式，指令名字段定义如下：（分数：9.99）(1).该指令系统最多可有多少条指令?该计算机最多有多少个通用寄存器?存储器地址寄存器(MDR)至少各需多少位?（分数：3.33）_正确答案：(指令系统最多支持：16 条指令；计算机最多有 8 个通用寄存器。地址空间大小 128KB，按字编址，有 64K 个存储单元，地址位数为 16 位。存储器地址寄存
31、器(MAR)不小于地址位数，至少 16 位；存储器数据寄存器(MDR)不小于字长位数，至少 16 位。)解析：(2).转移指令的目标地址范围是多少?（分数：3.33）_正确答案：(转移指令的目标地址范围：0000HFFFFH。)解析：(3).若操作码 0010B 表示加法操作(助记符为 a d d)，寄存器 R4 和 R5 的编号分别为 100B 和 101B，R4 的内容为 1 2 3 4 H，R5 的内容为 5 6 7 8 H，地址 1 2 3 4 H 中的内容为 5 6 78 H 中的内容为 1 2 3 4 H，则汇编语言为 a d d(R4).(R5)+(逗号前原操作数，都号后为目的操
32、作数)对应的机器码是什么(用十六进制表示)?该指令执行后，哪些寄存器和存储单元的内容会改变?改变后的内容是什么?（分数：3.33）_正确答案：(根据题目中给出的各个部分的内容，可知：OP:0010，M S:001，R 4:100，M d:010，R S:101；)解析：某计算机的主存地址空间为 256MB，按字节编址，指令 Cache 分离均有 8 个 Cache 行，每个 Cache 行的大小为 64B，数据 Cache：采用直接映射方式，现有两个功能相同的程序 A 和 B，其伪代码如下页所示：（分数：9.99）(1).若不考虑用于 Cache 一致性维护和替换算法的控制位，则数据 Cach
33、e 的总容量是多少?（分数：3.33）_正确答案：(64B8=512B；)解析：(2).要组元素 a031和 a11各自所在的主存块对应的 Cache 行号分别是多少(Cache 行号从 0 开始)?（分数：3.33）_正确答案：(主存地址与 cache 的地址格式如下图所示：aij占 32 位，共四个字节；a00的开始地址为：320；a031与 a00相距 314 个地址单位，即 320+314=444；444 换成二进制：110111100；a11与 a00相距 2574 个地址单位，即 320+2574=1348；1348 换成二进制：10101000100；)解析：(3).程序 A 和
34、 B 的数据访问命令中各是多少?那个程序的执行时间更短?（分数：3.33）_正确答案：(程序 A 按行优先访问数组 aij：总共需要访问：256256=216次a00a01a02a03a04a05a06 a07第 1 块 a08a09a010a011a012a013a014 a015a016a017a018a019a020a021a022 a023第 2 块a024a025a026a027a028a029a030 a031a032a033a034a035a036a037a038 a039第 3 块a040a041a042a043a044a045a046 a047行优先的情况下，a00未命中，但
35、 a01，a02，a03，a04，a05，a06，a07，a08，a09，a010，a011，a012，a013，a014，a015均命中，则未命中的有 a00，a016，a032即每块的块首元素，共有 212个块，即未命中次数为 212； 故程序 A 的数据访问命中率为： )解析：假设计算机系统采用 CSCAN(循环扫描)磁盘调度策略，使用 2KB 的内存空间记录 16384 个磁盘块的空间状态。（分数：10.00）(1).请说明在上述条件下如何进行磁盘块空闲状态管理。（分数：5.00）_正确答案：(使用位示图法，每一位表示一个磁盘块是否空闲；)解析：(2).设某单面磁盘旋转速度为每分钟 6
36、000 转。每个磁道有 100 个扇区，相临磁道间的平均移动时间为1ms。若在某时刻，磁头位于 100 号磁道处，并沿着磁道号大的方向移动(如下图所示)，磁道号请求队列为50，90，30，120。对请求队列中的每个磁道需读取 1 个随机分布的扇区，则读完这个扇区点共需要多少时间?要求给出计算过程。（分数：5.00）_正确答案：(每分钟 6000 转，转 1 圈需要 0.01s，通过一个扇区需要 0.1ms。被访问的下一个磁道号移动距离(磁道数)：被访问的下一个磁道号 移动距离(磁道数)120 2030 9050 2090 40T=(20+90+20+40)1ms+40.1ms=170.4ms)
37、解析：设某计算机的逻辑地址空间和物理地址空间均为 64KB，按字节编址。若某进程最多需要 6 页(Page)数据存储空间，页的大小为 1KB。操作系统采用固定分配局部置换策略为此进程分配 4 个页框(Page Fame)。页号 页根号 装入时刻 访问位0 7 130 11 4 230 12 2 200 13 9 160 1当该进程执行到时刻 260 时，要访问逻辑地址为 17CAH 的数据，请问答下列问题：（分数：9.99）(1).该逻辑地址对应的页号是多少?（分数：3.33）_正确答案：(由于该计算机的逻辑地址空间和物理地址空间均为 64KB=216B，按字节编址，且页的大小为1K=210，
38、故逻辑地址和物理地址的地址格式均为：17CAH=0001 0111 1100 1010B逻辑地址格式为：)解析：(2).若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程。（分数：3.33）_正确答案：(采用 FIFO 置换算法，与最早调入的页面即 0 号页面置换，其所在的页框号为 7，于是对应的物理地址为：)解析：(3).若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程。(设搜索下一页的指针沿顺时针方向移动，且当前指向 2 号页框，示意图如下)（分数：3.33）_正确答案：(采用 Clock 置换算法，首先从当前位置(2 号
39、页框)开始顺时针寻找访问位为 0 的页面，当指针指向的页面的访问位为 1 时，就把该访问位清零，指针遍历一周后，回到 2 号页框，此时 2 号页框的访问位为 0，置换该页框的页面，于是对应的物理地址为：)解析：某局域网采用 CSMA/CD 协议实现介质访问控制，数据传输速率为 10Mbps，主机甲和主机乙之间的距离为2km，信号传播速度是 200000km/s。请回答下列问题，并给出计算过程。（分数：10.00）(1).若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间?最长需经过多长时间?(假设主机甲和主机乙发送数据过程中，其他主机不发送数据)（分数：5.00）_正确答案：(当甲乙同时向对方发送数据时，两台主机均检测到冲突所需时间最短：当一方发送的数据马上要到达另一方时，另一方开始发送数据，两台主机均检测到冲突所需时间最长：)解析：(2).若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据锁(1518 字节)向主机乙发送数据，主机乙每成功收到一个数据锁后，立即发送下一个数据锁，此时主机甲的有效数据传输速率是多少?(不考虑以大网锁的前导码)（分数：5.00）_正确答案：(发送一锁所需时间：主机乙每成功收到一个数据帧后，向主机甲发送确认帧，确认帧的发送时延：)解析：
