.wd.2019年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业根基综合试题一、单项选择题：140小题，每题2分，共80分。以下每题给出的四个选项中，只有一个选项符合试题要求。1.设n是描述问题规模的非负整数，以下程序段的时间复杂度是x=0；while(n=(x+l)*(x+l)x=x+l；A. O(log n)B. O(n1/2)C. O(n)D. O(n2)2.假设将一棵树T转化为对应的二又树BT，则以下对BT的遍历中，其遍历序列与T的后根遍历序列一样的是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历3.对n个互不一样的符号进展哈夫曼编码。假设生成的哈夫曼树共有115个结点，则n的值是A. 56 B. 57 C. 58 D. 604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。以下关于T1与T3的表达中，正确的选项是I.假设v是T1的叶结点，则T1与T3可能不一样.假设v不是T1的叶结点，则T1与T3一定不一样.假设v不是T1的叶结点，则T1与T3一定一样A. 仅I B. 仅II C. 仅I、 D. 仅I、5.以以下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开场时间和最迟开场时间分别是A. 3和7B. 12和12C. 12和14D. 15和156.用有向无环图描述表达式(x+y)*(x+y)/x)，需要的顶点个数至少是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，以下因素中，还需要考虑的是I.数据的规模.数据的存储方式.算法的稳定性V.数据的初始状态A. 仅B. 仅I、C. 仅、IVD. I、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. 1 B. 2 C. 3 D. 412. 以下关于冯诺依曼构造计算机 根本思想的表达中，错误的选项是A. 程序的功能都通过中央处理器执行指令实现B. 指令和数据都用二进制表示，形式上无差异C. 指令按地址访问，数据都在指令中直接给出D. 程序执行前，指令和数据需预先存放在存储器中13. 考虑以下C语言代码：unsigned short usi=65535；short si=usi；执行上述程序段后，si的值是A. -1 B. -32767 C. -32768 D. -6553514. 以下关于缺页处理的表达中，错误的选项是A. 缺页是在地址转换时CPU检测到的一种异常B. 缺页处理由操作系统提供的缺页处理程序来完成C. 缺页处理程序根据页故障地址从外存读入所缺失的页D. 缺页处理完成后回到发生缺页的指令的下一条指令执行15. 某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234 FF00H，该操作数采用基址寻址方式，形式地址(用补码表示)为FF12H，基址存放器内容为F000 0000H，则该操作数的LSB(最低有效字节)所在的地址是A. F000 FF12H B. F000 FF15H C. EFFF FF12H D. EFFF FF15H16.以下有关处理器时钟脉冲信号的表达中，错误的选项是A. 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C. 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D. 处理器总是在每来一个时钟脉冲信号时就开场执行一条新的指令17.某指令功能为Rr2Rr1+MRr0，其两个源操作数分别采用存放器、存放器间接寻址方式。对于以下给定部件，该指令在取数及执行过程中需要用到的是I.通用存放器组(GPRs).算术逻辑单元(ALU).存储器(Memory).指令译码器(ID)A. 仅I、 B. 仅I、C. 仅、IV D. 仅I、18.在采用“取指、译码/取数、执行、访存、写回5段流水线的处理器中，执行如下指令序列，其中s0、s1、s2、s3和t2表示存放器编号。I1：add s2，s1，s0 /Rs2Rs1+Rs0I2：load s3，0(t2) /Rs3MRt2+0I3：add s2，s2 s3 /Rs2Rs2+Rs3I4：store s2，0(t2)/MRt2+0Rs2以下指令对中，不存在数据冒险的是A. I1和I3 B. I2和I3 C. I2和I4 D. I3和I419.假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总线的工作频率为1333MHz、总线宽度为64位，则存储器总线的总带宽大约是A. 10.66 GB/s B. 32 GB/s C. 64 GB/s D. 96 GB/s20.以下关于磁盘存储器的表达中，错误的选项是A. 磁盘的格式化容量比非格式化容量小B. 扇区中包含数据、地址和校验等信息C. 磁盘存储器的最小读写单位为一个字节D. 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成21. 某设备以中断方式与CPU进展数据交换，CPU主频为1 GHz，设备接口中的数据缓冲存放器为32位，设备的数据传输率为50kB/s。假设每次中断开销(包括中断响应和中断处理)为1000个时钟周期，则CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是A. 1.25%B. 2.5%C. 5%D. 12. 5%22. 以下关于DMA方式的表达中，正确的选项是I. DMA传送前由设备驱动程序设置传送参数II.数据传送前由DMA控制器请求总线使用权.数据传送由DMA控制器直接控制总线完成IV.DMA传送完毕后的处理由中断服务程序完成A. 仅I、B. 仅、C. 仅、IVD. I、IV23. 以下关于线程的描述中，错误的选项是A. 内核级线程的调度由操作系统完成B. 操作系统为每个用户级线程建设一个线程控制块C. 用户级线程间的切换比内核级线程间的切换效率高D. 用户级线程可以在不支持内核级线程的操作系统上实现24.以下选项中，可能将进程唤醒的事件是I.I/O完毕.某进程退出临界区.当前进程的时间片用完A. 仅IB. 仅C. 仅I、D. I、25.以下关于系统调用的表达中，正确的选项是I.在执行系统调用服务程序的过程中，CPU处于内核态.操作系统通过提供系统调用防止用户程序直接访问外设.不同的操作系统为应用程序提供了统一的系统调用接口IV.系统调用是操作系统内核为应用程序提供服务的接口A. 仅I、IV B. 仅II、IIIC. 仅I、IVD. 仅I、26.以下选项中，可用于文件系统管理空闲磁盘块的数据构造是I.位图.索引节点.空闲磁盘块链.文件分配表(FAT)A. 仅I、B. 仅、C. 仅l、 D. 仅、27.系统采用二级反响队列调度算法进展进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创立的进程首先进入Q1；Q1中的进程执行一个时间片后，假设未完毕，则转入Q2。假设当前Q1、Q2为空，系统依次创立进程Pl、P2后即开场进程调度Pl、P2需要的CPU时间分别为30ms和20ms，则进程P1、P2在系统中的平均等待时间为A. 25 ms B. 20 ms C. 15 ms D. 10 ms28.在分段存储管理系统中，用共享段表描述所有被共享的段。假设进程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. 3 B. 4 C. 5 D. 630.以下关于死锁的表达中，正确的选项是I.可以通过剥夺进程资源解除死锁II.死锁的预防方法能确保系统不发生死锁III.银行家算法可以判断系统是否处于死锁状态.当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态A. 仅II、 B. 仅I、C. 仅I、 D. 仅I、31. 某计算机主存按字节编址，采用二级分页存储管理，地址构造如下所示页目录号(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. 同轴电缆35.对于滑动窗口协议，如果分组序号采用3比特编号，发送窗口大小为5，则接收窗口最大是A. 2B. 3C. 4D. 536.假设一个采用CSMA/CD协议的100Mbps局域网，最小帧长是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时刻第一次收到确认序列号