統考計算機考研真題

單項選擇題，每小題2分，共80分。

i.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區，主機將要

輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯

結構應該是

A.棧B.隊列C.樹D.圖

2.設棧S和隊列Q的初始狀態均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即

進入隊列Q,且7個元素出隊的順序是bdcfeag,則棧S的容量至少

是A.1B.2C.3D.4

3.給定二叉樹圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表

根結點的右子樹。若遍歷后的結點序列為3,1,7,5,6,2,4,則其遍歷方

式是A.LRNB.NRLC.RLND.RNL

4.下列二叉排序樹中，滿足平衡二叉樹定義的是

5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數

最多是

A.39B.52C.lllD.119

6.將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原

來的森林中，u和v可能具有的關系是I.父子關系II.兄弟關系川.u的父結點與v的父

結點是兄弟關系

A.只有IIB.I和IIC.I和川和川

7.下列關于無向連通圖特性的敘述中，正確的是

I.所有頂點的度之和為偶數II.邊數大于頂點個數減1川.至少有一個頂點的度為1

A.只有IB,只有IIC.I和IID.I和III

8.下列敘述中，不符合m階B樹定義要求的是

A.根節點最多有m棵子樹B.所有葉結點都在同一層上

C.各結點內關鍵字均升序或降序排列D.葉結點之間通過指針鏈接

9.已知關鍵序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入關鍵字3,調整

后得到的小根堆是

A.3,5,12,8,28,20,15,22,19

B.3,5,12,19,20,15,22,8,28

C.3,8,12,5,20,15,22,28,19

D.3,12,5,8,28,20,15,22,19

10.若數據元素序列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=00000076H

A.X=0000007FH,y=FFF9H,z=FFFF0076H

A.X=0000007FH,y=FFF7H,z=FFFF0076H

A.X=0000007FH,y=FFF7H,z=00000076H

13.浮點數加減運算過程一般包括對階、尾數運算、規格化、舍入和判溢出等步驟。設浮點

數的階碼和尾數均采用補碼表示，且位數分別為5位和7位（均含2位符號位）。若有兩個

數*=27*29a2,Y=25X33,則用浮點加法計算X+Y的最終結果是

A.001111100010B.001110100010

C.010000010001D.發生溢出

14.某計算機的Cache共有16塊，采用2路組相聯映射方式（即每組2塊）。每個主存塊大

小為32字節，按字節編址。主存129號單元所在主存塊應裝入到的Cache組號是

A.0B.2C.4D.6

15.某計算機主存容量為64KB,其中ROM區為4KB,其余為RAM區，按字節編址。現要用

2KX8位的ROM芯片和4KX4位的RAM芯片來設計該存儲器，則需要上述規格的ROM芯

片數和RAM芯片數分別是

A.1、15B.2、15C.1、30D.2、30

16.某機器字長16位，主存按字節編址，轉移指令采用相對尋址，由兩個字節組成，第一

字節為操作碼字段，第二字節為相對位移量字段。假定取指令時，每取一個字節PC自動加

1?若某轉移指令所在主存地址為2000H,相對位移量字段的內容為06H,則該轉移指令成

功轉以后的目標地址是

A.2006HB.2007HC.2008HD.2009H

17.下列關于RISC的敘述中，錯誤的是

A.RISC普遍采用微程序控制器

B.RISC大多數指令在一個時鐘周期內完成

C.RISC的內部通用寄存器數量相對CISC多

D.RISC的指令數、尋址方式和指令格式種類相對CISC少

18.某計算機的指令流水線由四個功能段組成，指令流經各功能段的時間（忽略各功能段之

間的緩存時間）分別是90ns、80ns、70ns和60ns,則該計算機的CPU時鐘周期至少是

A.90nsB.80nsC.70nsD.60ns

19.相對于微程序控制器，硬布線控制器的特點是

A.指令執行速度慢，指令功能的修改和擴展容易

B.指令執行速度慢，指令功能的修改和擴展難

C.指令執行速度快，指令功能的修改和擴展容易

D.指令執行速度快，指令功能的修改和擴展難

20.假設某系統總線在一個總線周期中并行傳輸4字節信息，一個總線周期占用2個時鐘周

期，總線時鐘頻率為10MHz,則總線帶寬是

A.lOMB/sB.20MB/SC.40MB/SD.80MB/S

21.假設某計算機的存儲系統由Cache和主存組成，某程序執行過程中訪存1000次，其中

訪問Cache缺失（未命中）50次，則Cache的命中率是

A.5%B.9.5%C.50%D.95%

22.下列選項中，能引起外部中斷的事件是

A.鍵盤輸入B.除數為0C.浮點運算下溢D.訪存缺頁

23.單處理機系統中，可并行的是

I進程與進程H處理機與設備川處理機與通道IV設備與設備

