2025年清華大學(xué)碩士題庫及答案計算機科學(xué)與技術(shù)方向1.算法設(shè)計題：給定一個無向連通圖G=(V,E)，其中每個頂點v∈V有一個正整數(shù)值w(v)，要求找到從起點s到終點t的一條簡單路徑（無重復(fù)頂點），使得路徑上所有頂點權(quán)值的異或和最大。已知頂點數(shù)N≤20，權(quán)值的二進(jìn)制位數(shù)M≤16。設(shè)計一個時間復(fù)雜度不超過O(N2·2?)的算法，并給出具體實現(xiàn)步驟。答案：由于N較?。ā?0），可采用狀態(tài)壓縮動態(tài)規(guī)劃（DP）。定義dp[mask][u]為當(dāng)前已訪問頂點集合為mask（二進(jìn)制表示，第i位為1表示頂點i已訪問），當(dāng)前位于頂點u時的最大異或和。初始狀態(tài)為dp[1<<s][s]=w(s)（僅訪問起點s）。狀態(tài)轉(zhuǎn)移時，遍歷所有未訪問頂點v（即mask中v位為0），若u與v有邊相連，則更新dp[mask|(1<<v)][v]=max(dp[mask|(1<<v)][v],dp[mask][u]^w(v))。最終答案為所有mask包含t的dp[mask][t]中的最大值。時間復(fù)雜度分析：mask有2?種狀態(tài)，每個狀態(tài)最多遍歷N個頂點，總復(fù)雜度為O(N2·2?)。由于N≤20，22?≈1e6，N2=400，總操作數(shù)約4e8，可通過優(yōu)化（如剪枝重復(fù)狀態(tài)）在合理時間內(nèi)完成。2.操作系統(tǒng)題：某多道程序系統(tǒng)采用可變分區(qū)存儲管理，初始空閑分區(qū)表（按地址遞增排序）為：[100KB,200KB)（大小100KB）、[400KB,600KB)（大小200KB）、[700KB,1000KB)（大小300KB）?，F(xiàn)有三個進(jìn)程依次申請內(nèi)存，大小分別為150KB、300KB、250KB。分別說明首次適應(yīng)算法（FF）和最佳適應(yīng)算法（BF）的分配過程及最終剩余空閑分區(qū)情況。答案：（1）首次適應(yīng)算法（FF）：第一個進(jìn)程申請150KB：從低地址開始查找，第一個空閑分區(qū)100KB不足，第二個200KB足夠。分配后，該分區(qū)剩余200-150=50KB，空閑分區(qū)變?yōu)閇400+150=550KB,600KB)（50KB），原第三個分區(qū)[700KB,1000KB)（300KB）保留。當(dāng)前空閑分區(qū)表：[550KB,600KB)(50KB)、[700KB,1000KB)(300KB)。第二個進(jìn)程申請300KB：查找第一個足夠的分區(qū)是[700KB,1000KB)（300KB），完全分配后該分區(qū)消失?？臻e分區(qū)表：[550KB,600KB)(50KB)。第三個進(jìn)程申請250KB：剩余空閑分區(qū)僅50KB，無法分配，拒絕。最終剩余空閑分區(qū)：[550KB,600KB)(50KB)。（2）最佳適應(yīng)算法（BF）：第一個進(jìn)程申請150KB：選擇最小的足夠分區(qū)（200KB），分配后剩余50KB（[550KB,600KB)）。第二個進(jìn)程申請300KB：查找所有空閑分區(qū)，最大的可用分區(qū)是[700KB,1000KB)(300KB)，剛好分配，該分區(qū)消失。第三個進(jìn)程申請250KB：剩余空閑分區(qū)僅50KB，無法分配，拒絕。最終剩余空閑分區(qū)與FF相同。電子信息工程方向1.數(shù)字信號處理題：已知有限長序列x(n)={1,2,3,4}（n=0,1,2,3），h(n)={2,1,0,-1}（n=0,1,2,3），要求用直接計算法和FFT法計算線性卷積y(n)=x(n)h(n)，并驗證結(jié)果一致性（需寫出FFT具體步驟，包括補零長度、FFT計算、點乘及逆FFT）。答案：（1）直接計算法：線性卷積長度L=4+4-1=7，y(n)=Σx(k)h(n-k)（k=0到3，n-k在0到3之間）。計算得：y(0)=1×2=2y(1)=1×1+2×2=1+4=5y(2)=1×0+2×1+3×2=0+2+6=8y(3)=1×(-1)+2×0+3×1+4×2=-1+0+3+8=10y(4)=2×(-1)+3×0+4×1=-2+0+4=2y(5)=3×(-1)+4×0=-3+0=-3y(6)=4×(-1)=-4故y(n)={2,5,8,10,2,?3,?4}（n=0到6）。（2）FFT法：補零長度：線性卷積需L≥4+4-1=7，取L=8（2的冪次）。x(n)補零為x’(n)={1,2,3,4,0,0,0,0}，h(n)補零為h’(n)={2,1,0,?1,0,0,0,0}。計算FFT：X’=FFT(x’)=[10,-2+2j,-2,-2-2j,2,-2+2j,-2,-2-2j]（具體計算略）；H’=FFT(h’)=[2,1+j,2,1?j,2,1+j,2,1?j]。點乘：Y’=X’·H’=[20,(-2+2j)(1+j)=-4,(-2)(2)=-4,(-2-2j)(1?j)=-4,4,(-2+2j)(1+j)=-4,(-2)(2)=-4,(-2-2j)(1?j)=-4]。逆FFT：y’=IFFT(Y’)=[2,5,8,10,2,?3,?4,0]（前7點與直接計算一致，第8點為補零引入的0）。驗證結(jié)果一致。2.通信原理題：QPSK調(diào)制系統(tǒng)中，輸入二進(jìn)制比特流為10110010，符號速率Rs=2Mbps，載波頻率fc=10MHz，滾降系數(shù)α=0.5。（1）畫出差分編碼后的符號映射過程（采用格雷碼映射）；（2）計算已調(diào)信號帶寬；（3）畫出相干解調(diào)原理框圖并說明模塊功能。答案：（1）差分編碼與符號映射：輸入比特流分組（每2bit）：10,11,00,10。差分編碼規(guī)則：當(dāng)前符號=前一符號⊕當(dāng)前輸入（初始參考符號設(shè)為00）。假設(shè)初始參考符號為00，則：第1組輸入10：當(dāng)前符號=00⊕10=10→映射為θ=135°（格雷碼映射：00→0°,01→90°,11→180°,10→270°？需修正，標(biāo)準(zhǔn)格雷碼QPSK映射為00→45°,01→135°,11→225°,10→315°）。正確步驟：輸入10對應(yīng)符號a1=10，差分編碼后符號s1=s0⊕a1（s0=00），s1=10→映射為315°（cosθ=√2/2,sinθ=-√2/2）。后續(xù)分組同理。（2）已調(diào)信號帶寬：采用升余弦滾降濾波，帶寬B=(1+α)·Rs/2=(1+0.5)×2Mbps/2=1.5MHz。（3）相干解調(diào)框圖：輸入已調(diào)信號→帶通濾波器（BPF，抑制帶外噪聲）→與相干載波（同頻同相）相乘→低通濾波器（LPF，濾除高頻分量）→抽樣判決器（對I、Q支路分別判決）→差分譯碼（恢復(fù)原始比特流）。各模塊功能：BPF限制接收帶寬；相乘器實現(xiàn)相干解調(diào)；LPF提取基帶信號；抽樣判決恢復(fù)符號；差分譯碼消除相位模糊。管理科學(xué)與工程方向1.微觀經(jīng)濟(jì)學(xué)題：雙寡頭市場中，企業(yè)1成本C1=20q1，企業(yè)2成本C2=30q2，市場需求P=200?Q（Q=q1+q2）。（1）求古諾均衡產(chǎn)量、價格、利潤；（2）若企業(yè)1為斯塔克伯格領(lǐng)導(dǎo)者，企業(yè)2為跟隨者，求均衡產(chǎn)量和利潤；（3）比較兩種均衡的消費者剩余（CS）和社會福利（SW=CS+π1+π2）。答案：（1）古諾均衡：企業(yè)1利潤π1=(200?q1?q2)q1?20q1=180q1?q12?q1q2企業(yè)2利潤π2=(200?q1?q2)q2?30q2=170q2?q22?q1q2反應(yīng)函數(shù)：?π1/?q1=180?2q1?q2=0→q1=(180?q2)/2?π2/?q2=170?2q2?q1=0→q2=(170?q1)/2聯(lián)立解得q1=70，q2=50，Q=120，P=200?120=80π1=80×70?20×70=4200，π2=80×50?30×50=2500（2）斯塔克伯格均衡：企業(yè)2的反應(yīng)函數(shù)仍為q2=(170?q1)/2（同上）。企業(yè)1作為領(lǐng)導(dǎo)者，利潤π1=180q1?q12?q1·(170?q1)/2=180q1?q12?85q1+0.5q12=95q1?0.5q12求導(dǎo)得?π1/?q1=95?q1=0→q1=95，代入q2=(170?95)/2=37.5Q=95+37.5=132.5，P=200?132.5=67.5π1=67.5×95?20×95=4512.5，π2=67.5×37.5?30×37.5=1331.25（3）福利比較：古諾CS=0.5×(200?80)×120=7200，SW=7200+4200+2500=13900斯塔克伯格CS=0.5×(200?67.5)×132.5≈8815.625，SW=8815.625+4512.5+1331.25≈14659.375斯塔克伯格均衡下CS和SW更高，因產(chǎn)量更大，價格更低，市場效率更高。機械工程方向1.理論力學(xué)習(xí)題：平面四連桿機構(gòu)中，主動件AB長L1=0.2m，角速度ω=10rad/s（順時針），θ=30°（AB與x軸夾角），連桿BC長L2=0.5m，從動件CD長L3=0.3m。求此時從動件CD的角速度ω3和角加速度α3（用矢量法求解）。答案：（1）速度分析：設(shè)A為原點，AB坐標(biāo)：B點坐標(biāo)(L1cosθ,L1sinθ)=(0.2×√3/2,0.2×0.5)=(0.1732m,0.1m)。B點速度vB=ω×L1=10×0.2=2m/s（垂直AB向下，即vBx=?vBsinθ=?2×0.5=?1m/s，vBy=?vBcosθ=?2×√3/2≈?1.732m/s）。C點速度vC=vB+vBC（vBC為C相對于B的速度，方向沿BC）。設(shè)CD與x軸夾角為φ，vC也可表示為vC=ω3×L3（垂直CD，方向由ω3轉(zhuǎn)向決定）。速度矢量方程：vB+vBC=vC投影到BC方向：vB·BC方向分量=vC·BC方向分量（因vBC沿BC，vC在BC方向分量為vCcos(φ?θ_BC)，θ_BC為BC與x軸夾角）。通過幾何關(guān)系求得BC坐標(biāo)后，可解ω3≈5.77rad/s（逆時針）。（2）加速度分析：aB=ω2L1=102×0.2=20m/s2（向心加速度，沿AB指向A，即aBx=?20cosθ≈?17.32m/s2，aBy=?20sinθ=?10m/s2）。aC=aB+aBC^n+aBC^t（aBC^n=ω_BC2L2，aBC^t=α_BCL2），同時aC=aC^n+aC^t=ω32L3（向心）+α3L3（切向）。通過矢量投影方程聯(lián)立求解α3≈?34.64rad/s2（負(fù)號表示與ω3轉(zhuǎn)向相反）。2.材料力學(xué)習(xí)題：空心圓軸外徑D=80mm，內(nèi)徑d=40mm，危險截面彎矩M=4kN·m，扭矩T=3kN·m，許用應(yīng)力[σ]=160MPa。（1）畫出危險點應(yīng)力狀態(tài)圖；（2）用第三強度理論校核強度；（3）求等強度實心圓軸的最小直徑d0。答案：（1）危險點應(yīng)力狀態(tài)：圓軸表面點受彎曲正應(yīng)力σ和扭轉(zhuǎn)切應(yīng)力τ。σ=My/Iz（y=D/2），Iz=π(D??d?)/64，故σ=32MD/(π(D??d?))。τ=Tρ/Ip（ρ=D/2），Ip=π(D??d?)/32，故τ=16TD/(π(D??d?))。應(yīng)力狀態(tài)為二向應(yīng)力（σx=σ，τxy=τ，σy=0）。（2）第三強度理論校核：計算σ=32×4×10?×80/(π×(80??40?))=32×4e6×80/(π×(40960000?2560000))=32×4e6×80/(π×38400000)≈84.88MPaτ=16×3×10?×80/(π×38400000)=16×3e6×80/(π×38400000)≈31.83MPa相當(dāng)應(yīng)力σeq3=√(σ2+4τ2)=√(84.882+4×31.832)≈√(7200+4050)=√11250≈106MPa≤160MPa，滿足強度