計算機考研專業(yè)課真題及答案解析

1、一、單項選擇題： 1-40 題，每題 20 分共 80 分。在每個小題給出的四個選項中選正確答案。1、若元素 a、b、c、d、e、f 依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是（）A、dcebfaB、cbdaefC、bcaefdD、afedcb2、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順順序是（）A、bacdeB、dbaceC、dbcaeD、ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）4、在下列所示的平衡二叉樹中插入關鍵字 48 后得到一棵新平衡二叉樹， 在新平衡二叉樹中，關鍵

2、字 37 所在結點的左、右子結點中保存的關鍵字分別是（）A、13，48B、24，48C、24，53D、24，905、在一棵度數(shù)為 4 的樹 T 中，若有 20 個度為 4 的結點， 10 個度為 3 的結點， 1 個度為 2 的結點， 10 個度為 1 的結點，則樹 T 的葉結點個數(shù)是（）A、41B、82C、113精選文庫D、1226、對 n（n>=2）個權值均不相同的字符構成哈弗曼樹，關于該樹的敘述中，錯誤的是（）A、該樹一定是一棵完全二交叉B、樹中一定沒有度為1 的結點C、樹中兩個權值最小的結點一定是兄弟結點D、樹中任一非葉結點的權值一定不小于下一層任一結點的權值7、若無向圖 G=（

3、V.E）中含 7 個頂點，則保證圖 G在任何情況下都是連通的，則需要的邊數(shù)最少是（）A、6B、15C、16D、218、對下圖進行拓撲排序，可以得到不同的拓撲序列的個數(shù)是（）A、4B、3C、2D、19、已知一個長度為 16 的順序表 L，其元素按關鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多的是（）A、4B、5C、6D、7-2精選文庫10、采用遞歸方式對順序表進行快速排序， 下列關于遞歸次數(shù)的敘述中， 正確的是（）A、遞歸次數(shù)于初始數(shù)據(jù)的排列次數(shù)無關B、每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)（勤思考研）C、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D、遞歸次數(shù)與每次

4、劃分后得到的分區(qū)處理順序無關11、對一組數(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ù)排序法12. 下列選項中，能縮短程序執(zhí)行時間的措施是 ()1. 提高 CPU時鐘頻率 2. 優(yōu)化通過數(shù)據(jù)結構 3. 優(yōu)化通過程序A.僅1和2B.僅1和3C,僅2和3D.1,2,313. 假定有 4 個整數(shù)用 8 位補碼分別表示 r1=FEH，r2=F2H，r3=9

5、0H，r4=F8H，若將運算結果存放在一個 8 位寄存器中，則下列運算會發(fā)生益處的是 ()A. r1 x r2B. r2 x r3C. r1 x r4D. r2 x r414. 假定變量 i ，f ，d 數(shù)據(jù)類型分別為 int, float, double(int 用補碼表示，float和 double 用 IEEE754 單精度和雙精度浮點數(shù)據(jù)格式表示 ) ，已知 i=785 ，-3精選文庫f=1.5678e3 ，d=1.5e100，若在 32 位機器中執(zhí)行下列關系表達式，則結果為真的是 ()(I) i=(int)(float)I(II)f=(float)(int)f(III)f=(floa

6、t)(double)f (IV)(d+f)-d=fA. 僅I 和II B. 僅I 和III C. 僅II 和IIID. 僅III和IV15. 假定用若干個 2K x 4 位芯片組成一個 8K x 8 為存儲器，則 0B1FH所在芯片的最小地址是 ()A.0000HB.0600HC.0700HD.0800H16. 下列有關 RAM和 ROM得敘述中正確的是 ()I RAM 是易失性存儲器， ROM是非易失性存儲器II RAM 和 ROM都是采用隨機存取方式進行信息訪問III RAM 和 ROM都可用做 Cache IV RAM和 ROM都需要進行刷新A. 僅I 和IIB. 僅II 和IIIC.

7、僅I ，II ，III-4精選文庫D. 僅 II ，III ，IV17. 下列命令組合情況，一次訪存過程中，不可能發(fā)生的是()A.TLB 未命中， Cache 未命中， Page未命中B.TLB 未命中， Cache 命中， Page命中C.TLB 命中， Cache未命中， Page命中D.TLB 命中， Cache命中， Page未命中18. 下列寄存器中，反匯編語言程序員可見的是 ()A. 存儲器地址寄存器 (MAR)B. 程序計數(shù)器 (PC)C. 存儲區(qū)數(shù)據(jù)寄存器 (MDR)D. 指令寄存器 (IR)19. 下列不會引起指令流水阻塞的是 () A. 數(shù)據(jù)旁路B. 數(shù)據(jù)相關C. 條件轉移

