2022計算機考研408真題3

2022年全國碩士研究生入學(xué)統(tǒng)一考試

計算機科學(xué)與技術(shù)學(xué)科聯(lián)考

計算機學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項選擇題：第170小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求。1.若元素次優(yōu)孰注孰「依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（）。A.d,c,e,b,f,aD.a,f,e,d,c,b2.某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，若元素a,b,c,d,c依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是（）。A.b,a,c,d,ed,b,c,a,ee,c,b,a,d.下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）。NULL廠NULLNULLNULL'Sd.在下圖所示的平衡二叉樹中，插入關(guān)鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹關(guān)鍵中，字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是（A..在一棵度數(shù)為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，I個度為2的結(jié)點,10個度為1的結(jié)點，則樹T的葉結(jié)點個數(shù)是（A.41B.82C.113D.122當(dāng)該進程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)。請回答下列問題：（1）該邏輯地址對應(yīng)的頁號是多少？（2）若采用先進先出（FIFO）置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（3）若采用時鐘（Clock）置換克法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（設(shè)搜索下一頁的指針按順時針方向移動，且指向當(dāng)前2號頁框，示意圖如下所示）（9分）某局域網(wǎng)采用CSMA/CD協(xié)議實現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸率為10Mbi〃s,主機甲和主機乙之間的距離為2km,信號傳播速度是200000km/$。請回答下列問題，要求說明理由或?qū)懗鲇嬎氵^程。若主機甲和主機乙發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，再到兩臺主機均檢測到?jīng)_突時刻為止，最短需經(jīng)過多長時間？最長經(jīng)過多長時間？（假設(shè)主機甲和主機乙發(fā)送數(shù)據(jù)過程中，其他主機不發(fā)送數(shù)據(jù)）若網(wǎng)絡(luò)不存在任何沖突與差錯，主機甲總是以標(biāo)準(zhǔn)的最長以太數(shù)據(jù)幀（15I8B）向主機乙發(fā)送數(shù)據(jù)，主機乙每成功收到一個數(shù)據(jù)幀后立即向主機甲發(fā)送一個64B的確認幀，主機甲收到確認幀后立即發(fā)送卜一個數(shù)據(jù)幀。此時主機甲的有效數(shù)據(jù)傳輸速率是多少？（不考慮以太網(wǎng)幀的前導(dǎo)碼）6.對n（n>2）個權(quán)值均不相同的字符構(gòu)成赫夫曼樹。下列關(guān)于該赭夫曼樹的敘述中，錯誤的是（A口該樹一定是一棵完全二叉樹D.C樹中一定沒有度為1的結(jié)點:樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點7,樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值的勰^^<V.E）中含有7個頂點，要保證圖G在任何情況下都是連通的，則需要TOC\o"1-5"\h\zA.6B.15C.16D.21只對下困港行捫撲排岸.可以徂至II不同柘撲岸磯的個和臬（A.4B.3C.2D.1.已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列。若采用折半查找法查找一個L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是（）。A.4B.5C.6D.7.采用遞歸方式對順序表進行快速排序。下列關(guān)于遞歸次數(shù)的敘述中，正確的是（A.口遞歸次數(shù)與初始數(shù)據(jù)的排列次數(shù)無關(guān)O*C每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)D每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù),遞歸次數(shù)與每次劃分后得到的分區(qū)的糊艇稀，若前三趟蚪結(jié)果如下：.對一組數(shù)據(jù)（2,第一趟排序結(jié)果：2,熊二翎轉(zhuǎn)結(jié)果：2,第三趟庫岸結(jié)果：2,則采用的排序方法可能是（88起泡排序88歸并排序A.B.希爾排序C.D.基數(shù)排序.下列選項中，能縮短程序執(zhí)行時間的措施是（提高CPU時鐘頻率H.優(yōu)化數(shù)據(jù)通路結(jié)構(gòu)對程序進行編譯優(yōu)化A.僅I和IIB.僅I和UIC.僅II和HID.I、II和HI.假定有4個整數(shù)用8位補碼分別表示為rl=FEH.r2=F2H.r3=90H.r4=F8Ho若將運算結(jié)果存放在一個8位寄存器中，則下列運算中會發(fā)生溢出的是（A.rlxr2B.r2xr3C.rlxr4D.r2xr414.假定變量i、f、d數(shù)據(jù)類型分別為ini、float、double（int用補碼表示，float和double分別用IEEE754單精度和雙精度浮點數(shù)據(jù)格式表示），已知i=785.仁1.5678e3,d=1.5clOO,若在32位機器中執(zhí)行下列關(guān)系表達式，則結(jié)果為“真”的是（）。

