為你2011年考研計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考試真題及答案詳解

1、2011 年考研計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合及詳解一、單項(xiàng)選擇題：140 小題，每小題 2 分，共 80 分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。請(qǐng)?jiān)诖痤}卡上將所選項(xiàng)的字母涂黑。1設(shè) n 是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是x = 2;while ( x < n/2 ) x = 2*x;DO(n2)AO(log2n)BO(n)CO(n log2n)2元素a, b, c, d, e 依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d 開頭的序列個(gè)數(shù)是A33已知循環(huán)隊(duì)列B4C5D6在一維數(shù)組A0.n-1

2、中，且隊(duì)列非空時(shí) front 和rear 分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第 1 個(gè)進(jìn)入隊(duì)列的元素始時(shí)front 和rear 的值分別是在A0處，則初A0, 0B0, n-1Cn-1, 0Dn-1, n-14若一棵完全二叉樹有 768 個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是A257B258C384D3855若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為 1, 2, 3, 4 和 4, 3, 2, 1，則該二叉樹的中序遍歷序列不會(huì)是A1, 2, 3, 4B2, 3, 4, 1C3, 2, 4, 1D4, 3, 2, 16已知一棵有 2011 個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)為 116，該

3、樹對(duì)應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個(gè)數(shù)是A115B116C1895D18967. 對(duì)于下列關(guān)鍵字序列，不可能A95, 22, 91, 24, 94, 71C21, 89, 77, 29, 36, 388. 下列關(guān)于圖的敘述中，正確的是I. 回路是簡(jiǎn)單路徑某二叉排序樹中一條查找路徑的序列是B92, 20, 91, 34, 88, 35D12, 25, 71, 68, 33, 34II稀疏圖，用鄰接矩陣比鄰接表更省空間III若有向圖中A僅II拓?fù)湫蛄?，則該圖不回路B僅I、IIC僅IIID僅I、III9. 為提高散列（Hash）表的查找效率，可以采取的正確措施是I. 增大裝填（載）因子II. 設(shè)計(jì)III

4、. 處理（碰撞）少的散列函數(shù)（碰撞）時(shí)避免產(chǎn)生聚集（堆積）現(xiàn)象您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心A僅IB僅IIC僅I、IID僅II、III10為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的方式是A順序B散列C鏈?zhǔn)紻索引新元素 18，將其再調(diào)整為大根堆，11已知序列 25, 13, 10, 12, 9 是大根堆，在序列尾部調(diào)整過程中元A1間進(jìn)行的比較次數(shù)是B2C4D512下列選項(xiàng)中，描述浮點(diǎn)數(shù)操作速度指標(biāo)的是AMIPSBCPICIPCDMFLOPS13float 型數(shù)據(jù)通常用IEEE 754 單精度浮點(diǎn)數(shù)格式表示。若編譯器將float 型變量 x 分配在一個(gè) 32 位浮點(diǎn)寄存器FR1 中，且

5、 x = -8.25，則 FR1 的內(nèi)容是AC104 0000HBC242 0000HCC184 0000HDC1C2 0000H14下列各類AEPROM15某計(jì)算機(jī)器中，不采用隨機(jī)存取方式的是BCDROMCDRAMDSRAM器按字節(jié)編址，主存地址空間大小為 64 MB，現(xiàn)用 4M × 8 位的RAM組成 32 MB 的主A22 位器，則B23 位器地址寄存器MAR 的位數(shù)至少是C25 位D26 位16偏移尋址通過將某個(gè)寄存器內(nèi)容與一個(gè)形式地址相加而生成有效地址。下列尋址不屬于偏移尋址方式的是，A間接尋址B基址尋址C相對(duì)尋址D變址尋址17某機(jī)器有一個(gè)標(biāo)志寄存器，其中有進(jìn)位/借位標(biāo)志

