2009-計算機考研408真題及答案LtD2009年計算機統考真題一．單項選擇題，每小題2分，共80分。

1.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是A.棧B.隊列C.樹D.圖2.設棧S和隊列Q的初始狀態均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是A．1B.2C.3D.43.給定二叉樹圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。若遍歷后的結點序列為3，1，7，5，6，2，4，則其遍歷方式是9.已知關鍵序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關鍵字3，調整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若數據元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結果，則該排序算法只能是A．起泡排序B.插入排序C.選擇排序D.二路歸并排序11.馮·諾依曼計算機中指令和數據均以二進制形式存放在存儲器中，CPU區分它們的依據是A．指令操作碼的譯碼結果B.指令和數據的尋址方式C.指令周期的不同階段D.指令和數據所在的存儲單元12.一個C語言程序在一臺32位機器上運行。程序中定義了三個變量xyz，其中x和z是int型，y為short型。當x=127，y=-9時，執行賦值語句z=x+y后，xyz的值分別是A．X=0000007FH，y=FFF9H，z=00000076HA．X=0000007FH，y=FFF9H，z=FFFF0076HA．X=0000007FH，y=FFF7H，z=FFFF0076HA．X=0000007FH，y=FFF7H，z=00000076H13.浮點數加減運算過程一般包括對階、尾數運算、規格化、舍入和判溢出等步驟。設浮點數的階碼和尾數均采用補碼表示，且位數分別為5位和7位（均含2位符號位）。若有兩個數X=27×29/32，Y=25×5/8，則用浮點加法計算X+Y的最終結果是A．001111100010B.001110100010C．010000010001D.發生溢出14.某計算機的Cache共有16塊，采用2路組相聯映射方式（即每組2塊）。每個主存塊大小為32字節，按字節編址。主存129號單元所在主存塊應裝入到的Cache組號是A．0B.2C.4D.615.某計算機主存容量為64KB，其中ROM區為4KB，其余為RAM區，按字節編址。現要用2K×8位的ROM芯片和4K×4位的RAM芯片來設計該存儲器，則需要上述規格的ROM芯片數和RAM芯片數分別是A．1、15B．2、15C．1、30D．2、3016.某機器字長16位，主存按字節編址，轉移指令采用相對尋址，由兩個字節組成，第一字節為操作碼字段，第二字節為相對位移量字段。假定取指令時，每取一個字節PC自動加1。若某轉移指令所在主存地址為2000H，相對位移量字段的內容為06H，則該轉移指令成功轉以后的目標地址是A.2006HB.2007HC.2008HD.2009H17.下列關于RISC的敘述中，錯誤的是A．RISC普遍采用微程序控制器B．RISC大多數指令在一個時鐘周期內完成C．RISC的內部通用寄存器數量相對CISC多D．RISC的指令數、尋址方式和指令格式種類相對CISC少18.某計算機的指令流水線由四個功能段組成，指令流經各功能段的時間（忽略各功能段之間的緩存時間）分別是90ns、80ns、70ns和60ns，則該計算機的CPU時鐘周期至少是A．90nsB.80nsC.70nsD.60ns19.相對于微程序控制器，硬布線控制器的特點是A．指令執行速度慢，指令功能的修改和擴展容易B．指令執行速度慢，指令功能的修改和擴展難C．指令執行速度快，指令功能的修改和擴展容易D．指令執行速度快，指令功能的修改和擴展難20.假設某系統總線在一個總線周期中并行傳輸4字節信息，一個總線周期占用2個時鐘周期，總線時鐘頻率為10MHz，則總線帶寬是A．10MB/sB.20MB/SC.40MB/SD.80MB/S21.假設某計算機的存儲系統由Cache和主存組成，某程序執行過程中訪存1000次，其中訪問Cache缺失（未命中）50次，則Cache的命中率是A．5%B.9.5%C.50%D.95%22.下列選項中，能引起外部中斷的事件是A．鍵盤輸入B.除數為0C.浮點運算下溢D.訪存缺頁23.單處理機系統中，可并行的是I進程與進程II處理機與設備III處理機與通道IV設備與設備A．I、II和IIIB.I、II和IVC.I、III和IVD.II、III和IV24.下列進程調度算法中，綜合考慮進程等待時間和執行時間的是A．時間片輪轉調度算法B.短進程優先調度算法C.先來先服務調度算法D.高響應比優先調度算法25.某計算機系統中有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是A．2B.3C.4D.526．分區分配內存管理方式的主要保護措施是A．界地址保護B.程序代碼保護C.數據保護D.棧保護27.一個分段存儲管理系統中，地址長度為32位，其中段號占8位，則最大段長是A．2的8次方字節B.2的16次方字節C.2的21次方字節D.2的32次方字節28.下列文件物理結構中，適合隨機訪問且易于文件擴展的是A．連續結構B.索引結構C.鏈式結構且磁盤塊定長D.鏈式結構且磁盤塊變長29.假設磁頭當前位于第105道，正在向磁道序號增加的方向移動。現有一個磁道訪問請求序列為35，45，12，68，110，180，170，195，采用SCAN調度（電梯調度）算法得到的磁道訪問序列是A．110，170，180，195，68，45，35，12B.110，68，45，35，12，170，180，195C.110，170，180，195，12，35，45，68D.12，35，45，68，110，170，180，19530.文件系統中，文件訪問控制信息存儲的合理位置是A．文件控制塊B.文件分配表C.用戶口令表D.系統注冊表31．設文件F1的當前引用計數值為1，先建立F1的符號鏈接（軟鏈接）文件F2，再建立F1的硬鏈接文件F3，然后刪除F1。此時，F2和F3的引用計數值分別是A．0、1B.1、1C.1、2D.2、132．程序員利用系統調用打開I/O設備時，通常使用的設備標識是A．邏輯設備名B.物理設備名C.主設備號D.從設備號33.在OSI參考模型中，自下而上第一個提供端到端服務的層次是A．數據鏈路層B.傳輸層C.會話層D.應用層34．在無噪聲情況下，若某通信鏈路的帶寬為3kHz，采用4個相位，每個相位具有4種振幅的QAM調制技術，則該通信鏈路的最大數據傳輸速率是A．12kbpsB.24kbpsC.48kbpsD.96kbps35.數據鏈路層采用了后退N幀（GBN）協議，發送方已經發送了編號為0~7的幀。當計時器超時時，若發送方只收到0、2、3號幀的確認，則發送方需要重發的幀數是A．2B.3C.4D.536.以太網交換機進行轉發決策時使用的PDU地址是A．目的物理地址B.目的IP地址C.源物理地址D.源IP地址37.在一個采用CSMA/CD協議的網絡中，傳輸介質是一根完整的電纜，傳輸速率為1Gbps，電纜中的信號傳播速度是200000km/s。若最小數據幀長度減少800比特，則最遠的兩個站點之間的距離至少需要A．增加160mB.增加80mC.減少160mD.減少80m38.主機甲和主機乙間已建立一個TCP連接，主機甲向主機乙發送了兩個連續的TCP段，分別包含300字節和500字節的有效載荷，第一個段的序列號為200，主機乙正確接收到兩個段后，發送給主機甲的確認序列號是A．500B.700C.800D.100039．一個TCP連接總是以1KB的最大段發送TCP段，發送方有足夠多的數據要發送。當擁塞窗口為16KB時發生了超時，如果接下來的4個RTT（往返時間）時間內的TCP段的傳輸都是成功的，那么當第4個RTT時間內發送的所有TCP段都得到肯定應答時，擁塞窗口大小是A．7KBB.8KBC.9KBD.16KB40.FTP客戶和服務器間傳遞FTP命令時，使用的連接是A．建立在TCP之上的控制連接B.建立在TCP之上的數據連接C.建立在UDP之上的控制連接D.建立在UDP之上的數據連接二．綜合應用題。共70分。41.（10分）帶權圖（權值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑。假定從初始頂點到目標頂點之間存在路徑，現有一種解決該問題的方法：①設最短路徑初始時僅包含初始頂點，令當前頂點u為初始頂點；②選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當前頂點u=v；③重復步驟②，直到u是目標頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。42.（15分）已知一個帶有表頭結點的單鏈表，結點結構為datalink假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的結點（k為正整數）。若查找成功，算法輸出該結點的data值，并返回1；否則，只返回0。要求：（1）描述算法的基本設計思想（2）描述算法的詳細實現步驟（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C或C++或JAVA語言實現），關鍵之處請給出簡要注釋。43.（8分）某計算機的CPU主頻為500MHz，CPI為5（即執行每條指令平均需5個時鐘周期）。假定某外設的數據傳輸率為0.5MB/s，采用中斷方式與主機進行數據傳送，以32位為傳輸單位，對應的中斷服務程序包含18條指令，中斷服務的其他開銷相當于2條指令的執行時間。請回答下列問題，要求給出計算過程。（1）在中斷方式下，CPU用于該外設I/O的時間占整個CPU時間的百分比是多少？（2）當該外設的數據傳輸率達到5MB/s時，改用DMA方式傳送數據。假設每次DMA傳送大小為5000B，且DMA預處理和后處理的總開銷為500個時鐘周期，則CPU用于該外設I/O的時間占整個CPU時間的百分比是多少？（假設DMA與CPU之間沒有訪存沖突）44.（13分）某計算機字長16位，采用16位定長指令字結構，部分數據通路結構如圖所示。圖中所有控制信號為1時表示有效、為0時表示無效。例如控制信號MDRinE為1表示允許數據從DB打入MDR，MDRin為1表示允許數據從內總線打入MDR。假設MAR的輸出一直處于使能狀態。加法指令“ADD（R1），R0”的功能為（R0）+（（R1））→（R1），即將R0中的數據與R1的內容所指主存單元的數據相加，并將結果送入R1的內容所指主存單元中保存。數據通路結構下表給出了上述指令取值和譯碼階段每個節拍（時鐘周期）的功能和有效控制信號，請按表中描述方式用表格列出指令執行階段每個節拍的功能和有效控制信號。功能和控制信號時鐘功能有效控制信號C1MAR←(PC)PCout,MARinC2MDR←M(MAR)PC←(PC)+1MemR,MDRinEPC+1C3IR←(MDR)MDRout,IRinC4指令譯碼無45.（7分）三個進程P1、P2、P3互斥使用一個包含N（N>0）個單元的緩沖區。P1每次用produce（）生成一個正整數并用put（）送入緩沖區某一空單元中；P2每次用getodd（）從該緩沖區中取出一個奇數并用countodd（）統計奇數個數；P3每次用geteven（）從該緩沖區中取出一個偶數并用counteven（）統計偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。46.（8分）請求分頁管理系統中，假設某進程的頁表內容如下表所示。頁表內容頁號頁框（PageFrame）號有效位（存在位）0101H11—02254H1頁面大小為4KB，一次內存的訪問時間是100ns，一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為108ns（已含更新TLB和頁表的時間），進程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設①TLB初始為空；②地址轉換時先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時間）；③有效位為0表示頁面不在內存，產生缺頁中斷，缺頁中斷處理后，返回到產生缺頁中斷的指令處重新執行。設有虛地址訪問序列2362H、1565H、25A5H，請問：（1）依次訪問上述三個虛地址，各需多少時間？給出計算過程。（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。47．（9分）某公司網絡拓撲圖如下圖所示，路由器R1通過接口E1、E2分別連接局域網1、局域網2，通過接口L0連接路由器R2，并通過路由器R2連接域名服務器與互聯網。R1的L0接口的IP地址是；R2的L0接口的IP地址是，L1接口的IP地址是，E0接口的IP地址是；域名服務器的IP地址是。R1和R2的路由表結構為：目的網絡IP地址子網掩碼下一跳IP地址接口將IP地址空間/24劃分為兩個子網，分配給局域網1、局域網2，每個局域網分配的地址數不少于120個，請給出子網劃分結果。說明理由或給出必要的計算過程。請給出R1的路由表，使其明確包括到局域網1的路由、局域網2的路由、域名服務器的主機路由和互聯網的路由。請采用路由聚合技術，給出R2到局域網1和局域網2的路由。2009年計算機統考真題參考答案一．選擇題

