2009-2015年计算机考研408真题

【实例简介】
计算机硕士研究生入学统一考试（408）真题2009-2015年的
干道论坛www.cskaoyan.com 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰千留余香 的薮据传输率为0.5MBs,又用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序 0 101H 包含18条指令,中断服务的其他开销相当于2条指令的执行时间。请回答下列问题,要给出计算过程。 1)在中断方式下,CPU用于该外设IO的时问占整个CPU时间的百分比是多少? 254H 2)当该外没的数传输率达到5MBs时,改用DMA方式传送数据。假定每次DMA传送块大八为 5000B,且DMA预处理和后处理的总开销为500个时钟期,则CPU用于该外设IO的时问占整^CPU 页面大小为4KB,一次网存的访问时间是100ns,一次快表TLB)的访问时间是10ns,理一次缺页的平均 时问的百分比是多少?(假设DMA与CPU之问没有访存冲突) 时门10ns(已含更新TLB和页表的时间),进程的驻留集大小固定为2,又用最近最少使用置换算法{LRU和 44.(13分)某计算机字爻16位,采用16位定长指令字结构,部分数据通路结构如下图所示,图中所有控制 部淘汰策略。假设①TLB初始为空:②地址转换时先汸问TLB,若TLB未命中,冄访问页表(忽咯访问页表之 信号为1时表示有效、为0时表示无效。例如控倒信号 MDRine为1表示允许数据从DB打入MDR, MDRin 后的TLB更新时间):③有效位为0表示贝面不在内存,产生缺页中断,缺页中断理后,返回到产生缺页中 为1表小允许数据从内总线打入MDR。假设MAR的输出一直处,使能状态。加法指令ADD(R1),R0 断的指令处重新执行,设有虚地址訪问序列2362H、1565H、25A5H,请问 的功能为(R0H(R)->(R1),即将R0中的数据与R1的内所指主存单元的数据相加,并将结果送入R1 (1)依次访句上述三个虚地址,各需多少时间?给出计算过程 的内容所指主存单元中保存 (2)基于上述访问序列,虚地址1565H的物理地址是多少?请说明理由。 47.(9分)某网络拓扑如下图所小,路由器R1通讨接口E1、E2分别连接局域刈1、局域刈2,通过接口L0 ddr 连接路由器R2,并選过路由器R2连接域名服务器与互联网。R1的I0接口的IP地址是20211821:R2 的L0接口的IP地址是202.118.22,L1接口的IP地址是130.11.120.1,ED接口的IP地址是202.118.3.1: 域名服务器的IP地址是202118.32 「互联网 局域网1 MIRour 13D11.120.1 204.113.2.1 2U2.118.3L aDD一 RIin +I 域名业务尜 l 控司信号图例 及其控制信号 全指令译吗鄙件 寄存器缩入控制信号 R1和R2的路曰表结构为 下表给出了上述指令取指和译码阶段每个节拍(时钟周期)的功能和有效控制信号,请按表中描述方式用表格 目的对络IP也址 子刈掩码 下一趺IP地址 列出指令执行阶段每个节拍的功能和有效控制信号 (1)将IP地址空司202.118.1.024划分为2个子网,分别分配纶局域网1、局域网2,每个局域网需分配的 时钟 有效痉制信号 IP地址数不少丁120个。请给出了网划分结果,说明理由或给出必要的计算过程。 MAR←(PC) PCout, marin (2)请给出R1约路由表,使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和互 MDR←MMDR MemR. MDRinE. PC+1 联网的路由 PC<(PCHI 3)请采用路由聚合技术,给出R2到局域网1和局域网2的路由。 IR< (MDR) MDRout Iril 指令译码 无 45.(7分)=个进程P、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用 pmduce(生成一个正 整数并月pu0送入缓冲区某一空单元中;P2每次用 geode0从该缓冲区中取出一个奇数户用 countoddo统 计奇数个数:P3每次用 teteven从该缓冲区中取出个偶数并用 countervein统计偶数个数。请用信号量机 制实现这三个进程的司步与互斥活动,并说明所定义信号量的含义。要求月伪代码描述。 46.(8分)请求分五管理系统中,假设某进程的页表内容如下表所示 页号 页框( Page fran)号 有效位(行在位) 干道论坛www.cskaoyan.com 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰手留余香 参考答案 while(p ! -NULL! f ∥遍历链表直到最后一个点 单项选择题 if( court k) count++ ∥计数,若cour 移动p 同步移动 9.A10. 11.C 16.C 19.D 20.B f(count k) ∥查找大败返回0 33.B 34.B35.C36.A37 38.D39.C e1se{∥否则打印并返回 综合应用题 prnt f (d,->data) 41.解答: turn 该方法不一定(或不能)求得最短路径。 例如,对于下图所小的带权图,如果按照题中的原则,从A到C的最短路径是A-→B->C,事实|其最知路 Search k 径是A->D>C 提示:算法程序题,如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数,如果能 用伪代码写出自然更好,比较复杂的地方可以直接用文字表达 若所给出的算法采用一遍扫描方式就能得到正确结果,可给满分15分:若采用两遍或多遍扫描才能得到 正确结果的,最高分10分。若采用递归算法得到正确结果的,最高给10分:若实现算法的空间复杂度过高(使 用了大小与k有关的辅助数组),但结果正确,最高给10分 43.解答 42.解答 (1)按题意,外设每秒传送0.5MB,中时每次传送4B。中断方式下,CPU每次用于数据传送的时钟同 (1)算法的基本设计思想(5分) 为:5×18+5×2-100 问题的关键是设计一个尽可能高效的算法,通过表的一趟遍历,找到倒数第k个结点的位置。算法的基 为达到外设D5MBs的数据传输,外设每秒中请的中断次数为:0.5MB/4B=12500 本设计思想是:定义两个指针变量p和q,初始时均指向头结点的下一个结点(链表的第一个结点)。p指针沿 秒钟内用于中断的开销:100×12500=1250000=12.5M个时钟哥期 链表移动;当p指针移动到第k个结点时,q指针开始与p指针冋步移动;当p指针移动到最后一个结点时,q PU用于外设MO的时间占整个CPU村间的百分比:12.5M50M=2.5%。 指针所指示缉点为倒数第k个结点。以上过程对链表仪进行一遍扫摧。 2)当外设数据传输率提高到5MBs时改用DMA方式传送,每次DMA传送5000B,1秒钟内需产生的 (2)算法的详细实现步骤(5分) DMA次数:5MB5000B-1000 ① count=0,p和q指向链表表头结点的下一个结点 CPU用于DMA处理的总开销:1000×500=50000=0.M个时钟周期 ②若p为空,转⑤ CPU用于外设IO的时间占整个CPU时可的白分比:0.5M/500M=0.1%。 ③若 count等于k,则q指向下一个结点:否则, count= count+1 44.解答 ④p指向下一个结点,转② 条指令的执行过程通常由取指、译码和执行3个步骤完成,本题中取指用3个节拦、译码用1个节拍, ⑥若 count等于k,则查找成功,输凵该结点的cata域的值,返回1;舍则,说明k超过」线性表的长 执行加法运算并把结果写入主存如何完成呢?包括划分执行步骤、确定完成的功能、要提供的控制信号,这是 度,杳找失败,返回0 本题要测试的内容。为回答这个白题,首先要看清图中给出的部件组成情况和信息传送釣路径。 ⑥算法结束 要完成的功能时(R0)+((R1)→(R1),从图中看到 (3)算法实现(5分) (1)R0、RI都有送自己内容到内总线的路径,控制信号介别是R00u和 Clout typedef int ElenTy:e; 链表数据的类型定义 12)ALU加运算,2个数据由工作寄存器A和内总线提供,制信号是Add:A只接收闪总线的内容,控制 typedef st ruct I Node 连表细点的结构定义 信号是Ain:结果需存AC,控制信号是ACin:AC的内容可送内总线,控制信号是 A Cout; data ∥结点数据 3)PC可接收内总线的内容,还可增1,控制信号是PCin和PC+1,PC的内容可送内总线,控制信号是PCot struct T,node link ∥结点链接指针 )指令寄存器IR可接收内总线的内容,控制信号是IRin I *L_nist (5)读写存储器时,地址由MAR纤AB提供,MAR只接收总线上的信息,控制信号是MARi arch k(linkist int k)i 6)读存储器,提供读命令MemR,并通过DB送入MDR,控制信号是 MDRinE MDR的内容可送入总线, ∥查找链表1st倒数第k个结点,并输出该结点aata或的值 控制信号是 MDRou Linklis-p=1t-1irk,q=1ist-1ink;∥指针、q指示第一个结点 (7)写存储器,提供写命令Memⅳ,数据出MDR通过DB送到存储器的数据引脚,控制信号是 MDRoutE 干道论坛www.cskaoyan.com 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰千留余香 然后是划分执行步骤、确定每一步完成的功能、需要提供釣控制信号。这是由指令应完成的功能和计算机 MDR <MOMAR 硬件的实际组成情况和信息传送的可旿径共同决定的,基本原则是步骤越少越妤。硬件电眳婓能支持·可以 C A←-(MDR) MDRout A in 有多种方案,解题时应参抿以给出的答题格式,即取指和译码阶段的那张表的内窣,但不必把表三有的内容再 AC←(A)+(RO) ROout. AddACin MDR←(AC) 划分指令执行步骤,萌定每一步完成的功能、给岀需要提供的控制信号: C10 MIMAR)<(MDR) MDRouteMemw 请注意,(R0)+(R))表示:R0省存器的内容与R1作地址从主存中读出來的数完成加法运算;而→ 解答 R1)表示把R的内容作为主存储器的地址完戍写主存操作。为防上出现误辉,题中还特地太此作了文字说 定义信号量odd控制Pl与P2之间的同步;even控Pl与P3之同的同步; empty控制生产者与消费者之 明。这条指令的功能是先到主存储器取一个数,之后运算,再将结果写回主存储器 间的同步; mutex控訇走程间互斥使用缓冲区。程序如卜: (1)执行相加运算,需把存储器中的数据读出,为此首先送地址,将R1的内容送MAR,控制信号是Rot semaphore ocd =0, even =0, empty=N, mute MARin 2)启动读主存操作,读出的内容送入MDR,控制信号是MemR、 MDRin F。还可同时把RQ的内容经内总 线送入A,用到的制信号是R0out、Ain x= produce();∥生成一个数 3)执行加法运算,即A的内容与MDR的內容相加,结果保存到AC,控制信号是 MDRout、Add、Acin ∥判断缓冲区是否有空单元 (4)要把AC的内容写入主套,山于R1的内容已经在MAR中,地址三经有了,但需要把写入的数据(已 2(mutex)i ∥缓冲区是否破占用 经在AC口)经內总线送入MDR,控制信号是 A Cout.、MDRn t() (5)给出写上存的命令,把MDR的内容经DB送存器的数据线引脚,执行写燥作,制信号是 MDRoute (nut ex) ∥释放缓汁区 这儿个步骤是有先后次序的,前面的完成了,下一梦才可以执行,也保证了不会产生硬件线路的冲突。请 v(even) ∥如果是偶数,向P3发出信号 注意,使用最为频繁的是内总线,它在任何时刻只能接收一个輸入数据,并且冋內总线发送信息的电路只能 三态门器件迕接到内总线,5个向内总裁发送信息的控制信号( A Cout, POut,R0out, Clout, MDRout)最多 y(。ac) ∥如果是奇数,向P2发出信号 只能有一个为1,其他4个必须仝为0,或者5个全为0 仔细看一下,发现可以把第2个步骤的操作划分到两个步骤中完成,一个步骙中安排MDR接收从存储器 中读出的内容,到疠外一个步骤文现RU的内容逶入A:这多用了一个操作步骤,指令的执行速度会变慢。有些 解题者在写仁储器之前,还会再行一次把R1的内容送MAR,尽管无此必要,但不属于原理上的错误。 ?(oddi ∥收到P1发来的信号,已产生一个奇数 当然还可以有其他的设计结果。 ∥缓冲区是否白用 解题时这些叙还内容不必写出来(这写出这些内容是希望帮助大家领会本题要测试的知识点和指令的执 getodd( 行辶桯),直接按照已经给岀的表硌的形式、按照提供旳填写办法扫设汁的表格及其内容填好就可以」。 v(mutex) ∥释放缓汁区 请注意,题目表栘内容(告诉你答题的格式和答题内容旳表达方式)与你答题的表格为容合在一起才是这 ∥向1发信号,多出一个空单元 条指令的完整的执行过程,千万不要产生仁何错觉。 counted(i 参考答案 时钟 功能 有效控制信号 MARE(RI Clout.MA Rin MDR←M(MAR) DRie ∥收到P1发来的信号,已产生一个偶数 A<(R0 ROut, Ain 2(mutex)i ∥缓冲区是否破占用 (A) MDRout. Addacin getever ()i MDR<(AC) ∥释放缓汁区 MOMAR)<(DR) MDRout E, Menw ∥向P1发信号,多出一个空单元 A<(R0”也可在C7:“AC←(MDR)+(A)”之前单列的一个时钟周内执行。 counteven 参考答案二 功能 有效控制信号 解答: Cs AAR←(R1) Rlout.MA Rin (1)根据页式管耳的工作原理,应先考虑页面大小,以便将页弓和页内位移分解来。页面大小为4KB 干道论坛www.cskaoyan.com 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰手留余香 即212,则得到页内位移占虚地址的低12位,页号言剩余高位。可得二个虚地址的页号P如下(十六进制的 转发路径都是从L0接口转发,因上采用路由聚合技术后,路由器R2到局域网1和局域网2的路由为: 位数字转换成4位二进,因此,十六进制的低二位正为页内位移,最高位为页亏): 目的刈络|P地址 下一跳|P地址 接口 62H1:P=2,访问快表10ns,因初始为窣,访问页表100ns得到页框亏,合成勿理地址后访问主存10m 202.118.10 255.255.255.0 02.118.2.1 共计10ns+100s+100ns=210ns 15651:P=1,访问快表1Ons,落空,访问页表100ns落空,进行缺页中断处理10°ns,访问快表10ns,合 成物理地址后访问主存10mn5,共计10ns+100ns+10ns+10ms+100ns=10000022ns 5A5I:P=2,访问快表,园第一次访问已将该页号放入昃表,因此花费10ns便可合成物理地址,访问主 存100ns,共计1Cns+l00ns= ilons (2)当访问虚地址1565H时,产生缺页中断,合法驻留集为2,必须从页表中淘汰一个页面,根据题日的 置换算法,应淘汰0号页面,因此1565H的对应而框号为101H。由上可得1565H物理地址为101565H 解答 (LCDR中的子网亏可以全0或全1,但主机号不能全0或全 因此若将P地址空间202118.1.0/24划分为2个子网,且每个局域网需分配的P地址个数不少于120个 子网号至少要占用一位 日2-2<120<2-2可知,三机号至少要占用7位 由于源P地址空间的网络前缀为24位,因此上机号位数+子网号位数=8 综上可得土机号位数为7,子网号位数为1 因此子网的划分结果为:子对1:202.118.10/25子网2:202.118.1.128/25 地址分配方案:子网1分配给局域网1,子网2分配给局域网2,或子网1分配给局域网2,子网2分配给 局域网1。 (2)由于局域网1和局域网2分别与路由器R1的E1、E2接凵直接相连,因此在R1的路由表中,目的网 络为局域网1的转发路径是直接通过接口E1转发,目的网络为局域网2的转发路径是直接暹过接口E1转发。 庄于局域网1、2的网络前缀均为25位,因此它们的子网掩码均为255.255.255.128 根捏题意,R1专门为域名服务器设定了一个特定的路山表项,因上该络山表项中的子网掩码应为 255255255255:对应的下一跳转发地王是202.11822,转发接口是L0 根据題意,刭互联网的路t实质上柑当于一个默认路口,默认峂由一般写作QU,即目的地址为0.0.0.0 子刚掩码为0.0.00。对应的下一跳转发地址是202.118.2.2,转发接口是L0。 综上可得到路由器R1的路由表为: (若子网1分配给局域网1,子网2分配给局域网2) 目的网络IP地址 了网掩码 下跳P地址接口 202.118.1.0 255.255255.128 E1 2021161122525218 02.118.3.2 5255.255.255 202.118.2.2 0.0 18.2.2 (若子网1分配给局域网2,子网2分配给局域网1) 「目的网络|P块圳 了网掩码下跳P均圳接口 202.118.1.128 255.255.255.128 E1 202.118.1.0 255.255.255.128 02.118.3.2 2525525252011822 0.0.0.0 0.0.0.0 02.118.2.2 LO 3)局域网1和局域网2的地址叮以聚合为202.118.1.0/24,而对于峰由器R2来说,通往局域网1和2的 王道论坛 sk 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰手留余香 2010年全国硕士研究生入学统一考试 B.每次划分后,先处理珓长的分区可以减少递归次数 计算机科学与技术学科联考 C.每次划分后,先处理较短的分可以减少递归次薮 计算机学科专业基础综合试题 D.递归次数与每次划分后得到的分区的处理顺序无关 单项选择题:第1~40小题,每小题2分,共R0分。下列每题给出的四个选项中,只有一个选项最符合试 11.对一组数据(2,12,16,8,5,10进行排序,若前二遍排序结果如下: 题要求 第一趙排序结果:2,12,16,5,10,88 若元素a、b、c、d、e、f依次进栈,允进栈、退栈操作交替进行,但不允迕续三次进行退栈操作,则 第二趟排序结果:2,12,5,10,16,88 不可能得到的出栈序列是 第二趟排序结果:2,5,10,12,16,88 b. cbdae f 则采用的排序方法可能是 c. bca fd D. afdcb 2.某队列允许在其两端进行入队操作,但仅允许在一端进行岀队操作。若元a、b、c、d、c依次入此队列 A.起泡排序B.希尔排序C.归并排序D.基数排序 后再进行出队操作,则不可能得到的H队序列是 12.下列选项中,能缩短程序执行时间的拮施是 I.提高CPU时钟频率 a, bade B. bacc c. dbcc Ⅱl.优化数据通路结构 D ccba .对稈序进行编译优化 3.下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是 A.仅1和ⅢB.仅I和ⅢC.仅Ⅱ和ⅢD.I、Ⅱ和 13.假定有4个整数用8位补码分别表示rl=FEH,r2=FH,r3=90H,r4=F8H,若将运算结果存放在一个8位 寄存器中,则下列运算中会发左溢出的是 9) A. rI xr2 B. I2xr 14.假定变量i、f和d的数据类型分别为int, float和 double(int用码表示,font和 double分别用IEEE754 单精度和双精度浮点数格式表示),已知=785f=1.5678:3,d=1.5e100若在32位机器中执行下列关系表达 式,则结果为“真”的是 (I)r--(float(unt)r 4.在右图所示的平衡一叉树中,指入关键字48后得到一棵新平衡一叉树。在新平 (II)f=(float( doubl)f(Iv)d+f)d==f 衡二叉树中,关键字37所在结点的左、右了结点中保存钓关键字分别是 A.仅1和ⅡB.仅I和ⅢC.仅∏和ⅢD.仅Ⅲ和IV 15.15.假定用若干个2kx4位的芯广组成一个8kx8位的存储器,则地址0BIFH所在态片的最小地工是 C.24,53 D、24,90 A. 0000H C.0700H 5.在一棵度为4的树T屮,若有20个度为4的结点,10个度为3的结点,1个度 16.下列有关RAM和ROM的叙述中,正確的是 为2的结点,10个度为1的结点,则树T的叶结点个数是 IRAM是易失存储器,ROM是非易失性存储器 II RAM和ROM都采用随机存取方式进行信息访问 6.对n(n>2)个权值均不相同的字符构迨成哈大曼树。下列关于该哈大曼树的叙述中,错误的是。 III RAM和ROM都可用 Cache A.该树一定是一棵完全二又杯 IVRAM和ROM都需要进行刷新 B.树中一定没有度为1的结点。 A.仅1和ⅡB.仅1和Ⅲ1C.仅1,1和IVD.仅I:和V C.树中两个权值最小的结一定是兄弟结点 17.下列命中组合情况中,次访存过程中不可能发生的是 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值。 A.1LB木命中;(ache未命中,Page木命中 若尢向图G=(VE)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是 B.LB木命中, Cache命中,Page命中 B.15 D.21 C.TLB命中, Cache未命中,Page命中 8.对右图进行拓扑排序,可以得到不同的扑序列的个数是 D.TLB命中, Cache命中,Page未命中 18.下列寄存器中,汇编语言程序员可见的是 9.已知一个长度为16的顺序表L,其元素按关键字有序排列。若采月折半查 A.存储器地址寄在器(MAR) B.程序计数器PC) 找法查授一个L中个存在的元素,则关键字的比较次数最多的是。 C.存储器数据寄存器(MDR) D.指令寄存器(IR) B.5 D.7 19.下列选项中,不会引起令流水线阻塞是 10.采用递归方式对顾序表进行快速排序。下列关丁递归次数的叙述中,正确的是 A.数据旁路(转发) B.数据相关 A.递归次数与胡始数据的排列次序无关。 C.条件转移 D.资源冲突 干道论坛www.cskaoyan.com 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰手留余香 20.下列选项中的英文缩写均为总线标准的是。 则并发执行达程P0和P1时产生的情形是 A.PCI、CRT、LSB、旦S A.不能侏证进程互斥进入临界区,会出现“饥饿”现象 B.ISA、CPI、VESA、EISA B.不能侏证进程互斥进入临界区,不会出现“饥哦”现象 C.ISA、SCSI、RAM、MIPS C.能保证进程互斥进入临界区,会出现“饥饿”现象 D.ISA、LISA、PCI、PCI- Express D.能保证进程互斥过入临界区,不会岀现∵饥饿”现象 21.单级中析系统中,中断服务程序内的执行顺序是 28.某基于动态分区存储管理的计算机,其三存容量为55MR(初始为空闲),采用最佳适配( Best Fit)算法,分配 I保护现场 开中断 I关中断 IV保存断点 和释放的顺序为:分配L5MB,分配30MB,释放15MB,分配8MB,分配6MB,此时主存中最大空闲分 V中断事件处理Ⅵ恢复现场 区的大小是 A.->V->VI->T->VIT B. III->->V->VIT A. MB C. I OMB D. 15MR C. IL- NV->V-2VI->VT D. IV->->->VI-2VTT 29.某计算机采用一级页表的分存储管理方弌,按字节编址,页人小为210字节,页表项人小为2字节,逻辑 22.假定一台计算机的显示存储器用DRAM芯片实现,若要求显示分辨率为1600-1200,颜色深度为24位 地址结构为 帧频为85HZ,显存总带宽的50%用来刷新屏幕,则需要的显存总带宽夲少约为 页目录号 页号 页内偏移量 A. 245Mbps B. 979Mbps 逻辑地址空间大小为26页,则表示整个逻辑地空间的页目录表口包含表项的个数至少是 C. 1 958Mbps D. 7834Mbps 23.下列选项中,换作系统提供给应用序的接口是 30.设文什索引节点中有7个地址项,其中4个地项是直接地址紧引,2个地址项是一级间接地址索引,1 A.系统调用 B.十断 个地址顶是二级间接地址索引,每个地址项大小为4字节。若镃盘索引决和憾盍数据决大小均为256字节, 原语 则可表示的单个文件最大长度是 24.卜列选项中,导致创建浙进程的操作是 A. 33 KB B. 519KB C.057KBD.16513KB I压户登录成功 Ⅱ设备分配启动程序执行 31.设置当前工作目录的主要目的是 仪I和B.仪和ⅢC.仪1和ⅢD.I、Ⅱ和Ⅲ A.节省外存空同 B.节省内存空间 25.设与某资潺关联的信号量初值为3,当前值为1。若M表示该资源的可用个数,N表示等待该资源的进程 C.加快文件的检索速度 D.加快文件的读/写速度 数,则M,N分别是 32.本地用户通过键盘登陆系统时,首先获得键盘输入信息的程序是 A.U、1 B.1、0 D,2,0 A.命令解释程序 B.中断处理程序 26.下列选项中,降低迂程优先级的合理时机是 C.系统调用服务程序 D.用户登永程序 A.进程的时间片用 33.下列选项屮,不属于网络休系结构所描述的内容是 B.进程刚完成LO,进入就绪列队 A.网络的层次 B.每层使用的协议 C.进程长翡处于就绪列队中 C.协议的内部实现细芍 每层必须完成的功能 D.进程从就绪态转为运行态 34.在下图所示的采用存储转发”方式的分组交换网络中,所有链路的数据传输速率为100bps,分组人小为 27,进程P0和P1的共享变量定义及其初值为 1000B,其中分组头大小为20B。若主机H向主机H2发送个大小为980000B的文件,则在不考虑分组 boolean nag[2]: 拆装时间和传播延迟的情况下,从HI发送开始到H2接收完为止,需要的时间至少是。 flag[O= FATSF: flag[ 1]=FAISe, 若进P0和Pl访问临界资源的类C伪代码实现如下 void PU //进程P0 vOlc P1()/进程P1 B.80.08ns Whi⊥e(TRUE) Whi⊥ eRLE C.80.6ms 24 ms 35.某白治系统内采用RP协议,若该白治系统内的路由器R1收到其邻居路由器R2的距离矢量,距离矢量中 flag[0]=TRUE; turn=1 flag [1]=TRUE; turn=o while(flag[1]&s(turn--1)) while(flac [0]&4(tu 包含信息<net,16>,则能得出的结论是 A.R2可以经过R1到达retl,跳数为17 临界区 可以到达netl,跳数为15 flag[0]-FALSE flag [1]-ENLSE C.R可以经过R2到达retl,跳数为17 过R2到达 干道论坛www.cskaoyan.com 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰手留余香 36.若碎由器R因为用寒丢弃IP分组,则此时R可向发出该IP分组的源主机发送的ICMP报文类型是 寄存器间接 操作数=(Rn)) A.路由重定 B.目的不可运 010B存器间、目增(Rn)+操作数=(Rn)),(Rn)+1→Rn C.源点抑制 D.超时 相对 D(Rn 传移目标地址=(PC)+(Rn) 37.某网络的IP地址空间为192.168.5.0/24,采月定长子网划分,子网掩码为255.255.255.248,则该网络中的 最大子网个数、每个子网内的最大可分配地址个数分别是。 注:(X)表示有俑器地址Ⅹ或寄存器Ⅹ的内容 请叵答下列问题 A.32,8 1)该指令系统最多可有多少条指令?该计算机最多有多少个通用寄存器?存储器地址寄存器(MAR)和 存储器数据寄存器(MDR)至少各需要多少位? 38.下列网络设备中,能够抑制广播风暴的是 (2)转移指令的目标地址范围是多少? I中继器 I集线 Ⅲ网桥 Ⅳ路由器 )若操作码0010B表示加法操作(助记符为ad),寄存器R4和R5的编号弓分别为100B和101B,R4的内容 A.仅I和Ⅲ R.仅Ⅲ D.仅Ⅳ 为1234H,R5的内容为5678H,地址1234H的内容为5678H,地址5678H中的内容为1234H,则汇编语言为add C.仅和Ⅳ 39.主机甲和主机乙之间已建立了一个TCP连接,TCP最人段长度为1000字节。若主机甲的当前捱塞窗口为 (R4),(R5)”(逗亏前为源操作数,逗号后为目的操作数)对应的机器码是什么(用十六进訇表示)?该指 4000字节,在主机甲向主机乙连续发送两个最人段后,成功收到主机乙发送的第一个段的确认段,确认段 令执行后,哪些寄存器和存储单元中的内容会改变?改变后的内容是什么? 中通告的接收窗口人小为2000字节,则此时主机甲还可以向主机乙发送的最人字节数是 44.(12分)某计算机的主存地址空间大小为256MB,按字节编址。指令 Cache和数据 Cache分离,均有8 个 Cache行,每个 Cache行大小为64B,数据 Cache采用直接映射方式,现有两个功能相同的程序A和R B.2000 其伪代码如下所示: C,3000 D.4000 程序A: 程序B: 40.如果本地域名服务器无缓,当采用递归方法解析另一网络某主机域名时,用户主枳、本地域名服务器发 nta256][256 inta[256][25E] 送的域名请求消息数分别为 nt sum array-() B.一条、多条 int sum array2: C.多条、一条 D.多条、多条 3, s:Im=0 二、综合应用题:第41~47题,共70分 「r(i=0;i<256;⊥++) ur(i=C;i<256;1++) fo(j=0;j<256;j+- fxii=0;i<256;i++) 41.(10分)洛关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下 su:m + a[1]131 reTurn s ulI ReturN Sulll 标从O开始的一维数组,散列函数为:Hkey)=(kyx3)MOD7,处理冲突采用线性探测再散列法,要求波 填(载)因子为0.7 假定int类型数用32位补码表示,程序编译封i,j,sum均分配在寄存器口,数组a按行优先方式存放 (1)请画出所构造的散列表。 其首地址为320(十进制数)。请国答下列问题,要求说明理出或给出计算过程 (2)分别计算等概率情况下查找成功和查找不成功的平均查找长度 1)若不考忠月于 cache一致性丝护和替换算法的控制位,则数据 Cache的总容量为多少? 42.(13分)设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方自都尽可能高效的算 (2)数组元素a[0][31]和a[各自所在的土存块对应的Cahe行号分别是多少(Cahe行号从0开始)? 法。将R中保的序列循坏左移p(0n)个位置,即将R中的数据由(X0,1..xXn-1)变换为(Xp, (3)程序A和B的数据访问命中率各是多少?哪个程序的执行时间更短 Yp+1.Xn-1,X0.X1.Xp1)。要求 5.(7分冫假设计算机系统采用 CSCAN(循坏扫描〕磁盘谪度策略,使用2KB的内存空间记录16384个憾 (1)给出算法的其本设计思想 盘块的空闲状态 (2)根据设计思想,采月C或C+或JAⅥ语言描述算法,关键之处给出注释 (1)请说明在上述条件下如何进行磁盘块空闪状态的管理。 (3)说明你所设计算法的时间复杂度和空间复杂度 (2)设其单百磁盘旋转速度为每分钟6000转,每个磁道有100个扇又,相邻道间的平均移动时间为1ms 43.(11分)某计算机宰孓为16位,主在坤址空间大小为128KB,按字编址。采用单字长指令格式,指令各 若在某时刻,磁头位于100号磁道处,并沿着憾道号增大的方向移动(如卜图所示),憾道号请求队列为50, 字段定义如下 ∞0,30,120,对请求队列中的每个磁道需读取1个随机分布的厨区,则读完这4个扇区点共需要多少时间?要 1211 65 求给出计算过程 Ms 〔3)如臭将嵫盐替換为随机访问的rash半导体行储器(如U、SSD等),是否有比 CSCAN更鳥效的憾 源探作数 日的操作数 盘调度策眳?若有,给出磁盘调度策略的名称并说明理由;若无,说明理曰。 转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义如下: Ms/Md 寻址方式 助记符 含义 奇行器直接 Rn 操作数-Rn) 干道论坛www.cskaoyan.com 予人玫瑰手留余斧 于道论坛www.cskaoyan.com 予人玫瑰手留余香 0号磁道 参考答案 隴机分布的某扇区 单项选子题 C5. 8.B 头移动方向 11.A12 14.B 15.D 18.B 19.A 21.A 22.D 23.A 24.C 号磁道 R30.C31 、综合应用题 6.(8分)设某汁算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page) 41.解答 数据存偕空同,页的大八为1KB,操作系统采用定分配局部置换策略为此诖程分配4个页框( Page frame)。 (1)由装载因子7,数据总数为7,得一维数红大小为707=10,数红下标为09。所构造的散列函数值如 在时刻260前钓该步程访问情况如下表所小(访问位即使用位 所小 页号 页框号 装入时刻 访问位 kev 83011|18914 0 130 0 365560 4 采用线性探测再散列法处理冲突,所杓造的散列表为 200 地址 6 60 关键字7 当亥进程扶行到时刻260封,要汸问逻辑地址为17CAH的数据。请叫答下列问题 (2)査找成功时,是根据每个厂素查找次数来训算平均长度,在等概率的情况下,各关键字的查找次数为: (1)该逻辑地址对应的页号是多少? 8 30 (2)若采用先进先出(FIFO)置换算沄,该逻辑地址对应的物地址是多少?要求给出计算过程 18 (3)若采用时钟CICK)置换算法,该逻辑地址对应的物理地址是多少?要求治出训算过程(设 搜索下一页的指针沿顺时针方向移动,且当前指向2号页框,小意图如下) 故,AS1=查找次数1几素个数=(1+2+1+1+1+3+3)/7=12/7 这里要特别防止惯性思维。查抆失败时,是根据査找失败位置计算平均次数,根据散列函数MOD7.初始 只可能在0-6的位置。等概率情况下,查找06位置查找矢败的查找次数为 q号页柜 3号页 2号页\号夏框 5 5 故,ASL不力一查找次数/散列后的地址个数-(3+2+1+2+1+5+4)!7-18/7 、C号页 1号页 号页框 7号贞枉 42.解答 1)算法的基本设计思想 图3.15页框示意图 可以将这个问题看做是把数组ab转換成效组ba(a代表数组的前p个元素,b代表数纠中余下的np个元 47.(9分)某局域网采用CSMA/CD协议实现介质访问控制,数据传输运为10Mbps,主机甲和主杌乙之问 素),先将a逆置得到ab,再将b遵置得到ab,最后将整个a1b逆置得到(ab)-ba。设 Reverse图数执 的离为2km,信号传播速度是200000kms。请回答下列问向题,要求说明理由或写出计算过程。 行将数组元素逆置的换作,对 abcdefgh向左循环移动3(p-3)个位置的过程如下 (1)若主机甲和三机♂发送数据时发生冲突,则从开始发送数据时刻起,到两台主机均检测到冮突时刻止, Reverse(0,p-1)得到 cade fgh 最短需经过多长时间?最长需经过多长时问(假没主机甲和主机乙发送数据过程中,其他主机不发送数拒)? Reverse(p,1)得到 cbahgfed; (2)若网络不存在仁何冲突与差错,主机甲总是以标准的最长以太网数据帧(1518字节)向主机乙发送效 Reverse(O,n-1)得到 defghabc 据,主机乙每成功收到一个数据帧后立即忾主机甲发送一个64字节的确认帧,主机甲收到确认帧后方可发送下 注: Reverse中,两个参数分别表示数组中待转换元素的始末位置。 个数据帧。此时主机甲的有效数据传输速率是多少(不考虑以太网的前导码)? (2)仅用c语言摧述算法如下 void Reverse(int R[], int from, int to)i 【实例截图】
【核心代码】