计算机-408真题和答案2009-2017年

所需积分/C币:16 2019-05-06 17:12:59 2.72MB PDF
19
收藏 收藏
举报

历届计算机科学与技术考研真题详解、答案。历届计算机科学与技术考研真题详解、答案。历届计算机科学与技术考研真题详解、答案。
oCn中公考研 中公考研学员内部资料 下来的4个RTT(往返时间)时间内的TCP段的传输郗是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥 塞窗口大小是 A. 7KB B. 8KB C. 9KB D. 16KB 40.FTP客户和服务器间传递FTP命令时,使用的连接是 A.建立在TCP之上的控削连孩 B.建立在TCP之上的数据连接 C.建立在UDP之上的控制连接 D.建立在UDP之上的数据连接 二、综合应用题:第41~47题,共70分。 41.(10分)带权图(权值非负,表小边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径 假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法 ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点 ②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v; ③重复步骤②,直到u是日标顶点时为止 请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明 42.(15分)已知一个带有表头结点的单链表,结点结构为: data link 假设该链表只给出了头指钳list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为 正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求: 1)描述算法的基本设计思想。 2)描述算法的详细实现步骤。 3〕根据设计思想和实现步骤,采用程序设计语言描述算法(使用C、C艹+或Java语言实现),关键之处请给出简要注释 43.(8分)某计算机的CPU主频为500M,C門为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为 0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条 指令的执行时间。请回答卜列问题,要求给 出计算过程 1)在中断方式下,CPU用于该外设IO的时间占整个CPU时间的百分比是多少? 2〕当该外设的数据传输率达到5MB/s时,改用DMA方式传送数捱。假定每次DMA传送块大小为 5000B,且DⅥA预处哩和后处理的总开销为500个时钟周期,则CPU用丁该外设IO的时间占整个CPU 间的百分比是多少?(假设DMA与CPU之间没有访存冲突) 44.(I3分)某计算机字长为16位,采用16位定长指令字结构,部分数据通路结构如图A-2所示,图中所有控制信号为1时表示有 效、为0时表示无效。例如,控制信号 MDRinE为1表示允许数据从DB打入MDR, MDRin为1表示允许数据从内总线打入MDR3假 设MAR的输出一直处于使能状在。加法指令“ADD(R1),R0”的功能为(RU)+(R1)(R1),即将R0中的数据与R1的内容所指主存单元的 数据相加,并将结果送入R1的内容所指主存单元中保存。 存储器(M) emR Addr DB MDRoutE-4 MAR -MARin MDRin-MDR--MDRinE MDRout ROut ROin- Ro H △ POut PCin RIot ADD RIin--Rl PC:I ACin--AC R 控制信号图例 ACout xout三态门及其控制信号 至指令译码部件 Xin寄存器输入控制信号 表A-1给出了上述指令取指和译码阶段每个节拍(时钟周期)的功能和有效控制信号,请按表中描述方式用表格列出指令执行阶段每 个节拍的功能和有效控制信号。 表A-1 时钟 功能 有效控制信号 C1 MAR←(PC) POut、 MARin MDR←M(MDR C2 PC←(PC)+1 MemR. MDRinE. PC+l IR←(DR) MD Rout. IRin 指令译吗 4 oCn中公考研 中公考研学员内部资料 45.(7分)三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用 produce 生成一个正整数并用puO送入缓冲区某一空单元中;P2每次用 goddo从该缓冲区中取出一个奇数并用 countoddo统计奇数个数;P3每次用 getevenO从该缓冲区中取出一个偶数并用 counteveno统计偶数个数。请用信号量机制实现这三个进程的同步 与互斥活动,并说明所定义信号量的含义。要求用伪代码描述 46.(8分)请求分页管理系统中,假设某进程的页表內容见表A-2 表A-2 页 页框( Page frame 有效位(存在位) 101I 页面大小为4KB,一次内存的访问时间为100ns,一次快表(TLB)的访问时间为10ns,处理一次缺页的平均时间为10%ns(已含更 新TLB和页表的时间),进稈的驻留集大小固定为2,采用最近最少使用置换算法(LRU)和局部淘汰策略。假设①TLB初始为空:②地 址转换时先访问TIB,若TB未命中,再访问页表(忽略访问页表之后的TIB更新时间):③有效位为0表示页面不在内存,产生缺页 中断,缺页中断处理后,返冋到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H,请问: 1)依次访问上述三个虚地址,各需多少时间?给出计算过程。 2)基丁上述访问序列,虚地址1565H的物理地址是多少?请说明理由。 47.(9分)某网络拓扑如图A-3所示,路由器R1通过接口E1、E2分别连接局域网1、局域网2,通过接口L0连接路由器R2,并 通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是 202.118.2.1,R2的L0接口的IP地址是20211822,L1接口的IP地址是130.11.120.,1,E0接口的IP地 址是202.118.3,1,域饣服务器的IP地址是202.118.3.2 互联网 LO 局域网1 202,118,2.2 lsU.1.I20. 20L.II&,2. 卫(后战网2 02.I18.3.1 域名服务器 202.18.3.2 图A-3 R1和R2的路由表结构为 L日的T地址千N掩的 下一跳IP地址 接口 1)将IP地址空间202118.1.0/24划分为2个子网,分别分配给局域网1、局域网2,每个局域网需分配的IP地址数不少于120个。请给出 子网划分结果,说明理由或给出必要的计算过程。 2〕请给出RI的路由表,使其明确包括到局域网Ⅰ的路由、局域网2的路由、域名服务器的主机路由和互联网的路由 3〕请采用路由聚合技术,给出R2到局域网1和局域网2的路由。 Of中公考研 中公考研学员内部资料 答案如下 、选择题 4 6 7 8 9 10 B B A 13 15 16 18 19 20 C D 21 24 26 C B B B 、综合应用题 41.该方法求得的路径个一定是最短路径。例如,对于下图所示的带权图,如果按照题中的原则,从A到 C的最短路径为A→B→C,事实上其最短路径为A→D→丶C D 42 (1)算法基思想如下:从头至尾遍历单链表,并用拦针p指向当前结点的前k个结点。当遍历到链表 的最后一个结点时,指针p所指向的结点即为所查找的结点。 (2)详细实现步骤:增加两个指针变量和一个整型变量,从链表头向后遍历,其中指针p1指向当前遍 历的结点,指针p指向p1所指向结点的前k个结点,如果p1之前没有k个结点,那么p指向表头 结点。冋整型变量ⅰ表示当前遍历了多少个结点,当ⅳk时,指针p随着每次遍历,也向前移动一个结 点。当遍历完成时,p或者指向表头结点,或者指向链表屮倒数第k个位置上的结点。 (3)算法摧述 int LocateElement(Linklist list, int k) p1=list->link p=list; i=1 ile(p1) p1=p1->ink f(>k)p=p>next;∥果ik,则p也往后移 f(p=|ist) return o;∥说明链表没有k个结点 else printf(“%dn“,p->data); return 1 6f中公考研 中公考研学员内部资料 43. (1)在中断方式下,每32位(4B)被中断一次,故每秒中断 0.5MB4B=0.5×10614=125×104次要注意的是,这里是数据传输率,所以1MB=106B。因为中 断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间,且执行每条指令平均需 5个时钟周期,所以,1秒内用于屮断的时钟周期数为 (18+2)×5×12.5×104=12.5×106 (2)在DMA方式下,每秒进行DMA操作 5MB/5000B=5×1065000=1×103次因为DMA预处理和后处理的总开销为500个时钟周期 所以1秒钟之内用于DMA操作的时钟周期数为 500×1×103=5×105 故在DMA方式下,占整个CPU时间的百分比是 (5×105)/(500×106))×100%=0.1% 44.撸令执行阶段每个节拍的功能和有效控制信号如下所 时钟 功能 有效控制信号 C5 MAR←(R1) PCout MARin 6 MDR←MMAR) MemR. MARinE C7 A←(RO) ROout ain AC←(MDR)+(A) MDRout Addr Acin MDR←(AC) ACout. Morin C10 M(MAR)←MDR MDRoute Memw 45.定义信号量S1控制P1与P2之间的同步:S2控制P1与P3之间的同步: empty控制生产者与 消费者之间的同步; mutex控制进程间互斥使用缓冲区。程序如下:vars1=0,s2-0, empty=N, mutex=1 Arbi P1: begin X= produce();/生成一个数* P( empty);/判断缓冲区是否有空单元* P( mutex);/*缓冲区是香被占用 Puto fx%2==0 V(s2);/如果是偶数,向P3发出信号* else V(s1);/如果是奇薮,向P2发出信号 ∨( mutex);/使用完缓沖区,释放 P2 begin P(s1);收到P1发来的信号,已产生一个奇数 );缓冲区是否被占用 Getodd(); Countodd(:= counted()+1;V( mutex);/释放缓冲区* pty);/向P1发信号,多出一个空单元 P3: begin P(s2)收到P1发来的信号,已产生 偶数 );/*缓冲区是否被占用 Geteven(); Counteven():= counter()+1;V( mutex);/释放缓冲区* ty);/*向P1发信号,多出一个空单元 end 46 (1)根据贞式管理的工作原理,应先考虑页血大小,以便将贝号和内位移分解出来。贞面大小为 4KB,即212,则得到贞内位移占虚地址的低12位,页号占剩佘高位。可得三个虚地址的贞号P如 下(十六进制的一位数宇转换成4位二进制,因此,六进制的低三位正好为贞内位移,最高位为页 号 2362H:P=2,访问快表10ns,因初始为空,访问页表100ns得到页框号,合成物坦地址后访问主存10 Of中公考研 中公考研学员内部资料 0ns,共计 10ns+100ns+100ns=210ns 1565H:P=1,访问快表10ns,落空,访问页表100ns落空,进行缺页中断处坦108ns,合成物理地址 后访问主存 100ns,共计 10ns+100ns+108ns+100ns≈108ns 25A5H:P=2,访问快表,因第一次访问已将该页号放入快表,因此花费10ns便可合成物理地址,访问主存 100ns,共计10ns+100ns=110ns (2)当访问虚地址1565H时,产生缺页中断,合法驻留集为2,必须从页表中淘汰一个页面,根据题目 的置换算法,应淘汰0号页面,因此1565H的对应页框号为101H。由此可得1565H的物理地址为 10 1565H。 47 (1)无类|P地址的核心是采用不定长的网络号和主机号,并通过相应的子网掩码米表示(即网络号 部分为1,主机号部分为0)。本题中网络地址位数是 24,由于P地址是32位,因此其主机号部分就是8位。因此,子网掩码就是 11111111111111111111111100000000,即255255255.0 根据无类P地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全 1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。 该网络要划分为两个子网,每个子网要120台主机,因此主机位数Ⅹ应该满足下面三个条 件:×<8,因为是在主机号位长为8位的网络进行划分,所以X一定要小于8位。 2x>120,因为根据题意需要容纳120台主机。X是整数。 解上述方程,得到X7.子网掩码就是1111111111111111111 10000000,即255255255128。所以划分的两个网段是:202.118.1.025与202.118.1.128/25 (2)填写R1的路由表 填写到局域网1的路由。局域网1的网络地址和掩码在问题(1)已绎求出来了,为202.118.1.0/25 则R1路由表应填入的网络地址为202.118.1.0,掩码为255255255.128。由于局域网1是自接连 接到路由器R1的ε1口上的,因此,下一跳地址填写直接路由( Direct)。接口填写E1 填写到局域网2的路由表1。局域网2的网络地址和掩码在问题(1)中已经求出来了,为 202.1181.128/25则R1路由表应该填入的网终地址为 202.1181.128,掩码为255255.255.128.由于局域网2是直接连接到路由器R1的E2口上的,因 此 逃地址填写直接烙由。接口填写E2。 填写到域名服务器的路由。由于域名服务器的旧P地址为202.118.3.2,而该地址为主机地址,因掩码 为255255.255255。同时,路由器R1要到DNs服务器,就需要通过路由器R2的接口L0才能到 达,因此下一跳地址填写L0的|P地址(202.118.2.2) 填写互联网路由。木题实质是编写默认路由。默认路由是一种特殊的静态路由,指的是当路由表中与包的 目的地址之间没有匹配的表项时路由器能够做出的选扦。如果没有默认路由器,那么目的地址在路由表中没 有匹配表项的包将被丟弃。默认路由在某些时候非常有效,当存在末梢网终时,默认路由会大大简化路 由器的配置,减轻管理员的工作负担,提高网络性能。默认路由叫做“Oo'路由,因为路由的IP地址 0.0.0.0,而子网掩码也是0.0.0.0。同时路由器R1连接的网络需要通过路由器R2的L0口才能到 达互联网络,因此下一跳地址填写LO的|P为202.118.2.2。 综上,填写的路由表如下 R1路由器 目的网络IP地址 子网掩码 下一跳IP地址 接口 202.118.1.0 255.255.255.128 Direct E1 202.118.1.128 255.255.255.128 Direct E2 202.118.3.2 255.255255.255 202.1182.2 LO 0.0.00 0.0.0.0 202.118.2.2 LO (3)填写R2到局域网1和局域网2的路由表2。局域网1和局域网2的地址可以聚合为 202.118.1.0/24,而R2去往局域网1和局域网2都是同一条路径。因此,路由表里面只需要填写到 202.118.1 0/24网络的路由即可,如下表所示R2路由表 目的网绪|P地址 」恻掩码 下一刷P地址 接口 202.118.1.0 255.255.2550 202.118.2.1 LO 8oft中公考研 中公考研学员内部资料 2010年全国硕士研究生入学统一考试 讣算机科学与技术学科联考 计算机学科专业基础综合试题 、单项选择题:第1~40小题,每小题2分,共80分。卜列每题给出的四个选项中,只 有一个选项最符合试题要求。 1.若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次 进行退栈操作,则不可能得到的出栈序列是() b, f, a B. c, b, d, c. b, c, a, e,f, d D. a, f, e, d, c, b 2.某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,若元素a,b,c,d, e依次入此队列后再进行出队操作,则不可能得到的出队序列是()。 b, a, d, e b. d, b c.d b, c, a, c D. e, c, b, a, d 3.下列线索二叉树中(用虚线衣示线索),符合后序线索树定义的是 NULL NULL NULL B NULL NULL 4.在下图所小的平衡二叉树中,插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树 中,关键字37所在结点的左、右子结点中保存的关键字分别是( A.B3、48 B.24、48 C.24、53 D.24、90 5.在棵度数为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2 的结点,10个度为1的结点,则树T的叶结点个数是()。 B.82 C.113 D.122 6.对n(n∞2)个权值均八相同的字符构成赫夫曼树。下列关于该赫夫曼树的叙述中,错误 的是 A.该树一定是一棵亢全:叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 7.若无向图G-(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需 要的边数最少是()。 B.15 C.16 D.21 Of中公考研 中公考研学员内部资料 8.对下图进行拓扑排序,可以得到不同拓扑序列的个数是()。 A.4 B.3 C.2 D.1 9.已知个长度为16的顺序衣L,其元素按关键字有序排列。若采用折半查找法查找个 L中不存在的元素,则关键字的比较次数最多是() A.4 B.5 D.7 10.采用递归方式对顺序表进行快速排序。卜列关于递归次数的叙述中,止确的是()。 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 则采用的排序方法可能是()。 A.起泡排序 B.希尔排序 C.归并排序 D.基数排序 12.下列选项中,能缩短程序执行吋间的措施是() 提高CPU时钟频率 Ⅱ.优化数据通路结构 Ⅲ.对程序进行编译优化 A.仅和Ⅱ B.仅Ⅰ和Ⅲ C.仅Ⅱ和Ⅲ D 和I 13.假定有4个整数用8位补码分别表示为r1-FEH,r2-F2H,r3-90H,r4-F8H。若将运算 结果存放在一个8位寄存器中,则下列运算中会发生溢出的是() B.r2×r3 C.rl×r4 D.r2×r4 14.假定变量i、f、d数据类型分别为int、foat、 double(int用补码表小,foat和 double分 别用IEE754单精度和双精度浮点数据格式衣示),已知ⅰ785,f-1.5678e3,d-1.5e10,右 在32位机器中执行下列关系表达式,则结果为“真”的是() (int(float ) float(int)f III. f=(float) (double)f ⅣV.(d+f)d=f A.仅Ⅰ和Ⅱ B.仪Ⅰ和Ⅲ C.仅Ⅱ和l D.仅Ⅲ和Ⅳ 15.假定用若干个2K×4位芯片组成个8K×8位的存储器,则地址 OBIFH所在芯片的最 小地址是() A.0000H B.0600H C.0700H D.0800H 16.下列有关RAM和ROM的叙述中,正确的是( RAM是易失性存储器,ROM是非易失性存储器 Ⅱ.RAM和ROM都是采用随机存取方式进行信息访问的 Ⅲ.RAM和ROM都可用做 Cache Ⅳ.RAM和ROM都需要进行刷新 A.仅Ⅰ和Ⅱ B.仅Ⅱ和Ⅲ C.仅Ⅰ、Ⅱ和I D.仅ll、Ⅲ、Ⅳ 17.下列命中组合情况中,“次访存过程中不可能发生的是()。 A.TLB未命中, Cache未命中,Page未命中 B.TLB未命中, Cache命中,Page命中 C.TLB命中, Cache末命中,Page命中 D.TLB命中, Cache命中,Page未命中 18.下列寄存器中,汇编语言程序员可见的是()。 1of中公考研 中公考研学员内部资料 A.存储器地址寄存器(MAR)B.程序计数器(PC) C.存储器数据寄存器(MDR)D.指令寄存器(IR) 19.下列选项中,不会引起指令流水阻塞的是()。 A.数据旁路(转发) B.数据相关 C.条件转移 D.资源冲突 20.下列选项中的英文缩写均为总线标准的是()。 A.PCI、CRT、USB、EISA B.ISA、CPI、ⅤESA、EISA C.ISA、SCSI、RAM、MIPS D.ISA、EISA、PCI、 PCI-Express 21.单级中断系统中,中断服务程序执行顺序是()。 保护现场 Ⅱ.开中断 Ⅲ.关中断 Ⅳ.保存断点 V.中断事件处理 Ⅵ.恢复现场 Ⅶ.中断返回 A.I→>V->Ⅵ→Ⅱ->Ⅶ B.II->I->V->Ⅶ C.Ⅲ->Ⅳ>V->Ⅵ->Ⅶ D.Ⅳ->1->V->Ⅵ->Ⅶ 22.假定一台计算机的显示存储器用DRAM芯片实现,若要求显示分辨率为1600×1200, 颜色深度为24位,帧频为85Hz,显存总带宽的50%用来刷新屏幕,则需要的显存总带宽至 少约为()。 A. 245Mbit/s b. 979Mbit/ C. 1958Mbit D. 7834Mbit/s 23.下列选项中,操作系统提供的给应用程序的接∏是 )。 系统调用B.中断 C.库函数 D.原语 24.下列选项中,导致创建新进稈的操作是 I.用户登录成功 ∏1.设备分配 Ⅲ.启动程序执行 A.仅Ⅰ和ⅡB.仅Ⅱ和ⅢC.仅Ⅰ和ⅢD.I、Ⅱ、Ⅲ 25.设与某资源相关联的信号量初值为3,当前值为1。若M表示该资源的可用个数,N 表示等待该资源的进程数,则M、N分别是()。 A.0、1 B.1、0 C.1、2 D.2、0 26.下列选项中,降低进程优先级的合理时机是()。 A.进程的时间片用完 B.进程刚完成LO,进入就绪列阝 C.进程长期处于就绪列队 D.进程从就绪状态转为运行态 27.进行p0和p1的共享变量定义及其初值为: boolean flag[2] int turn=0 nag[o]-FALSE; flag[1]=FALSE 若进行p0和pl访问临界资源的类C代码实现如下: void poO∥进程pO void p10∥进程pl i whilc (TRue) i whilc True) i flagloFTRUE; turn=l i flagllFTRUE: turn=0 While (nlag[l]&&(turn==1)) While (nag[o]&&(turn==0) 临界区 临界区; flag FALSe flagyl=FALSE 则并发执行进程p0和p1时产生的情形是()。 A.不能保证进程互斥进入临界区,会出现“饥饿”现象 B.不能保证进程互斥进入临界区,不会出现“饥饿”现象 C.能保证进程互斥进入临界区,会出现“饥饿”现象 D.能保证进程互斥进入临界区,不会出现“饥饿”现象28.某基于动态分区存储管理的计 算机,其主存容量为55MB(初始为空闲),采用最佳适应分( Best fiu)算法,分酉和释 放的顺序为:分配15MB,分配30MB,释放15MB,分配8MB,分配6MB,此时主存中 最大空闲分区的大小是( A. 7MB B. 9MB C. 1OMB D. 15MB 29.某计算机釆用二级页表的分页存储管理方式,按字节编制,页的大小为210字节,页表 项大小为2字节,逻辑地址结构为: 逻辑地址空间大小为216页,则表示整个逻缉地址空 页目录号 页号 页内偏移量

...展开详情
试读 101P 计算机-408真题和答案2009-2017年
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享小兵

关注 私信
上传资源赚钱or赚积分
最新推荐
计算机-408真题和答案2009-2017年 16积分/C币 立即下载
1/101
计算机-408真题和答案2009-2017年第1页
计算机-408真题和答案2009-2017年第2页
计算机-408真题和答案2009-2017年第3页
计算机-408真题和答案2009-2017年第4页
计算机-408真题和答案2009-2017年第5页
计算机-408真题和答案2009-2017年第6页
计算机-408真题和答案2009-2017年第7页
计算机-408真题和答案2009-2017年第8页
计算机-408真题和答案2009-2017年第9页
计算机-408真题和答案2009-2017年第10页
计算机-408真题和答案2009-2017年第11页
计算机-408真题和答案2009-2017年第12页
计算机-408真题和答案2009-2017年第13页
计算机-408真题和答案2009-2017年第14页
计算机-408真题和答案2009-2017年第15页
计算机-408真题和答案2009-2017年第16页
计算机-408真题和答案2009-2017年第17页
计算机-408真题和答案2009-2017年第18页
计算机-408真题和答案2009-2017年第19页
计算机-408真题和答案2009-2017年第20页

试读结束, 可继续阅读

16积分/C币 立即下载