搜索
2019年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求）1．设n是描述问题规模的非负整数，下列程序段的时间复杂度是。x=0;while(n=(x+1)*(x+1))x=x+1;A．O(logn)B．O(n1/2)C．O(n)D．O(n2)2．若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是。A．先序遍历B．中序遍历C．后序遍历D．按层遍历3．对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是。A．56B．57C．58D．604．在任意一棵非空平衡二叉树（AVL树）T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是。I．若v是T1的叶结点，则T1与T3可能不相同II．若v不是T1的叶结点，则T1与T3一定不相同III．若v不是T1的叶结点，则T1与T3一定相同A．仅IB．仅IIC．仅I、IID．仅I、III5．下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是。A．3和7B．12和12C．12和14D．15和156．用有向无环图描述表达式()(()/)xyxyx，需要的顶点个数至少是。A．5B．6C．8D．97．选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是。I．数据的规模II．数据的存储方式III．算法的稳定性IV．数据的初始状态A．仅IIIB．仅I、IIC．仅II、III、IVD．I、II、III、IV·2·8．现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列87,40,30,6,11,22,98,20依次插入HT后，HT查找失败的平均查找长度是。A．4B．5.25C．6D．6.299．设主串T=abaabaabcabaabc，模式串S=abaabc，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是。A．9B．10C．12D．1510．排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不．可能是快速排序第二趟结果的是。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,6011．设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是。A．1B．2C．3D．412．下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是。A．程序的功能都通过中央处理器执行指令实现B．指令和数据都用二进制数表示，形式上无差别C．指令按地址访问，数据都在指令中直接给出D．程序执行前，指令和数据需预先存放在存储器中13．考虑以下C语言代码：unsignedshortusi=65535;shortsi=usi;C．-32768执行上述程序段后，si的值是。A．-1B．-32767D．-6553514．下列关于缺页处理的叙述中，错误的是。A．缺页是在地址转换时CPU检测到的一种异常B．缺页处理由操作系统提供的缺页处理程序来完成C．缺页处理程序根据页故障地址从外存读入所缺失的页D．缺页处理完成后回到发生缺页的指令的下一条指令执行15．某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234FF00H，该操作数采用基址寻址方式，形式地址（用补码表示）为FF12H，基址寄存器的内容为F0000000H，则该操作数的LSB（最低有效字节）所在的地址是。A．F000FF12HB．F000FF15HC．EFFFFF12HD．EFFFFF15H16．下列有关处理器时钟脉冲信号的叙述中，错误的是。A．时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成B．时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C．时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D．处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令17．某指令功能为R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是。I．通用寄存器组（GPRs）II．算术逻辑单元（ALU）·3·III．存储器（Memory）IV．指令译码器（ID）A．仅I、IIB．仅I、II、IIIC．仅II、III、IVD．仅I、III、IV18．在采用“取指、译码/取数、执行、访存、写回”5段流水线的处理器中，执行如下指令序列，其中s0、s1、s2、s3和t2表示寄存器编号。I1：adds2,s1,s0//R[s2]R[s1]+R[s0]I2：loads3,0(t2)//R[s3]M[R[t2]+0]I3：adds2,s2,s3//R[s2]R[s2]+R[s3]I4：stores2,0(t2)//M[R[t2]+0]R[s2]下列指令对中，不存在数据冒险的是。A．I1和I3B．I2和I3C．I2和I4D．I3和I419．假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总线的工作频率为1333MHz，总线宽度为64位，则存储器总线的总带宽大约是。A．10.66GB/sB．32GB/sC．64GB/sD．96GB/s20．下列关于磁盘存储器的叙述中，错误的是。A．磁盘的格式化容量比非格式化容量小B．扇区中包含数据、地址和校验等信息C．磁盘存储器的最小读写单位为一字节D．磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成21．某设备以中断方式与CPU进行数据交换，CPU主频为1GHz，设备接口中的数据缓冲寄存器为32位，设备的数据传输率为50kB/s。若每次中断开销（包括中断响应和中断处理）为1000个时钟周期，则CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是。A．1.25%B．2.5%C．5%D．12.5%22．下列关于DMA方式的叙述中，正确的是。I．DMA传送前由设备驱动程序设置传送参数II．数据传送前由DMA控制器请求总线使用权III．数据传送由DMA控制器直接控制总线完成IV．DMA传送结束后的处理由中断服务程序完成A．仅I、IIB．仅I、III、IVC．仅II、III、IVD．I、II、III、IV23．下列关于线程的描述中，错误的是。A．内核级线程的调度由操作系统完成B．操作系统为每个用户级线程建立一个线程控制块C．用户级线程间的切换比内核级线程间的切换效率高D．用户级线程可以在不支持内核级线程的操作系统上实现24．下列选项中，可能会将进程唤醒的事件是。I．I/O结束II．某进程退出临界区III．当前进程的时间片用完A．仅IB．仅IIIC．仅I、IID．I、II、III25．下列关于系统调用的叙述中，正确的是。I．在执行系统调用服务程序的过程中，CPU处于内核态II．操作系统通过提供系统调用避免用户程序直接访问外设·4·III．不同的操作系统为应用程序提供了统一的系统调用接口IV．系统调用是操作系统内核为应用程序提供服务的接口A．仅I、IVB．仅II、IIIC．仅I、II、IVD．仅I、III、IV26.下列选项中，可用于文件系统管理空闲磁盘块的数据结构是。I．位图II．索引结点III．空闲磁盘块链IV．文件分配表（FAT）A．仅I、IIB．仅I、III、IVC．仅I、IIID．仅II、III、IV27．系统采用二级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2。若当前Q1、Q2为空，系统依次创建进程P1、P2后即开始进程调度，P1、P2需要的CPU时间分别为30ms和20ms，则进程P1、P2在系统中的平均等待时间为。A．25msB．20msC．15msD．10ms28．在分段存储管理系统中，用共享段表描述所有被共享的段。若进程P1和P2共享段S，下列叙述中，错误的是。A．在物理内存中仅保存一份段S的内容B．段S在P1和P2中应该具有相同的段号C．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，则进程访问上述页的过程中，产生页置换的总次数是。A．3B．4C．5D．630．下列关于死锁的叙述中，正确的是。I．可以通过剥夺进程资源解除死锁II．死锁的预防方法能确保系统不发生死锁III．银行家算法可以判断系统是否处于死锁状态IV．当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态A．仅II、IIIB．仅I、II、IVC．仅I、II、IIID．仅I、III、IV31．某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：页目录号（10位）页号（10位）页内偏移（12位）虚拟地址20501225H对应的页目录号、页号分别是。A．081H、101HB．081H、401HC．201H、101HD．201H、401H32．在下列动态分区分配算法中，最容易产生内存碎片的是。A．首次适应算法B．最坏适应算法C．最佳适应算法D．循环首次适应算法33．OSI参考模型的第5层（自下而上）完成的主要功能是。A．差错控制B．路由选择C．会话管理D．数据表示转换34．100BaseT快速以太网使用的导向传输介质是。A．双绞线B．单模光纤C．多模光纤D．同轴电缆·5·35．对于滑动窗口协议，若分组序号采用3比特编号，发送窗口大小为5，则接收窗口最大是。A．2B．3C．4D．536．假设一个采用CSMA/CD协议的10Mb/s局域网，最小帧长是128B，则在一个冲突域内两个站点之间的单向传播延时最多是。A．2.56µsB．5.12µsC．10.24µsD．20.48µs37．若将101.200.16.0/20划分为5个子网，则可能的最小子网的可分配IP地址数是。A．126B．254C．510D．102238．某客户通过一个TCP连接向服务器发送数据的部分过程如题38图所示。客户在t0时刻第一次收到确认序列号ack_seq=100的段，并发送序列号seq=100的段，但发生丢失。若TCP支持快速重传，则客户重新发送seq=100段的时刻是。A．t1B．t2C．t3D．t4题38图39．若主机甲主动发起一个与主机乙的TCP连接，甲、乙选择的初始序列号分别为2018和2046，则第三次握手TCP段的确认序列号是。A．2018B．2019C．2046D．204740．下列关于网络应用模型的叙述中，错误的是。A．在P2P模型中，结点之间具有对等关系B．在客户/服务器（C/S）模型中，客户与客户之间可以直接通信C．在C/S模型中，主动发起通信的是客户，被动通信的是服务器D．在向多用户分发一个文件时，P2P模型通常比C/S模型所需的时间短二、综合应用题（第41～47小题，共70分）41．（13分）设线性表12321(,,,,,,)nnnLaaaaaa采用带头结点的单链表保存，链表中的结点定义如下：typedefstructnode·6·{intdata;structnode*next;}NODE；请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表12132(,,,,,,)nnnLaaaaaa。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++语