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

20102010年計算機408統(tǒng)考真題第1頁，共8頁2010年全國碩士研究生入學統(tǒng)一考試計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題-、單項選擇題（第1?40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求）.若元素a,h（:再力」依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是OA.dcebfa B.CbdaefC.bcaefdD.afedcb.某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a,b,c,d,e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是。C.dbcaeA.bacdeB.dbaceD.ecbadC.dbcaeA.bacdeB.dbaceD.ecbad2010年計算機408統(tǒng)考真題第2010年計算機408統(tǒng)考真題第#頁，共8頁A.13,48C.24,53B.24,48D.24,90A.41B.82C.113A.13,48C.24,53B.24,48D.24,90A.41B.82C.113D.122二叉樹。在新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是?.在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉結點個數(shù)是.對"522）個權值均不相同的字符構造成哈夫曼樹。下列關于該哈夫曼樹的敘述中，箱誤的是。A.該樹一定是一棵完全二叉樹.樹中一定沒有度為1的結點C.樹中兩個權值最小的結點一定是兄弟結點D.樹中任一非葉結點的權值一定不小于下一層任一結點的權值.若無向圖G=(V,E)中含有7個頂點，要保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是_—.已知一個長度為16的順序表L,其元素按關鍵字有序排列。若采用折半查找法查找一個L中不存在的元素，則關鍵字的比較次數(shù)最多的是一?。A.4 B.5 C.6 D.7.采用遞歸方式對順序表進行快速排序。下列關于遞歸次數(shù)的敘述中，正確的是，A.遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關B.每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C.每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D.遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關.對一組數(shù)據(jù)(2,12,16,88,5,10)進行排序，若前三趟排序結果如下:第一趟排序結果：2,12,16,5,10,88第二趟排序結果:2,12,5,10,16,88第三趟排序結果:2,5,10,12,16,88則采用的排序方法可能是。A.冒泡排序 B.希爾排序 C.歸并排序 D.基數(shù)排序.下列選項中，能縮短程序執(zhí)行時間的措施是一一.=I.提高CPU時鐘頻率 II.優(yōu)化數(shù)據(jù)通路結構IIL對程序進行編譯優(yōu)化A.僅I和II B.僅I和IIIC.僅II和IIID.I、II和III.假定有4個整數(shù)用8位補碼分別表示rl=FEH,r2=F2H,r3=90H,r4=F8H,若將運算結果存放在一個8位寄存器中，則下列運算中會發(fā)生溢出的是。A.rlχr2 B.r2χr3 C.rlχr4 D.r2χr4.假定變量i、f和d的數(shù)據(jù)類型分別為int、0oat和double(int用補碼表示，日Oat和double分別用IEEE754單精度和雙精度浮點數(shù)格式表示)，已知i=785,f=1.5678e3,d=L5el00。若在32位機器中執(zhí)行下列關系表達式，則結果為“真”的是—..；I.i=(int)(0oat)i IL打=(0oat)(int)fIIL—出Oat)(double)f IV.(d+q-d=fA.僅I和II B.僅I和IIIC.僅II和IIID.僅皿和IV.假定用若干-2Kχ4位的芯片組成一個8Kχ8位的存儲器，則地址OBlFH所在芯片的最小地址是,0地址是,0A.OoooH B.060OH C.070OH D.080OH.下列有關RAM和RoM的敘述中，正確的是。RAM是易失性存儲器，ROM是非易失性存儲器ILRAM和ROM都采用隨機存取方式進行信息訪問R^和ROM都可用作CaCheB.僅II和IIIB.僅II和IIID.僅II、III和IVA.僅I和IIC.僅I、II和IV.下列命.中組合情況中，一次訪存過程中不可能發(fā)生的是一一一。TLB未命中，CaChe未命中，Page未命中TLB未命中，CaChe命中，Page命中TLB命中，CaChe未命中，Page命中TLB命中，CaChe命中，Page未命中.下列寄存器中，匯編語言程序員可見的是。A.存儲器地址寄存器（MAR） B.程序計數(shù)器（PC）C.存儲器數(shù)據(jù)寄存器（MDR） D.指令寄存器（IR）.下列選項中，不會引起指令流水線阻塞的是一一。A.數(shù)據(jù)旁路（轉發(fā)） B.數(shù)據(jù)相關C.條件轉移 D.資源沖突.下列選項中的英文縮寫均為總線標準的是。A.PCI、CRT、USB、EISA B. ISA、CPI、VESA、EISAC.ISA、SCSI、RAM、MIPS D. ISA、EISA、PCI、PCI-EXPreSS21.單級中斷系統(tǒng)中，中斷服務程序內(nèi)的執(zhí)行順序是。.保護現(xiàn)場 II.開中斷 III.關中斷 IV.保存斷點V.中斷事件處理 VI.恢復現(xiàn)場 VII.中斷返回A.IfVfV-VII B.III→I→V→VΠC.IIIfIVfVfVIfVII D.IV-I-VfVIfVII22.假定一臺計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600×1200,顏色深度為24位，幀頻為85Hz,顯存總帶寬的50%用來刷新屏幕，則需要的顯存總帶寬至少約為：A.245Mbps B.979MbpsC.1958Mbps D.7834Mbps23.下列選項中,A.系統(tǒng)調(diào)用操作系統(tǒng)提供給應用程序的接口是23.下列選項中,A.系統(tǒng)調(diào)用操作系統(tǒng)提供給應用程序的接口是B.中斷C.庫函數(shù)D.原語24.下列選項中,I.用戶登錄成功A.僅I24.下列選項中,I.用戶登錄成功A.僅I和IIIII.啟動程序執(zhí)行C.僅I和IIID.I、II和IIIA.0、126.下列選項中B.1、0C.1、2D.2、0降低進程優(yōu)先級的合理時機是導致創(chuàng)建新進程的操作是IL設備分配B.僅II和III25.設與某資源關聯(lián)的信號量初值為3,當前值為1。若"表示該資源的可用個數(shù)，N表示等待該資源的進程數(shù)，則m、N分別是^。A.A.進程的時間片用完C.進程長期處于就緒列隊中B.進程剛完成I/O,進入就緒列隊D.進程從就緒狀態(tài)轉為運行狀態(tài).進程PO和Pl的共享變量定義及其初值為：booleanflag[2];inttum=0;flag[0]=FALSE;flag[l]=FALSE;若進程PO和Pl訪問臨界資源的類C偽代碼實現(xiàn)如下:voidP0() voidP0() //進程Po{While(TRUE){flag[0]=TRUE;turn=l;while(flag[l]&&(turn==l));臨界區(qū)；flag[0]=FALSE;voidPl() //進程Pl{―while(TRUE){flag[l]=TRUE;turn=0;while(flag[0]&&(turn==0));臨界區(qū)；flag[l]=FALSE;則并發(fā)執(zhí)行進程Po和Pl時產(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)象.某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55MB(初始為空閑)，采用最佳適配(BeStFit)算法，分配和釋放的順序為：分配15MB,分配30MB,釋放15MB,分配8MB,分配6MB,此時主存中最大空閑分區(qū)的大小是oA.7MB B.9MB C.IOMB D.15MB.某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為2l。B,頁表項大小為2B,邏輯地址結構為I 頁目錄號 I頁號I頁內(nèi)偏移豆邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是. A.64 B.128 C.256 D.512.設文件索引結點中有7個地址項，其中4個地址項是直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為440。若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256B,則可表示的單個文件最大長度是 。A.33KB B.519KB C.1057^ D.16513KB.設置當前工作目錄的主要目的是一.A.節(jié)省外存空間 B.節(jié)省內(nèi)存空間C.加快文件的檢索速度 D.加快文件的讀/寫速度.本地用戶通過鍵盤登錄系統(tǒng)時，首先獲得鍵盤輸入信息的程序是.A.命令解釋程序 B.中斷處理程序C.系統(tǒng)調(diào)用服務程序 D.用戶登錄程序.下列選項中，不屬于網(wǎng)絡體系結構所描述的內(nèi)容是.

