2025年信息学奥赛选拔考试试题卷及答案

2025年信息学奥赛选拔考试试题卷及答案1.单选题（每题3分，共30分）1.1若整数x满足(x⊕(x+1))&(x+2)=0，则x在0≤x≤63范围内出现的次数为A.16B.32C.48D.641.2对长度为n的序列a，定义f(i)=max{a[j]|j<i且a[j]<a[i]}，若不存在则f(i)=0。若a为1~n的随机排列，则Σf(i)的期望值为A.Θ(n)B.Θ(nlogn)C.Θ(n²)D.Θ(n√n)1.3一棵n个叶子的二叉树，每个内部节点存储其子树叶子数的斐波那契值，根节点值为F(k)，则k的最大可能值为A.n−1B.nC.n+1D.2n−21.4给定无向图G=(V,E)，|V|=1e5，|E|=2e5，边权为1或2，求1到n的最短路径，时间复杂度最优的算法是A.Dijkstra+二叉堆B.0-1BFSC.线段树优化DijkstraD.SPFA1.5在模998244353下，多项式(1+x)^nmodx^64的系数逆序后形成的向量与原向量的循环卷积结果为A.0B.1C.nD.2^n1.6若二维数组A[0..1023][0..1023]按行主序存储，首地址为0，每个元素占4字节，则A[i][j]与A[j][i]地址差的绝对值最大为A.0B.4092C.4096D.81921.7对长度为1e6的01串，每次操作可翻转一个长度为k的连续子串，求最少操作使全0，k为偶数，则问题可转化为A.差分+并查集B.线性基C.最短路D.最小生成树1.8在C++20中，表达式([]<typenameT>(Tx){returnx+x;})(1.5)的类型为A.intB.doubleC.floatD.ill-formed1.9若哈希表采用开放寻址+二次探查，负载因子α=0.7，则一次成功查找的平均探查次数约为A.1.2B.1.4C.1.7D.2.01.10对随机变量X∈{0,1}^n，定义Y=ΣX_i，Z=Ymod3，则Z的熵H(Z)随n增大趋于A.0B.log2(3)C.nD.12.不定项选择（每题4分，共20分，多选漏选错选均不得分）2.1以下哪些算法在期望线性时间内解决最小圆覆盖问题A.随机增量B.分治C.模拟退火D.Megiddo剪枝2.2对一棵Treap，执行split与merge各一次，以下哪些性质必然保持A.堆性质B.二叉搜索性质C.子树大小D.中序遍历2.3在32位系统上，以下哪些代码片段可能产生未定义行为A.inta=1<<31;B.floatf=1e40;C.charc=256;D.intp=0;p=0;2.4以下哪些图问题在平面图上有比通用图更快的算法A.最大流B.全源最短路C.最小割D.最大独立集2.5对长度为n的序列，以下哪些排序算法最坏比较次数为Θ(nlogn)且额外空间O(1)A.堆排B.归并C.块排D.平滑排序3.填空题（每空3分，共30分）3.1设f(n)=Σ_{k=0}^{n}C(n,k)·k^3，则f(n)=______(用n与2^n表示)。3.2若矩阵A∈R^{3×3}满足A^3=0且A≠0，则A的秩最大为______。3.3对正整数n，定义g(n)为n的二进制表示中相邻不同位的对数，则g(2025)=______。3.4在模1e9+7下，Σ_{i=1}^{2025}i^{i}mod1e9+7=______。3.5若四叉堆存储在数组中，根下标为0，则下标为i的节点的第3个子节点下标为______。3.6对长度为n的括号序列，定义其“深度”为最大嵌套层数，则深度为k的合法序列数为______（用C表示组合数）。3.7若随机置换π∈S_n，则π的循环个数的期望为______。3.8在C++中，表达式typeid(std::move(0)).name()[0]在GCC下的常见值为______。3.9对一棵n个节点的红黑树，插入一个新节点后，经过的“黑高”调整最多涉及______次旋转。3.10若有限状态自动机M有5个状态，输入字母表大小为2，则M的不同数量上限为______（用指数表示）。4.程序阅读与输出（每题5分，共20分）4.1```cppinclude<bits/stdc++.h>usingnamespacestd;intmain(){inta=0,b=1,c=2;for(inti=0;i<10;i++){tie(a,b,c)=make_tuple(b^c,a+(b&1),a-b);}cout<<a<<""<<b<<""<<c<<endl;return0;}```输出：______4.2```cppinclude<bits/stdc++.h>usingnamespacestd;intmain(){vector<int>v={3,1,4,1,5};autof=[&](autoself,intl,intr)->int{if(l==r)returnv[l];intm=(l+r)/2;returnself(self,l,m)^self(self,m+1,r);};cout<<f(f,0,4)<<endl;return0;}```输出：______4.3```cppinclude<bits/stdc++.h>usingnamespacestd;intmain(){intn=13,m=17;autoq=[](inta,intb){return(a|b)&-(a|b);};cout<<q(n^m,n&m)<<endl;return0;}```输出：______4.4```cppinclude<bits/stdc++.h>usingnamespacestd;intmain(){uint64_tx=1;for(inti=0;i<64;i++)x|=x<<i;cout<<__builtin_popcountll(x)<<endl;return0;}```输出：______5.程序填空（每空4分，共20分）5.1给定n×m网格，每个格子为'0'~'9'，求从(1,1)到(n,m)路径上数字拼接成整数mod1e9+7的最小值。空处填适当代码。```cppconstintMOD=1e9+7;intn,m,dp[1005][1005][10];charg[1005][1005];intmain(){cin>>n>>m;for(inti=1;i<=n;i++)cin>>(g[i]+1);memset(dp,0x3f,sizeofdp);dp[1][1][g[1][1]-'0']=g[1][1]-'0';for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)if(i+j>2){intc=g[i][j]-'0';for(intd=0;d<10;d++){intv=dp[i][j][d];if(i>1)dp[i][j][(d10+c)%10]=min(dp[i][j][(d10+c)%10],______(1)______);if(j>1)dp[i][j][(d10+c)%10]=min(dp[i][j][(d10+c)%10],______(2)______);}}intans=min_element(dp[n][m],dp[n][m]+10);cout<<ans<<endl;}```(1)______(2)______5.2给定长为n的序列a，求最长子数组满足区间mex等于区间或值。空处填适当代码。```cppintn,a[200005],ans=0;set<int>s;intmex(){intm=0;while(s.count(m))m++;returnm;}intmain(){cin>>n;for(inti=0;i<n;i++)cin>>a[i];for(intl=0,r=0,orv=0;l<n;l++){while(r<n){s.insert(a[r]);orv|=a[r];if(mex()==orv)ans=max(ans,______(3)______);elsebreak;r++;}s.erase(a[l]);orv&=~______(4)______;}cout<<ans<<endl;}```(3)______(4)______6.算法设计题（共50分）6.1（15分）给定一棵n个节点的树，边权为1，定义f(u,v)为u到v路径上的边数。求Σ_{u<v}f(u,v)^2mod998244353。要求：时间复杂度O(n)，空间O(n）。6.2（15分）给定长为n的序列a，|a_i|≤1e9，求一个子序列，使得其元素乘积的绝对值最大，输出该绝对值mod1e9+7。要求：时间复杂度O(nlogn)，空间O(n）。6.3（20分）动态维护一个可重集，支持：1.插入x；2.删除x（保证存在）；3.查询第k小元素；4.查询所有元素中位数与平均值的差的绝对值。初始为空，操作次数q≤1e5，|x|≤1e9。要求：每次操作时间复杂度O(logq)，空间O(q)。7.答案与解析1.1B解析：x⊕(x+1)最低位连续1的个数为t，则(x+2)的最低位0位于第t+1位，按位与为0当且仅当t≥1，即x为偶数，共32个。1.2A解析：等价于求排列中“左小”对数期望，线性。1.3C解析：斐波那契数列增长指数级，最大k=n+1。1.4B解析：0-1BFS边权仅1或2，双端队列线性。1.5A解析：逆序后与原序列在模x^64下卷积为0。1.6B解析：行主序地址差|1024i+j−(1024j+i)|最大取i=1023,j=0，得4092。1.7A解析：差分后问题变为区间翻转，并查集维护连续段。1.8B解析：auto返回double。1.9C解析：二次探查成功查找平均探查次数1/(1−α)−α/2≈1.7。1.10B解析：中心极限定理，Z趋于均匀，熵log2(3)。2.1AB2.2ABCD2.3ACD2.4ABC2.5AD3.1n(n+3)2^{n−3}3.223.363.47385341273.54i+33.6C(n,k)−C(n,k−1)3.7H_n≈lnn+γ3.8i3.923.102^{40}4.161−54.204.3164.4645.1(1)(dp[i−1][j][d]10+c)%10(