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

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

1、2022年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题(第140小题，每小题2分，共80分。下列每题给出的四个选项中, 只有一个选项最符合试题要求)I.设是描述问题规模的非负整数，下列程序段的时间复杂度是x=0;while (n=(x+1)*(x+1) x=x+l;A . O(logH)B . 0(叼2 .若将一棵树T转化为对应的二叉树BT, 根遍历序列相同的是。A.先序遍历B.中序遍历3 .对个互不相同的符号进行哈夫曼编码。 是C . 0(/i)D . O(n2)则下列对BT的遍历中，其遍历序列与T的后C.后序遍历D.按层遍历若生成的哈夫曼树共有

2、115个结点，则的值4 .在任意一棵非空平衡二叉树(AVL树)中，删除某结点v之后形成平衡二叉树T2, 再将v插入T2形成平衡二叉树T3o下列关于与T3的叙述中，正确的是 oI .若v是的叶结点，则与13可能不相同II .若V不是T1的叶结点，则T与T3一定不相同III .若v不是的叶结点，则与T3一定相同A.仅 IB.仅 IIC.仅 I、IID.仅 I、III5 .下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始 时间分别是。A. 3和 7B. 12 和 12C. 12 和 14D . 15 和 156 .用有向无环图描述表达式(x + y)(x + y) /x)

3、,需要的顶点个数至少是。7 .选择一个排序算法时，除算法的时空效率，I.数据的规模 II.数据的存储方式 III.A.仅 III下列因素中，还需要考虑的是算法的稳定性8 .仅 I、HIV.数据的初始状态C.仅【I、III、IVD. I 、 n 、 IH 、 IV8 .现有长度为II且初始为空的散列表HT,散列函数是（key） = key % 7,采用线性探查 （线性探测再散列）法解决冲突。将关键字序列87,40, 30,6, 11, 22, 98, 20依次插入HT后，HT 查找失败的平均查找长度是 oA . 4B . 5.25C . 6D . 6.299 .设主串T = abaabaabca

4、baabc,模式串S = abaabc,采用KMP算法进行模式匹配,到 匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是。A. 9B . 10C. 12D . 1510 .排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一 “趟”。下列序列 中，不可能是快速排序第二趟结果的是 oA . 5,2, 16, 12, 28, 60, 32, 72B . 2, 16, 5, 28, 12, 60, 32, 72C . 2, 12, 16, 5, 28, 32, 72, 60D . 5, 2, 12, 28, 16, 32, 72, 6011 .设外存上有120个初始归并段，进行12路归

5、并时，为实现最佳归并，需要补充的虚段 个数是 OA. 1B. 2C. 3D. 412 .下列关于冯诺依曼结构计算机基本思想的叙述中，错误的是 oA.程序的功能都通过中央处理器执行指令实现B.指令和数据都用二进制数表示，形式上无差别C.指令按地址访问，数据都在指令中直接给出D.程序执行前，指令和数据需预先存放在存储器中.考虑以下C语言代码： unsigned short usi = 65535; short si = usi;执行上述程序段后，Si的值是。A. -1B . -32767C . -32768D . -6553513 .下列关于缺页处理的叙述中，错误的是 oA.缺页是在地址转换时CP

6、U检测到的一种异常B.缺页处理由操作系统提供的缺页处理程序来完成C.缺页处理程序根据页故障地址从外存读入所缺失的页D.缺页处理完成后回到发生缺页的指令的下一条指令执行14 .某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234 FF00H,该操 作数采用基址寻址方式，形式地址（用补码表示）为FF12H,基址寄存器的内容为F000 0000H, 则该操作数的LSB （最低有效字节）所在的地址是。A . F000 FFI2H B . F000 FF15H C . EFFF FF12H D . EFFF FF15H15 .下列有关处理器时钟脉冲信号的叙述中，错误的是 0A.时钟脉冲信号

7、由机器脉冲源发出的脉冲信号经整形和分频后形成B.时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C.时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D.处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令16 .某指令功能为R-Rrl + MRrO,其两个源操作数分别采用寄存器、寄存器间接 寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是 0I.通用寄存器组（GPRs）II.算术逻辑单元（ALU）2III.存储器（Memory）IV.指令译码器（ID）A.仅 I、IIB.仅 I、H、III C.仅 II、III . IV D.仅 I、HI、IV18 .在采用

8、“取指、译码/取数、执行、访存、写回” 5段流水线的处理器中，执行如下指令序列，其中s（）、si、s2、s3和t2表示寄存器编号。II： add s2, si,sO 12： load s3z 0 (t2) 13： add s2,s2,s3 14： store s2,0(t2)/Rs2 Rsl+RsO /Rs3MRt2+0 /Rs2 R(s2+Rs3 /MRt2+0 Rs2下列指令对中，不存在数据冒险的是 oA . 11 和 13B . 12 和 13C . 12 和 14D . 13 和 1419 .假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3- 1333,即内存条 所接插的

9、存储器总线的工作频率为1333MHz，总线宽度为64位，则存储器总线的总带宽大约 是 OA . I0.66GB/SA . I0.66GB/SB . 32GB/SC . 64GB/SD . 96GB/S20 .下列关于磁盘存储器的叙述中，错误的是 oA.磁盘的格式化容量比非格式化容量小21 扇区中包含数据、地址和校验等信息C.磁盘存储器的最小读写单位为一字节D.磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成22 .某设备以中断方式与CPU进行数据交换，CPU主频为1GHz,设备接口中的数据缓冲 寄存器为32位，设备的数据传输率为50kB/so若每次中断开销（包括中断响应和中断处理）为 1000个时

10、钟周期，则CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是。A . 1.25%B . 2.5%C . 5%D . 12.5%23 .下列关于DMA方式的叙述中，正确的是。I . DMA传送前由设备驱动程序设置传送参数II .数据传送前由DMA控制器请求总线使用权III .数据传送由DMA控制器直接控制总线完成IV . DMA传送结束后的处理由中断服务程序完成A.仅 I、IIB.仅 I、III、IVV .仅 n、in、ivd . 1、n、in、iv23.下列关于线程的描述中，错误的是。A.内核级线程的调度由操作系统完成B.操作系统为每个用户级线程建立一个线程控制块C.用户级线程间的

11、切换比内核级线程间的切换效率高D.用户级线程可以在不支持内核级线程的操作系统上实现24 .下列选项中，可能会将进程唤醒的事件是 o1. I/O结束II.某进程退出临界区 III.当前进程的时间片用完A.仅 IB.仅 HIC.仅 I、IID . I、II、III25 .下列关于系统调用的叙述中，正确的是。I .在执行系统调用服务程序的过程中，CPU处于内核态II .操作系统通过提供系统调用避免用户程序直接访问外设3III .不同的操作系统为应用程序提供了统一的系统调用接口IV .系统调用是操作系统内核为应用程序提供服务的接口A.仅 I、IVB.仅 H、IIIC.仅 I、II、IV D.仅 I、H

12、I、IV26.下列选项中，可用于文件系统管理空闲磁盘块的数据结构是。I.位图 H.索引结点 III.空闲磁盘块链 IV.文件分配表（FAT）A.仅 I、IIB.仅 I、III . IV C.仅 I、IIID.仅 II、III . IV27 .系统采用二级反馈队列调度算法进行进程调度。就绪队列Qi采用时间片轮转调度算法， 时间片为10ms；就绪队列Q?采用短进程优先调度算法；系统优先调度Qi队列中的进程，当 Qi为空时系统才会调度Q2中的进程；新创建的进程首先进入Qi; Qi中的进程执行一个时间片 后,若未结束，则转入Qo若当前Qi, Q2为空，系统依次创建进程Pi、P2后即开始进程调度， Ph

13、 P2需要的CPU时间分别为30ms和20ms,则进程Pi、P2在系统中的平均等待时间为。A . 25msB . 20msC . 15msD . 10ms28 .在分段存储管理系统中，用共享段表描述所有被共享的段。若进程Pi和P2共享段S, 下列叙述中，错误的是 oA.在物理内存中仅保存一份段S的内容29 段S在Pi和P2中应该具有相同的段号C . Pi和P2共享段S在共享段表中的段表项D. Pi和P2都不再使用段S时才回收段S所占的内存空间I 9.某系统采用LRU页置换算法和局部置换策略，若系统为进程P预分配了4个页框， 进程P访问页号的序列为0, 1,2, 7, 0,5, 3, 5, 0,

14、2, 7, 6,则进程访问上述页的过程中，产生页置 换的总次数是。A . 3B . 4C . 5D . 6II .下列关于死锁的叙述中，正确的是 oIII 以通过剥夺进程资源解除死锁IV .死锁的预防方法能确保系统不发生死锁V II.银行家算法可以判断系统是否处于死锁状态VI .当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态A.仅 II s IIIB.仅 I、II、IV C.仅 I、II、III D.仅 I、III、IV31 .某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：页目录号（10位）页号（10位）页内偏移（12位）虚拟地址2050 1225H对应的页目录号、页

15、号分别是。A . 081H、101H B . 081H、401HC . 20IH、101H D . 201H、401H32 .在下列动态分区分配算法中，最容易产生内存碎片的是 oA.首次适应算法B.最坏适应算法C.最佳适应算法D.循环首次适应算法33 . OSI参考模型的第5层（自下而上）完成的主要功能是。A.差错控制B.路由选择C.会话管理D.数据表示转换34 . lOOBaseT快速以太网使用的导向传输介质是。A.双绞线B.单模光纤C.多模光纤D.同釉电缆43官5.方滑:wdu机敏朝若分组序号采用3更比多特考编研号真，题注口大【优小路为考研5,】则公窗口曷大是 oA . 2B . 3C .

16、 4D . 536 .假设一个采用CSMA/CD协议的10Mb/s局域网，最小帧长是128B,则在一个冲突域 内两个站点之间的单向传播延时最多是 oA . 2.56psB . 5. 12psC . 10.24psD . 20.48ps37 .若将101.200. 16.0/20划分为5个子网，则可能的最小子网的可分配IP地址数是。A . 126B . 254C . 510D . 102238 .某客户通过一个TCP连接向服务器发送数据的部分过程如题38图所示。客户在用时 刻第一次收到确认序列号ack_seq = 100的段，并发送序列号seq = 100的段，但发生丢失。若 TCP支持快速重传

17、，则客户重新发送seq= 100段的时刻是。A . tB . t2C . /3D . t4题38图39 .若主机甲主动发起一个与主机乙的TCP连接，甲、乙选择的初始序列号分别为2018 和2046,则第三次握手TCP段的确认序列号是。A . 2018B. 2019C . 2046D . 204740 .下列关于网络应用模型的叙述中，错误的是。A.在P2P模型中，结点之间具有对等关系41 在客户/服务器（C/S）模型中，客户与客户之间可以直接通信C.在C/S模型中，主动发起通信的是客户，被动通信的是服务器D .在向多用户分发一个文件时，P2P模型通常比C/S模型所需的时间短二、综合应用题（第4广

18、47小题，共70分）41.（13分）设线性表乙二（41,42,43，-4“一2，。”一1，。）采用带头结点的单链表保存，链表中的 结点定义如下：typedef struct node int data;struct node* next; NODE；请官一方计网一站个:*响.y。氮il杂u.度co为m何)且时间上尽可考效触膜算题法资，【考悯的】各公给众,得到线性表乙=(外, 4，七，4一1，田,凡-2,)。要求：(0给出算法的基本设计思想。(2)根据设计思想，采用C或C+语言描述算法，关键之处给出注释。(3)说明你所设计的算法的时间复杂度。42. (1()分)请设计一个队列，要求满足：初始时队

19、列为空；入队时，允许增加队列 占用空间；出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减； 入队操作和出队操作的时间复杂度始终保持为0(1)。请回答下列问题：(1)该队列是应选择链式存储结构，还是应选择顺序存储结构？(2)画出队列的初始状态，并给出判断队空和队满的条件。(3)画出第一个元素入队后的队列状态。(4)给出入队操作和出队操作的基本过程。43. (8分)有(23)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在 圆桌中心有？个碗，每两位哲学家之间有一-根筷子。每位哲学家必须取到一个碗和两 侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使

20、尽可能多的哲学 家同时就餐，且防止tH现死锁现象，请使用信号量的P、V操作wait。、signal。操作描述上 述过程中的互斥与同步，并说明所用信号量及初值的含义。44. (7分)某计算机系统中的磁盘有300个柱面，每个柱面有10个磁道，每个磁道有2(X) 个扇区，扇区大小为512Bo文件系统的每个簇包含2个扇区。请回答下列问题：(1)磁盘的容量是多少？(2)假设磁头在85号柱面上，此时有4个磁盘访问请求，簇号分别为100 260 . 60 005、 101 660和110 560。若采用最短寻道时间优先(SSTF)调度算法，则系统访问簇的先后次序是 什么？(3)第100 530簇在磁盘上的物

21、理地址是什么？将簇号转换成磁盘物理地址的过程是由I/O 系统的什么程序完成的？45. (16分)已知.*) = ！ =(一1)(一 2) . 2 1 ,计算/()的C语言函数fl的源程 序( 阴影部分)及其在32位计算机M上的部分机器级代码如下：int fl(int n)1 0040100055pushebpif(nl)110040101883 7D08 01cmpdvzord ptr ebp+ 8 , 1120040101C7E 17jlefl+35h (00401035)return n*fl(n-1);130040101E8B 4508moveax, dword ptr ebp+ 8 1

22、40040102183 E801subeax, 1150040102450pusheax1600401025E8 D6FF FF FF callfl ( 00401000)1900401030OF AFClimuleax, ecx2000401033EB 05jmpfl+3Ah (0040103a)else return 1;)2100401035 B8 01 00 00 00 mov eax, 126004010403B ECcmp ebpz esp300040104AC3ret6 其中，旃静物茯蹄胡辖柠号、虚拟地址、机器联辅伊麝塔嬖斗带第狒的髀令蠹品int 型数据占32位。请回答下列问题：

