2013計算機考研真題及答案解析

2013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題2013年全國碩士研究生入學(xué)統(tǒng)一考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題（科目代碼408）12013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題一、單項選擇題：第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求。1．求整數(shù)n(n≥0)階乘的算法如下，其時間復(fù)雜度是intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A.O(log2n)

B.O(n)

C.(nlog2n)

D.O(n2)2．已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。將中綴表達式a+b-a*((cd)/e-f)+g轉(zhuǎn)換為等價的后綴表達式ab+acd+e/f-*-g+時，用棧來存放暫時還不能確定運算次序的操作符，若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是A.5

B.7

C.8

D.113.若一棵二叉樹的前序遍歷序列為a,e,b,d,c，后序遍歷序列為b,c,d,e,a，則根結(jié)點的孩子結(jié)點A.只有e

B.有e、b

C.有e、c

D.無法確定4．若平衡二叉樹的高度為6，且所有非葉結(jié)點的平衡因子均為1，則該平衡二叉樹的結(jié)點總數(shù)為A.10

B.20

C.32

D.335．對有n個結(jié)點、e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法時間復(fù)雜度是A.O(n)

B.O(e)

C.O(n+e)

D.O(n*e)6．若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是A.存在，且唯一C.存在，可能不唯一

B.存在，且不唯一D.無法確定是否存在7．對如下有向帶權(quán)圖，若采用迪杰斯特拉（Dijkstra）算法求源點a到其他各頂點的最短路徑，則得到的第一條最短路徑的目標(biāo)頂點是b，第二條最短路徑的目標(biāo)頂點是c，后續(xù)得到的其余各最短路徑的目標(biāo)頂點依次是22013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題A.d,e,f

B.e,d,f

C.f,d,e

D.f,e,d8．下列關(guān)于最小生成樹的說法中，正確的是I.最小生成樹樹的代價唯一II.權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中III.用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同IV.普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同A.僅I

B.僅II

C.僅I、III

D.僅II、IV9．設(shè)有一棵3階B樹，如下圖所示。刪除關(guān)鍵字78得到一棵新B樹，其最右葉結(jié)點所含的關(guān)鍵字是A.60

B.60,62

C.62,65

D.6510．在內(nèi)部排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束都至少能夠確定一個元素最終位置的方法是I.簡單選擇排序

II.希爾排序

III.快速排序

IV堆排序

V.二路歸并排序A.僅I、III、IVC.僅II、III、IV

B.僅I、III、VD.僅III、IV、V11．對一待排序序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同之處是A.排序的總趟數(shù)C.使用輔助空間的數(shù)量

B.元素的移動次數(shù)D.元素之間的比較次數(shù)12．假定基準(zhǔn)程序A在某計算機上的運行時間為100秒，其中90秒為CPU時間，其余為I/O時間。若CPU速度提高50%，I/O速度不變，則運行基準(zhǔn)程序A所耗費的時間是A.55秒

B.60秒

C.65秒

D.70秒13．假定編譯器規(guī)定int和short類型長度占32位和16位，執(zhí)行下列C語言語句unsignedshortx=65530;unsignedinty=x;得到y(tǒng)的機器數(shù)為32013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題A.00007FFA

B.0000FFFA

C.FFFF7FFA

D.FFFFFFFA14．float類型（即IEEE754單精度浮點數(shù)格式）能表示的最大正整數(shù)是A.2126-2103

B.2127-2104

C.2127-2103

D.2128-210415．某計算機存儲器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長度分別為32位和16位，并且數(shù)據(jù)按邊界對齊存儲。某C語言程序段如下：struct{inta;charb;shortc;}record;record.a=273;若record變量的首地址為0Xc008，則低至0Xc008中內(nèi)容及record.c的地址分別為A.0x00、0xC00DC.0x11、0xC00D