1

2

3

4

5

6

7

8

9

10

B

C

D

B

C

B

A

D

A

B

11

12

13

14

15

16

17

18

19

20

C

D

D

C

D

C

A

A

D

B

21

22

23

24

25

26

27

28

29

30

D

A

D

D

C

A

C

B

A

A

31

32

33

34

35

36

37

38

39

40

B

A

B

B

C

A

D

D

C

A

選擇題部分答案解析：1.此題考察各數據結構的特點。棧的特點是先進后出。隊列的特點是先進先出。樹的特點是節點的前驅只能有一個的數據結構。圖是最復雜的數據結構，它是前驅和后繼都可以有多個的網狀結構。2.元素abcdefg依次進入棧，bdcfeag依次出隊，那么他們在棧中操作順序依次為：a入棧、b入棧、b出棧、c入棧、d入棧、d出棧、c出棧、e入棧、f入棧、f出棧、e出棧、a出棧、g入棧、g出棧。這其間棧中數據最多有3個。3.一看第一個遍歷出來的元素是3，所以后序遍歷4.平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1.。5.第6層有8個葉節點，說明這個完全二叉樹最多共7層，所以樹的節點數為：1+2+4+8+16+32+48=111。8.B樹是一種多叉平衡查找樹。一棵m階的B樹，或為空樹，或為滿足下列特性的m叉樹：

