计算机学科专业基础综合真题及答案.pdf

20192019 年全国硕士研究生招生考试年全国硕士研究生招生考试计算机科学与技术学科联考计算机科学与技术学科联考计算机学科专业基础综合试题计算机学科专业基础综合试题一、单项选择题：一、单项选择题：140140 小题，每小题小题，每小题2 2 分，共分，共8080 分下列每题给出的四个选项中，只有一个选项符合试题要分下列每题给出的四个选项中，只有一个选项符合试题要求1. 1.设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n=(x+l)*(x+l)x=x+l；A.A. O(log n)B.B. O(n1/2)C.C. O(n)D.D. O(n2)2. 2.若将一棵树 T 转化为对应的二又树BT，则下列对BT 的遍历中，其遍历序列与T 的后根遍历序列相同的是A.A. 先序遍历B.B. 中序遍历C.C. 后序遍历D.D. 按层遍历3. 3.对 n 个互不相同的符号进行哈夫曼编码若生成的哈夫曼树共有115 个结点，则 n 的值是A.A. 56B.B. 57C.C. 58D.D. 604. 4.在任意一棵非空平衡二又树(AVL 树)T1中，删除某结点 v 之后形成平衡二又树 T2，再将 w 插入 T2形成平衡二又树 T3。

下列关于 T1与 T3的叙述中，正确的是I.若 v 是 T1的叶结点，则 T1与 T3可能不相同.若 v 不是 T1的叶结点，则 T1与 T3一定不相同.若 v 不是 T1的叶结点，则 T1与 T3一定相同A.A. 仅 IB.B. 仅 IIC.C. 仅 I、D.D. 仅 I、5. 5.下图所示的 AOE 网表示一项包含 8 个活动的工程活动 d的最早开始时间和最迟开始时间分别是A.A. 3 和 7B.B. 12 和 12C.C. 12 和 14D.D. 15 和 156. 6.用有向无环图描述表达式(x+y)*(x+y)/x)，需要的顶点个数至少是A.A. 5B.B. 6C.C. 8D.D. 97. 7.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模.数据的存储方式.算法的稳定性V.数据的初始状态A.A. 仅B.B. 仅 I、C.C. 仅、IVD.D. I、8. 8.现有长度为 11 且初始为空的散列表 HT，散列函数是 H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列 87，40，30，6，11，22，98，20 依次插入到 HT 后，HT 查找失败的平均查找长度是A.A. 4B.B. 5.25C.C. 6D.D. 6.299. 9.设主串 T=“abaabaabcabaabc”，模式串 S=“abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A.A. 9B.B. 10C.C. 12D.D. 1510.10. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。

下列序列中，不可能是快速排序第二趟结果的是A.A. 5，2，16，12，28，60，32，72B.B. 2，16，5，28，12，60，32，72C.C. 2，12，16，5，28，32，72，60D.D. 5，2，12，28，16，32，72，6011.11. 设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是A.A. 1B.B. 2C.C. 3D.D. 412.12. 下列关于冯诺依曼结构计算机基本思想的叙述中，错误的是A.A. 程序的功能都通过中央处理器执行指令实现B.B. 指令和数据都用二进制表示，形式上无差别C.C. 指令按地址访问，数据都在指令中直接给出D.D. 程序执行前，指令和数据需预先存放在存储器中欢迎下载13.13. 考虑以下 C 语言代码：unsigned short usi=65535；short si=usi；执行上述程序段后，si 的值是A.A. -1B.B. -32767C.C. -32768D.D. -6553514.14. 下列关于缺页处理的叙述中，错误的是A.A. 缺页是在地址转换时CPU 检测到的一种异常B.B. 缺页处理由操作系统提供的缺页处理程序来完成C.C. 缺页处理程序根据页故障地址从外存读入所缺失的页D.D. 缺页处理完成后回到发生缺页的指令的下一条指令执行15.15. 某计算机采用大端方式，按字节编址。

某指令中操作数的机器数为1234 FF00H，该操作数采用基址寻址方式，形式地址(用补码表示)为 FF12H，基址寄存器内容为 F000 0000H，则该操作数的 LSB(最低有效字节)所在的地址是A.A. F000 FF12HB.B. F000 FF15HC.C. EFFF FF12HD.D. EFFF FF15H16.16. 下列有关处理器时钟脉冲信号的叙述中，错误的是A.A. 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成B.B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C.C. 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D.D. 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令17.17. 某指令功能为 Rr2Rr1+MRr0，其两个源操作数分别采用寄存器、 寄存器间接寻址方式对于下列给定部件，该指令在取数及执行过程中需要用到的是I.通用寄存器组(GPRs).算术逻辑单元(ALU).存储器(Memory).指令译码器(ID)A.A. 仅 I、B.B. 仅 I、C.C. 仅、IVD.D. 仅 I、18.18. 在采用“取指、译码/取数、执行、访存、写回”5 段流水线的处理器中，执行如下指令序列，其中s0、s1、s2、s3 和 t2 表示寄存器编号。