B.0x00、0xC00ED.0x11、0xC00E16．下列關(guān)于閃存（FlashMemory）的敘述中，錯誤的是A.信息可讀可寫，并且讀、寫速度一樣快B.存儲元由MOS管組成，是一種半導(dǎo)體存儲器C.掉電后信息不丟失，是一種非易失性存儲器D.采用隨機訪問方式，可替代計算機外部存儲器17．假設(shè)某計算機按字編址，Cache有4個行，Cache和主存之間交換的塊為1個字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方式和LRU替換算法。當(dāng)訪問的主存地址依次為0,4,8,2,0,6,8,6,4,8時，命中Cache的次數(shù)是A.1

B.2

C.3

D.418．某計算機的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接編碼法，共有33個微命令，構(gòu)成5個互斥類，分別包含7、3、12、5和6個微命令，則操作控制字段至少有A.5位

B.6位

C.15位

D.33位19．某同步總線的時鐘頻率為100MHz，寬度為32位，地址/數(shù)據(jù)線復(fù)用，每傳送一次地址或者數(shù)據(jù)占用一個時鐘周期。若該總線支持突發(fā)（猝發(fā)）傳輸方式，則一次“主存寫”總線事務(wù)傳輸128位數(shù)據(jù)所需要的時間至少是A.20ns

B.40ns

C.50ns

D.80ns20．下列關(guān)于USB總線特性的描述中，錯誤的是42013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題A.可實現(xiàn)外設(shè)的即插即用和熱拔插B.可通過級聯(lián)方式連接多臺外設(shè)C.是一種通信總線，連接不同外設(shè)D.同時可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高21．下列選項中，在I/O總線的數(shù)據(jù)線上傳輸?shù)男畔↖.I/O接口中的命令字

II.I/O接口中的狀態(tài)字

III.中斷類型號A.僅I、II

B.僅I、III

C.僅II、III

D.I、II、III22．響應(yīng)外部中斷的過程中，中斷隱指令完成的操作，除保護斷點外，還包括I.關(guān)中斷

II.保存通用寄存器的內(nèi)容

III.形成中斷服務(wù)程序入口地址并送PCA.僅I、II

B.僅I、III

C.僅II、III

D.I、II、III23．下列選項中，不可能在用戶態(tài)發(fā)生的事件是A.系統(tǒng)調(diào)用

B.外部中斷

C.進程切換

D.缺頁24．中斷處理和子程序調(diào)用都需要壓棧以保護現(xiàn)場，中斷處理一定會保存而子程序調(diào)用不需要保存其內(nèi)容的是A.程序計數(shù)器C.通用數(shù)據(jù)寄存器25．下列關(guān)于虛擬存儲器的敘述中，正確的是A.虛擬存儲只能基于連續(xù)分配技術(shù)C.虛擬存儲容量只受外存容量的限制

B.程序狀態(tài)字寄存器D.通用地址寄存器B.虛擬存儲只能基于非連續(xù)分配技術(shù)D.虛擬存儲容量只受內(nèi)存容量的限制26．操作系的I/O子系統(tǒng)通常由四個層次組成，每一層明確定義了與鄰近層次的接口，其合理的層次組織排列順序是A.用戶級I/O軟件、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動程序、中斷處理程序B.用戶級I/O軟件、設(shè)備無關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動程序C.用戶級I/O軟件、設(shè)備驅(qū)動程序、設(shè)備無關(guān)軟件、中斷處理程序D.用戶級I/O軟件、中斷處理程序、設(shè)備無關(guān)軟件、設(shè)備驅(qū)動程序27．假設(shè)5個進程P0、P1、P2、P3、P4共享三類資源R1、R2、R3，這些資源總數(shù)分別為18、6、22。T0時刻的資源分配情況如下表所示，此時存在的一個安全序列是52013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題進程P0P1P2P3P4

R134423

已分配資源R220001

R333544

R155444

資源最大需求R253022

R31061154A.P0,P2,P4,P1,P3C.P2，P1，P0，P3，P4