23、(1)计算贝1。)需要调用函数门多少次？执行哪条指令会递归调用fl?(2)上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？(3)根据第16行的call指令，第17行指令的虚拟地址应是多少？已知第16行的call指令 采用相对寻址方式，该指令中的偏移量应是多少(给出计算过程)？已知第16行的call指令的 后4字节为偏移量，M是采用大端方式还是采用小端方式？(4) /(13) = 6227020800,但fl(l3)的返回值为1932053504,为什么两者不相等？要使 门(13)能返回正确的结果，应如何修改fl的源程序？(5)第19行的imul指令(带符号整数乘)的功能是R

24、eax-ReaxxRecxb当乘法器输 出的高、低32位乘枳之间满足什么条件时，溢出标志OF=1?要使CPU在发生溢出时转异常 处理，编译器应在imul指令后应加一条什么指令？46. (7分)对于题45,若计算机M的主存地址为32位，采用分页存储管理方式，页大小 为4KB,则第1行的push指令和第3()行的ret指令是否在同一页中(说明理由)？若指令Cache 有64行，采用4路组相联映射方式，主存块大小为64B,则32位主存地址中，哪几位表示块 内地址？哪几位表示Cache组号？哪几位表示标记(tag)信息？读取第16行的call指令时， 只可能在指令Cache的哪一组中命中(说明理由)？47. (9分)某网络拓扑如题47图所示，其中R为路由器，主机HrH4的IP地址配置以 及R的各接口 IP地址配置如图中所示。现有若干以太网交换机(无VLAN功能)和路由器两 类网络互连设备可供选择。题47图请回答下列问题：(1)设备1、设备2和设备3分别应选择什么类型的网络设备？(2)设备1、设备2和设备3中，哪几个设备的接口需要配置IP地址？为对应的接口配置 正确的IP地址。(3)为确保主机HrH4能够访问Internet , R需要提供什么服务？(4)若主机H3发送一个目的地址为的IP数据报，网络中哪几个主机会接收 该数据报？