A.kIIIIIB.I、II和IVC.I、III和IVD.IKIII和IV

24.下列進程調度算法中，綜合考慮進程等待時間和執行時間的是

A.時間片輪轉調度算法B.短進程優先調度算法

C.先來先服務調度算法D.高響應比優先調度算法

25.某計算機系統中有8臺打印機，有K個進程競爭使用，每個進程

最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是（）

不死鎖需要2K+K8,最多支持3個進程并發。注意問的如果是“不

會發生死鎖的最大值”就選Bo4個以上就死鎖，所以會死鎖的最

小值是4。別看錯了。

A.B.3C.4D.5

26.分區分配內存管理方式的主要保護措施是

A.界地址保護B.程序代碼保護C.數據保護D.棧保護

27.一個分段存儲管理系統中，地址長度為32位，其中段號占8位，

則段長最大

A.2的8次方字節B.2的16次方字節C.2的24次方字節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,12

B.110,68,45,35,12,170,180,195

C.110,170,180,195,12,35,45,68

D.12,35,45,68,110,170,180,195

30.文件系統中，文件訪問控制信息存儲的合理位置是

A.文件控制塊B.文件分配表C.用戶口令表D.系統注冊表

31.設文件F1的當前引用計數值為1,先建立F1的符號鏈接（軟鏈

接）文件F2,再建立F1的硬鏈接文件F3,然后刪除Flo此時，F2

和F3的引用計數值分別是

A.0、1B.l、1C.1、2D.2、1

32.程序員利用系統調用打開I/O設備時，通常使用的設備標識是

A.邏輯設備名B.物理設備名C.主設備號D.從設備號

33.在0SI參考模型中，自下而上第一個提供端到端服務的層次是

A.數據鏈路層B.傳輸層C.會話層D.應用層

34.在無噪聲情況下，若某通信鏈路的帶寬為3kHz,采用4個相位，每個相位具有4種振

幅的QAM調制技術，則該通信鏈路的最大數據傳輸速率是

A.12kbpsB.24kbpsC.48kbpsD.96kbps

35.數據鏈路層采用了后退N幀（GBN）協議，發送方已經發送了編號為0~7的幀。當計時

器超時時，若發送方只收到0、2、3號幀的確認，則發送方需要重發的幀數是

A.2B.3C.4D.5

36.以太網交換機進行轉發決策時使用的PDU地址是

A.目的物理地址B.目的IP地址C.源物理地址D.源IP地址

37.在一個采用CSMA/CD協議的網絡中，傳輸介質是一根完整的電纜，傳輸速率為lGbps,

電纜中的信號傳播速度是200000km/s。若最小數據幀長度減少800比特，則最遠的兩個站

點之間的距離至少需要

A.增加160mB.增加80mC.減少160mD.減少80m

38.主機甲和主機乙間已建立一個TCP連接，主機甲向主機乙發送了兩個連續的TCP段，分

別包含300字節和500字節的有效載荷，第一個段的序列號為200,主機乙正確接收到兩個

段后，發送給主機甲的確認序列號是A.500B.700C.800D.1000

39.一個TCP連接總是以1KB的最大段發送TCP段，發送方有足夠多的數據要發送。當擁

塞窗口為16KB時發生了超時，如果接下來的4個RTT（往返時間）時間內的TCP段的傳輸

都是成功的，那么當第4個RTT時間內發送的所有TCP段都得到肯定應答時，擁塞窗口大

小是

A.7KBB.8KBC.9KBD.16KB

40.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(RI),R0”的功能為(R0)+((R1))-(R1),即

將R0中的數據與R1的內容所指主存單元的數據相加，并將結果送入R1的內容所指主存單

元中保存。

存儲器M

數據通路結構

下表給出了上述指令取值和譯碼階段每個節拍(時鐘周期)的功能和有效控制信號，請按

表中描

述方式用表格列出指令執行階段每個節拍的功能和有效控制信號。

功能和控制信號

時鐘功能有效控制信號

C1MAR+(PC)PCout,MARin

C2MDR-M(MAR)MemR,MDRinE

PC*-(PC)+1PC+1

C3IR*-(MDR)MDRoutJRin

C4指令譯碼無

45.(7分)三個進程Pl、P2、P3互斥使用一個包含N(N>0)個單元的緩沖區。

P1每次用produce()生成一個正整數并用put()送入緩沖區某一空單元中；

P2每次用getodd()從該緩沖區中取出一個奇數并用countodd()統計奇數個

數；P3每次用geteven()從該緩沖區中取出一個偶數并用counteven()統計

偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義

的信號量的含義。要求用偽代碼描述。

46.(8分)請求分頁管理系統中，假設某進程的頁表內容如下表所示。

頁面大小為4KB,一次內存的訪問時間是

頁號頁框號有效位