6、CF、零標(biāo)志 ZF、符號(hào)標(biāo)志 SF 和溢出標(biāo)志OF，條件轉(zhuǎn)移指令bgt（無符號(hào)整數(shù)比較大轉(zhuǎn)移）的轉(zhuǎn)移條件是ACF+OF1B SF+ZF 1C CF+ZF 1D CF+SF 118下列給出的指令系統(tǒng)特點(diǎn)中，有利于實(shí)現(xiàn)指令流水線的是I 指令格式規(guī)整且長(zhǎng)度一致II指令和數(shù)據(jù)按邊界對(duì)齊存放III只有Load/Store 指令才能對(duì)操作數(shù)進(jìn)行A僅I、II不采用B僅II、IIIC僅I、IIIDI、II、III19Cache 和指令預(yù)取技術(shù)，且機(jī)器處于“開中斷”狀態(tài)，則在下列有關(guān)指令執(zhí)行的敘述中，錯(cuò)誤的是A每個(gè)指令周期中CPU 都至少內(nèi)存一次B每個(gè)指令周期一定大于或等于一個(gè)CPU 時(shí)鐘周期C空操作指令的指令

7、周期中任何寄存器的內(nèi)容都被改變D當(dāng)前程序在每條指令執(zhí)行結(jié)束時(shí)都可能被外部中斷打斷20在系統(tǒng)總線的數(shù)據(jù)線上，不可能傳輸?shù)氖茿指令C握手（應(yīng)答）信號(hào)21某計(jì)算機(jī)有五級(jí)中斷 L4 B操作數(shù) D中斷類型號(hào)字為 M4M3M2M1M0，Mi=1（0i4）表示對(duì) LiL0，中斷級(jí)中斷進(jìn)行。若中斷響應(yīng)優(yōu)先級(jí)從高到低的順序是 L0L1L2L3L4，且要求中您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心斷處理優(yōu)先級(jí)從高到低的順序?yàn)?L4L0L2L1L3，則 L1 的中斷處理設(shè)置的中斷字是A11110B01101C00011D01010A 的 I/O，22某計(jì)算機(jī)處理器主頻為 50 MHz，采用定時(shí)一次所用的時(shí)鐘周

8、期數(shù)至少為 500。在方式程序運(yùn)行A 工作期間，為保證數(shù)據(jù)不丟失，每秒需對(duì)其至少 200 次，則CPU 用于A 的I/O 的時(shí)間占整個(gè)CPU 時(shí)間的百分比至少是A0.02%B0.05%C0.20%D0.50%23下列選項(xiàng)中，滿足短任務(wù)優(yōu)先且不會(huì)發(fā)生饑餓現(xiàn)象的調(diào)度算法是A先來先服務(wù)C時(shí)間片輪轉(zhuǎn)24下列選項(xiàng)中，在用戶態(tài)執(zhí)行的是A命令解釋程序C進(jìn)程調(diào)度程序B高響應(yīng)比優(yōu)先D非搶占式短任務(wù)優(yōu)先B缺頁處理程序D時(shí)鐘中斷處理程序25在支持多線程的系統(tǒng)中，進(jìn)程P 創(chuàng)建的若干個(gè)線程不能共享的是A進(jìn)程P 的代碼段B進(jìn)程P 中打開的文件C進(jìn)程P 的全局變量D進(jìn)程P 中某線程的棧指針26用戶程序發(fā)出磁盤I/O 請(qǐng)求后

9、，系統(tǒng)的正確處理流程是A. 用戶程序系統(tǒng)調(diào)用處理B. 用戶程序系統(tǒng)調(diào)用處理程序斷處理程序驅(qū)動(dòng)驅(qū)動(dòng)程序斷處理程序斷處理程序C用戶程序D用戶程序驅(qū)動(dòng)程序系統(tǒng)調(diào)用處理驅(qū)動(dòng)斷處理程序系統(tǒng)調(diào)用處理程序27某時(shí)刻進(jìn)程的資源使用情況如下表所示。此時(shí)的安全序列是AP1, P2, P3, P4 CP1, P4, P3, P2BP1, P3, P2, P4D不28在缺頁處理過程中，操作系統(tǒng)執(zhí)行的操作可能是I修改頁表II磁盤I/OIII分配頁框您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心進(jìn)程已分配資源尚需資源可用資源R1R2R3R1R2R3R1R2R3P1200001021P2120132P3011131P400