B.P1,P0,P3,P4,P2D.P3,P4,P2,P1,P028．若一個用戶進程通過read系統(tǒng)調(diào)用讀取一個磁盤文件中的數(shù)據(jù)，則下列關(guān)于此過程的敘述中，正確的是I.若該文件的數(shù)據(jù)不在內(nèi)存，則該進程進入睡眠等待狀態(tài)II.請求read系統(tǒng)調(diào)用會導(dǎo)致CPU從用戶態(tài)切換到核心態(tài)III.read系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱A.僅I、II

B.僅I、III

C.僅II、III

D.I、II和III29．一個多道批處理系統(tǒng)中僅有P1和P2兩個作業(yè)，P2比P1晚5ms到達，它的計算和I/O操作順序如下：P1：計算60ms，I/O80ms，計算20msP2：計算120ms，I/O40ms，計算40ms若不考慮調(diào)度和切換時間，則完成兩個作業(yè)需要的時間最少是A.240ms

B.260ms

C.340ms

D.360ms30．若某單處理器多進程系統(tǒng)中有多個就緒態(tài)進程，則下列關(guān)于處理機調(diào)度的敘述中錯誤的是A.在進程結(jié)束時能進行處理機調(diào)度B.創(chuàng)建新進程后能進行處理機調(diào)度C.在進程處于臨界區(qū)時不能進行處理機調(diào)度D.在系統(tǒng)調(diào)用完成并返回用戶態(tài)時能進行處理機調(diào)度31．下列關(guān)于進程和線程的敘述中，正確的是A.不管系統(tǒng)是否支持線程，進程都是資源分配的基本單位B.線程是資源分配的基本單位，進程是調(diào)度的基本單位C.系統(tǒng)級線程和用戶級線程的切換都需要內(nèi)核的支持D.同一進程中的各個線程擁有各自不同的地址空間32．下列選項中，不能改善磁盤設(shè)備I/O性能的是62013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題A.重排I/O請求次序C.預(yù)讀和滯后寫33．在TCP/IP體系結(jié)構(gòu)中，直接為ICMP提供服務(wù)協(xié)議的是

B.在一個磁盤上設(shè)置多個分區(qū)D.優(yōu)化文件物理的分布A.PPP

B.IP

C.UDP

D.TCP34．在物理層接口特性中，用于描述完成每種功能的事件發(fā)生順序的是A.機械特性

B.功能特性

C.過程特性

D.電氣特性35．以太網(wǎng)的MAC協(xié)議提供的是A.無連接的不可靠的服務(wù)C.有連接的可靠的服務(wù)

B.無連接的可靠的服務(wù)D.有連接的不可靠的服務(wù)36．兩臺主機之間的數(shù)據(jù)鏈路層采用后退N幀協(xié)議（GBN）傳輸數(shù)據(jù)數(shù)據(jù)傳輸速率為16kbps，單向傳播時延為270ms，數(shù)據(jù)幀長度范圍是128~512字節(jié)，接收方總是以與數(shù)據(jù)幀等長的幀進行確認(rèn)。為使信道利用率達到最高，幀序列的比特數(shù)至少為A.5

B.4

C.3

D.237．下列關(guān)于IP路由器功能的描述中，正確的是I.運行路由協(xié)議，設(shè)備路由表II.監(jiān)測到擁塞時，合理丟棄IP分組III.對收到的IP分組頭進行差錯校驗，確保傳輸?shù)腎P分組不丟失IV.根據(jù)收到的IP分組的目的IP地址，將其轉(zhuǎn)發(fā)到合適的輸出線路上A.僅III、IV

B.僅I、II、III

C.僅I、II、IV

D.I、II、III、IV38．ARP協(xié)議的功能是A.根據(jù)IP地址查詢MAC地址C.根據(jù)域名查詢IP地址