100ns,一次快表(TLB)的訪問時間是10ns,

(存在位)

處理一次缺頁的平均時間為108ns(已含更新

0101H1

TLB和頁表的時間)，進程的駐留集大小固定

1—0

為2,采用最近最少使用置換算法(LRU)和

局部淘汰策略。假設2254H1

①TLB初始為空；

②地址轉換時先訪問TLB,若TLB未命中，再訪問頁表

(忽略訪問頁表之后的TLB更新時間)；

③有效位為0表示頁面不在內存，產生缺頁中斷，缺頁中斷處理后，返回到產

生缺頁中斷的指令處重新執行。設有虛地址訪問序列

2362H、1565H、25A5H,請問：

(1)依次訪問上述三個虛地址，各需多少時間？給出計算過程。

(2)基于上述訪問序列，虛地址1565H的

物理地址是多少？請說明理由。

47.(9分)某公司網絡拓撲圖如下圖所示，路由器R1通過接口El、E2分別連接局域網1、

局域網2,

通過接口L0連接路由器R2,并通過路由器R2連接域名服務器與互聯網。R1的L0接口的

1P地址是

;R2的L0接口的IP地址是,L1接口的IP地址是,E0

接口的

IP地址是；域名服務器的IP地址是?

2ZE.II&11

墳￡短務R

RI和R2的路由我結構為:

阻的網絡IP地址子網捆烏ITTIIP地址腹口一|

將IP地址空間啟4劃分為兩個子網，分配給局域網1、局域網2,每個局域網分

配的地

址數不少于120個，請給出子網劃分結果。說明理由或給出必要的計算過程。

請給出R1的路由表，使其明確包括到局域網1的路由、局域網2的路由、域名服務器的主

機路由和

互聯網的路由。請采用路由聚合技術，給出R2到局域網1和局域網2的路由。

2009年計算機統考真題參考答案

選擇題

12廠451,8910

BCDBCBI)AB

11121314151617181920

C1)DCI)CAA1)°

2122232425262728