8、D. 資源沖突20. 下列選項中的英文縮寫均為總線規(guī)范的是 () A. PCI 、 CRT、USB、EISAB. ISA 、 CPI、VESA、 EISA C. ISA 、 SCSI、 RAM、 MIPSD. ISA 、 EISA、 PCI、 PCI-Express21、單級中斷系統(tǒng)中，中斷服務程序執(zhí)行順序是（）I 保護現(xiàn)場II 開中斷-5精選文庫III 關中斷IV 保存斷點V 中斷事件處理VI 恢復現(xiàn)場VII 中斷返回A、I->V->VI->II->VIIB、III->I->V->VIIC、III->IV->V->VI->VI

9、ID、IV->I->V->VI->VII22、假定一臺計算機的顯示存儲器用DRAM芯片實現(xiàn)，若要求顯示分辨率為1600*1200，顏色深度為 24 位，幀頻為 85HZ，現(xiàn)實總帶寬的 50%用來刷新屏幕，則需要的顯存總帶寬至少約為（）A、245MbpsB、979MbpsC、1958MbpsD、7834Mbps23、下列選項中，操作S 提供的給應程序的接口是（）A、系統(tǒng)調(diào)用B、中斷C、庫函數(shù)D、原語24、下列選項中，導制創(chuàng)進新進程的操作是（）I 用戶登陸成功 II設備分配 III啟動程序執(zhí)行A、僅I 和II-6精選文庫B、僅 II和 IIIC、僅 I 和 IIID、I 、

10、II 、III25、設與某資源相關聯(lián)的信號量初值為 3，當前值為 1，若 M表示該資源的可用個數(shù)， N表示等待該資源的進程數(shù)，則 M， N分別是（）A、0，1B、1，0C、1，2D、2，026、下列選項中，降低進程優(yōu)先權級的合理時機是（）A、進程的時間片用完B、進程剛完成 I/O ，進入就緒列隊C、進程長期處于就緒列隊D、進程從就緒狀態(tài)轉為運行狀態(tài)27、進行 PO和 P1 的共享變量定義及其初值為（）booleam turn=0。flag0=false。 flag1=false。若進行 P0 和 P1 訪問臨界資源的類C 代碼實現(xiàn)如下：void p0() /進程 p0 vo

11、id p1 () /進程 p1 while（ TRUE） while（TRUE）flag0=TRUE 。 turn=1 。 flag0=TRUE 。 turn=0 。While flag1&&(turn=1) While flag0&&(turn=0)-7精選文庫臨界區(qū)；臨界區(qū)；flag0=FALSE 。 flag1=FALSE 。 則并發(fā)執(zhí)行進程PO和 P1 時產(chǎn)生的情況是（）A、不能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象B、不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象C、能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象D、能保證進程互斥進入臨界區(qū)，不會出

12、現(xiàn)“饑餓”現(xiàn)象28、某基于動態(tài)分區(qū)存儲經(jīng)管的計算機，其主存容量為 55Mb（初始為空），采用最佳適配（ Best Fit ）算法，分配和釋放的順序為：分配 15Mb，分配 30Mb，釋放 15Mb，分配 6Mb，此時主存中最大空閑分區(qū)的大小是（）A、7MbB、9MbC、10MbD、15Mb29、某計算機采用二級頁表的分頁存儲經(jīng)管方式， 按字節(jié)編制，頁大小為 2（ 10）【 2 的 10 次方，下同】字節(jié)，頁表項大小為 2 字節(jié)，邏輯地址結構為頁目錄號頁號頁內(nèi)偏移量邏輯地址空間大小為 2（10）頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是（）A、64B、128C、256-8精選文庫

13、D、51230設文件索引節(jié)點中有 7 個地址項，其中 4 個地址為直接地址索引， 1 個地址項是二級間接地址索引， 每個地址項的大小為 4 字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為 256 字節(jié)，則可表示的單個文件最大長度是 ()A. 33KBB. 519KBC. 1057KBD. 16513KB31. 設當前工作目錄的主要目的是 () A. 節(jié)省外存空間B. 節(jié)省內(nèi)存空間C. 加快文件的檢索速度D. 加快文件的讀寫速度32. 本地用戶通過鍵盤登陸系統(tǒng)是，首先獲得鍵盤輸入信息的程序時()A. 命令解釋程序B. 中斷處理程序C. 系統(tǒng)調(diào)用程序D. 用戶登錄程序33.下列選項中，不屬于網(wǎng)絡體系結構中