B.根據(jù)MAC地址查詢IP地址D.根據(jù)IP地址查詢域名39．某主機的IP地址為180.80.77.55，子網(wǎng)掩碼為255.255.252.0。若該主機向其所在子網(wǎng)發(fā)送廣播分組，則目的地址可以是A.180.80.76.0

B.180.80.76.255

C.180.80.77.255

D.180.80.79.25540．若用戶1與用戶2之間發(fā)送和接收電子郵件的過程如下圖所示，則圖中①、②、③階段分別使用的應(yīng)用層協(xié)議可以是72013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題A.SMTP、SMTP、SMTPC.POP3、SMTP、SMTP

B.POP3、SMTP、POP3D.SMTP、SMTP、POP3二、綜合應(yīng)用題：第41～47題，共70分。請將答案寫在答題紙指定位置上。41.（10分）設(shè)有6個有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200個數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個表最終合并成1個升序表，并在最壞情況下比較的總次數(shù)達到最小。請問答下列問題。（1）給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。（2）根據(jù)你的合并過程，描述n（n≥2）個不等長升序表的合并策略，并說明理由。82013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題42.（13分）假定采用帶頭結(jié)點的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間，例如，“l(fā)oading”和“being”的存儲映像如下圖所示。str1l

o

a

dstr2

b

e

i

p

n

g^設(shè)str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為

，請設(shè)計一個時間上盡可能高效的算法，找出由str1和str2所指向兩個鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點的位置p）。要求：（1）給出算法的基本設(shè)計思想。（2）根據(jù)設(shè)計思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。（3）說明你所設(shè)計算法的時間復(fù)雜度。92013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題43.（11分）假設(shè)某計算機的CPU主頻為80MHz，CPI為4，并且平均每條指令訪存1.5次，主存與Cache之間交換的塊大小為16B，Cache的命中率為99%，存儲器總線寬度為32位。請回答下列問題。（1）該計算機的MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA傳送的情況下。主存帶寬至少達到多少才能滿足CPU的訪存要求？（2）假定在Cache缺失的情況下訪問主存時，存在0.0005%的缺頁率，則CPU平均每秒產(chǎn)生多少次缺頁異常？若頁面大小為4KB，每次缺頁都需要訪問磁盤，訪問磁盤時DMA傳送采用周期挪用方式，磁盤I/O接口的數(shù)據(jù)緩沖寄存器為32位，則磁盤I/O接口平均每秒發(fā)出的DMA請求次數(shù)至少是多少？（3）CPU和DMA控制器同時要求使用存儲器總線時，哪個優(yōu)先級更高？為什么？（4）為了提高性能，主存采用4體低位交叉存儲器，工作時每1/4周期啟動一個存儲體，每個存儲體傳送周期為50ns，則主存能提供的最大帶寬是多少？44.（12分）某16位計算機中，帶符號整數(shù)用補碼表示，數(shù)據(jù)Cache和指令Cache分離。題44表給出了指令系統(tǒng)中部分指令格式，其中Rs和Rd表示寄存器，mem表示存儲單元地址，（x）表示寄存器x或存儲單元x的內(nèi)容。題44表指令系統(tǒng)中部分指令格式10名稱指令的匯編格式名稱指令的匯編格式指令功能加法指令A(yù)DDRs，Rd(Rs)+(Rd)->Rd算術(shù)/邏輯左移SHLRd2*(Rd)->Rd算術(shù)右移SHRRd(Rd)/2->Rd取數(shù)指令LOADRd，mem(mem)->Rd存數(shù)指令STORERs，memRs->(mem)2013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題該計算機采用5段流水方式執(zhí)行指令，各流水段分別是取指（IF）、譯碼/讀寄存器（ID）、執(zhí)行/計算有效地址（EX）、訪問存儲器（M）和結(jié)果寫回寄存器（WB），流水線采用“按序發(fā)射，按序完成”方式，沒有采用轉(zhuǎn)發(fā)技術(shù)處理數(shù)據(jù)相關(guān)，并且同一寄存器的讀和寫操作不能在同一個時鐘周期內(nèi)進行。請回答下列問題。（1）若int型變量x的值為-513，存放在寄存器R1中，則執(zhí)行“SHLR1”后，R1中的內(nèi)容是多少？（用十六進制表示）（2）若在某個時間段中，有連續(xù)的4條指令進入流水線，在其執(zhí)行過程中沒有發(fā)生任何阻塞，則執(zhí)行這4條指令所需的時鐘周期數(shù)為多少？（3）若高級語言程序中某賦值語句為x=a+b，x、a和b均為int型變量，它們的存儲單元地址分別表示為[x]、[a]和[b]。該語句對應(yīng)的指令序列及其在指令流中的執(zhí)行過程如題44圖所示。I1I2I3I4

