2026年计算机科学与技术专业必修课程考试试题及答案解析

2026年计算机科学与技术专业必修课程考试试题及答案解析一、单项选择题（本大题共20小题，每小题2分，共40分。在每小题给出的四个选项中，只有一项是符合题目要求的）1.在时间复杂度为O(A.直接插入排序B.快速排序C.冒泡排序D.简单选择排序2.若一棵二叉树具有n个节点，则其二叉链表存储结构中，空的指针域个数为（）。A.nB.nC.nD.23.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A.1/2B.1C.2D.44.操作系统中，负责对进程进行调度和分派的核心程序称为（）。A.进程控制块(PCB)B.作业调度程序C.进程调度程序D.设备驱动程序5.虚拟存储器的容量主要受（）的限制。A.物理内存大小B.辅存（外存）容量C.CPU地址空间大小D.数据总线宽度6.在TCP/IP参考模型中，负责端到端通信、提供可靠数据传输服务的是（）。A.网络接口层B.网际层C.传输层D.应用层7.假设某计算机的Cache容量为16KB，块大小为64B，主存容量为4MB，若采用直接映射方式，则主存地址中的标记字段占（）位。A.8B.10C.12D.148.下列关于死锁的必要条件中，可以通过破坏“循环等待”条件来预防死锁的策略是（）。A.静态分配所有资源B.释放进程占有的部分资源C.资源有序分配策略D.抢占资源9.IEEE754浮点数标准中，单精度浮点数（32位）的阶码采用移码表示，偏置值为（）。A.127B.128C.255D.25610.在OSI七层模型中，负责数据加密、解密和压缩的层是（）。A.表示层B.会话层C.传输层D.应用层11.设散列表长为14，散列函数H(A.2B.7C.9D.1012.若某进程在运行过程中因等待I/O操作而阻塞，则此时该进程的状态将从运行态变为（）。A.就绪态B.阻塞态C.挂起态D.终止态13.IP地址202.113.16.10属于（）类IP地址。A.A类B.B类C.C类D.D类14.补码定点整数加减运算中，发生溢出的判断条件是（）。A.最高位进位为1B.符号位进位为1C.双符号位不同D.最高位为115.下列排序算法中，不属于稳定排序的是（）。A.归并排序B.基数排序C.堆排序D.冒泡排序16.在分段存储管理系统中，逻辑地址到物理地址的映射是通过（）实现的。A.页表B.段表C.TLBD.快表17.CSMA/CD协议适用于（）。A.无线局域网B.总线型以太网C.令牌环网D.广域网18.相对于微程序控制器，硬布线控制器的优点是（）。A.指令执行速度快B.设计灵活C.易于修改和扩展功能D.规律性强19.在KMP算法中，next数组的作用是（）。A.记录模式串在主串中出现的位置B.记录模式串内部的最长公共前后缀C.记录主串的匹配进度D.记录模式串的长度20.DNS协议主要用于实现（）网络服务功能。A.域名到IP地址的解析B.IP地址到域名的解析C.邮件传输D.文件传输二、多项选择题（本大题共10小题，每小题3分，共30分。在每小题给出的四个选项中，有多项是符合题目要求的。全部选对得3分，部分选对得1分，有选错得0分）21.下列数据结构中，属于非线性结构的有（）。A.树B.图C.队列D.栈22.进程通信的主要方式包括（）。A.管道B.消息传递C.共享内存D.信号量23.引起进程切换的事件可能有（）。A.时间片用完B.更高优先级的进程就绪C.进程请求I/OD.进程执行了exit系统调用24.计算机网络中的物理层接口特性包括（）。A.机械特性B.电气特性C.功能特性D.规程特性25.以下关于虚拟内存的叙述，正确的有（）。A.虚拟内存利用了局部性原理B.虚拟内存的大小受限于物理内存和外存之和C.虚拟内存允许程序比物理内存大D.虚拟内存的实现需要硬件支持26.常见的动态内存分配算法有______。A.首次适应算法B.最佳适应算法C.最坏适应算法D.伙伴系统27.下列指令中，属于特权指令的有（）。A.修改PSW（程序状态字）B.启动I/O指令C.访管指令D.移位指令28.在TCP协议中，建立连接的三次握手过程中，客户端可能发送的报文段标志位包括（）。A.SYNB.ACKC.FIND.PSH29.组合逻辑电路与时序逻辑电路的区别在于（）。A.组合逻辑电路无记忆功能B.时序逻辑电路输出取决于当前输入和状态C.组合逻辑电路包含存储元件D.时序逻辑电路受时钟控制30.常用的网络拓扑结构有（）。A.星型B.环型C.总线型D.网状型三、填空题（本大题共10小题，每小题2分，共20分）31.设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈，若出栈序列为b,d,c,f,e,a，则栈的容量至少为______。32.在深度为h的完全二叉树中，第i层（i≤33.若进程P通过信号量S执行P(S)操作，则当S34.某计算机字长为32位，存储容量为256MB，按字编址，则地址寄存器的位数为______位。35.在IP数据报分片传输中，负责在目的主机重组数据报的字段是______和______。36.两个整数A=−15和B37.在操作系统中，文件控制块FCB是操作系统为了管理文件而建立的数据结构，其中包含文件的______、文件物理位置等信息。38.若哈希函数H(39.在DMA（直接存储器访问）控制方式中，数据传输是在______和______之间直接进行的。40.在滑动窗口协议中，若发送窗口大小为N，则发送方在收到确认前最多可以发送______个帧。四、简答题（本大题共4小题，每小题5分，共20分）41.简述快速排序算法的基本思想及其平均时间复杂度。42.什么是进程间的同步与互斥？信号量机制中的P(S)43.简述TCP协议建立连接（三次握手）的过程以及断开连接（四次挥手）的过程。44.解释Cache（高速缓存）的局部性原理，并说明直接映射、全相联映射和组相联映射这三种映射方式的主要区别。五、综合应用题（本大题共4小题，共70分）45.（15分）设散列表长度为m=13，散列函数为H((1)请采用线性探测再散列法解决冲突，构造该散列表。(2)计算在等概率查找成功情况下的平均查找长度（ASL）。46.（20分）某系统采用页式存储管理，页面大小为4KB，用户逻辑地址空间为32位（即）。某进程的页表如下表所示（页表项有效位为1表示在内存，为0表示不在内存；物理块号即为页框号）：页号有效位物理块号访问位修改位013001171120---31500...............(1)该逻辑地址空间最多能容纳多少个页面？(2)逻辑地址0x00003A2和0x00012B8对应的物理地址是多少？（若缺页请指出）(3)若系统采用LRU（最近最少使用）页面置换算法，当访问逻辑地址0x0002100时发生缺页中断，当前内存中已无空闲页框，且物理内存共有4个页框（分别被页0、页1、页3占用），请说明置换过程，写出被置换出的页号。47.（15分）假设主机A向主机B发送一个大的TCP报文段。TCP报文头固定部分为20字节，数据部分为3000字节。网络层MTU（最大传输单元）为1500字节（包含IP头部20字节）。(1)该TCP报文段在IP层需要进行分片吗？如果需要，请计算需要分成多少片？(2)请写出第一个IP分片和第二个IP分片中的“总长度”、“标识”、“标志”、“片偏移”字段的值。（假设IP标识为1234）。48.（20分）某计算机的指令字长为16位，采用扩展操作码技术，指令系统包含二地址指令、一地址指令和零地址指令。每个地址码长度为4位。(1)若二地址指令有M条，一地址指令有N条，零地址指令有P条，请写出三者数量之间的约束关系式。(2)若二地址指令有15条，一地址指令有30条，在不考虑操作码扩展特例的情况下，最多还能定义多少条零地址指令？(3)某指令格式如下所示：|Op(4位)|Ms(2位)|Md(2位)|Rs(2位)|Rd(2位)|其中Op为操作码，Ms/Md为源/目的操作数寻址方式，Rs/Rd为寄存器编号。若机器共有8个通用寄存器，请说明该指令格式最多支持多少种寻址方式的组合。六、参考答案及解析一、单项选择题1.D解析：简单选择排序无论初始序列如何，都需要进行n−1趟排序，每趟都要在剩余元素中比较找出最小（或最大）元素，其时间复杂度恒定为O()。直接插入排序、冒泡排序在最好情况下（已有序）为2.B解析：二叉链表中，每个节点有2个指针域（左孩子、右孩子）。n个节点共有2n个指针域。其中n−1个非空指针域用于连接节点（树的边数为n3.C解析：无无向图中，每条边连接2个顶点，对这两个顶点的度数各贡献1。因此，所有顶点的度数之和等于边数的2倍。4.C解析：进程调度程序（ProcessScheduler）是操作系统的核心组件，负责根据一定的调度算法从就绪队列中选择一个进程，将CPU分配给它。5.C解析：虚拟存储器的大小取决于CPU所能支持的逻辑地址空间的大小。虽然物理内存和辅存大小是实际限制，但理论上限由CPU的地址总线宽度（位数）决定。6.C解析：传输层负责端到端的通信，TCP（传输控制协议）提供面向连接的、可靠的数据传输服务。7.B解析：主存容量4M块大小64BCache容量16KB=直接映射下，Cache行号占8位。主存地址结构：标记(Tag)+Cache行号+块内地址。标记位数=主存地址位数Cache行号位数块内地址位数=228注：此处计算若按主存字节地址算，Tag为8位。若按题目选项语境，通常主存地址位数为22位。注：此处计算若按主存字节地址算，Tag为8位。若按题目选项语境，通常主存地址位数为22位。修正计算：修正计算：主存地址22位。块内地址6位。Cache行数，行号8位。Tag=228再次审视选项：选项为8,10,12,14。计算得8位。选A。再次审视选项：选项为8,10,12,14。计算得8位。选A。等等，重新检查：主存4MB=。Cache16KB。块64B。等等，重新检查：主存4MB=。Cache16KB。块64B。Cache行数=/=主存块地址=22−Tag=主存块地址Cache行号=16−故选A。8.C解析：资源有序分配策略是指规定所有进程必须严格按照资源编号的递增次序申请资源，从而破坏了循环等待条件。9.A解析：IEEE754单精度浮点数，阶码8位，采用移码表示，偏置值通常为−110.A解析：表示层负责处理数据的格式化、加密/解密、压缩/解压等，以确保一个系统的应用层发送的数据能被另一个系统的应用层读取。11.C解析：计算H(检查地址9：表中未列出被占用，且题目已知地址为1,3,5,6。所以直接插入9。选C。12.B解析：进程因等待I/O事件而无法继续执行，由运行态转变为阻塞态（或等待态）。13.C解析：A类范围1-126，B类128-191，C类192-223。202属于C类。14.C解析：利用双符号位（变形补码）判断溢出是常用方法。正数的双符号位为00，负数为11。若运算结果双符号位为01（上溢）或10（下溢），则表示溢出，即双符号位不同时溢出。15.C解析：堆排序是不稳定的排序算法。例如序列[5,5,3]，堆排序过程可能改变两个5的相对顺序。16.B解析：分段存储管理通过段表实现逻辑地址到物理地址的映射。段表记录每段的基址（起始地址）和段长。17.B解析：CSMA/CD（载波监听多路访问/冲突检测）是总线型以太网的核心介质访问控制协议。18.A解析：硬布线控制器采用组合逻辑电路设计，速度快（适合RISC），但结构复杂、设计困难、不易修改。微程序控制器设计灵活、易于扩充，但速度稍慢。19.B解析：KMP算法通过next数组（或优化后的nextval数组）记录模式串自身的部分匹配信息（即真前缀与真后缀的最长公共长度），当匹配失败时，利用next数组将模式串向右滑动尽可能远的距离，避免主串指针回溯。20.A解析：DNS（域名系统）主要用于将便于人类记忆的主机域名解析为网络可识别的IP地址。二、多项选择题21.AB解析：树和图是典型的非线性结构。队列和栈是线性结构。22.ABC解析：进程通信方式包括管道（Pipe）、消息传递（MessagePassing，如消息队列、信箱）、共享内存（SharedMemory）。信号量主要用于同步与互斥，虽然传递了信号，但通常不归类为数据交换的通信方式。23.ABCD解析：时间片用完（抢占）、高优先级进程抢占（抢占）、请求I/O（阻塞）、程序正常/异常结束（终止）都会引起进程切换。24.ABCD解析：物理层接口特性包含机械（形状、尺寸）、电气（电压、电平）、功能（各条线的用途）、规程（事件顺序）四个特性。25.ACD解析：虚拟内存基于局部性原理（A）。它允许程序大小大于物理内存（C）。实现需要硬件支持（如页表基址寄存器、TLB等）（D）。选项B错误，虚拟内存大小理论上只受限于CPU地址空间，与物理内存+外存之和无关（虽然实际上受限于外存容量，但理论上限是地址空间）。26.ABC解析：伙伴系统也是一种动态分区分配，但通常归类为特定的伙伴算法。常见的连续内存分配算法包括首次适应、最佳适应、最坏适应。27.AB解析：特权指令只能由操作系统内核使用，如修改PSW（程序状态字）、启动I/O、修改时钟、修改内存保护寄存器等。访管指令（Trap/SVC）是由用户程序主动发起，用于进入内核态，属于非特权指令（用户可调用）。移位指令是普通算术逻辑指令。28.AB解析：三次握手：客户端发送SYN（同步），服务端回复SYN+ACK，客户端发送ACK。客户端可能发送SYN（第一步）和ACK（第三步）。29.ABD解析：组合逻辑电路无记忆功能（A正确），输出仅取决于当前输入。时序逻辑电路包含存储元件（如触发器）（C错误），输出取决于当前输入和电路状态（B正确），受时钟信号控制（D正确）。30.ABCD解析：星型、环型、总线型、网状型都是常见的网络拓扑结构。三、填空题31.3解析：a入栈；b入栈，b出栈（栈：a）；c入栈；d入栈，d出栈（栈：a,c）；c出栈（栈：a）；e入栈；f入栈，f出栈（栈：a,e）；e出栈（栈：a）；a出栈。过程中栈内元素最多为3（如a,c,d或a,e,f）。32.解析：二叉树第i层（根为第1层）最多有个节点。33.阻塞（或等待）解析：P(S)操作中，S.v34.26解析：存储容量256MB=B。字长32位=4B。按字编址，总字数=/=。地址寄存器需26位才能寻址所有字单元。35.标识；片偏移（或Identification；FragmentOffset）解析：IP数据报头部的“标识”字段用于标识属于同一数据报的分片；“片偏移”字段用于指明分片在原数据报中的相对位置。36.E9解析：A=−15B=6,求[A[−11110001+结果为11101011。转换为十六进制：EB。修正：11110001+11111010：修正：1+0=10+1=10+0=00+1=11+1=0(进1)1+1+1=1(进1)1+1+1=1(进1)1+1=0(进1)结果：11101011->EB。再次检查：[−B是对[B连同符号位求反加1。再次检查：[00000110→加法：11110001+1111101011101011结果为EB。注：若题目是A−B，结果是EB。若计算有误请核对。注：若题目是等等，−1521的补码（8位）：21=00010101反码=11101010补码=11101011十六进制为EB。正确。37.文件名（或文件标识符）解析：FCB包含文件名、文件物理位置、文件逻辑结构、存取控制信息、文件属性等信息。38.1；7解析：H(H(H(H(H(H(故14下标为1，20下标为7。39.内存；外设（或I/O设备）解析：DMA方式用于在内存和外设之间直接进行高速数据块传输，无需CPU干预。40.N解析：发送窗口大小为N，意味着发送方在收到第一个确认之前，最多可以连续发送N个帧（序号从0到N-1）。四、简答题41.答：基本思想：快速排序采用分治法。从待排序序列中任选一个元素作为“枢轴”（Pivot），通过一趟排序将序列分为两部分，一部分所有元素均小于等于枢轴，另一部分所有元素均大于等于枢轴。然后分别对这两部分递归地进行快速排序，直至整个序列有序。平均时间复杂度：O(nl42.答：同步：指并发进程之间因相互合作而产生的直接制约关系，即进程A必须在进程B完成某操作后才能执行，需协调执行顺序。互斥：指并发进程之间因共享临界资源而产生的间接制约关系，即各进程互斥地访问共享资源，某一时刻仅允许一个进程进入临界区。P(S)原语：S.value=V(S)原语：S.value=43.答：三次握手：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报文（ACK=1,ack=y+1,seq=x+1），进入ESTABLISHED状态。服务端收到ACK后也进入ESTABLISHED状态。四次挥手：1.主动方发送FIN报文（FIN=1,seq=u），进入FIN_WAIT_1状态。2.被动方收到FIN，发送ACK报文（ACK=1,ack=u+1,seq=v），进入CLOSE_WAIT状态。主动方收到后进入FIN_WAIT_2状态。3.被动方数据发送完毕，发送FIN报文（FIN=1,seq=w），进入LAST_ACK状态。4.主动方收到FIN，发送ACK报文（ACK=1,ack=w+1,seq=u+1），进入TIME_WAIT状态，等待2MSL后关闭。被动方收到ACK后关闭。44.答：局部性原理：指程序在执行时呈现出局部性特征，包括时间局部性（最近访问的单元很可能再次被访问）和空间局部性（最近访问单元的邻近单元很可能被访问）。Cache利用此原理提高命中率。映射方式区别：直接映射：每个主存块只能映射到Cache中唯一固定的行。优点是硬件简单，缺点是冲突率高。全相联映射：每个主存块可以映射到Cache中的任意一行。优点是冲突率低，空间利用率高，缺点是比较电路复杂，成本高。组相联映射：Cache分组，每组多行。主存块映射到固定的组，组内任意行。是前两者的折衷，兼顾了性能和成本。五、综合应用题45.解：(1)构造散列表：m=19:19。地址6空，存入。14:14。地址1空，存入。23:23。地址10空，存入。1:1。冲突，探查2。地址2空，存入。68:68。地址3空，存入。20:20。地址7空，存入。84:84。冲突，探查7。地址7冲突（20），探查8。地址8空，存入。27:27。冲突，探查2。冲突（1），探查3。冲突（68），探查4。地址4空，存入。55:55。冲突，探查4。冲突（27），探查5。地址5空，存入。11:11。地址11空，存入。散列表（下标：内容）：0:NULL1:142:13:684:275:556:197:208:849:NULL10:2311:1112:NULL(2)计算ASL：19:1次14:1次23:1次1:2次68:1次20:1次84:3次27:4次55:3次11:1次总次数=1+元素个数n=AS46.解：(1)页面总数：逻辑地址空间32位，页面大小4KB(B)。页面数=/=(2)物理地址计算：逻辑地址结构：页号（高20位）+页内偏移（低12位）。0x00003A2：二进制：`0000000000000000001110100010`页号=0，页内偏移=0x3A2。查页表：页0有效位为1，物理块号3。物理地址=(物理块号<<12)|偏移=3×0x00012B8：二进制：`0000000000000001001010111000`页号=1，页内偏移=0x2B8。查页表：页1有效位为1，物理块号7。物理地址=7×(3)LRU置换过程：访问逻辑地址0x0002100。页号=2，页内偏移=0x100。查页表：页2有效位为0，发生缺页中断。内存物理块情况（假设初始）：{3:页0,7:页1,5:页3}。共3块被占用。题目指出“物理内存共有4个页框（分别被页0、页1、页3占用）”，且“已无空闲页框”。这意味着虽然总容量是4，但当前3个被占用，可能有一个被保留或题目暗示这3个占用了活跃空间，需在它们之间置换。或者意味着虽然总共4个，但只有这3个是进程占用的有效页，且无法分配新的（可能系统保留或题目描述暗示这3个就是候选集）。根据LRU，需要在页0、页1、页3中选择最久未使用的。修正理解：题目说“物理内存共有4个页框...已无空闲页框”，通常意味着这4个全满了，但只列出了3个页（0,1,3）。可能有一个页框未被列出或属于系统。但若严格按LRU在页0、1、3中置换：修正理解：题目说“物理内存共有4个页框...已无空闲页框”，通常意味着这4个全满了，但只列出了3个页（0,1,3）。可能有一个页框未被列出或属于系统。但若严格按LRU在页0、1、3中置换：假设访问序列或时间戳：题目未给出之前的访问历史。但页表中有“访问位”。通常LRU实现需要近似或完整历史。若基于题目给出的页表信息：页0访问位0，页1访问位1，页3访问位0。仅凭当前访问位无法精确判断LRU（需知道页1是最近访问的，但页0和页3谁更久远？）。另一种可能：题目暗示这4个页框全满，其中一个是页0，一个是页1，一个是页3，还有一个可能是其他页或无效。既然只给了这三个，我们假设置换候选是这三个。另一种可能：题目暗示这4个页框全满，其中一个是页0，一个是页1，一个是页3，还有一个可能是其他页或无效。既然只给了这三个，我们假设置换候选是这三个。如果必须选择，通常Clock算法会选访问位为0的。这里页0和页3访问位为0。在缺乏完整历史的情况下，假设页0是最久未被访问的（或根据默认逻辑）。注：在标准考试题中，若未给历史，通常假设页表顺序或特定规则。这里假设置换页0。注：在标准考试题中，若未给历史，通常假设页表顺序或特定规则。这里假设置换页0。被置换出的页号：0。47.解：(1)分片判断：IP层MTU=1500字节。IP头部=20字节。IP数据载荷最大=150020TCP报文总长=20(头)+3000(数据)=3020字节。因为3020>数据部分3000字节。第一片数据：1480字节。第二片数据：30001480因为1520>第三片数据：15201480共分为3片。(2)字段计算：标识字段Identification=1234（所有分片相同）。第一片：总长度=IP头(20)+数据(1480)=1500。标识=1234。标志：MF=1（还有后续分片），DF=0。片偏移=0/8=0。第二片：总长度=IP头(20)+数据(1480)=1500。标识=1234。标志：MF=1，DF=0。片偏移=1480/8=185。第三片（题目未问，补充）：总长度=20+40=60。标志：MF=0（最后一片）。片偏移=(1480题目要求第一片和第二片：第一片：总长度1500，标识1234，标志（MF=1），片偏移0。第二片：总长度1500，标识1234，标志（MF=1），片偏移185。48.解：(1)约束关系式：指令字长16位，地址码长4位。设二地址指令格式：Op(4位)+A1(4位)+A2(4位)。剩余4位可扩展。设一地址指令格式：扩展Op(8位)+A1(4位)。剩余4位可扩展。设零地址指令格式：扩展Op(12位)。二地址指令占用了高4位中的M个编码。剩余给一地址指令的编码空间：(M一地址指令占用了其中的N个。剩余给零地址指令的编码空间：((关系式：((即：P≤(2)计算零地址指令数量：已知M=可用的扩展空间计算：4位操作码共16种。二地址用掉15种，剩1种（即前4位为1111）。这1种前缀扩展给一地址：后4位可用。共1×一地址用掉30种？这里N=检查题目逻辑：如果M=15，剩余1个4位码。扩展4位作为一地址操作码，共16个8位码。若N=30，则空间不足。检查题目逻辑：如果修正：通常二地址指令留K个给一地址扩展。修正：通常二地址指令留K个给一地址扩展。若M=15，说明前4位有15个被二地址占用，剩下一地址指令空间=1×题目说一地址指令有30条，这在常规扩展操作码下是不可能的（除非二地址留出的扩展位更多）。假设题目意为：二地址指令15条，一地址指令30条。假设题目意为：二地址指令15条，一地址指令30条。那么，二地址必须留出足够的空间给一地址。设二地址留出x个4位码给一地址。一地址空间=x×需x×所以二地址指令最多只能有162题目给定M=15，这与可能的解释：题目数据是独立的，或者“不考虑操作码扩展特例”意