2022计算机考研408真题5.docx

《2022计算机考研408真题5.docx》由会员分享，可在线阅读，更多相关《2022计算机考研408真题5.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2022年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题(第140小题，每小题2分，共80分。下列每题给出的四个选项中，只 有一个选项最符合试题要求)l求整数( N0)阶乘的算法如下，其时间复杂度是int fact(int n) (if (n c揭 D.无法确定总数为A. 10A. 10B. 20C. 32D. 335.对有个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度 是oA.o(，)B.O (e)C.O(+e)D. O ( e)4?若平衡二叉树的高度为6,且所有非叶结点的平衡因子均为1,则该平衡二叉树的结点A.存在，且唯

2、一B.存在，且不唯一C.存在，可能不唯一D.无法确定是否存在若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列6. 如右图所示的有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b, 第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是_O题47-a表编号IP分组的前40字节内容（十六进制）145 00 00 30 01 9b 40 00 80 06 lde8 c0a8 00 08d3 44 47 50Ob d9 13 88 84 6b 41 c5 00 00 00 00 70 02

3、 43 80 5d bO 00 00243 00 00 30 00 00 40 00 31 0616e 83 d3 44 47 50 c0a8 00 0813 88 Ob d9 eO59 9fef 84 6b 41 c6 70 12 16dO 37 el 00 00345 00 0() 28 01 9c40 00 80 06 Idef c0a8 00 08d3 44 47 50Ob d9 13 88 84 6b 41 c6 eO59 9ffU 50 fU 43 80 2b32 00 00445 000038 01 9d40 00 8006 Idde c0a8 00 00d3 44 47 50O

4、b d9 13 88 84 6b 41 c6 eO 59 9ffU 50 18 43 80 e6 55 00 00545 00 00 28 68 11 40 00 31 06 06 7a d3 44 47 50c0a8 00 0813 88 Ob d9 eO599fW 84 6b 41 d6 50 10 16dO 57d2 00 00回答下列问题。1）题47.a表中的IP分组中，哪几个是由H发送的？哪几个完成了 TCP连接建立过程？ 哪几个在通过快速以太网传输时进行了填充？2）根据题47.a表中的IP分组，分析S已经收到的应用层数据字节数是多少？3）若题47.a表中的某个IP分组在S发出时的前

5、40字节如题47.b表所示，则该P如组到 达H 时经过了多少个路由器？题47-b表45 00 00 28 6811 4000 40 06 ec ad d3444750 ca 76 01 06来自S的分组131 88 al 08 eO 59 9ff0 84 6b 41 d6 50 10 16 dO b7d6 00 00注：IP分组头和TCP段头结构分别如题47-a图和题47-b图所示。bitOmininil 11111111111111A1111版本言服务类型总长度标识志片偏移生存时间 rTTT ）协议头部校验和源IP地址目的IP地址162431A. d, e, fB. e, d, fC.7.

6、下列关于最小生成树的叙述中，正确的是L最小生成树的代价唯一II .所有权值最小的边一定会出现在所有的最小生成树中III .使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV .使用普里姆算法和克鲁斯卡尔（KniskaD算法得到的最小生成树总不相同A.仅 IB.仅 nc.仅 I、inD.仅 n、9 .已知一棵3阶B树，如下图所示。删除关键字78得到一棵新B.树，其最右叶结点中10 .在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是.HL快速排序B 仅 I、IIL V D.仅 III、IV

7、、V11 .简单选择排序n .希尔排序IV.堆排序V.二路归并排序A. 仅 I、III IVC.仅 II、III、IV11 .对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可的：同之处是 OA.排序的总趟数B.元素的移动次数c.使用辅助空间的数量D.元素之间的比较尸数12 .假定基准程序A在某计算机上的运行时间为100秒，其中，。秒为CPU时间，其余为 I/O时间。若CPU速度提高50%, I/O速度不变，则运行基准程序A所耗费的时间是A. 55sB 60sC. 65sD. 70s.假定编译器规定int和shon型长度分别为32应和，6位，执行下列C语言语句： unsigned s

8、ho Lt x=65530;unsigned . int.、尸幻得到y的机器数为 。A. 0000 7FFAH气B.C FFFF 7FFAHD. 0000 FFFAH FFFF FFFAH 能表示的最大14 . Boat类型（即IEEE754单舫冽孚点数格式）正整数学。2127_2 J 03D. 八210415 .某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int型和short型 长度分别为32位和16仓，并且数据按边界对齐存储。某C语言程序段如下：structint a: char b; short c;)record;record.a=273;若record变量的首地址为

9、0xC008,则地址0xC008中内容及record.c的地址分别为A. 0x00 OxCOODB. 0x00 OxCOOEC. Oxlk OxCOODD. Oxlk OxCOOE16.下列关于闪存(Flash Memory)的叙述中，错误的是。A.信息可读可写，并且读、写速度一样快B.存储元由MOS管组成，是一种半导体存储器C.掉电后信息不丢失，是一种非易失性存储器D.采用随机访问方式，可替代计算机外部存储器17.假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。 若Cache的内容初始为空采用2路组相联映射方式和LRU替换策略。访问的主存地址依次为0,A.

10、 1B.2C.3D.44, 8,2Q 6, 8,6,4, 8 时、命中 Cache 的次数是。18.1. 计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码 法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段 至少有。A.5 位B.6 位C.15 位D.33 位19.某同步总线的时钟频率为100MHz,宽度为32位地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发)传输方式， 则一次主存写”总统读 务传输128位数据所需要的时间至少是_。A. 20nsB. 40nsC. 50nsD. 80ns20.下列关

