2010年考研計算機統(tǒng)考408真題

1、2010年考研計算機統(tǒng)考408真題單項選擇題若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是1。d c e b f ac b d a e fb c a e f da f e d c b某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a,b,c,d,e依次進入此隊列后再進行出隊操作，則不可能得到的出隊序列是2。b a c d ed b a c ed b c a ee c b a d下列線索二叉樹（用虛線表示線索），符合后序線索樹定義的是3。在圖B-1所示的平衡二叉樹，插入關(guān)鍵字48后得到一棵新平衡二叉樹。在

2、新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是4。圖B-113，4824，4824，5324，90在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3 的結(jié)點，10個度為1的結(jié)點，則樹T的葉結(jié)點個數(shù)是5。4182113112對n（n=2）個權(quán)值均不相同的字符構(gòu)造成赫夫曼樹。下列關(guān)于該赫夫曼樹的敘述中，錯誤的是6。該樹一定是一棵完全二叉樹樹中一定沒有度為1的結(jié)點樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值若無向圖G=(V,E)中含有7個頂點，要保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是7。6151621對圖B-2進行

3、拓撲排序，可以得到不同的拓撲序列的個數(shù)是8。4321已知一個長度為16的順序表L，其元素按關(guān)鍵字有序排列。若采用折半查找法查找一個L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多的是9。4567采用遞歸方式對順序表進行快速排序。下列關(guān)于遞歸次數(shù)的敘述中，正確的是10。遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關(guān)對一組數(shù)據(jù)（2,12,16,88,5,10）進行排序，若前三趟排序結(jié)果如下：第一趟排序結(jié)果：2,12,16,5,10,88第二趟排序結(jié)果：2,12,5,10,16,88第三趟排

4、序結(jié)果：2,5,10,12,16,88則采用的排序方法可能是11。冒泡排序希爾排序歸并排序基數(shù)排序下列選項中，能縮短短程序執(zhí)行時間的措施是12。I.提高CPU時鐘頻率II.優(yōu)化數(shù)據(jù)通路結(jié)構(gòu)III.對程序進行編譯優(yōu)化僅I和II僅I和III僅II和IIII、II和III假定有4個整數(shù)用8位補碼分別表示r1=FEH，r2=F2H，r3=90H，r4=F8H，若將運算結(jié)果存放在一個8位寄存器中，則下列運算中會發(fā)生溢出的是13。r1*r2r2*r3r1*r4r2*r4假定變量i，f和d的數(shù)據(jù)類型分別為int、float和double（int用補碼表示，float和double分別用IEEE754單精度和

5、雙精度浮點數(shù)格式表示），已知i=785，f=1.5678e3，d=1.5e100。若在32位機器執(zhí)行下列關(guān)系表達式，則結(jié)果為“真”的是14。Ii=(int)(float)iIIf=(float)(int)fIIIf=(float)(double)fIV(d+f)-d)=f僅I和II僅I和III僅II和III僅III和IV假定用若干個2K*4的芯片組成一個8K*8位的存儲器，則地址0B1FH所在芯片的最小地址是15。0000H0600H0700H0800H下列有關(guān)RAM和ROM的敘述中，正確的是16。I.RAM是易失性存儲器，ROM是非易失性存儲器II.RAM和ROM都采用隨機存取方式進行信息訪

6、問III.RAM和ROM都可用作CacheIV.RAM和ROM都需要進行刷新僅I和II僅II和III僅I、III和IV僅II、III和IV下列命中組合情況中，一次訪存過程中不可能發(fā)生的是17。TLB未命中，Cache未命中，Page未命中TLB未命中，Cache命中，Page命中TLB命中，Cache未命中，Page命中TLB命中，Cache命中，Page未命中下列寄存器中，匯編語言程序員可見的是18。存儲器地址寄存器（MAR）程序計數(shù)器（PC）存儲器數(shù)據(jù)寄存器（MDR）指令寄存器（IR）下列選項中，不會引起指令流水線阻塞的是19。數(shù)據(jù)旁路（轉(zhuǎn)發(fā)）數(shù)據(jù)相關(guān)條件轉(zhuǎn)移資源沖突下列選項中的英文縮寫均

7、為總線標準的是20。PCI、CRT、USB、EISAISA、CPI、VESA、EISAISA、SCSI、RAM、MIPSISA、EISA、PCI、PCI-Express單級中斷系統(tǒng)中，中斷服務程序內(nèi)的執(zhí)行順序是21。I.保護現(xiàn)場II.開中斷III.關(guān)中斷IV.保存斷點V.中斷事件處理VI.恢復現(xiàn)場VII.中斷返回IVVIIIVIIIIIIVVIIIIIIVVVIVIIIVIVVIVII假定一臺計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600*1200，顏色深度為24位，幀頻為85Hz，顯存總帶寬的50%用來刷新屏幕，則需要的顯存總帶寬至少約為22。245Mbit/s979Mbi