A.網(wǎng)絡的層次C.協(xié)議的內(nèi)部實現(xiàn)細節(jié)B.每層使用的協(xié)議D.每層必須完成的功能.在右圖所示的采用“存儲-轉發(fā)”方式的分組交換網(wǎng)’皿，_一=__=； 絡中，所有鏈路的數(shù)據(jù)傳輸速率為IOOMbps,分組大小為A.網(wǎng)絡的層次C.協(xié)議的內(nèi)部實現(xiàn)細節(jié)B.每層使用的協(xié)議D.每層必須完成的功能1000B,其中分組頭大小為20B。若主機Hl向主機H2發(fā)送 V=√一個大小為980000B的文件，則在不考慮分組拆裝時間和傳 一J播延遲的情況下，從Hl發(fā)送開始到H2接收完為止，需要的時間至少是__。A.80ms B.80.08msC.80.16msD.80.24ms.某自治系統(tǒng)內(nèi)采用RIP協(xié)議，若該自治系統(tǒng)內(nèi)的路由器Rl收到其鄰居路由器R2的距離矢量，距離矢量中包含信息<netl,16>,則能得出的結論是。A.心可以經(jīng)過Rl到達netl,跳數(shù)為17B.R2可以到達netl,跳數(shù)為16C.Rl可以經(jīng)過旭到達netl,跳數(shù)為17D.Rl不能經(jīng)過R2到達netl.若路由器R因為擁塞丟棄IP分組，則此時R可向發(fā)出該IP分組的源主機發(fā)送的ICMP報文類型是.A.路由重定向 B.目的不可達C.源點抑制 D.超時.某網(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ù)分別是。A.32,8 B. 32,6 C.8,32 D.8,30.下列網(wǎng)絡設備中，能夠抑制廣播風暴的是。I.中繼器 II.集線器 III.網(wǎng)橋 IV.路由器A.僅I和II B.僅III C.僅III和IV D.僅IV.主機甲和主機乙之間已建立了一個TCP連接，TCP最大段長度為1000B。若主機甲的當前擁塞窗口為4000B,在主機甲向主機乙連續(xù)發(fā)送兩個最大段后，成功收到主機乙發(fā)送的第一個段的確認段，確認段中通告的接收窗口大小為2000B,則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是。A.1000 B.2000 C.3000 D.4000.如果本地域名服務器無緩存，當采用遞歸方法解析另一網(wǎng)絡某主機域名時，用戶主機、本地域名服務器發(fā)送的域名請求消息數(shù)分別為。A.一條、一條 B.一條、多條C.多條、一條D.多條、多條二、綜合應用題(第41?47題，共70分).(10分)將關鍵字序列(7,8,30,11,18,9,14)散列存儲到散列表中。散列表的存儲空間是一個下標從0開始的一維數(shù)組，散列函數(shù)為H(key)=(keyx3)mod7,處理沖突采用線性探測再散列法，要求裝填(載)因子為0.7。1)請畫出所構造的散列表。2)分別計算等概率情況下查找成功和查找不成功的平均查找長度。.(13分)設將〃(〃>1)個整數(shù)存放到一維數(shù)組R中。試設計一個在時間和空間兩方面都盡可能高效的算法。將R中保存的序列循環(huán)左移P(0<p<")個位置，即將R中的數(shù)據(jù)由(Xo,Xl,…，X1)變換為(Xp,Xp+1,?",Xrt-i,Xo,Xi,…，Xp-i)。要求：

