《全国硕士研究生入学统一考试-计算机科学与技术学科联考计算机学科专业基础综合试题.pdf》由会员分享，可在线阅读，更多相关《全国硕士研究生入学统一考试-计算机科学与技术学科联考计算机学科专业基础综合试题.pdf（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第140小题，每小题2分，共80分。下列每题给出的四个选项中,只有一个选项最符合试题要求。1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机 将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结 构应该是_。A.栈 B.队列 C.树 D.图 Q2.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进 厂 入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是_o
2、0 A.1 B.2 C.3 D.4 瓜3.给定二叉树如图A-l所示。设N代表二叉树的根，L代表根结点的左子 二 树，R代表根结点的右子树。若遍历后的结点序列是3,1,7,5,6,2,4,则 图A 其遍历方式是 oA.LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是 oA.B C.D.5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点 个数最多是。A.39 B.52 C.Il l D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在 原来的森林中，u和v可能具有的关系是 oI.父子关系 n.
3、兄弟关系III.U的父结点与V的父结点是兄弟关系A.只有 II B.1 和 II C.1 和HI D.1、II 和HI7.下列关于无向连通图特性的叙述中，正确的是。I,所有顶点的度之和为偶数II.边数大于顶点个数减1-1-III.至少有一个顶点的度为1A,只有I B.只有n C.I和H D.1和HI8.下列叙述中，不符合m阶B树定义要求的是.A.根结点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接9.已知关键字序列5,8,12,19,28,20,整后得到的小根堆是。A.3,5,12,8,28,20,15,22,1915,22是小根堆（最小堆
4、），插入关键字3,调B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,1910.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A,冒泡排序 B.插入排序C.选择排序 D.二路归并排序11.冯诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据 是 OA.指令操作码的译码结果 B.指令和数据的寻址方式C.指令周期的不同阶段 D.指令和数据所在的存储单元12.一个C语言程序在一台32位机器上运行。程序中定义
5、了三个变量x、y和z,其中x和 z为int型，y为short型。当x=127,y=-9时，执行赋值语句z=x+y后，x、y和z的值分别是。A.x=0000007FH,y=FFF9H,z=00000076HB.x=0000007FH,y=FFF9H,z=FFFF0076HC.x=0000007FH,y=FFF7H,z=FFFF0076HD.x=0000007FH,y=FFF7H,z=00000076H13.浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数 X=27X29/32,Y=25
6、X5/8,则用浮点加法计算X+Y的最终结果是。A.00111 1100010 B.00111 0100010C.01000 0010001 D.发生溢出14.某计算机的Ca c he共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大 小为32B,按字节编址。主存129号单元所在主存块应装入到的Ca c he组号是。A.0 B.1 C.4 D.615.某计算机主存容量为64KB,其中ROM区为4KB,其余为RAM区，按字节编址。现要 用2KX8位的ROM芯片和4KX4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯 片数和RAM芯片数分别是 oA.1、15 B.2、15 C.1
7、、30 D.2、3016.某机器字长为16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字 节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转 移指令所在主存地址为2000H,相对位移量字段的内容为06H,则该转移指令成功转移后的目标地址 是。A.2006H B.2007H C.2008H D.2009H17.下列关于RISC的叙述中，错误的是。A.RISC普遍采用微程序控制器-2-B.RISC大多数指令在一个时钟周期内完成C.RISC的内部通用寄存器数量相对CISC多D.RISC的指令数、寻址方式和指令格式种类相对CISC少18.某计算机
8、的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之 间的缓存时间）分别为90ns、80ns、70ns、和60ns,则该计算机的CPU时钟周期至少是。A.90ns B.80ns C.70ns D.60ns19.相对于微程序控制器，硬布线控制器的特点是 oA.指令执行速度慢，指令功能的修改和扩展容易B.指令执行速度慢，指令功能的修改和扩展难C.指令执行速度快，指令功能的修改和扩展容易D.指令执行速度快，指令功能的修改和扩展难20.假设某系统总线在一个总线周期中并行传输4B信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz,则总线带宽是 oA.10MB/s B.20MB/
9、s C.40MB/s D.80MB/s21.假设某计算机的存储系统由Ca c he和主存组成，某程序执行过程中访存1000次，其中 访问Ca c he缺失（未命中）50次，则Ca c he的命中率是。A.5%B.9.5%C.50%D.95%22.下列选项中，能引起外部中断的事件是 oA.键盘输入 B.除数为0C.浮点运算下溢 D.访存缺页23.单处理机系统中，可并行的是 oI进程与进程 n处理机与设备 ni处理机与通道 iv设备与设备A.I、II和III B.I、n和IVC.I、in和W D.II、HI和W24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是 oA.时间片轮转调度算法
10、B.短进程优先调度算法C.先来先服务调度算法 D.高响应比优先调度算法25.某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是 oA.2 B.3 C.4 D.526.分区分配内存管理方式的主要保护措施是 oA.界地址保护 B.程序代码保护 C.数据保护 D,栈保护27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是。A.28B B.2,6B C.224B D.232B28.下列文件物理结构中，适合随机访问且易于文件扩展的是 oA.连续结构 B.索引结构C.链式结构且磁盘块定长 D.链式结构且磁盘块变长29.假设
11、磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求 序列为35,45,12,68,110,180,170,195,采用SCAN调度（电梯调度）算法得到的磁道访 问序列是 OA.110,170,180,195,68,45,35,12-3-B.110,68,45,35,12,170,180,195C.110,170,180,195,12,35,45,68D.12,35,45,68,110,170,180,19530.文件系统中，文件访问控制信息存储的合理位置是 oA.文件控制块 B.文件分配表 C.用户口令表 D.系统注册表31.设文件F1的当前引用计数值为1,先建立F1的
12、符号链接（软链接）文件F2,再建立 F1的硬链接文件F3,然后删除F1。此时，F2和F3的引用计数值分别是。A.0、1 B.1 C.1、2 D.2、132.程序员利用系统调用打开I/O设备时，通常使用的设备标识是 oA.逻辑设备名 B.物理设备名C.主设备号 D.从设备号33.在OSI参考模型中，自下而上第一个提供端到端服务的层次是 oA.数据链路层 B.传输层 C.会话层 D.应用层34.在无噪声情况下，若某通信链路的带宽为3kHz,采用4个相位，每个相位具有4种振幅 的QAM调制技术，则该通信链路的最大数据传输速率是 oA.12Kb it/s B.24Kb it/s C.48Kb it/s
13、 D.96Kb it/s35.数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为07的帧。当计时 器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是 oA.2 B.3 C.4 D.536.以太网交换机进行转发决策时使用的PDU地址是。A.目的物理地址 B.目的IP地址 C.源物理地址 D.源IP地址37.在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为IGb it/s,电缆中的信号传播速度为200 000km/s。若最小数据帧长度减少800b it,则最远的两个站点之间的 距离至少需要 oA.增加160m B.增加80m C.减少160m
14、 D.减少80m38.主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段,分别包含300B和500B的有效载荷，第一个段的序列号为200,主机乙正确接收到两个段后，发 送给主机甲的确认序列号是 oA.500 B.700 C.800 D.100039.一个TCP连接总是以1KB的最大段长发送TCP段，发送方有足够多的数据要发送。当 拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都 是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小 是 OA.7KB B.8KB C.9KB D.16KB40.FT
15、P客户和服务器间传递FTP命令时，使用的连接是 oA.建立在TCP之上的控制连接 B.建立在TCP之上的数据连接C.建立在UDP之上的控制连接 D.建立在UDP之上的数据连接二 综合应用题：第4147题，共70分。41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从 初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种-4-解决该问题的方法：设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；选择离U最近且尚未在最短路径中的一个顶点V,加入到最短路径中，修改当前顶点u=v；重复步骤，直到u是目标顶点时为止。请问上述方法能否求得
16、最短路径？若该方法可行，请证明之；否则，请举例说明。42.（15分）已知一个带有表头结点的单链表，结点结构为：d atalink假设该链表只给出了头指针l isto在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的d a ta域的值,并返回1:否则，只返回0。要求：1）描述算法的基本设计思想。2）描述算法的详细实现步骤。3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C+或Ja v a语言实现）,关键之处请给出简要注释。43.（8分）某计算机的CPU主频为500MHz,CPI为5（即执行每条指令平均需5个
17、时钟周 期）。假定某外设的数据传输率为0.5MB/S,采用中断方式与主机进行数据传送，以32位为传输 单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？2）当该外设的数据传输率达到5MB/S时，改用DMA方式传送数据。假定每次DMA传送块 大小为5000B,且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的 时间占整个CPU时间的百分比是多少（假设DMA与CPU之间没有访存冲突）？44.（13分）某计算机字长为16位，采用1
18、6位定长指令字结构，部分数据通路结构如图A-2 所示，图中所有控制信号为1时表示有效、为0时表示无效。例如，控制信号MDRinE为1表示 允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一 直处于使能状态。加法指令ADD（RI）,R0”的功能为（RO）+（R1）-（R1）,即将R0中的数据与 R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。存他器（M）MemRMemW DataAddr 0）个单元的缓冲区。P1每次用 prod uc e。生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getod d（）从该缓冲区
19、中 取出一个奇数并用c ountod d。统计奇数个数；P3每次用getev en。从该缓冲区中取出一个偶数并 用c ountev en。统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定 义信号量的含义（要求用伪代码描述）。46.（8分）请求分页管理系统中，假设某进程的页表内容见表A-2。页面大小为4KB,一次内存的访问时间为100ns,一次快表（TLB）的访问时间为10ns,处理一次缺页 的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2,采用最近最少使用置换算 法（LRU）和局部淘汰策略。假设TLB初始为空；地址转换时先访问TLB,若TLB
20、未命中，再访问页 有效位为0表示页面不在内存中，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H,请问：1）依次访问上述三个虚地址，各需多少时间？给出计算过程。2）基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。47.（9分）某网络拓扑如图A-3所示，路由器R1通过接口 El、E2分别连接局域网1、局域 网2,通过接口 L0连接路由器R2,并通过路由器R2连接域名服务器与互联网。R1的L0接口 的 IP 地址是 202.118.2.1,R2 的 L0 接口的 IP 地址是 202.11822,L1 接口的 I
21、P 地址是 130.11.120.1,E0接口的IP地址是202.118.3.1,域名服务器的IP地址是202.118.3.2。表A-2页号页框(Page Frame)号有效位（存在位）0101H11022 5 4H1表（忽略访问页表之后的TLB更新时间）;图A-3-6-R1和R2的路由表结构为:目的网络ip地址子网掩码下一跳ip地址接口1）将IP地址空间202.118.1.0/24划分为2个子网，分别分配给局域网1、局域网2,每个局 域网需分配的IP地址数不少于120个。请给出子网划分结果，说明理由或给出必要的计算过程。2）请给出R1的路由表，使其明确包括到局域网1的路由、局域网2的路由、域
22、名服务器的 主机路由和互联网的路由。3）请采用路由聚合技术，给出R2到局域网1和局域网2的路由。-7-2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一单项选择题：第140小题，每小题2分，共80分。下列每题给出的四个选项中,只有一个选项最符合试题要求。1.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次 进行退栈操作，则不可能得到的出栈序列是 oA.d c e b f a B.c b d a e f C.b c a e f d D.a f e d c b2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元
23、素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是 oA.b a c d e B.d b a c e C.d b c a e D.e c b a d3.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是。A.B.C.D.4.在图B-1所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存 夕力 的关键字分别是 o(A.13,48 B.24,48C.24,53 D.24,90 CD5.在一棵度为4的树T中，若有20个度为4的结点，10个度为3 图6的结点，1个度为2的结点，10个度为1的结点，则树T的叶结
24、点个数 是 OA.41 B.82 C.113 D.1226.对n(n22)个权值均不相同的字符构造成哈夫曼树。下列关于该哈夫曼树的叙述中，霜送的是 OA.该树一定是一棵完全二叉树-8-B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值7.若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边 数最少是 oA.6 B.15 C.168.对图B-2进行拓扑排序，可以得到不同的拓扑序列的个数是.A.4B.3C.2D.19.已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用折半查找法查找一个
25、L中不存在的元素，则关键字的比较次数最多的是 oA.4 B.5 C.6 D.710.采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区的处理顺序无关11.对一组数据(2,12,16,88,5,第一趟排序结果：2,12,16,5,第二趟排序结果：2,12,5,10,第三趟排序结果：2,5,10,12,则采用的排序方法可能是_oA.冒泡排序 B.希尔排序10)进行排序，若前三趟排序结果如下：10,8816,8816,
26、88C.归并排序 D.基数排序12.下列选项中，能缩短程序执行时间的措施是.I.提高CPU时钟频率III.对程序进行编译优化a.仅I和n b.仅I和inn.优化数据通路结构c.仅 n 和in d.I、n和in13.假定有4个整数用8位补码分别表示rl=FEH,r2=F2H,r3=90H,r4=F8H,若将运算结 果存放在一个8位寄存器中，则下列运算中会发生溢出的是。A.rl Xr2 B.r2Xr3 C.rl Xr4 D.r2Xr414.假定变量i、f和d的数据类型分别为int、fl oa t和d oub l e(int用补码表示，fl oa t和d oub l e 分别用IEEE754单精度和
27、双精度浮点数格式表示)，已知i=785,f=1.5678e3,d=1.5el 00o若在32 位机器中执行下列关系表达式，则结果为“真”的是 oI.i=(int)(fl oa t)i II.f=(fl oa t)(int)fIII.f=(fl oa t)(d oub l e)f IV.(d+f)-d=fa.仅i和n b.仅i和in c.仅n和in d.仅m和w15.假定用若干个2K义4位的芯片组成一个8KX8位的存储器，则地址0B1FH所在芯片的 最小地址是 o-9-A.OOOOH B.0600H C.0700H D.O8OOH16.下列有关RAM和ROM的叙述中，正确的是 oI.RAM是易失
28、性存储器，ROM是非易失性存储器II.RAM和ROM都采用随机存取方式进行信息访问III.RAM和ROM都可用作Ca c heW.RAM和ROM都需要进行刷新a.仅I和n b.仅n和mc.仅 I、n 和w d.仅 n、in和w17.下列命中组合情况中，一次访存过程中不可能发生的是 oA.TLB未命中，Ca c he未命中，Pa ge未命中B.TLB未命中，Ca c he命中，Pa ge命中C.TLB命中，Ca c he未命中，Pa ge命中D.TLB命中，Ca c he命中，Pa ge未命中18.下列寄存器中，汇编语言程序员可见的是。A.存储器地址寄存器（MAR）B,程序计数器（PC）C.存储
29、器数据寄存器（MDR）D,指令寄存器（IR）19.下列选项中，不会引起指令流水线阻塞的是。A.数据旁路（转发）B.数据相关C.条件转移 D.资源冲突20.下列选项中的英文缩写均为总线标准的是。A.PCI、CRT、USB、EISA B.ISA、CPI、VESA、EISAC.ISA、SCSL RAM、MIPSD.ISA、EISA、PCL PCI-Express21.单级中断系统中，中断服务程序内的执行顺序是.1.保护现场II.开中断V.中断事件处理VI.恢复现场A.I-V-YI-n-VIIc.iii-iv-v-*vi-viiIII.关中断 W.保存断点v n.中断返回b.in-I-V-v nd.i
30、v-i v-v if vn22.假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600X1200,颜色深度为24位，帧频为85Hz,显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约 为 oA.245Mb it/sB.979Mb it/sC.1 958Mb it/s D.7 834Mb it/s23.下列选项中，操作系统提供给应用程序的接口是 oA.系统调用 B.中断 C.库函数 D,原语24.下列选项中，导致创建新进程的操作是 oI.用户登录成功II.设备分配 III.启动程序执行A.仅 I 和 II B.仅II和HI C.仅 I 和HI D.1、I和HI25.设与某
31、资源关联的信号量初值为3,当前值为1。若M表示该资源的可用个数，N表示 等待该资源的进程数，则M、N分别是 oA.0、1 B.1、0 C.1、2 D.2、026.下列选项中，降低进程优先级的合理时机是。-10-A.进程的时间片用完 B.进程刚完成I/O,进入就绪列队C.进程长期处于就绪列队中 D,进程从就绪状态转为运行状态27.进程P0和P1的共享变量定义及其初值为：b ool ea n fl a g2；int turn=0；fl a g|O=FALSE；fl a g 1=FALSE；若进程PO和Pl访问临界资源的类C伪代码实现如下：v oid PO()/进程 PO(w hil e(TRUE)
32、(fl a gO=TRUE;turn=l;w hil e(fl a g1&(turn=l);临界区；fl a gO=FALSE;v oid Pl()/进程 Pl(w hil e(TRUE)(fl a gl=TRUE;turn=0;w hil e(fl a g0&(turn=0);临界区；fl a gl J=FALSE;则并发执行进程PO和Pl时产生的情形是 OA.不能保证进程互斥进入临界区，会出现“饥饿”现象B.不能保证进程互斥进入临界区，不会出现“饥饿”现象C.能保证进程互斥进入临界区，会出现“饥饿”现象D.能保证进程互斥进入临界区，不会出现“饥饿”现象28.某基于动态分区存储管理的计算机，
33、其主存容量为55MB(初始为空闲)，采用最佳适配(Best Fit)算法，分配和释放的顺序为：分配15MB,分配30MB,释放15MB,分配8MB,分配 6MB,此时主存中最大空闲分区的大小是。A.7MB B.9MB C.10MB D.15MB29.某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为21B,页表项大小 为2B,逻辑地址结构为：页目录号页号页内偏移量逻辑地址空间大小为于页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少 是 OA.64 B.128 C.256 D.51230.设文件索引结点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级 间接地址索引
34、，1个地址项是二级间接地址索引，每个地址项大小为4B。若磁盘索引块和磁盘数 据块大小均为256B,则可表示的单个文件最大长度是 oA.33KB B.519KB C.1 057KB D.16 513KB31.设置当前工作目录的主要目的是 oA.节省外存空间 B.节省内存空间C.加快文件的检索速度 D.加快文件的读/写速度32.本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是 oA.命令解释程序 B.中断处理程序-11-C.系统调用服务程序D.用户登录程序33.下列选项中，不属于网络体系结构所描述的内容是，A.网络的层次C.协议的内部实现细节B.每层使用的协议D.每层必须完成的功能34.在
35、图B-3所示的采用“存储一转发”方式的分组交 换网络中，所有链路的数据传输速率为100Mb it/s,分组大小 为1000B,其中分组头大小为20B。若主机H1向主机H2发 送一个大小为980 000B的文件，则在不考虑分组拆装时间和 传播延迟的情况下，从H1发送开始到H2接收完为止，需要 的时间季少是。图B-3A.80msB.80.08msC.80.16msD.80.24ms35.某自治系统内采用RIP协议，若该自治系统内的路由器RI收到其邻居路由器R2的距离 矢量，距离矢量中包含信息,则能得出的结论是 oA.R2可以经过R1到达netl,跳数为17B.R2可以到达netl,跳数为16C.R
36、1可以经过R2到达netl,跳数为17D.R1不能经过R2到达netl36.若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP 报文类型是 OA.路由重定向 B.目的不可达 C.源点抑制 D,超时37.某网络的IP地址空间为192.168.5.0/24,采用定长子网划分，子网掩码为255.255.255.248,则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是 oA.32,8 B.32,6 C.8,32 D.8,3038.下列网络设备中，能够抑制广播风暴的是 oI.中继器 II.集线器 III.网桥 IV.路由器a.仅I和H b.仅in c.仅in和
37、w d.仅w39.主机甲和主机乙之间已建立了一个TCP连接，TCP最大段长度为1 000B。若主机甲的 当前拥塞窗口为4000B,在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的第一 个段的确认段，确认段中通告的接收窗口大小为2 000B,则此时主机甲还可以向主机乙发送的 最大字节数是。A.1 000 B.2 000 C.3 000 D.4 00040.如果本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为。A.一条、一条 B.一条、多条 C.多条、一条 D.多条、多条二、综合应用题：第4147题，共70分。41.（10分
38、）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存 储空间是一个下标从0开始的一维数组，散列函数为H（key）=（keyX3）mod 7,处理冲突采用线性 探测再散列法，要求装填（载）因子为0.7。1）请画出所构造的散列表。2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。42.（13分）设将（1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都-12-尽可能高效的算法。将R中保存的序列循环左移p（Op）个位置，即将R中的数据由（X。,X1,一Xn_）变换为（Xp,xp+1,.,xn_1,x0,x1,.,xw）o 要求:1）给出算法的基本设计思
39、想。2）根据设计思想，采用C、C+或Ja v a语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度和空间复杂度。43.（11分）某计算机字长为16位，主存地址空间大小为128KB,按字编址。采用单字长指 令格式，指令各字段定义如图B-4所示。15 12 11 6 5 0源操作数 目的操作数图B-4OPMsRsMdRd转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义见表B-1。表B-1Ms/Md寻址方式助记符含义000B寄存器直接Rn操作数=（Rn）001B寄存器间接(Rn)操作数=（Rn）01 O B寄存器间接、自增(Rn)+操作数=(Rn),(Rn)+1-Rn011
40、B相对D(Rn)转移目标地址=（PC）+（Rn）注：（X）表示存储器地址X或寄存器X的内容。请回答下列问题：1）该指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存 器（MAR）和存储器数据寄存器（MDR）至少各需要多少位？2）转移指令的目标地址范围是多少？3）若操作码0010B表示加法操作（助记符为a d d）,寄存器R4和R5的编号分别为100B和 101B,R4的内容为1234H,R5的内容为5678H,地址1234H中的内容为5678H,地址5678H中 的内容为1234H,则汇编语言为“a d d（R4）,（R5）+”（逗号前为源操作数，逗号后为目的操作数）对
41、应的机器码是什么（用十六进制表示）？该指令执行后，哪些寄存器和存储单元中的内容 会改变？改变后的内容是什么？44.（12分）某计算机的主存地址空间大小为256MB,按字节编址。指令Ca c he和数据Ca c he 分离,均有8个Ca c he行，每个Ca c he行大小为64B,数据Ca c he采用直接映射方式。现有两个 功能相同的程序A和B,其伪代码如下：程序A:int a 256256int sum_a rra yl()(int i,j,sum=0;for(i=0;i256;i+)for(j=0;j 256;j+)sum+=a ij;return sum;程序B:int a 25625
42、6int sum_a rra y2()int i,j,sum=0;for(j=0;j 256;j+)for(i=0;i256;i+)sum+=a ij j J;return sum;-13-假定int类型数据用32位补码表示，程序编译时i、j、sum均分配在寄存器中，数组a按行 优先方式存放，其首地址为320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。1）若不考虑用于Ca c he一致性维护和替换算法的控制位，则数据Ca c he的总容量为多少？2）数组元素a 031和各自所在的主存块对应的Ca c he行号分别是多少（Ca c he行号 从0开始）？3）程序A和B的数据访问命中
43、率各是多少？哪个程序的执行时间更短？45.（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间 记录 16 384个磁盘块的空闲状态。1）请说明在上述条件下如何进行磁盘块空闲状态的管理。2）设某单面磁盘旋转速度为6000r/min,每个磁道有100个扇区，相邻磁道间的平均移动时间 为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如图B-5所示），磁道号请求队列为50,90,30,120,对请求队列中的每个磁道需读取1个随机分布的扇区，则 读完这4个扇区点共需要多少时间？要求给出计算过程。3）如果将磁盘替换为随机访问的Fl a sh半导体存
44、储器（如U盘、SSD等），是否有比CSCAN 更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。随机分布的某扇区图B-546.（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程 最多需要6页（Pa ge）数据存储空间，页的大小为1KB,操作系统采用固定分配局部置换策略为 此进程分配4个页框（Pa ge Fra me）o在时刻260前的该进程访问情况见表B-2（访问位即使用位）。表B-2页号页框号装入时刻访问位071301142301222001392601当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：1）
45、该逻辑地址对应的页号是多少？2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过 程。3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过 程（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如图B-6所示）。-14-47.（9分）某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10Mb it/s,主 机甲和主机乙之间的距离为2km,信号传播速度为200 000km/s。请回答下列问题，要求说明理 由或写出计算过程。1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测 到冲
46、突时刻止，最短需经过多长时间？最长需经过多长时间（假设主机甲和主机乙发送数据过程 中，其他主机不发送数据）？2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518B）向主机 乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64B的确认帧，主机甲收到 确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网的前导 码）？-15-2011年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。下列每小题给出的四个选项中，只有一项符合题目要求。(请在答题卡上将所选项的字母涂
47、黑o)1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是 ox=2；w hil e(x 1550ps D.2000ps 2000ps32.有两个并发执行的进程Pl和P2,共享初值为1的变量x。P1对x加1,2对乂减1。加1和减1操作的指令序列分别如下所示。/加1操作l oa d Rl,x/取x到寄存器R1中inc R1store x,RI/将R1的内容存入x两个操作完成后，X的值_。A.可能为-1或3C.可能为0、1或233.TCP/IP参考模型的网络层提供的是.A,无连接不可靠的数据报服务C.有连接不可靠的虚电路服务/减1操作 l oa d R2,x d ec R2 store x
48、,R2B,只能为1D.可能为-1、0、1或2B,无连接可靠的数据报服务 D.有连接可靠的虚电路服务34.若某通信链路的数据传输速率为2400b it/s,采用4相位调制，则该链路的波特率是。A.600波特 B.1200波特 C.4800波特 D.9600波特35.数据链路层采用选择重传协议(SR)传输数据，发送方已发送了 03号数据帧，现已 收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是 oA.1 B.2 C.3 D.436.下列选项中，对正确接收到的数据帧进行确认的MAC协议是A.CSMA B.CDMAC.CSMA/CD D.CSMA/CA37.某网络拓扑如下图所示，路由器R
49、1只有到达子网192.168.1.0/24的路由。为使R1可以 将IP分组正确地路由到图中所有的子网，则在R1中需要增加的一条路由(目的网络，子网掩码,下一跳)是 oA.192.168.2.0255.255.255.128192.168.1.1B.192.168.2.0255.255.255.0192.168.1.1C.192.168.2.0255.255.255.128192.168.1.2D.192.168.2.0255.255.255.0192.168.1.238.在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的IP分组的最大主机数是.-19-A.0 B.1
50、 C.2 D.439.主机甲向主机乙发送一个（SYN=1,seq=11220）的TCP段，期望与主机乙建立TCP连 接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP段可能是 oA.（SYN=O,ACK=O,seq=11221,a c k=11221）B.（SYN=1,ACK=1,seq=11220,a c k=11220）C.（SYN=1,ACK=1,seq=11221,a c k=11221）D.（SYN=O,ACK=O,seq=11220,a c k=11220）40.主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了 3个连续的TCP段，分别包含300B、400B