8、t/s1 958Mbit/s7 834Mbit/s下列選項中，操作系統(tǒng)提供給應用程序的接口是23。系統(tǒng)調(diào)用中斷庫函數(shù)原語下列選項中，導致創(chuàng)建新進程的操作是24。I.用戶登錄成功II.設(shè)備分配III.啟動程序執(zhí)行僅I和II僅II和III僅I和IIII 、II和III設(shè)與某資源關(guān)聯(lián)的信號量初值為3，當前值為1。若M表示該資源的可用個數(shù)，N表示等待該資源的進程數(shù)，則M、N分別是25。0、11、01、22、0下列選項中，降低進程優(yōu)先級的合理時機是26。進程的時間片用完進程剛完成I/O，進入就緒列隊進程長期處于就緒列隊中進程從就緒狀態(tài)轉(zhuǎn)為運行狀態(tài)進程P0和P1的共享變量定義及其初值為Boolean fl

9、ag2;Int turn=0;Flag0=FALAE; flag1=FALSE;若進程P0和P1訪問臨界資源的C偽代碼實現(xiàn)如下:則并發(fā)執(zhí)行進程P0和P1時產(chǎn)生的情形是27。不能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓“現(xiàn)象不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓“現(xiàn)象能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓“現(xiàn)象能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓“現(xiàn)象某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55MB（初始為空閑），采用最佳適配（Best Fit）算法，分配和釋放的順序為：分配15Mb，分配30MB，釋放15MB，分配8MB，分配6MB，此時主存中最大空閑分區(qū)的大小是28。7MB9MB10

10、MB15MB某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為210B，頁表項大小為2B，邏輯地址結(jié)構(gòu)為：邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是29。64128256512設(shè)文件索引節(jié)點中有7個地址項，其中4個地址項是直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4B。若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256B，則可表示的單個文件最大長度是30。33KB519KB1 057KB16 513 KB設(shè)計當前工作目錄的主要目的是31。節(jié)省外存空間節(jié)省內(nèi)存空間加快文件的檢索速度加快文件的讀/寫速度本地用戶通

11、過鍵盤登錄系統(tǒng)時，首先獲得鍵盤輸入信息的程序是32。命令解釋程序中斷處理程序系統(tǒng)調(diào)用服務程序用戶登錄程序下列選項中，不屬于網(wǎng)絡體系結(jié)構(gòu)所描述的內(nèi)容是33。網(wǎng)絡的層次每層使用的協(xié)議協(xié)議的內(nèi)部實現(xiàn)細節(jié)每層必須完成的功能在圖B-3所示的采用“存儲-轉(zhuǎn)發(fā)“方式的分組交換網(wǎng)絡中，所有鏈路的數(shù)據(jù)傳輸速率為100Bbit/s，分組大小為1000B，其中分組頭大小為20B。若主機H1向主機H2 發(fā)送一個大小為980 000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發(fā)送開始到H2接收完為止，需要的時間至少是34。圖B-380ms80.08ms80.16ms80.24ms某自治系統(tǒng)內(nèi)采用RIP協(xié)議

12、，若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量，距離矢量中包含信息，則能得出的結(jié)論是35。R1可以經(jīng)過R1到達net1，跳數(shù)為17R2可以到達net1，跳數(shù)為16R1可以經(jīng)過R2到達net1，跳數(shù)為17R1不能經(jīng)過R2到達net1若路由器R因為擁塞丟棄IP分組，則此時R可向發(fā)出該IP分組的源主機發(fā)送的ICMP報文類型是36。路由重定向目的不可達源點抑制超時某網(wǎng)絡的IP地址空間為192.168.5.0/24，采用定長子網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248，則該網(wǎng)絡中的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)分別是37。32，832，68，328，30下列網(wǎng)絡設(shè)備中，能

13、夠抑制廣播風暴的是38。I.中繼器II.集線器III.網(wǎng)橋IV.路由器僅I和II僅III僅III和IV僅IV主機甲和主機乙之間已建立了一個TCP連接，TCP最大段長度為1 000B。若主機甲的當前擁塞窗口為4 000B，在主機甲向主機乙連續(xù)發(fā)送兩個最大段后，成功收到主機乙發(fā)送的第一個段的確認段，確認段中通告的接收窗口大小為2 000B，則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是39。1 0002 0003 0004 000如果本地域名服務器無緩存，當采用遞歸方法解析另一網(wǎng)絡某主機域名時，用戶主機、本地域名服務器發(fā)送的域名請求消息數(shù)分別為40。一條、一條一條、多條多條、一條多條、多條綜合應用題