11、于USB总线特性的描述中，错误的 oA.可实现外设的即插即用和热拔插B. 可通过级联方式连接多台外设宙畲C.是一种通信总线，连接不同外设D.同时可传输2位数据，数据传输率高一21 .下列选项中，在I/O总线的数据线上传输的信息包括 oLI/O接口中的命令字ILI/O接口中的状态字UL中断类型号A.仅 I、IIB.仅 I、IIIC.但】山 D.I、II、III22 .响应外部中断的过程中，中断隐指令完成的噪仲，除保护断点外，还包括 oL关中断II.保存通用寄存器的内容口.形成中断服务程序入口地址并送PCA.仅 I、IIB.仅 I、mC.仅 II、IIID. I、II、III23 .下列选项中，不

12、可能在用户态发生的事件是。A.系统调用B.外部改友C.进程切换D.缺页24 .中断处理和子程序调用都F要压栈以保护现场，中断处理一定会保存而子程序调用不 需要保存其内容的是。A.程序计数器B.程序状态字寄存器C,通用数据寄存器D.通用地址寄存器25 .下列关于虚存储器的叙述中，正确的是 oA.虚拟存储只无基于连续分配技术26 虚拟存虻能基于非连续分配技术C.广诚石储容量只受外存容量的限制D.虚拟存储容量只受内存容量的限制26.操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是用户级I/O软件、 用户级I/O软件、 用户级I/O软件、 用户级1

13、/0软件、用户级I/O软件、 用户级I/O软件、 用户级I/O软件、 用户级1/0软件、A.B.C.D.27.设备无关软件、设备驱动程序、中断处理程序 设备无关软件、中断处理程序、设备驱动程序 设备驱动程序、设备无关软件、中断处理程序 中断处理程序、设备无关软件、设备驱动程序假设5个进程Po、Pi、P2、P3、P4共享三类资源Ri、R2、R3这些资源总数分别为18进程已分配资源资源最大需求RiR2R3RiR2R3Po3235510Pl403536P24054011P3204425P43144246、220To时刻的资源分配情况如下表所示，此时存在的一个安全序列是A. Po, P 2, P% P

