考研计算机学科专业基础综合模拟试题及答案解析

考研计算机学科专业基础综合模拟试题及答案解析(14)一、单项选择题：第1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1.下列关于数据结构的叙述中，错误的是A.数据的逻辑结构与数据在计算机中的存储方式无关B.数据的物理结构是指数据在计算机内的存储方式，又称存储结构C.算法的时间复杂度取决于问题的规模和待处理数据的初始状态D.算法的空间复杂度只与算法本身设计的辅助空间有关，与输入规模无关2.设栈的输入序列为1,A.3B.5C.2D.13.已知一棵完全二叉树有N个结点，则该树的深度为（根结点位于第1层）A.⌊B.⌊C.⌈D.⌈4.在有向图的邻接矩阵存储中，第i行的非零元素个数为A.顶点i的度B.顶点i的入度C.顶点i的出度D.顶点i的关联边数5.下列关于树与二叉树的叙述中，正确的是A.二叉树就是度为2的树B.哈夫曼树中没有度为1的结点C.在二叉排序树中，根结点的值一定是树中最大的D.将森林转换为二叉树后，第一棵树的所有结点均在二叉树的左子树上6.对有n个顶点、e条边的连通图采用邻接矩阵进行深度优先遍历，其时间复杂度为A.OB.OC.OD.O7.下列关于散列表的说法中，正确的是A.散列函数构造得越复杂，冲突的概率越低B.装填因子α越小，发生冲突的概率不一定越低C.采用线性探测法处理冲突时，同义词在散列表中必定相邻D.采用链地址法处理冲突时，查找一个元素的平均查找长度与装填因子成正比8.下列排序算法中，在最坏情况下时间复杂度为O(nlA.快速排序B.归并排序C.堆排序D.简单选择排序9.下列关于线程的描述中，错误的是A.线程是处理机调度的基本单位B.线程自己不拥有系统资源C.同一进程内的线程切换不会引起进程切换D.线程的创建和撤销所需的系统开销比进程大10.某计算机主存按字节编址，主存地址为32位，采用页式虚拟存储管理，页大小为4KB。若页表项大小为A.1B.2C.4D.811.假设某系统中有同类资源m个，可被n个进程共享，每个进程最多申请k个该类资源。为使系统不会发生死锁，m和n、k之间应满足的关系是A.mB.mC.mD.m12.下列关于设备分配的叙述中，正确的是A.独占设备可以采用时间片轮转方式进行分配B.SPOOLing技术的目的是提高共享设备的利用率C.SPOOLing系统将一台独占设备改造成多台虚拟设备D.采用SPOOLing技术后，用户进程可以直接独占设备13.浮点数加减运算中的对阶操作是指A.小阶向大阶对齐，尾数右移B.大阶向小阶对齐，尾数右移C.小阶向大阶对齐，尾数左移D.大阶向小阶对齐，尾数左移14.某机器字长8位，采用补码表示。已知[X=11101111A.−B.−C.17D.1515.某同步总线采用并行传输，总线时钟频率为50MHzA.100B.200C.400D.80016.下列关于指令寻址方式的叙述中，错误的是A.变址寻址中，有效地址等于形式地址加上变址寄存器的内容B.基址寻址主要用于为程序或数据分配存储空间，其基址寄存器的内容通常由操作系统管理C.相对寻址中，有效地址等于程序计数器PC的内容加上指令中的形式地址D.间接寻址不需要访存即可取得操作数17.在微程序控制器中，机器指令与微指令的关系是A.每一条机器指令由一条微指令解释执行B.每一条机器指令由一段微程序解释执行C.每一条机器指令由一个微程序解释执行，且微程序中只包含一条微指令D.微指令直接由硬件执行，与机器指令无关18.采用组相联映射方式的Cache中，主存地址划分为A.主存字块标记、组地址、块内地址B.主存字块标记、行地址、块内地址C.区号、组号、块号、块内地址D.主存字块标记、组内块号、块内地址19.下列关于I/O方式的叙述中，正确的是A.程序查询方式下，CPU与外设并行工作B.程序中断方式下，中断响应优先级总是高于中断处理优先级C.DMA方式下，数据传输以字为单位，完全由CPU控制D.DMA方式的响应时间通常比程序中断方式的响应时间短20.下列关于TCP/IP参考模型的描述中，错误的是A.网络接口层对应OSI参考模型的物理层和数据链路层B.网际层提供无连接、不可靠的数据报传输服务C.传输层提供端到端的可靠或不可靠数据传输服务D.应用层不仅包含应用层协议，还包含表示层和会话层部分功能21.若某信道无噪声且带宽为4kHzA.16B.32C.8D.6422.下列关于CSMA/CD协议的叙述中，正确的是A.适用于无线局域网B.站点在发送数据前先检测信道，发送过程中不需要检测C.采用截断二进制指数退避算法解决冲突问题D.最小帧长度的设定是为了保证发送站点能够在发送完毕前检测到冲突23.某路由器接收到一个目的IP地址为172.16.17.5的IP数据报。若路由表中有四条路由条目：172.16.0.0/16、A.172.16B.172.16C.172.16D.172.1624.在TCP连接建立过程中，如果主机A向主机B发送SYN报文段，其中序号seq=A.xB.xC.xD.x25.下列网络设备中，能够隔离广播域的是A.集线器B.交换机C.路由器D.网桥26.下列关于IPv4与IPv6的比较，正确的是A.IPv4的首部长度固定，IPv6的首部长度可变B.IPv4支持IPSec，IPv6不支持IPSecC.IPv6的地址空间是IPv4地址空间的倍D.IPv6采用了16字节的地址表示法27.某文件系统采用链式分配方式存储文件。若磁盘块大小为4KB，文件大小为A.4次，4次B.4次，3次C.3次，4次D.3次，3次28.在请求分页存储管理中，若采用LRU页面置换算法，且系统分配给某进程的物理块数为3。进程访问页面的序列为1,A.7B.8C.9D.1029.下列关于进程同步与互斥的叙述中，正确的是A.信号量的初值只能为0或1B.管程的引入主要是为了解决信号量机制中大量P、V操作分散带来的编程困难C.在记录型信号量机制中，当S.vaD.P操作和V操作可以被中断30.下列算法中，不属于磁盘调度算法的是A.电梯调度算法B.最短寻道时间优先算法C.时间片轮转算法D.循环扫描算法31.下列关于虚拟存储器的叙述中，错误的是A.虚拟存储器的大小受计算机系统地址位数的限制B.虚拟存储器的实现对程序员是透明的，但需要硬件和操作系统的支持C.虚拟存储器利用了局部性原理D.虚拟存储器的实际运行速度接近于主存，但其容量受外存容量的限制32.某计算机采用多级中断系统，在保护现场和恢复现场的过程中A.保护现场必须关中断，恢复现场也必须关中断B.保护现场必须关中断，恢复现场可以开中断C.保护现场可以开中断，恢复现场必须关中断D.保护现场和恢复现场都可以开中断33.在TCP/IP协议栈中，ARP协议的主要作用是A.将IP地址解析为MAC地址B.将MAC地址解析为IP地址C.将域名解析为IP地址D.将IP地址解析为域名34.下列关于数据链路层差错控制的叙述中，正确的是A.CRC校验可以纠正错误B.海明码可以纠正双比特错误C.奇偶校验码能够检测出所有偶数个比特错误D.CRC校验码的生成和检验均由硬件完成，不能由软件实现35.一台主机的IP地址为192.168.1A.30B.31C.32D.1436.若一棵m阶B树中，根结点最多有m棵子树，则关于该B树的描述中，正确的是A.根结点至少有两个子树B.每个结点至少有⌈mC.所有叶子结点均在同一层D.插入关键字时，若结点满则先分裂后插入37.下列关于红黑树的叙述中，错误的是A.红黑树是一棵二叉搜索树B.红黑树的每个结点是红色或黑色C.从任一结点到其每个叶子结点的所有简单路径都包含相同数目的红色结点D.红黑树的插入和删除操作的时间复杂度均为O38.下列指令中，不影响标志寄存器状态标志位的是A.ADDB.SUBC.INCD.CMP39.在指令流水线中，下列解决数据冒险的方法中，硬件开销最大但效率最高的是A.插入停顿周期B.编译器插入空操作指令C.数据旁路技术D.分支预测技术40.下列关于DNS系统的描述中，错误的是A.DNS服务器采用层次式的树状结构B.DNS查询分为递归查询和迭代查询C.本地域名服务器通常采用迭代查询D.域名解析过程中，主机向本地域名服务器的查询一般是递归的二、综合应用题：第41~47题，共70分。41.（15分）已知一棵二叉树的先序遍历序列为A,B,（1）请画出该二叉树的树形结构图。（5分）（2）写出该二叉树的后序遍历序列。（5分）（3）若将该二叉树转换为对应的森林，请画出转换后的森林结构图，并指出该森林由几棵树组成。（5分）42.（8分）给定一个无序数组A=（1）以第一个元素49为基准，写出快速排序算法在第一趟划分过程中的数组元素变化情况（要求显示出指针移动和元素交换的详细步骤）。（4分）（2）设计一个时间复杂度为O(n)43.（9分）某计算机主存按字节编址，地址空间为32MB。Cache采用组相联映射方式，Cache数据区容量为64KB，主存块大小为0x0000000,0x0000040,0x0000080,0x（1）主存地址和Cache地址各为多少位？主存地址如何划分？给出各字段的位数。（3分）（2）若Cache采用LRU替换算法，请分析上述访问序列在Cache中的命中情况，计算命中率。（3分）（3）若将映射方式改为直接映射，其他条件不变，分析上述访问序列在Cache中的命中情况，并比较组相联映射与直接映射在此场景下的优劣。（3分）44.（14分）某计算机字长为16位，采用补码定点小数表示，其中阶符和数符各占1位，阶码部分占5位（采用整数补码表示），尾数部分占9位（不含符号位）。已知X=,Y（1）将X和Y转换为二进制浮点数表示，要求尾数部分采用补码表示且为规格化形式，阶码采用补码表示。（5分）（2）按照浮点数加减法的步骤（对阶、尾数求和、规格化、舍入、溢出判断），计算X+45.（7分）某系统中有四个进程,,,和三类资源A,进程的最大需求向量为(3,2,进程的最大需求向量为(6,1,进程的最大需求向量为(3,1,进程的最大需求向量为(4,2,假设系统当前可用资源向量为(1（1）计算各进程的尚需资源向量，并写出时刻的工作向量W和完成向量Fin（2）利用银行家算法判断时刻系统是否处于安全状态，若安全，给出安全序列；若不安全，说明理由。（5分）46.（8分）某文件系统采用多级索引结构，磁盘盘块大小为1KB。每个inode包含10个直接块指针、1个一级间接块指针、1个二级间接块指针和1个三级间接块指针。盘块号占（1）计算该文件系统中文件的最大长度（以GB为单位，保留小数）。（4分）（2）若进程需要读取某文件偏移量为20500B47.（9分）某网络拓扑结构如下：主机连接到交换机的端口1，主机连接到交换机的端口2，交换机通过端口3连接到路由器，路由器通过另一接口连接到互联网。主机的IP地址为192.168.1.10/24，网关为192.168.1.1；主机的IP地址为192.168.1.20/24，网关为192.168.1.1。路由器连接内网的接口IP地址为（1）主机要向主机发送一个IP数据报。在发送的数据帧中，源MAC地址和目的MAC地址分别是什么？（2分）（2）若交换机初始MAC地址表为空，请详细描述到的数据帧传输过程中，交换机的学习与转发过程。（3分）（3）若主机要访问互联网上的服务器（公网IP为8.8.8.8），在发送的数据帧中，目的MAC地址是什么？在经过路由器转发后的数据帧中，源MAC和目的MAC分别是谁？（假设路由器到下一跳路由器的链路为以太网，且已知下一跳路由器的MAC地址为，路由器内网接口MAC为，外网接口MAC为）。（4分）三、答案与解析一、单项选择题1.【答案】D【解析】算法的空间复杂度不仅与算法本身设计的辅助空间有关，还可能受到输入数据规模的影响。例如，若算法需要根据输入规模n动态分配大小为n的数组作为辅助空间，则空间复杂度与输入规模有关。其他选项描述均正确。2.【答案】C【解析】栈的特点是后进先出。对于选项C：输入1,2,3,4,5。若输出为2,3.【答案】A【解析】完全二叉树深度为h，结点数为N。根据完全二叉树的性质，深度为h−1的满二叉树结点数为−1，深度为h的满二叉树结点数为−1。所以−1<N4.【答案】C【解析】在有向图的邻接矩阵中，行表示顶点的出边，列表示顶点的入边。第i行的非零元素表示从顶点i出发的边，因此其个数等于顶点i的出度。5.【答案】B【解析】哈夫曼树在构造过程中每次选取两棵子树合并，因此不存在度为1的结点。二叉树可以是空树或只有一个结点，度为2的树至少有3个结点；二叉排序树的中序遍历才是有序的，根结点的值不一定最大；森林转二叉树后，第一棵树的根作为二叉树的根，第一棵树的子树作为二叉树的左子树，其余树的根作为右子树链。6.【答案】C【解析】采用邻接矩阵存储图，深度优先遍历需要访问矩阵的每一行每一列，因此时间复杂度与顶点数n相关，为O()，与边数7.【答案】D【解析】采用链地址法处理冲突时，查找长度与装填因子α呈正比线性关系，即ASL≈8.【答案】C【解析】快速排序最坏时间复杂度为O()，空间复杂度O(lon)；归并排序时间复杂度最坏为O(n9.【答案】D【解析】线程是轻量级进程，其创建和撤销的系统开销比进程小。选项D描述错误，符合题意。10.【答案】A【解析】页大小为4KB=B，主存地址32位，故页内偏移占12位，虚页号占20位。页表项大小为4B，则每页可容纳411.【答案】B【解析】为防止死锁，最极端的情况是所有n个进程都获得了k−1个资源，此时系统中剩余资源数m−12.【答案】C【解析】SPOOLing技术通过共享设备模拟独占设备，将一台独占设备改造成多台虚拟设备，从而提高系统吞吐量和设备利用率。独占设备不能采用时间片轮转方式，选项A错误。13.【答案】A【解析】浮点数加减运算对阶的原则是“小阶向大阶看齐”。小阶向大阶对齐时，需要将小阶的尾数向右移位，每右移一位，阶码加1，直到两阶码相等。14.【答案】A【解析】补码11101111最高位为1，表示负数。求其原码：符号位不变，数值位按位取反加1，得到10010001。转换为十进制为−115.【答案】B【解析】总线时钟频率为50MHz，宽度为32bi16.【答案】D【解析】间接寻址需要访问内存获取有效地址，随后再访问内存获取操作数，因此间接寻址至少需要两次访存。选项D错误。17.【答案】B【解析】在微程序控制器中，每一条机器指令对应一段微程序，微程序由若干条微指令组成，微指令解释执行机器指令。18.【答案】A【解析】组相联映射将主存地址分为三部分：主存字块标记、组地址和块内地址。主存块被映射到特定的组，组内可以进行全相联映射。19.【答案】D【解析】DMA响应发生在总线周期结束后，而中断响应发生在当前指令周期结束后。指令周期通常长于总线周期，因此DMA的响应时间通常比程序中断方式短。程序查询方式下CPU与外设串行工作。20.【答案】A【解析】TCP/IP的网络接口层并没有明确划分具体的协议，它对应OSI参考模型的物理层和数据链路层，但TCP/IP并没有定义这两层的具体实现，而是直接使用现成的网络硬件和协议。A描述在标准上存在争议，但较常见的说法是网络接口层对应OSI的物理层和数据链路层。更明显的错误可能在于其他选项。重新审视：D应用层不仅包含应用层，也包含了OSI表示层和会话层功能。A是对的。选A。（注意：有时教材认为网络接口层涵盖了这两层，本题没有其他选项更明显错误，实际此题A选项在教材中通常被接受为正确。但有些考题会将A设计为错误，因为网络接口层本身并没有定义物理层。如果遵循谢希仁教材，网络接口层对应OSI的物理层和数据链路层。那么选A。但若出题人意图为网络接口层不等于物理层，则另当别论。暂视为无争议题目。）然而，此处需仔细考察，通常TCP/IP的应用层确实包含了表示层和会话层的功能。若选错误项，选A不合适。其实，D选项描述是正确的。A选项也是通常接受的描述。等等，OSI有七层，TCP/IP四层。网络接口层对应物理层和数据链路层，是对的。是不是A选项说“网络接口层对应物理层和数据链路层”有瑕疵？实际上TCP/IP没有明确这两层。让我们重新看选项。D说包含了表示层和会话层部分功能，是对的。A错在TCP/IP并未定义物理层和网络接口层细节。故选A可能。为严谨，此处保留。21.【答案】B【解析】奈氏准则：最大数据传输率=2W22.【答案】D【解析】CSMA/CD适用于总线型或星型拓扑的有线局域网。站点在发送前和发送中都必须检测信道。采用截断二进制指数退避算法。最小帧长=争用期×数据传输率，以确保发送站点在发送完毕前能检测到冲突。选项D正确。23.【答案】D【解析】最长前缀匹配原则。将四个路由条目与目标IP172.16.17.5匹配。172.16.0.0/16匹配16位；24.【答案】B【解析】TCP三次握手中，主机B收到序号seq=x的SYN报文段，返回的SYN+ACK报文段中，确认号25.【答案】C【解析】路由器工作在网络层，能够隔离广播域。集线器、交换机和网桥工作在物理层或数据链路层，只能隔离冲突域，不能隔离广播域。26.【答案】C【解析】IPv6地址为128位（16字节），IPv4为32位。/=，即IPv6地址空间是IPv4的倍。IPv6基本首部长度固定为40B，IPv4首部长度可变。27.【答案】B【解析】文件大小15KB，磁盘块4K28.【答案】D【解析】使用LRU，物理块数为3。序列：1(缺),2(缺),3(缺),4(缺，替换1),1(缺，替换2),2(缺，替换3),5(缺，替换4),1(命中),2(命中),3(缺，替换5),4(缺，替换1),5(缺，替换2)。缺页次数统计：1,2,3,4,1,2,5,3,4,5，共10次缺页。选项D正确。29.【答案】B【解析】管程的引入是为了解决信号量机制中P、V操作分散、易出错的问题，管程将共享变量及对变量的操作封装起来。信号量初值可大于1。选项C错误，绝对值表示等待该资源的进程数。选项D错误，P、V操作是原语，不可中断。30.【答案】C【解析】时间片轮转算法是处理机调度算法，不是磁盘调度算法。31.【答案】B【解析】虚拟存储器的实现需要硬件（如MMU、页表机制）和操作系统（如请求调页、页面置换）的共同支持。但是，虚拟存储器的实现对程序员并不是完全透明的，在某些系统编程或性能优化场景下，程序员需要了解页大小、TLB等机制。通常操作系统教材中说虚拟存储器对应用程序员透明，但如果选项B说“对程序员透明”，则过于绝对，且虚拟存储器的容量受外存和地址位数共同限制。B错。32.【答案】C【解析】在保护现场和恢复现场时，通常要求中断处理过程不被打断。但现在的计算机中，保护现场通常由硬件完成，如果是软件保护现场，需要关中断；恢复现场时，必须关中断，恢复完成后再开中断。选项C更符合传统计算机组成原理教材的描述。33.【答案】A【解析】ARP协议工作在数据链路层和网络层边界，主要用于将IP地址解析为MAC地址。34.【答案】C【解析】奇偶校验码只能检测奇数个比特错误，无法纠正错误。C