14、所描述的內(nèi)容是()A. 網(wǎng)絡的層次B. 每一層使用的協(xié)議C. 協(xié)議的內(nèi)部實現(xiàn)細節(jié)D. 每一層必須完成的功能34. 在下圖所表示的采用”存儲 - 轉發(fā)”方式分組的交換網(wǎng)絡中所有的鏈路的數(shù)據(jù)傳輸速度為 100Mbps，分組大小為 1000B，其中分組頭大小為 20B 若主機 H1 向主機 H2發(fā)送一個大小為 980000 的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從 H1 發(fā)送到 H2 接受完為止，需要的時間至少是 ()-9精選文庫A.80msB. 80.08msC. 80.16msD. 80.24ms35. 某自治系統(tǒng)采用 RIP 協(xié)議，若該自治系統(tǒng)內(nèi)的路由器 R1收到其鄰居路由器R2的

15、距離矢量中包含的信息 <net1 ，16>，則可能得出的結論是 ()A. R2 可以經(jīng)過 R1到達 net1 ，跳數(shù)為 17B. R2 可以到達 net1 ，跳數(shù)為 16C. R1 可以經(jīng)過 R2到達 net1 ，跳數(shù)為 17D.R1 不能經(jīng)過 R2到達 net136. 若路由器 R 因為擁塞丟棄 IP 分組，則此時 R 可向發(fā)出該 IP 分組的源主機的ICMP報文件的類型是 ()A. 路由重定向B. 目的不可達C. 源抑制D. 超時37、某網(wǎng)絡的 IP 地址空間為采用長子網(wǎng)劃分，子網(wǎng)掩碼為，則該網(wǎng)絡的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)的最大可分配地址個數(shù)為 ()A、32，8B、32，6C、

16、8，32D、8，3038、下列網(wǎng)絡設備中，能夠抑制網(wǎng)絡風暴的是（）I 中斷器-10精選文庫II 集線器III 網(wǎng)橋IV 路由器A、僅I 和IIB、僅 IIIC、僅 III和 IVD、僅 IV39、主機甲和主機乙之間建立一個 TCP連接，TCP最大段長度為 1000 字節(jié)，（勤思考研）若主機甲的當前擁塞窗口為 4000 字節(jié)，在主機甲向主機乙連續(xù)發(fā)送 2 個最大段后，成功收到主機乙發(fā)送的第一段的確認段， 確認段中通告的接收窗口大小為 2000 字節(jié)，則此時主機甲還可以向主機乙發(fā)送的最大字節(jié)數(shù)是（）A、1000B、2000C、3000D、400040、如果本地域名服務無緩存， 當采用遞歸方法解讀另

17、一網(wǎng)絡某主機域名時， 用戶主機本地域名服務器發(fā)送的域名請求條數(shù)分別為（）A、1條，1 條B、1 條，多條C、多條， 1 條D、多條，多條二、綜合應用題： 41-47 小題，共 70 分41. （ 10 分）將關鍵字序列 (7 、8、30、11、 18、9、14) 散列存儲到散列表中，（勤思考研）散列表的存儲空間是一個下標從 0 開始的一個一維數(shù)組散列 , 函數(shù)為： H(key)=(key x 3)MODT ，處理沖突采用線性探測再散列法，要求裝載因子為 0.7-11精選文庫問題：(1). 請畫出所構造的散列表。(2). 分別計算等概率情況下，查找成功和查找不成功的平均查找長度。42.（13 分

18、）設將 n(n>1) 個整數(shù)存放到一維數(shù)組R 中。設計一個在時間和空間兩方面盡可能高效的算法。將R 中的序列循環(huán)左移P（0<P<n）個位置，即將R中的數(shù)據(jù)由 (X0, X1,Xn-1) 變換為 (Xp, Xp- 1Xn-1 ，X0, X1Xp-1) 要求：（ 1）、給出算法的基本設計思想。（ 2）、根據(jù)設計思想， 采用 C 或 C+或 JAVA語言描述算法， 關鍵之處給出注釋。（ 3）、說明你所設計算法的時間復雜度和空間復雜度。43、(11 分 ) 某計算機字節(jié)長為16 位，主存地址空間大小為128KB，按字編址。采用字長指令格式，指令名字段定義如下：1512 116 50O