14、l, P 3C. P2, Pl, Po, P3, P4B. Pl, Po, P 3, P4, P 2D. P3, P4, P 2, Pi, P 028.若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是I.若该文件的数据不在内存中，则该进程进入睡眠等待状态II.请求read系统调用会导致CPU从用户态切换到核心态IIL read系统调用的参数应包含文件的名称A.仅 I、IIB.仅 I、IIIC.仅 C仅 II、Ilin, in d. K II 和 III29. 一个多道批处理系统中仅有Pi和P2两个作业，P2比Pi晚5ms到达，它们的计算和I/O操作

15、顺序如下：Pi：计算 60ms,I/O 80ms,计算 20msP2：计算 120ms, I/O 40ms,计算 40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是 OA. 240msB. 260msC. 340msD. 360ms30 .若某单处理器多进程系统中有多个就绪态进程则下列关于处理机调度的叙述中，错误 的是。A.在进程结束时能进行处理机调度B.创建新进程后能进行处理机调度C.在进程处于临界区时不能进行处理机调度D.在系统调用完成并返回用户态时能进行处理机调度31 .下列关于进程和线程的叙述中，正确的是 oA.不管系统是否支持线程，进程都是资源分配的基本单位B.线程是资源

16、分配的基本单位，进程是调度的基本单位C.系统级线程和用户级线程的切换都需要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间32 .下列选项中，不能改善磁盘设备I/O性能的是 OA.重排I/O请求次序B.在一个磁盘上设置多个分区C .预读和滞后写D.优化文件物理块的分布33 .在TCP/IP体系结构中，直接为ICMP提供服务的协议是 oA. PPPB. IPC. UDPD. TCP34 .在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是A.机械特性B.功能特性C.过程特性D.电气特性35 .以太网的MAC协议提供的是 oA.无连接不可靠服务B.无连接可靠服务C .有连接不可靠服

17、务D .有连接可靠服务36 .两台主机之间的数据链路层采用后退N帧协议（GBN）传输数据，数据传输速率为 16kbps,单向传播时延为270ms，数据帧长度范围是128s512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的应博效至少为oa =d rC.3正确的D.2A.5B.4是_37 .下列关于IP路由器功能的描述中，一L运行路由协议，设置路由表n.监测到拥塞时，合理丢弃ip分组确保传输的ip分组不丢失 心翻稗脚!隋岫1 彳磷料跳 将其转发到合适的输出线路上A.仅 III、IVC.仅 I、II、IV38 . ARP协议的功能是 oA.根据IP地址查询MAC地址C

18、.根据域名查询IP地址39 .某主机的IP地址为180.8077.55,A.仅 III、IVC.仅 I、II、IV40 . ARP协议的功能是 oA.根据IP地址查询MAC地址C.根据域名查询IP地址41 .某主机的IP地址为180.8077.55,B.仅 I、 II、 IIID I、H、III、IVB.根据MAC地址查询IP地址D.根据IP地址查询域名子网掩码为255,255,252,0。若该主机向其所在子网发送广播分组，则目的地址可以是。B180.80.76.255c.i80.80、 7 齐 5 40 .若用户1与用户2之间发送和接收电子邮件的过袒如下图所示，则图中。 阶段 分别使用的应用

19、层协议可以是。用户1的邮 用户2的邮用户1件服务器件服务器用户2B.POP3、SMTP、POP3D.SMTP、SMTP、POP3ASMTP、SMTP、SMTPC.POP3、SMTP、SMTP二、综合应用题（第41 -项题，共70分）41 .设有6个有序表/、B、C、D、E、F,分别含有10、35、40、50、60和200个数据元 素，各表中元素接，辱排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在 最坏情况下比壮凶总次数达到最小。请回答下列问题。1）给凸二整的合并过程，并求出最坏情况下比较的总次数。2）根据”合并过程，描述N 6VN2）个不等长升序表的合并策略，并说明理由42.假

20、定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。stn设Strl和Str2分别指向两个单词所在单链表的头结点，链表结点结构为3避t请设计一 个时间上尽可能高效的算法，找出由*1和str2所指向两个链表共同后缀的起始位置（如图中字 符i所在结点的位置P）。要求：1）给出算法的基本设计思想。2）根据设计思想，采用C或C+或Java语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度。43.假定某计算机的CPU主频为80MHz,CPI为4,平均每条指令访存1.5次,主存与Cache之 间交

