2024-2019全国硕士研究生招生考试计算机学科专业基础试题（408计算机统考）

2019年全国硕士研究生入学统一考计算机科学与技术学科联考计算机学科专业基础综合试一、单项选择题（1～40280分。下列每题给出的四个选项中，设n是描述问题规模的非负整数，下列程序段的时间复杂度 while(n>=(x+1)*(x+1)) 若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后 在任意一棵非空平衡二叉树（AVL树）T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是 vT1的叶结点T1T3可能不相v不是T1的叶结点，则T1T3一定不相v不是T1的叶结点T1T3一定相A．仅 B．仅 C．仅I、 D．仅I、下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始 A．3和7 B．12和12 C．12和14 D．15和156．用有向无环图描述表达式(xy)((xy)/x)，需要的顶点个数至少是 A．仅III B．仅I、IIC．仅II、III、 D．I、II、III、2019年计算机408统考真题第1页，共7现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7（线性探测再散列）法解决冲突。将关键字序列87,40,30,6,11,22,98,20依次插入HT后，HT 设主串T="abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法进行模式匹配，到 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，可能是快速排序第二趟结果的是 。A．5,2,16,12,28,60,32, B．2,16,5,28,12,60,32,C．2,12,16,5,28,32,72, D．5,2,12,28,16,32,72,设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚 unsignedshortusi=65535;shortsi=usi;13．考虑unsignedshortusi=65535;shortsi=usi;执行上述程序段后，si的值 A．- B．- C．- D．- A．缺页是在地址转换时CPU检测到的一种异常某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234FF00H，该操作数采用基址寻址方式，形式地址（用补码表示）为FF12H，基址寄存器的内容为F0000000H，则该操作数的LSB（最低有效字节）所在的地址是 A．F000 B．F000 C．EFFF D．EFFF D．处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指某指令功能为R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采用寄存器、寄存器间 I．通用寄存器组 II．算术逻辑单元2019年计算机408统考真题第2页，共7III．存储器 IV．指令译码器A．仅I、II B．仅I、II、III C．仅II、III、IV D．仅I、III、IV18．在采用“取指、译码/取数、执行、访存、写回”5段流水线的处理器中，执行如下令序列s0、s1、s2、s3t2表示寄存器编号I1I1：addI2：loads3,0(t2)I3：adds2,s2,s3I4：stores2,0(t2)下列指令对中，不存在数据冒险的 A．I1和 B．I2和 C．I2和 D．I3和19假定一台计算机采用3通道存储器总线配套的内存条型号为DD3-133即内存条所接插的存储器总线的工作频率为133MHz，总线宽度为64位，则存储器总线的总带宽大约是 。 C．磁盘存储器的最小读写单位为一字D．磁盘存储器由磁盘控制器、磁盘驱动器和盘片组某设备以中断方式与CPU进行数据交换，CPU主频为1GHz，设备接口中的数据缓冲1000个时钟周期则CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多 下列关于DMA方式的叙述中，正确的 DMA传送前由设备驱动程序设置传送参数据传送前由DMA控制器请求总线使用数据传送由DMA控制器直接控制总线完DMA传送结束后的处理由中断服务程序完A．仅I、 B．仅I、III、C．仅II、III、IV 内核级线程的调度由操作系统完 I．I/O结 II．某进程退出临界 III．当前进程的时间片用A．仅I B．仅III C．仅I、II 在执行系统调用服务程序的过程中，CPU处于内核操作系统通过提供系统调用避免用户程序直接访问外A．仅I、 B．仅II、 C．仅I、II、 D．仅I、III、26.下列选项中，可用于文件系统管理空闲磁盘块的数据结构 位 II．索引结 III．空闲磁盘块 IV．文件分配表A．仅I、II B．仅I、III、IV C．仅I、III D．仅II、III、IV27．系统采用二级反馈队列调度算法进行进程调度就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2。若当前Q1、Q2为空，系统依次创建进程P1、P2后即开始进程调度，P1P2需要的CPU时间分别为30ms和20ms，则进程P1P2在系统中的平均等待时间 在分段存储管理系统中，用共享段表描述所有被共享的段。若进程P1和2共享段，下列叙述中，错误的是 。A．在物理内存中仅保存一份段S的内容B．段SP1P2中应该具有相同的段号C．P1P2共享段S在共享段表中的段表项D．P1P2都不再使S时才回收段S所占的内存空某系统釆用LRU页置换算法和局部置换策略，若系统为进程P预分配了4个页框，进程P访问页号的序列为0,1,2,7,0,5,3,5,0,2,7,6，则进程访问上述页的过程中，产生页置 I．可以通过剥夺进程资源解除IV．当系统出现死锁时，必然有两个或两个以上的进程处于阻塞A．仅II、III B．仅I、II、IV C．仅I、II、III 页目录号（10位页内偏移（12位虚拟地址20501225H对应的页目录号、页号分别 A．081H、 B．081H、 C．201H、 D．201H、 33．OSI参考模型的第5层（自下而上）完成的主要功能是 34．100BaseT快速以太网使用的导向传输介质是 双绞 B．单模光 C．多模光 D．同轴电对于滑动窗口协议，若分组序号采用3比特编号，发送窗口大小为5，则接收窗口最 假设一个采用CSMA/CD协议的10Mb/s局域网，最小帧长是128B，则在一个冲突域 若将/20划分为5个子网则可能的最小子网的可分配IP地址数 某客户通过一个TCP连接向服务器发送数据的部分过程如题38图所示。客户在t0时刻第一次收到确认序列号ack_seq=100的段，并发送序列号seq=100的段，但发生丢失。若TCP支持快速重传，则客户重新发送seq=100段的时刻是 38若主机甲主动发起一个与主机乙的TCP连接，甲、乙选择的初始序列号分别为和2046，则第三次握手TCP段的确认序列号 A．在P2P模型中，结点之间具有对等关系C．在C/S模型中，主动发起通信的是客户，被动通信的是服务器D．在向多用户分发一个文件时，P2P模型通常比C/S模型所需的时间二、综合应用题（第41～47小题，共70分41（13分）设线性表L(a1a2a3,an2an1an)采用带头结点的单链表保存，链表中的 typedefstruct intstruct}请设计一个空间复杂度为O(1LL(1,an,a2,an1,a3,an2,)。要求：给出算法的基本设计思想根据设计思想，采用C或C++语言描述算法，关键之处给出注释说明你所设计的算法的时间复杂度42（10分）请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列④入队操作和出队操作的时间复杂度始终保持为O(1)。请回答下列问该队列是应选择链式存储结构，还是应选择顺序存储结画出队列的初始状态，并给出判断队空和队满的条件画出第一个元素入队后的队列状态给出入队操作和出队操作的基本过43（8分）有（≥）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有m≥1侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学PV［a()、na()操作描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。44（7分）某计算机系统中的磁盘有300个柱面，每个柱面有10个磁道，每个磁道有个扇区，扇区大小为512B。文件系统的每个簇包含2个扇区。请回答下列问磁盘的容量是多少假设磁85号柱面上，此时有4个磁盘访问请求，簇号分别为100260、60005第100530簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由系统的什么程序完成的45（16序（阴影部分）及其在32位计算机M上的部分机器级代码如t tt t{ 1push……… 837D08 cmpdwordptr 7E jlef1+35h returnn*f1(n-1); 8B4508 moveax,dwordptr[ebp+8] 83E801 subeax,1 pusheax E8D6FFFFFFcallf1(00401000) 0FAFC1 imuleax,ecx EB05 jmpf1+3Ah(0040103a) elsereturn1; B801000000moveax,1 ………cmpebp,………其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算M按字节编址，int型数据占32位。请回答下列问题：计算f(10)需要调用函数f1多少次？执行哪条指令会递归调用上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行16行的call17行指令的虚拟地址应是多少？已知第16call指令采用相对寻址方式，该指令中的偏移量应是多少（给出计算过程）？已知第16行的call指令4字节为偏移量，M是采用大端方式还是采用小端方式？（4）f(13)=6227020800，但f1(13)的返回值为1932053504，为什么两者不相等？要使f1(13)能返回正确的结果，应如何修改f1的源程序？（5）第19行的imul指令（带符号整数乘）的功能是R[eax]←R[eax]×R[ecx]，当乘法器输出的高、低32位乘积之间满足什么条件时，溢出标志OF=1？要使CPU在发生溢出时转异常处理，编译器应在imul指令后应加一条什么指令？46（7分）45，若计算机M的主存地址为32位，釆用分页存储管理方式，页大小为4KB，则第1行的push指令和第30行的ret指令是否在同一页（说明理由）？若指令Cache有64行，采用4路组相联映射方式，主存块大小为64B，则32位主存地址中，哪几位表示块内地址？哪几位表示Cache组号？哪几位表示标记（tag）信息？读取第16行的call指令时，只可能在Cache的哪一组中命中（说明理由）？47（9分）某网络拓扑如题47图所示，其中R为路由器，主机H1～H4IP地址配置以及R的各接口IP地址配置如图中所示。现有若干以太网交换机（无VLAN功能）和路由器两47请回答下列问题（1）123分别应选择什么类型的网络设备IP地址。（3）为确保主机H1～H4能够访问Internet，R需要提供什么服2021年计算机408统考真题第1页，共92021年计算机408统考真题第2页，共92021年计算机408统考真题第3页，共92021年计算机408统考真题第4页，共92021年计算机408统考真题第5页，共92021年计算机408统考真题第6页，共92021年计算机408统考真题第7页，共92021年计算机408统考真题第8页，共9C87t)�itjHJLJ=IHJ!!ffi:ft7':1Ja$Jffi:,�iffi:ffi-1-wi±�-i23R,�r�fc7tIRlLfittffi:5I�J=llf-��JgI��JJ�1-?tIR,r-rt�ft*#E,7tIR�tRT���ft-�,o�JI!ffi:ilii:Jttf?t1R,4:l-?tIRITTffi1-wiIR�fiff,ffl5IRITTt1�dt*#Eo*#E*ffl$�fr�51�:Ji:it,��fifffD?tlR5l�f¥ff5'�.fROM"5f¥ffo*#EJa$JMfii:p*JtJJ:tzi:lf-Uiff,7tIR5Ifif,ROMi:pITT5Ififf,1ittffi:5fT�•:m:*ff?t!R,tAff�41-ttftITT�m�ff¾tti-1ittffi:wilRITT�?tffiX#*#Effl§3RITTR�?t�¾ftffi2)�ITTU1-ttfti:r�JVGITT?C97t)���1,E1+:t,io�47OOJ=ifr�,Ll::t:�3'.t:�:rJLsiffiM�4Hl3ffR1=jInternet�iEl3ffiff�7tt:1HJ,:$:i-&�45�*HLH2ITTIP±-&±JI::;¥□MAC±-&±Jl:::f,io00i:pJ=ifroftto�lH1Webn�*ff,ftt1�tCt1>to)sffi-<J-JTHTTPiw:JH�XITTLl::t:�$9!,tofljt11Al'sJ��*it:i{ffiiJ1=j.11:UJ-'.WebijjloJ��it{::El -·"·•�- 192.168.1126/25