LOADLOADADDSTORE

R1，[a]R2，[b]R1，R2R2，[x]題44圖指令序列及其執(zhí)行過程示意圖則這4條指令執(zhí)行過程中I3的ID段和I4的IF段被阻塞的原因各是什么？（4）若高級語言程序中某賦值語句為x=x*2+a，x和a均為unsignedint類型變量，它們的存儲單元地址分別表示為[x]、[a]，則執(zhí)行這條語句至少需要多少個時鐘周期？要求模仿題44圖畫出這條語句對應(yīng)的指令序列及其在流水線中的執(zhí)行過程示意圖。112013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題45.(7分)某請求分頁系統(tǒng)的頁面置換策略如下：從0時刻開始掃描，每隔5個時間單位掃描一輪駐留集（掃描時間忽略不計）且在本輪沒有被訪問過的頁框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次分配之前不清空。當(dāng)放發(fā)生缺頁時，如果該頁曾被使用過且還在空閑頁鏈表中，則重新放回進程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁框。忽略其它進程的影響和系統(tǒng)開銷。初始時進程駐留集為空。目前系統(tǒng)空閑頁的頁框號依次為32、15、21、41。進程P依次訪問的<虛擬頁號，訪問時刻>為<1,1>、<3,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>。請回答下列問題。（1）當(dāng)虛擬頁為<0,4>時，對應(yīng)的頁框號是什么？（2）當(dāng)虛擬頁為<1,11>時，對應(yīng)的頁框號是什么？說明理由。（3）當(dāng)虛擬頁為<2,14>時，對應(yīng)的頁框號是什么？說明理由。（4）這種方法是否適合于時間局部性好的程序？說明理由。122013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題46.（8分）某文件系統(tǒng)空間的最大容量為4TB（1TB=240），以磁盤塊為基本分配單位。磁盤塊大小為1KB。文件控制塊（FCB）包含一個512B的索引表區(qū)。請回答下列問題。（1）假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表區(qū)存放文件占用的磁盤塊號，索引表項中塊號最少占多少字節(jié)？可支持的單個文件最大長度是多少字節(jié)？（2）假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第0~7字節(jié)采用<起始塊號，塊數(shù)>格式表示文件創(chuàng)建時預(yù)分配的連續(xù)存儲空間。其中起始塊號占6B，塊數(shù)占2B，剩余504字節(jié)采用直接索引結(jié)構(gòu)，一個索引項占6B，則可支持的單個文件最大長度是多少字節(jié)？為了使單個文件的長度達到最大，請指出起始塊號和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理由。47.（9分）主機H通過快速以太網(wǎng)連接Internet，IP地址為192.168.0.8，服務(wù)器S的IP地址為211.68.71.80。H與S使用TCP通信時，在H上捕獲的其中5個IP分組如題47-a表所示。題47-a表回答下列問題。（1）題47-a表中的IP分組中，哪幾個是由H發(fā)送的？哪幾個完成了TCP連接建立過程？哪幾個在通過快速以太網(wǎng)傳輸時進行了填充？（2）根據(jù)題47-a表中的IP分組，分析S已經(jīng)收到的應(yīng)用層數(shù)據(jù)字節(jié)數(shù)是多少？（3）若題47-a表中的某個IP分組在S發(fā)出時的前40字節(jié)如題47-b表所示，則該IP分組到達H時經(jīng)過了多13編號IP編號IP分組的前40字節(jié)內(nèi)容（十六進制）145000030019b400080061de8c0a80008d34447500bd91388846b41c500000000700243805db000002430000300000400031066e83d3444750c0a8000813880bd9e0599fef846b41c6701216d037e10000345000028019c400080061defc0a80008d34447500bd91388846b41c6e0599ff050f043802b320000445000038019d400080061ddec0a80008d34447500bd91388846b41c6e0599ff050184380e6550000545000028681140003106067ad3444750c0a8000813880bd9e0599ff0846b41d6501016d057d200002013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題少個路由器？題47-b表來自S的分組