19、PM5R5MdRd源操作數(shù)目的操作數(shù)轉移指令采用相對尋址，相對偏移是用補碼表示，尋址方式定義如下：Ms/Md尋址方式助記符含義000B寄存器直接Rn操作數(shù) =(Rn)001B寄存器間接(Rn)操作數(shù) =（ Rn）010B寄存器間接、自增(Rn)+操作數(shù) =(Rn) ，(Rn)+1->Rn011B相對D(Rn)轉移目標地址 =(PC)+(Rn)注： (X) 表示有存儲地址 X 或寄存器 X 的內(nèi)容，請回答下列問題：(1) 、該指令系統(tǒng)最多可有多少指令該計算機最多有多少個通用寄存器？（勤思教育）存儲地址寄存器 (MAR)和存儲數(shù)據(jù)寄存器 (MDR)至少各需多少位？(2) 、轉移指令的目標地址

20、范圍是多少？(3) 、若操作碼 0010B 表示加法操作 ( 助記符為 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ù) )對應的機器碼是什么 ( 用十六進制 ) 該指令執(zhí)行后，（勤思教育） 哪些寄存器和存儲單元的內(nèi)容會改變？改變后的內(nèi)容是什么？-12精選文庫44、(12 分 ) 某計算機的主存地址空間大小為 256M，按字節(jié)編址。指令 Cache分離，均有 8 個

21、Cache 行，每個 Cache行大小為 64MB，數(shù)據(jù) Cache采用直接映射方式，（勤思教育）現(xiàn)有兩個功能相同的程序 A 和 B，其偽代碼如下：程序 A:int sum_array1()int i, j, sum = 0。for (i = 0。 i < 256。 i+)for (j= 0。 j < 256。 j+)sum += aij。return sum。程序 B:int sum_array2()int i, j, sum = 0。for (j = 0。 j < 256。 j+)for (i= 0。 i < 25

22、6。 i+)sum += aij。return sum。-13精選文庫假定 int 類型數(shù)據(jù)用 32 位補碼表示， 程序編譯時 i ，j ，sum均分配在寄存器中，數(shù)組 a 按行優(yōu)先方式存放，其地址為 320( 十進制 ) 。請回答，要求說明理由或給出計算過程。(1) 、若不考慮用于 Cache一致維護和替換算法的控制位，則數(shù)據(jù) Cache 的總容量為多少(2) 、數(shù)組元素 a031 和 a11 各自所在的主存塊對應的 Cache 行號分別是多少 (Cache 行號從 0 開始 )(3) 、程序 A 和 B 得數(shù)據(jù)訪問命中率各是多少？哪個程序的執(zhí)行時間短？45、（7 分）假設計算機系統(tǒng)采用 C

23、SCAN(循環(huán)掃描 ) 磁盤調(diào)度策略 , 使用 2KB的內(nèi)存空間記錄 16384 個磁盤的空閑狀態(tài)(1) 、請說明在上述條件如何進行磁盤塊空閑狀態(tài)的經(jīng)管。(2) 、設某單面磁盤的旋轉速度為每分鐘 6000 轉，（勤思教育）每個磁道有 100 個扇區(qū)，相臨磁道間的平均移動的時間為 1ms.若在某時刻，磁頭位于 100 號磁道處，并沿著磁道號增大的方向移動 ( 如下圖所示 ), 磁道號的請求隊列為 50， 90，30，120 對請求隊列中的每個磁道需讀取 1 個隨機分布的扇區(qū)，則讀完這個扇區(qū)點共需要多少時間？需要給出計算過程。46.(8 分) 設某計算機的邏輯地址空間和物理地址空間均為 64KB，

24、按字節(jié)編址。（勤思教育）某進程最多需要 6 頁數(shù)據(jù)存儲空間，頁的大小為 1KB，操作系統(tǒng)采用固定分配局部置換策略為此進程分配 4 個頁框。頁號頁框號裝入時間訪問位071301142301222001391601當該進程執(zhí)行到時刻260 時，要訪問邏輯地址為17CAH的數(shù)據(jù)。請回答下列問題：(1) 、該邏輯地址對應的頁號時多少(2) 、若采用先進先出 (FIFO) 置換算法，該邏輯地址對應的物理地址？要求給出計算過程。(3) 、采用時鐘 (Clock) 置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程。（設搜索下一頁的指針按順時針方向移動，且指向當前 2 號頁框，示-14精選文庫意圖如

25、下）47、（9 分）某局域網(wǎng)采用 CSMA/CD協(xié)議實現(xiàn)介質(zhì)訪問控制， 數(shù)據(jù)傳輸率為 100M/S，主機甲和主機已的距離為 2KM，信號傳播速速時 200000M/S請回答下列問題，并給出計算過程。（ 1）、若主機甲和主機已發(fā)送數(shù)據(jù)時發(fā)生沖突，則從開始發(fā)送數(shù)據(jù)時刻起，到兩臺主機均檢測到?jīng)_突時刻為止，最短經(jīng)過多長時間？最長經(jīng)過多長時間？ ( 假設主機甲和主機已發(fā)送數(shù)據(jù)時，其它主機不發(fā)送數(shù)據(jù) )（ 2）、若網(wǎng)絡不存在任何沖突與差錯， 主機甲總是以規(guī)范的最長以太數(shù)據(jù)幀 (1518 字節(jié) ) 向主機已發(fā)送數(shù)據(jù)，主機已每成功收到一個數(shù)據(jù)幀后，立即發(fā)送下一個數(shù)據(jù)幀，（勤思教育）此時主機甲的有效數(shù)據(jù)傳輸速率

