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

4.在由6個(gè)字符組成的字符集S中，各字符出現(xiàn)的頻次分別為3,4,5,6,8,10,為S構(gòu)造的哈夫曼編碼的加權(quán)平均長(zhǎng)度為A2.4B2.5C2.67D25.已知一棵二叉樹(shù)的樹(shù)型如下圖所示，若其后序遍歷序列為fdbeca,則其先序遍歷序列是?6.對(duì)于邊權(quán)值都為1的無(wú)向圖，可以求出某一點(diǎn)到其他所有點(diǎn)的最短路徑的是?I普里姆算法Ⅱ克魯斯卡爾算法Ⅲ廣度優(yōu)先遍歷BFS7.下面關(guān)于非空B樹(shù)的說(shuō)法正確的是?I插入可能會(huì)增加樹(shù)的高度Ⅱ刪除節(jié)點(diǎn)一定會(huì)改變?nèi)~節(jié)點(diǎn)ⅢB樹(shù)查找一定會(huì)查找到葉節(jié)點(diǎn)IV插入節(jié)點(diǎn)最終一定在葉節(jié)點(diǎn)上01234數(shù)據(jù)失敗次數(shù)13212Ⅲ快速排序組成原理：少?表2.2IEEE754浮點(diǎn)數(shù)的解釋負(fù)零負(fù)無(wú)窮大無(wú)定義數(shù)(非數(shù))規(guī)格化作零正數(shù)單精度(32位)雙精度(64位)00或10階碼00255(全1)255(全1)255(全1)0<e<2550<e<2550000一-2-1(0.0010或10階碼002047(全1)2047(全1)2047(全1)0<e<20470<e<2047000 0一A0.8,0.4msC1.25,0.4msAOF=0,CF=0BOF=0,CF=118.元件分為兩類，組合邏輯元件(也稱操作元操作系統(tǒng)：Ⅲ安全性高A數(shù)組B隊(duì)列C單向鏈表D雙向鏈表A阻塞進(jìn)程B執(zhí)行CPU調(diào)度C喚醒進(jìn)程D執(zhí)行系統(tǒng)調(diào)用A鍵盤(pán)輸入B缺頁(yè)異常28.采用搶占式優(yōu)先級(jí)算法(優(yōu)先數(shù)越大優(yōu)先級(jí)越高),如圖，平均周轉(zhuǎn)時(shí)間是多少?到達(dá)時(shí)刻執(zhí)行時(shí)間1A刪除目錄項(xiàng)33.如圖，2段鏈路的數(shù)據(jù)傳輸速軍為100Mbps,時(shí)延帶覓積(即單向傳搖時(shí)延*帶寬)均為到H2收到文件全部數(shù)據(jù)時(shí)刻止，所需的時(shí)間至少是(注：M=10^)?A80.02msB80.08msC80.09msAQAM-16BQAM-3235.假設(shè)通過(guò)同一信道，數(shù)據(jù)鏈路層分別采用停等協(xié)議，GBN協(xié)議和SR協(xié)議(發(fā)送窗口和接收窗口相等)傳輸數(shù)據(jù)，三個(gè)協(xié)以數(shù)據(jù)幀長(zhǎng)相同，忽略確認(rèn)幀長(zhǎng)度，幀序號(hào)位數(shù)為3比特，若AU1≤U2≤U3BU1≤U3sU2CU2≤U3sU136已知10BaseT以太網(wǎng)的爭(zhēng)用時(shí)間片為51.2us,若網(wǎng)卡在發(fā)送某吃時(shí)發(fā)生了連續(xù)4次沖突，則基于二進(jìn)制指數(shù)腿比算法確定的再次嘗試重發(fā)該幀前等待的最長(zhǎng)時(shí)間是()A51.2usB204.8us收到下列比特串時(shí)，可以斷定其在傳輸過(guò)程中未發(fā)生錯(cuò)誤的是(),則經(jīng)過(guò)R2轉(zhuǎn)發(fā)后，該IP分組的源IP地址是?NATR239主機(jī)168.16.8424/20所在子網(wǎng)的最小可分配地址和最大可分配地址分別足?BDIipv6地址空間是ipv4地址空間的941.(13分)對(duì)于有向圖，如果一個(gè)頂點(diǎn)的出度大于入度，則這個(gè)頂點(diǎn)稱為K頂點(diǎn)。有向圖用typedefintEdge[MAXV][MAXV];//鄰接矩陣(1)說(shuō)明算法思想(預(yù)計(jì)占5-6分)(2)用C/C++實(shí)現(xiàn)算法(預(yù)計(jì)占7~8分)(1)算法思想：遍歷有向圖中所有頂點(diǎn)，并統(tǒng)計(jì)各頂點(diǎn)的出度和入度，輸出出度大于入度的K頂點(diǎn)，并使用變量count累計(jì)K頂點(diǎn)的總數(shù)。計(jì)算頂點(diǎn)i的出度：遍歷鄰接矩陣的i行元素，即Edge[J[0]-Edge[i][numVertex-1],統(tǒng)計(jì)非零元素個(gè)數(shù)，即為頂點(diǎn)i的出度計(jì)算頂點(diǎn)i的入度：遍歷鄰接矩陣的i列元素，即Edge[0][]~Edge[numVertex-1]0,統(tǒng)計(jì)非零元素個(gè)數(shù)，即為頂點(diǎn)i的入度(2)算法實(shí)現(xiàn)：far(ne=0;i<G.numVertexfortntj=0:j<G.nu=Vertex;j+)|for(Lntj=0;j<G.nu=Vertex;j++)142.(10分)在進(jìn)行外部排序時(shí)，可使用置換選擇排序生成初始?xì)w開(kāi)段內(nèi)存工作區(qū)可存儲(chǔ)m個(gè)記錄，某文件含h個(gè)記錄。(1)若n=19,m=4,文件記錄關(guān)鍵字為生成幾個(gè)初始?xì)w并段?每個(gè)歸并段各是什么?(2)對(duì)于任塞m(n>>m>0),使用置換選擇排序生成第一個(gè)初始?xì)w井段的最大可能長(zhǎng)度，最小可能長(zhǎng)度分別是?【參考答案】①37,51,63,92,94,99(2分)②14,15,23,31,48,5680,90,166(2分)①8,17,43,100(2分)(2)最大可能長(zhǎng)度為n,最小可能長(zhǎng)度為m.(各占1分)43(14分)某機(jī)器字長(zhǎng)為32位的計(jì)茸機(jī)M,采用請(qǐng)求調(diào)頁(yè)存儲(chǔ)管理。虛擬地址32位，頁(yè)面大小4KB,Cache采用4路組相歌呋射，內(nèi)存塊大小為32B,Cache數(shù)據(jù)區(qū)大小為8KB,二維數(shù)組inta[24//64]按行優(yōu)先存儲(chǔ)，數(shù)組的起始虛擬地址為00422000H,數(shù)組a的數(shù)指初始時(shí)未洞入內(nèi)存，按如下方式訪問(wèn)數(shù)組a;(1)數(shù)組a分為幾個(gè)頁(yè)面存儲(chǔ)?訪問(wèn)散組a缺頁(yè)幾次?頁(yè)故障地址各是什么?(2)不考點(diǎn)對(duì)安品，j的訪問(wèn)，訪問(wèn)數(shù)組a的過(guò)程是否具有時(shí)間局部性?為什么?(3)在計(jì)算機(jī)M的32位地址中，塊內(nèi)地址是哪幾位?Cache組號(hào)足哪幾位?數(shù)組元前a1][O的起擬地址是什么?對(duì)應(yīng)的Cache組號(hào)是什么?(4)數(shù)組a總共占多少塊?訪問(wèn)a的Cache命中率是多少?若宋用如下方式訪問(wèn)數(shù)組a,則命中率又是多少?【參考答案】(1)數(shù)組a分為2個(gè)頁(yè)面存儲(chǔ)，(1分)頁(yè)故障地址分別是00422000H,00423000H,(1+1分)(2)投有時(shí)問(wèn)局部性，(1分)時(shí)間部性是指，程序在一段時(shí)間內(nèi)，訪問(wèn)同一個(gè)數(shù)正多次。對(duì)于數(shù)a,再個(gè)元素僅被訪問(wèn)一次，因此不具有時(shí)間同部性(2分)(3)32位地址結(jié)構(gòu)如下：tag標(biāo)記21bil+組號(hào)6bt+塊內(nèi)地址5bt,若用A31-AO表示32位地址，則塊內(nèi)地址是A4-AO(1分)Cache組號(hào)是A10-A5(1分)a[1[的慮擬以地址是00422100H(1分)對(duì)應(yīng)的Cache組號(hào)足8(1分)(4)數(shù)組a總共占192塊(1分)訪問(wèn)a的Cache命中率是778=875%(1分)若按列訪問(wèn)教組a,Cache命中率同樣是875%(1分)44.(9分)43題的C語(yǔ)吉代碼，對(duì)應(yīng)的機(jī)器級(jí)代碼如下，請(qǐng)回答問(wèn)題。jmp00401084h19004010AEC78482002042000AD00000mov[ecx+edx4+(1)第20條指今的虛擬地址是什么?(2)第2條指令jmp的股操作碼是EBH,它的轉(zhuǎn)移目標(biāo)地址是00401084h,第7條指令jge的操作碼是7DH,它的轉(zhuǎn)移目標(biāo)地址是004010bch,這兩條指令分別采用什么尋址方式?請(qǐng)給出jmp指令的轉(zhuǎn)移目標(biāo)地址計(jì)算過(guò)程。(3)第19條指令，實(shí)現(xiàn)了a同u-10。該指令的源操作數(shù)采用什么尋址方式?已知edx存放(4)第一次取第19條指令時(shí)，是否發(fā)生缺頁(yè)?為什么?(1)第20條指令的虛擬地址是004010B9h(1分)(2)jmp指令采用相對(duì)尋址(1分)ie指令采用相對(duì)尋址(1分)執(zhí)行jmp指令時(shí)，程序計(jì)數(shù)器PC指向jmp指令的后令的轉(zhuǎn)移目標(biāo)地址計(jì)算過(guò)程為0040107Bh+09h=00401084h(1分)(3)衙操作數(shù)采用立即尋址(1分)ecx存放的值=i1644=i256(1分)系統(tǒng)采用小端存儲(chǔ)(1分)(4)沒(méi)有發(fā)生缺頁(yè)(1分)第19條指令的頁(yè)號(hào)是00401h,第1條指令的頁(yè)號(hào)也是00401h。網(wǎng)開(kāi)始訪問(wèn)第1條指令時(shí)，就會(huì)把頁(yè)面00401h涸入內(nèi)存，之后當(dāng)?shù)谝淮卧L問(wèn)到第19條指令時(shí)，頁(yè)面已經(jīng)在內(nèi)存中，因此不會(huì)發(fā)生缺頁(yè)。(2分)注：第2小問(wèn)，mp、Jge指令的等址方式，如果否情移尋址，可能也含給分我們不一樣偏移尋址偏移尋址區(qū)在于伯稱的“知店”樣操作系統(tǒng)：//進(jìn)入?yún)^(qū)if(key=TRUE)//臨界區(qū).//退出區(qū)(1)請(qǐng)修改代碼，正確實(shí)現(xiàn)互斥(不增加語(yǔ)句條數(shù))(2)是否可以用函數(shù)newSwap(&a,&b)代苔swap指令?為什么?(1)修改進(jìn)入?yún)^(qū)代碼：if(key=TRUE)改為while(key=TRUE)(2分)(2)不可以代苔swap指令。(1分)他線程，從而導(dǎo)致無(wú)法正確實(shí)現(xiàn)線程互斥。(2分)(1)①的前、后分別是哪個(gè)步驟?⑥的后面是什么步驟?(2)哪個(gè)步驟一定會(huì)使CPU從P進(jìn)程切換到其他進(jìn)程?哪個(gè)步驟之后調(diào)度器可以調(diào)度進(jìn)程P?(3)哪個(gè)步愛(ài)是由鍵盤(pán)驅(qū)動(dòng)程序完成的?(4)中斷處理時(shí)，進(jìn)程P是什么狀態(tài)?CPU處于內(nèi)核態(tài)還是用戶態(tài)?【參考答案】(1)①的前面是③(1分)①的后面是⑤(1分)(2)②使得CPU從進(jìn)程P切換為其他進(jìn)程(1分)(3)③由鍵盤(pán)驅(qū)動(dòng)程序完成(1分)(4)中斷處理時(shí)，進(jìn)程P處于陽(yáng)塞態(tài)(1分)CPU處于內(nèi)核態(tài)(1分)I【解析】6個(gè)步驟的處理煩序是：②⑤④③①⑤47.(9分)如圖，主機(jī)H登錄FTP服務(wù)器后自服務(wù)器上估一個(gè)大小為18000B的文件F,假設(shè)H傳輸F建立數(shù)據(jù)連接時(shí)，選擇的初始序號(hào)為100,MTU=1000B,擁寒控制初始閾值為4MSS,(1)FTP的控制連接是持久的還是非持久的?FTP的數(shù)據(jù)連接是持久的還是非持久的?H登控制連接是持久的；(1分)數(shù)據(jù)連接是非持久的；(1分)控制連接。(1分)101(1分)18102(1分)