研究生考試考研計算機學科專業(yè)基礎(chǔ)(408)試卷與參考答案一、單項選擇題（每題2分，共80分）1.設(shè)n是描述問題規(guī)模的非負整數(shù)，下面程序片段的時間復(fù)雜度是（）```pythonx=2;while(x<n/2)x=2x;```A.O(log?n)B.O(n)C.O(nlog?n)D.O(n2)2.已知操作符包括‘+’、‘-’、‘’、‘/’、‘(’、‘)’。將中綴表達式a+b-a((c+d)/e-f)+g轉(zhuǎn)換為等價的后綴表達式ab+acd+e/f--g+時，用棧來存放暫時還不能確定運算次序的操作符。若棧初始為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是（）A.5B.7C.8D.113.若平衡二叉樹的高度為6，且所有非葉子結(jié)點的平衡因子均為1，則該平衡二叉樹的結(jié)點總數(shù)為（）A.12B.20C.32D.334.若將關(guān)鍵字1，2，3，4，5，6，7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結(jié)點的個數(shù)是（）A.0B.1C.2D.35.已知三叉樹T中6度為1的結(jié)點，5個度為2的結(jié)點，3個度為3的結(jié)點，則該樹中有（）個葉子結(jié)點。A.8B.10C.12D.136.若X是后序線索二叉樹中的葉結(jié)點，且X存在左兄弟結(jié)點Y，則X的右線索指向的是（）A.X的父結(jié)點B.以Y為根的子樹的最左下結(jié)點C.X的左兄弟結(jié)點YD.以Y為根的子樹的最右下結(jié)點7.在任意一棵非空二叉排序樹T?中，刪除某結(jié)點v之后形成二叉排序樹T?，再將v插入T?形成二叉排序樹T?。下列關(guān)于T?與T?的敘述中，正確的是（）I.若v是T?的葉結(jié)點，則T?與T?不同II.若v是T?的葉結(jié)點，則T?與T?相同III.若v不是T?的葉結(jié)點，則T?與T?不同IV.若v不是T?的葉結(jié)點，則T?與T?相同A.僅I、IIIB.僅I、IVC.僅II、IIID.僅II、IV8.若對如下無向圖進行遍歷，則下列選項中，不是廣度優(yōu)先遍歷序列的是（）```plaintext0--1||2--3```A.0，1，2，3B.0，2，3，1C.0，3，2，1D.0，1，3，29.下列關(guān)于圖的敘述中，正確的是（）I.回路是簡單路徑II.存儲稀疏圖，用鄰接矩陣比鄰接表更省空間III.若有向圖中存在拓撲序列，則該圖不存在回路A.僅IIB.僅I、IIC.僅IIID.僅I、III10.為實現(xiàn)快速排序算法，待排序序列宜采用的存儲方式是（）A.順序存儲B.散列存儲C.鏈式存儲D.索引存儲11.已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，將其再調(diào)整為大根堆，調(diào)整過程中元素之間進行的比較次數(shù)是（）A.1B.2C.4D.512.假定基準程序A在某計算機上的運行時間為100秒，其中90秒為CPU時間，其余為I/O時間。若CPU速度提高50%，I/O速度不變，則運行基準程序A所耗費的時間是（）A.55秒B.60秒C.65秒D.70秒13.下列關(guān)于銀行家算法的敘述中，正確的是（）A.銀行家算法可以預(yù)防死鎖B.當系統(tǒng)處于安全狀態(tài)時，系統(tǒng)中一定無死鎖進程C.當系統(tǒng)處于不安全狀態(tài)時，系統(tǒng)中一定會出現(xiàn)死鎖進程D.銀行家算法破壞了死鎖必要條件中的“請求和保持”條件14.若用戶進程訪問內(nèi)存時產(chǎn)生缺頁，則下列選項中，操作系統(tǒng)可能執(zhí)行的操作是（）I.處理越界錯II.置換頁III.分配內(nèi)存A.僅I、IIB.僅II、IIIC.僅I、IIID.I、II和III15.當系統(tǒng)發(fā)生抖動（thrashing）時，可以采取的有效措施是（）A.增加磁盤交換區(qū)的容量B.降低用戶進程的優(yōu)先級C.提高用戶進程的優(yōu)先級D.終止部分用戶進程16.在虛擬內(nèi)存管理中，地址變換機構(gòu)將邏輯地址變換為物理地址，形成該邏輯地址的階段是（）A.編輯B.編譯C.鏈接D.裝載17.某文件系統(tǒng)為一級目錄結(jié)構(gòu)，文件的數(shù)據(jù)一次性寫入磁盤，已寫入的文件不可修改，但可多次創(chuàng)建新文件。在連續(xù)、鏈式、索引三種文件的數(shù)據(jù)塊組織方式中，（）A.連續(xù)方式更適合于順序讀寫，鏈式方式更適合于隨機讀寫B(tài).鏈式方式更適合于順序讀寫，連續(xù)方式更適合于隨機讀寫C.連續(xù)方式更適合于順序讀寫，索引方式更適合于隨機讀寫D.索引方式更適合于順序讀寫，鏈式方式更適合于隨機讀寫18.假設(shè)磁頭當前位于第105道，正在向磁道序號增加的方向移動?，F(xiàn)有一個磁道訪問請求序列為35，45，12，68，110，180，170，195，采用SCAN調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是（）A.110，170，180，195，68，45，35，12B.110，68，45，35，12，170，180，195C.12，35，45，68，110，170，180，195D.195，180，170，110，68，45，35，1219.下列選項中，滿足短任務(wù)優(yōu)先且不會發(fā)生饑餓現(xiàn)象的調(diào)度算法是（）A.先來先服務(wù)B.高響應(yīng)比優(yōu)先C.時間片輪轉(zhuǎn)D.非搶占式短任務(wù)優(yōu)先20.假設(shè)某系統(tǒng)總線在一個總線周期中并行傳輸4字節(jié)信息，一個總線周期占用2個時鐘周期，總線時鐘頻率為10MHz，則總線帶寬是（）A.10MB/sB.20MB/sC.40MB/sD.80MB/s21.下列選項中，能引起外部中斷的事件是（）A.鍵盤輸入B.除數(shù)為0C.浮點運算下溢D.訪存缺頁22.單級中斷系統(tǒng)中，中斷服務(wù)程序內(nèi)的執(zhí)行順序是（）I.保護現(xiàn)場II.開中斷III.關(guān)中斷IV.保存斷點V.中斷事件處理VI.恢復(fù)現(xiàn)場VII.中斷返回A.I→V→VI→II→VIIB.III→I→V→VIIC.III→IV→V→VI→VIID.IV→I→V→VI→VII23.下列選項中，屬于Internet應(yīng)用層協(xié)議的是（）A.IPB.TCPC.UDPD.SMTP24.某主機的IP地址為5，子網(wǎng)掩碼為。若該主機向其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是（）A.B.55C.55D.25.下列關(guān)于UDP協(xié)議的敘述中，正確的是（）I.提供無連接服務(wù)II.提供復(fù)用/分用服務(wù)III.通過差錯校驗，保障可靠數(shù)據(jù)傳輸A.僅IB.僅I、IIC.僅II、IIID.I、II、III26.若用戶1與用戶2之間發(fā)送和接收電子郵件的過程如下圖所示，則圖中①、②、③階段分別使用的應(yīng)用層協(xié)議可以是（）```plaintext用戶1--①-->郵件服務(wù)器1--②-->郵件服務(wù)器2--③-->用戶2```A.SMTP、SMTP、SMTPB.POP3、SMTP、POP3C.POP3、SMTP、SMTPD.SMTP、SMTP、POP327.某網(wǎng)絡(luò)拓撲如下圖所示，路由器R1只有到達子網(wǎng)/24的路由。為使R1可以將IP分組正確地路由到圖中所有子網(wǎng)，則在R1中需要增加的一條路由（目的網(wǎng)絡(luò)，子網(wǎng)掩碼，下一跳）是（）```plaintextR1--/24--LAN1||--/24--LAN2||--/24--LAN3```A.，，B.，，C.，，D.，，28.在子網(wǎng)/30中，能接收目的地址為的IP分組的最大主機數(shù)是（）A.0B.1C.2D.429.某自治系統(tǒng)內(nèi)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量中包含信息<net1，16>，則可能得出的結(jié)論是（）A.R2可以經(jīng)過R1到達net1，跳數(shù)為17B.R2可以到達net1，跳數(shù)為16C.R1可以經(jīng)過R2到達net1，跳數(shù)為17D.R1不能經(jīng)過R2到達net130.若路由器R因為擁塞丟棄IP分組，則此時R可以向發(fā)出該IP分組的源主機發(fā)送的ICMP報文類型是（）A.路由重定向B.目的不可達C.源抑制D.超時31.某網(wǎng)絡(luò)的IP地址空間為/24，采用定長子網(wǎng)劃分，子網(wǎng)掩碼為48，則該網(wǎng)絡(luò)的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)分別是（）A.32，8B.32，6C.8，32D.8，3032.下列關(guān)于IP路由器功能的描述中，正確的是（）I.運行路由協(xié)議，設(shè)置路由表II.監(jiān)測到擁塞時，合理丟棄IP分組III.對收到的IP分組頭進行差錯校驗，確保傳輸?shù)腎P分組不丟失IV.根據(jù)收到的IP分組的目的IP地址，將其轉(zhuǎn)發(fā)到合適的輸出線路上A.僅III、IVB.僅I、II、IIIC.僅I、II、IVD.I、II、III、IV33.一個進程的讀磁盤操作完成后，操作系統(tǒng)針對該進程必做的是（）A.修改進程狀態(tài)為就緒態(tài)B.降低進程優(yōu)先級C.給進程分配用戶內(nèi)存空間D.增加進程的時間片大小34.若一個用戶進程通過read系統(tǒng)調(diào)用讀取一個磁盤文件中的數(shù)據(jù)，則下列關(guān)于此過程的敘述中，正確的是（）I.若該文件的數(shù)據(jù)不在內(nèi)存中，則該進程進入睡眠等待狀態(tài)II.請求read系統(tǒng)調(diào)用會導(dǎo)致CPU從用戶態(tài)切換到核心態(tài)III.read系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱A.僅I、IIB.僅I、IIIC.僅II、IIID.I、II和III35.下列選項中，會導(dǎo)致用戶進程從用戶態(tài)切換到內(nèi)核態(tài)的操作是（）I.整數(shù)除以零II.sin函數(shù)調(diào)用III.read系統(tǒng)調(diào)用A.僅I、IIB.僅I、IIIC.僅II、IIID.I、II和III36.計算機開機后，操作系統(tǒng)最終被加載到（）A.BIOSB.ROMC.EPROMD.RAM37.若某計算機最復(fù)雜指令的執(zhí)行需要完成5個子功能，分別由功能部件A～E實現(xiàn)，各功能部件所需時間分別為80ps、50ps、50ps、70ps和50ps，采用流水線方式執(zhí)行該指令，則CPU的時鐘周期至少為（）A.50psB.70psC.80psD.300ps38.下列關(guān)于超標量流水線特性的敘述中，正確的是（）I.能縮短流水線功能段的處理時間II.能在一個時鐘周期內(nèi)同時發(fā)射多條指令I(lǐng)II.能結(jié)合動態(tài)調(diào)度技術(shù)提高指令執(zhí)行并行性A.僅IIB.僅I、IIIC.僅II、IIID.I、II和III39.假定不采用Cache和指令預(yù)取技術(shù)，且機器處于“開中斷”狀態(tài)，則在下列有關(guān)指令執(zhí)行的敘述中，錯誤的是（）A.每個指令周期中CPU都至少訪問內(nèi)存一次B.每個指令周期一定大于或等于一個CPU時鐘周期C.空操作指令的指令周期中任何寄存器的內(nèi)容都不會被改變D.當前程序在每條指令執(zhí)行結(jié)束時都可能被外部中斷打斷40.某計算機采用微程序控制器，共有32條指令，公共的取指微程序包含2條微指令，各指令對應(yīng)的微程序平均由4條微指令組成，采用斷定法（下地址字段法）確定下條微指令的地址，則微指令寄存器的位數(shù)至少是（）A.5B.6C.8D.9二、綜合應(yīng)用題（共70分）41.（13分）設(shè)包含4個數(shù)據(jù)元素的集合S={'do'，'for'，'repeat'，'while'}，各元素的查找概率依次為：p?=0.35，p?=0.15，p?=0.15，p?=0.35。將S保存在一個長度為4的順序表中。（1）若采用順序查找法，試設(shè)計元素在順序表中的最優(yōu)存儲順序，使查找S中任一元素的平均查找長度達到最小，并求出此時的平均查找長度。（2）若采用折半查找法，試設(shè)計元素在順序表中的最優(yōu)存儲順序，使查找S中任一元素的平均查找長度達到最小，并求出此時的平均查找長度。42.（12分）設(shè)將n（n>1）個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，將R中保存的序列循環(huán)左移p（0<p<n）個位置，即將R中的數(shù)據(jù)由（X?，X?，…，X???）變換為（X?，X???，…，X???，X?，X?，…，X???）。要求：（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C++或Java語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。43.（8分）某計算機主存按字節(jié)編址，邏輯地址和物理地址都是32位，頁表項大小為4字節(jié)。請回答下列問題：（1）若使用一級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為：|頁號（20位）|頁內(nèi)偏移量（12位）|則頁表占用多少字節(jié)？（2）若使用二級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為：|外層頁號（10位）|內(nèi)層頁號（10位）|頁內(nèi)偏移量（12位）|設(shè)外層頁表有T?項，內(nèi)層頁表有T?項，每個頁表項均存儲在一個物理頁中，請問T?和T?分別為多少？頁表共占用多少頁？44.（10分）某計算機的CPU主頻為500MHz，CPI為5（即執(zhí)行每條指令平均需5個時鐘周期）。假定某外設(shè)的數(shù)據(jù)傳輸率為0.5MB/s，采用中斷方式與主機進行數(shù)據(jù)傳送，以32位為傳輸單位，對應(yīng)的中斷服務(wù)程序包含18條指令，中斷服務(wù)的其他開銷相當于2條指令的執(zhí)行時間。請回答下列問題，要求給出計算過程。（1）在中斷方式下，CPU用于該外設(shè)I/O的時間占整個CPU時間的百分比是多少？（2）當該外設(shè)的數(shù)據(jù)傳輸率達到5MB/s時，改用DMA方式傳送數(shù)據(jù)。假定每次DMA傳送塊大小為5000B，且DMA預(yù)處理和后處理的總開銷為500個時鐘周期，則CPU用于該外設(shè)I/O的時間占整個CPU時間的百分比是多少？（假設(shè)DMA與CPU之間沒有訪存沖突）45.（7分）某系統(tǒng)采用改進型CLOCK置換算法，頁表項中字段A為訪問位，M為修改位。A=0表示頁未被訪問過，A=1表示頁被訪問過；M=0表示頁未被修改過，M=1表示頁被修改過。按（A，M）所有可能的取值，將頁分為四類：（0，0）、（0，1）、（1，0）、（1，1）。（1）試問該算法淘汰頁的次序是什么？（2）假定系統(tǒng)有5頁，其中頁1至頁5的（A，M）值分別為（1，1）、（0，1）、（1，0）、（0，0）、（1，0），若需淘汰一頁，將淘汰哪一頁？說明理由。46.（8分）某文件系統(tǒng)空間的最大容量為4TB（1TB=2??B），以磁盤塊為基本分配單位，磁盤塊大小為1KB。文件控制塊（FCB）包含一個512B的索引表區(qū)。請回答下列問題：（1）假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的磁盤塊號。索引表項中塊號最少占多少字節(jié)？可支持的單個文件最大長度是多少？（2）假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第0～7字節(jié)采用直接索引結(jié)構(gòu)，第8～15字節(jié)采用一級間接索引結(jié)構(gòu)，第16～23字節(jié)采用二級間接索引結(jié)構(gòu)，第24～31字節(jié)采用三級間接索引結(jié)構(gòu)。其中，每個索引表項占4字節(jié)，且所有磁盤塊按順序編號。問該文件系統(tǒng)可支持的單個文件最大長度是多少？47.（12分）某網(wǎng)絡(luò)拓撲如下圖所示，其中路由器內(nèi)網(wǎng)接口、DHCP服務(wù)器、WWW服務(wù)器與主機1均采用靜態(tài)IP地址配置，相關(guān)地址信息見圖中標注；主機2～主機N通過DHCP服務(wù)器動態(tài)獲取IP地址。```plaintext+----------------+|Internet|+----------------+||+----------------+|Router|||||+----------------+||+----------------+|DHCPServer|||+----------------+||+----------------+|WWWServer|||+----------------+||+----------------+|Switch|+----------------+|||Host1||00|||||+----------------+|||Host2-HostN|```（1）DHCP服務(wù)器可分配的IP地址范圍是多少？（2）主機2使用DHCP獲取IP地址的過程中，發(fā)送的第一個廣播包的目的IP地址是什么？封裝該廣播包的以太網(wǎng)幀的目的MAC地址是什么？（3）假設(shè)主機2首次成功獲取到的IP地址為10，當主機2再次需要獲取IP地址時，它向DHCP服務(wù)器發(fā)送的第一個請求包中包含的源IP地址是什么？參考答案單項選擇題1.A2.A3.B4.D5.B6.A7.C8.C9.C10.A11.B12.D13.B14.B15.D16.C17.C18.A19.B20.B21.A22.A23.D24.C25.B26.D27.C28.C29.D30.C31.B32.C33.A34.A35.B36.D37.C38.C39.C40.C綜合應(yīng)用題41.（1）順序查找時，按查找概率由大到小排列元素，即{'do'，'while'，'for'，'repeat'}。平均查找長度ASL=0.35×1+0.35×2+0.15×3+0.15×4=2.1。（2）折半查找時，按元素值的大小排序（這里可以按字典序），即{'do'，'for'，'repeat'，'while'}。平均查找長度ASL=(1×0.35+2×0.15+2×0.15+3×0.35)=2。42.（1）算法基本設(shè)計思想：先將數(shù)組的前p個元素逆置，再將數(shù)組的后n-p個元素逆置，最后將整個數(shù)組逆置。（2）以下是使用Java語言實現(xiàn)的代碼：```javapublicclassCircularShift{publicstaticvoidreverse(int[]R,intstart,intend){while(start<end){inttemp=R[start];R[start]=R[end];R[end]=temp;start++;end--;}}publicstaticvoidcircularShift(int[]R,intp){intn=R.length;reverse(R,0,p-1);//逆置前p個元素reverse(R,p,n-1);//逆置后n-p個元素reverse(R,0,n-1);//逆置整個數(shù)組}publicstaticvoidmain(String[]args){int[]R={1,2,3,4,5,6,7};intp=3;circularShift(R,p);for(intnum:R){System.out.print(num+"");}}}```（3）時間復(fù)雜度：三次逆置操作，每次逆置操作的時間復(fù)雜度為O(n/2)，所以總的時間復(fù)雜度為O(n)?？臻g復(fù)雜度：只使用了常數(shù)級的額外空間，所以空間復(fù)雜度為O(1)。43.（1）頁號為20位，頁表項數(shù)為22?個，每個頁表項大小為4字節(jié)，所以頁表占用的字節(jié)數(shù)為22?×4=4MB。（2）外層頁號10位，所以T?=21?項；內(nèi)層頁號10位，所以T?=21?項。每個頁表項存儲在一個物理頁中，外層頁表占21?頁，內(nèi)層頁表共21?×21?頁，所以頁表共占用21?+21?×21?=21?(1+21?)頁。44.（1）外設(shè)數(shù)據(jù)傳輸率為0.5MB/s，以32位（4B）為傳輸單位，則每秒傳輸次數(shù)為0.5MB/4B=0.5×22?/4=128×102次。每次中斷服務(wù)程序包含18條指令，其他開銷相當于2條指令，共20條指令。每條指令平均需5個時鐘周期，CPU主頻為500MHz，即每秒500×10?個時鐘周期。CPU用于該外設(shè)I/O的時鐘周期數(shù)為128×102×20×5。CPU用于該外設(shè)I/O的時間占整個CPU時間的百分比為(128×102×20×5)/(500×10?)×100%=2.56