45000028681140004006ecadd3444750ca7601061388a108e0599ff0

846b41d6501016d0b7d60000注：IP分組頭和TCP段頭結(jié)構(gòu)分別如題47-a圖，題47-b圖所示。題47-a圖IP分組頭結(jié)構(gòu)題47-b圖TCP段頭結(jié)構(gòu)142013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題計算機專業(yè)基礎(chǔ)綜合試題參考答案一、單項選擇題：每小題2分，共80分。1-5BAABC21-25DBCBB

6-10CCADA26-30ADABC

11-15DDBDD31-35ABBCA

16-20ACCCD36-40BCADD二、綜合應(yīng)用題：41~47小題，共70分。41.【解析】（1）對于長度分別為m，n的兩個有序表的合并過程，最壞情況下需要一直比較到兩個表尾元素，比較次數(shù)為m+n-1次。已知需要5次兩兩合并，故可設(shè)總比較次數(shù)為X-5，X就是以N個葉子結(jié)點表示升序表，以升序表的表長表示結(jié)點權(quán)重，構(gòu)造的二叉樹的帶權(quán)路徑長度。故只需設(shè)計方案使得X最小。這樣受哈夫曼樹和最佳歸并樹思想的啟發(fā)，設(shè)計哈夫曼樹如下：這樣，最壞情況下比較的總次數(shù)為：N=(10+35)×4+(40+50+60)×3+200?5=825（2）N（N≥2）個不等長升序表的合并策略：以N個葉子結(jié)點表示升序表，以升序表的表長表示結(jié)點權(quán)重，構(gòu)造哈夫曼樹。合并時，從深度最大的結(jié)點所代表的升序表開始合并，依深度次序一直進行到根結(jié)點。理由：N個有序表合并需要進行N-1次兩兩合并，可設(shè)最壞情況下的比較總次數(shù)為X-N+1，X就是以N個葉子結(jié)點表示升序表，以升序表的表長表示結(jié)點權(quán)重，構(gòu)造的二叉樹的帶權(quán)路徑長度。根據(jù)哈夫曼樹的特點，上述設(shè)計的比較次數(shù)是最小的。42.【解析】（1）算法思想：順序遍歷兩個鏈表到尾結(jié)點時，并不能保證兩個鏈表同時到達尾結(jié)點。這是因為兩個鏈表的長度不同。假設(shè)一個鏈表比另一個鏈表長k個結(jié)點，我們先在長鏈表上遍歷k個結(jié)點，之后同步遍歷兩個鏈表。這樣我們就能夠保證它們同時到達最后一個結(jié)點了。由于兩個鏈表從第一個公共結(jié)點到鏈表的尾結(jié)點都是重合的。所以它們肯定同時到達第一個公共結(jié)點。于是得到算法思路：①遍歷兩個鏈表求的它們的長度L1，L2；②比較L1，L2，找出較長的鏈表，并求L=|L1-L2|；③先遍歷長鏈表的L各結(jié)點；152013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題④同步遍歷兩個鏈表，直至找到相同結(jié)點或鏈表結(jié)束。（2）算法的C語言代碼描述LinkListSearch_First_Common(LinkListL1,LinkListL2){//本算法實現(xiàn)線性時間內(nèi)找到兩個單鏈表的第一個公共結(jié)點intlen1=Length(L1);,len2=Length(L2);LinkListlongList,shortlist;//分別指向較長和較短的鏈表if(len1>len2){longList=L1->next;shortlist=L2->next;L=len1-len2;//表長之差}else{longList=L2->next;shortlist=L1->next;L=len2-len1;//表長之差}While(L--)longList=longList->next;while(longList!=NULL){if(longList==shortList)//同步尋找共同結(jié)點returnlongList;else{longList=longList->next;shortlist=shortlist->next;}}//whilereturnNULL;}（3）算法的時間復(fù)雜度為O(len1+len2)，空間復(fù)雜度為O(1)。43.【解析】（1）MIPS=CPU主頻×10-6/CPI=80M/4=20；平均每條指令訪存1.5次,Cache的命中率為99%，故每秒Cache缺失的次數(shù)=20M×1.5×1%=300000（次）；（2）在不使用DMA傳送的情況下，所有主存的存取操作都需要經(jīng)過CPU，所以主存帶寬至少應(yīng)為20M/s×1.5×4B=120MB/s。由于頁式虛擬存儲方式的頁表始終位于內(nèi)存，則產(chǎn)生缺頁異常的只能是指令的訪存。每秒產(chǎn)生缺頁中斷20M/s×1.5×0.0005%=150次。因此平均每秒發(fā)出的DMA請求次數(shù)至少是150×4KB/4B=150K次。（3）優(yōu)先響應(yīng)DMA請求。DMA通常連接高速I/O設(shè)備，若不及時處理可能丟失數(shù)據(jù)。（4）當(dāng)4體低位交叉存儲器穩(wěn)定運行時，能提供的最大帶寬為4×4B/50ns=320MB/s。44.【解析】（1）x的機器碼為[x]補=111111011111B，即指令執(zhí)行前（R1）=FDFFH，右移1位后位1111111011111111B，即指令執(zhí)行后（R1）=FEFFH。（2）至少需要4+（5-1）=8個時鐘周期數(shù)。（3）I3的ID段被阻塞的原因：因為I3與I1和I2都存在數(shù)據(jù)相關(guān)，需等到I1和I2將結(jié)果寫回寄存器后，I3才能162013年全國碩士研究生入學(xué)統(tǒng)一考試—計算機專業(yè)基礎(chǔ)綜合試題讀寄存器內(nèi)容，所以I3的ID段被阻塞。I4的IF段被阻塞的原因：因為I4的前一條指令I(lǐng)3在ID段被阻塞，所以I4的IF段被阻塞。（4）因2*x操作有左移和加法兩種實現(xiàn)方法，故x=x*2+a對應(yīng)的指令序列為I1LOAD

R1，[x]I2LOADR2，[a]I3SHLR1//或者

ADDR1，R1I4I5

ADDR1，R2STORER2，[x]這5條指令在流水線中執(zhí)行過程如下圖所示。故執(zhí)行x=x*2+a語句最少需要17個時鐘周期。45.【解析】（1）頁框號為21。因為起始駐留集為空，而0頁對應(yīng)的頁框為空閑鏈表中的第三個空閑頁框（21），其對應(yīng)的頁框號為21。（2）頁框號為32。理由：因11>10故發(fā)生第三輪掃描，頁號為1的頁框在第二輪已處于空閑頁框鏈表中，此刻該頁又被重新訪問，因此應(yīng)被重新放回駐留集中，其頁框號為32。（3）頁框號為41。理由：因為第2頁從來沒有被訪問過，它不在駐留集中，因此從空閑頁框鏈表中取出鏈表頭的頁框41，頁框號為41。（4）