①樹中每個結點至多有m棵子樹；

②若根結點不是葉子結點，則它至少有兩棵子樹；

③除根之外的所有非葉子結點至少有「m/2]棵子樹；

④所有的非葉子結點中包含卞列數據信息

(n，A0，K1，A1，K2，A2，…，Kn，An)

其中：Ki(i=1，2，…，n)為關鍵字，且Ki<Ki+1(i=1，2，…，n-1)：Ai(i=0，1，…，n)

⑤所有的葉子結點都出現在同一層次上，并且不帶信息(可以看作縣外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指針為空)。9.堆調整算法的應用10.解此題必須熟知各種排序方法的步驟。11.考察CPU區分指令和數據的方法：取指令和取數據發生在指令的不同階段。13.熟悉浮點運算過程14.熟悉組相聯映射的方式。組相聯的映象規則：

(1)主存和Cache按同樣大小劃分成塊。

(2)主存和Cache按同樣大小劃分成組。

(3)主存容量是緩存容量的整數倍，將主存空間按緩沖區的大小分成區，主存中每一區的組數與緩存的組數相同。

(4)當主存的數據調入緩存時，主存與緩存的組號應相等，也就是各區中的某一塊只能存入緩存的同組號的空間內，但組內各塊地址之間則可以任意存放，即從主存的組到Cache的組之間采用直接映象方式；在兩個對應的組內部采用全相聯映象方式。15.需要ROM片數：4K*8/2K*8=2，需要RAM片數：60K*8/4K*4=30.16.相對尋址：以當前程序計數器pc的內容為基址，加上指令給出的一字節補碼數（偏移量）形成新的pc值的尋址方式稱為相對尋址。17.精簡指令集的特點：統一指令編碼(例如，所有指令中的op-code永遠位于同樣的位位置、等長指令)，可快速解譯；泛用的緩存器，所有緩存器可用于所有內容，以及編譯器設計的單純化(不過緩存器中區分了整數和浮點數)；單純的尋址模式(復雜尋址模式以簡單計算指令序列取代)；硬件中支持少數數據型別(例如，一些CISC計算機中存有處理字節字符串的指令。這在RISC計算機中不太可能出現)。RISC設計上同時也有哈佛內存模塊特色，凡指令流和數據流在概念上分開；這意味著更改代碼存在的內存地址對處理器執行過的指令沒有影響（因為CPU有著獨立的指令和數據緩存），至少在特殊的同步指令發出前。在另一面，這允許指令緩存和數據緩存同時被訪問，通常能改進運行效率。18.時鐘周期以最大的流水段為準19.硬布線控制器是早期設計計算機的一種方法。硬布線控制器是將控制部件做成產生專門固定時序控制信號的邏輯電路，產生各種控制信號，因而又稱為組合邏輯控制器。這種邏輯電路以使用最少元件和取得最高操作速度為設計目標，因為該邏輯電路由門電路和觸發器構成的復雜樹型網絡，所以稱為硬布線控制器。微程序控制的基本思想，就是仿照通常的解題程序的方法，把操作控制信號編成所謂的“微指令”，存放到一個只讀存儲器里．當機器運行時，一條又一條地讀出這些微指令，從而產生全機所需要的各種操作控制信號，使相應部件執行所規定的操作20.10M/2*4=20MB/S21.(1000-50)/1000=95%25.K的最小值是4，當K為4是，每個進程若占用2臺打印機，則發生死鎖。27.段號占8位，則段內地址24位。也就是2^24位，即2^21字節。29.SCAN調度算法就是電梯調度算法，顧名思義就是如果開始時磁頭往外就一直要到最外面，然后再返回向里（磁頭編號一般是最外面為0號往里增加），就像電梯若往下則一直要下到最底層才會再上升一樣。32.無論有多少物理設備都要映射為邏輯設備使用。這些設備在程序員看來是沒有差別的。33.傳輸層和應用層都是端到端的。自下而上次一個端到端的是傳輸層。35.在后退N協議式ARQ中，接收方應以正確的順序把沙鷗到的報文遞交到主機。發送方在不等待確認就連續發送許多幀的情況下，有可能發了N個幀以后，才發現尚未收到對前面幀的確認信息，也許某個幀在傳輸過程中出錯了。接收方因這一幀出錯，查出后不會交給本地主機，對后面再發送來的N個幀也可能均不接收而丟棄。換句話說，接收方只能按順序接收。36.以太網交換機工作在物理層，所以進行交換決策時使用的是物理地址。38.主機乙發送給主機甲的確認序列號是期待接收到的數據的序列號39.擁塞控制是指節制沿著一條通路的分組流以保持網絡部件免于變得過量擁擠所采用的控制規程。