10、1200A僅I、IIB僅IIC僅IIIDI、II 和III29I II發(fā)生抖動(dòng)（thrashing）時(shí)，可以采取的有效措施是撤銷部分進(jìn)程增加磁盤交換區(qū)的容量III提高用戶進(jìn)程的優(yōu)先級(jí)A僅IB僅IIC僅IIID僅I、II30在虛擬內(nèi)存管理中，地址變換機(jī)構(gòu)將邏輯地址變換為物理地址，形成該邏輯地址的階段是A編輯B編譯C鏈接D裝載31. 某文件占 10 個(gè)磁盤塊，現(xiàn)要把該文件磁盤塊逐個(gè)讀入主存緩沖區(qū)，并送用戶區(qū)進(jìn)行分析。假設(shè)一個(gè)緩沖區(qū)與一個(gè)磁盤塊大小相同，把一個(gè)磁盤塊讀入緩沖區(qū)的時(shí)間為 100 s， 將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)的時(shí)間是50 s，CPU 對(duì)一塊數(shù)據(jù)進(jìn)行分析的時(shí)間為50 s。在單緩沖區(qū)和雙

11、緩沖區(qū)結(jié)構(gòu)下，讀入并分析完該文件的時(shí)間分別是A1500 s、1000 sB1550 s、1100 s C1550 s、1550 s D2000 s、2000 s32. 有兩個(gè)并發(fā)執(zhí)行的進(jìn)程P1 和P2，共享初值為 1 的變量 x。P1 對(duì) x 加 1，P2 對(duì) x 減 1。加 1 和減 1 操作的指令序列分別如下所示。/ 加 1 操作load R1, x/ 減 1 操作load R2, x decR2store x, R2取x 到寄存器R1 中/incR1將R1 的內(nèi)容存入xstore x, R1兩個(gè)操作完成后，x 的值A(chǔ)可能為-1 或 3 C可能為 0、1 或 2/B只能為 1D可能為-1、

12、0、1 或 233TCP/IP 參考模型的網(wǎng)絡(luò)層提供的是A無連接不可靠的數(shù)據(jù)報(bào)服務(wù)C有連接不可靠的虛電路服務(wù)B無連接可靠的數(shù)據(jù)報(bào)服務(wù)D有連接可靠的虛電路服務(wù)34若某通信鏈路的數(shù)據(jù)傳輸速率為 2400 bps，采用 4 相位調(diào)制，則該鏈路的率是A600B1200C4800D960035數(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ù)是A1B2C3D436下列選項(xiàng)中，對(duì)正確接收到的數(shù)據(jù)幀進(jìn)行確認(rèn)的MAC 協(xié)議是ACSMABCDMACCSMA/CDDCSMA/CA37某網(wǎng)絡(luò)拓?fù)淙缦聢D所示，路由器R1

13、 只有到達(dá)子網(wǎng) /24 的路由。為使R1 可以您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心將IP 分組正確地路由到圖中所有子網(wǎng)，則在 R1 中需要增加的一條路由（目的網(wǎng)絡(luò)，子網(wǎng)掩碼，下一跳）是R1119922.116688.11.00/2244R2119922.1.166.12288/2/255119922.116688.22.00/225530A， B， C，D，255.255.

14、255.128，，28，，38在子網(wǎng) /30 中，能接收目的地址為 的IP 分組的最大主機(jī)數(shù)是A0B1C2D439主機(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(S

15、YN = 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)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)是A300B500C1200D1400二、綜合應(yīng)用題：4147 小題，共

16、70 分。請(qǐng)將寫在答題紙指定位置上。41（8 分）已知有 6 個(gè)頂點(diǎn)（頂點(diǎn)編號(hào)為 0 5）的有向帶G，其鄰接矩陣A 為上三角矩陣，按行為主序（行優(yōu)先）保如下的一維數(shù)組中。要求：（1）寫出圖G 的鄰接矩陣A。（2）畫出有向帶G。（3）求圖G 的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長(zhǎng)度。您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心42（15 分）一個(gè)長(zhǎng)度為 L（L1）的升序序列 S，處在第 éL/2ù 個(gè)位置的數(shù)稱為S 的中位數(shù)。例如，若序列S1=(11, 13, 15, 17, 19)，則S1 的中位數(shù)是 15。兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=(2

17、, 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ù)雜度。43（11 分）unsigned int unsigned int int m = x;int n = y;unsigned int unsigned int在一個(gè) 8 位字長(zhǎng)的計(jì)算機(jī)中運(yùn)行如下類C 程序段：x = 134;y = 246;z1 = x

