1. 設 n 是描述問題規模的非負整數，下面程序片段的時間復雜度是x=2;while(xx=2*x;
A.O(log2n)
B.O(n)
C.O(nlog2n)
D.O(n2)
解答：A。程序中，執行頻率最高的語句為“x=2*x”。設該語句執行了t次，則2t+1=n/2，故t=log2(n/2)-1=log2n-2= O(log2n)。
2. 元素a，b，c，d，e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數是
A.3
B.4
C.5
D.6
解答：B。出棧順序必為d_c_b_a_，e的順序不定，在任意一個“_”上都有可能。
3. 已知循環隊列存儲在一維數組A[0...n-1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是
A.0,0
B.0，n-1
C.n-1,0
D.n-1，n-1
解答：B。插入元素時，front不變，rear+1.而插入第一個元素之后，隊尾要指向尾元素，顯然，rear初始應該為n-1,front為0。
4. 若一棵完全二叉樹有768個結點，則該二叉樹中葉結點的個數是
A.257
B.258
C.384
D.385
解答：C。葉結點數為n，則度為2的結點數為n-1,度為1的結點數為0或1，本題中為1(總結點數為偶數)，故而即2n=768。
5. 若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1，則該二叉樹的中序遍歷序列不會是
A.1,2,3,4
B.2,3,4,1
C.3,2,4,1
D.4,3,2,1
解答：C。由前序和后序遍歷序列可知3為根結點，故(1,2)為左子樹，(4)為右子樹，C不可能。或畫圖即可得出結果。
6. 已知一棵有2011個結點的樹，其葉結點個數為116，該樹對應的二叉樹中無右孩子的結點個數是
A.115
B.116
C.1895
D.1896
解答：D。本題可采用特殊情況法解。設題意中的樹是如下圖所示的結構，則對應的二叉樹中僅有前115個葉結點有右孩子。
„„
共116個葉結點
7. 對于下列關鍵字序列，不可能構成某二叉排序樹中一條查找路徑的序列是
A.95,22,91,24,94,71
C.21,89,77,29,36,38
B.92,20,91,34,88,35
D.12,25,71,68,33,34
解答：A。選項A中，當查到91后再向24查找，說明這一條路徑之后查找的數都要比91小，后面的94就錯了。
8. 下列關于圖的敘述中，正確的是
Ⅰ. 回路是簡單路徑
Ⅱ.存儲稀疏圖，用鄰接矩陣比鄰接表更省空間
Ⅲ.若有向圖中存在拓撲序列，則該圖不存在回路
A.僅Ⅱ
B.僅Ⅰ、Ⅱ
C.僅Ⅲ
D.僅Ⅰ、Ⅲ
解答：C。Ⅰ.回路對應于路徑，簡單回路對應于簡單路徑;Ⅱ.剛好相反;Ⅲ.拓撲有序的必要條件。故選C。
9. 為提高散列(Hash)表的查找效率，可以采取的正確措施是
Ⅰ. 增大裝填(載)因子
Ⅱ.設計沖突(碰撞)少的散列函數
Ⅲ.處理沖突(碰撞)時避免產生聚集(堆積)現象
A.僅Ⅰ
B.僅Ⅱ
C.僅Ⅰ、Ⅱ
D.僅Ⅱ、Ⅲ
解答：B。III錯在“避免”二字。
10.為實現快速排序算法，待排序序列宜采用的存儲方式是
A.順序存儲 B.散列存儲 C.鏈式存儲
解答：A。內部排序采用順序存儲結構。D.索引存儲
11.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，將其再調整為大根堆，調整過程中元素之間進行的比較次數是
A.1
B.2
C.4
D.5
解答：B。首先與10比較，交換位置，再與25比較，不交換位置。比較了二次。
12.下列選項中，描述浮點數操作速度指標的是
A.MIPS
B.CPI
C.IPC
D.MFLOPS
解答：D。送分題。
13.float型數據通常用IEEE 754單精度浮點數格式表示。若編譯器將float型變量x分配在一個32位浮點寄存器FR1中，且x=-8.25，則FR1的內容是
A.C104 0000H B.C242 0000H C.C184 0000H D.C1C2 0000H
解答：A。x的二進制表示為-1000.01﹦-1.000 01×211根據IEEE754標準隱藏最高位的“1”，又E-127=3，所以E=130=1000 0010(2)數據存儲為1位數符+8位階碼(含階符)+23位尾數。故FR1內容為1 10000 0010 0000 10000 0000 0000 0000 000即1100 0001 0000 0100 0000 0000 0000 0000，即C104000H
14.下列各類存儲器中，不采用隨機存取方式的是
A.EPROM
B.CDROM
C.DRAM
D.SRAM
解答：B。光盤采用順序存取方式。
15.某計算機存儲器按字節編址，主存地址空間大小為64MB，現用4M×8位的RAM芯片組成32MB的主存儲器，則存儲器地址寄存器MAR的位數至少是
A.22位
B.23位
C.25位
D.26位
解答：D。64MB的主存地址空間，故而MAR的尋址范圍是64M，故而是26位。而實際的主存的空間不能代表MAR的位數。
16.偏移尋址通過將某個寄存器內容與一個形式地址相加而生成有效地址。下列尋址方式中，不屬于偏移尋址方式的是
A.間接尋址
B.基址尋址
C.相對尋址
D.變址尋址
解答：A。間接尋址不需要寄存器，EA=(A)。基址尋址：EA=A+基址寄存器內同;相對尋址：EA﹦A+PC內容;變址尋址：EA﹦A+變址寄存器內容。
17.某機器有一個標志寄存器，其中有進位/借位標志CF、零標志ZF、符號標志SF和溢出標志OF，條件轉移指令bgt(無符號整數比較大于時轉移)的轉移條件是
A. CF +OF =1B. SF +ZF =1
C. CF +ZF =1
D. CF +SF =1
解答：C。無符號整數比較，如A>B，則A-B無進位/借位，也不為0。故而CF和ZF均為0。
18.下列給出的指令系統特點中，有利于實現指令流水線的是
Ⅰ. 指令格式規整且長度一致 Ⅱ.指令和數據按邊界對齊存放
Ⅲ.只有Load/Store指令才能對操作數進行存儲訪問
A.僅Ⅰ、Ⅱ
B.僅Ⅱ、Ⅲ
C.僅Ⅰ、Ⅲ
D.Ⅰ、Ⅱ、Ⅲ
解答：D。指令定長、對齊、僅Load/Store指令訪存，以上三個都是RISC的特征。均能夠有效的簡化流水線的復雜度。
19.假定不采用Cache和指令預取技術，且機器處于“開中斷”狀態，則在下列有關指令執行的敘述中，錯誤..的是
A.每個指令周期中CPU都至少訪問內存一次
B.每個指令周期一定大于或等于一個CPU時鐘周期
C.空操作指令的指令周期中任何寄存器的內容都不會被改變
D.當前程序在每條指令執行結束時都可能被外部中斷打斷
解答：C。會自動加1，A取指令要訪存、B時鐘周期對指令不可分割。
20.在系統總線的數據線上，不.可能傳輸的是
A.指令
C.握手(應答)信號
B.操作數
D.中斷類型號
解答：C。握手(應答)信號在通信總線上傳輸。
21.某計算機有五級中斷L4——L0，中斷屏蔽字為M4M3M2M1M0，Mi=1(0≤i≤4)表示對Li級中斷進行屏蔽。若中斷響應優先級從高到低的順序是L4→L0→L2→L1→L3 ，則L1的中斷處理程序中設置的中斷屏蔽字是
A.11110
B.01101
C.00011
D.01010
解答：D。高等級置0表示可被中斷，比該等級低的置1表示不可被中斷。
22.某計算機處理器主頻為50MHz，采用定時查詢方式控制設備A的I/O，查詢程序運行一次所用的時鐘周期數至少為500。在設備A工作期間，為保證數據不丟失，每秒需對其查詢至少200次，則CPU用于設備A的I/O的時間占整個CPU時間的百分比至少是
A.0.02%
B.0.05%
C.0.20%
D.0.50%
解答：C。每秒200次查詢，每次500個周期，則每秒最少200×500﹦10 0000個周期，10
0000÷50M=0.20%。
23.下列選項中，滿足短任務優先且不會發生饑餓現象的調度算法是
A.先來先服務
C.時間片輪轉
B.高響應比優先
D.非搶占式短任務優先
解答：B。響應比=作業響應時間/作業執行時間 =(作業執行時間+作業等待時間)/作業執行時間。高響應比算法，在等待時間相同情況下，作業執行時間越少，響應比越高，優先執行，滿足短任務優先。隨著等待時間增加，響應比也會變大，執行機會就增大，所以不會產生饑餓現象。先來先服務和時間片輪轉不符合短任務優先，非搶占式短任務優先會產生饑餓現象。
24.下列選項中，在用戶態執行的是
A.命令解釋程序
C.進程調度程序
B.缺頁處理程序
D.時鐘中斷處理程序
解答：A。缺頁處理程序和時鐘中斷都屬于中斷，在核心態執行。進程調度屬于系統調用在核心態執行，命令解釋程序屬于命令接口，它在用戶態執行。
25.在支持多線程的系統中，進程P創建的若干個線程不能共享的是
A.進程P的代碼段
C.進程P的全局變量
B.進程P中打開的文件
D.進程P中某線程的棧指針
解答：D。進程中某線程的棧指針，對其它線程透明，不能與其它線程共享。
26.用戶程序發出磁盤I/O請求后，系統的正確處理流程是
A.用戶程序→系統調用處理程序→中斷處理程序→設備驅動程序
B.用戶程序→系統調用處理程序→設備驅動程序→中斷處理程序
C.用戶程序→設備驅動程序→系統調用處理程序→中斷處理程序
D.用戶程序→設備驅動程序→中斷處理程序→系統調用處理程序
解答：B。輸入/輸出軟件一般從上到下分為四個層次：用戶層、與設備無關軟件層、設備驅動程序以及中斷處理程序。與設備無關軟件層也就是系統調用的處理程序。所以爭取處理流程為B選項。
27.某時刻進程的資源使用情況如下表所示。（圖暫缺）
此時的安全序列是
A.P1,P2,P3,P4
C.P1,P4,P3,P2
B.P1,P3,P2,P4
D.不存在
解答：D。使用銀行家算法得，不存在安全序列。
28.在缺頁處理過程中，操作系統執行的操作可能是
Ⅰ. 修改頁表
A.僅Ⅰ、Ⅱ
Ⅱ.磁盤I/O Ⅲ.分配頁框
B.僅Ⅱ C.僅Ⅲ
D.Ⅰ、Ⅱ和Ⅲ
解答：D。缺頁中斷調入新頁面，肯定要修改頁表項和分配頁框，所以I、III可能發生，同時內存沒有頁面，需要從外存讀入，會發生磁盤I/O。
29.當系統發生抖動(thrashing)時，可用采取的有效措施是
Ⅰ. 撤銷部分進程
Ⅱ.增加磁盤交換區的容量
Ⅲ.提高用戶進程的優先級
A.僅Ⅰ
B.僅Ⅱ
C.僅Ⅲ
D.僅Ⅰ、Ⅱ
解答：A。在具有對換功能的操作系統中，通常把外存分為文件區和對換區。前者用于存放文件，后者用于存放從內存換出的進程。抖動現象是指剛剛被換出的頁很快又要被訪問為此，又要換出其他頁，而該頁又快被訪問，如此頻繁的置換頁面，以致大部分時間都花在頁面置換上。撤銷部分進程可以減少所要用到的頁面數，防止抖動。對換區大小和進程優先級都與抖動無關。
30.在虛擬內存管理中，地址變換機構將邏輯地址變換為物理地址，形成該邏輯地址的階段
是
A.編輯
B.編譯
C.鏈接
D.裝載
解答：B。編譯過程指編譯程序將用戶源代碼編譯成目標模塊。源地址編譯成目標程序
時，會形成邏輯地址。
31.某文件占 10 個磁盤塊，現要把該文件磁盤塊逐個讀入主存緩沖區，并送用戶區進行分析，假設一個緩沖區與一個磁盤塊大小相同，把一個磁盤塊讀入緩沖區的時間為100us，將緩沖區的數據傳送到用戶區的時間是50us，CPU對一塊數據進行分析的時間為50us。在單緩沖區和雙緩沖區結構下，讀入并分析完該文件的時間分別是
A.1500us、1000us
C.1550us、1550us
B.1550us、1100us
D.2000us、2000us
解答：B。單緩沖區下當上一個磁盤塊從緩沖區讀入用戶區完成時下一磁盤塊才能開始讀入，也就是當最后一塊磁盤塊讀入用戶區完畢時所用時間為150×\u65297X0=1500。加上處理最后一個磁盤塊的時間50為1550。雙緩沖區下，不存在等待磁盤塊從緩沖區讀入用戶區的問題，也就是100×\u65297X0+100=1100。
32.有兩個并發執行的進程P1和P2，共享初值為1的變量x。P1對x加1，P2對x減1。加1和減1操作的指令序列分別如下所示。// 加1操作load R1，x // 取x到寄存器R1中 inc R1// 減1操作load R2，xdec R2store x，R1 // 將R1的內容存入x store x，R2兩個操作完成后，x的值
A.可能為-1或3
C.可能為0、1或2
B.只能為1
D.可能為-1、0、1或2
解答：C。將P1中3條語句變為1,2,3，P2中3條語句編為4，5，6。則依次執行1,2,3,4,5得結果1，依次執行1,2,4,5,6,3得結果2，執行4，5，1，2，3，6得結果0。結果-1不可能得出，選C。
33.TCP/IP參考模型的網絡層提供的是
A.無連接不可靠的數據報服務
C.有連接不可靠的虛電路服務
B.無連接可靠的數據報服務
D.有連接可靠的虛電路服務
解答：A。TCP/IP的網絡層向上只提供簡單靈活的、無連接的、盡最大努力交付的數據報服務。此外考察IP首部，如果是面向連接的，則應有用于建立連接的字段，但是沒有;如果提供可靠的服務，則至少應有序號和校驗和兩個字段，但是IP分組頭中也沒有(IP首部中只是首部校驗和)。因此網絡層提供的無連接不可靠的數據服務。有連接可靠的服務由傳輸層的TCP提供。
34.若某通信鏈路的數據傳輸速率為2400bps，采用4相位調制，則該鏈路的波特率是
A.600波特
B.1200波特
C.4800波特
D.9600波特
解答：B。有 4 種相位，則一個碼元需要由 log24=2 個 bit 表示，則波特率=比特率/2=1200波特。
35.數據鏈路層采用選擇重傳協議(SR)傳輸數據，發送方已發送了0——3號數據幀，現已收到1號幀的確認，而0、2號幀依次超時，則此時需要重傳的幀數是
A.1
B.2
C.3
D.4
解答：B。選擇重傳協議中，接收方逐個地確認正確接收的分組，不管接收到的分組是否有序，只要正確接收就發送選擇ACK分組進行確認。因此選擇重傳協議中的ACK分組不再具有累積確認的作用。這點要特別注意與GBN協議的區別。此題中只收到1號幀的確認，0、2號幀超時，由于對于1號幀的確認不具累積確認的作用，因此發送方認為接收方沒有收到0、2號幀，于是重傳這兩幀。
36.下列選項中，對正確接收到的數據幀進行確認的MAC協議是
A.CSMA
B.CDMA
C.CSMA/CD
D.CSMA/CA
解答：D。可以用排除法。首先CDMA即碼分多址，是物理層的東西;CSMA/CD即帶沖突檢測的載波監聽多路訪問，這個應該比較熟悉，接收方并不需要確認;CSMA，既然CSMA/CD是其超集，CSMA/CD沒有的東西，CSMA自然也沒有。于是排除法選D。CSMA/CA是無線局域網標準802.11中的協議。CSMA/CA利用ACK信號來避免沖突的發生，也就是說，只有當客戶端收到網絡上返回的ACK信號后才確認送出的數據已經正確到達目的地址。
37.某網絡拓撲如下圖所示，路由器R1只有到達子網192.168.1.0/24的路由。為使R1可以將IP分組正確地路由到圖中所有子網，則在R1中需要增加的一條路由(目的網絡，子網掩碼，下一跳)是
A.192.168.2.0
B.192.168.2.0
C.192.168.2.0
D.192.168.2.0
255.255.255.128
255.255.255.0
255.255.255.128
255.255.255.0
192.168.1.1
192.168.1.1
192.168.1.2
192.168.1.2
解答：D。此題主要考察路由聚合。要使R1能夠正確將分組路由到所有子網，則R1中需要有到192.168.2.0/25和192.168.2.128/25的路由。觀察發現網絡192.168.2.0/25和192.168.2.128/25的網絡號的前24位都相同，于是可以聚合成超網192.168.2.0/24。從圖中可以看出下一跳地址應該是192.168.1.2。
38.在子網192.168.4.0/30中，能接收目的地址為192.168.4.3的IP分組的最大主機數是
A.0
B.1
C.2
D.4
解答：C。首先分析192.168.4.0/30這個網絡。主機號占兩位，地址范圍192.168.4.0/30——192.168.4.3/30，即可以容納(4-2=2)個主機。主機位為全1時，即192.168.4.3，是廣播地址，因此網內所有主機都能收到，因此選C。
39.主機甲向主機乙發送一個(SYN=1，seq=11220)的TCP段，期望與主機乙建立TCP連接，若主機乙接受該連接請求，則主機乙向主機甲發送的正確的TCP段可能是
A.(SYN=0，ACK=0，seq=11221，ack=11221)
B.(SYN=1，ACK=1，seq=11220，ack=11220)
C.(SYN=1，ACK=1，seq=11221，ack=11221)
D.(SYN=0，ACK=0，seq=11220，ack=11220)
解答：C。主機乙收到連接請求報文后，如同意連接，則向甲發送確認。在確認報文段中應把SYN位和ACK位都置1，確認號是甲發送的TCP段的初始序號seq=11220加1，即為ack=11221，同時也要選擇并消耗一個初始序號seq，seq值由主機乙的TCP進程確定，本題取seq=11221與確認號、甲請求報文段的序號沒有任何關系。
40.主機甲與主機乙之間已建立一個TCP連接，主機甲向主機乙發送了3個連續的TCP段，分別包含300字節、400字節和500字節的有效載荷，第3個段的序號為900。若主機乙僅正確接收到第1和第3個段，則主機乙發送給主機甲的確認序號是
A.300
B.500
C.1200
D.1400
解答：B。TCP段首部中的序號字段是指本報文段所發送的數據的第一個字節的序號。第三個段的序號為900，則第二個段的序號為900-400=500。而確認號是期待收到對方下一個報文段的第一個字節的序號。現在主機乙期待收到第二個段，故甲的確認號是500。
二、綜合應用題：41——47小題，共70分。請將答案寫在答題紙指定位置上。
41.(8 分)已知有 6 個頂點(頂點編號為 0——5)的有向帶權圖 G，其鄰接矩陣 A 為上三角矩陣，按行為主序(行優先)保存在如下的一維數組中。4 6 ∞ ∞ ∞ 5 ∞ ∞ ∞ 4 3 ∞ ∞ 3 3
要求：
(1)寫出圖 G 的鄰接矩陣 A。
(2)畫出有向帶權圖 G。
(3)求圖 G 的關鍵路徑，并計算該關鍵路徑的長度。
解答：
(1)圖G的鄰接矩陣 A 如下所示。（圖暫缺）
(2)有向帶權圖 G 如下圖所示。（圖暫缺）
(3)關鍵路徑為 0à1à2à3à5(如下圖所示粗線表示)，長度為 4+5+4+3=16。
42.(15分)一個長度為 L(L≥1)的升序序列S，處在第 éL / 2ù個位置的數稱為 S 的中位數。例如，若序列 S1=(11,13,15,17,19)，則 S1 的中位數是 15，兩個序列的中位數是含它們所有元素的升序序列的中位數。例如，若 S2=(2,4,6,8,20)，則 S1 和 S2 的中位數是 11。現在有兩個等長升序序列 A 和 B，試設計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列 A 和 B 的中位數。要求：
(1)給出算法的基本設計思想。
(2)根據設計思想，采用 C 或 C++或 JAVA 語言描述算法，關鍵之處給出注釋。
(3)說明你所設計算法的時間復雜度和空間復雜度。
解答：
(1)算法的基本設計思想如下。
分別求出序列 A 和 B 的中位數，設為 a 和 b，求序列 A 和 B 的中位數過程如下：
1)若 a=b，則 a 或 b 即為所求中位數，算法結束。
2)若 a
度相等;
3)若 a>b，則舍棄序列 A 中較大的一半，同時舍棄序列 B 中較小的一半，要求舍棄的在保留的兩個升序序列中，重復過程 1)、2)、3)，直到兩個序列中只含一個元素時為止，較小者即為所求的中位數。
(2)（暫缺）
(3)算法的時間復雜度為 O(log2n)，空間復雜度為 O(1)。
43.(11 分)假定在一個 8 位字長的計算機中運行如下類 C 程序段：
unsigned int x = 134;
unsigned int y = 246;
int m = x;
int n = y;
unsigned int z1 = x-y;
unsigned int z2 = x+y;
int k1 = m-n;
int k2 = m+n;
若編譯器編譯時將 8 個 8 位寄存器 R1——R8 分別分配給變量 x、y、m、n、z1、z2、k1和 k2。請回答下列問題。(提示：帶符號整數用補碼表示)
(1)執行上述程序段后，寄存器 R1、R5 和 R6 的內容分別是什么?(用十六進制表示)
(2)執行上述程序段后，變量 m 和 k1 的值分別是多少?(用十進制表示)
(3)上述程序段涉及帶符號整數加/減、無符號整數加/減運算，這四種運算能否利用
同一個加法器輔助電路實現?簡述理由。
(4)計算機內部如何判斷帶符號整數加/減運算的結果是否發生溢出?上述程序段中，哪些帶符號整數運算語句的執行結果會發生溢出?
解答：
(1) R1=134=86H, R5=90H, R6=7CH;
134=1000 0110B=86H ; x-y=1000 0110B-1111 0110B=1001 0000B=90H ; x+y=1000
0110B+1111 0110B=0111 1100B(溢出)
(2)m=-122,k1=-112
m=1000 0110B，做高位為符號位，則 m 的原碼為 1111 1010B=-122;n=1111 0110Bn 的原碼為 1000 1001=-10;k1=m-n=-112。
(3)無符號數和有符號數都是以補碼的形式存儲，加減運算沒有區別(不考慮溢出情況時)，只是輸出的時候若是有符號數的最高位是符號位。減法運算求[-x]補的時候，是連同符號位一起按位取反末位加 1，但是如果有溢出情況，這兩者是有區別的，所以可以利用同一個加法器實現，但是溢出判斷電路不同。
(4)判斷方法是如果最高位進位和符號位的進位不同，則為溢出;“int k2=m+n;”會溢出;三種方法可以判斷溢出，雙符號位、最高位進位、符號相同操作數的運算后與原操作數的符號不同則溢出
44.(12分)某計算機存儲器按字節編址，虛擬(邏輯)地址空間大小為16MB，主存(物理)地址空間大小為 1MB，頁面大小為 4KB;Cache 采用直接映射方式，共 8 行;主存與 Cache 之間交換的塊大小為 32B。系統運行到某一時刻時，頁表的部分內容和 Cache的部分內容分別如題 44-a 圖、題 44-b 圖所示，圖中頁框號及標記字段的內容為十六進制形式。
題 44-a 圖 頁表的部分內容
請回答下列問題。
題 44-b 圖 Cache 的部分內容
(1)虛擬地址共有幾位，哪幾位表示虛頁號?物理地址共有幾位，哪幾位表示頁框號(物理頁號)?
(2)使用物理地址訪問 Cache 時，物理地址應劃分成哪幾個字段?要求說明每個字段的位數及在物理地址中的位置。
(3)虛擬地址 001C60H 所在的頁面是否在主存中?若在主存中，則該虛擬地址對應的物理地址是什么?訪問該地址時是否 Cache 命中?要求說明理由。
(4)假定為該機配置一個 4 路組相聯的 TLB 共可存放 8 個頁表項，若其當前內容(十六進制)如題 44-c 圖所示，則此時虛擬地址 024BACH 所在的頁面是否存在主存中?要求說明理由.
解答：
題 44-c 圖 TLB 的部分內容
(1)24 位、前 12 位;20 位、前 8 位。16M=224 故虛擬地址 24 位，4K=212，故頁內地址 12 位，所以虛頁號為前 12 位;1M=220故物理地址 20 位，20-12=8，故前 8 位為頁框號。
(2)
主存字塊標記(12bit)、cache 字塊標記(3bit)、字塊內地址(5bit)物理地址 20 位，其中，塊大小為 32B=25B 故塊內地址 5 位;cache 共 8 行，8=23，故字塊標記為 3 位;20-5-2=12，故主存字塊標記為12位。
(3) 在主存中，04C60H, 不命中，沒有 04C 的標記字段001C60H 中虛頁號為 001H=1，查頁表知其有效位為 1，在內存中;該物理地址對應的也表項中，頁框號為 04H 故物理地址為 04C60H;物理地址 04C60H 在直接映射方式下，對應的行號為 4，有效位為 1 但是標記位為 064H≠04CH 故不命中。
(4)在，012 的那個標記是對的。
思路： 標記11位組地址 1 位頁內地址 12 位，前 12 位為 0000 0010 0100，組地址位為0，第0組中存在標記為 012 的頁，其頁框號為 1F，故 024BACH 所在的頁面存在主存中。
45.(8 分)某銀行提供 1 個服務窗口和 10 個供顧客等待的座位。顧客到達銀行時，若有空座位，則到取號機上領取一個號，等待叫號。取號機每次僅允許一位顧客使用。當營業員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營業員的活動過程描述如下：7分)某文件系統為一級目錄結構，文件的數據一次性寫入磁盤，已寫入的文件不可修改，但可多次創建新文件。請回答如下問題。
(1)在連續、鏈式、索引三種文件的數據塊組織方式中，哪種更合適?要求說明理由。為定位文件數據塊，需要 FCB 中設計哪些相關描述字段?
(2)為快速找到文件，對于 FCB，是集中存儲好，還是與對應的文件數據塊連續存儲好?要求說明理由。
解答：
(1) 連續更合適,因為一次寫入不存在插入問題,連續的數據塊組織方式完全可以滿足一次性寫入磁盤。同時連續文件組織方式減少了其他不必要的空間開銷，而連續的組織方式順序查找讀取速度是最快的。
(2)FCB集中存儲好。目錄是存在磁盤上的，所以檢索目錄的時候需要訪問磁盤，速度很慢;集中存儲是將文件控制塊的一部分數據分解出去，存在另一個數據結構中，而在目錄中僅留下文件的基本信息和指向該數據結構的指針，這樣一來就有效地縮短減少了目錄的體積，減少了目錄在磁盤中的塊數，于是檢索目錄時讀取磁盤的次數也減少，于是就加快了檢索目錄的次數。
題 47-a 圖是網絡拓撲，題 47-b 圖是該主機進行 Web 請求的 1 個以太網數據幀前 80 個
0000 00 21 27 21 51 ee 00 15 c5 c1 5e 28 08 00 45 00 .!|!Q... ..^(..E.
0010 01 ef 11 3b 40 00 80 06 ba 9d 0a 02 80 64 40 aa ...:@... .....d@.
0020 62 20 04 ff 00 50 e0 e2 00 fa 7b f9 f8 05 50 18 b ...P.. ..{...P.
0030 fa f0 1a c4 00 00 47 45 54 20 2f 72 66 63 2e 68 ......GE T /rfc.h
0040 74 6d 6c 20 48 54 54 50 2f 31 2e 31 0d 0a 41 63 tml HTTP /1.1..Ac
題 47-b 圖 以太網數據幀(前 80 字節)請參考圖中的數據回答以下問題。
(1)Web 服務器的 IP 地址是什么?該主機的默認網關的 MAC 地址是什么?
(2)該主機在構造題 47-b 圖的數據幀時，使用什么協議確定目的MAC地址?封裝該 協議請求報文的以太網幀的目的 MAC 地址是什么?
(3)假設 HTTP/1.1 協議以持續的非流水線方式工作，一次請求-響應時間為 RTT，rfc.html 頁面引用了 5 個 JPEG 小圖像，則從發出題 47-b 圖中的 Web 請求開始到瀏覽器收到全部內容為止，需要多少個 RTT?
(4)該幀所封裝的 IP 分組經過路由器 R 轉發時，需修改 IP 分組頭中的哪些字段?注：以太網數據幀結構和 IP 分組頭結構分別如題47-c 圖、題47-d 圖所示。
6B 6B 2B 46-1500B 4B
目的 MAC 地址
源 MAC 地址 類型 數 據
題 47-c 圖 以太網幀結構
CRC
解答：
(1)（暫缺）
(2)ARP 協議解決 IP 地址到 MAC 地址的映射問題。主機的 ARP 進程在本以太網以廣播的形式發送 ARP 請求分組，在以太 網上廣播 時，以太網幀的目的地址為全 1，即 FF-FF-FF-FF-FF-FF。
(3)HTTP/1.1 協議以持續的非流水線方式工作時，服務器在發送響應后仍然在一段時間內保持這段連接，客戶機在收到前一個響應后才能發送下一個請求。第一個 RTT 用于請求 web頁面，客戶機收到第一個請求的響應后(還有五個請求未發送)，每訪問一次對象就用去一個RTT。故共 1+5=6 個 RTT 后瀏覽器收到全部內容。
(4)源 IP 地址 0a 02 80 64 改為 65 0c 7b 0f生存時間(TTL)減 1校驗和字段重新計算
私有地址和 Internet 上的主機通信時，須有 NAT 路由器進行網絡地址轉換，把 IP 數據報的源 IP 地址(本題為私有地址 10.2.128.100)轉換為 NAT 路由器的一個全球 IP 地址(本題為 101.12.123.15)。因此，源 IP 地址字段 0a 02 80 64 變為 65 0c 7b 0f。IP 數據報每經過一個路由器，生存時間 TTL 值就減 1，并重新計算首部校驗和。若 IP 分組的長度超過輸出鏈路的 MTU，則總長度字段、標志字段、片偏移字段也要發生變化。注意，圖 47-b 中每行前 4bit 是數據幀的字節計數，不屬于以太網數據幀的內容。