1）給出算法的基本設計思想。2）根據(jù)設計思想，采用C、C+堿JaVa語言描述算法，關鍵之處給出注釋。3）說明你所設計算法的時間復雜度和空間復雜度。.（11分）某計算機字長為16位，主存地址空間大小為128KB,按字編址。采用單字長指令格式，指令各字段定義如下圖所示。15 1211 65 OOPMSRsMdRd源操作數(shù) 目的操作數(shù)轉移指令采用相對尋址方式，相對偏移量用補碼表示，尋址方式定義見下表。Ms^d尋址方式助記符含義000B寄存器直接而操作數(shù)=（Rn）OOlB寄存器間接(Rn)操作數(shù)=（（Rn））OlOB寄存器間接、自增W)+操作數(shù)=((E)),&)+If心011B相對DN)轉移目標地址=（PC）+（E）注：（X）表示存儲器地址X或寄存器X的內(nèi)容。請回答下列問題：1）該指令系統(tǒng)最多可有多少條指令？該計算機最多有多少個通用寄存器？存儲器地址寄存器（MAR）和存儲器數(shù)據(jù)寄存器（MDR）至少各需要多少位？2）轉移指令的目標地址范圍是多少？3）若操作碼OoIoB表示加法操作（助記符為add）,寄存器R4和R5的編號分別為100B和101B,R4的內(nèi)容為1234H,R5的內(nèi)容為5678H,地址1234H中的內(nèi)容為5678H,地址5678H中的內(nèi)容為1234H,則匯編語描為“add（R4）,（R5）+（（逗號前為源操作數(shù)，逗號后為目的操作數(shù)）對應的機器碼是什么（用十六進制表示）？該指令執(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]程序A：inta[256][256]程序B：inta[256][256]intsum_arrayl()intsum_arrayl(){inti,j,sum=0;for(i=0;i<256;i++)for(j=0;j<256;j++)sum+=a[i][j];returnsum;}intsum_array2(){inti,j,sum=0;for(j=0;j<256;j++)for(i=0;i<256;i++)sum÷=a[i][j];returnsum;}假定int類型數(shù)據(jù)用32位補碼表示，程序編譯時i、j、s、均分配在寄存器中，數(shù)組a按行優(yōu)先方式存放，其首地址為320（十進制數(shù)）。請回答下列問題，要求說明理由或給出計算過程。1）若不考慮用于CaChe—致性維護和替換算法的控制位，則數(shù)據(jù)CaChe的總容量?多少？2）數(shù)組元素a[0][31]和a[l][l]各自所在的主存塊對應的CaChe行號分另I提多少（CaChe行號從0開始）？3）程序A和B的數(shù)據(jù)訪問命中率各是多少？哪個程序的執(zhí)行時間更短？.（7分）假設計算機系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個磁盤塊的空閑狀態(tài)。1）請說明在上述條件下如何進行磁盤塊空閑狀態(tài)的管理。2）設某單面磁盤旋轉速度為60001pm,每個磁道有100個扇區(qū)，相鄰磁道間的平均移動時間為1ms。若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動（見下圖），磁道號請求隊列為50,90,30,120,對請求隊列中的每個磁道需讀取1個隨機分布的扇區(qū)，則讀完這4個扇區(qū)點共需要多少時間？要求給出計算過程。3）如果將磁盤替換為隨機訪問的FIaSh半導體存儲器（如U盤