二．綜合應用題41.該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權圖，如果按照題中的原則，從A到C的最短路徑為A→B→C，事實上其最短路徑為A→D→C。42.（1）算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當前節點的前K個節點。當遍歷到鏈表的最后一個節點時，指針P所指向的節點即為所查找的節點。（2）詳細實現步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當前遍歷的節點，指針P指向P1所指向節點的前K個節點，如果P1之前沒有K個節點，那么P指向表頭節點。用整型變量i表示當前遍歷了多少節點，當i>k時，指針p隨著每次遍歷，也向前移動一個節點。當遍歷完成時，p或者指向表頭就節點，或者指向鏈表中倒數第K個位置上的節點。（3）算法描述：IntLocateElement(linklistlist,intk){P1=list->link;P=list;i=1;while(P1){P1=P1->link;i++;if(i>k)p=p->next;//如果i>k,則p也往后移}if(p==list)return0;//說明鏈表沒有k個結點else{printf(“%d\n“,p->data);return1;}}43.（1）在中斷方式下，每32位（4B）被中斷一次，故每秒中斷0.5MB/4B=0.5×106/4=12.5×104次要注意的是，這里是數據傳輸率，所以1MB=106B。因為中斷服務程序包含18條指令，中斷服務的其他開銷相當于2條指令的執行時間，且執行每條指令平均需5個時鐘周期，所以，1秒內用于中斷的時鐘周期數為（18+2）×5×12.5×104=12.5×106（2）在DMA方式下，每秒進行DMA操作5MB/5000B=5×106/5000=1×103次因為DMA預處理和后處理的總開銷為500個時鐘周期，所以1秒鐘之內用于DMA操作的時鐘周期數為500×1×103=5×105故在DMA方式下，占整個CPU時間的百分比是（（5×105）/（500×106））×100%=0.1%44.指令執行階段每個節拍的功能和有效控制信號如下所示時鐘功能有效控制信號C5MAR←(R1)PCout,MARinC6MDR←M(MAR)MemR,MDRinEC7A←(R0)R0out,AinC8AC←(MDR)+(A)MDRout,Addr,ACinC9MDR←(AC)ACout,MDRinC10M(MAR)←MDRMDRoutE,MemW45.定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產者與消費者之間的同步；mutex控制進程間互斥使用緩沖區。程序如下：Vars1=0,s2=0,empty=N,mutex=1;ParbeginP1:beginX=produce();/*生成一個數*/P(empty);/*判斷緩沖區是否有空單元*/P(mutex);/*緩沖區是否被占用*/Put();Ifx%2==0V(s2);/*如果是偶數，向P3發出信號*/elseV(s1);/*如果是奇數，向P2發出信號*/V(mutex);/*使用完緩沖區，釋放*/end.P2:beginP(s1);/*收到P1發來的信號，已產生一個奇數*/P(mutex);/*緩沖區是否被占用*/Getodd();Countodd():=countodd()+1;V(mutex);/*釋放緩沖區*/V(empty);/*向P1發信號，多出一個空單元*/end.P3:beginP(s2)/*收到P1發來的信號，已產生一個偶數*/P(mutex);/*緩沖區是否被占用*/Geteven();Counteven():=counteven()+1;V(mutex);/*釋放緩沖區*/V(empty);/*向P1發信號，多出一個空單元*/end.Parend.46.（1）根據頁式管理的工作原理，應先考慮頁面大小，以便將頁號和頁內位移分解出來。頁面大小為4KB，即212，則得到頁內位移占虛地址的低12位，頁號占剩余高位。可得三個虛地址的頁號P如下（十六進制的一位數字轉換成4位二進制，因此，十六進制的低三位正好為頁內位移，最高位為頁號）：2362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號，合成物理地址后訪問主存100ns，共計10ns+100ns+100ns=210ns。1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進行缺頁中斷處理108ns，合成物理地址后訪問主存100ns，共計10ns+100ns+108ns+100ns≈108ns。25A5H：P=2，訪問快表，因第一次訪問已將該頁號放入快表，因此花費10ns便可合成物理地址，訪問主存100ns，共計10ns+100ns=110ns。（2）當訪問虛地址1565H時，產生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據題目的置換算法，應淘汰0號頁面，因此1565H的對應頁框號為101H。由此可得1565H的物理地址為101565H。47.（1）無類IP地址的核心是采用不定長的網絡號和主機號，并通