2019年全国硕士研究生入学统一考试计算机学科专业基础综合真题.docx

2019年全国硕士研究生入学统一考试计算机学科专业基础综合真题(总分：150. 00，做题时间:180分钟)一、单项选择题(总题数：4(),分数：80. 00)设n是描述问题规模的非负整数，以下程序段的时间复杂度是()ox=0：while (n= (x+l)*(x+D)x=x+l：(分数：2. 00)A. O(log n)B.0(n,/2)B. O(n)D.0(n2)解析：1. 假设将-棵树T转化为对应的二又树BT,那么以下对BT的遍历中，其遍历序列与T的后根遍历序列相 同的是()。(分数：2.00)A. 先序遍历B. 中序遍历 JC. 后序遍历D. 按层调历 解析：2. 对n个互不相同的符号进行哈夫曼编码。假设生成的哈夫曼树共有115个结点，那么n的值是 ()o (分数：2. 00)A. 56B. 57C. 58 VD. 60解析:c.D.t4解析：39. 假设主机甲主动发起一个与主机乙的TCP连接，甲、乙选择的初始序列号分别为2018和2046,那么第 三次握手TCP段确实认序列号是()。(分数：2. 00)A. 2018B. 2019C. 2046D. 2047 V解析：40. 以下关于网络应用模型的表达中，错误的选项是()。(分数：2.00)A. 在P2P模型中，结点之间具有对等关系B. 在客户/服务器(C/S)模型中，客户与客户之间可以直接通信 7C. 在C/S模型中，主动发起通信的是客户，被动通信的是服务器D. 在向多用户分发一个文件时，P2P模型通常比C/S模型所需时间短解析：二、综合应用题(总题数：7,分数：70. 00)设线性表L=(al, a2, a，an-2, a-L a。)采用带头结点的单链表保存，链表中结点定义如下： typedef struct node int data；struct node* next； NODE；请设计一个空间复杂度为0(1)旦时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L =(31, fin, &2r 3n-l fo要求：(分数：13)(1) .给出算法的基本设计思想。(分数：3)正确答案：(算法的基本设计思想：先刈1 察 L= (a” a- a3, . ,a”)和 L = (a”a?, as an-2 . ) 发现 L 是由 L 摘取第一个元素，再摘取倒数第一个元素依次合并而成的。为了方便链表后半段取元素，需要先将L后半 段原地逆置题目要求空间复杂度为0(1),不能借助栈,否那么每取最后一个结点都需要遍历一次链 表。先找出链表L的中间结点，为此设段两个指针p和q,指针p每次走一步，指针q每次走两 步，当指针q到达链尾时，指针P正好在链表的中间结点：然后将L的后半段结点原地逆置。从 单链表前后两段中依次各取一个结点，按要求重排。)解析：(2) .根据设计思想，采用C或C+语言描述算法，关键之处给出注释。(分数：5)正确答案：(算法实现:)解析：(3) .说明你所设计的算法的时间复杂度。(分数：5)正确答案：(第1步找中间结点的时间复杂度为0(n),第2步逆置.的时间复杂度为0(n),第3步合并链表的时间复杂 度为0(n),所以该算法的时间复杂度为0(n)。)解析：请设计一个队列，要求满足：初始时队列为空：入队时，允许增加队列占用空间；出队后，出队 元素所占用的空间可重复使用，即整个队列所占用的空间只增不减：人队操作和出队操作的时间复杂 度始终保持为0(1)。请回答以下问题：(分数：10).该队列应该选择链式存储结构，还是顺序存储结构？(分数：2)正确答案：(顺序存储无法满足要求的队列占用空间随假设入队操作而增加。根据要求来分析：要求容易满足：链式 存储方便开辟新空间，要求容易满足；对于要求，出队后的结点并不真正释放，用队头指针指向新的 队头结点，新元素入队时，有空余结点那么无须开辟新空间，赋值到队尾后的第一个空结点即可，然后用队 尾指针指向新的队尾结点，这就需要设计成一个首尾相接的循环单链表，类似于循环队列的思想。设置队 头、队尾指针后，链式队列的入队操作和出队操作的时间复杂度均为0(1),要求可以满足。因此，采用链式存储结构(两段式单向循环链表)，队头指针为front,队尾指针为rear。)解析：(1) .画出队列的初始状态，并给出判断队空和队满的条件。(分数：2)正确答案：（ 该循环链式队列的实现，可以参考循环队列，不同之处在于循环链式队列可以方便增加空间，出队的结点 可以循环利用，入队时空间不够也可以动态增加。同样，循环链式队列也要区分队满和队空的情况，这里 参考循环队列牺牲一个单元来判断。初始时，创立只有一个空闲结点的循环单链表，头指针front和尾 指针rear均指向空闲结点，如以下图所示。队空的判定条件：front = rear。 队满的判定条件：front = rcar-ncxto解析:（3）.画出第个元素入队后的队列状态。（分数：3）正确答案：（ 插入第个元素后的状态如以下图所示。） 解析:（4）.给出入队操作和出队操作的基本过程。（分数：3）正确答案：（ 操作的基本过程如卜:）解析:41. 有n（nN3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有个 碗，每两位哲学家之间有1根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完 毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲斗家同时就餐，且防止出现死锁现象，清使 用信号量的P、V操作（wait。、signal（）操作）描述上述过程中的互斥与同步，并说明所用信号量及初 值的含义。（分数：8. 00）正确答案：（正确答案：(第12行的jlc指令是条件转移指令，其含义为小于等于时转移，本行代码的意义为：当nWl时，跳 转至地址0040 1035Ho第16行的call指令为函数调用指令，第20行的jmp指令为无条件转移指 令，第30行的ret指令为子程序的返回指令，这三条指令一定会使程序跳转执行。)解析：(3).根据第16行call指令，第17行指令的虚拟地址应是多少？己知第16行call指令采用相对寻 址方式，该指令中的偏移量应是多少(给出计算过程)？己知第16行call指令的后4字节为偏移量， M采用大端还是小端方式？(分数：3)正确答案：(其长度计算机M上按字节编址，第16行的call指令的虚拟地址为0040 1025H,长度为5字节，故 第17行的指令的虚拟地址为0040 1025H + 5 = 0040 102A1U第16行的call指令采用相对寻址方 式，即目标地址=(PC) +偏移量，call指令的目标地址为0040 1000H,所以偏移登=目标地址-(PC) =0040 1000H - 0040 102AH = FFFF FFD6H.根据第 16 行的 call 指令的偏移量字段为 D6 FF FF FF, 可以确定M采用小端方式。)解析：(4) . f (13)=6 227 020 800,但fl(13)的返回值为1 932 053 504,为什么两者不相等?要使fl (13)能 返回正确的结果，应如何修改fl源程序？(分数：3)正确答案：(因为f(13) = 6227020800,其结果超出了 32位int型数据可表示的最大范围，因此f(13)的返回值是 一个发生了溢出的错误结果。为使fl (13)能返回正确结果，可将函数fl的返回值类型改为double (或 long long,或 long double 或 float)类型。)解析：(5) .第19行imul eax,ecx表示有符号数乘法，乘数为Reax和Recx,当乘法器输出的高、低32 位乘积之间满足什么条件时，溢出标志OF=1?要使CPU在发生溢出时转异常处理，编译器应在imul 指令后加一条什么指令？(分数：4)正确答案：(假设乘积的高33位为非全0或非全1,那么0F = 1。编译器应在imul指令后加一条“溢出自陷指令”， 使得CPU自动查询溢出标志OF,当OF = 1时调出“溢出异常处理程序”。解析:42. 对于题45,假设计算机M的主存地址为32位,采用分页存储管理方式，页大小为4KB,那么第1行 push指令和第30行ret指令是否在同一页中（说明理由）？假设指令Cache有64行，采用4路组相联 映射方式，主存块大小为64B,那么32位主存地址中，哪儿位表示块内地址？哪儿位表示Cache组号？ 哪几位表示标记（lag）信息？读取第16行call指令时，只可能在指令Cache的娜一组中命中（说明理 山）？（分数：7. 00）正确答案：（ 因为页大小为4KB,所以虚拟地址的高20位为虚拟页号。第1行的push指令和第30行的ret指 令的虚拟地址的高20位都是00401H,因此两条指令在同-页中。指令Cache有64块，采用4路组相联映射方式，故指令Cache共有64/4 =16组，Cache组号共4 位。主存块大小为64B,故块内地址为低6位。综上所述，在32位主存地址中，低6位为块内地址， 中间4位为组号，高22位为标记。因为页大小为4KB,所以虚拟地址和物理地址的最低12位完全相同，因而call指令虚拟地址0040 1025H中的025H = 0000 0010 0101B为物理地址的低12位，对应的710位为组号，故对应的 Cache组号为0。解析: 某网络拓扑如题47图所示，其中R为路山器，主机H1TI4的IP地址配置以及R的各接口 IP地址 配省如图中所示。现有假设干台以太网交换机（无VLAN功能）和路由器两类网络互连设备可供选择。请回答以下问题：（分数：9）（1）.设备1、设备2和设备3分别应选择什么类型网络设备？（分数：2）正确答案：（以太网交换机（无VLAN功能）连接的假设干LAN仍然是一个网络（同一个广播域），路山器可以连接不 同的LAN、不同的WAN或把WAN和LAN互联起来，隔离了广播域。IP地址192. 168. 1. 2/26与192. 168. 1. 3/26 的网 络前缀 均为 192. 168. 1.0,视 为 LANE IP 地 址 192. 168. 1.66/26 与192. 168. 1.67/26的网络前缀均为192.168.1.64,视为LAN2。所以设备1为路由器,设备2、3为以 太网交换机。解析:（2）.设备1、设备2和设备3中，哪儿个设备的接口需要配置IP地址？并为对应的接口配置正确的 TP地址。（分数：2）正确答案：（设备1为路由器，其接口应配置IP地址。IF1接口与路由器R相连，其相连接口的IP地址为192. 168. 1.253/30, 253的二进制表示形式为11111101,故IF1接口的网络前缀也应为192. 168. 1. 111111,己分配 192. 168. 1.253,去除全 0 全 1, IF1 接口的 IP 地址应为192. 168. 1.254 LAN1的默认网关为192. 168. 1. 1, LAN2的默认网关为192. 168. 1.65,网关的IP地址是具有路由功能的设备的IP地址，通常默认网关地址就是路由器中的LAN端口地址，设备1的IF2、 IF3接口的IP地址分别设置为192. 168. 1. 1和192. 168. 1. 65,）解析：（3）.为确保主机H1H4能够访问Internet, R需要提供什么服务？（分数：2）正确答案：（私有地址段:C类192. 168.0. 0192. 168.255.255,即H1H4均为私有IP地址，假设要能够访问 Internet, R需要提供NAT服务,即网络地址转换服务。）解析：（4）.假设主机H3发送一个目的地址为的IP数据报，网络中哪几个主机会接收该数据 报？（分数：3）正确答案：（主机H3发送一个目的地址为192. 168. 1. 127的IP数据报，主机号全为1,为本网络的广播地址，由 于路由器可以隔离广播域，只有主机H4会接收到数据报。）解析：3. 在任意一棵非空平衡二又树（AVL树）中，删除某结点v之后形成平衡二又树T”再将w插入L形 成平衡二又树T；lo以下关于与L的表达中，正确的选项是（）。I .假设v是Ti的叶结点，那么L与L可能不相同假设v不是的叶结点，那么L与T3一定不相同II. 假设v不是，的叶结点，那么与L一定相同（分数：2. 00）A. 仅 I VB. 仅 IIC. 仅 I、IID. 仅 I、III 解析：4. 以下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是 （）0（分数：2.00）A. 3 和 7121415B. 12C. 12D. 15 解析：）。（分数：2.00）5. 用有向无环图描述表达式（x+y）*（x+y）/x）,需要的顶点个数至少是（A. 5 JB. 6C. 8D. 9解析：6. 选择一个排序算法时，除算法的时空效率外，以下因素中，还需要考虑的是（）。I. 数据的规模II .数据的存储方式III. 算法的稳定性数据的初始状态（分数：2.00）A. 仅IIIB. 仅 I、IIC. 仅 1【、IIL IVD. 【、II、IIL IV J 解析：7. 现有长度为11且初始为空的散列表HT,散列函数是H（key）=key%7,采用线性探查（线性探测再散列） 法解决冲突将关键字序列87, 40, 30, 6, 11, 22, 98, 20依次插入到HT后，HT查找失败的平均查找长度是（）。（分数：2. 00）A. 4B. 5. 25C. 6 VD. 6. 29解析：8. 设主串T= abaabaabcabaabc”，模式串S= abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比拟次数是（）。（分数：2.00）A. 9B. 10 JC. 12D. 15解析：9. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。以下序列中，不可能是快速排序第二趟结果的是（）。（分数：2.00）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 J11.设外存上有（ ）。120个初始归并段，进行12路归并时，为实现最正确归并，需要补充的虚段个数是（分数：2. 00）A. 1B. 2 VC. 3D. 4解析：12. 以下关于冯诺依曼结构计算机基本思想的表达中，错误的选项是（）。（分数：2.00）A. 程序的功能都通过中央处理器执行指令实现B. 指令和数据都用二进制表示，形式上无差异C. 指令按地址访问，数据都在指令中直接给出 JD. 程序执行前，指令和数据需预先存放在存储器中解析：13. 考虑以下C语言代码：unsigned short usi=65535：short si=usi:执行上述程序段后，si的值是（） （分数：2. 00）A. -1 5/B. -32767C. -32768D. -65535解析：14. 以下关于缺页处理的表达中，错误的选项是（）。（分数：2.00）A. 缺页是在地址转换时CPU椅测到的一种异常B. 缺页处理由操作系统提供的缺页处理程序来完成C. 缺页处理程序根据页故障地址从外存读入所缺失的页D. 缺页处理完成后回到发生缺页的指令的下一条指令执行 J解析：15. 某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234 FF00H,该操作数采用基址寻 址方式，形式地址（用补码表示）为FF12II,基址寄存器内容为F000 0000H,那么该操作数的LSB（最低有 效字节）所在的地址是（）.（分数：2.00）A. F000 FF12HB. F000 FF15HC. EFFF FF12HD. EFFFFF15H V解析：16. 以下有关处理器时钟脉冲信号的表达中，错误的选项是（）。（分数：2.00）A. 时钟脉冲信号山机器脉冲源发出的脉冲信号经整形和分频后形成B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C. 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D. 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令 V解析：17. 某指令功能为Rr2-Rrl+MRrO,其两个源操作数分别采用寄存器、寄存器间接寻址方式。对 于以下给定部件，该指令在取数及执行过程中需要用到的是（）o1 .通用寄存器组（GPRs）II. 算术逻辑单元（ALL）存储器（Memory）III. 指令译码器（ID）（分数：2. 00）A. 仅 I、IIB. 仅 I、II、III JC. 仅 II、III、IVD. 仅 I、山、IV解析:写回” 5段流水线的处理器中，执行如下指令序列，其中/Rs2*-Rsl+RsO/Rs3-MRt2+0 Rs2-Rs2+Rs3MRt2+0-Rs2）。（分数：2. 00）18. 在采用“取指、译码/取数、执行、访存、 sO、si、s2、s3和t2表示寄存器编号。I 1: add s2, si, sOI 2： load s3, 0（t2）I 3： add s2, s2 s3I 4： store s2, 0（t2）以下指令对中，不存在数据冒险的是（A. I 1 和 I 3B. 2 和 I 3C. I 2和【4 JD. I 3 和 I 4解析:19. 假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-1333,即内存条所接插的存储器 总线的工作频率为1333 MHz、总线宽度为64位，那么存储器总线的总带宽大约是（） （分数：2. 00）A. 10. 66 GB/sB. 32 GB/sVC. 64 GB/sD. 96 GB/s解析：20. 以下关于磁盘存储器的表达中，错误的选项是（）。（分数：2. 00）A. 磁盘的格式化容量比非格式化容量小B. 扇区中包含数据、地址和校验等信息C. 磁盘存储器的最小读写单位为一个字节 VD. 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成解析：21. 某设备以中断方式与CPU进行数据交换，CPU主频为1 GHz,设备接口中的数据缓冲寄存器为32 位，设备的数据传输率为50kB/s。假设每次中断开销（包括中断响应和中断处理）为1000个时钟周期，那么 CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是（）。（分数：2. 00）A. 1. 25% JB. 2. 5%C. 5%D. 12. 5%解析：22. 以下关于DMA方式的表达中，正确的选项是（）oI . DMA传送前由设备驱动程序设置传送参数II. 数据传送前由DMA控制器请求总线使用权数据传送由DMA控制器直接控制总线完成III. DMA传送结束后的处理由中断服务程序完成（分数：2.00）A. 仅 I、IIB. 仅 I、III、IVC. 仅 II、III、IV【）.I、II、III、IV J解析：23. 以下关于线程的描述中，错误的选项是（）。（分数：2.00）A. 内核级线程的调度由操作系统完成B. 操作系统为每个用户级线程建立一个线程控制块JC. 用户级线程间的切换比内核级线程间的切换效率高D. 用户级线程可以在不支持内核级线程的操作系统上实现 解析：24. 以下选项中，可能将进程唤醒的事件是（）。I . I/O结束某进程退出临界区II. 当前进程的时间片用完（分数：2.00）A. 仅IB. 仅IIIC. 仅 I、II JD. I、II、III解析：25. 以下关于系统调用的表达中，正确的选项是（）.在执行系统调用服务程序的过程中，CPU处于内核态I 操作系统通过提供系统调用防止用户程序直接访问外设IH.不同的操作系统为应用程序提供了统一的系统调用接口III. 系统调用是操作系统内核为应用程序提供服务的接口（分数：2.00）A. 仅 I、IVB. 仅 II、IIIC. 仅 I、II、D. 仅 I、Ilk IV解析：26. 以下选项中，可用于文件系统管理空闲磁盘块的数据结构是（）。I .位图.索引节点III. 空闲磁盘块链文件分配表（FAT）（分数：2.00）A. 仅 I、IIB. 仅 I、III、IV JC. 仅 I、IIID. 仅 II、III、IV解析：27, 系统采用二级反应队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为 10ms：就绪队列Q2采用短进程优先调度算法：系统优先调度Q1队列中的进程，当Q1为空时系统才 会调度Q2中的进程：新创立的进程首先进入QI； Q1中的进程执行一个时间片后，假设未结束，那么转入 Q2。假设当前QI、Q2为空，系统依次创立进程Pl、P2后即开始进程调度Pl、P2需要的CPU时间分别 为30ms和20ms,那么进程Pl、P2在系统中的平均等待时间为（） （分数：2.00）A. 25 mB. 20 msC. 15 ms JD. 10 ms 解析：28. 在分段存储管理系统中，用共享段表描述所有被共享的段。假设进程P1和P2共享段S,卜列表达 中，错误的选项是（分数：2.00）A. 在物理内存中仅保存一份段S的内容B. 段S在P1和P2中应该具有相同的段号 VC. P1和P2共享段S在共享段表中的段表项D. P1和P2都不再使用段S时才回收段S所占的内存空间解析：29. 某系统采用LRU页置换算法和局部置换策略，假设系统为进程P预分配了 4个页框，进程P访问页 号的序列为0，1, 2, 7, 0, 5, 3, 5, 0, 2, 7, 6,那么进程访问上述页的过程中，产生页置.换的总次数 是（）。（分数：2. 00）A. 3B. 4C. 5VD. 6 解析：30.以下关于死锁的表达中，正确的选项是（）。I 可以通过剥夺进程资源解除死锁II死锁的预防方法能确保系统不发生死锁1H.银行家算法可以判断系统是否处于死锁状态IV.当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态（分数：2. 00）A. 仅 II、IIIB. 仅 1、II、IV JC. 仅 I、II、IIID. 仅 I、IIL IV解析：31.某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示页目录号（10位） 页号（10位） 页内偏移（12位）虚拟地址2050 1225H对应的页目录号、页号分别是（）。（分数：2. 00）A. 081H. 101H VB. 081H、401HC. 201H、10111D. 201H、401H 解析：32.在以下动态分区分配算法中，最容易产生内存碎片的是（）o （分数：2.00）A. 首次适应算法B. 最坏适应算法C. 最正确适应算法 JD. 循环首次适应算法 解析：33.OSI参考模型的第5层（自下而上）完成的主要功能是（）0 （分数：2.00）A. 过失控制B. 路由选择C. 会话管理JD. 数据表示转换 解析：34. lOOBaseT快速以太网使用的导向传输介质是（分数：2.00）A. 双绞线 J单模光纤C. 多模光纤D. 同轴电缆解析：35. 对于滑动窗I协议，如果分组序号采用3比特编号，发送窗口大小为5,那么接收窗口最大是 （）。（分数：2. 00）A. 2B. 3 VC. 4D. 5解析：36. 假设个采用CS.MA/CD协议的100Mbps局域网，最小帧长是128 B,那么在个冲突域内两个站点之 间的单向传播延时最多是（）o （分数：2.00）A. 2. 56 P sB. 5. 12 us VC. 10. 24 usD. 20. 48 us解析：37. 假设将101. 200. 16. 0/20划分为5个子网，那么可能的最小子网的可分配IP地址数是 （）。（分数：2. 00）A. 126B. 254 JC. 510D. 1022 解析：38. 某客户通过一个TCP连接向服务器发送数据的局部过程如题38图所示。客户在10时刻第一次收 到确认序列号ack seq=100的段，并发送序列号seq=100的段，但发生丧失。假设TCP支持快速重传, 那么客户重新发送seq=100段的时刻是（）。.（分数：2. 00）A.B.