2013計(jì)算機(jī)考研真題及答案解析

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

B.O(n)

C.(nlog2n)

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

B.7

C.8

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

B.有e、b

C.有e、c

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

B.20

C.32

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

B.O(e)

C.O(n+e)

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

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

B.e,d,f

C.f,d,e

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

B.僅II

C.僅I、III

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

B.60,62

C.62,65

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

II.希爾排序

III.快速排序

IV堆排序

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

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

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

B.60秒

C.65秒

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

B.0000FFFA

C.FFFF7FFA

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

B.2127-2104

C.2127-2103

D.2128-210415．某計(jì)算機(jī)存儲(chǔ)器按字節(jié)編址，采用小端方式存放數(shù)據(jù)。假定編譯器規(guī)定int和short型長(zhǎng)度分別為32位和16位，并且數(shù)據(jù)按邊界對(duì)齊存儲(chǔ)。某C語(yǔ)言程序段如下：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）的敘述中，錯(cuò)誤的是A.信息可讀可寫(xiě)，并且讀、寫(xiě)速度一樣快B.存儲(chǔ)元由MOS管組成，是一種半導(dǎo)體存儲(chǔ)器C.掉電后信息不丟失，是一種非易失性存儲(chǔ)器D.采用隨機(jī)訪問(wèn)方式，可替代計(jì)算機(jī)外部存儲(chǔ)器17．假設(shè)某計(jì)算機(jī)按字編址，Cache有4個(gè)行，Cache和主存之間交換的塊為1個(gè)字。若Cache的內(nèi)容初始為空，采用2路組相聯(lián)映射方式和LRU替換算法。當(dāng)訪問(wèn)的主存地址依次為0,4,8,2,0,6,8,6,4,8時(shí)，命中Cache的次數(shù)是A.1

B.2

C.3

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

B.6位

C.15位

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

B.40ns

C.50ns

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

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

III.中斷類型號(hào)A.僅I、II

B.僅I、III

C.僅II、III

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

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

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

B.僅I、III

C.僅II、III

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

B.外部中斷

C.進(jìn)程切換

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

B.程序狀態(tài)字寄存器D.通用地址寄存器B.虛擬存儲(chǔ)只能基于非連續(xù)分配技術(shù)D.虛擬存儲(chǔ)容量只受內(nèi)存容量的限制26．操作系的I/O子系統(tǒng)通常由四個(gè)層次組成，每一層明確定義了與鄰近層次的接口，其合理的層次組織排列順序是A.用戶級(jí)I/O軟件、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序、中斷處理程序B.用戶級(jí)I/O軟件、設(shè)備無(wú)關(guān)軟件、中斷處理程序、設(shè)備驅(qū)動(dòng)程序C.用戶級(jí)I/O軟件、設(shè)備驅(qū)動(dòng)程序、設(shè)備無(wú)關(guān)軟件、中斷處理程序D.用戶級(jí)I/O軟件、中斷處理程序、設(shè)備無(wú)關(guān)軟件、設(shè)備驅(qū)動(dòng)程序27．假設(shè)5個(gè)進(jìn)程P0、P1、P2、P3、P4共享三類資源R1、R2、R3，這些資源總數(shù)分別為18、6、22。T0時(shí)刻的資源分配情況如下表所示，此時(shí)存在的一個(gè)安全序列是52013年全國(guó)碩士研究生入學(xué)統(tǒng)一考試—計(jì)算機(jī)專業(yè)基礎(chǔ)綜合試題進(jìn)程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．若一個(gè)用戶進(jìn)程通過(guò)read系統(tǒng)調(diào)用讀取一個(gè)磁盤(pán)文件中的數(shù)據(jù)，則下列關(guān)于此過(guò)程的敘述中，正確的是I.若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)II.請(qǐng)求read系統(tǒng)調(diào)用會(huì)導(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．一個(gè)多道批處理系統(tǒng)中僅有P1和P2兩個(gè)作業(yè)，P2比P1晚5ms到達(dá)，它的計(jì)算和I/O操作順序如下：P1：計(jì)算60ms，I/O80ms，計(jì)算20msP2：計(jì)算120ms，I/O40ms，計(jì)算40ms若不考慮調(diào)度和切換時(shí)間，則完成兩個(gè)作業(yè)需要的時(shí)間最少是A.240ms

B.260ms

C.340ms

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

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

B.IP

C.UDP

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

B.功能特性

C.過(guò)程特性

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

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

B.4

C.3

D.237．下列關(guān)于IP路由器功能的描述中，正確的是I.運(yùn)行路由協(xié)議，設(shè)備路由表II.監(jiān)測(cè)到擁塞時(shí)，合理丟棄IP分組III.對(duì)收到的IP分組頭進(jìn)行差錯(cuò)校驗(yàn)，確保傳輸?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．某主機(jī)的IP地址為180.80.77.55，子網(wǎng)掩碼為255.255.252.0。若該主機(jī)向其所在子網(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ā)送和接收電子郵件的過(guò)程如下圖所示，則圖中①、②、③階段分別使用的應(yīng)用層協(xié)議可以是72013年全國(guó)碩士研究生入學(xué)統(tǒng)一考試—計(jì)算機(jī)專業(yè)基礎(chǔ)綜合試題A.SMTP、SMTP、SMTPC.POP3、SMTP、SMTP

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

o

a

dstr2

b

e

i

p

n

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

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

LOADLOADADDSTORE

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

6-10CCADA26-30ADABC

11-15DDBDD31-35ABBCA

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

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

ADDR1，R1I4I5

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