2025年计算机专业课考试试题及答案

2025年计算机专业课考试试题及答案一、单项选择题（每题2分，共20分）1.以下关于平衡二叉树（AVL树）的描述中，错误的是（）。A.任意节点的左右子树高度差绝对值不超过1B.插入操作可能引发多次旋转调整C.查找时间复杂度为O(logn)D.删除操作不会改变树的平衡因子答案：D解析：删除操作可能导致多个祖先节点的平衡因子变化，需要从删除位置向上回溯调整，因此可能改变平衡因子。2.某进程在时间片轮转调度中被分配了5ms的时间片，当它执行3ms后发生I/O请求并进入阻塞态，此时CPU的调度行为是（）。A.立即剥夺该进程CPU，调度下一个进程B.等待该进程I/O完成后继续执行剩余2msC.将该进程时间片重置为5ms，重新进入就绪队列D.该进程继续占用CPU直到时间片耗尽答案：A解析：时间片轮转调度中，进程因I/O阻塞时会主动释放CPU，调度程序立即选择下一个就绪进程执行。3.在TCP协议中，若发送方窗口大小为1000字节，接收方通告窗口大小为800字节，此时发送方实际可发送的最大数据量是（）。A.1000字节B.800字节C.1800字节D.由拥塞窗口决定答案：B解析：TCP发送窗口取接收方通告窗口和拥塞窗口的较小值，本题未提及拥塞窗口，默认取接收方通告窗口。4.关系模式R(A,B,C,D)，函数依赖为A→B,B→C,C→D，则R的最高范式是（）。A.1NFB.2NFC.3NFD.BCNF答案：B解析：候选键为A，非主属性B、C、D均部分依赖于A（A→B→C→D存在传递依赖），因此不满足3NF，但满足2NF（无部分依赖）。5.以下关于虚拟内存的描述中，正确的是（）。A.虚拟内存的大小仅受限于物理内存容量B.页面置换算法的目标是减少缺页中断次数C.抖动现象是由于进程访问的页面均在内存中引起的D.段页式管理中，段表和页表都只需存储在内存中答案：B解析：虚拟内存大小受限于地址空间和外存容量（A错误）；抖动是频繁缺页导致（C错误）；段表和页表可部分存于外存（D错误）。6.若一个无向图有n个顶点和m条边，其邻接矩阵存储的空间复杂度为（）。A.O(n)B.O(m)C.O(n²)D.O(n+m)答案：C解析：邻接矩阵是n×n的二维数组，空间复杂度为O(n²)。7.某计算机的主存地址为32位，按字节编址，若使用4M×8位的DRAM芯片构成64MB的主存，需要的芯片数量是（）。A.8片B.16片C.32片D.64片答案：B解析：每片芯片容量为4M×8位=4MB（8位=1字节），64MB/4MB=16片。8.以下关于广度优先搜索（BFS）的描述中，错误的是（）。A.可以用于求解无权图的最短路径问题B.需要使用队列作为辅助数据结构C.遍历顺序与递归深度优先搜索（DFS）相同D.时间复杂度为O(V+E)（V为顶点数，E为边数）答案：C解析：BFS按层遍历，DFS按深度优先，遍历顺序不同。9.在数据库事务中，“一个事务的执行不被其他事务干扰”体现了事务的（）特性。A.原子性（Atomicity）B.一致性（Consistency）C.隔离性（Isolation）D.持久性（Durability）答案：C解析：隔离性要求事务间互不干扰，保证各自的执行环境。10.某指令系统采用定长指令字（32位），操作码占8位，地址码字段设计为3个16位的地址码，这种设计会导致（）。A.指令长度超过32位B.地址码总长度超过24位C.无法表示三地址指令D.操作码空间浪费答案：D解析：3个16位地址码总长度为48位，超过32位，因此实际需缩短地址码长度，导致操作码占8位时地址码空间不足，需采用扩展操作码技术，原设计会浪费操作码空间。二、填空题（每空2分，共20分）1.数据结构中，栈的基本操作包括入栈、出栈、取栈顶元素和__________（判断栈是否为空）。答案：判空2.操作系统中，进程的三种基本状态是运行态、就绪态和__________。答案：阻塞态（或等待态）3.TCP协议中，三次握手的第三个报文是__________（填写标志位组合）。答案：ACK4.关系数据库中，若两个关系R和S的笛卡尔积有m×n个元组，则R有m个元组，S有__________个元组。答案：n5.计算机组成原理中，CPU的主要组成部分包括运算器、控制器和__________。答案：寄存器组6.图的遍历中，深度优先搜索的非递归实现通常使用__________作为辅助数据结构。答案：栈7.虚拟内存管理中，常用的页面置换算法有最佳置换算法（OPT）、先进先出算法（FIFO）和__________（写出一种）。答案：最近最久未使用算法（LRU）8.数据库设计的四个阶段是需求分析、概念设计、逻辑设计和__________。答案：物理设计9.指令周期是指CPU从__________到执行完该指令所需的全部时间。答案：取出一条指令10.在无向图中，若存在一个顶点v，使得删除v后图的连通分量数目增加，则v称为__________。答案：关节点（或割点）三、简答题（每题8分，共40分）1.简述快速排序的基本思想，并说明其平均时间复杂度和最坏时间复杂度的区别及原因。答案：快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，然后分别对这两部分继续进行排序，以达到整个序列有序。平均时间复杂度为O(nlogn)，此时每次划分能将序列大致均分，递归深度为logn，每层处理n个元素。最坏时间复杂度为O(n²)，当序列已经有序（正序或逆序）时，每次划分仅减少一个元素（基准元素为最值），递归深度为n，每层处理n、n-1、…、1个元素，总时间为n(n+1)/2≈O(n²)。2.说明操作系统中进程与线程的区别（至少列出4点）。答案：（1）资源分配：进程是资源分配的基本单位，线程是CPU调度的基本单位；（2）独立性：进程间资源独立（除共享内存等特殊情况），同一进程内的线程共享进程资源；（3）并发性：进程间并发需切换上下文，开销大；线程间并发切换仅需切换线程上下文，开销小；（4）创建/销毁开销：进程创建需分配内存、文件等资源，开销大；线程创建仅需分配少量寄存器和栈空间，开销小；（5）地址空间：进程拥有独立的地址空间，线程共享所属进程的地址空间。3.描述TCP协议中拥塞控制的四个阶段及其核心机制。答案：TCP拥塞控制分为四个阶段：（1）慢开始（SlowStart）：初始时拥塞窗口（cwnd）从1MSS（最大报文段长度）开始，每经过一个RTT（往返时间），cwnd翻倍，直到达到慢开始门限（ssthresh）；（2）拥塞避免（CongestionAvoidance）：当cwnd≥ssthresh时，进入拥塞避免阶段，每经过一个RTT，cwnd增加1MSS，线性增长；（3）快速重传（FastRetransmit）：当发送方收到3个重复ACK时，认为发生轻度拥塞，立即重传丢失的报文段，无需等待超时；（4）快速恢复（FastRecovery）：快速重传后，将ssthresh设为当前cwnd的一半，cwnd设为ssthresh+3MSS（3个重复ACK表明有3个报文段已到达接收方），然后进入拥塞避免阶段。4.解释数据库中事务的ACID特性，并说明日志（Log）在保证ACID中的作用。答案：ACID特性：-原子性（Atomicity）：事务的所有操作要么全部完成，要么全部不完成；-一致性（Consistency）：事务执行前后数据库处于一致状态；-隔离性（Isolation）：事务间互不干扰，执行结果与串行执行相同；-持久性（Durability）：事务提交后，其修改永久保存在数据库中。日志的作用：-原子性：通过日志记录事务的所有操作，若事务失败，利用日志回滚（Undo）未完成的操作；-持久性：事务提交前将日志写入磁盘（先写日志后写数据库），确保即使系统崩溃，可通过日志重做（Redo）已提交但未写入数据库的操作；-隔离性：通过日志配合锁机制或时间戳，记录事务对数据的修改，确保其他事务不会看到未提交的中间状态。5.说明计算机中Cache（高速缓存）的作用，并解释直接映射、全相联映射和组相联映射的区别。答案：Cache的作用是解决CPU与主存速度不匹配的问题，利用局部性原理，将主存中近期频繁访问的内容复制到高速的Cache中，减少CPU访问主存的时间。三种映射方式的区别：（1）直接映射：主存块只能映射到Cache的一个特定位置（主存块号modCache块数），实现简单但冲突率高（不同主存块映射到同一Cache位置时需替换）；（2）全相联映射：主存块可映射到Cache的任意位置，冲突率低但需要全比较电路（查找时需比较所有Cache块的标记），实现复杂；（3）组相联映射：将Cache分为若干组，每组包含k个块，主存块映射到特定组（主存块号mod组数），组内全相联。结合了直接映射的简单性和全相联的低冲突率，k为组的大小（如2路组相联、4路组相联）。四、算法设计题（每题10分，共20分）1.设计一个算法，判断一个单链表是否为回文链表（即正读和反读相同）。要求时间复杂度为O(n)，空间复杂度为O(1)（允许修改原链表）。答案：算法步骤：（1）使用快慢指针法找到链表的中间节点：快指针每次走2步，慢指针每次走1步，快指针到达末尾时，慢指针指向中间（奇数个节点）或前半部分末尾（偶数个节点）；（2）反转链表的后半部分：以慢指针的下一个节点为起点，反转后半部分链表；（3）比较前半部分和反转后的后半部分链表：逐一比较节点值，若全部相同则为回文；（4）恢复原链表（可选，根据题目要求是否保留原结构）。代码实现（伪代码）：```functionisPalindrome(head):ifhead==nullorhead.next==null:returntrue找中间节点slow=headfast=headwhilefast.next!=nullandfast.next.next!=null:slow=slow.nextfast=fast.next.next反转后半部分secondHalf=reverseList(slow.next)比较p1=headp2=secondHalfwhilep2!=null:ifp1.val!=p2.val:returnfalsep1=p1.nextp2=p2.nextreturntruefunctionreverseList(head):prev=nullcurr=headwhilecurr!=null:next=curr.nextcurr.next=prevprev=currcurr=nextreturnprev```2.给定一个整数数组nums和一个目标值target，设计一个算法找出所有满足a+b+c=target的三元组（a,b,c），要求不包含重复的三元组。答案：算法思路（双指针法）：（1）排序数组：先对nums进行排序，便于去重和后续双指针操作；（2）遍历固定第一个数a：从i=0开始，若nums[i]>target（当target为正时）可提前终止（因数组已排序，后续数更大）；（3）去重第一个数：若nums[i]==nums[i-1]（i>0），跳过以避免重复三元组；（4）双指针寻找b和c：设左指针left=i+1，右指针right=len(nums)-1，计算sum=nums[i]+nums[left]+nums[right]；（5）根据sum与target的关系调整指针：-若sum==target：记录三元组，然后移动左指针（跳过重复值）和右指针（跳过重复值）；-若sum<target：左指针右移（增大sum）；-若sum>target：右指针左移（减小sum）。代码实现（伪代码）：```functionthreeSum(nums,target):sort(nums)result=[]n=len(nums)forifrom0ton-3:ifi>0andnums[i]==nums[i-1]:去重acontinuea=nums[i]ifa>targetandtarget>0:提前终止（可选优化）breakleft=i+1right=n-1whileleft<right:b=nums[left]c=nums[right]sum=a+b+cifsum==target:result.append([a,b,c])去重bwhileleft<rightandnums[left]==nums[left+1]:left+=1去重cwhileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifsum<target:left+=1else:right-=1returnresult```五、综合应用题（每题10分，共20分）1.某操作系统采用可变分区存储管理，内存初始状态为0~1023KB空闲。现有以下进程请求分配内存：-进程A：200KB-进程B：300KB-进程C：150KB-进程D：400KB（1）若采用首次适应算法（FirstFit），画出分配后的内存布局（标注分区起始地址、大小及状态）；（2）若进程B和进程C先后释放内存，采用伙伴系统（BuddySystem）管理时，释放后的空闲分区如何合并？答案：（1）首次适应算法分配过程：初始空闲分区：0~1023KB（1024KB）。-分配进程A（200KB）：从0开始分配，剩余空闲分区为200~1023KB（824KB）；-分配进程B（300KB）：从200开始分配，剩余空闲分区为500~1023KB（524KB）；-分配进程C（150KB）：从500开始分配，剩余空闲分区为650~1023KB（374KB）；-分配进程D（400KB）：剩余空闲分区374KB<400KB，无法分配（需等待或换出）。最终内存布局（地址单位：KB）：0~199：进程A（200KB，已分配）200~499：进程B（300KB，已分配）500~649：进程C（150KB，已分配）650~1023：空闲（374KB）（2）伙伴系统合并过程（假设内存总大小为1024KB=2^10）：-进程B释放300KB：伙伴系统要求分区大小为2的幂次，进程B实际分配的分区大小为512KB（2^9，因300KB≤512KB且512KB是≥300KB的最小2的幂）；原进程B的分区起始地址为200KB，512KB分区的起始地址需对齐到512KB边界（200KB不在0、512、1024…，矛盾，说明首次适应分配的分区可能不满足伙伴系统的对齐要求。因此需重新假设伙伴系统下的分配：伙伴系统中，进程B请求300KB，分配512KB（2^9），起始地址为0~511KB（假设首次分配）；但原题中首次适应的分配与伙伴系统的分配策略不同，需明确伙伴系统下的分配：正确步骤应为：初始空闲块为1024KB（2^10）。-进程A请求200KB，分配256KB（2^8），剩余空闲块为1024-256=768KB（分为256KB和512KB？不，伙伴系统分配时拆分大的块。正确拆分：1024KB拆分为512KB和512KB，其中一个512KB拆分为256KB和256KB，分配256KB给A（起始地址0~255KB）；-进程B请求300KB，分配512KB（2^9），从剩余的512KB块分配（起始地址256~767KB）；-进程C请求150KB，分配256KB（2^8），从剩余的256KB块（768~1023KB）分配（起始地址768~1023KB中的前256KB，即768~1023KB被拆分为256KB和256KB，分配256KB给C）；当进程B（512KB，地址256~767KB）和进程C（256KB，地址768~1023KB中的768~1023？不，正确地址应为768~1023KB是512KB块，拆分为256KB和256KB，假设C分配的是768~1023KB中的768~1023KB？可能更简单的方式是：释放进程B（512KB，地址256~767KB）和进程C（256KB，地址768~1023KB中的768~1023KB？实际伙伴系统中，相邻且