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