18、y;z2 = x+y;intk1 = mn;intk2 = 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)

19、算語句的執(zhí)行結(jié)果會(huì)發(fā)生溢出？44（12 分）某計(jì)算機(jī)器按字節(jié)編址，虛擬（邏輯）地址空間大小為 16 MB，主存（物理）地址空間大小為 1 MB，頁面大小為 4 KB；Cache 采用直接方式，共 8 行；主存與Cache 之間交換的塊大小為 32 B。系統(tǒng)運(yùn)行到某一時(shí)刻時(shí)，頁表的部分內(nèi)容和Cache的部分內(nèi)容分別如題 44-a 圖、題 44-b 圖所示，圖中頁框號(hào)及標(biāo)記字段的內(nèi)容為十六進(jìn)制形式。虛頁號(hào)有效位頁框號(hào)行號(hào)有效位標(biāo)記00112233445566您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心10200-101D11051064114D0-1061041151020-12B0題 44-a

20、 圖 頁表的部分內(nèi)容請(qǐng)回答下列問題。題 44-b 圖 Cache 的部分內(nèi)容（1）虛擬地址共有幾位，哪幾位表示虛頁號(hào)？物理地址共有幾位，哪幾位表示頁框號(hào)（物理頁號(hào)）？（2）使用物理地址Cache 時(shí)，物理地址應(yīng)劃分成哪幾個(gè)字段？要求說明每個(gè)字段的位數(shù)及在物理地址中的位置。（3）虛擬地址 001C60H 所在的頁面是否在主存中？若在主存中，則該虛擬地址對(duì)應(yīng)的物理地址是什么？該地址時(shí)是否Cache 命中？要求說明理由。相聯(lián)的 TLB，該 TLB 共可存放 8 個(gè)頁表項(xiàng)，若其當(dāng)前（4）為該機(jī)配置一個(gè) 4內(nèi)容（十六進(jìn)制）如題 44-c 圖所示，則此時(shí)虛擬地址 024BACH 所在的頁面是否在主存中？要

21、求說明理由。組號(hào) 有效位 標(biāo)記 頁框號(hào) 有效位 標(biāo)記 頁框號(hào) 有效位 標(biāo)記 頁框號(hào) 有效位 標(biāo)記 頁框號(hào)01題 44-c 圖 TLB 的部分內(nèi)容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)過程描述如下：cobeginprocess 顧客i從取號(hào)機(jī)獲得一個(gè)號(hào)碼； 等待叫號(hào)；獲得服務(wù)；process 營(yíng)業(yè)員while (TRUE)叫號(hào)；為顧務(wù)； coend請(qǐng)?zhí)砑颖匾男盘?hào)量和P、V（或wait()、signal()）

22、操作，實(shí)現(xiàn)上述過程中的互斥與同您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心0-1001150-10121F10132D0-10087E0-71327127A步。要求寫出完整的過程，說明信號(hào)量的含義并賦初值。46.（7 分）某文件系統(tǒng)為一級(jí)目錄結(jié)構(gòu)，文件的數(shù)據(jù)改，但可多次創(chuàng)建新文件。請(qǐng)回答如下問題。（1）在連續(xù)、鏈?zhǔn)健⑺饕N文件的數(shù)據(jù)塊組織寫入磁盤，已寫入的文件不可修，哪種更合適？要求說明理由。為定位文件數(shù)據(jù)塊，需在FCB 中設(shè)計(jì)哪些相關(guān)描述字段？（2）為快速找到文件，對(duì)于好？要求說明理由。FCB，是集中好，還是與對(duì)應(yīng)的文件數(shù)據(jù)塊連續(xù)您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心47（9 分

23、）某主機(jī)的 MAC 地址為 00-15-C5-C1-5E-28，IP 地址為 00（私有地址）。題47-a 圖是網(wǎng)絡(luò)拓?fù)洌} 47-b 圖是該主機(jī)進(jìn)行Web 請(qǐng)求的 1 個(gè)以太網(wǎng)數(shù)據(jù)幀前 80 個(gè)字節(jié)的十六進(jìn)制及ASCII 碼內(nèi)容。MTU=1500 BR005Internet題 47-a 圖 網(wǎng)絡(luò)拓?fù)漕} 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í)，使用什么

