2010考研試題及答案及資料LtD1、若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是（

D

）A：dcebfa

B：cbdaef

C：dbcaef

D：afedcb2、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順序是（C）A：bacde

B：dbace

C：dbcae

D：ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（

B

）4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是（C）A：13，48

B：24，48

C：24，53

D：24，905、在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則樹T的葉節(jié)點個數(shù)是（B）A：41

B：82

C：113

D：12218、下列存儲器中，匯編語言程序員可見的是（B）A：存儲器地址寄存器（MAR）

B：程序計數(shù)器（PC）C：存儲器數(shù)據(jù)寄存器（MDR）

D：指令寄存器（IR）19、下列不會引起指令流水阻塞的是（A）A：數(shù)據(jù)旁路

B：數(shù)據(jù)相關(guān)

C：條件轉(zhuǎn)移

D：資源沖突20、下列選項中的英文縮寫均為總線標(biāo)準(zhǔn)的是（D）A：PCI、CRT、USB、EISA

B：ISA、CPI、VESA、EISAC：ISA、SCSI、RAM、MIPS

D：ISA、EISA、PCI、PCI-Express21、單級中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是（A）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、VII22、假定一臺計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600*1200，顏色深度為24位，幀頻為85Hz，顯示總帶寬的50%用來刷新屏幕，則需要的顯存總帶寬至少約為（D）A：245MbpsB：979MbpsC：1958MbpsD：7834Mbps23、下列選項中，操作S提供的給應(yīng)用程序的接口是（A）A：系統(tǒng)調(diào)用B：中斷C：庫函數(shù)D：原語24、下列選項中，導(dǎo)致創(chuàng)進新進程的操作是（C）I用戶成功登陸

II設(shè)備分配

III啟動程序執(zhí)行A：僅I和IIB：僅II和IIIC：僅I和IIID：I，II，III25、設(shè)與某資源相關(guān)聯(lián)的信號量初值為3，當(dāng)前值為1，若M表示該資源的可用個數(shù)，N表示等待資源的進程數(shù)，則M,N分別是（B）A：0，1B：1，0C：1，2D：2，026、下列選項中，降低進程優(yōu)先權(quán)級的合理時機是（A）A：進程的時間片用完B：進程剛完成Z/O，進入就緒隊列C：進程長期處于就緒隊列中D：就緒從就緒狀態(tài)轉(zhuǎn)為運行態(tài)27、進行P0和P1的共享變量定義及其初值為（A）booleanflag[2]；intturn=0；flag[0]=faulse；flag[1]=faulse；若進行P0和P1訪問臨界資源的類C代碼實現(xiàn)如下：Void

p0（）//進程p0

Void

p1（）//進程p1{while（TURE）}

{while（TURE）}Flag[0]=TURE;ture=1

Flag[1]=TURE;ture=1While（flag[1]&&（turn==1））

While（flag[0]&&（turn==0））臨界區(qū)：Flag[0]=FALSE;