21、换的块大小为16B, Cache的命中率为99%,存储器总线宽度为32位。请回答下列问题。1）该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送 的情况下，主存带宽至少达到多少才能满足CPU的访存要求？2）假定在Cache缺失的情况下访问主存时，存在0.0005%的缺页率则CPU平均每秒尸生 多少次缺页异常？若页面大小为4KB,每次缺页都需要访问磁盘，访问磁盘时DMA*声送采用周 期挪用方式，磁盘.1/0接口的数据缓冲寄存器为32位，则磁盘I/O接口平均每秒发出的DMA请 求次数至少是多少？3） CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高？为什

22、么？4）为了提高性能主存采用四体低位交叉存储模式工作时每1/4个存话周期启动一个体。 若每个体的存储周期为50ns,则该主存能提供的最大带宽是多少？44 .某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache分离。题44表 给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址，（x）表 示寄存器x或存储单元x的内容。指令系统中部分指1枯式名称指令的汇编格式指令功能加法指令ADD Rs, Rd(Rs) + (Rd)-Rd算术/逻辑左移SHL Rd2*(Rd)-Rd算术右移SHR Rd(Rd)/2-Rd取数指令LOAD Rd,mem(mem)-Rd存数指

23、令STORE Rs, mem(Rs)-mem该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、 执行/计算有效地址（E、）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序 发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不 能在同一个时钟周期A进行。请回答下列问题：1）若in彖笑量x的值为513,存放在寄存器R1中，则执行指令“SHR R1”后，R1伐 内容 是多产？（用十六进制表示）2）右个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生何可阻塞，则 执行这4条指令所需的时钟周期数为多少？更多考研真题

24、资料关注【优路考研】公众号3）若高级语言程序中某赋值语句为x= a + b,x、a和b均为int型变量，它们的存储单 元地址分别表示为x、a和以。该语句对应的指令序列及其在指令流水线中的执行过 图所示。IlLOADRI, a12LOADR2,b13ADDR1,R214STORER2, x时间单元则这4条指令执行过程中，13的ID段和14的IF段被阻塞的原因各是什么？指令 1234567891011121314IlIFIDEXMWB12IFIDEXMWB13IFID EXM WBLiIFID EXM WB4）若高级语言程序中某赋值语句为x = x*2 +a, x和a均为unsignedint类型

25、变量，它们的存储单元地址分别 表示为x、a,则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令 序 列 及 其 在 流 水 线 中 的 执 行 过 程 示 意 图。45 .某请求分页系统的局部页面置换策略如下：系统从。时刻开始扫描，每隔5个时间单位 扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲 页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空 闲页链表中，那么重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框

26、链表中 页框号依次为32、15、21、41o进程P依次访问的v虚拟页号，访问时刻是vl, 1,v3,2,v0,4, VO, 6, o 请回答下列问题。1）访问时，对应的页框号是什么？说明理由。2）访问时，对应的页框号是什么？说明理由。3）访问时，对应的页框号是什么？说明理由。4）该策略是否适合于时间局部性好的程序？说明理由。46 .某文件系统空间的最大容量为4TB （1TB = 2,ob）,以磁盘块为基本分配单位。磁盘块大 小为1陷。文件控制块（FCB）包含一个512B的索引表区。请回答下列问题。1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块 号最少占多少字节？可支持的单个文件最大长度是多少字节？2）假设索引表区采用如下结构：第0-7字节采用v起始块号，块数格式表示文件创建时预 分配的连续存储空间，其中起始块号占6B,块数占2B；剩余504字节采用直接索引结构，一个索 引项占6B,那么可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出 起始块号和块数分别所占字节数的合理值并说明理由。47 .主机H通过快速以太网连接Internet, IP地址为192.168.0.8,服务器S的IP地址为211.68.71.80o H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。