I1：add s2，s1，s0/Rs2Rs1+Rs0I2：load s3，0(t2)/Rs3MRt2+0I3：add s2，s2s3/Rs2Rs2+Rs3I4：store s2，0(t2)/MRt2+0Rs2下列指令对中，不存在数据冒险的是A.A. I1 和 I3B.B. I2 和 I3C.C. I2 和 I4D.D. I3 和 I419.19. 假定一台计算机采用 3 通道存储器总线，配套的内存条型号为 DDR3-1333，即内存条所接插的存储器总线的工作频率为 1333 MHz、总线宽度为 64 位，则存储器总线的总带宽大约是A. 10.A. 10. 66 GB/sB.B. 32 GB/sC.C. 64 GB/sD.D. 96 GB/s20.20. 下列关于磁盘存储器的叙述中，错误的是A.A. 磁盘的格式化容量比非格式化容量小B.B. 扇区中包含数据、地址和校验等信息C.C. 磁盘存储器的最小读写单位为一个字节D.D. 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成21.21. 某设备以中断方式与 CPU 进行数据交换，CPU 主频为 1 GHz，设备接口中的数据缓冲寄存器为 32 位，设备的数据传输率为 50kB/s。

若每次中断开销(包括中断响应和中断处理)为 1000 个时钟周期，则 CPU用于该设备输入/输出的时间占整个 CPU 时间的百分比最多是A.A. 1.25%B.B. 2.5%C.C. 5%D.D. 12. 5%22.22. 下列关于 DMA 方式的叙述中，正确的是I. DMA 传送前由设备驱动程序设置传送参数II.数据传送前由 DMA 控制器请求总线使用权.数据传送由 DMA 控制器直接控制总线完成IV.DMA传送结束后的处理由中断服务程序完成A.A. 仅 I、B.B. 仅、C.C. 仅、IVD.D. I、IV欢迎下载23.23. 下列关于线程的描述中，错误的是A.A. 内核级线程的调度由操作系统完成B.B. 操作系统为每个用户级线程建立一个线程控制块C.C. 用户级线程间的切换比内核级线程间的切换效率高D.D. 用户级线程可以在不支持内核级线程的操作系统上实现24.24. 下列选项中，可能将进程唤醒的事件是I. I/O 结束. 某进程退出临界区. 当前进程的时间片用完A.A. 仅 IB.B. 仅C.C. 仅 I、D.D. I、25.25. 下列关于系统调用的叙述中，正确的是I.在执行系统调用服务程序的过程中，CPU 处于内核态.操作系统通过提供系统调用避免用户程序直接访问外设.不同的操作系统为应用程序提供了统一的系统调用接口IV.系统调用是操作系统内核为应用程序提供服务的接口A.A. 仅 I、IVB.B. 仅 II、IIIC.C. 仅 I、IVD.D. 仅 I、26.26. 下列选项中，可用于文件系统管理空闲磁盘块的数据结构是I.位图.索引节点.空闲磁盘块链.文件分配表(FAT)A.A. 仅 I、B.B. 仅、C.C. 仅 l、D.D. 仅、27.27. 系统采用二级反馈队列调度算法进行进程调度。

就绪队列Q1 采用时间片轮转调度算法，时间片为10ms；就绪队列 Q2 采用短进程优先调度算法；系统优先调度Q1 队列中的进程，当Q1 为空时系统才会调度Q2中的进程；新创建的进程首先进入Q1；Q1 中的进程执行一个时间片后，若未结束，则转入Q2若当前Q1、 Q2 为空， 系统依次创建进程Pl、 P2 后即开始进程调度Pl、 P2 需要的 CPU 时间分别为 30ms 和 20ms，则进程 P1、P2 在系统中的平均等待时间为A.A. 25 msB.B. 20 msC.C. 15 msD.D. 10 ms28.28. 在分段存储管理系统中，用共享段表描述所有被共享的段若进程P1 和 P2 共享段 S，下列叙述中，错误的是A.A. 在物理内存中仅保存一份段S 的内容B.B. 段 S 在 P1 和 P2 中应该具有相同的段号C.C. P1 和 P2 共享段 S 在共享段表中的段表项D.D. P1 和 P2 都不再使用段 S 时才回收段 S 所占的内存空间29.29. 某系统采用 LRU 页置换算法和局部置换策略，若系统为进程P 预分配了 4 个页框，进程P 访问页号的序列为 0，1，2，7，0，5，3，5，0，2，7，6，则进程访问上述页的过程中，产生页置换的总次数是A.A. 3B.B. 4C.C. 5D.D. 630.30. 下列关于死锁的叙述中，正确的是I. 可以通过剥夺进程资源解除死锁II. 死锁的预防方法能确保系统不发生死锁III. 银行家算法可以判断系统是否处于死锁状态. 当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态A.A. 仅 II、B.B. 仅 I、C.C. 仅 I、D.D. 仅 I、31.31. 某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示页目录号(10 位)页号(10 位)页内偏移(12 位)虚拟地址 2050 1225H 对应的页目录号、页号分别是A.A. 081H、101HB.B. 081H、401HC.C. 201H、101HD.D. 201H、401H32.32. 在下列动态分区分配算法中，最容易产生内存碎片的是A.A. 首次适应算法B.B. 最坏适应算法C.C. 最佳适应算法D.D. 循环首次适应算法33.33. OSI 参考模型的第 5 层(自下而上)完成的主要功能是A.A. 差错控制B.B. 路由选择C.C. 会话管理D.D. 数据表示转换34.34. 100BaseT 快速以太网使用的导向传输介质是A.A. 双绞线B.B. 单模光纤C.C. 多模光纤D.D. 同轴电缆35.35. 对于滑动窗口协议，如果分组序号采用3 比特编号，发送窗口大小为5，则接收窗口最大是A.A. 2B.B. 3C.C. 4D.D. 5欢迎下载36.36. 假设一个采用 CSMA/CD 协议的 100Mbps 局域网， 最小帧长是 128 B， 则在一个冲突域内两个站点之间的单向传播延时最多是A.A. 2.56 sB.B. 5.12 sC.C. 10.24 sD.D. 20.48 s37.37. 若将 101.01. 200. 16.。