I?i=(int)(float)iII.f==(float)(mt)fIII.f=(float)(double)fIV.(d+f)-d==fA.僅I和IIB.僅I和HIC.僅II和HID.僅HI和IV.假定用若干個2KX4位芯片組成一個8Kx8位的存儲器，則地址0B1FH所在芯片的最小地址A.0000HB.0600HC.0700HD.0800H.下列有關(guān)RAM和ROM的敘述中，正確的是（）。RAM是易失性存儲器，ROM是非易失性存儲器RAM和ROM都是采用隨機存取方式進行信息訪問的RAM和ROM都可用做CacheRAM和ROM都需要進行刷新A,僅I和IIB.僅II和UIC.僅I、II和IHD.僅IkIU、IV17.下列命中組合情況中，一次訪存過程中不可能發(fā)生的是（TLBA.未命中，Cache未命中，Page未命中TLB未命中，Cache命中，Page命中TLB命中，Cache未命中，Page命中TLB命中，CacheC.命中，Page未命中D..下列寄存器中，匯編語言程序員可見的是（）。A,存儲器地址寄存器（MAR）B.程序計數(shù)器（PC）C.存儲器數(shù)據(jù)寄存器（MDR）D.指令寄存器（IR）.下列選項中，不會引起指令流水阻塞的是（A,數(shù)據(jù)旁路（轉(zhuǎn)發(fā)）B.數(shù)據(jù)相關(guān)C.條件轉(zhuǎn)移D.資源沖突.下列選項中的英文縮寫均為總線標(biāo)準(zhǔn)的是（A.PCLCRT.USB、EISAB.ISA、CPLISA、SCSLRAM.MIPSD.ISA,EISA,WKPCI-Express21.單級中斷系統(tǒng)）O）OII.開中斷IV.保存斷點VI.恢復(fù)現(xiàn)場I.保護現(xiàn)場in.關(guān)中斷v.中斷事件處理VD.中斷返回B.m->i->v->vn是(九c.in->iv->v->vi->vnD.iv->i->v->vi->vn22.假定一臺計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600x1200,顏色深度為24位，幀頻為85Hz,顯存總帶寬的50%是(九c.in->iv->v->vi->vnD.iv->i->v->vi->vnA,245Mbi火979Mbit/s958Mbit/s下D.7834Mbit/s列選項中，系操作系統(tǒng)提供的給應(yīng)用程序的接口是（統(tǒng)調(diào)用下列b.中斷C.庫函數(shù)D.原語導(dǎo)致創(chuàng)建新進程的操作選項中，皇/23.A.24.I-用戶登錄成功IL設(shè)備分配HI.啟動程序執(zhí)行A.僅I和^B.僅^和HIC.僅I和HID.LIkIII.設(shè)與某資源相關(guān)聯(lián)的信號量初值為3,當(dāng)前值為1。若M表示該資源的可用個數(shù)，N表示等待該資源的進程數(shù)，則M、N分別是（”A.O、IB.l>0C.1、2D.2、0.下列選項中，降低進程優(yōu)先級的合理時機是（A.進程的時間片用完B.進程剛完成I/O,進入就緒列隊C.進程長期處于就緒列隊D.進程從就緒狀態(tài)轉(zhuǎn)為運行態(tài).進行pO和pl的共享變量定義及其初值為：booleanflag[21;inttum=O;flag[O]=FALSE;flag[l]=FALSE;若進行p。和pl訪問臨界資源的類c代碼實現(xiàn)如下：voidp0()〃進程pO

(while(TRUE){nag[O]=TRUE;tum=l;voidp0()〃進程pO

(while(TRUE){nag[O]=TRUE;tum=l;While(flag[1]&&(tum==1));臨界區(qū)：flag|O]=FALSE;(flag[l]=TRUE:tum=0;While(flag[0]&&(tum=0));臨界區(qū)；flagUJ=FALSE;))則并發(fā)執(zhí)行進程p。和pl時產(chǎn)牛.的情形是（不能保證進程互斥進入臨界區(qū)會出現(xiàn)“饑餓”現(xiàn)象不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象.某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55MB（初始為空閑），采用最佳適應(yīng)分配（BestFit）算法,分配和釋放的順序為:分配15MB,分配30MB,釋放15MB,分配8MB,分配6MB,此時主存中最大空閑分區(qū)的大小是（A.7MBB.9MBC.10MBD.15MB.某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編制，頁的大小為21。字節(jié)，頁表項大小為2字節(jié)，邏輯地址結(jié)構(gòu)為：邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是（A.64B.128C.256.設(shè)文件索引結(jié)點中有7個地址項，其中4個地址項為直接地址索引，2個地址項為一級間接地址索引，1個地址項為二級間接地址索引，每個地址項的大小為4B。若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256B,則可表示的單個文件最大長度是（A.33KBB.519KBC.31.設(shè)置當(dāng)前工作目錄的主要目的是（A.節(jié)省外存空間B.“加快文件的檢索速度D.I057KB解.本地用戶通過鍵盤登錄系統(tǒng)時，首先獲得鍵盤輸入信息的程序是（節(jié)省內(nèi)存空間）加快文件的讀/創(chuàng)摘期B頁號頁內(nèi)偏移道A.命令解釋程序B.中斷處理程序C.系統(tǒng)調(diào)用服務(wù)程序D.用戶登錄程序.下列選項中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)所描述的內(nèi)容是（）。A.網(wǎng)絡(luò)的層次B.每一層使用的協(xié)議C協(xié)議的內(nèi)部實現(xiàn)細節(jié)D.每一層必須完成的功能.在下圖所表示的采用“存儲-轉(zhuǎn)發(fā)”方式的分組交換網(wǎng)絡(luò)中，所有鏈路的數(shù)據(jù)傳輸速率為100Mbit/s,分組大小為1000B,其中分組頭大小為20Bo若主機H1向主機H2發(fā)送一個大小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從HI發(fā)送開始到H2接收完為止，需要的時間至少是（）。A.80msB.80.08msC.80.16msD.80.24ms.某自治系統(tǒng)內(nèi)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器RI收到其鄰居路由器R2的距離矢量，距離矢量中包含信息<neil,16>,則能得出的結(jié)論是（）。R2可以經(jīng)過R1到達netl,跳數(shù)為17R2可以到達netl,跳數(shù)為16R1可以經(jīng)過R2到達netl,跳數(shù)為17R1不能經(jīng)過R2到達nctl若路由器R因為擁塞丟棄IP分組，則此時R可向發(fā)出該IP分組的源主機發(fā)送的ICMP報文類型是（）。A.路由重定向B.目的不可達C.源抑制D.超時某網(wǎng)絡(luò)的IP地址空間為192.168.5.0/24,采用定長子網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248,則該網(wǎng)絡(luò)中的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)分別是（）OA.32、8B.32、6C.8,32D.8、30下列網(wǎng)絡(luò)設(shè)備中，能夠抑制廣播風(fēng)暴的是（）。L中維器II.集線器in.網(wǎng)橋IV.路由器A僅I和IIB.僅IHC.僅III和IVD.僅IV主機甲和主機乙之間已建立一個TCP連接，TCP最大段長度為1000B,若主機甲的當(dāng)前擁塞窗口為4000B,在主機甲向主機乙連續(xù)發(fā)送2個最大段后，成功收到主機乙發(fā)送的對第?個段的確認段確認段中通告的接收窗口大小為2000B,則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是（）。A.1（X）0B.2000C.3000D.4000如果本地域名服務(wù)器無緩存，當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機域名時，用戶主機、本地域名服務(wù)器發(fā)送的墟茗請求消息數(shù)分別為（）。A.條、一條B.一條、多條C.多條、一條D.多條、多條二、綜合應(yīng)用題：4177小題，共70分。請將答案寫在答題紙指定位置上。（10分）將關(guān)鍵字序列（7、8、30、11、18、9、14）散列存儲到散列表中，散列表的存儲空間是一個下標(biāo)從。開始的一維數(shù)組，散列函數(shù)為H（key）=（keyx3）MOD7,處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7。（1）請畫出所構(gòu)造的散列表。（2）分別計算等概率情況下查找成功和查找不成功的平均查找長度。(13分)設(shè)將n(n>l)個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，將R中保存的序列循環(huán)左移p(O<pvn)個位置，即將R中的數(shù)據(jù)序列由(Xo,XI,…，Xnni)變換為(Xp,Xp+l,…,Xnni,Xo,XI,-,Xp-l)0要求：(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C什或Java語言描述完法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。(11分)某計算機字節(jié)長為16位，主存地址空間大小為128KB，按字編址。采用單字長指令格式，指令各字段定義如下：151211650OPIMSIRSIMdIRd

源操作數(shù)目的操作數(shù)轉(zhuǎn)移指令采用相對尋址方式，相對偏移量用補碼表示，尋址方式定義如下表:Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù)=(Rn)001B寄存器間接(Rn)操作數(shù)=((Rn))010B寄存器間接、自增(Rn)+操作數(shù)=((Rn)),(Rn)+l->Rn01IB相對D(Rn)轉(zhuǎn)移i標(biāo)地址=(PC)+(Rn)注：(X)表示存儲地址X或寄存器X的內(nèi)容。請回答下列問題：(1)該指令系統(tǒng)最多可有多少指令？該計算機最多有多少個通用寄存器？存儲器地址寄存器(MAR)和存儲器數(shù)據(jù)寄存器(MDR)至少各需要多少位？(2)轉(zhuǎn)移指令的目標(biāo)地址范圍是多少？(3)若操作碼00I0B表示加法操作(助記符為add),寄存器R4和R5的編號分別為I00B和IO1B,R4的內(nèi)容為1234H,R5的內(nèi)容為5678H，地址1234H中的內(nèi)容為5678H，地址5678H中的內(nèi)容為I234H,則匯編語句“add(R4),(R5)+”(逗號前為源操作數(shù)，逗號后為目的操作數(shù))對應(yīng)的機器碼是什么(用十六進制表示)？該指令執(zhí)行后，哪些寄存器和存儲單元中的內(nèi)容會改變？改變后的內(nèi)容是什么？(12分)某計算機的主存地址空間大小為256MB,按字節(jié)編址。指令Cache和數(shù)據(jù)Cache分離,均有8個Cache行，每個Cache行大小為64B,數(shù)據(jù)Cache采用直接映射方式?，F(xiàn)有兩個功能相同的程序A和B,其偽代碼如下所示：程序A:inta[256][256];程序B:inta[256][256];intsum_array1()intsum_array2()intij,sum=O;(br(i=0;iv256;i++)intij,sum=O;fbr(j=0;j<256j++)sumsum+=a[i][j];returnsum;returnsum;})假定int類型數(shù)據(jù)用32位補碼表示，程序編譯時i、j、