I)Al)1)CX(B

3132B3343536373840

BABCADDA|

12345678910

BCDBCBADAB

11121314151617181920

CDDCDCAADB

21222324252627282930

DADDCACBAA

31323334353637383940

BABBCADDCA

1.為解決計算機與打印機之間速度不匹配的問題,通常設置一個打印數據緩沖區，該緩沖區

的邏輯結構應該是（隊列）

棧的定義:棧是只準在表尾進行插入和刪除的線性表，稱為LI0F0（即后進先出表）。允許

插入和刪除的一端叫棧頂，另一端叫棧底。

隊列的定義：隊列是允許在一端進行插入而在另一端進行刪除的線性表。允許插入的一端

稱為隊尾，允許刪除的一端稱為隊頭。隊列也稱為先進先出表（FIFO）

樹的定義：樹是包含n個結點的有限集合（n>0）

圖的定義：圖（Graph）是由非空的頂點集合和一個描述頂點之間關系一邊（或者弧）的

集合組成。其形式化定義為：G=（V,E）

其中G表一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。

2.設棧S和隊列Q的初始狀態均為空,元素abcdefg依次進入棧S。若每個元素出棧后立即

進入隊列Q,且7個元素出隊的順序是bdcfeag,則棧S的容量？？？（3）

3.給定二叉樹圖，若遍歷后的結點序列為XXX,則其遍歷方式是???

設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。

4.平衡二叉樹定義:若一棵二叉樹中每個結點的左、右子樹的高度至多相差1,則稱此樹為

平衡二叉樹。我們把二叉樹中每個結點的左子樹高度減去右子樹高度定義為該結點的平衡

因子（balancefactor）0因此，平衡樹中每個結點的平衡因子只能是1、0或-1。

5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個

數最多是？？？（111）

二叉樹:二叉樹是一種重要的樹形結構，它是n（n>=0）個結點的有限集，其子樹分為互不

相交的兩個集合，分別稱為左子樹和右子樹，左子樹和右子樹也是如上定義的二叉樹。左

子樹和右子樹的順序不能互換。

滿二叉樹:深度為k結點數為2飛-1的二叉樹。

完全二叉樹:若對滿二叉樹的結點從上到下從左到右進行編號，則深度為k且有n個結點

的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹的編號從1到n一一對應時，

稱為完全二叉樹。

6.將森林轉換為對應的二叉樹,若在二叉樹中,結點u是結點v的父結點的父結點，則在

原來的森林中,u和v可能具有的關系是:父子關系或兄弟關系。

森林轉換為對應的二叉樹:兄弟之間連線，父只與長子連線。（左孩子右兄弟）

7.無向連通圖特性的敘述:所有頂點的度之和為偶數。

頂點的度定義:與定點v相關聯的邊數（每個環計算兩次）。

度為零的頂點稱為孤立頂點，度為奇數的頂點稱為奇點，度為偶數的頂點稱為偶點。

8.一棵m階B樹（1970年,R.Bayer和E.mccreight提出了一種適用于處查找的樹，它是

一種平衡多叉樹）

定義：

⑴樹中每個結點至多有m個孩子；

⑵除根結點和葉子結點外，其它每個結點至少有m/2個孩子；

⑶若根結點不是葉子結點，則至少有2個孩子（除非B樹只有一個結點）；

（4）所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息；

⑸有k個孩子的非終端結點恰好包含有k-1個關鍵字（各節點內關鍵字均升序或降序排

列）.

9.堆（Heap）分為小根堆和大根堆兩種，對于一個小根堆，它是具有如下特性的一棵完全二

叉樹：

（1）若樹根結點存在左孩子，則根結點的值（或某個域的值）小于等于左孩子結點的值（或某

個域的值）；

（2）若樹根結點存在右孩子，則根結點的值（或某個域的值）小于等于右孩子結點的值（或某

個域的值）；

（3）以左、右孩子為根的子樹又各是一個堆。

大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。

由堆的定義可知，若一棵完全二叉樹是堆，則該樹中以每個結點為根的子樹也都是一個

堆。

分別為一個小根堆和一個大根堆。根據堆的定義可知，堆頂結點，即整個完全二叉樹的根

結點，對于小根堆來說具有最小值，對于大根堆來說具有最大值。

堆排序利用了大根堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特征，使得在當前無

序區中選取最大（或最小）關鍵字的記錄變得簡單。

當向一個小根堆插入一個具有最小值的元素時,該元素需要逐層向上調整,直到被調整到堆

項位置為止。

10.數據元素序列11,12,13,7,8,9,23,4,5是第二趟排序后的結果，則該排序算法

只能是插入排序。

氣泡排序基本思想:

設待排序對象序列中的對象個數為no一般地，第i趟起泡排序從1到n-i+1依次比較相鄰

兩個記錄地關鍵字，如果發生逆序，則交換之，其結果是這n-i+1個記錄中，關鍵字最大

的記錄被交換到第n-i+1的位置上，最多作n-1趟。

簡單選擇排序基本思想:

第一趟在R[L.n]中選最小的，與R[l]交換

第二趟在R[2..n]中選最小的，與R[2]交換，依次類推，進行n-l次選擇后，整個文件有

序。

直接插入排序基本思想:

將一個記錄插入到已排序的有序表中，使插入后的表仍然有序。

折半插入排序基本思想:

將一個記錄插入到已排序的有序表中，使插入后的表仍然有序，但插入時利用折半搜索法

尋找元素的插入位置。

歸并排序基本思想:

又一類不同的排序方法，將兩個或兩個以上的有序表合并成一個新的有序表。

快速排序基本思想:

取中任一記錄作為“樞軸”，一趟排序之后樞軸的值均小于“樞軸”左邊的值，樞

軸右邊的值均大于“樞軸”的值。

堆排序基本思想:

1.如何將一個無序序列調整為堆？

2.如何在互換堆頂之后重新調整為堆(關鍵)？

希爾排序(ShellSort)基本思想:

l.n大，劃分成若干子序列，分別直接插入排序。

2.待整個記錄“基本有序”時，對整體直接重排。

11.馮?諾依曼計算機中指令和數據均以二進制形式存放在存儲器中，四區分它們的依據

是指令周期的不同階段。

12.十進制轉換:

十進制轉任意進制的通用方法是：除x取余倒排法(x代表進制數)。

如：將十進制數76轉換成任意進制

1.轉成二進制

76/2...0

=38/2...0

=19/2...1

=9/2...1

=4/2...0

=2/2...0

=1/2...1

76(10)=1001100(2)

2.轉成八進制

76/8...4

=9/8…1

=1/8...1

76(10)=114(8)

3.轉成十六進制

76/16...12

=4/16...4

76（10）=4C（16）

B：二進制數。

Q:八進制數。

D：十進制數。

H：十六進制數。

負數用十六進制和八進制怎么表示?

使用補碼（二進制），而且還要指定字長

比如說一個二字節整型的-2就應該是：

1111111111111110

再轉化其它進制

十六進制：FFFE

八進制：177776

13.浮點數加減運算過程一般包括對階、尾數運算、規格化、舍入和判溢出等步驟。設浮點

數的階碼和尾數均采用補碼表示,且位數分別為5位和7位（均含2位符號位）。若有兩

個數X=2，*29/32,Y=2,5*5/8,則用浮點加法計算X+Y的最終結果是發生溢出

浮點數表示:小數點的位置可以在一定范圍內浮動。

E為階，包括階符和階碼（整數），階碼為數決定了浮點數的表示范圍。

M為位數，包括數符和尾數，表示數的精度和正負。

對階原則：小階對大階。

雙符號位判溢:力口，減后。兩個符號位出現“奧”，表示已經溢出,即結果大于+1.

14.存儲器的分類:

1.按存儲介子分：（D半導體存儲器；（2）磁表面存儲器；（3）光介子存儲器。

2.按存取方式分類：（1）隨機存取存儲器RAM；（2）順序存儲器SAM；（3）直接存取存儲淵

DAMo

3.按計算機功能分類:

（1）主存儲器（主存）

用于存放計算機運行期間的大量程序和數據的存儲器,CPU能直接訪問。由M0S存儲器構成。

（2）高速緩沖存儲器（Cache）

Cache是介于CPU和主存之間高速小容量存儲器，用于存放最活躍的程序塊和數據。由靜態

M0S存儲器構成。

特點：速度快，但容量小，位價格較高。

主存和Cache一起構成計算機的內底儲番（內存），是CPU能直接訪問的存儲器。

（3）輔助存儲器（外存儲器）

存放當前暫不參與運行的程序和數據，需要時再與主存成批交換信息的存儲器。

特點是容量大，可存放大量的程序和數據，但速度慢。

（4）控制存儲器（CM）

在微程序控制的計算機中，用于存放執行指令的微程序的存儲器。

CM一般由ROM構成，屬于控制器的一部分。

4.其它分類:

a.按讀寫功能分類:

(1)只讀存儲器(ROM):工作時只能讀出不能寫入的存儲器。

(2)讀寫存儲器(RAM):既能讀出又能寫入的存儲器。

b.按信息的可保存性分類

(1)永久性存儲器：指斷電后仍能保存信息的存儲器，如磁表面存儲器。

(2)非永久性存儲器:指斷電后信息即消失的存儲器，如半導體讀寫存儲器。

某計算機的Cache共有16塊，采用2路組相連映射方式(即每組2塊)。每個主存塊大小

為32字節，按字節編址。主存129號單元所在主存塊應裝入到Cache組號是(4)

15.主存容量是根據地址線的位數來確定的,在16位PC機中地址總線的寬度是20位,則主

存大小為:2~20byte=lMB,現在的PC機一般都是32位地址總線的,最大直接尋址空間

為:2飛2,即主存最大容量為4GB

某計算機主存容量為KKB,其中ROM區為4KB,其余為RAM區，按字節編址。現要用2K*8

位的ROM芯片和4K*4位的RAM芯片來設計該存儲器，則需要上述規格的ROM芯片數和RAM

芯片數分別是230

16.某計算機字長16位，主存按字節編址，轉換指令采用相對尋址，由兩個字節組成，第

一字節為操作碼字段，第二字節為相對位移量字段。假定取指令時，每取一字節PC自動加

1?若某轉移指令所在主存地址為2000H,相對位移量字段的內容為06H,則該轉移指令成

功轉移后的目標地址是(2008H)

相對昱址：以當前程序計數器pc的內容為基址，加上指令給出的一字節補碼數(偏移量)

形成新的pc值的尋址方式稱為相對尋址。

目的地址=源地址+相對轉移指令字節數+指令中給定的偏移量(rel).

17.RISC(精簡指令系統)的敘述:

(1).選用的是使用頻率很高的一些簡單指令;

(2).指令長度固定，指令格式及尋址方式種類少；

(3).只有取數/存數指令訪問存儲器，其余指令的操作都在寄存器之間進行；

(4).大多數指令可在一個計算機周期內完成。

18.指令周期是取出并執行一條指令的時間。

指令周期常常有若干個CPU周期，CPU周期也稱為機器周期，由于CPU訪問一次內存所花費

的時間較長，因此通常用內存中讀取一個指令字的最短時間來規定CPU周期。這就是說一

條指令取出階段(通常為取指)需要一個CPU周期時間。而一個CPU周期時間又包含若干

個時鐘周期(通常為節拍脈沖或T周期，它是處理操作的最基本的單位)。這些時鐘周期的

總和則規定了一個CPU周期的時間寬度。

某計算機的指令流水線由四個功能段組成，指令流經各功能段的時間(忽略各功能段之間

的緩沖時間)分別是90ns、80ns、70ns、60ns,則計算機的CPU時鐘周期是(90ns)。

19.相對于微程序控制器，硬布線控制器的特點是指令執行速度快，指令功能的修改和擴展

難。

20.假設某系統總線在一個總線周期中并行傳輸4字節信息，一個總線周期占用2個時鐘周

期，總線時鐘頻率為10MHz,則總線帶寬是(20MB/S)

時鐘周期和時鐘頻率互為倒數關系。

lKHz=1000Hz；

lMHz=1000KHz

并行總線帶寬(MB/s)=并行總線時鐘頻率(MHz)*并行總線位寬(bit/8=B)*每時鐘傳

輸幾組數據(cycle)

串行總線帶寬(MB/s)=串行總線時鐘頻率(MHz)*串行總線位寬(bit/8=B)*串行總線

管線*編碼方式*每時鐘傳輸幾組數據(cycle)

1字節(Byte)=8位(bit)

21.假設某計算機的存儲系統由Cache和主存組成，某程序執行過程中訪存1000次，其中

訪問Cache缺失(未命中)50次，則Cache的命中率是(95%)

22.能引起外部中斷的事件是:鍵盤輸入(人的干預)或外請求。(外中斷都是強迫中斷)

23.單處理機系統中,可并行的是(IKIH和IV)

I進程與進程II處理機與設備HI處理機與通道IV設備與設備

24.進程調度算法中，綜合考慮進程等待時間和執法世間是：(高響應比優先調度算法).

FCFS:誰先到就緒隊列,將處理機分給誰；

時間片輪轉調度法：以先來后到的次序+時間片輪轉；

優先級調度:選優先級最高的進程占用處理機(優先級可動態改變)；

短進程優先:取所需的運行時間最短的進程(該算法能使平均等待時間最短).

25.某計算機系統有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該

系統可能會發生死鎖的K的最小值是(4)

26.分區分配內存管理方式的主要保護措施是(界地址保護)

27.一個分段存儲管理系統中,地址長度為32位，其中段號占8位，則最大段長是(2.24).

分頁與分段的區別:

分頁:信息的物理單位大小一樣，由系統固定地址空間是一維的

分段:信息的邏輯單位大小不等，由用戶確定地址空間是二維的

28.文件物理結構中,適合隨機訪問且易于文件擴展的是（索引結構）.

連續結構:將一個文件中邏輯上連續的信息存放到存儲介質的依次相鄰的塊上便形成順序

結構，這類文件叫連續文件，又稱順序文件。

優點：簡單;支持順序存取和隨機存取；順序存取速度快；所需的磁盤尋道次數和尋道時間

最少.

缺點：建立文件前需要能預先確定文件長度，以便分配存儲空間；修改、插入和增生文件

記錄有困難；對直接存儲器作連續分配，會造成少量空閑塊的浪費。

鏈接結構:一個文件的信息存放在若干不連續的物理塊中，各塊之間通過指針連接，前一

個物理塊指向下一個物理塊。

優點：提高了磁盤空間利用率，不存在外部碎片問題；有利于文件插入和刪除；有利于文件

動態擴充.

缺點：存取速度慢，不適于隨機存取；可靠性問題，如指針出錯；更多的尋道次數和尋道

時間；鏈接指針占用一定的空間.

索引結構:一個文件的信息存放在若干不連續物理塊中，系統為每個文件建立一個專用數

據結構一一索引表。表中每一欄目指出文件信息所在的邏輯塊號和與之對應的物理塊號。

索引表的物理地址則由文件說明信息項給出。

優點：保持了鏈接結構的優點，又解決了其缺點；即能順序存取，又能隨機存取；滿足了文

件動態增長、插入刪除的要求；也能充分利用外存空間。

缺點：較多的尋道次數和尋道時間；索引表本身帶來了系統開銷如：內外存空間，存取時

間。

29.SCAN調度（電梯調度）算法:電梯調度算法基于日常生活中的電梯工作模式：電梯保持按

一個方向移動，直到在那個方向上沒有請求為止，然后改變方向。反映在磁盤調度上，總

是沿著移動臂的移動方向選擇距離磁頭當前位置最近的I/O請求作為下一次調度的對象。

如果該方向上已無I/O請求，則改變方向再做選擇。

假設磁頭當前位于第105道，正在向磁道序號增加的方向移動。現在一個磁道訪問請求序

列為35,45,12,68,110,180,170,195,采用SCAN調度（電梯調度）算法得到的磁道

訪問序列是:110,170,180,195,68,45,35,12。

30.文件系統中，文件訪問控制信息存儲的合理位置是（文件控制塊）。

31.硬鏈接:在磁盤上有一份內容一樣的文件產生，但不改變文件的Inode,也就是與原文件

共用Inodeo

軟鏈接:不在磁盤上有一份內容一樣的文件產生，但產生新的Inode。

設文件Fl的當前引用計數值為1,先建立F1的符號鏈接（軟鏈接）文件F2,再建立F1的

硬鏈接文件F3,然后刪除F1。此時，F2和F3的引用計數值分別是（1,1）。

32.程序員利用系統調用打開I/O設備時，通常使用的設備標識是（邏輯設備名）。

33.在0SI參考模型中，自下而上第一個提供端到端服務的層次是（傳輸層）。

自下而上方法的一般從檢查物理層開始。

自下而上分別稱為：物理層、數據鏈路層、網絡層、傳輸層、會話層、表示層和應用層。

傳輸層是兩臺計算機經過網絡進行數據通信時，第一個端到端的層次，具有緩沖作用。

34.1924年奈奎斯特（Nyquist）就推導出在理想低通信道的最高大碼元傳輸速率的公式：

理想低通信道的最高大碼元傳輸速率C=2W.Iog2N（其中W是想低通信道的帶寬,N是

電平強度）

信道帶寬與數據傳輸速率的關系可以奈奎斯特（Nyquist）準則與香農（Shanon）定律描述。

奈奎斯特定理描述了有限帶寬、無噪聲信道的最大數據傳輸速率與信道帶寬的關系。香農

定理則描述了有限帶寬、有隨機熱噪聲信道的最大傳輸速率與信道帶寬、信噪比之間的關

系。

奈奎斯通隹則指出：對于二進制數據信號的最大數據傳輸速率Rmax與通信信道帶寬B（B=f,

單位Hz）的關系可以寫為：Rmax=2*B（bps）

香農定理指出:在有隨機熱噪聲的信道上傳輸數據信號時，數據傳輸速率Rmax與信道帶寬

B、信噪比S/N的關系為：

Rmax=B*log2（H-S/N））［以2為底,1+S/N的對數］

式中,Rmax單位為bps,帶寬B單位為Hz,信噪比S/N通常以dB(分貝)數表示.若S/N=30(dB),

那么信噪比根據公式：S/N(dB)=10*lg(S/N)則S/N=1000。若帶寬B=3000Hz,則

RmaxQ30kbps。

(1)對于帶寬為6MHz的信道，若用4種不同的狀態來表示數據，在不考慮熱噪聲的情況

下，該信道的最大數據傳輸速率是多少？

答：由無熱噪聲的奈奎斯特公式：C=2Hlog2N=2*6M*log24=24Mbps,即該信道的最大數據傳

輸速率是24Mbps

(2)在無噪聲情況下,若某通信鏈路的帶寬為3KHz,采用4個相位，每個相位具有4種振

幅的QAM調制技術，則該通信鏈路的最大數據傳輸速率是(24kbps)

C=2Hlog2N=2*3k*log216=24kbps.

35.后退N幀ARQ就是從出錯處重發已發出過的N個幀。

數據鏈路層采用了后退N幀(GBN)協議，發送方已經發送了編號為0~7的幀。當計時器超

時時，若發送方只收到0、2、3號幀的確認，則發送方需要重發的幀數是(4)。

36.以太網交換機進行轉發決策時使用的PDU地址是(目的物理地址).

ARP協議是"AddressResolutionProtocolw(地址解析協議)的縮寫。在局域網中，網

絡中實際傳輸的是“幀”，幀里面是有目標主機的MAC地址的。在以太網中，一個主機要

和另一個主機進行直接通信，必須要知道目標主機的MAC地址。但這個目標MAC地址是如

何獲得的呢？它就是通過地址解析協議獲得的。所謂“地址解析”就是主機在發送幀前將

目標IP地址轉換成目標MAC地址的過程。ARP協議的基本功能就是通過目標設備的IP地址,

查詢目標設備的MAC地址，以保證通信的順利進行。

37.CSMA/CD是一種分布式介質訪問控制協議，網中的各個站(節點)都能獨立地決定數據

幀的發送與接收。每個站在發送數據幀之前，首先要進行載波監聽，只有介質空閑時，才

允許發送幀。這時，如果兩個以上的站同時監聽到介質空閑并發送幀，則會產生沖突現象,

這使發送的幀都成為無效幀，發送隨即宣告失敗。每個站必須有能力隨時檢測沖突是否發

生，一旦發生沖突，則應停止發送，以免介質帶寬因傳送無效幀而被白白浪費，然后隨機

延時一段時間后，再重新爭用介質，重發送幀。CSMA/CD協議簡單、可靠，其網絡系統(如

Ethernet)被廣泛使用。

在一個采用CSMA/CD協議的網絡中，傳輸介質是一根完整的電纜，傳輸速率為lGbps,電纜

中的信號傳播速度是200000km/s。若最小數據幀長度減少800比特，則最遠的兩個站點之

間的距離至少需要（減少80）?

最短幀長=2札*10~9（b/s）+200000000m/s=10*L（bit）.

38.主機甲和主機乙之間建立一個TCP連接,主機甲向主機乙發送了兩個連續的TCP段,分別

含300字節和500字節的有效載荷,第一個段的序列號為200,主機乙正確接收到兩個段后，

發送給主機甲的確認序列號是（1000）。

例如，序列號等于前一個報文段的序列號與前一個報文段中數據字節的數量之和。例如，

假設源主機發送3個報文段，每個報文段有100字節的數據，且第一個報文段的序列號是

1000,那么接收到第一個報文段后，目的主機返回含確認號1100的報頭。接收到第二個報

文段（其序號為1100）后，目的主機返回確認號1200。接收到第三個報文段后，目的主機

返回確認號1300。

39.確定擁塞窗口的大小的過程：在剛建立連接時，將擁塞窗口的大小初始化為該連接所需

的最大連接數據段的長度值，并發送一個最大長度的數據段（當然必須是接收窗口允許的）。

如果在定時器超時前得到確認，將擁塞窗口的大小增加一個數據段的字節數，并發送兩個

數據段，如果每個數據段在定時器超時前都得到確認，就再在原基礎上增加一倍，即為4

個數據段的大小，如此反復，每次都在前一次的基礎上加倍。當定時器超時或達到發送窗

口設定值，停止擁塞窗口尺寸的增加。這種反復稱為慢速啟動，所有的TCP協議都支持這

種方法。

一個TCP連接總是以1KB的最大段發送TCP段，發送方有足夠多的數據要發送。當擁塞窗

口為16KB時發生了超時，如果接下來的4個RTT（往返時間）時間內的TCP段的傳輸都是

成功的，那么當第4個RTT時間內發送的所有TCP段都得到肯定應答時，擁塞窗口大小是

（9KB）.

40.FTP客戶和服務器間傳遞FTP時，使用的連接是（建立在TCP之上的控制連接）。

綜合應用題

41.該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權圖，如果按照題中的

原則，

從A到C的最短路徑為A-B-C,事實上其最短路徑為A-D-C。

從A到C的最短路徑為ATAC,事實上其最為路假為

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)

