信息技術(shù)競(jìng)賽測(cè)試題及答案1.單選題（每題2分，共20分）1.1在IPv6地址2001:0db8:0000:0000:0000:ff00:0042:8329中，使用零壓縮法可簡(jiǎn)寫(xiě)為A.2001:db8::ff00:42:8329B.2001:db8:0:0:ff:42:8329C.2001:db8::ff:9D.2001:db8:::ff00:42:8329答案：A解析：IPv6零壓縮只能出現(xiàn)一次“::”，且必須省略連續(xù)的全0段。A項(xiàng)正確省略了中間5個(gè)0段。1.2某二叉樹(shù)后序遍歷為DABFC，中序遍歷為ADBFC，則其先序遍歷為A.CABDFB.CBADFC.ABDFCD.CBAFD答案：B解析：后序最后訪(fǎng)問(wèn)根，可知根為C；中序中C右側(cè)無(wú)節(jié)點(diǎn)，故右子樹(shù)空；左子樹(shù)中序ADBF，后序DABF，遞歸可得先序CBADF。1.3在Linux中，將文件描述符3重定向到標(biāo)準(zhǔn)錯(cuò)誤，應(yīng)使用A.3>&2B.2>&3C.3<&2D.2<&3答案：A解析：>&表示復(fù)制描述符，3>&2把fd3指向fd2的當(dāng)前目標(biāo)，即標(biāo)準(zhǔn)錯(cuò)誤。1.4若某時(shí)序數(shù)據(jù)庫(kù)采用LSM-Tree，以下哪項(xiàng)操作最耗時(shí)A.順序?qū)慚emTableB.磁盤(pán)flushC.合并SSTableD.布隆過(guò)濾器查詢(xún)答案：C解析：合并SSTable需多路歸并并清理過(guò)期數(shù)據(jù)，磁盤(pán)I/O與CPU開(kāi)銷(xiāo)最大。1.5在Python3中，表達(dá)式`[1,2]*3`的結(jié)果是A.[3,6]B.[1,2,1,2,1,2]C.[1,2,3]D.報(bào)錯(cuò)答案：B解析：列表乘號(hào)表示重復(fù)拼接，而非元素相乘。1.6使用Kruskal算法求最小生成樹(shù)時(shí)，判斷環(huán)需借助A.棧B.隊(duì)列C.并查集D.拓?fù)渑判虼鸢福篊解析：并查集可在近似O(α)時(shí)間內(nèi)判斷兩頂點(diǎn)是否連通。1.7在HTTPS握手階段，服務(wù)器發(fā)送的Certificate消息主要攜帶A.對(duì)稱(chēng)密鑰B.證書(shū)鏈C.會(huì)話(huà)票據(jù)D.橢圓曲線(xiàn)參數(shù)答案：B解析：Certificate用于向客戶(hù)端出示公鑰證書(shū)鏈。1.8若CPU緩存行大小64B，數(shù)組元素double占8B，則步長(zhǎng)為多少時(shí)最可能發(fā)生偽共享A.4B.8C.16D.32答案：B解析：同一緩存行可容納8個(gè)double，若多線(xiàn)程以步長(zhǎng)8訪(fǎng)問(wèn)相鄰元素，則位于同一行。1.9SQL標(biāo)準(zhǔn)中，可重復(fù)讀隔離級(jí)別下，不會(huì)出現(xiàn)A.臟讀B.不可重復(fù)讀C.幻讀D.丟失更新答案：A解析：可重復(fù)讀禁止臟讀與不可重復(fù)讀，但幻讀仍可能出現(xiàn)。1.10在Git中，命令`gitreset--softHEAD~3`會(huì)A.丟棄最近3次提交且工作區(qū)回退B.保留工作區(qū)與暫存區(qū)，僅移動(dòng)HEADC.刪除最近3次提交記錄且暫存區(qū)清空D.生成新分支答案：B解析：--soft僅移動(dòng)HEAD指針，不改變索引與工作目錄。2.多選題（每題3分，共15分，多選少選均不得分）2.1以下哪些HTTP頭部可用來(lái)實(shí)現(xiàn)客戶(hù)端緩存A.ETagB.Last-ModifiedC.ExpiresD.Set-Cookie答案：ABC解析：ETag與Last-Modified用于條件請(qǐng)求，Expires指定過(guò)期時(shí)間，Set-Cookie與會(huì)話(huà)相關(guān)。2.2關(guān)于RAID5，描述正確的有A.允許單盤(pán)故障B.寫(xiě)入需計(jì)算校驗(yàn)C.容量利用率(n-1)/nD.最少需4塊盤(pán)答案：ABC解析：RAID5最少3塊盤(pán)即可。2.3以下哪些屬于穩(wěn)定排序算法A.歸并排序B.堆排序C.冒泡排序D.計(jì)數(shù)排序答案：ACD解析：堆排序不穩(wěn)定。2.4在C語(yǔ)言中，關(guān)于`volatile`關(guān)鍵字，正確的有A.禁止編譯器優(yōu)化該變量B.保證原子性C.適用于訪(fǎng)問(wèn)硬件寄存器D.與并發(fā)安全無(wú)關(guān)答案：ACD解析：volatile不保證原子性，需配合鎖或原子操作。2.5以下哪些設(shè)計(jì)模式可降低系統(tǒng)耦合A.觀察者B.工廠方法C.單例D.適配器答案：ABD解析：?jiǎn)卫饕刂茖?shí)例數(shù)量，不直接降低耦合。3.填空題（每空2分，共20分）3.1若某無(wú)向圖有n個(gè)頂點(diǎn)、e條邊，使用鄰接矩陣存儲(chǔ)，空間復(fù)雜度為_(kāi)_______。答案：O(n2)3.2在TCP首部中，用于流量控制的字段是________。答案：WindowSize3.3若某系統(tǒng)采用二級(jí)頁(yè)表，頁(yè)大小4KB，地址寬度48位，則頁(yè)內(nèi)偏移占________位。答案：123.4在MySQL8.0中，默認(rèn)的認(rèn)證插件為_(kāi)_______。答案：caching_sha2_password3.5若某算法時(shí)間復(fù)雜度為T(mén)(n)=4T(n/2)+O(n2)，根據(jù)主定理，其復(fù)雜度為_(kāi)_______。答案：O(n2logn)3.6在RSA加密中，若公鑰指數(shù)e=3，則私鑰指數(shù)d需滿(mǎn)足3d≡1mod________。答案：φ(n)3.7在CSS中，選擇器`.item:nth-child(2n+1)`匹配第________個(gè)子元素。答案：奇數(shù)3.8若某SSD的擦除單位大小為256KB，寫(xiě)入單位4KB，則寫(xiě)入放大系數(shù)最小理論值為_(kāi)_______。答案：643.9在Python中，使用`with`語(yǔ)句管理資源時(shí)，對(duì)象需實(shí)現(xiàn)________方法。答案：`__enter__`與`__exit__`3.10在機(jī)器學(xué)習(xí)中，F(xiàn)1分?jǐn)?shù)是精確率與召回率的________平均。答案：調(diào)和4.程序閱讀題（每題5分，共15分）4.1閱讀以下C++代碼，寫(xiě)出輸出結(jié)果：```cppinclude<iostream>template<intN>structFact{staticconstintval=N*Fact<N-1>::val;};template<>structFact<0>{staticconstintval=1;};intmain(){std::cout<<Fact<5>::val<<std::endl;}```答案：120解析：編譯期遞歸計(jì)算階乘，5!=120。4.2閱讀以下Python代碼，寫(xiě)出輸出結(jié)果：```pythondeffoo(x=[]):x.append(1)returnxprint(foo(),foo(),sep='-')```答案：[1]-[1,1]解析：默認(rèn)參數(shù)在函數(shù)定義時(shí)求值，列表x為可變對(duì)象，狀態(tài)持續(xù)。4.3閱讀以下SQL語(yǔ)句，寫(xiě)出查詢(xún)結(jié)果（僅寫(xiě)出數(shù)字）：表T結(jié)構(gòu)(idint,valint)，數(shù)據(jù)：(1,10),(2,20),(3,30)```sqlSELECTSUM(val)FILTER(WHEREid<=2)FROMT;```答案：30解析：PostgreSQL支持FILTER子句，僅對(duì)id≤2的行求和。5.編程填空題（每空3分，共15分）5.1補(bǔ)全快速排序的partition函數(shù)，使數(shù)組升序：```cppintpartition(inta[],intl,intr){intpivot=a[r],i=l;for(intj=l;j<r;++j){if(a[j]<pivot){std::swap(a[i],a[j]);________;}}std::swap(a[i],a[r]);returni;}```答案：`++i`5.2補(bǔ)全Python生成器，實(shí)現(xiàn)斐波那契無(wú)限序列：```pythondeffib():a,b=0,1whileTrue:yieldaa,b=b,________```答案：`a+b`5.3補(bǔ)全Java代碼，使用雙重檢查鎖定實(shí)現(xiàn)線(xiàn)程安全單例：```javaclassSingleton{privatestaticvolatileSingletoninst;privateSingleton(){}staticSingletonget(){if(inst==null){synchronized(Singleton.class){if(______)inst=newSingleton();}}returninst;}}```答案：`inst==null`5.4補(bǔ)全Go代碼，實(shí)現(xiàn)并發(fā)安全計(jì)數(shù)器：```gotypeCounterstruct{musync.Mutexnint64}func(c*Counter)Inc(){c.mu.________c.n++c.mu.________}```答案：`Lock()`、`Unlock()`5.5補(bǔ)全SQL，將表user中name字段重復(fù)行保留id最大者：```sqlDELETEFROMuserWHEREidNOTIN(SELECT________FROMuserGROUPBYname);```答案：`MAX(id)`6.算法設(shè)計(jì)題（共30分）6.1（10分）給定長(zhǎng)度為n的整數(shù)數(shù)組，求最長(zhǎng)嚴(yán)格遞增子序列長(zhǎng)度。n≤10?，元素范圍[-10?,10?]。要求：寫(xiě)出核心算法思路、偽代碼、時(shí)間復(fù)雜度。答案：思路：使用patiencesorting優(yōu)化，維護(hù)tails數(shù)組，tails[i]記錄長(zhǎng)度為i+1的LIS最小末尾。偽代碼：```tails=[]forxinarr:idx=lower_bound(tails,x)#首個(gè)≥x的位置ifidx==len(tails):tails.append(x)else:tails[idx]=xreturnlen(tails)```時(shí)間復(fù)雜度：O(nlogn)6.2（10分）設(shè)計(jì)分布式限流器，支持每秒百萬(wàn)級(jí)請(qǐng)求，多節(jié)點(diǎn)共享配額。要求：說(shuō)明數(shù)據(jù)結(jié)構(gòu)與一致性方案，給出偽代碼。答案：采用令牌桶+Redis+Lua腳本。結(jié)構(gòu)：key格式`bucket:{api}`，字段`tokens`剩余令牌數(shù)，`last_refill`上次填充時(shí)間。Lua腳本原子執(zhí)行：```localrate=tonumber(ARGV[1])localburst=tonumber(ARGV[2])localnow=tonumber(ARGV[3])localkey=KEYS[1]localbucket=redis.call('HMGET',key,'tokens','last')localtokens=tonumber(bucket[1])orburstlocallast=tonumber(bucket[2])ornowlocaldelta=math.min((nowlast)*rate,bursttokens)tokens=tokens+deltalocalallowed=tokens>=1ifallowedthentokens=tokens1endredis.call('HMSET',key,'tokens',tokens,'last',now)returnallowed```一致性：Redis單線(xiàn)程執(zhí)行Lua，保證原子性；多節(jié)點(diǎn)共享配額。6.3（10分）給定10億個(gè)URL，每個(gè)64B，內(nèi)存限制1GB，去重并統(tǒng)計(jì)出現(xiàn)次數(shù)前100的URL。要求：給出外部排序+哈希+堆的完整流程，計(jì)算I/O次數(shù)。答案：步驟：1.順序讀取文件，按hash(url)%2000分桶寫(xiě)入2000個(gè)臨時(shí)文件，每文件約50MB，內(nèi)存占用<500MB。2.對(duì)每個(gè)小文件，使用哈希表去重并統(tǒng)計(jì)頻次，寫(xiě)入<(url,count)>有序中間文件。3.多路歸并中間文件，同時(shí)維護(hù)100大小的小頂堆，保留全局Top100。I/O：分桶階段：讀10GB，寫(xiě)10GB歸并階段：讀10GB，寫(xiě)0（僅輸出Top100）總I/O≈30GB，機(jī)械盤(pán)約5分鐘。7.系統(tǒng)綜合題（共20分）7.1（10分）某微服務(wù)集群高峰期出現(xiàn)“部分接口超時(shí)但CPU利用率低”現(xiàn)象，給出排查清單與工具。答案：清單：1.網(wǎng)絡(luò)延遲：tcpdump+Wireshark抓包，查看RTT與重傳。2.連接池耗盡：監(jiān)控連接池active/idle，使用netstat-ant|grepESTABLISHED。3.線(xiàn)程池饑餓：jstack查看WAITING線(xiàn)程，Arthasthread命令。4.GC停頓：jstat–gc查看FullGC次數(shù)與時(shí)間，GC日志分析。5.數(shù)據(jù)庫(kù)慢查詢(xún)：開(kāi)啟slow_query_log，pt-query-digest分析。6.鎖競(jìng)爭(zhēng)：MySQL的performance_schema或Redis的SLOWLOG。7.磁盤(pán)I/O：iostat-x1查看%util與await。8.容器限流：檢查Kubernetes的CPUthrottle，cat/sys/fs/cgroup/…/cpu.stat。7.2（10分）設(shè)計(jì)一個(gè)可水平擴(kuò)展的IM消息系統(tǒng)，支持單聊、群聊、已讀回執(zhí)，日活1億，峰值QPS500萬(wàn)。要求：畫(huà)出核心架構(gòu)圖，說(shuō)明消息可靠投遞、順序、存儲(chǔ)選型。答案：架構(gòu)：接入層：多地域WebSocket集群，基于Netty，無(wú)狀態(tài)，支持水平擴(kuò)展。路由層：一致性哈希按uid分片，維護(hù)用戶(hù)→網(wǎng)關(guān)映射，使用RedisCluster存儲(chǔ)在線(xiàn)狀態(tài)。消息隊(duì)列：Kafka分區(qū)按會(huì)話(huà)id