2026年下半年程序员考试基础知识真题（专业解析+参考答案）

2026年下半年程序员考试基础知识真题（专业解析+参考答案）一、单项选择题1.在计算机系统中，以下关于进程与线程的描述中，错误的是（）。A.进程是资源分配的基本单位，线程是CPU调度的基本单位B.同一进程内的多个线程共享该进程所拥有的全部资源C.线程的创建、切换和撤销开销通常大于进程D.多线程编程模型中，一个线程的崩溃可能导致整个进程终止2.对长度为n的有序顺序表进行折半查找，其时间复杂度为（）。A.O(n)B.O(n²)C.O(log₂n)D.O(nlog₂n)3.在TCP/IP协议簇中，负责将域名解析为IP地址的协议是（）。A.HTTPB.FTPC.DNSD.DHCP4.已知一棵二叉树的中序遍历序列为DBEAC，后序遍历序列为DEBCA，则该二叉树的前序遍历序列为（）。A.ABCDEB.ABDECC.ABDCED.ACBDE5.在关系数据库中，关于第三范式（3NF）的叙述，正确的是（）。A.关系模式R属于3NF当且仅当每个非主属性都完全函数依赖于主键B.关系模式R属于3NF当且仅当每个非主属性都不传递函数依赖于主键C.关系模式R属于3NF当且仅当消除了非主属性对主键的部分函数依赖和传递函数依赖D.关系模式R属于3NF当且仅当消除了主属性对主键的部分函数依赖和传递函数依赖6.采用动态规划算法解决某问题，其最优子结构性质的含义是（）。A.问题的最优解包含其子问题的最优解B.问题可以分解为若干个规模较小的相同子问题C.子问题的解可以被重复利用D.问题可以通过贪心选择得到全局最优解7.在面向对象设计中，以下关于“开闭原则”的描述，最准确的是（）。A.对扩展开放，对修改关闭B.子类必须能够替换其父类C.一个类只负责一项职责D.高层模块不应依赖于低层模块，二者都应依赖于抽象8.在32位操作系统中，一个进程的虚拟地址空间大小通常是（）。A.2GBB.4GBC.8GBD.由物理内存大小决定9.对数组[25,84,21,47,15,27,68,35,20]进行堆排序，构建初始大顶堆后，堆顶元素是（）。A.15B.20C.84D.2510.在软件开发过程中，将系统分解为若干个子系统，并确定各子系统的接口，属于（）阶段的主要任务。A.可行性分析B.需求分析C.概要设计D.详细设计11.对于无向图G=(V,E)，其邻接矩阵表示法中，说法正确的是（）。A.邻接矩阵一定是稀疏矩阵B.邻接矩阵中第i行（或第i列）非零元素的个数等于顶点i的度C.邻接矩阵的主对角线元素均为1D.邻接矩阵一定是对称矩阵12.在C语言中，设有定义`inta[5]={1,2,3,4,5};`，则表达式`(a+3)`的值是（）。12.在C语言中，设有定义`inta[5]={1,2,3,4,5};`，则表达式`(a+3)`的值是（）。A.3B.4C.5D.非法访问13.关于敏捷开发方法中的“Scrum”，以下描述不正确的是（）。A.Scrum团队通常包括产品负责人、ScrumMaster和开发团队B.一个Sprint（迭代）的周期长度通常是固定的，如2-4周C.每日站会的目的是汇报详细工作进度给管理者D.产品待办事项列表（ProductBacklog）由产品负责人负责维护14.某算法的时间复杂度递推公式为T(n)=2T(n/2)+n，且T(1)=1，则该算法的时间复杂度为（）。A.O(n)B.O(nlog₂n)C.O(n²)D.O(log₂n)15.在数据库事务的ACID特性中，“一致性”（Consistency）是指（）。A.事务的执行必须使数据库从一个一致性状态变到另一个一致性状态B.事务一旦提交，其对数据库的改变就是永久性的C.一个事务内部的操作及使用的数据对其他并发事务是隔离的D.事务中的所有操作要么全部执行，要么全部不执行16.在IPv4网络中，子网掩码为24，则该子网中可分配给主机的IP地址数量最多为（）。A.30B.31C.32D.6217.以下排序算法中，在最坏情况下时间复杂度可以达到O(nlog₂n)的是（）。A.冒泡排序B.快速排序C.归并排序D.直接插入排序18.在软件测试中，旨在检查软件是否满足需求规格说明书中规定的功能和性能的测试是（）。A.单元测试B.集成测试C.确认测试D.系统测试19.在HTML5中，用于定义文档导航链接区域的语义化标签是（）。A.`<section>`B.`<article>`C.`<nav>`D.`<aside>`20.关于死锁的必要条件，以下描述不正确的是（）。A.互斥条件B.请求和保持条件C.不可剥夺条件D.环路等待条件E.所有进程都处于运行状态二、综合应用题21.阅读以下C语言程序，分析并回答问题。```cinclude<stdio.h>intfunc(intn){if(n<=1)returnn;returnfunc(n1)+func(n2);}intmain(){intresult=func(5);printf("%d\n",result);return0;}```(1)函数`func`实现的功能是什么？当输入为5时，程序的输出结果是多少？(2)分析该算法的时间复杂度和空间复杂度。(3)请给出一种改进算法（可以使用循环或记忆化递归），并简要说明其优势。22.某公司网络拓扑结构如下图所示（此处为文字描述）。路由器R1连接两个子网：子网A（/24）和子网B（/24）。路由器R2连接子网B和互联网。所有设备均采用静态IP配置。子网B中的一台主机H（IP:00）无法访问互联网，但可以正常访问子网A和子网B内的其他主机。(1)请列出可能导致此问题的三个常见原因。(2)假设问题出在主机H的默认网关配置错误上。请写出在Windows系统中，使用命令行查看并修改该主机IP地址和默认网关配置的主要步骤（命令）。(3)除了网关配置，简述在路由器R2上可能存在的两种导致该问题的配置错误。23.设有关系模式R（A,B,C,D,E），其函数依赖集F={A→BC,CD→E,B→D,E→A}。(1)求关系模式R的候选键。(2)判断关系模式R最高属于第几范式？并说明理由。(3)若R不属于BCNF，请将其分解为满足BCNF的关系模式集合，要求分解具有无损连接性。24.某系统采用请求分页存储管理方式，页面大小为4KB。现有一个进程的逻辑地址空间为8页（0~7），其页表如下所示，其中状态位为1表示页在内存中，为0表示不在内存中。访问内存时间为100ns，访问快表（TLB）时间为10ns，快表命中率为80%。假设访问过程是：先查快表，若命中则直接形成物理地址访问内存；若未命中则需访问内存中的页表，找到页框号后形成物理地址再访问一次内存。页号页框号状态位0511-02813-041215316-0761(1)计算逻辑地址0x5A3C对应的页号与页内偏移量（用十六进制表示）。(2)若进程要访问逻辑地址0x5A3C，请计算该次有效访问的平均时间。(3)若将页面大小改为8KB，且保持进程逻辑地址空间总大小不变，则页表项数目和页内偏移量的位数分别如何变化？25.现有一个任务调度问题：有n个独立的任务J1,J2,...,Jn，每个任务有一个处理时间ti（正整数）和一个截止时间di（正整数）。如果任务Ji在截止时间di之前完成，则获得收益pi，否则收益为0。设计一个算法，安排任务的执行顺序（一个时刻只能执行一个任务，任务执行不可中断），使得获得的总收益最大。(1)请说明该问题是否具有贪心选择性质？并简述理由。(2)基于贪心算法思想，设计一个求解该问题的贪心策略，并描述其基本步骤。(3)假设任务处理时间均为1（即ti=1），请证明你所设计的贪心策略能获得最优解。参考答案与解析一、单项选择题1.【答案】C【解析】线程是进程内的一个执行单元，其创建、切换和撤销的开销远小于进程，因为线程共享进程的地址空间和大部分资源。选项C的描述恰好相反，因此错误。2.【答案】C【解析】折半查找每次将查找区间缩小一半，其时间复杂度为O(log₂n)。3.【答案】C【解析】DNS（DomainNameSystem）是用于将人类可读的域名解析为机器可识别的IP地址的协议。4.【答案】C【解析】后序遍历序列的最后一个节点‘A’是根节点。在中序遍历序列中，‘A’将序列分为左子树‘DBE’和右子树‘C’。递归分析：对于左子树‘DBE’，其后序遍历序列（来自原后序‘DEB’）的最后一个节点‘B’是左子树的根，‘B’在中序‘DBE’中将左子树分为‘D’（左）和‘E’（右）。因此前序遍历顺序为：根A，左子树根B，B的左孩子D，B的右孩子E，最后是A的右孩子C，即ABDCE。5.【答案】C【解析】第三范式（3NF）要求关系模式R∈2NF，且消除非主属性对主键的传递函数依赖。选项A描述的是第二范式（2NF）的要求。选项B描述不完整，3NF要求非主属性既不部分依赖于主键，也不传递依赖于主键。选项D描述的是BCNF对主属性的要求。6.【答案】A【解析】最优子结构性质是动态规划算法的基本要素之一，指的是问题的最优解包含其子问题的最优解。利用这个性质，可以通过求解子问题的最优解来构造原问题的最优解。7.【答案】A【解析】开闭原则是面向对象设计的重要原则，由BertrandMeyer提出，其核心是“软件实体（类、模块、函数等）应该对扩展开放，对修改关闭”。选项B是里氏替换原则，选项C是单一职责原则，选项D是依赖倒置原则。8.【答案】B【解析】在32位操作系统中，CPU的寻址能力是2^32=4GB，因此每个进程拥有独立的4GB虚拟地址空间（通常用户空间占3GB，内核空间占1GB，或按类似比例划分）。9.【答案】C【解析】构建大顶堆的过程是从最后一个非叶子节点开始向上调整。初始数组构成完全二叉树。调整后，根节点（堆顶）为最大值84。10.【答案】C【解析】概要设计阶段的主要任务是设计软件系统的体系结构，确定系统由哪些模块（或子系统）组成，以及模块（子系统）之间的接口关系。11.【答案】B【解析】对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数即为顶点i的度。邻接矩阵不一定稀疏（对于稠密图就不是），主对角线元素在无自环的情况下为0，无向图的邻接矩阵是对称的，但题目中“一定”过于绝对（虽然通常如此，但理论上存储时可能只存上三角），而B选项的描述是无向图邻接矩阵的确定性质。12.【答案】B【解析】数组名a在表达式中通常被视为指向其首元素的指针，即`a`等价于`&a[0]`。`a+3`指向第4个元素`a[3]`，其值为4。`(a+3)`即解引用得到`a[3]`的值。13.【答案】C【解析】每日站会（DailyScrum）是开发团队内部的短会，目的是同步进度、发现问题、规划当天工作，其核心是团队成员间的协作沟通，而非向管理者汇报。管理者通常不参加站会。14.【答案】B【解析】根据主定理（MasterTheorem），对于递归式T(n)=aT(n/b)+f(n)，此处a=2,b=2,f(n)=n。满足情况二：f(n)=Θ(n^{log_ba})=Θ(n^{log_22})=Θ(n)，因此时间复杂度为T(n)=Θ(n^{log_ba}logn)=Θ(nlogn)。15.【答案】A【解析】ACID特性中：A（Atomicity）原子性：事务是一个不可分割的工作单位；C（Consistency）一致性：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态；I（Isolation）隔离性：事务的执行不受其他事务干扰；D（Durability）持久性：事务一旦提交，改变是永久性的。16.【答案】A【解析】子网掩码24的二进制为11111111.11111111.11111111.11100000，主机位有5位。可分配主机IP数量为2^52=322=30个（减去网络地址和广播地址）。17.【答案】C【解析】归并排序在任何情况下时间复杂度都是O(nlog₂n)。冒泡排序和直接插入排序最坏为O(n²)。快速排序在最坏情况下（如已排序序列）时间复杂度为O(n²)，虽然平均为O(nlog₂n)。18.【答案】D【解析】系统测试是将已经集成好的软件系统，作为整个计算机系统的一个元素，与计算机硬件、外设、支持软件、数据和人员等其他系统元素结合在一起，在实际运行（使用）环境下进行的一系列测试，旨在验证系统是否满足需求规格说明。19.【答案】C【解析】HTML5语义化标签中，`<nav>`定义导航链接的部分；`<section>`定义文档中的节；`<article>`定义独立的内容；`<aside>`定义页面内容之外的内容（如侧边栏）。20.【答案】E【解析】死锁的四个必要条件是：互斥、请求和保持、不可剥夺、环路等待。“所有进程都处于运行状态”不是死锁的条件，死锁时进程可能处于等待状态。二、综合应用题21.【答案与解析】(1)函数`func`实现了计算斐波那契数列第n项的功能。当输入为5时，`func(5)=func(4)+func(3)=(func(3)+func(2))+(func(2)+func(1))`，递归计算后结果为5。(2)时间复杂度：该递归算法呈现指数级复杂度。设T(n)为计算fib(n)的时间，则T(n)=T(n-1)+T(n-2)+O(1)，其时间复杂度近似为O(2^n)。空间复杂度：主要消耗在递归调用栈上，深度为n，因此空间复杂度为O(n)。(3)改进算法（迭代法）：```cintfib(intn){if(n<=1)returnn;intprev=0,curr=1;for(inti=2;i<=n;i++){intnext=prev+curr;prev=curr;curr=next;}returncurr;}```优势：迭代法将时间复杂度降至O(n)，空间复杂度降至O(1)，避免了递归带来的巨大时间开销和栈溢出风险。22.【答案与解析】(1)三个常见原因：主机H的默认网关配置错误。主机H的默认网关配置错误。路由器R2上未配置指向互联网的默认路由或路由错误。路由器R2上未配置指向互联网的默认路由或路由错误。路由器R2上配置了错误的ACL（访问控制列表），阻止了来自子网B的流量。路由器R2上配置了错误的ACL（访问控制列表），阻止了来自子网B的流量。（其他合理原因也可，如R2外部接口故障、ISP线路问题等）(2)主要步骤（Windows命令行）：查看当前IP配置：`ipconfig/all`查看当前IP配置：`ipconfig/all`修改IP地址和默认网关（例如，设置IP为00，网关为，子网掩码）：修改IP地址和默认网关（例如，设置IP为00，网关为，子网掩码）：```netshinterfaceipsetaddressname="以太网"static00```（接口名称需根据实际情况调整，如“本地连接”）(3)在路由器R2上可能存在的两种配置错误：路由配置错误：R2缺少指向互联网服务提供商（ISP）网关的默认路由（如`iproute<ISP网关IP>`）。NAT配置错误：如果内网访问互联网需要网络地址转换（NAT），可能在R2上未正确配置NAT规则，导致内网IP地址无法被转换为公网IP。23.【答案与解析】(1)求候选键。计算属性闭包：计算属性闭包：求A的闭包A⁺：A→BC，B→D，所以A⁺=ABCD。又CD→E，E→A，所以A⁺=ABCDE。故A是候选键。求A的闭包A⁺：A→BC，B→D，所以A⁺=ABCD。又CD→E，E→A，所以A⁺=ABCDE。故A是候选键。求E的闭包E⁺：E→A，A→BC，B→D，所以E⁺=ABCDE。故E是候选键。求E的闭包E⁺：E→A，A→BC，B→D，所以E⁺=ABCDE。故E是候选键。求CD的闭包(CD)⁺：CD→E，E→A，A→BC，所以(CD)⁺=ABCDE。故CD是候选键。求CD的闭包(CD)⁺：CD→E，E→A，A→BC，所以(CD)⁺=ABCDE。故CD是候选键。求BC的闭包(BC)⁺：B→D，所以(BC)⁺=BCD。CD→E，所以(BC)⁺=BCDE。E→A，所以(BC)⁺=ABCDE。故BC是候选键。求BC的闭包(BC)⁺：B→D，所以(BC)⁺=BCD。CD→E，所以(BC)⁺=BCDE。E→A，所以(BC)⁺=ABCDE。故BC是候选键。候选键有：A,E,CD,BC。候选键有：A,E,CD,BC。(2)判断范式级别。所有属性A,B,C,D,E都是主属性（因为都存在于某个候选键中）。所有属性A,B,C,D,E都是主属性（因为都存在于某个候选键中）。对于3NF，要求不存在非主属性对主键的传递依赖。由于所有属性都是主属性，因此不可能存在非主属性传递依赖于主键。所以关系模式R至少属于3NF。对于3NF，要求不存在非主属性对主键的传递依赖。由于所有属性都是主属性，因此不可能存在非主属性传递依赖于主键。所以关系模式R至少属于3NF。检查BCNF：BCNF要求每一个决定因素都包含候选键。现有函数依赖B→D，其中决定因素B不是候选键（B的闭包B⁺=BD，不包含所有属性）。因此R不属于BCNF。检查BCNF：BCNF要求每一个决定因素都包含候选键。现有函数依赖B→D，其中决定因素B不是候选键（B的闭包B⁺=BD，不包含所有属性）。因此R不属于BCNF。结论：R最高属于3NF。结论：R最高属于3NF。(3)分解为BCNF。从违反BCNF的函数依赖B→D开始分解。R1=B⁺=BD。R1=B⁺=BD。R2=R{D}+{B}=ABCE。但R2中需要保持原有的函数依赖关系。检查R2的函数依赖：A→BC（在R2中为A→BC），E→A，B→?(B→D不在R2中，但B是R2的属性，且D已移出)，CD→E（C和D未同时出现在R2中，此依赖可能丢失，需检查后续分解或考虑其他分解方式）。R2=R{D}+{B}=ABCE。但R2中需要保持原有的函数依赖关系。检查R2的函数依赖：A→BC（在R2中为A→BC），E→A，B→?(B→D不在R2中，但B是R2的属性，且D已移出)，CD→E（C和D未同时出现在R2中，此依赖可能丢失，需检查后续分解或考虑其他分解方式）。更稳妥的分解过程：以B→D为基准分解后，R1(B,D)。原关系R(A,B,C,D,E)去掉D后，加上B得到R2(A,B,C,E)。现在分析R2：计算R2中函数依赖在属性集上的投影。有A→BC（在R2中即A→BC），E→A，B→(无，因D已不在)。候选键？在R2中，A⁺=ABCE，E⁺=ABCE，BC⁺=BC?在R2中，BC的闭包：已知B不能推出其他（除了自己），C也不能，但BC一起呢？原CD→E，现在C和B在一起，没有依赖能推出E。所以BC不是R2的候选键。R2的候选键是A和E。检查R2是否满足BCNF：依赖A→BC，决定因素A是候选键，满足。E→A，决定因素E是候选键，满足。故R2属于BCNF。最终分解结果为：R1(B,D)和R2(A,B,C,E)。该分解具有无损连接性（因为R1∩R2={B}，且B→D成立）。24.【答案与解析】(1)页面大小=4KB=2^12B，所以页内偏移量占12位（二进制）。逻辑地址0x5A3C转换为二进制：`0101101000111100`。取高20位（因为32位系统，虚拟地址32位，减去偏移量12位，页号占20位）计算页号过于复杂，更简单的方法是：逻辑地址0x5A3C是十六进制，其十进制值为23100。页号=逻辑地址/页面大小=23100/4096=5（取整）。页内偏移量=逻辑地址%页面大小=23100%4096=2310054096=2310020480=2620。2620的十六进制为0xA3C。取高20位（因为32位系统，虚拟地址32位，减去偏移量12位，页号占20位）计算页号过于复杂，更简单的方法是：逻辑地址0x5A3C是十六进制，其十进制值为23100。页号=逻辑地址/页面大小=23100/4096=5（取整）。页内偏移量=逻辑地址%页面大小=23100%4096=2310054096=2310020480=2620。2620的十六进制为0xA3C。或者直接取十六进制：页面大小4KB=0x1000。页号=0x5A3C/0x1000=0x5。页内偏移量=0x5A3C%0x1000=0xA3C。答：页号为0x5，页内偏移量为0xA3C。(2)访问逻辑地址0x5A3C，其页号为5。查页表，页号5的状态位为1，在内存中，页框号为3，不会产生缺页中断。有效访问时间=TLB访问时间+(1TLB命中率)访问页表时间+访问内存数据时间。有效访问时间=TLB访问时间+(1TLB命中率)访问页表时间+访问内存数据时间。其中，访问页表时间是一次内存访问，访问内存数据时间也是一次内存访问。公式化：设Tm为访问内存时间（100ns），Tt为访问TLB时间（10ns），H为命中率（80%）。则平均有效访问时间=Tt+(1-H)Tm+Tm=10+0.2100+100=10+20+100=130ns。则平均有效访问时间=Tt+(1-H)Tm+Tm=10+0.2100+100=10+20+100=130ns。答：平均有效访问时间为130ns。(3)逻辑地址空间总大小不变=8页4KB=32KB。(3)逻辑地址空间总大小不变=8页4KB=32KB。页面大小改为8KB后，总页数=32KB/8KB=4页。页表项数目：从8项减少为4项。页表项数目：从8项减少为4项。页内偏移量位数：页面大小8KB=2^13B，所以页内偏移量位数从12位增加到13位。页内偏移量位数：页面大小8KB=2^13B，所以页内偏移量位数从12位增加到13位。25.【答案与解析】(1)该问题具有贪心选择性质。因为目标是总收益最大，一个直观的贪心思想是优先安排单位时间内收益高（或更紧急）的任务。具体来说，可以按照某种规则（如按截止时间排序，或按收益与处理时间的比值排序）来选择任务，并证明通过这样的局部最优选择可以导致全局最优解。对于处理时间均为1的特殊情况，贪心性质更明显。(2)贪心策略（按截止时间排序，收益相同时任意）：步骤1：将所有任务按照截止时间di的非递减顺序排序。如果截止时间相同，可以按收益pi的非递增顺序排序。步骤2：初始化一个当前时间t=0，以及一个可选任务集合S（初始为空）。步骤3：按排序顺序依次考虑每个任务Ji：如果t+ti<=di，则将任务Ji加入集合S，并更新当前时间t=t+ti。如果t+ti<=di，则将任务Ji加入集合S，并更新当前时间t=t+ti。否则（即无法在截止时间前完成），从集合S中（包括当前任务Ji）寻找一个收益最小的任务Jk（如果Ji的收益比S中最小收益还小，则直接丢弃Ji；否则，用Ji替换Jk，并保持t不变（因为总处理时间可能因替换而改变，但这里ti可能不同，需要更复杂的处理）。这个替换策略是为了在时间槽有限的情况下，尽可能保留高收益任务。否则（即无法在截止时间前完成），从集合S中（包括当前任务Ji）寻找一个收益最小的任务Jk（如果Ji的收益比S中最小收益还小，则直接丢弃Ji；否则，用Ji替换Jk，并保持t不变（因为总处理时间可能因替换而改变，但这