{Pl=list->link;

P=list;

i=l；

while(Pl)

{Pl=Pl->link;

i++；

if(i>k)p=p->next;〃如果i>k,則p也往后移

)

if(p==list)return0;〃說明鏈表沒有k個結點

else

printf("%d\nw,p->data);

return1;

43.(1)在中斷方式下，每32位(4B)被中斷一次，故每秒中斷

0.5MB/4B=0.5X10^4=12.5X104次

要注意的是，這里是數據傳輸率，所以1MB=1O6B。因為中斷服務程序包含18條指令，中

斷服務的

其他開銷相當于2條指令的執行時間，且執行每條指令平均需5個時鐘周期，所以，1秒內

用于中斷

的時鐘周期數為

(18+2)X5X12.5X104=12.5X106

(2)在DMA方式下，每秒進行DMA操作

5MB/5000B=5X10^5000=1X103次因為DMA預處理和后處理的總開銷為500個時鐘周期,

所以1秒

鐘之內用于DMA操作的時鐘周期數為

500X1X103=5X105

故在DMA方式下，占整個CPU時間的百分比是

((5X105)/(500X106))X100%=0.1%

44.指令執行階段每個節拍的功能和有效控制信號如下所示

時鐘功能有效控制信號

時鐘功能有效控制信號

C5MAR-(RI)PCout,MARin

C6V1DR-MemRAIDKinE

￡7Ae-(RO)ROout.Ain

C8AC-(MDR)+(A)MDRout.Addr.ACin

C951DR-(AC)ACoutAIDRin

M(MAR)-MDRMDRoutEAIemW

C5MAR-(R1)PCout,MARin

C6MDR-M(MAR)MemR,MDRinE

C7A*-(R0)R0out,Ain

C8AC+(MDR)+(A)MDRout,Addr,ACin

C9MDR+(AC)ACout,MDRin

CIOM(MAR)-MDRMDRoutE,MemW

45.定義信號量SI控制Pl與P2之間的同步；S2控制Pl與P3之間的同步；empty控制

生產者與消費者

之間的同步；mutex控制進程間互斥使用緩沖區。程序如下：

Varsl=0/s2=0/empty=N/mutex=l;

Parbegin

Pl:begin

X=produce();

P(empty);

P(mutex);

Put();

Ifx%2==0

V(s2);

else

V(sl);

V(mutex);

end.

P2:begin

P(sl)；

P(mutex);

Getodd();

Countodd():=countodd()+1；4KB,頁內占12位，即16機制的3位

則2362H的最高位就是頁號

V(mutex);

V(empty);2:10不命中+100頁表+100內存地址

end.

1；10不命中+100頁表+108缺頁+100內

P3:begin

存地址

P(s2)

P(mutex);2：10命中+100內存地址

Geteven();

Counteven():=counteven()+1;1號頁內偏移565H,缺頁，置換0,

V(mutex);101565H

V(empty);

end.

Parend.

46.

(1)根據頁式管理的工作原理，應先考慮頁面大小，以便將頁號和頁內位移分解出來。

頁面大小為4KB,即212,則得到頁內位移占虛地址的低12位，頁號占剩余高位。可

得三個虛地址的頁號P如下(十六進制的一位數字轉換成4位二進制，因此，十六進制

的低三