14、將關(guān)鍵字序列（7、8、30、11、18、9、14）散列存儲到散列表中。散列表的存儲空間是一個下標從0開始的一維數(shù)組，散列函數(shù)為H(key)=(key*3)mod 7，處理沖突采用線性控制再散列法，要求裝填（載）因子為0.7。請畫出所構(gòu)造的散列表。分別計算等概率情況下查找成功和查找不成功的平均查找長度。設(shè)將n(n1)個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面都盡可能高效的算法。將R中保存的序列循環(huán)左移p(0pn)個位置，即將R中的數(shù)據(jù)由(X0,X1,Xn-1)變換為(Xp,Xp+1,Xn-1,X0,X1,Xp-1)。要求：給出算法的基本設(shè)計思想。根據(jù)設(shè)計思想，采用C、C+或Java語

15、言描述算法，關(guān)鍵之處給出注釋。說明你所設(shè)計算法的時間復雜度和空間復雜度。某計算機字長為16位，主存地址空間大小為128KB，按字編址。采用單字長指令格式，指令各字段定義如圖B-4所示。轉(zhuǎn)移指令采用相對尋址方式，相對偏移量用補碼表示，尋址方式定義見表B-1.注：(X)表示存儲器地址X或寄存器X的內(nèi)容。請回答下列問題：該指令系統(tǒng)最多可有多少條指令？該計算機最多有多少個通用寄存器？存儲器地址寄存器（MAR）和存儲器數(shù)據(jù)寄存器（MAR）至少各需要多少位？轉(zhuǎn)移指令的目標地址范圍是多少？若操作碼0010B表示加法操作（助記符為add），寄存器R4和R5的編號分別為100B和101B，R4的內(nèi)容為1234H

16、，R5的內(nèi)容為5678H，地址1234H中的內(nèi)容為5678H，地址5678H中的內(nèi)容為1234H，則匯編語言為“add(R4),(R5)+”（逗號前為源操作數(shù)，逗號后為目的操作數(shù)）對應的機器碼是什么（用十六進制表示）？該指令執(zhí)行后，哪些寄存器和存儲單元中的內(nèi)容會改變？改變后的內(nèi)容是什么？某計算機的主存地址空間大小為256MB，按字節(jié)編址。指令Cache和數(shù)據(jù)Cache分離，均有8個Cache行，每個Cache行大小為64B，數(shù)據(jù)Cache采用直接映射方式?，F(xiàn)有兩個功能相同的程序A和B，其偽代碼如下：假定int類型數(shù)據(jù)用32位補碼表示，程序編譯時i、j、sum均分配在寄存器中，數(shù)組a按行優(yōu)先方式

17、存放，其首地址為320（十進制數(shù)）。請回答下列問題，要求說明理由或給出計算過程。若不考慮用于Cache一致性維護和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘繛槎嗌伲繑?shù)組元素a031和a11各自所在的主存塊對應的Cache行號分別是多少（Cache行號從0開始）？程序A和B的數(shù)據(jù)訪問命中率各是多少？哪個程序的執(zhí)行時間更短？假設(shè)計算機系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16 384個磁盤塊的空閑狀態(tài)。請說明在上述條件下如何進行磁盤塊空閑狀態(tài)的管理。設(shè)某單面磁盤旋轉(zhuǎn)速度為6000r/min，每個磁盤有100個扇區(qū)，相鄰磁盤間的平均移動時間為1ms。若在某時刻，磁盤位于

18、100號磁盤處，并沿著磁盤號增大的方向移動（如圖B-5所示），磁盤號請求隊列為50，90，30，120，對請求隊列中的每個磁盤需讀取1個隨機分布的扇區(qū)，則讀完這4個扇區(qū)點共需要多少時間？要求給出計算過程。如果將磁盤替換為隨機訪問的Flash半導體存儲器（如U盤、SSD等），是否有比CSCAN更高效的磁盤調(diào)度策略？若有，給出磁盤調(diào)度策略的名稱并說明理由，若無，說明理由。設(shè)某計算機的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。若某進程最多需要6頁（Page）數(shù)據(jù)存儲空間，頁的大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為此進程分配4個頁框（Page Frame）。在時刻260前的該進程訪問情況見表B-2（訪問位即使用位）。當該進程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)。請回答下列問題：該邏輯地址對應的頁號是多少？若采用先進先出（FIFO）置換算法，該邏輯地址的對應的物理地址是多少？要求給出計算過程。若采用時鐘（CLOCK）置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程（設(shè)搜索下一頁的指針沿順時針方向移動，且當前指向2號頁框，示意圖如圖B-6所示。）某局域網(wǎng)采用CSMA/CD協(xié)議實現(xiàn)介質(zhì)訪問控制，數(shù)據(jù)傳輸速率為10