26、是多少？ ( 不考慮以太網(wǎng)幀的前導碼 )-15精選文庫答案1-5DCBCB6-10AABAD11-15ADCBD16-20ADBAD21-25ADACB26-30AABBC31-35CBCAA36-40CBCAA41、(1) 因為裝填因子為 0.7 ，數(shù)據(jù)總數(shù)為 7，所以存儲空間長度為L = 7/0.7 = 10因此可選 T=10，構造的散列函數(shù)為H(key) = (key*3) MOD 10線性探測再散列函數(shù)為：Hi = ( H(key)+ di ) MOD 10 , (di = 1,2,3.9)因此，各數(shù)據(jù)的下標為H(7) = (7*3) MOD 10 = 1H(8) = (8*3) MO

27、D 10 = 4H(30) = (30*3) MOD 10 = 0H(11) = (11*3) MOD 10 = 3H(18) = (18*3) MOD 10 = 4H1 = ( H(18) +1) MOD 10 = 5H(9) = (9*3) MOD 10 = 7H(14) = (14*3) MOD 10 = 2-16精選文庫所構造的散列表如下：012345678930714118189(2) 查找成功的平均查找長度為：ASL1 = (1+1+1+1+2+1+1)/7 = 8/7查找不成功的平均查找長度為：ASL2 =(7+6+5+4+3+2+1+2+1+1) = 3.242、（ 1）建立一

28、個可以放下 p 個整數(shù)的輔助隊列，將數(shù)組 R 中的前 p 個整數(shù)依次進入輔助隊列，將 R 中后面的 n-p 個整數(shù)依次前移 p 個位置，將輔助隊列中的數(shù)據(jù)依次出隊，依次放入 R 中第 n-p 個整數(shù)開始的位置。（ 2）使用 c 語言描述算法如下：void Shift(int *pR, int n, int p) /pR是指向數(shù)組 R的指針， n 為存放的整數(shù)個數(shù)，/p為循環(huán)左移的個數(shù)int tempp。 /輔助數(shù)組，存放要移出的整數(shù)。int i=0。while(i<p) /將 R 中前 p 個數(shù)據(jù)存入輔助數(shù)組中。tempi = pRi。i+ 。i = 0。while(i < n-p

29、) /將 R 中從第 p 個整數(shù)開始的整數(shù)前移p 個位置。pRi = pRp+i。-17精選文庫i+ 。i = 0。while(i < p) /將輔助數(shù)組中的 p 個數(shù)據(jù)放到 R 中第 n-p 個數(shù)據(jù)的后面。pRn-p+i = tempi。i+ 。return 。（ 3）所設計的算法的時間復雜度為O(n), 空間復雜度為 O(p)43、（ 1） OP字段占 4 個 bit位，因此該指令系統(tǒng)最多有24 = 16 條指令； Rs/Rd為 3 個 bit ，因此最多有 23 = 8個通用寄存器； 128K/2 = 64k = 216,所以存儲器地址寄存器位數(shù)至少為16 位，指令字長度為16 位

30、，所以存儲器數(shù)據(jù)寄存器至少為 16 位。（ 2）因為 Rn是 16 位寄存器，所以可以尋址的目標地址范圍是 64K，即整個存儲器空間。（ 3）對應的機器碼是 230DH，該指令執(zhí)行后 R5的內(nèi)容變?yōu)?5679H，地址 5678H 的內(nèi)容變?yōu)?68AC。44. 解題思路：（ 1） cache 總容量等于 cache 每一行的容量乘以 cache 的行數(shù)。大家需要注意的是，本題 cache 總容量分別等于數(shù)據(jù) cache 和指令 cache 的總和。（ 2）分別計算出 A031A11 的地址的值，然后根據(jù)直接映射方式除以cache 行的大小，與 cache 行數(shù)求余，所得的余數(shù)就是所映射的cache 塊。（ 3） cache 的命中率等于訪問 cache 的次數(shù)除以 cache 的次數(shù)加上訪問內(nèi)存的次數(shù)。本題通過計算得知，命中率高