考研計算機學科專業(yè)基礎(408)研究生考試試題與參考答案2025年一、單項選擇題（每小題2分，共80分）數(shù)據(jù)結(jié)構部分1.已知一棵完全二叉樹有768個節(jié)點，其中葉子節(jié)點的個數(shù)是（）。A.383B.384C.385D.3862.對圖G進行拓撲排序時，不可能得到的序列是（）。圖G的鄰接表表示為：0→1,2；1→3；2→3；3→4；4→?。A.0,1,2,3,4B.0,2,1,3,4C.0,1,3,2,4D.0,2,1,4,33.設哈希表長度為13（地址0-12），哈希函數(shù)H(key)=key%13，采用線性探測法處理沖突。依次插入關鍵字26、14、37、42、50，此時查找關鍵字50的平均查找長度為（）。A.1B.2C.3D.44.對序列{5,3,8,6,7,2,4,1}進行快速排序，以第一個元素為樞軸，第一趟劃分后的序列是（）。A.{1,3,2,4,5,7,6,8}B.{4,3,2,1,5,7,6,8}C.{2,3,4,1,5,7,6,8}D.{3,2,4,1,5,8,6,7}5.已知某二叉樹的后序遍歷序列為D、E、B、F、C、A，中序遍歷序列為D、B、E、A、F、C，則前序遍歷序列為（）。A.A、B、D、E、C、FB.A、B、D、E、F、CC.A、B、E、D、C、FD.A、C、F、B、D、E計算機組成原理部分6.若浮點數(shù)格式為階碼4位（含1位符號位，移碼表示），尾數(shù)8位（含1位符號位，補碼表示），則該浮點數(shù)能表示的最大正數(shù)為（）。A.(1-2??)×2?B.(1-2??)×2?C.(1-2??)×2?D.(1-2??)×2?7.某計算機主存地址32位，按字節(jié)編址，Cache容量64KB，塊大小128B，采用4路組相聯(lián)映射。主存地址中組號的位數(shù)是（）。A.10B.11C.12D.138.某指令系統(tǒng)中，指令字長16位，操作碼4位，采用擴展操作碼技術。若三地址指令有15條，二地址指令最多有（）條。A.15B.16C.31D.329.某CPU的時鐘頻率為2GHz，某程序包含10?條指令，CPI為1.5，則執(zhí)行該程序的時間為（）。A.0.5sB.0.75sC.1sD.1.5s10.下列關于DRAM刷新的描述中，錯誤的是（）。A.刷新操作按行進行B.集中刷新會產(chǎn)生死時間C.分散刷新會降低內(nèi)存速度D.異步刷新的間隔為2ms操作系統(tǒng)部分11.進程從運行態(tài)轉(zhuǎn)換為阻塞態(tài)的原因是（）。A.時間片用完B.等待I/O完成C.被調(diào)度程序選中D.等待的I/O完成12.系統(tǒng)有3個同類資源，進程P1、P2、P3的最大需求分別為2、2、2，當前已分配1、1、0。若P3申請1個資源，系統(tǒng)（）。A.處于安全狀態(tài)B.進入死鎖C.不安全但未死鎖D.無法判斷13.某分頁系統(tǒng)的邏輯地址16位，頁大小4KB，頁表項占4B，采用一級頁表。頁表需要的最大內(nèi)存空間是（）。A.4KBB.8KBC.16KBD.32KB14.下列文件物理結(jié)構中，支持隨機訪問且空間利用率最高的是（）。A.連續(xù)結(jié)構B.隱式鏈接結(jié)構C.顯式鏈接結(jié)構D.索引結(jié)構15.下列關于SPOOLing技術的描述中，錯誤的是（）。A.需共享打印機B.利用磁盤作為輸入井/輸出井C.緩和CPU與I/O設備速度不匹配D.實現(xiàn)了虛擬設備計算機網(wǎng)絡部分16.下列屬于數(shù)據(jù)鏈路層功能的是（）。A.路由選擇B.流量控制C.端到端可靠傳輸D.物理地址轉(zhuǎn)換17.某C類網(wǎng)絡192.168.1.0/24，若劃分子網(wǎng)，每個子網(wǎng)至少50臺主機，則子網(wǎng)掩碼應為（）。A.255.255.255.128B.255.255.255.192C.255.255.255.224D.255.255.255.24018.下列TCP報文中，不包含確認號字段的是（）。A.SYNB.ACKC.FIND.RST19.若主機A通過CSMA/CD向主機B發(fā)送數(shù)據(jù)，傳播時延為20μs，最短幀長應為（）。A.40bitB.80bitC.400bitD.800bit20.下列關于DNS查詢的描述中，正確的是（）。A.遞歸查詢要求本地域名服務器承擔全部查詢B.迭代查詢中根域名服務器返回最終IPC.客戶端只能發(fā)起遞歸查詢D.反向查詢根據(jù)IP查域名二、綜合應用題（共70分）數(shù)據(jù)結(jié)構（22分）21.（10分）已知帶頭結(jié)點的單鏈表L存儲整數(shù)，設計算法將L中所有奇數(shù)移到偶數(shù)前面，要求時間復雜度O(n)，空間復雜度O(1)。（用C語言描述）22.（12分）某無向圖G的鄰接矩陣如下（頂點編號0-4）：\[\begin{bmatrix}0&1&0&1&0\\1&0&1&1&1\\0&1&0&0&1\\1&1&0&0&1\\0&1&1&1&0\\\end{bmatrix}\]（1）畫出G的鄰接表表示；（4分）（2）寫出從頂點0出發(fā)的廣度優(yōu)先遍歷（BFS）序列（假設訪問順序按頂點編號升序）；（4分）（3）計算G的邊數(shù)和頂點0的度。（4分）計算機組成原理（22分）23.（10分）某計算機主存地址20位，按字節(jié)編址，使用8K×8位的SRAM芯片構成64KB主存。（1）需要多少片SRAM芯片？（2分）（2）畫出主存地址分配圖（標出片內(nèi)地址、片選地址位數(shù)）；（6分）（3）若采用全譯碼法，片選信號由哪幾位地址線產(chǎn)生？（2分）24.（12分）某指令系統(tǒng)有32位指令，包含操作碼（6位）、源寄存器R1（5位）、源寄存器R2（5位）、目的寄存器Rd（5位）、立即數(shù)（11位）。支持以下尋址方式：-寄存器尋址：操作數(shù)在R1/R2-立即尋址：操作數(shù)為立即數(shù)-直接尋址：有效地址=立即數(shù)（16位）-寄存器間接尋址：有效地址=R1的內(nèi)容（1）若指令需支持上述四種尋址方式，操作碼應如何設計？（4分）（2）對于指令“ADDRd,R1,R2”（寄存器尋址），寫出指令各字段的具體內(nèi)容；（4分）（3）對于指令“LOADRd,[R1]”（寄存器間接尋址），若R1的內(nèi)容為0x2000，主存0x2000處存儲0x3000，0x3000處存儲0x4000，求Rd的最終值（假設按字編址，字長32位）。（4分）操作系統(tǒng)（16分）25.（8分）系統(tǒng)有5個哲學家，共享5根筷子，每根筷子只能被1人使用。設計信號量機制解決“哲學家進餐問題”，要求避免死鎖。（需給出信號量定義、初始化值及偽代碼）26.（8分）某請求分頁系統(tǒng)，頁大小4KB，頁表項占8B，TLB命中率90%，內(nèi)存訪問時間100ns，缺頁率0.1%，缺頁處理時間10ms（含頁表更新和TLB更新）。計算有效訪問時間（EAT）。計算機網(wǎng)絡（10分）27.（10分）某網(wǎng)絡拓撲如下：-路由器R1連接子網(wǎng)A（192.168.1.0/24）和子網(wǎng)B（192.168.2.0/24）-路由器R2連接子網(wǎng)B（192.168.2.0/24）和子網(wǎng)C（192.168.3.0/24）-R1與R2通過廣域網(wǎng)接口相連，IP地址分別為10.0.0.1/30和10.0.0.2/30（1）寫出R1的路由表（包含目的網(wǎng)絡、子網(wǎng)掩碼、下一跳、接口）；（6分）（2）若子網(wǎng)A中主機192.168.1.10向子網(wǎng)C中主機192.168.3.20發(fā)送數(shù)據(jù)，簡述數(shù)據(jù)報的轉(zhuǎn)發(fā)過程。（4分）參考答案一、單項選擇題1.B2.C3.C4.B5.A6.A7.A8.C9.B10.D11.B12.A13.C14.A15.A16.B17.B18.A19.C20.A二、綜合應用題21.算法思路：維護兩個指針，odd指向最后一個奇數(shù)節(jié)點，even遍歷鏈表。當遇到奇數(shù)時，將其插入到odd之后，并更新odd；遇到偶數(shù)則繼續(xù)遍歷。代碼實現(xiàn)：```cvoidMoveOddToFront(LinkListL){LNodeodd=L,even=L->next;while(even!=NULL){if(even->data%2==1){//奇數(shù)節(jié)點LNodep=even;even=even->next;p->next=odd->next;odd->next=p;odd=p;}else{//偶數(shù)節(jié)點even=even->next;}}}```22.（1）鄰接表：0:1→3→?1:0→2→3→4→?2:1→4→?3:0→1→4→?4:1→2→3→?（2）BFS序列：0→1→3→2→4（訪問順序按頂點編號升序，隊列處理）（3）邊數(shù)：鄰接矩陣中1的個數(shù)/2=(2+4+2+3+3)/2=7條；頂點0的度=鄰接矩陣第0行1的個數(shù)=2（無向圖度=邊數(shù)）23.（1）主存容量64KB=64×1024×8bit，芯片容量8K×8bit，故需要64K/8K=8片。（2）地址分配：主存地址20位，片內(nèi)地址=log2(8K)=13位（8K=213），片選地址=20-13=7位。地址線A0-A12為片內(nèi)地址，A13-A19為片選地址（共7位）。（3）全譯碼法中，片選信號由高位地址線A13-A19經(jīng)譯碼器產(chǎn)生，每個芯片對應唯一的片選信號。24.（1）操作碼6位，用高2位表示尋址方式（00:寄存器，01:立即，10:直接，11:寄存器間接），剩余4位表示具體操作。（2）“ADDRd,R1,R2”為寄存器尋址，操作碼前2位00，后4位為ADD的編碼（如0001），R1、R2、Rd字段分別填對應寄存器號，立即數(shù)字段無意義（填0）。（3）寄存器間接尋址時，有效地址=R1內(nèi)容=0x2000，主存0x2000處存儲0x3000（這是間接地址），實際操作數(shù)在0x3000處，值為0x4000，故Rd=0x4000。25.信號量定義：mutex（互斥取筷子，初值1），chopstick[5]（每根筷子，初值1）。偽代碼：```semaphoremutex=1;semaphorechopstick[5]={1,1,1,1,1};voidphilosopher(inti){while(1){think();wait(mutex);//互斥取筷子wait(chopstick[i]);//取左筷子wait(chopstick[(i+1)%5]);//取右筷子signal(mutex);//釋放互斥eat();signal(chopstick[i]);//放左筷子signal(chopstick[(i+1)%5]);//放右筷子}}```26.EAT=TLB命中時的訪問時間+TLB未命中時的訪問時間=0.9×(100ns)+0.1×[100ns（訪問內(nèi)存頁表）+100ns（訪問數(shù)據(jù)）]+0.1%×[缺頁處理時間+2×100ns]=90ns+0.1×200ns+0.001×(10ms+200ns)≈90ns+20ns+10μs≈10.11μs27.（1）R1路由表：-目的網(wǎng)絡192.168.1.0，子網(wǎng)掩碼255.255.255.0，下一跳-，接口子網(wǎng)A-目的網(wǎng)絡192.168.2.0，子網(wǎng)掩碼255.255.255.0，下一跳-，接口子網(wǎng)B-