计算机专业(基础综合)模拟试卷115(题后含答案及解析)

计算机专业(基础综合)模拟试卷115(题后含答案及解析)一、单项选择题（共30小题，每小题2分，共60分）1.某算法的时间复杂度为T(n)A.OB.OC.OD.O2.设栈的输入序列为1,A.3B.4C.1D.23.在一个长度为n的循环队列中，若队头指针为`front`，队尾指针为`rear`，队列的最大容量为`MaxSize`，则判断队列为满的条件是（）。A.`front==rear`B.`(rear+1)%MaxSize==front`C.`rear==MaxSize`D.`front==(rear+1)%MaxSize`4.已知一棵完全二叉树有n个结点，则该二叉树的深度为（）。A.⌊B.⌊C.⌈D.⌈5.在图的最短路径算法中，Dijkstra算法要求图中边的权值（）。A.均为正数B.均为非负数C.可正可负D.均为整数6.下列排序算法中，在最坏情况下时间复杂度为O(nlA.快速排序B.归并排序C.堆排序D.冒泡排序7.在一棵度为3的树中，有3个度为1的结点，2个度为2的结点，1个度为3的结点，则该树中有多少个叶子结点？（）A.4B.5C.6D.78.哈希表解决冲突的常用方法有线性探测法、二次探测法等。对于线性探测法，当哈希表的装填因子为α时，查找成功的平均查找长度近似为（）。A.(B.C.1D.−9.计算机中，下列寻址方式中，执行速度最快的是（）。A.直接寻址B.间接寻址C.立即寻址D.寄存器寻址10.IEEE754单精度浮点数标准中，阶码采用偏移量为127的移码表示。若某浮点数的阶码二进制表示为10000001，则其实际阶码的十进制真值为（）。A.1B.2C.−D.12911.采用组相联映射方式的Cache中，主存物理地址分为（）。A.主存字块标记、组地址、块内地址B.主存字块标记、组地址、字地址C.区号、组号、块号、块内地址D.主存字块标记、Cache块地址、块内地址12.在计算机指令流水线中，解决数据相关问题的常用方法是（）。A.数据旁路技术B.延迟转移技术C.分支预测技术D.指令预取技术13.某总线在一个总线周期中并行传输4个字节的数据，总线频率为50MA.100B.150C.200D.40014.DMA数据传送方式的特点是（）。A.在DMA控制器接管总线控制权期间，CPU处于停止等待状态，不执行任何指令B.DMA方式主要用于主机与慢速外设之间的数据交换C.DMA方式在数据传输过程中不需要CPU干预，完全由硬件完成D.DMA方式在传送数据时，每一周期都需要CPU参与15.操作系统中，进程与程序的主要区别是（）。A.程序有状态而进程没有状态B.进程是动态的，程序是静态的C.进程只能在一个处理器上运行，程序可以在多个处理器上运行D.程序保存在内存中，进程保存在外存中16.在分页存储管理系统中，若页大小为4KB，逻辑地址为A.页号1，页内偏移0B.页号2，页内偏移0C.页号1，页内偏移0D.页号0，页内偏移017.某系统有同类资源m个，供n个进程共享。若每个进程最多申请k个资源，则系统不会发生死锁的条件是（）。A.nB.nC.nD.n18.文件系统中，设文件索引节点中有7个直接块指针，1个一级间接块指针，1个二级间接块指针。若每个磁盘块大小为4KB，指针占用A.4B.4C.40D.4019.在磁盘调度算法中，既考虑了寻道时间，又考虑了旋转延迟的算法是（）。A.先来先服务（FCFS）B.最短寻道时间优先（SSTF）C.扫描算法（SCAN）D.循环扫描算法（C-SCAN）20.TCP/IP参考模型中，网络层的核心协议是（）。A.TCPB.UDPC.IPD.HTTP21.香农定理指出，在有噪声的信道中，信道的极限数据传输速率C为（）。A.CB.CC.CD.C22.若某IPv4地址为3，其子网掩码为A.192.168B.192.168C.192.168D.192.16823.CSMA/CD协议中，二进制指数退避算法的目的是（）。A.减少冲突发生的概率B.避免冲突的发生C.检测冲突的发生D.保证数据包的顺序传输24.在TCP数据传输中，如果接收方通告窗口大小为0，则发送方将（）。A.立即关闭连接B.停止发送数据，直到接收方通告窗口大小大于0C.继续发送数据，但每次只能发送一个字节D.采用慢开始算法降低发送速率25.下列协议中，使用UDP协议进行传输的是（）。A.HTTPB.SMTPC.DNSD.FTP二、填空题（共10小题，每小题2分，共20分）1.数据结构中，逻辑结构分为线性结构和非线性结构，树和图都属于________结构。2.一个有n个顶点、e条边的连通无向图，若采用邻接矩阵存储，则其深度优先遍历的时间复杂度为________。3.在计算机中，一个16位无符号整数的表示范围是0到________。4.Cache的地址映射方式有直接映射、全相联映射和________映射。5.CPU在响应中断时，必须保护好断点地址和________，然后跳转到中断服务程序执行。6.在虚拟页式存储管理中，当发生缺页中断时，如果内存中没有空闲物理块，操作系统必须调用页面________算法来淘汰页面。7.在操作系统中，信号量的初值为5，经过多次P、V操作后，信号量的值变为−38.计算机网络中，物理层的主要任务是确定与传输媒体接口有关的一些特性，如机械特性、电气特性、功能特性和________特性。9.香农定理和奈奎斯特定理分别从带宽和________两个方面限制了信道的数据传输速率。10.以太网帧的最小长度为________字节，设置最小帧长的目的是为了保证发送端在发送过程中能够检测到冲突。三、简答题（共4小题，每小题5分，共20分）1.简述进程与线程的区别与联系。2.简述TCP三次握手的过程，并说明为什么不能采用两次握手。3.简述快速排序的基本思想，并给出其在最坏情况下的时间复杂度及产生最坏情况的原因。4.简述DMA方式与中断方式的区别。四、计算题与设计题（共3小题，每小题10分，共30分）1.（数据结构）给定一组权值W=2.（计算机组成原理）某计算机主存容量为256MB，Cache容量为512KB，主存块大小为3.（操作系统）某系统有A,B,C三类资源，当前系统状态如下表所示。系统是否处于安全状态？请写出详细的分析过程。如果此时进程进程Allocation(A,B,C)Max(A,B,C)Available(A,B,C)$P_0$$0,1,0$$7,5,3$$3,3,2$$P_1$$2,0,0$$3,2,2$$P_2$$3,0,2$$9,0,2$$P_3$$2,1,1$$2,2,2$$P_4$$0,0,2$$4,3,3$一、单项选择题答案及解析1.【答案】C【解析】递推关系式T(n)=T2.【答案】B【解析】栈的特点是后进先出。对于选项B，若输出为4，说明1,2,3,4全部入栈；输出4后栈顶为3，下一个输出的只能是3.【答案】B【解析】在循环队列中，为了区分队空和队满，通常会牺牲一个存储单元。队空的判断条件是`front==rear`；队满的判断条件是尾指针再加1后等于头指针，即`(rear+1)%MaxSize==front`。4.【答案】A【解析】完全二叉树深度为h，其结点数n满足≤n≤−1。解得≤n<，两边取对数得5.【答案】B【解析】Dijkstra算法基于贪心策略，每一步都选择当前距离最短的顶点，并对其邻接边进行松弛操作。如果图中存在负权边，可能导致后续找到的路径具有更小的权值，破坏了贪心选择的最优子结构，从而导致错误结果。因此要求权值非负。6.【答案】C【解析】快速排序最坏时间复杂度为O()；归并排序时间复杂度为O(nlog7.【答案】D【解析】树的总结点数n等于所有度数之和加1。n=3×1+2×2+8.【答案】A【解析】对于线性探测法处理冲突的哈希表，查找成功时的平均查找长度（ASL）的近似公式为(1+)9.【答案】C【解析】立即寻址不需要访问内存获取操作数，操作数直接包含在指令中，在取指令阶段即获得，因此执行速度最快。寄存器寻址也需要在指令执行阶段访问寄存器。10.【答案】B【解析】IEEE754单精度浮点数阶码占用8位，采用偏移量为127的移码（实际为减去127）。移码的二进制表示为10000001，对应的十进制数为129。实际阶码E=11.【答案】A【解析】在组相联映射中，主存物理地址被划分为三部分：主存字块标记、组地址和块内地址。Cache的组地址直接对应主存地址中的组地址字段，而主存字块标记用于判断是否命中。12.【答案】A【解析】数据相关（数据冒险）是指流水线中后面的指令依赖于前面指令的执行结果。数据旁路技术（或转发技术）将前一条指令ALU的计算结果直接旁路给后一条指令的ALU输入端，而不必等待写回寄存器，从而解决数据相关带来的停顿问题。13.【答案】C【解析】总线带宽=总线频率×每个周期传输的字节数=5014.【答案】C【解析】DMA（直接存储器存取）方式用于高速外设与内存之间的大批量数据传输。在传输前和传输后需要CPU干预，但在数据传输过程中，由DMA控制器接管总线控制权，完全由硬件完成，CPU不参与周期性干预。15.【答案】B【解析】程序是静态的指令和数据的集合，而进程是程序在计算机上的一次动态执行过程。进程具有生命周期和状态变化，程序没有。进程是系统进行资源分配和调度的独立单位。16.【答案】A【解析】页大小为4KB=4096B=0x1000B，因此页内偏移量占17.【答案】A【解析】避免死锁的条件是：最坏情况下，所有进程都已经获得了最大需求减1的资源，此时只要系统再多出一个资源，就能满足某个进程运行完毕并释放资源。因此需要满足n(18.【答案】B【解析】直接块有7×4KB=28KB。一级间接块指针指向一个磁盘块，该块存放4KB/4B=1024个指针，故一级间接表示1024×4KB=4MB。二级间接块存放1024×102419.【答案】D【解析】通常的磁盘调度算法（FCFS,SSTF,SCAN等）只考虑了寻道时间，但基于旋转位置的优化调度（如最短定位时间优先SPTF）或者某些系统增强版的循环扫描算法（考虑了扇区旋转的C-SCAN/LOOK）会兼顾旋转延迟。但在标准操作系统的基本考题中，SCAN和C-SCAN虽然主要优化寻道，但更细致的调度，比如考虑当前扇区位置的最短时间优先算法会兼顾旋转延迟。若按教材最严格分类，这里考查的是能够改善读写性能的算法综合。但在部分教材中，C-SCAN在某些实现中被认为涉及旋转优化。更好的解释是早期的FCFS、SSTF只看寻道距离。因此选择C-SCAN或SCAN，但鉴于题目给出循环扫描算法，其单向移动特性使得磁盘旋转与磁头移动在某种程度上的协同更平滑。注意，标准教材中只有涉及到特定旋转调度算法时才计算旋转延迟，这里题目可能更偏向于对C-SCAN的考察，选D。实际上，如果选项中有SLTF（最短定位时间优先）最合适，但这里没有。根据一般考研大纲对磁盘调度的定义，可能题意指代某些涉及整体延迟优化的算法。本题选D或C，更准确的是D（由于涉及回到起点，等待磁头，此时可能伴随旋转优化）。暂定D。20.【答案】C【解析】TCP/IP参考模型分为应用层、传输层、网际层（网络层）和网络接口层。网络层的核心协议是IP协议（网际协议），负责将数据报从源主机送到目的主机。21.【答案】A【解析】香农定理给出了在有噪声信道中，信道带宽为W，信号功率为S，噪声功率为N时的极限数据传输速率：C=22.【答案】B【解析】子网掩码24的最后一段224的二进制为11100000，即主机位占5位。IP地址3的二进制为00100001。将IP与掩码做与运算，最后一段23.【答案】A【解析】CSMA/CD网络中，发生冲突后，适配器会执行截断二进制指数退避算法，通过随机等待一段时间来减少再次冲突的概率。它不能避免冲突（只能减少概率），冲突检测是由硬件冲突检测电路完成的。24.【答案】B【解析】TCP使用滑动窗口进行流量控制。如果接收方通告窗口为0，表示接收缓存已满，发送方必须停止发送数据，直到收到接收方发送的窗口更新报文段（通告窗口大于0）。为防止该报文丢失导致死锁，发送方通常发送零窗口探测报文。25.【答案】C【解析】DNS在进行域名解析时主要使用UDP协议以降低开销和提高响应速度。HTTP、SMTP和FTP均使用可靠的TCP协议进行传输。虽然DNS在某些情况下（如区域传送）也使用TCP，但通常的查询使用UDP。二、填空题答案及解析1.【答案】非线性【解析】数据结构按逻辑结构可分为线性结构和非线性结构。线性结构中元素是一对一的关系，而非线性结构中元素是一对多或多对多的关系。树是一对多，图是多对多，故均为非线性结构。2.【答案】O【解析】无向图采用邻接矩阵存储时，深度优先遍历（DFS）需要访问每个顶点，并查找每个顶点的所有邻接边。邻接矩阵是一个n×n的矩阵，查找每个顶点的邻接点需要遍历对应的一行，耗时O(n)3.【答案】65535或−【解析】16位无符号整数的范围是从0000000000000000到1111111111111111，对应的十进制为0到−14.【答案】组相联【解析】Cache地址映射方式主要有三种：直接映射（主存块只能映射到固定的Cache块）、全相联映射（主存块可以映射到任意Cache块）、组相联映射（主存块映射到固定的组，组内任意块）。5.【答案】程序状态字（PSW）/现场信息【解析】中断响应时，硬件自动保存断点地址（PC）和程序状态字（PSW）到堆栈中，以保证中断返回时能恢复原来的执行状态和程序流。6.【答案】置换【解析】当发生缺页中断且内存没有空闲物理块时，操作系统需要采用页面置换算法（如FIFO、LRU、LFU等）选择一个页面调出内存，以便将所需页面调入。7.【答案】3【解析】信号量S的初值为5，表示系统原有5个资源。当S<0时，|S|表示等待该资源的进程数。此时8.【答案】过程（或规程）【解析】物理层接口规范主要包括四个特性：机械特性（接线器形状、尺寸等）、电气特性（电压范围等）、功能特性（引脚功能分配）和过程特性（规程特性，指明不同功能出现的顺序）。9.【答案】信噪比【解析】奈奎斯特定理给出了在无噪声理想信道中，带宽与最大数据传输速率的关系；而香农定理给出了在有噪声的实际信道中，带宽和信噪比共同决定的最大数据传输速率。10.【答案】64【解析】以太网规定了最小帧长为64字节。如果发送的数据不足64字节，需要填充至64字节。设置最小帧长是为了确保发送端在发送完整个帧之前能够检测到可能发生的冲突，因为以太网的争用期为51.2μs，在此期间可发送512比特即三、简答题答案及解析1.【答案】区别与联系如下：（1）区别：a.资源分配：进程是操作系统进行资源分配和保护的基本单位，拥有独立的地址空间和系统资源；线程是进程内的一个执行实体，不拥有系统资源，仅共享其所属进程的资源。b.调度：在引入线程的操作系统中，线程是独立调度的基本单位，进程不再是调度的基本单位。c.系统开销：进程在创建、撤销和上下文切换时，涉及地址空间和环境的切换，系统开销大；线程在上述操作时，因为共享进程的地址空间，开销远小于进程。d.并发性：进程和线程都具有并发性，但线程的引入提高了系统的并发程度。（2）联系：a.线程是进程的一部分，一个进程可以包含多个线程。b.线程不能脱离进程独立存在，线程的生命周期与进程相关联。c.不同进程间的线程是相互独立的，而同一进程内的多个线程可以并发执行，并通过共享进程的内存空间直接通信。2.【答案】TCP三次握手过程如下：（1）第一次握手：客户端向服务器发送一个SYN报文段（SYN=1），并随机选择一个初始序号seq=x，进入SYN_SENT状态。（2）第二次握手：服务器收到SYN报文段后，同意建立连接，向客户端发送一个SYN和ACK报文段（SYN=1,ACK=1），确认号ack=x+1，同时随机选择自己的初始序号seq=y，进入SYN_RCVD状态。（3）第三次握手：客户端收到服务器的SYN+ACK报文段后，向服务器发送一个确认报文段（ACK=1），确认号ack=y+1，序号seq=x+1。发送完毕后，客户端和服务器均进入ESTABLISHED状态。不能采用两次握手的原因：主要是为了防止已失效的连接请求报文段突然又传送到了服务端，导致资源浪费。假设客户端发送了一个连接请求，但由于网络延迟长时间未到达，客户端超时后重新发送请求并建立连接传输数据后释放。此时之前那个失效的请求到达了服务器，如果是两次握手，服务器收到请求就会认为是新的连接请求，直接分配资源进入连接状态等待数据发送，而客户端并不会回应，服务器的资源将一直被占用导致死锁。采用三次握手，服务器在发送完确认后，还要等待客户端的二次确认，如果不收到客户端的确认，就不会真正建立连接，从而避免了上述问题。3.【答案】快速排序的基本思想：快速排序基于分治法。首先从待排序序列中选取一个元素作为基准（pivot）。然后将序列中所有比基准小的元素移到基准之前，比基准大的元素移到基准之后，这样基准就被放到了它最终排序后应该处于的位置。此时，整个序列被划分为两部分，基准前一部分均小于基准，后一部分均大于基准。接着，对这两部分子序列递归地进行快速排序，直到所有子序列长度为1，排序完成。最坏时间复杂度及原因：最坏时间复杂度为O(产生最坏情况的原因是划分极度不平衡。例如，当待排序序列已经有序（正序或逆序），且每次选择的基准为序列的第一个或最后一个元素时，每次划分只能将一个元素放到正确位置，另一个子序列长度为n−1。这样递归深度变为n，总的比较次数为n+4.【答案】区别如下：（1）数据传输控制方式：在中断方式下，外设与主机之间的数据传输由CPU执行中断服务程序来完成，CPU需要介入每一个数据的传输（如从外设端口读取数据到寄存器，再写入内存）；而在DMA方式下，数据传输完全由DMA控制器（DMAC）硬件控制，直接在外设和内存之间进行，不需要CPU干预。（2）CPU利用率：DMA方式下CPU在数据传输期间可以去执行其他任务（除了总线竞争时刻），而中断方式下CPU必须暂停当前任务转去处理数据传输，因此DMA方式的CPU利用率远高于中断方式。（3）响应时间：中断方式在一条指令执行完毕后才响应中断；DMA方式可以在机器周期（总线周期）结束时响应，响应时间更短，速度更快。（4）适用场景：中断方式适用于中低速外设的数据传输，如键盘、鼠标等；DMA方式适用于高速大批量数据传输的设备，如磁盘、网卡等。（5）异常处理能力：中断方式可以处理复杂的逻辑和异常事件；DMA方式仅负责简单的数据传送，不具备处理异常事件的能力。四、计算题与设计题答案及解析1.【答案】哈夫曼树的构造过程如下：已知权值集合W=2,（1）选出权值最小的两个结点2和3，构造一个新结点，其权值为2+3=5。将2,3（2）从剩余集合中选出权值最小的两个结点4和5，构造新结点，权值为4+5=9（3）选出权值最小的两个结点7和8，构造新结点，权值为7+8=15（4）选出权值最小的两个结点9和9，构造新结点，权值为9+9=18（5）最后将15和