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