24、協(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頁面了 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 圖所示。題 47-c 圖 以太網(wǎng)幀結(jié)構(gòu)比特 08162431頭部長(zhǎng)度服務(wù)類型版本總長(zhǎng)度標(biāo)識(shí)標(biāo)志片偏移生存時(shí)間(TTL)協(xié)議頭部校驗(yàn)和

25、源IP地址目的IP地址題 47-d 圖 IP 分組頭結(jié)構(gòu)您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心6 B6 B2 B46-1500 B4 B目的MAC地址源MAC地址類型數(shù)據(jù)CRC及詳解一、單項(xiàng)選擇題：140 小題，每小題 2 分，共 80 分。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。請(qǐng)?jiān)诖痤}卡上將所選項(xiàng)的字母涂黑。1. 【2. 【3. 【4. 【5. 【6. 【7. 【8. 【9. 【10. 【11. 【12. 【13. 【14. 【15. 【16. 【17. 【18. 【19. 【20. 【21. 【22. 【23. 【24. 【25. 【26. 【27. 【】A】B

26、】B】C】C】D】A】C】B】A】B】D】A】B】D】A】C】D】C】C】D】C】B】A】D】B】D28. 【29. 【30. 【31. 【32. 【】D】A】B】B】C您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心33. 【34. 【35. 【36. 【37. 【】A】B】B】D】D38【】C39【】C40【】B二、綜合應(yīng)用題：4147 小題，共 70 分。請(qǐng)將41寫在答題紙指定位置上?！尽看祟}考察的知識(shí)點(diǎn)是圖的以及關(guān)鍵路徑求解的綜合知識(shí)。（1）由題可以畫出待定上三角矩陣的結(jié)構(gòu)圖如下（圖中“？”待定元素）é 0? ùú?0¥¥¥&#

27、165;? 0¥¥¥? 0¥¥? 0¥ê ¥?êê ¥úúúúúúû? 0ê ¥êê ¥ê ¥ë可以看出，第一行至第五行主對(duì)角線上方的元素分別 5、4、3、2、1 個(gè)，由此可以畫出壓縮數(shù)組中的元素所屬行的情況，如下圖所示：第三行第一行第二行第四行第五行將個(gè)元素填入各行即得鄰接矩陣：（2 分）¥¥40¥

28、5;¥¥3¥0¥¥ ùé 040¥¥¥¥650¥¥¥ê ¥¥ úêê ¥ú¥ úA= ê ¥ú3êúê ¥3 úê ¥ú0ëû(2)根據(jù)第一步所得矩陣A 容易做出有向帶G，如下：（2 分）您所獲取的資料來源于 考研資料考研資料，請(qǐng)

29、中心0363445233514(3)下圖中粗線箭頭所標(biāo)識(shí)的 4 個(gè)活動(dòng)組成G 的關(guān)鍵路徑（3 分）0363442533514由上圖容易求得圖的關(guān)鍵路徑長(zhǎng)度為：4+5+4+3=16。42【】此題考察的知識(shí)點(diǎn)是基本算法的靈活運(yùn)用。（1）算法的基本設(shè)計(jì)思想：（5 分）1)比較笨的：將兩升序序列歸并排序，然后求其中位數(shù)，時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度O(n)。2) 高效的：分別求兩個(gè)升序序列A 和B 的中位數(shù)，設(shè)為a 和b。如果a=b，則 a 或者b 即為所求的中位數(shù)。：如果將兩序列歸并排序，則最終序列中，排在子序列 ab 前邊的元素為先前兩序列中排在a 和b 前邊的元素；排在子序列ab 后邊的元素

