2019计算机考研408真题和答案（版本一）.pdf

2019年全同硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综介试题吧项选择题：140小题，每小腿2分，共80分。F列每题输出的四个项巾，只,fj一个选项符介i.i:t题要求。I.设凡是描述问题规模的七负整数，下列程序段的时间组杂度是X=O;while(n=(x+l)*(x+l)X=x+j A.0(log n)B.0(n 112)C.0(n)D.0(n 2)2.若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历巾，其遍历序列与T的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历3.对n个互不相同的符号进行阶犬虽编码。若生成的哈夫曼树共有115个结点，则n的值是A.56B.57C.58D.604.在任意一棵iF？：平衡二叉树（AVL树）Ti中，删除某结点u之后形成平衡二叉树Tz，再将u插入Tz形成平衡二叉树T。下列关于Ti与飞的叙述中，正确的是I.若u是Ti的叶结点，则Ti与T可能不相同II.若u不是Ti的叶结点，则Ti与T3定不相同田若v不是Ti的叶结点，则Ti与T一定相同A.仅IB.仅HC仅I,IID.仅I、田5.下图所示的AOE网表示一项包含8个活动的工程活动d的最早开始时间和最迟开始时间分别是淘宝店铺：光速考研工作室A.3和7B.12和12C.12和14D.15和156.用有向无环图描述表达式（x+y)*(x+y)/x），需要的顶点个数至少是A.5B.6 C.8 D.97.选择一个排序算法时，除算法的时 空效率外，下列队l亲巾，压芮要考虑的是I.数据的规樵皿.n法的稳定性A.仅皿II.数据的在储方式IV.数据的初始状态B.仅I、HC.仅E、皿、TVD.1、H、皿、W8.现有乏度为ll且初始为空的散列在HT，散列的数是 H(key)=key%7，采用线性探街（线忡，探测再散列）法解决冲突将关键字序列87,40,30,6,II,22，饵，20依次插入到HT后，HT奇找失败的平均冕战长度是A.4 8.5.25 C.6 D.6.299.设主申 T“abaabaal】cabaa be”，模式申 S“abaabc”，采用 KMP J+法进行模式匹配，到匹配成 功111为止，在匹配过程中进行的单个于符间的比较次数是A.9B.10 C.12D.15 10.排厅，过秤，巾，对尚未确定最终位置的所有元东进行一遍处理称为一“跑”。下列序列巾，不11J能是快速排印第二趟结果的是A.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,60门设外存立有120个初始归并段，进行12路Hl并 时，为实现最佳归井，简要补充的虚段个数是A.IB.2C.3D.412.下列关于冯诺依曼结构计算机基本思想的叙述中，错误的是A.程序 的功能都通过中央处理器执行指令 实现B.指令和数据部用二迸制表示，形式上无差别C.指令按地址访问，数据都在指令中直接给出D.程序执行前，指令和数据J;j预先存放在在储器中13.考虑以下C语言代码：unsigned short usi=65535;short si=usi;执行上述 程序段后，si的值是A.-I B.-32767C.-3276814.下列关于缺页处用的叙述巾，错误的是A.缺页是在地.bl：转换时CPU检测到的种异常B.缺贞处理由操作系统提供的缺页处理程序米完成D.-65535 C.缺页处理程序根据页故障地址从外仔读入所 缺失的页D.缺贞处理完成后l叶剑发生缺贞的指令 的下一条指令执行15.某计算机采用大端方式，战？节编址。某指令中操作数的 机器 数为1234 FFOOH，眩操作数采用基址寻址方式，形式 地址（用补码占尽）为FFl2H，基址寄存器内容为FOOO OOOOH，则该操作数的LSB（扯低有效宁节）所在的地址是A.FOOO FFl2H C.EFFF FF12H B.FOOO FF15日D.EFFF FFl5H 16.下列有关处理器 时钟脉冲的号的叙述中，错误的是A.n,J钟脉冲信号111机器 脉冲源发出的脉冲信号经整形和分频后形成B.时钟脉冲信号的宽度称为时钟周期，M钟周期 的倒数为机器主频C.Hf钟周期以相邻状态单元间组合逻辑rl!路的故大延迟为基准淘宝店铺：光速考研工作室确定D.处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令17.某指令功能为Rr2Rrl+MRrO，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是I.通用寄再器组（GPRs)Il.算术逻辑单元（ALU)皿存储器（Memory)N.指令译码器（JD)A.仅I、EB.仅l,TT、田C.仅E、皿、WD仅I、田、W18.在采用“取指、译码取数、执行、访在、写回”5段流水线的处理器中，执行如下指令序列，其中sO、sl、s2、s3 和 t2-1曼示寄再器编号。IL:adds2,sl,s0/Rs2R s I +R sO 12:load s3,0(t2)I I R s3 M R t2+0I3:add s2,s2 s3 14:store s2,0(L2)下列指令对中，不存在数据冒险的是/I R s2R s2+R s3 I I M R t2 +0 R s2A.II 和 I3B.12 和 I3C.12 和 14D.I3 和 1419.假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-l333，即内存条所接插的存储器总线的工作频率为1333MHz、总线宽度为64位，则存储器总线的总带宽大约是A.10.66 GB/sB.32 GB/sC.64 GB/sD.96 GB/s20.下列关于磁盘再储器的叙述中，错误的是A.磁盘的格式化容量比非格式化容茧小B.扇区中包含数据、地址和校验等信息C磁盘存储器的最小读写单位为一个字节D.磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成21.某设备以中断方式与 CPU 进行数据交换，CPU 主频为 IGHz，设备接口中的数据缓冲寄存器为32位，设备的数据传输率为50kB/s。若每次中断开销（包括中断响应和中断处理）为 l000个时钟周期，则 CPU 用于该设备输入输出的时间占整个 CPU 时间的百分比最多是A.1.25%B.2.5%C.5%D.12.5%22.下列关于 DMA 方式的叙述中，正确的是I DMA 传送前由设备驱动程序设置传送参数1数据传送前由DMA 控制器请求总线使用权m.数据传送由DMA 控制器直接控制总线完成N.DMA 传送结束后的处理由中断服务程序完成A.仅I、HB.仅I、E、WC.仅E、皿、WD.I、E、E、W23.下列关于线程的描述中，错误的是A.内核级线程的调度由操作系统完成B.操作系统为每个用户级线程建立一个线程控制块C.用户级线程间的切换比内核级线程间的切换效率高D.用户级线程可以在不支持内核级线程的操作系统上实现24.下列选项中，可能将进程唤醒的事件是I.110结束n.某进程退出临界区皿当前进程的时间片用完A.仅IB.仅EC.仅I、ED.I、E、E25.下列关于系统调用的叙述中，正确的是I.在执行系统调用服务程序的过程中，CPU 处于内核态n.操作系统通过提供系统调用避免用户程序直接访问外设皿不同的操作系统为应用程序提供了统一的系统调用接口N.系统调用是操作系统内核为应用程序提供服务的接口A.仅I、WB.仅E、EC仅I、E、WD.仅I、皿、W26.下列选项中，可用于文件系统管理空闲磁盘块的数据结构是I.位图n.索引节点皿空闲磁盘块链A.仅I、EN.文件分配表（FAT)B.仅I、E、W淘宝店铺：光速考研工作室C.仅I、皿D仅E、田、W27.系统采用二级反馈队列调度算法进行进程调度。就绪队列 QI 采用时间片轮转调度算法，时间片为10 ms；就绪队列 Q2采用短进程优先调度算法；系统优先调度 QI 队列中的进程，当 Ql 为空时系统才会调度 Q2中的进程；新创建的进程首先进入 Ql;Ql 中的进程执行一个时间片后，若未结束，则转入 Q2。若：当前。l、Q2为空，系统依次创建进程 Pl、P2 后即开始进程调度 Pl、四百要的CPU 时间分别为30 ms 和 20 ms，则进程 Pl、P2 在系统中的平均等待时间为应拟地址2050 1225H对州的贞口录号、反号分别是A.081 H、101HB.081 H、401HA.25 msB.20 msC.15 msD.10 msC.201 H、l01 HD.201 H、4011132.在下列动态分区分配算法巾，直言容劫产生内在碎片的是A.首次适应11=法B.最坏适j也算法C.MH适应算法D.循环芮次适！但1；法33.OSI参考模咽的第5层（白下而t.）完成的主要功能是J.铺控制B.路Lli滥炸C.会iZ管理D.数据-Uift.转换34.I OOBaseT 快速以太网使用的导向传输介质是八双绞线B.单悦光纤C.多快Jt纤D.f,d都f电缆35.对于滑动窗口协议，如果分mrr-号采用3 比特编号，发送窗口大小为5，则接收窗口届大是A.2B.3C.4D.536.假设一个采用 CSMA/CD 协议的100 Mhps 局域网，段小帧i乏足 128B，则在一个冲突域内两个站点之间的机，1,1传播延时监多是A.2.56 sB.5.12 sC.10.24 sD.20.48 s37.行将 l01.200.16.0/20 划分为5 个子网，则可能的最小子网的可分IYc IP 地址数是A.126B.254C.510D.102238.；占有：尸通过一个 TCP 连接向服务器发送数据的部分过程如题38图所示客户在lo时刻第一次收到确认rr:列号 ack_seq=I 00的段，并发送序列号seq=100的段，但发哇丢失。.t:TCP 支持快速重传，则客户屯新发送seq=100段的时刻是28.在分段再储管理系统中，用共学段在描述所有被共字的段。丰午进程 Pl 和 P2 共字段 S，下列叙述1p，错误的是A.在物理内存中仅保在一份段S的内容B.段 S 在 Pl 和 P2 rj1应该具有相同的段号C.Pl J和P2 共享段 S 在共字段友小的段丘项D.Pl 和 P2 都不再使用段 SJlf才i口l收段 S 所山的内行空间29.某系统采用LRU页页换n法和局部lm换策略，拧系统为迸程P 1！分配了4个页框，进程 P 访问页号的rr-列为0,1,2,7,0,5,3,5,0,2,7,6，则进程访问上述页的过程中，产生Jj.i1换的总次数是A.3B.4C.530.下夕lj 关于死锁的叙述巾，正确的是I.i可以边过剥夺进程资源解除死锁I.夕E锁的预防方法能确保系统不友生死锁皿银行家算法可以判断系统是否处于死锁状态N.、可系统出现死锁时，必然有两个旦旦两个以i二的迸程处于fll束态A.仅H、皿B.仅I、H、WC.仅I、H、皿D.仅I、皿、W31.某计算机主仔按宁节编址，采用二级分贞在储管理，地址结构如下D.6A.t1 2 RU C.t3 D.t4 39.店主机可1主动发起一个与主机乙的 TCP 连接，可1、乙选择的初始f列号分别为 2018 和 2046，则第二次握子 TCP 段的确认序列号是所示JJi:I I求）(IO f,i.)到1号（IOfiL)JJ内偏移（12 位）A.2018B.2019C.204640.下列关于网络应用模型的叙述中，错误的是A.在 P2P 模型中，结点之间具有对等关系D.2047淘宝店铺：光速考研工作室客户to!3!4 时间服务器题38囱B.在客户服务器（C/S）模型巾，客户与客户之间可以直接通信C.在C/S模型中，主动发起通信的是客户，被动通信的是服务器0.在向多用户分发一个文件时，P2P模型通常比C/S 模型所市时间短二、综合应用题：“47小题，其70分。41.(13分）设线性表L=(a1,a2，句，a.-2,an-I,an）采用带头结点的单链表保存，链表中结点定义如下：typedef struct nodeI int data;struct node*next;I NODE;谙设计一个空间复杂度为O(I）且时间上尽可能高效的算法，E新排列L中的各结点，得到线性表L(a1，气，鸟，a.-1，鸟，a.-2，）。要求：(I）给出算法的基本设计思想(2）根据设计思想，采用C或C语言描述算法，关键之处给出注释。(3）说明你所设计的算法的时间复杂度。42.(10分)i.j设计一个队列，要求满足：初始时队列为空；入队时，允许增加队列占用空间；出队后，出队元素所占用的宅时可重复使用，即整个队列所占用的空间只增不减；入队操作和出队操作的时间复杂度始终保持为0(I）。请回答下列问题：(1）该队列应该选拇链式存储结构，近是顺序在储结构？(2）画出队列的初始状态，并给出判断队空和l队满的条件(3）刚出第一个元亲人队后的队列状态。(4）给出入队操作和l出队操作的基本过程。43.(8分）有n(n注3）位哲学家用坐在一张圆桌边，创位哲学家交替地就餐和l思考。在国桌中心有m(m;:,I）个碗，每两位哲学家之间有l根筷子。每位哲学家必须取到一个碗和两侧的筷F之后，才能就餐，进餐完毕，将碗和l筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号茸的 P、V操作（wait（）、signal（）操作）描述上述过程中的互斥与向步，并说明所用信号盐及初值的含义。44.(7分）某计算机系统中的磁盘有300个柱而，每个柱面有10个磁道，每个磁道有200个扇区，扇区大小为512 B。文件系统的每个簇包含2个扇区。hf回答下列问题：(1）磁盘的容业是多少？(2）假设磁头在85号桂面上，此时有4个磁盘访问请求，簇号分别为：100 260、60 005、101 660 和l 10 560。若采用最短寻道时间优先（SSTF）调度算法，则系统访问簇的先后次序是什么？(3）第 100 530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由I/0系统的什么程序完成的？45.(16分）己知f(n)=n!=n x(n-I)X(n-2)xx2xl，计算J（川的淘宝店铺：光速考研工作室C语言函数门的源程序（阴影部分）及其在32位计算机Mt的部分机器级代码如下：int fl(int n)I1 00401000 55 if(nl)push ebp 11 00401018 83 7D 08 0 I cmp dword plr ebp+8,I 12 0040101C 7E 17 jle f1+35h(00401035)return n*fl(n-1);13 0040101E 8B 45 08 14 00401021 83 E8 01 15 00401024 50 mov e缸，dword ptr ebp+8 sub eax,l push eax 16 0040 I 025 E8 D6 FF FF FF call fl(0040 I 000)19 00401030 OF AF Cl imul eax,ecx 20 00401033 EB 05 jmp fl+3Ah(0040103a)else return I;21 00401035 26 00401040 B8 01 00 00 00 mov 38 EC cmp 30 0040104A C3 rel eax,l ebp,esp 其中，机器级代码行包插行号、虚拟地址、机器指令和汇编指令，计算机 M 披字节编址，int 型数据占 32 位。请回答下列问题：(1）计算！（10）荷要调用函数fl多少次？执行哪条指令会递lj I调用 fl?(2）上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？(3）根据第16 行 call 指令，第门行指令的虚拟地址应是多少？巳知第16 行 call 指令采用相对寻址方式，该指令中的偏移量应是多少（给出计算过程）？已知第16 行 call 指令的后4字节为偏格茧，M采用大端还是小端方式？(4)f(13)=6 227 020 800，但 fl(l3）的返回值为 l 932 053 504，为什么两者不相等？要使f1(13）能返回正确的结果，应如何修改门源程序？(5）第 19行1YR ecx，吁乘法器输出的l二5、低32位乘积之问满足什么条件HJ，溢出标志OF=1？要使 CPU J巨友生溢出时转非常处理，编译器应在 imul 揣令后)Ju一条什么指令？46.(7 分）对于题45，若计算机M的主存地址为32 位，采用分页存储管理方式，页大小为4 KB，则第 l 行 push 指令和 第 30行 rel 指令是否在同一页中（说明理由）？行指令 Cache 有 64行，采用4路组相联映射方式，主仔块大小为 64B，则 32 位主存地址巾，哪几位表示块内地址？哪儿位在示 Cache组号？哪几位表示标记（lag）信息？读取第 16行 call 指令时，只可能在指令 Cache的哪一组中命中（说明理由）？47.(9分）某网络拓扑如题 47图所示，只中R为路由器，主机H1 H4的 IP 地址配置以及R的各接 fl IP 地址配置如图中所示。现有若F台以太网交换机（无VLAN功能）和 路由器两类网络互连设备可供选择。请回答下列问题：(l）设备l、设备2和设备3分别应选择什么类型网络设备？(2）设备l、设备2 和设备3巾，哪几个设备的接口需要配置 IP 地址？并为对应的接口配置正确的 IP 地址。(3）为确保主机 Hl H4 能够的问 Internet,R 需要提供什么服务？(4）若主机 H3 发送一个口的地址为 192.168.1.127的 IP 数据报，网络 中哪几个 主机会接收该数据报？淘宝店铺：光速考研工作室101.1.2.10 !Fl 年：设备14IP地址192.168.1.2/26 IP地址：192.168.1.3/26IP地址：l92.168.1.66/26 IP地.l!f:192.168.1.67/26 默认网关：192.168.1.1 默认网关：192.168.1.1默认例关：192.168.1.65默认闷关192.168.1.65题47图I.B6.A11.B16.D21.A26.B31.A36.B、2019年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题参考答案单项选择题2.B3.C4.A5.C7.D8.C9.B10.D12.C13.A14.D15.D17.B18.C19.B20.C22.D23.B24.C25.C27.C28.B29.C30.B32.C33.C34.A35.B37.B38.C39.D40.B综合应用题41.答案要点(1）算法的基本设计思想：算法分3步完成第l步，采用两个指针交替前行，找到守主链表的中间结点；第2步，将单链表的后半段结点原地逆置；第3步，从单链表前后两段中依次各取一个结点，按要求重排。(2）算法实现：void change_list(NODE*h)NODE*p,*q,*r,*s;p=q=h;while(q-next!=NULL)寻找中间结点淘宝店铺：光速考研工作室p=p-next;II p走一步q=q-nexl;if(q-next!=NULL)q=q-next;I I q走阔步q二p-next;I I p所指结点为巾问结点，q为后、卡段链点的计结点p-next=NULL;while(q!=NULL)II将链在盯、卡段逆EI r=q-next;q-nrxt=p-next;p-next=q;q=r;吕 h-next;II s指向前中段的第一个数如结点，,!JJ插入点q=p-next;II q指向后平段的第一个数据结点p-next=NULL;while(q!=NULL)将链在后、长段的结点插入到指定位置r=q-next;I I r指向后、毛段的下一个结点q-next=s-nexl;将q所指结点插入到s所指结点之后s-next=q;s=q-next;II s指向前半段的下一个插入点q=r;(3）算法的时间复杂度：参考答案的时间复杂度为0(n)42.答案要点(I）采用链式仔储结构（两段式单向循环链在），队头指针为front,队尾指针为rear(2）初始时，创建只有一个空闲结点的两段式单向循环链表，头指针front与尾指针陀ar均捐oJ空闲结点如1下图所示。二里二队空的判定条件：front=rear。队满的判定条件：front=rear-next。(3）插入第二个元素后的队列状态：(4）操作的基本过程：人队操作：,:(front=rear-nexl)队满则在rear!Ci面恼人一个新的空闲结点；人队JGi号保存到rear所指纣点小；rear=rear-next；返问Ill队操作：导干(front=rear)队空则111队失败，返；J:lil front所指纺点巾的元才f e;front=front-ne1；返回e。43.答案要点信号iJ:semaphore bowl;用于协调哲学家对碗的使用semapl阳e chopsticks n ;for(int i=O;i n;i+)用于协调听学家对筷子的使用淘宝店铺：光速考研工作室chopsticks i .value=I;设置两个哲学家之间筷子的数盐bowl.value=min(n-1,m);I I bowl.value主三n-1，确保不死锁Co B egin w h i le(True)I哲学家i的程序思考；P(bowl);P(chopstic ks i );P(chopsticks(i+I)MOD n);就餐；V(chopstick s i );V(chopsticks(i+I)MOD n);V(bowl);C oEnd 44.答案要点取碗取左边筷子取右边筷子(1）磁盘容量（300 xl0 x200 x512/1024)KB=3105KB。(2）依次访问的簇是100 260、IOI 660、l10 560、60 005。(3）第100 530簇在磁盘上的物理地址由其所在的柱面号、磁头号、扇区号构成其所在的柱面号为L100530/(10 x200/2）100。100530%(10 x200/2)=530，磁头号为L5301c 20012）5o 剧区号为（5302)%200=60。将簇号转换成磁监物理地址的过程由磁盘驱动程序完成。45.答案要点(1）计算J(10）芮要调用函数fl共10次执行第16行call指令会递lj I调用fl。(2）第12行jle指令是条件转移指令。第16行call指令、第20行jmp指令、第30行削指令一定会使程序跳转执行。(3）第16行call指令的下一条指令的 地址为0040 1025H+5=0040 102AH，故第17行指令的虚拟地址是0040 I 02A H call 指令采用相对寻址方式，即门标地址（PC）偏移茧，call指令的U标地址为0040 IOOOH，所以偏移吐fl标地址（PC)=0040 IOOOH-0040 102AH=FFFF FFD6H 根据第16行call指令的偏移茧字段为D6 FF FF FF，可确定M采用小端方式。(4）囚为J(13)=6 227 020 800，大于32位int 型数据可表示的最大值，因而fl(l3）的返回值是一个发生了溢出的结果。为使fl(l3）能 返11正确结果，可将函数门的返回值类电改为do uble（或long long 或long do uble.!.!.X flo at)0(5）若乘积的高33位为非全0 或七全l，则OF=I 编译器应该在irnul指令后加一条“溢出自陷指令”，使得CPU白动查询溢出 标忐OF，巧OF=I时调出“溢出异常处理 程序”。46.答案要点第l行指令和第30行指令的代码在同一页。因为页大小为4KB，所以虚拟地址的高20位为虚拟页号。第 l行指令和！第30行指令的虚拟地址 高20位都是00401H，因此两条指令在同一页中。Cache组数为64/4=16，因此，主存地址刷分巾，低6位为块内地址、中间4位为组号（细索引）、自22位为标记。读取第16行call指令时，只吁能在指令 Ca che第0 组中命中。因为页大小为4KB，所以虚拟地址和 物理地址的最低12位完全相同，因而call指令 虚拟地址 0040 1025H中的025H=0000 00100 IO I B=00 0000 100 IO I B 为物理地址的低12位，故对应Ca che组号为0。47.答案要点(I）设备l：路由器，设备2：以太网交换机，设备3：以太网交换机(2）设备l 的接口市要配置IP地址；民备l 的IFI、JF2和IF3 接口的IP地址分别是：192.168.1.254、192.168.1.1 和192.168.1.650(3)R需要提供NAT服务(4）主机H4会接收该数据报。淘宝店铺：光速考研工作室