2026程序设计能力试题及答案

2026程序设计能力试题及答案一、单项选择题（每题2分，共20分）1.在C++17中，若定义```cppautof=[](autox,autoy){returnx+y;};```则表达式`f(3,4.5)`的返回值类型为A.int  B.double  C.std::common_type_t<int,double>  D.编译失败答案：B解析：lambda的返回类型由`+`运算符推导，`int+double`结果为`double`。2.对长度为n的数组执行一次快速排序的划分操作（Hoare划分），最坏情况下交换次数为A.O(1)  B.O(logn)  C.O(n)  D.O(n²)答案：C解析：划分本身需扫描整个区间，最坏交换次数与n同阶。3.在64位Linux下，结构体```cppstructS{chara;doubleb;charc;};```的大小为A.10  B.16  C.24  D.32答案：C解析：对齐到8字节，布局为1(a)+7(填充)+8(b)+1(c)+7(填充)=24。4.对下图进行广度优先搜索，顶点访问顺序（同层按字母序）为A→B A→C B→D C→E D→F E→GA.ABCDEFG  B.ACBEDGF  C.ABDCEFG  D.ABCDFEG答案：A解析：队列先存A，弹出后依次压入B、C；B弹出后压D；C弹出后压E；依此类推。5.在Python3.10中，表达式```python(lambdax:(lambday:x+y))(5)(7)```的值为A.12  B.5  C.7  D.报错答案：A解析：外层lambda返回内层lambda，x被捕获为5，再调用y=7。6.若哈希表采用开放定址法，装载因子α=0.85，则成功查找期望探查次数约为A.1.5  B.2.5  C.3.8  D.5.2答案：C解析：线性探测公式½(1+1/(1−α))≈3.83。7.在Java17中，代码```javavarlist=List.of(1,2,3);list.add(4);```运行结果A.编译错误  B.运行抛UnsupportedOperationExceptionC.正常执行  D.抛NullPointerException答案：B解析：`List.of`返回不可变列表。8.对二叉搜索树执行删除操作后，若仍需保证树高为O(logn)，应采用A.普通BST  B.AVL树  C.Treap  D.B树答案：B解析：AVL通过旋转严格平衡。9.在SQL标准中，下列语句哪一条一定能触发索引范围扫描A.SELECT*FROMTWHEREABS(col)=5;B.SELECT*FROMTWHEREcolBETWEEN10AND20;C.SELECT*FROMTWHEREcolLIKE'%abc';D.SELECT*FROMTWHEREcol+1=100;答案：B解析：BETWEEN可使用有序索引；ABS与表达式导致失效；前缀通配符失效。10.在Go1.20中，通道ch的容量为0，执行```goch:=make(chanint)select{casech<1:fmt.Print("A")case<-ch:fmt.Print("B")default:fmt.Print("C")}```输出为A.A  B.B  C.C  D.死锁答案：C解析：无缓冲通道读写均阻塞，default分支可立即执行。二、填空题（每空3分，共30分）11.对序列{5,1,7,3,9}进行希尔排序，增量序列取3、1，第一趟增量为3后的数组为______。答案：31759解析：增量3分组(5,3)(1,9)(7)，组内插入排序得(3,5)(1,9)(7)。12.在IPv4子网/27中，可用主机地址数量为______。答案：30解析：32−27=5位主机号，2⁵−2=30。13.若某算法最坏时间复杂度T(n)=4T(n/2)+O(n²)，则根据主定理T(n)=______。答案：Θ(n²logn)解析：符合主定理情形2，a=4,b=2,f(n)=Θ(n^{log_ba})=Θ(n²)。14.在Rust1.70中，代码```rustletv=vec![1,2,3];letr=&v[1..];println!("{}",std::mem::size_of_val(r));```输出为______字节。答案：16解析：切片胖指针，含8字节数据指针与8字节长度。15.对8位补码数11111011算术右移两位后的二进制为______。答案：11111110解析：符号位1填充，右移后11111110。16.在Linux系统调用中，打开文件返回的文件描述符最小可用值为______。答案：3解析：0/1/2被stdin/stdout/stderr占用。17.在正则引擎中，表达式`(a|b)*c\1`能否匹配字符串"abca"______（填能/不能）。答案：不能解析：`\1`引用未捕获分组，空引用无法匹配a。18.在HTTP/2帧格式中，帧首部长度为______字节。答案：9解析：3字节长度+1类型+1标志+4流标识=9。19.在PyTorch2.0中，张量`x=torch.randn(3,4,5)`，执行`x.transpose(0,2).contiguous().shape`结果为______。答案：torch.Size([5,4,3])解析：转置后维度重排再连续化。20.在Git2.40中，命令`gitlog--oneline--graph--all`默认使用的字符集编码为______。答案：UTF-8解析：Git默认以UTF-8输出日志。三、程序阅读题（每题10分，共30分）21.阅读下列C++20代码，写出输出结果。```cppinclude<iostream>include<coroutine>structpromise{structpromise_type{intvalue;autoinitial_suspend(){returnstd::suspend_always{};}autofinal_suspend()noexcept{returnstd::suspend_always{};}autoget_return_object(){returnpromise{std::coroutine_handle<promise_type>::from_promise(*this)};}voidreturn_value(intv){value=v;}voidunhandled_exception(){}};std::coroutine_handle<promise_type>h;promise(std::coroutine_handle<promise_type>x):h(x){}~promise(){if(h)h.destroy();}intget(){returnmise().value;}};promisefoo(){co_return42;}intmain(){autop=foo();std::cout<<p.get();}```答案：42解析：协程返回42，main中通过promise对象取出。22.阅读下列Python3.11代码，写出输出。```pythonfromfunctoolsimportlru_cache@lru_cache(maxsize=None)deff(n):ifn<2:returnnreturnf(n-1)+f(n-2)+f(n//2)print(f(6))```答案：42解析：记忆化递归，自底向上计算得f(6)=42。23.阅读下列Go1.20代码，写出输出。```gopackagemainimport"fmt"typeIinterface{M()}typeTstruct{vint}func(tT)M(){fmt.Print(t.v)}funcmain(){varxI=T{7}varyI=&T{8}x.M()y.M()}```答案：78解析：值接收者，x复制值7，y解引用后同样打印8。四、算法设计题（每题20分，共40分）24.给定一张n点m边的无向图，边权为1或2。设计O(n+m)算法求出从源点s到所有点的最短距离，并给出核心代码。答案：将边权2拆成两条权1的边，中间引入虚拟节点；再用普通BFS即可。```cppvector<int>dist;voidbfs01(ints,constvector<vector<pair<int,int>>>&g){intn=g.size();dist.assign(n,-1);deque<int>dq;dist[s]=0;dq.push_back(s);while(!dq.empty()){intu=dq.front();dq.pop_front();for(auto[v,w]:g[u]){if(dist[v]==-1||dist[v]>dist[u]+w){dist[v]=dist[u]+w;if(w==0)dq.push_front(v);elsedq.push_back(v);}}}}```实际无需拆边，直接0-1BFS：权1放队尾，权0放队首。复杂度O(n+m)。25.给定长为n的整数数组a，允许将任意子数组加1或减1共k次，求最终数组最小化∑|a_i|的值。n≤2×10⁵，|a_i|≤10⁹，k≤10¹⁴。答案：差分转化。设差分数组d，操作等价于对d做±1。目标最小化∑|前缀和|。观察到最优策略一定先消除极值。将d排序，取绝对值最大的前k个，每次减1，累加贡献即可。```cpptypedeflonglongll;llsolve(vector<int>a,llk){intn=a.size();vector<ll>d(n);for(inti=1;i<n;i++)d[i]=(ll)a[i]a[i-1];sort(d.begin()+1,d.end(),[](llx,lly){returnabs(x)>abs(y);});for(inti=1;i<n&&k;i++){llt=min(k,abs(d[i]));if(d[i]>0)d[i]-=t;elsed[i]+=t;k-=t;}llsum=0,ans=0;for(inti=0;i<n;i++){sum+=d[i];ans+=abs(sum);}returnans;}```时间O(nlogn)。五、系统与综合（每题15分，共30分）26.描述如何在4KB页式系统中实现一个支持线程级迁移的内存池，要求：(1)避免falsesharing；(2)页内碎片<1/16；(3)迁移时无需全局锁。答案：采用per-CPU池，每池维护16条slab链，每条链管理同一大小对象（2⁴~2¹⁹字节）。slab内部采用bitmap标记空闲，页首放置元数据。对象地址按64字节对齐，避免falsesharing。迁移时，将整页挂入目标CPU的迁移队列，通过RCU延迟回收，无需锁。页内碎片通过slab着色抵消，保证≤1/16。27.在分布式一致性场景，Raft与Paxos的最大工程差异是什么？给出一段50行以内Go代码，展示Raft如何动态变更集群配置而不停服。答案：最大差异：Raft将一致性与安全性分解为“Leader选举”“日志复制”“成员变更”三大子问题，提供日志连续性保证，工程上更易实现线性化语义。```gotypeConfChangestruct{Typeuint8//AddNodeRemoveNodeNodeIDuint64Context[]byte}func(r*Raft)proposeConfChange(ccConfChange)error{data:=encodeConfChange(cc)ent:=Entry{Type:EntryConfChange,Data:data}returnr.Propose(ent)}//在日志apply时func(r*Raft)applyConfChange(entEntry){varccConfChangedecodeConfChange(ent.Data,&cc)switchcc.Type{caseAddNode:r.addNode(cc.NodeID)caseRemoveNode:r.removeNode(cc.NodeID)}r.pendingConf=false}```通过jointconsensus两阶段：先进入joint状态（新旧多数派共同决策），再提交最终配置，实现零停机扩容缩容。六、编程实战（50分）28.在线评测地址省略，请在本机完成：题目：给定一棵n个节点的树，边带权w∈[1,10⁵]。q次查询，每次给出u,v,k，求u→v路径上第k小的边权。n,q≤10⁵，强制在线，lastans初始为0。输入格式：第一行n,q；接下来n−1行每行abc；接下来q行每行uvk，真实u,v,k需异或lastans。输出格式：每行一个答案，更新lastans。要求：代码总长度≤5KB；内存≤256MB；时间≤2s。参考思路：树链剖分+可持久化线段树合并。对边权离散化，每条边在DFS序对应子树内插入线段树。查询u,v时，拆成LCA两段，用五棵线段树相加减得路径上边权有序列表，再在线段树上二分第k小。核心代码（C++20，已压行）：```cppinclude<bits/stdc++.h>usingnamespacestd;constintN=1e5+5,LOG=17;intn,q,tot,fa[N][LOG],dep[N],sz[N],son[N],top[N],dfn[N],rk[N],a[N],b[N],c[N],w[N],lst;vector<pair<int,int>>g[N];structNode{intls,rs,s;}t[NLOG4];intrt[N],cnt;voidins(int&p,intl,intr,intx,intv){if(!p)p=++cnt;t[p].s+=v;if(l==r)return;intm=(l+r)>>1;x<=m?ins(t[p].ls,l,m,x,v):ins(t[p].rs,m+1,r,x,v);}intqk(intp1,intp2,intp3,intp4,intl,intr,intk){if(l==r)returnl;intm=(l+r)>>1,left=t[t[p1].ls].s+t[t[p2].ls].s-t[t[p3].ls].s-t[t[p4].ls].s;if(k<=left)returnqk(t[p1].ls,t[p2].ls,t[p3].ls,t[p4].ls,l,m,k);elsereturnqk(t[p1].rs,t[p2].rs,t[p3].rs,t[p4].rs,m+1,r,k-left);}voiddfs1(intu,intf){fa[u][0]=f;dep[u]=dep[f]+1;sz[u]=1;for(inti=1;i<LOG;i++)fa[u][i]=fa[fa[u][i-1]][i-1];for(auto[v,idx]:g[u])if(v!=f){w[v]=c[idx];dfs1(v,u);sz[u]+=sz[v];if(sz[v]>sz[son[u]])son[u]=v;}}voiddfs2(intu,i