30、為先前兩序列a 和b 后邊的元素。所以子序列ab 一定位于最終序列的中間，有因?yàn)閍=b，顯然 a 就是中位數(shù)。如果ab（假設(shè)a<b），中位數(shù)只能出現(xiàn)在（a，b）范圍內(nèi)。：同樣可以用歸并排序后的序列來驗(yàn)證，歸并后排序后必然有形如ab的序列出現(xiàn)，中位數(shù)必然出現(xiàn)在（a，b）范圍內(nèi)。因此可以做如下處理：舍棄a 所在序列A 之中比較小的一半，同時(shí)舍棄 b 所在序列B 之中比較大的一半。在保留的兩個(gè)升序序列中求出新的中位數(shù)a 和b，重復(fù)上述過程，直到兩個(gè)序列只含一個(gè)元素為止，則較小者即為所求中位數(shù)。（2）算法實(shí)現(xiàn)（高效）：（8 分）int Search(int A, int B, int n)int

31、 s1,e1,mid1,s2,e2,mid2;s1=0;您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心e1=n-1;s2=1;e2=n-1;while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(Amid1=Bmid2)return Amid1;if(Amid1<Bmid2)/分別考慮奇數(shù)和偶數(shù)，保持兩個(gè)子數(shù)組元素個(gè)數(shù)相等if（s1+e1）%2=0）/若元素個(gè)數(shù)為奇數(shù)s1=mid1;/舍棄A 中間點(diǎn)以前部分且保留中間點(diǎn)e2=mid2; /舍棄B 中間點(diǎn)以后部分且保留中間點(diǎn)else/若元素個(gè)數(shù)為偶數(shù)s1=mid1+1;/舍棄A 中間點(diǎn)以前部

32、分且保留中間點(diǎn)e2=mid2; /舍棄B 中間點(diǎn)以后部分且保留中間點(diǎn)elseif(s1+e1)%2=0)/若元素個(gè)數(shù)為奇數(shù)個(gè)e1=mid1;/舍棄A 中間點(diǎn)以后部分且保留中間點(diǎn)s2=mid2;/舍棄B 中間點(diǎn)以前部分且保留中間點(diǎn)else/若元素個(gè)數(shù)為偶數(shù)個(gè)e1=mid1+1；/舍棄A 中間點(diǎn)以后部分且保留中間點(diǎn)s2=mid2；/舍棄B 中間點(diǎn)以前部分且保留中間點(diǎn)您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心return （As1<Bs2 ? As1:Bs2）;(3)上述所給算法的時(shí)間、空間復(fù)雜度分別是O(log2n)和O(1)。（2 分）因?yàn)槊看慰偟脑貍€(gè)數(shù)變?yōu)樵瓉淼囊话?，所以有?第一

33、次：元素個(gè)數(shù)為n/2=n/(21)第二次：元素個(gè)數(shù)為n/4=n/(22)第k 次：元素個(gè)數(shù)為n/(2k) 最后元素個(gè)數(shù)為 2則有n/(2k)=2解得k= log2n 1因此：時(shí)間復(fù)雜度為O(log2n)，而空間復(fù)雜度從上述可看出為O(1)。43【】此題考察的知識(shí)點(diǎn)是程序編譯運(yùn)行寄存器的運(yùn)用與變化。（1）寄存器R1的是 134，轉(zhuǎn)換成二進(jìn)制為 1000 0110B，即 86H。寄存器R5的是xy 的內(nèi)容，xy=-112，轉(zhuǎn)換成二進(jìn)制為 1001 0000B，即 90H。寄存器R6 的是 x+y 的內(nèi)容，x+y=380，轉(zhuǎn)換成二進(jìn)制為 1 0111 1100B（前面的進(jìn)位舍棄），即 7CH。由于計(jì)

34、算機(jī)字長(zhǎng)為 8 位，所以無符號(hào)整數(shù)能表示的范圍為 0255。而x+y=380，故溢出。（2）m 二進(jìn)制表示為 1000 0110B，由于 m 是 int 型，所以最高位為符號(hào)位，所以可以得出m 的原碼為：1111 1010（對(duì) 1000 0110 除符號(hào)位取反加 1），即-122。同理 n的二進(jìn)制表示為 1111 0110B，故n 的原碼為：1000 1010，轉(zhuǎn)成十進(jìn)制為-10。所以k1=-122-（-10）=-112.（3）可以利用同一個(gè)加法器及輔助電路實(shí)現(xiàn)。因?yàn)闊o符號(hào)整數(shù)都是以補(bǔ)碼形式，所以運(yùn)算規(guī)則都是一樣的。但是有一點(diǎn)需要考慮，由于無符號(hào)整數(shù)和有符號(hào)整數(shù)的表示范圍是不一樣的，所以需要設(shè)