Flag[1]=FALSE;}

}}

}則并發(fā)執(zhí)行進程P0和P1時產(chǎn)生的情況是：A：不能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象B：不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象C：能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象D：能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象28、某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55mb（初試為空間），采用最佳適配（Bestfit）算法，分配和釋放的順序為：分配15mb，分配30mb，釋放15mb，分配8mb，此時主存中最大空閑分區(qū)的大小是（B）A：7mbB：9mbC：10mbD：15mb29、某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編制，頁大小為216字節(jié)，頁表項大小為2字節(jié)，邏輯地址結(jié)構(gòu)為頁目編號頁號頁內(nèi)偏移量邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是（B）A：64B：128C：256D：51230、設(shè)文件索引節(jié)點中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件的最大長度是（C）A：33kbB：519kbC：1057kbD：16513kb31、設(shè)置當(dāng)前工作目錄的主要目的是（C）A：節(jié)省外存空間B：節(jié)省內(nèi)容空間C：加快文件的檢索速度D：加快文件的讀寫速度32、本地用戶通過鍵盤登錄系統(tǒng)時，首先獲得鍵盤輸入信息的程序是（B）A：命令解釋程序B：中斷處理程序C：系統(tǒng)調(diào)用程序D：用戶登錄程序33、下列選項中，不屬于網(wǎng)絡(luò)體系結(jié)構(gòu)中所描述的內(nèi)容是（C）A：網(wǎng)絡(luò)的層次B：每一層使用的協(xié)議C：協(xié)議的內(nèi)部實現(xiàn)細(xì)節(jié)D：每一層必須完成的功能34、在下圖所示的采用“存儲-轉(zhuǎn)發(fā)”方式分組的交換網(wǎng)絡(luò)中，所有鏈路的數(shù)據(jù)傳輸速度為100mbps，分組大小為1000B，其中分組頭大小20B，若主機H1向主機H2發(fā)送一個大小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發(fā)送到H2接收完為止，需要的時間至少是（A）A：80msB：80.08msC：80.16msD：80.24ms35、某自治系統(tǒng)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器R1收到其鄰居路由器R2的距離矢量中包含信息＜net1，16＞，則可能得出的結(jié)論是（A）A：R2可以經(jīng)過R1到達(dá)net1，跳數(shù)為17B：R2可以到達(dá)net1，跳數(shù)為16C：R1可以經(jīng)過R2到達(dá)net1，跳數(shù)為17D：R1不能進過R2到達(dá)net136、若路由器R因為擁塞丟棄IP分組，則此時R可以向發(fā)出該IP分組的源主機發(fā)送的ICMP報文件類型是（C）A：路由重定向B：目的不可達(dá)C：源抑制D：超時37、某網(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ù)為（B）A：32，8B：32，6C：8，32D：8，3038、下列網(wǎng)絡(luò)設(shè)備中，能夠抑制網(wǎng)絡(luò)風(fēng)暴的是（C）Ⅰ中繼器

Ⅱ集線器

Ⅲ網(wǎng)橋

Ⅳ路由器A：僅Ⅰ和ⅡB：僅ⅢC：僅Ⅲ和ⅣD：僅Ⅳ39、主機甲和主機乙之間已建立一個TCP連接，TCP最大段長度為1000字節(jié)，若主機甲的當(dāng)前擁塞窗口為4000字節(jié)，在主機甲向主機乙連接發(fā)送2個最大段后，成功收到主機乙發(fā)送的第一段的確認(rèn)段，確認(rèn)段中通告的接收窗口大小為2000字節(jié)，則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是（A）A：1000B：2000C：3000D：400040、如果本地域名服務(wù)無緩存，當(dāng)采用遞歸方法解析另一網(wǎng)絡(luò)某主機域名時，用戶主機本地域名服務(wù)器發(fā)送的域名請求條數(shù)分別為（A）A：1條，1條B：1條，多條C：多條，1條D：多條，多條二、綜合應(yīng)用題：41-47小題，共計70分41.（10分）將關(guān)鍵字序列（7、8、11、18、9、14）散列存儲到散列列表中，散列表的存儲空間是一個下標(biāo)從0開始的一個一維數(shù)組散列函數(shù)維：H（key）=（key×3）MODT，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7問題：（1）請畫出所構(gòu)造的散列表；（2）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。解答：（1）由裝載因子0.7，數(shù)據(jù)總數(shù)7個→存儲空間長度為10→P=10所以，構(gòu)造的散列表為：01234567893071411818.9..H（7）=（7×3）MOD10=1（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.242.（13分）設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設(shè)計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P（0﹤P﹤n）個位置，即將R中的數(shù)據(jù)由（X0X1……Xn-1）變換為（XpXp+1……Xn-1

X0