00-11-22-33-44-Mt0ljt1WHsJ,H1�THTTPz.j�iiE1TTriJJ�1-mfflrzfiYJ,i5l?:B'SMA±-&±JI::,i4Tu□>,Jl!ljt1�tS3t�*ITTr;J�¾{ti-$!J!ITT§ITTMAC±-&±Jl:¾{2021年计算机408统考真题第9页，共9

•0092023全国硕士研究生1/2/3/4/5/6/7/8/9/10/11/12/2024考研408计算机统考真题与数据结D.+x*y/-D.p有右孩子，q有左孩B、D、11.外部排序使用败者树进行升序归并，记录“冠军”节点保存的是（）【答案】D.计算机组成原12、Cinti=32777；shortsi=i；intj=si；执行上述代码段后，jIV.汇编指A.仅I和 C.仅III和 D.仅I、III和D.单精度浮点数，双精度浮点用ALU和位移器实现的乘运算无法在一个时钟周期内完略D.Cache-主存层次可采用直接映射方式，主存-主存地址为30位，页大小为1KB。若TLB共有32个表项，采用4路组相联映射方 A.访问越权B.Cache缺失C.页面缺失D.TLB缺失19.5段流水线RISC说法错误的是（）存储器总线的时钟频率为420MHz，总线宽度为64位，每个时钟周期传送2次数据，支持突发传输，最多传8次，第一个时钟传地址和读写命令，从第4~7个始终连续传8次。总线带宽最大传输速率为（）。 关于中断1/O方式，错误的是（）DMA方式中，DMA控制器控制的数据传输通路位于（）操作系下面关于中断和异常的说法中，错误的是（）终止进程时，不一定执行的是（）支持页式存储管理的系统，进程切换时OS要执行（）I.更新PC值Ⅱ.更新栈基址高存器值（ebp）Ⅲ.回收分区时，仅合并大小相等的空闲分区的算法是（）AB.C.DI.进程P的地址空间RR调度，时间片为5ms，有10个进程，初始状态均处于就绪队列，执行结束前仅处于执行态或就绪态，队尾进程P所需CPU时间最短，为25ms，不考虑系统开销，则P的周转时间为（）。D.键盘控制器的数据缓冲A. B. C.788D.计算机网络33若分组交换网络及每段链路的带宽如下图，则H1到H2的最大吞吐量约A、 B. C、 D, 38.TCP连接和断开，时间是（）【答案】D41G IntnumberVertices,numEgges;//图的顶点数和有向边数CharVerticesList[maxV];//顶点表,MAXV为