35、置不一樣的溢出電路。（4）帶符號(hào)整數(shù)只有 k2 會(huì)發(fā)生溢出。分析：8 位帶符號(hào)整數(shù)的補(bǔ)碼取值范圍為：-128+127，而 k2=m+n=-122-10=-132，超出范圍，而 k=-112，在范圍-128+127之內(nèi)。三種可以溢出：雙符號(hào)位、最高位進(jìn)位、符號(hào)相同操作數(shù)的運(yùn)算后與原碼操作數(shù)的符號(hào)不同則溢出。您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心44【】此題考察的知識(shí)點(diǎn)是計(jì)算機(jī)的地址管理。（1）由于虛擬地址空間大小為16MB，且按字節(jié)編址，所以虛擬地址共有24 位（224=16M）。由于頁面大小為 4KB（212=4K），所以虛頁號(hào)為前 12 位。由于主存（物理）地址空間大小為 1MB，所

36、以物理地址共有 20 位（220=1M）。由于頁內(nèi)地址 12 位，所以 20-12=8，即前 8 位為頁框號(hào)。（2）由于Cache 采用直接方式，所以物理地址應(yīng)劃分成 3 個(gè)字段，如下：12 位3 位5 位分析：由于塊大小為 32B，所以字塊內(nèi)地址占 5 位。Cache 共 8 行，故字塊標(biāo)記占 3 位，所以主存字塊標(biāo)記占 20-5-3=12 位。（3）虛擬地址 001C60H 的虛頁號(hào)為前 12 位，即 001H=1。查表可知，其有效位為 1， 故在內(nèi)存中。虛頁號(hào)為 1 對(duì)應(yīng)頁框號(hào)為 04H，故物理地址為 04C60H。由于采用的是直接方式，所以對(duì)應(yīng) Cache 行號(hào)為 4。盡管有效位為 1

37、，但是由于標(biāo)記位 04CH064H，故不命中。（4）由于采用了 4應(yīng)劃分成 3 個(gè)字段，如下：相聯(lián)的，所以 Cache 被分為 2 組，每組 4 行。所以物理地址11 位1 位12 位將 024BACH 轉(zhuǎn)成二進(jìn)制為：0000 0010 010 0 1011 1010 1100，可以看出組號(hào)為 0，標(biāo)記為0000 0010 010，換成十六進(jìn)制為 0000 0001 0010（高位補(bǔ)一個(gè) 0），即 012H，從圖 44-c 中的 0 組可以看出，標(biāo)記為 012H 頁面的頁框號(hào)為 1F，故虛擬地址 024BACH 所在的頁面在主存中。45.【】此題考察的知識(shí)點(diǎn)是共享資源的使用與 P、V 操作以防

38、止死鎖。Semaphore seets =10;/表示空余座位數(shù)量的資源信號(hào)量，初值為 10Semaphore mutex = 1; /管理取號(hào)機(jī)的互斥信號(hào)量，初值為 1，表示取號(hào)機(jī)空閑Semaphore custom = 0; /表示顧客數(shù)量的資源信號(hào)量，初值為 0Process 顧客P(seets); /找個(gè)空座位P(mutex); /在看看取號(hào)機(jī)是否空閑從取號(hào)機(jī)取號(hào)；V(mutex) /放開那個(gè)取號(hào)機(jī)您所獲取的資料來源于 考研資料考研資料，請(qǐng)中心標(biāo)記位組號(hào)頁內(nèi)地址主存字塊標(biāo)記Cache 字塊標(biāo)記字塊內(nèi)地址V(custom); /取到號(hào)，告訴營(yíng)業(yè)員有顧客等待叫號(hào)；V(seets) /被叫號(hào)，離開座位接受服務(wù)；Process 營(yíng)業(yè)員While(true)P(custom); /看看有沒有等待的顧客叫號(hào)；為顧務(wù)；46.【】此題考察的知識(shí)點(diǎn)是文件系統(tǒng)中數(shù)據(jù)的組織方式，及文件的查找。（1）連續(xù)更合適