X1……Xp-1）要求：（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C++或JAVA語言表述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度解答：（1）前P個數(shù)依次進隊，while（1﹤n-p）A{i}-{i+p}：p個數(shù)依次出對，進入數(shù)組末尾（2）詳細(xì)程序略（3）時間復(fù)雜度O（N）;空間復(fù)雜度o(p)43.(11分)某計算機字長為16q位，主存地址空間大小為128KB，按字編址，采用字長指令格式，指令名字段定義如下：轉(zhuǎn)移指令采用相對尋址方式，相對偏移是用補碼表示，尋址方式定義如下：Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù)=（Rn）001B寄存器間接（Rn）操作數(shù)=（(Rn)）010B寄存器間接、自增（Rn）+操作數(shù)=（(Rn)），（Rn）+1→Rn011B相對D（Rn）轉(zhuǎn)移目標(biāo)地址=（PC）+（Rn）注：（X）表示有儲蓄地址X或寄存器X的內(nèi)容，請回答下列問題：（1）該指令系統(tǒng)最多可有多少條指令？該計算機最多有多少個通用寄存器？存儲器地址寄存器（MDR）至少各需多少位？（2）轉(zhuǎn)移指令的目標(biāo)地址范圍是多少？（3）若操作碼0010B表示加法操作（助記符為add），寄存器R4和R5的編號分別為100B和101B，R4的內(nèi)容為1234H，R5的內(nèi)容為5678H，地址1234H中的內(nèi)容為5678H中的內(nèi)容為1234H，則匯編語言為add（R4）.（R5）+（逗號前原操作數(shù)，都號后為目的操作數(shù)）對應(yīng)的機器碼是什么（用十六進制表示）？該指令執(zhí)行后，哪些寄存器和存儲單元的內(nèi)容會改變？改變后的內(nèi)容是什么？解答：該題的考點是指令系統(tǒng)設(shè)計，注意操作位數(shù)與指令條數(shù)的關(guān)系，地址碼與寄存器數(shù)的關(guān)系，指令字長與MOR的關(guān)系，存儲容量與MAR的關(guān)系，注意補碼計算的偏移地址。44.（12分）某計算機的主存地址空間為256MB，按字節(jié)編址，指令Cache分離‘均有8個Cache行，每個Cache行的大小為64MB，數(shù)據(jù)Cache采用直接映射方式，現(xiàn)有兩個功能相同的程序A和B,其偽代碼如下所示：假定int類型數(shù)據(jù)用32位補碼表示，程序編譯時i,j,sum均分配在寄存器中，數(shù)據(jù)a按行優(yōu)先方式存放，其地址為320（十進制數(shù)），請回答下列問題，要求說明理由或給出計算過程。（1）、若不考慮用于cache一致性維護和替換算法的控制位，則數(shù)據(jù)Cache的總?cè)萘渴嵌嗌?？?）、要組元素a[0][31]和a[1][1]各自所在的主存塊對應(yīng)的Cache行號分別是多少（Cache行號從0開始）？（3）、程序A和B的數(shù)據(jù)訪問命令中各是多少？那個程序的執(zhí)行時間更短？簡答：考點：Cache容量計算，直接映射方式的地址計算，以及命中率計算（行優(yōu)先遍歷與列優(yōu)先遍歷命中率分別很大）45、（7分）假設(shè)計算機系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個磁盤塊的空間狀態(tài)（1）、請說明在上述條件下如何進行磁盤塊空閑狀態(tài)管理。（2）、設(shè)某單面磁盤旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)。每個磁道有100個扇區(qū)，相臨磁道間的平均移動時間為1ms.若在某時刻，磁頭位于100號磁道處，并沿著磁道號大的方向移動（如下圖所示），磁道號請求隊列為50.90.30.120.對請求隊列中的每個磁道需讀取1個隨機分布的扇區(qū)，則讀完這個扇區(qū)點共需要多少時間？要求給出計算過程。46.（8分）設(shè)某計算機的邏輯地址空間和物理地址空間均為64KB.按字節(jié)編址。若某進程最多需要6頁（Page）數(shù)據(jù)存儲空間，頁的大小為1KB.操作系統(tǒng)采用固定分配局部置換策略為此進程分配4個頁框（PageFame）.頁號頁根號裝入時刻訪問位071301142301222001391601當(dāng)該進程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請問答下列問題：（1）、該邏輯地址對應(yīng)的頁號是多少？（2）、若采用先進先出（FIFO）置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（3）、若采用時鐘（CLOCK）置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（設(shè)搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向2號頁框，示意圖如下。）解答：17CAH=(0001011111001010)2（1）頁大小為1K，所以頁內(nèi)偏移地址為10位，于是前6位是頁號，所以第一間的解為：5（2）FIFO，則被置換的頁面所在頁框為7，所以對應(yīng)的物理地址為（0001111