奥林匹克信息学(计算机)竞赛初赛基础知识培训材料二试题库及答案

奥林匹克信息学(计算机)竞赛初赛基础知识培训材料二(试题库及答案一、单项选择题（每题2分，共30分）1.在C++中，若定义inta=3,b=4;则表达式(a^b)<<1的值为A.14  B.12  C.10  D.8答案：A解析：a^b为3^4=7，7<<1得14。2.若一棵完全二叉树共有2023个节点，则其叶子节点数为A.1011  B.1012  C.1013  D.1014答案：B解析：完全二叉树叶子数=⌈n/2⌉，2023为奇数，叶子数=1012。3.下列排序算法中，最坏情况下时间复杂度为O(nlogn)且稳定的是A.快速排序  B.归并排序  C.堆排序  D.希尔排序答案：B解析：归并排序稳定且最坏O(nlogn)。4.在32位系统中，以下结构体占用的字节数为structS{charc;doubled;inti;};A.16  B.20  C.24  D.32答案：C解析：按8字节对齐，char(1)+填充7+double(8)+int(4)+填充4=24。5.若图的邻接矩阵为对称矩阵，则该图A.必为无向图  B.必为有向图  C.可能为有向图  D.必为树答案：A解析：无向图邻接矩阵对称。6.以下关于并查集路径压缩的说法正确的是A.路径压缩会增加空间复杂度  B.路径压缩后查找操作均摊O(1)C.路径压缩不可与按秩合并共用  D.路径压缩会改变元素值答案：B解析：路径压缩使树高趋常数，查找近似O(1)。7.在模998244353下，7的逆元为A.855638018  B.142606337  C.998244346  D.142606336答案：A解析：快速幂求7^(mod-2)modmod得855638018。8.若哈希表采用链地址法，负载因子α=2，则平均成功查找长度A.O(1)  B.O(α)  C.O(1+α)  D.O(α²)答案：C解析：链地址法成功查找长度≈1+α/2。9.以下哪个正则表达式可匹配不含连续两个0的二进制串A.(101)  B.(1|01)0?  C.(1|01)  D.(0|1)答案：C解析：(1|01)*保证无连续0。10.在KMP算法中，模式串"ababaca"的next数组为A.0012301  B.-1001230C.0123012  D.-1012301答案：B解析：标准next数组定义，首元-1。11.若使用Prim算法求最小生成树，其时间复杂度用斐波那契堆可实现A.O(ElogV)  B.O(E+VlogV)  C.O(V²)  D.O(ElogE)答案：B解析：Prim+斐波那契堆为O(E+VlogV)。12.以下哪个C++关键字能阻止派生类覆盖函数A.final  B.override  C.static  D.volatile答案：A解析：final修饰虚函数不可再覆盖。13.在Linux中，查看当前进程打开文件描述符数量的命令是A.lsof-pPID  B.ls-l/proc/PID/fd  C.top-pPID  D.strace-pPID答案：B解析：/proc/PID/fd目录下文件数即描述符数。14.若浮点数采用IEEE754单精度，则0x40400000表示的十进制数为A.3.0  B.2.5  C.4.0  D.5.0答案：A解析：符号0，阶码10000000，尾数1.1，值=1.1×2^1=3.0。15.以下关于线段树延迟标记的说法错误的是A.延迟标记可减少更新复杂度  B.标记下传需递归左右子树C.标记可累积  D.标记无需下传即可回答区间查询答案：D解析：必须下传标记才能保证查询正确。二、不定项选择题（每题3分，共15分，多选少选均不得分）16.关于Dijkstra算法，下列说法正确的是A.可处理负权边  B.采用优先队列时复杂度O((V+E)logV)C.可用于差分约束系统  D.贪心策略保证最短路径答案：BD解析：A错，C为Bellman-Ford应用。17.以下哪些操作会使C++vector的迭代器失效A.push_back导致重新分配  B.insert中间元素C.erase尾部元素  D.修改元素值答案：ABC解析：重新分配或移动元素均使迭代器失效。18.关于Trie树，下列说法正确的是A.插入复杂度O(字符串长度)  B.可快速查询前缀C.必为二叉树  D.可压缩为DFA答案：ABD解析：Trie多叉，非必二叉。19.以下哪些排序算法属于比较排序A.计数排序  B.归并排序  C.基数排序  D.堆排序答案：BD解析：计数与基数为非比较排序。20.在Linux下，哪些信号不可被捕获或忽略A.SIGKILL  B.SIGSTOP  C.SIGTERM  D.SIGSEGV答案：AB解析：SIGKILL与SIGSTOP不可捕获。三、填空题（每空3分，共30分）21.若int占4字节，char占1字节，则union{intx;chary[5];}占__5__字节。解析：union取最大成员5字节，按最大对齐4对齐，总5。22.快速选择算法求第k小元素，平均时间复杂度__O(n)__。解析：类似快排划分，平均O(n)。23.设哈希函数h(k)=kmod7，采用线性探测，插入序列{8,15,22}后，22所在下标为__1__。解析：8→1，15→1冲突→2，22→1冲突→2冲突→3，最终22在3，更正：22mod7=1→1被8占→2被15占→3空，故填3。24.一颗AVL树最少节点数N(h)满足递推__N(h)=N(h-1)+N(h-2)+1__，初值N(0)=1,N(1)=2。解析：经典AVL最少节点递推。25.在模运算中，(a/b)modm等于__a·b^(m-2)modm__，当m为质数。解析：费马小求逆元。26.使用Floyd求传递闭包时，中间节点k的循环应放在__最外层__。解析：k外层次保证子问题正确。27.若二进制数101101左移2位后再算术右移2位，结果为__101101__。解析：左移2→10110100，算术右移2→11110101，若原6位则补符号位1，得111011，更正：设6位，101101→左2→10110100（8位），算术右2→11110101，截6位→110101。28.在C++中，typeid(a).name()返回类型名字符串，其头文件为__<typeinfo>__。29.若CPU缓存行64字节，则遍历步长为__16__个int时可触发缓存行跳跃，假设int=4字节。解析：64/4=16。30.采用主定理求解T(n)=4T(n/2)+n²，得T(n)=__Θ(n²logn)__。解析：符合主定理第2类，k=0。四、程序阅读题（每题5分，共20分）31.```cppinclude<iostream>usingnamespacestd;intmain(){inta=1,b=2,c=3;cout<<((a+=b,c=a+b,a+c)<<1)<<endl;return0;}```输出：__22__解析：逗号表达式依次执行，a+=b→a=3,c=3+2=5,a+c=8,8<<1=16，更正：a+c=3+5=8，8<<1=16，输出16。32.```cppintf(intn){staticintm=1;returnm*=n;}intmain(){for(inti=1;i<=4;i++)cout<<f(i)<<"";}```输出：__12624__解析：static保留上次值，阶乘。33.```cppintmain(){intx=0x89;x=(x&0xf0)>>4|(x&0x0f)<<4;printf("%#x\n",x);}```输出：__0x98__解析：高4位与低4位交换。34.```cpptemplate<intn>structF{staticintval(){returnn*F<n-1>::val();}};template<>structF<0>{staticintval(){return1;}};cout<<F<5>::val();```输出：__120__解析：编译期阶乘。五、程序填空题（每空4分，共20分）35.给定数组a[n]，求最长递增子序列长度，使用lower_bound优化：```cppintlis(vector<int>&a){vector<int>tail;for(intx:a){autoit=lower_bound(tail.begin(),tail.end(),x);if(it==tail.end())tail.push_back(x);else*it=x;}returntail.size();}```36.并查集按秩合并+路径压缩：```cppstructDSU{vector<int>fa,sz;DSU(intn):fa(n),sz(n,1){iota(fa.begin(),fa.end(),0);}intfind(intx){returnfa[x]==x?x:fa[x]=find(fa[x]);}voidmerge(intx,inty){x=find(x);y=find(y);if(x==y)return;if(sz[x]<sz[y])swap(x,y);fa[y]=x;sz[x]+=sz[y];}};```37.快速幂：```cpplonglongqpow(longlonga,longlongb,longlongmod){longlongr=1;for(;b;b>>=1,a=a*a%mod)if(b&1)r=r*a%mod;returnr;}```38.线段树区间加，区间求和：```cppstructSeg{vector<longlong>s,lz;intn;Seg(intn):n(n),s(n<<2),lz(n<<2){}voidadd(intl,intr,intv){add(1,0,n-1,l,r,v);}voidadd(intp,intl,intr,intL,intR,intv){if(L<=l&&r<=R){s[p]+=(r-l+1)*v;lz[p]+=v;return;}intm=(l+r)>>1;if(lz[p]){s[p<<1]+=(m-l+1)*lz[p];s[p<<1|1]+=(r-m)*lz[p];lz[p<<1]+=lz[p];lz[p<<1|1]+=lz[p];lz[p]=0;}if(L<=m)add(p<<1,l,m,L,R,v);if(R>m)add(p<<1|1,m+1,r,L,R,v);s[p]=s[p<<1]+s[p<<1|1];}longlongask(intl,intr){returnask(1,0,n-1,l,r);}longlongask(intp,intl,intr,intL,intR){if(L<=l&&r<=R)returns[p];intm=(l+r)>>1;if(lz[p]){s[p<<1]+=(m-l+1)*lz[p];s[p<<1|1]+=(r-m)*lz[p];lz[p<<1]+=lz[p];lz[p<<1|1]+=lz[p];lz[p]=0;}longlongret=0;if(L<=m)ret+=ask(p<<1,l,m,L,R);if(R>m)ret+=ask(p<<1|1,m+1,r,L,R);returnret;}};```39.字典序全排列下一位：```cppboolnextPerm(vector<int>&a){inti=a.size()-1;while(i&&a[i-1]>=a[i])i--;if(!i)returnfalse;intj=a.size()-1;while(a[j]<=a[i-1])j--;swap(a[i-1],a[j]);reverse(a.begin()+i,a.end());returntrue;}```六、算法设计题（共25分）40.（10分）给定n≤1e5个区间[li,ri]，求最少选择多少个点使每个区间至少包含一个点。解：贪心。按右端点升序排序，维护last=-inf，遍历若li>last则选ri，更新last=ri。证明：最优解交换论证。复杂度：O(nlogn)。41.（15分）给定长n≤1e5的序列a[i]∈[1,1e6]，求有多少子区间异或和等于k。解：前缀异或xor[i]，问题转化为求i<j满足xor[j]^xor[i]=k，即xor[i]=xor[j]^k。用unordered_map<longlong,int>cnt，遍历j时累加cnt[xor[j]^k]，再插入xor[j]。复杂度：O(n+1e6)。七、数学与复杂度题（共20分）42.（10分）求解递推T(n)=T(n/3)+T(2n/3)+O(n)，证明T(n)=Θ(nlogn)。解：画递归树，每层代价和为n，树高log_{3/2}n，总Θ(nlogn)。43.（10分）证明n个节点的红黑树高度至多为2log(n+1)。解：黑高bh≥h/2，节点数n≥2^{bh}-1，得h≤2log(n+1)。八、综合编程题（共30分）44.（30分）题目：给定一棵n≤2×1e5的无根树，边权为1，q≤1e5次查询，每次问u到v路径上第k小边权（此处边权全1，改为点权第k小）。修正：点权第k小。解：可持久化线段树+树上差分。步骤：1.DFS序+主席树，根到x路径建版本tree[x]。2.查询u,v,lca，答案=tree[u]+tree[v]-tree[lca]-tree[fa[lca]]上第k小。3.离散化点权，主席树节点存子树size。复杂度：O((n+q)logn)。参考代码：```cppinclude<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;intn,q,a[N],b[N],cnt,h[N],to[N<<1],nxt[N<<1];voidadd(intu,intv){to[++cnt]=v;nxt[cnt]=h[u];h[u]=cnt;}intfa[N],dep[N],sz[N],son[N],top[N],dfn[N],tot;voiddfs1(intu,intf){fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;son[u]=0;for(inti=h[u];i;i=nxt[i]){intv=to[i];if(v==f)continue;dfs1(v,u);sz[u]+=sz[v];if(sz[v]>sz[son[u]])son[u]=v;}}voiddfs2(intu,intt){top[u]=t;dfn[u]=++tot;if(son[u])dfs2(son[u],t);for(inti=h[u];i;i=nxt[i]){intv=to[i];if(v==fa[u]||v==son[u])continue;dfs2(v,v);}}intlca(intu,intv){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}returndep[u]<dep[v]?u:v;}structNode{intls,rs,s;}t[N*40];intrt[N],tc;intbuild(intl,intr){intp=++tc;t[p].s=0;if(l==r)returnp;intm=(l+r)>>1;t[p].ls=build(l,m);t[p].rs=build(m+1,r);returnp;}intupd(intpre,intl,intr,intx){intp=++tc;t[p]=t[pre];t[p].s++;if(l==r)returnp;intm=(l+r)>>1;if(x<=m)t[p].ls=upd(t[pre].ls,l,m,x);elset[p].rs=upd(t[pre].rs,m+1,r,x);returnp;}intqk(intu,intv,intx,inty,intl