2023年考研計算機408統(tǒng)考真題及答案解析

2023年408真題及答案1.對順序存儲的有序表(長度為n)操作時間復(fù)雜度為0(1)的是A查找特定元素B插入特定元素C刪除指定位置元素D讀出指定位置元素2.在雙向鏈表中，p指向的結(jié)點后面插入一個結(jié)點s,鏈表節(jié)點結(jié)構(gòu)如下，現(xiàn)已完成As->next->prev=p;S->preDp->next->prev=S->pr3.三元組方式存儲稀疏矩陣，除三元組外，以下必須要保存的東西是?I矩陣總行數(shù)Ⅱ矩陣中含非零元素的行數(shù)I矩陣總列數(shù)Ⅱ矩陣中含非零元素的列數(shù)4.在由6個字符組成的字符集S中，各字符出現(xiàn)的頻次分別為3,4,5,6,8,10,為S構(gòu)造的哈夫曼編碼的加權(quán)平均長度為A2.4B2.55.已知一棵二叉樹的樹型如下圖所示，若其后序遍歷序列為fdbeca,則其先序遍歷序列是?6.對于邊權(quán)值都為1的無向圖，可以求出某一點到其他所有點的最短路徑的是?I普里姆算法Ⅱ克魯斯卡爾算法Ⅲ廣度優(yōu)先遍歷BFS7.下面關(guān)于非空B樹的說法正確的是?I插入可能會增加樹的高度Ⅱ刪除節(jié)點一定會改變?nèi)~節(jié)點ⅢB樹查找一定會查找到葉節(jié)點IV插入節(jié)點最終一定在葉節(jié)點上9.散列函數(shù)hey=(x+4)%5,處理沖突采用線性探測法，插入2022,12,25,再刪除25,求查找失01234數(shù)據(jù)失敗次數(shù)13212I希爾排序Ⅱ歸并排序Ⅲ快速排序IV堆排序V基數(shù)排序A11組成原理：C通用寄存器編號D通用寄存器的內(nèi)容少?A-212B-1.01*2127【解析】單精度(32位)值雙精度(64位)值階碼尾數(shù)階碼尾數(shù)00000000負零1001000255(全1)0002047(全1)00負無窮大1255(全1)012047(全1)0-無定義數(shù)(非數(shù))0或1255(全1)0或12047(全1)0f2-127(1.0f1f1f-2-1023(1.)000010-2-126(0.)10RAM的地址為?16.CPU主頻為1.5GHz,P指令數(shù)為5*10°,平均CPA0.8,0.4msC1.25,0.4ms18.元件分為兩類，組合邏輯元件(也稱操作元件)和時序邏輯元件(也稱狀態(tài)元件)。以下C僅Ⅱ、Ⅲ19.某系統(tǒng)采用五段式指令流水線(IF、ID、EX、M、WB),采用數(shù)據(jù)旁路技術(shù)解決數(shù)據(jù)沖突，采用硬件阻塞方式處理控制沖突。題目給了四條指令，問會導(dǎo)致流水線阻塞的是哪幾條?(不太確定，如果誰還記得題目信息，請聯(lián)系我們)20.主存塊大小是32B,存儲器每次可以準(zhǔn)備64位數(shù)據(jù)(準(zhǔn)備需要6ns),無猝發(fā)傳輸，總線寬度是64位，總線頻率是1GHz,問讀取一個主存塊時間為A8ns21.以下關(guān)于中斷的說法錯誤的是?A指令執(zhí)行過程中會檢測是否有異常B指令執(zhí)行結(jié)束會檢測是否有中斷C開中斷時一旦檢測到有中斷就會立刻響應(yīng)D由中斷控制器向CPU報告中斷結(jié)束【解析】在支持多重中斷的系統(tǒng)中，當(dāng)CPU正在處理一個高優(yōu)先級中斷時，若檢測到一個低優(yōu)先級中斷，也不會立即響應(yīng)。另外，開中斷時，只有指令周期末尾，才會響應(yīng)中斷。22.以下關(guān)于IO控制方法的說法錯誤的是?A程序查詢方式是由CPU控制查詢B中斷方式是由CPU控制中斷CDMA方式中CPU執(zhí)行DMA程序控制數(shù)據(jù)傳輸DDMA方式常用于SSD和網(wǎng)絡(luò)適配器【解析】DMA方式下，數(shù)據(jù)傳輸由硬件(DMA控制器)完成23.與宏內(nèi)核相比，微內(nèi)核的優(yōu)點是?I性能好Ⅱ可靠性強Ⅲ安全性高IV可擴展性強D僅Ⅱ、Ⅲ、IV24.中斷向量表適合采用什么數(shù)據(jù)結(jié)構(gòu)?A數(shù)組B隊列C單向鏈表D雙向鏈表25.某系統(tǒng)采用頁式存儲管理，用位圖管理空閑頁框。若頁大小為4KB,物理內(nèi)存大小為16GB,則位圖所占空間大小是?A128B26.下列操作完成時，導(dǎo)致CPU從內(nèi)核態(tài)轉(zhuǎn)為用戶態(tài)的是?A阻塞進程B執(zhí)行CPU調(diào)度C喚醒進程D執(zhí)行系統(tǒng)調(diào)用27.下列由當(dāng)前線程引起的時間或執(zhí)行的操作中，可能導(dǎo)致該線程由執(zhí)行態(tài)變?yōu)榫途w態(tài)的是?A鍵盤輸入B缺頁異常C主動出讓CPUD執(zhí)行信號量的wait()操作28.采用搶占式優(yōu)先級算法(優(yōu)先數(shù)越大優(yōu)先級越高),如圖，平均周轉(zhuǎn)時間是多少?到達時刻執(zhí)行時間1A60msB61msC80ms29.兩個進程共享同一個頁中的數(shù)據(jù)，則數(shù)據(jù)在進程1、進程2中的頁號分別為p1、p2,在進程1、進程2中的頁框號分別為t1、t2,則下列說法中正確的是Ap1和p2不一定相同，t1和2不一定相同Bp1和p2一定相同，t1和t2不一定相同Dp1和p2一定相同，t1和t2一定相同30.文件F僅有一個進程打開，當(dāng)該進程關(guān)閉F時，必須的操作是A刪除目錄項B刪除內(nèi)存的文件索引結(jié)點C刪除外存的文件索引結(jié)點D文件磁盤索引節(jié)點鏈接計數(shù)器減一31.以下說法中錯誤的是?A每個進程有自己獨立的虛擬地址空間BC語言中的malloc返回的是虛擬地址C進程的數(shù)據(jù)段和代碼段可以有不同的訪問權(quán)限D(zhuǎn)進程的虛擬地址空間由內(nèi)存和外存的容量決定32.設(shè)備分配需要關(guān)注的是?1.設(shè)備類型IⅡ.設(shè)備使用狀態(tài)Ⅲ.邏輯設(shè)備和物理設(shè)備的映射IV.進程對設(shè)備的訪問權(quán)限這題全選I、Ⅱ、Ⅲ、IV計算機網(wǎng)絡(luò)：33.如圖，2段鏈路的數(shù)據(jù)傳輸速率為100Mbps,時延帶寬積(即單向傳插時延*帶寬)均為到H2收到文件全部數(shù)據(jù)時刻止，所需的時間至少是(注：M=10°)?RA80.02msB80.08msAQAM-16BQAM-3235.假設(shè)通過同一信道，數(shù)據(jù)鏈路層分別采用收窗口相等)傳輸數(shù)據(jù)，三個協(xié)議數(shù)據(jù)幀長相同，忽略確認(rèn)幀長度，幀序號位對應(yīng)三個協(xié)議的發(fā)送方最大信道利用率分別是U1、U2基于二進制指數(shù)腿比算法確定的再次嘗試重發(fā)該幀前等待的最長時間是()A51.2usB204.8usC768us收到下列比特串時，可以斷定其在傳輸過程中未發(fā)生錯誤的是(),則經(jīng)過R2轉(zhuǎn)發(fā)后，該IP分組的源IP地址是?A,54C,5441.(13分)對于有向圖，如果一個頂點的出度大于入度，則這個頂點稱為K頂點。有向圖用鄰接矩陣存儲，數(shù)據(jù)結(jié)構(gòu)定義如下：typedefstruct{2intnumVertex,numEdge;//要求實現(xiàn)函數(shù)intprintVertices(MGraphG),輸出有向圖中所有K頂點，并返回K頂點的總數(shù)。(2)用C/C++實現(xiàn)算法(預(yù)計占7~8分)(1)算法思想：遍歷有向圖中所有頂點，并統(tǒng)計各頂點的出度和入度，輸出出度大于入度的K頂點，并使用變量count累計K頂點的總數(shù)。計算頂點i的出度：遍歷鄰接矩陣的i行元素，即Edge[j[0]~Edge[i][numVertex-1],統(tǒng)計非零元素個數(shù)，即為頂點i的出度計算頂點i的入度：遍歷鄰接矩陣的i列元素，即Edge[0][]~Edge[numVertex-1]0,統(tǒng)計非零元素個數(shù)，即為頂點i的入度intprintVertices(MGrafor(intj=0;j<G.numVertex;j++){if(G.Edge[i][j]>0)o9for(intj=0;j<G.numVertex;j++){10}if(outDegree>inDegree){returncount;//返回頂點總數(shù)42.(10分)在進行外部排序時，可使用置換選擇排序生成初始歸并段。內(nèi)存工作區(qū)可存儲m個記錄，某文件含n個記錄。(1)若n=19,m=4。文件記錄關(guān)鍵字為：生成幾個初始歸并段?每個歸并段各是什么?(2)對于任意m(n>>m>0),使用置換選擇排序生成第一個初始歸并段的最大可能長度、最小可能長度分別是?【參考答案】(1)可生成3個初始歸并段(2分)①37,51,63,92,94,99(2分)②14,15,23,31,48,56,60,90,166(2分)③8,17,43,100(2分)(2)最大可能長度為n,最小可能長度為m。(各占1分)43.(14分)某機器字長為32位的計算機M,采用請求調(diào)頁存儲管理。虛擬地址32位，頁面大小4KB。Cache采用4路組相聯(lián)映射，內(nèi)存塊大小為32B,Cache數(shù)據(jù)區(qū)大小為8KB。二維數(shù)組inta[24][64]按行優(yōu)先存儲，數(shù)組的起始虛擬地址為00422000H。數(shù)組a的數(shù)據(jù)初始時未調(diào)入內(nèi)存，按如下方式訪問數(shù)組a:for(intj=0;j<64;j++)(1)數(shù)組a分為幾個頁面存儲?訪問數(shù)組a缺頁幾次?頁故障地址各是什么?(2)不考慮對變量i,j的訪問，訪問數(shù)組a的過程是否具有時間局部性?為什么?(3)在計算機M的32位地址中，塊內(nèi)地址是哪幾位?Cache組號是哪幾位?數(shù)組元素a[1][0]的虛擬地址是什么?對應(yīng)的Cache組號是什么?(4)數(shù)組a總共占多少塊?訪問a的Cache命中率是多少?若采用如下方式訪問數(shù)組a,則命中率又是多少?for(intj=0;j<64;j++)【參考答案】(1)數(shù)組a分為2個頁面存儲。(1分)訪問數(shù)組a缺頁2次。(1分)頁故障地址分別是00422000H、00423000H。(1+1分)時間局部性是指，程序在一段時間內(nèi)，訪問同一個數(shù)據(jù)多次。對于數(shù)組a,每個元素僅被訪問一次，因此不具有時間局部性。(2分)(3)32位地址結(jié)構(gòu)如下：tag標(biāo)記21bit+組號6bit+塊內(nèi)地址5bit。若用A31~A0表示32位地址，則塊內(nèi)地址是A4~AO(1分)Cache組號是A10~A5(1分)a[1][0]的虛擬地址是00422100H(1分)(4)數(shù)組a總共占192塊(1分)訪問a的Cache命中率是7/8=87.5%(1分)若按列訪問數(shù)組a,Cache命中率同樣是87.5%(1分)44.(9分)43題的C語言代碼，對應(yīng)的機器級代碼如下，請回答問題。可0|24畫1C7..2jmp00401084h37jge004010bch可64]畫80040108AC745...19004010AEC78482002042000A000000mov[ecx+edx*4+(1)第20條指令的虛擬地址是什么?(2)第2條指令jmp的操作碼是EBH,它的轉(zhuǎn)移目標(biāo)地址是00401084h。第7條指令jge的操作碼是7DH,它的轉(zhuǎn)移目標(biāo)地址是004010bch。這兩條指令分別采用什么尋址方式?請給出jmp指令的轉(zhuǎn)移目標(biāo)地址計算過程。(3)第19條指令，實現(xiàn)了a0-10。該指令的源操作數(shù)采用什么尋址方式?已知edx存放(4)第一次取第19條指令時，是否發(fā)生缺頁?為什么?【參考答案】(1)第20條指令的虛擬地址是004010B9h(1分)(2)jmp指令采用相對尋址(1分)jge指令采用相對尋址(1分)執(zhí)行jmp指令時，程序計數(shù)器PC指向jmp指令的后一條指令，即0040107Bh。jmp指令的轉(zhuǎn)移目標(biāo)地址計算過程為0040107Bh+09h=00401084h(1分)(3)源操作數(shù)采用立即尋址(1分)ecx存放的值=i*64*4=i*256(1分)系統(tǒng)采用小端存儲(1分)(4)沒有發(fā)生缺頁(1分)第19條指令的頁號是00401h,第1條指令的頁號也是00401h。剛開始訪問第1條指令時，就會把頁面00401h調(diào)入內(nèi)存。之后當(dāng)?shù)谝淮卧L問到第19條指令時，頁面已經(jīng)在內(nèi)存中，因此不會發(fā)生缺頁。(2分)注：第2小問，jmp、jge指令的尋址方式，如果答偏移尋址，可能也會給分偏移尋址偏移尋址區(qū)別在于偏移的“起點不一樣基址尋址：以程序的起始存放地址作為“起點”變址尋址：程序員白己決定從哪里作為“起點”相對尋址：以程序計數(shù)器PC所指地址作為“起點”操作系統(tǒng)：1boollock=FAlSE;//共享變量3//進入?yún)^(qū)7//臨界區(qū)9//退出區(qū)(1)請修改代碼，正確實現(xiàn)互斥(不增加語句條數(shù))(2)是否可以用函數(shù)newSwap(&a,&b)代替swap指令?為什么?(1)修改進入?yún)^(qū)代碼：if(key==TRUE)改為while(key==TRUE)(2分)(2)不可以代替swap指令。(1分)他線程，從而導(dǎo)致無法正確實現(xiàn)線程互斥。(2分)(1)①的前、后分別是哪個步驟?⑥的后面是什么步驟?(2)哪個步驟一定會使CPU從P進程切換到其他進程?哪個步驟之后調(diào)度器可以調(diào)度進程P?(3)哪個步驟是由鍵盤驅(qū)動程序完成的?(4)中斷處理時，進程P是什么狀態(tài)?CPU處于內(nèi)核態(tài)還是用戶態(tài)?【參考答案】(1)①的前面是③(1分)①的后面是⑤(1分)⑥的后面是④(1分)(2)②使得CPU從進程P切換為其他進程(1分)(3)③由鍵盤驅(qū)動程序完成(1分)(4)中斷處理時，進程P處于阻塞態(tài)(1分)CPU處于內(nèi)核態(tài)(1分)【解析】6個步的處理順序是：②⑥④③①⑤47.(9分)如圖，主機H登錄FTP服務(wù)器后自服務(wù)器上估一個大小為18000B的文件F,假設(shè)H傳輸F建立數(shù)據(jù)連接時，選擇的初始序號為100,MTU=1000B,擁塞控制