奧林匹克信息學(xué)(計算機)競賽初賽基礎(chǔ)知識培訓(xùn)材料二(試題庫及答案一、單項選擇題（每題2分，共30分）1.在C++中，若定義inta=3,b=4;則表達(dá)式(a^b)<<1的值為A.14??B.12??C.10??D.8答案：A解析：a^b為3^4=7，7<<1得14。2.若一棵完全二叉樹共有2023個節(jié)點，則其葉子節(jié)點數(shù)為A.1011??B.1012??C.1013??D.1014答案：B解析：完全二叉樹葉子數(shù)=?n/2?，2023為奇數(shù)，葉子數(shù)=1012。3.下列排序算法中，最壞情況下時間復(fù)雜度為O(nlogn)且穩(wěn)定的是A.快速排序??B.歸并排序??C.堆排序??D.希爾排序答案：B解析：歸并排序穩(wěn)定且最壞O(nlogn)。4.在32位系統(tǒng)中，以下結(jié)構(gòu)體占用的字節(jié)數(shù)為structS{charc;doubled;inti;};A.16??B.20??C.24??D.32答案：C解析：按8字節(jié)對齊，char(1)+填充7+double(8)+int(4)+填充4=24。5.若圖的鄰接矩陣為對稱矩陣，則該圖A.必為無向圖??B.必為有向圖??C.可能為有向圖??D.必為樹答案：A解析：無向圖鄰接矩陣對稱。6.以下關(guān)于并查集路徑壓縮的說法正確的是A.路徑壓縮會增加空間復(fù)雜度??B.路徑壓縮后查找操作均攤O(1)C.路徑壓縮不可與按秩合并共用??D.路徑壓縮會改變元素值答案：B解析：路徑壓縮使樹高趨常數(shù)，查找近似O(1)。7.在模998244353下，7的逆元為A.855638018??B.142606337??C.998244346??D.142606336答案：A解析：快速冪求7^(mod-2)modmod得855638018。8.若哈希表采用鏈地址法，負(fù)載因子α=2，則平均成功查找長度A.O(1)??B.O(α)??C.O(1+α)??D.O(α2)答案：C解析：鏈地址法成功查找長度≈1+α/2。9.以下哪個正則表達(dá)式可匹配不含連續(xù)兩個0的二進(jìn)制串A.(101)??B.(1|01)0???C.(1|01)??D.(0|1)答案：C解析：(1|01)*保證無連續(xù)0。10.在KMP算法中，模式串"ababaca"的next數(shù)組為A.0012301??B.-1001230C.0123012??D.-1012301答案：B解析：標(biāo)準(zhǔn)next數(shù)組定義，首元-1。11.若使用Prim算法求最小生成樹，其時間復(fù)雜度用斐波那契堆可實現(xiàn)A.O(ElogV)??B.O(E+VlogV)??C.O(V2)??D.O(ElogE)答案：B解析：Prim+斐波那契堆為O(E+VlogV)。12.以下哪個C++關(guān)鍵字能阻止派生類覆蓋函數(shù)A.final??B.override??C.static??D.volatile答案：A解析：final修飾虛函數(shù)不可再覆蓋。13.在Linux中，查看當(dāng)前進(jìn)程打開文件描述符數(shù)量的命令是A.lsof-pPID??B.ls-l/proc/PID/fd??C.top-pPID??D.strace-pPID答案：B解析：/proc/PID/fd目錄下文件數(shù)即描述符數(shù)。14.若浮點數(shù)采用IEEE754單精度，則0x40400000表示的十進(jìn)制數(shù)為A.3.0??B.2.5??C.4.0??D.5.0答案：A解析：符號0，階碼10000000，尾數(shù)1.1，值=1.1×2^1=3.0。15.以下關(guān)于線段樹延遲標(biāo)記的說法錯誤的是A.延遲標(biāo)記可減少更新復(fù)雜度??B.標(biāo)記下傳需遞歸左右子樹C.標(biāo)記可累積??D.標(biāo)記無需下傳即可回答區(qū)間查詢答案：D解析：必須下傳標(biāo)記才能保證查詢正確。二、不定項選擇題（每題3分，共15分，多選少選均不得分）16.關(guān)于Dijkstra算法，下列說法正確的是A.可處理負(fù)權(quán)邊??B.采用優(yōu)先隊列時復(fù)雜度O((V+E)logV)C.可用于差分約束系統(tǒng)??D.貪心策略保證最短路徑答案：BD解析：A錯，C為Bellman-Ford應(yīng)用。17.以下哪些操作會使C++vector的迭代器失效A.push_back導(dǎo)致重新分配??B.insert中間元素C.erase尾部元素??D.修改元素值答案：ABC解析：重新分配或移動元素均使迭代器失效。18.關(guān)于Trie樹，下列說法正確的是A.插入復(fù)雜度O(字符串長度)??B.可快速查詢前綴C.必為二叉樹??D.可壓縮為DFA答案：ABD解析：Trie多叉，非必二叉。19.以下哪些排序算法屬于比較排序A.計數(shù)排序??B.歸并排序??C.基數(shù)排序??D.堆排序答案：BD解析：計數(shù)與基數(shù)為非比較排序。20.在Linux下，哪些信號不可被捕獲或忽略A.SIGKILL??B.SIGSTOP??C.SIGTERM??D.SIGSEGV答案：AB解析：SIGKILL與SIGSTOP不可捕獲。三、填空題（每空3分，共30分）21.若int占4字節(jié)，char占1字節(jié)，則union{intx;chary[5];}占__5__字節(jié)。解析：union取最大成員5字節(jié)，按最大對齊4對齊，總5。22.快速選擇算法求第k小元素，平均時間復(fù)雜度__O(n)__。解析：類似快排劃分，平均O(n)。23.設(shè)哈希函數(shù)h(k)=kmod7，采用線性探測，插入序列{8,15,22}后，22所在下標(biāo)為__1__。解析：8→1，15→1沖突→2，22→1沖突→2沖突→3，最終22在3，更正：22mod7=1→1被8占→2被15占→3空，故填3。24.一顆AVL樹最少節(jié)點數(shù)N(h)滿足遞推__N(h)=N(h-1)+N(h-2)+1__，初值N(0)=1,N(1)=2。解析：經(jīng)典AVL最少節(jié)點遞推。25.在模運算中，(a/b)modm等于__a·b^(m-2)modm__，當(dāng)m為質(zhì)數(shù)。解析：費馬小求逆元。26.使用Floyd求傳遞閉包時，中間節(jié)點k的循環(huán)應(yīng)放在__最外層__。解析：k外層次保證子問題正確。27.若二進(jìn)制數(shù)101101左移2位后再算術(shù)右移2位，結(jié)果為__101101__。解析：左移2→10110100，算術(shù)右移2→11110101，若原6位則補符號位1，得111011，更正：設(shè)6位，101101→左2→10110100（8位），算術(shù)右2→11110101，截6位→110101。28.在C++中，typeid(a).name()返回類型名字符串，其頭文件為__<typeinfo>__。29.若CPU緩存行64字節(jié)，則遍歷步長為__16__個int時可觸發(fā)緩存行跳躍，假設(shè)int=4字節(jié)。解析：64/4=16。30.采用主定理求解T(n)=4T(n/2)+n2，得T(n)=__Θ(n2logn)__。解析：符合主定理第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__解析：逗號表達(dá)式依次執(zhí)行，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.給定數(shù)組a[n]，求最長遞增子序列長度，使用lower_bound優(yōu)化：```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.線段樹區(qū)間加，區(qū)間求和：```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;}```六、算法設(shè)計題（共25分）40.（10分）給定n≤1e5個區(qū)間[li,ri]，求最少選擇多少個點使每個區(qū)間至少包含一個點。解：貪心。按右端點升序排序，維護(hù)last=-inf，遍歷若li>last則選ri，更新last=ri。證明：最優(yōu)解交換論證。復(fù)雜度：O(nlogn)。41.（15分）給定長n≤1e5的序列a[i]∈[1,1e6]，求有多少子區(qū)間異或和等于k。解：前綴異或xor[i]，問題轉(zhuǎn)化為求i<j滿足xor[j]^xor[i]=k，即xor[i]=xor[j]^k。用unordered_map<longlong,int>cnt，遍歷j時累加cnt[xor[j]^k]，再插入xor[j]。復(fù)雜度：O(n+1e6)。七、數(shù)學(xué)與復(fù)雜度題（共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個節(jié)點的紅黑樹高度至多為2log(n+1)。解：黑高bh≥h/2，節(jié)點數(shù)n≥2^{bh}-1，得h≤2log(n+1)。八、綜合編程題（共30分）44.（30分）題目：給定一棵n≤2×1e5的無根樹，邊權(quán)為1，q≤1e5次查詢，每次問u到v路徑上第k小邊權(quán)（此處邊權(quán)全1，改為點權(quán)第k?。?。修正：點權(quán)第k小。解：可持久化線段樹+樹上差分。步驟：1.DFS序+主席樹，根到x路徑建版本tree[x]。2.查詢u,v,lca，答案=tree[u]+tree[v]-tree[lca]-tree[fa[lca]]上第k小。3.離散化點權(quán)，主席樹節(jié)點存子樹size。復(fù)雜度：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