2023計算機(jī)考研真題及答案

2023年全國碩士探討生入學(xué)統(tǒng)一考試一計算機(jī)專業(yè)基礎(chǔ)綜合試題

2023年全國碩士探討生入學(xué)統(tǒng)一考試

計算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考

計算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題

（科目代碼408）

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

一、單項選擇題：第1?40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題

要求。

1.求整數(shù)n(nK))階乘的算法如下，其時間困難度是

intfact(inln)

(

if(n<=1)return1;

returnn*fact(n-l);

)

A.O(log2n)B.O(n)C.(nlogzn)D.0(m)

2.己知操作符包括('和')'。將中綴表達(dá)式a+b-a*((cd)/e-f)+g轉(zhuǎn)換為等價的后綴表達(dá)式ab+acd+e/f-*-g+

時，用棧來存放短暫還不能確定運(yùn)算次序的操作符，若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最

大個數(shù)是

A.5B.7C.8D.II

3.若一棵二叉樹的前序遍歷序列為a,e,b,d,c,后序遍歷序列為b,c,d,e,a,則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)

A.只有eB.有e、bC.有e、cD.無法確定

4.若平衡二叉樹的高度為6,且全部非葉結(jié)點(diǎn)的平衡因子均為1,則該平衡二叉樹的結(jié)點(diǎn)總數(shù)為

A.10B.20C.32D.33

5.對有n個結(jié)點(diǎn)、e條邊且運(yùn)用鄰接表存儲的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時間困難度是

A.O(n)B.O(e)C.O(n+e)D.O(n*e)

6.若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是

A.存在，且唯一B.存在，且不唯一

C.存在，可能不唯一D.無法確定是否存在

7.對如下有向帶權(quán)圖，若采納迪杰斯特拉(Dijkstra)算法求源點(diǎn)a到其他各頂點(diǎn)的最短路徑，則得到的第一條最

短路徑的目標(biāo)頂點(diǎn)是b,其次條最短路徑的目標(biāo)頂點(diǎn)是c,后續(xù)得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是

2

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

A.d,e,fB.e,d,fC.f,d,eD.f,e,d

8.下列關(guān)于最小生成樹的說法中，正確的是

I.最小生成樹樹的代價唯一

II.權(quán)值最小的邊確定會出現(xiàn)在全部的最小生成樹中

111.用普里姆（Prim）算法從不同頂點(diǎn)起先得到的最小生成樹確定相同

IV.普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同

A.僅IB.僅IIC.僅I、IIID.僅II、IV

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

A.60B.60,62C.62,65D.65

10.在內(nèi)部排序過程中，對尚未確定最終位置的全部元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排

序結(jié)束都至少能夠確定一個元素最終位置的方法是

I.簡潔選擇排序H.希爾排序ni.快速排序iv堆排序V,二路歸并排序

A.僅I、III、IVB.僅I、III、V

C.僅H、HI、IVD.僅IILIV、V

11.對一待排序序列分別進(jìn)行折半插入排序和干脆插入排序，兩者之間可能的不同之處是

A.排序的總趟數(shù)B.元素的移動次數(shù)

C.運(yùn)用協(xié)助空間的數(shù)量D.元素之間的比較次數(shù)

12.假定基準(zhǔn)程序A在某計算機(jī)上的運(yùn)行時間為100秒，其中90秒為CPU時間，其余為I/O時間。若CPU速度

提高50%,I/O速度不變，則運(yùn)行基準(zhǔn)程序A所耗費(fèi)的時間是

A.55秒B.60秒C.65秒D.70秒

13.假定編譯器規(guī)定int和short類型長度占32位和16位，執(zhí)行下列C語言語句

unsignedshortx=65530;

unsignedinty=x;

得到y(tǒng)的機(jī)器數(shù)為

3

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

A.00007FFAB.0000FFFAC.FFFF7FFAD.FFFFFFFA

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

A.2126-2103B.2127-2104C.2127-2103D.2128-2lO4

15.某計算機(jī)存儲器按字節(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>OxCOODB.0x00、OxCOOE

C.0x1kOxCOODD.0x11>OxCOOE

16.下列關(guān)于閃存（FlashMemory）的敘述中，錯誤的是

A.信息可讀可寫，并且讀、寫速度一樣快

B.存儲元由MOS管組成，是一種半導(dǎo)體存儲器

C.掉電后信息不丟失，是一種非易失性存儲器

D.采納隨機(jī)訪問方式，可替代計算機(jī)外部存儲器

17.假設(shè)某計算機(jī)按字編址，Cache有4個行，Cache和主存之間交換的塊為1個字。若Cache的內(nèi)容初始為空，

采納2路組相聯(lián)映射方式和LRU替換算法。當(dāng)訪問的主存地址依次為0,4,8,2,0,6,8,64,8時，命中Cache的次數(shù)是

A.1B.2C.3D.4

18.某計算機(jī)的限制器采納微程序限制方式，微指令中的操作限制字段采納字段干脆編碼法，共有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.20nsB.40nsC.50nsD.80ns

20.下列關(guān)于USB總線特性的描述中，錯誤的是

4

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

A.可實(shí)現(xiàn)外設(shè)的即插即用和熱拔插

B.可通過級聯(lián)方式連接多臺外設(shè)

C.是一種通信總線，連接不同外設(shè)

D.同時可傳輸2位數(shù)據(jù)，數(shù)據(jù)傳輸率高

21.下列選項中，在I/O總線的數(shù)據(jù)線上傳輸?shù)男畔?/p>

I.I/O接口中的吩咐字II.I/O接口中的狀態(tài)字III.中斷類型號

A.僅I、IIB.僅I、H1C.僅II、IIID.LIkIII

22.響應(yīng)外部中斷的過程中，中斷隱指令完成的操作,除愛護(hù)斷點(diǎn)外，還包括

I.關(guān)中斷n.保存通用寄存器的內(nèi)容in.形成中斷服務(wù)程序入口地址并送PC

A.僅I、IIB.僅1、IIIC.僅II>IIID.I、II、III

23.下列選項中，不行能在用戶態(tài)發(fā)生的事務(wù)是

A.系統(tǒng)調(diào)用B.外部中斷C.進(jìn)程切換D.缺頁

24.中斷處理和子程序調(diào)用都須要壓棧以愛護(hù)現(xiàn)場,中斷處理確定會保存而子程序調(diào)用不須要保存其內(nèi)容的是

A.程序計數(shù)器B.程序狀態(tài)字寄存器

C.通用數(shù)據(jù)寄存器D.通用地址寄存器

25.下列關(guān)于虛擬存儲器的敘述中，正確的是

A.虛擬存儲只能基于連續(xù)安排技術(shù)B.虛擬存儲只能基于非連續(xù)安排技術(shù)

C.虛擬存儲容量只受外存容量的限制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個進(jìn)程P0、Pl、P2、P3、P4共享三類資源RI、R2、R3,這些資源總數(shù)分別為18、6、22。T0時刻的

資源安排狀況如下表所示，此時存在的一個平安序列是

5

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

已安排資源資源最大需求

進(jìn)程

R1R2R3R1R2R3

P03235510

P1403536

P24054011

P3204425

P4314424

A.P0,P2,P4,Pl,P3B.Pl,P0,P3,P4,P2

C.P2,Pl,P0,P3,P4D.P3,P4,P2,Pl,P0

28.若一個用戶進(jìn)程通過read系統(tǒng)調(diào)用讀取一個磁盤文件中的數(shù)據(jù)，則下列關(guān)于此過程的敘述中，正確的是

I.若該文件的數(shù)據(jù)不在內(nèi)存，則該進(jìn)程進(jìn)入睡眠等待狀態(tài)

H.懇求read系統(tǒng)調(diào)用會導(dǎo)致CPU從用戶態(tài)切換到核心態(tài)

III.read系統(tǒng)調(diào)用的參數(shù)應(yīng)包含文件的名稱

A.僅I、IIB.僅LIIIC.僅IhHID.I、II和III

29.一個多道批處理系統(tǒng)中僅有P1和P2兩個作業(yè)，P2比P1晚5ms到達(dá)，它的計算和I/O操作依次如下:

P1：計算60ms,I/O80ms,計算20ms

P2：計算120ms,I/O40ms,計算40ms

若不考慮調(diào)度和切換時間，則完成兩個作業(yè)須要的時間最少是

A.240msB.260msC.340msD.360ms

30.若某單處理器多進(jìn)程系統(tǒng)中有多個就緒態(tài)進(jìn)程，則下列關(guān)于處理機(jī)調(diào)度的敘述中錯誤的是

A.在進(jìn)程結(jié)束時能進(jìn)行處理機(jī)調(diào)度

B.創(chuàng)建新進(jìn)程后能進(jìn)行處理機(jī)調(diào)度

C.在進(jìn)程處于臨界區(qū)時不能進(jìn)行處理機(jī)調(diào)度

D.在系統(tǒng)調(diào)用完成并返回用戶態(tài)時能進(jìn)行處理機(jī)調(diào)度

31.下列關(guān)于進(jìn)程和線程的敘述中，正確的是

A.不管系統(tǒng)是否支持線程，進(jìn)程都是資源安排的基本單位

B.線程是資源安排的基本單位，進(jìn)程是調(diào)度的基本單位

C.系統(tǒng)級線程和用戶級線程的切換都須要內(nèi)核的支持

D.同一進(jìn)程中的各個線程擁有各自不同的地址空間

32.下列選項中，不能改善磁盤設(shè)備I/O性能的是

6

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

A.重排I/O懇求次序B.在一個磁盤上設(shè)置多個分區(qū)

C.預(yù)讀和滯后寫D.優(yōu)化文件物理的分布

33.在TCP/IP體系結(jié)構(gòu)中,干脆為ICMP供應(yīng)服務(wù)協(xié)議的是

A.PPPB.IPC.UDPD.TCP

34.在物理層接口特性中，用于描述完成每種功能的事務(wù)發(fā)生依次的是

A.機(jī)械特性B.功能特性C.過程特性D.電氣特性

35.以太網(wǎng)的MAC協(xié)議供應(yīng)的是

A.無連接的不行靠的服務(wù)B.無連接的牢靠的服務(wù)

C.有連接的牢靠的服務(wù)D.有連接的不行靠的服務(wù)

36.兩臺主機(jī)之間的數(shù)據(jù)鏈路層采納后退N幀協(xié)議（GBN）傳輸數(shù)據(jù)數(shù)據(jù)傳輸速率為16kbps,單向傳播時延為270ms,

數(shù)據(jù)幀長度范圍是128~512字節(jié)，接收方總是以與數(shù)據(jù)幀等長的幀進(jìn)行確認(rèn)。為使信道利用率達(dá)到最高，幀序列的

比特數(shù)至少為

A.5B.4C.3D.2

37.下列關(guān)于IP路由器功能的描述中，正確的是

1.運(yùn)行路由協(xié)議，設(shè)備路由表

n.監(jiān)測到擁塞時，合理丟棄IP分組

IH.對收到的IP分組頭進(jìn)行差錯校驗，確保傳輸?shù)腎P分組不丟失

IV.依據(jù)收到的IP分組的目的IP地址，將其轉(zhuǎn)發(fā)到合適的輸出線路上

A.僅1ILIVB.僅I、II、IIIC.僅I、11、IVD.LII、山、IV

38.ARP協(xié)議的功能是

A.依據(jù)IP地址查詢MAC地址B.依據(jù)MAC地址查詢IP地址

C.依據(jù)域名查詢IP地址D.依據(jù)IP地址查詢域名

39.某主機(jī)的IP地址為，子網(wǎng)掩碼為。若該主機(jī)向其所在子網(wǎng)發(fā)送廣播分組，則目的地

址可以是

40.若用戶1與用戶2之間發(fā)送和接收電子郵件的過程如下圖所示，則圖中①、②、③階段分別運(yùn)用的應(yīng)用層協(xié)議

可以是

7

2023年全國碩士探討生入學(xué)統(tǒng)一考試一計算機(jī)專業(yè)基礎(chǔ)綜合試題

用.戶1的用戶2的

如什赧務(wù)罵帥什正勢每月戶2

A.SMTP、SMTP、SMTPB.POP3、SMTP、POP3

C.POP3、SMTP、SMTPD.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ù)達(dá)到最小。

請問答下列問題。

（1）給出完整的合并過程，并求出最壞狀況下比較的總次數(shù)。

（2）依據(jù)你的合并過程，描述n（n>2）個不等長升序表的合并策略，并說明理由。

8

2023年全國碩士探討生入學(xué)統(tǒng)一考試T4■算機(jī)專業(yè)基礎(chǔ)綜合試題

42.(13分)假定采納帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間,

例如，"loading"和"being”的存儲映像如下圖所示。

strl

*om

str2

Jp

設(shè)strl和str2分別指向兩個單詞所在單鏈表的頭結(jié)點(diǎn)，鏈表結(jié)點(diǎn)結(jié)構(gòu)為data"請設(shè)計一個時間上盡

可能高效的算法，找出由strl和str2所指向兩個鏈表共同后綴的起始位置(如圖中字符i所在結(jié)點(diǎn)的位置p)。要求:

(1)給出算法的基本設(shè)計思想。

(2)依據(jù)設(shè)計思想，采納C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。

(3)說明你所設(shè)計算法的時間困難度。

9

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

43.（11分）假設(shè)某計算機(jī)的CPU主頻為80MHz,CPI為4,并且平均每條指令訪存1.5次，主存與Cache之間交

換的塊大小為16B,Cache的命中率為99%,存儲器總線寬度為32位。請回答下列問題。

（1）該計算機(jī)的MIPS數(shù)是多少？平均每秒Cache缺失的次數(shù)是多少？在不考慮DMA傳送的狀況下。主存帶寬至

少達(dá)到多少才能滿意CPU的訪存要求？

（2）假定在Cache缺失的狀況下訪問主存時，存在0.0005%的缺頁率，則CPU平均每秒產(chǎn)生多少次缺頁異樣？若

頁面大小為4KB,每次缺頁都須要訪問磁盤，訪問磁盤時DMA傳送采納周期挪用方式，磁盤I/O接口的數(shù)據(jù)緩沖

寄存器為32位，則磁盤I/O接口平均每秒發(fā)出的DMA懇求次數(shù)至少是多少？

（3）CPU和DMA限制器同時要求運(yùn)用存儲器總線時，哪個優(yōu)先級更高？為什么？

（4）為了提高性能，主存采納4體低位交叉存儲器，工作時每1/4周期啟動一個存儲體，每個存儲體傳送周期為

50ns,則主存能供應(yīng)的最大帶寬是多少？

44.（12分）某16位計算機(jī)中，帶符號整數(shù)用補(bǔ)碼表示，數(shù)據(jù)Cache和指令Cache分別。題44表給出了指令系統(tǒng)

中部分指令格式，其中Rs和Rd表示寄存器，mem表示存儲單元地址，（x）表示寄存器x或存儲單元x的內(nèi)容。

題44表指令系統(tǒng)中部分指令格式

名稱指令的匯編格式指令功能

加法指令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)

10

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

該計算機(jī)采納5段流水方式執(zhí)行指令，各流水段分別是取指（IF）、譯碼/讀寄存器（ID）、執(zhí)行/計算有效地

址（EX）、訪問存儲器（M）和結(jié)果寫回寄存器（WB）,流水線采納“按序放射，按序完成”方式，沒有采納轉(zhuǎn)發(fā)

技術(shù)處理數(shù)據(jù)相關(guān)，并且同一寄存器的讀和寫操作不能在同一個時鐘周期內(nèi)進(jìn)行。請回答下列問題。

（1）若int型變量x的值為-513,存放在寄存器R1中，則執(zhí)行“SHLR1”后，R1中的內(nèi)容是多少？（用十六進(jìn)制表

示）

（2）若在某個時間段中，有連續(xù)的4條指令進(jìn)入流水線，在其執(zhí)行過程中沒有發(fā)生任何堵塞，則執(zhí)行這4條指令

所需的時鐘周期數(shù)為多少？

（3）若高級語言程序中某賦值語句為x=a+b,x、a和b均為int型變量，它們的存儲單元地址分別表示為閔、［a］

和［b］。該語句對應(yīng)的指令序列及其在指令流中的執(zhí)行過程如題44圖所示。

11LOADRI,[a]

12LOADR2,[b]

13ADDRI,R2

14STORER2,[x]

時間田元

1234567891011121314

11IF10EXMWB

12IFIDEXMWB

13IFIDEXMWB

14IFIDEXMWB

題44圖指令序列及其執(zhí)行過程示意圖

則這4條指令執(zhí)行過程中13的ID段和14的IF段被堵塞的緣由各是什么？

（4）若高級語言程序中某賦值語句為x=x*2+a,x和a均為unsignedint類型變量，它們的存儲單元地址分別表示

為［x］、同，則執(zhí)行這條語句至少須要多少個時鐘周期？要求仿照題44圖畫出這條語句對應(yīng)的指令序列及其在流水

線中的執(zhí)行過程示意圖。

11

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

45.(7分)某懇求分頁系統(tǒng)的頁面置換策略如下：

從0時刻起先掃描，每隔5個時間單位掃描一輪駐留集(掃描時間忽視不計)且在本輪沒有被訪問過的頁

框?qū)⒈幌到y(tǒng)回收，并放入到空閑頁框鏈尾，其中內(nèi)容在下一次安排之前不清空。當(dāng)放發(fā)生缺頁時，假如該頁曾

被運(yùn)用過且還在空閑頁鏈表中，則重新放回進(jìn)程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁框。

忽視其它進(jìn)程的影響和系統(tǒng)開銷。初始時進(jìn)程駐留集為空。目前系統(tǒng)空閑頁的頁框號依次為32、15、21、41。

進(jìn)程P依次訪問的〈虛擬頁號，訪問時刻＞為＜1』＞、＜3,2＞、＜0,4＞、＜0,6＞、＜0,13＞、＜2,14＞?請回答下列問

題。

(1)當(dāng)虛擬頁為＜0,4＞時，對應(yīng)的頁框號是什么？

(2)當(dāng)虛擬頁為時，對應(yīng)的頁框號是什么？說明理由。

(3)當(dāng)虛擬頁為＜2,14＞時，對應(yīng)的頁框號是什么？說明理由。

(4)這種方法是否適合于時間局部性好的程序？說明理由。

12

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

46.(8分)某文件系統(tǒng)空間的最大容量為4TB(1TB=24O),以磁盤塊為基本安排單位。磁盤塊大小為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é)？為了使單個文件的長度達(dá)到最大，請指出起始塊號和塊數(shù)分別所占字節(jié)數(shù)的合理值并說明理

由。

47.(9分)主機(jī)H通過快速以太網(wǎng)連接Internet,IP地址為，服務(wù)器S的IP地址為。H與

S運(yùn)用TCP通信時，在H上捕獲的其中5個1P分組如題47-a表所示。

題47-a表

編號IP分組的前40字節(jié)內(nèi)容(十六進(jìn)制)

45000030019b40008006lde8c0a80008d3444750

1

0bd91388846b41c500000000700243805dbO0000

430000300000400031066e83d3444750cOa80008

2

1388Obd9eO599fef846b41c6701216dO37el0000

45000028019c40008006IdefcOa80008d3444750

3

0bd91388846b41c6eO599ffD50fO43802b320000

45000038019d40008006IddecOa80008d3444750

4

0bd91388846b41c6eO599ff050184380e6550000

45000028681140003106067ad3444750cOa80008

5

13880bd9eO599ff0846b41d6501016dO57d20000

回答下列問題。

(1)題47-a表中的1P分組中，哪幾個是由H發(fā)送的？哪幾個完成了TCP連接建立過程？哪幾個在通過快速

以太網(wǎng)傳輸時進(jìn)行了填充？

(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分組到達(dá)H時經(jīng)過了多

13

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

少個路由器？

題47-b表

來自S的分組45000028681140004006ecadd3444750ca760106

1388al08eO599ffO846b41d6501016dOb7d60000

注：/P分組頭和TCP段頭結(jié)構(gòu)分別如題47-a圖，題47-b圖所示。

題47-a圖IP分組頭結(jié)構(gòu)

題47-b圖TCP段頭結(jié)構(gòu)

14

2023年全國碩士探討生入學(xué)統(tǒng)一考試T4■算機(jī)專業(yè)基礎(chǔ)綜合試題

計算機(jī)專業(yè)基礎(chǔ)綜合試題參考答案

一、單項選擇題：每小題2分，共80分。

1-5BAABC6-10CCADA11-15DDBDD16-20ACCCD

21-25DBCBB26-30ADABC31-35ABBCA36-40BCADD

二、綜合應(yīng)用題：41-47小題，共70分。

41.【解析】

(1)對于長度分別為m,n的兩個有序表的合并過程，最壞狀況下須要始終比較到兩個表尾元素，比較次數(shù)為

m+n-1次。已知須要5次兩兩合并，故可設(shè)總比較次數(shù)為X-5,X就是以N個葉子結(jié)點(diǎn)表示升序表，以升序表的表

長表示結(jié)點(diǎn)權(quán)重，構(gòu)造的二叉樹的帶權(quán)路徑長度。故只需設(shè)計方案使得X最小。這樣受哈夫曼樹和最佳歸并樹思想

的啟發(fā)，設(shè)計哈夫曼樹如下：

395

這樣，最壞狀況下比較的總次數(shù)為：

N=(10+35)x4+(40+50+60)x3+200-5=825

(2)N(N22)個不等長升序表的合并策略：

以N個葉子結(jié)點(diǎn)表示升序表，以升序表的表長表示結(jié)點(diǎn)權(quán)重，構(gòu)造哈夫曼樹。合并時，從深度最大的結(jié)點(diǎn)所代

表的升序表起先合并，依深度次序始終進(jìn)行到根結(jié)點(diǎn)。

理由：N個有序表合并須要進(jìn)行N-1次兩兩合并，可設(shè)最壞狀況下的比較總次數(shù)為X-N+l,X就是以N個葉子

結(jié)點(diǎn)表示升序表，以升序表的表長表示結(jié)點(diǎn)權(quán)重，構(gòu)造的二叉樹的帶權(quán)路徑長度。依據(jù)哈夫曼樹的特點(diǎn)，上述設(shè)計

的比較次數(shù)是最小的。

42.【解析】

(1)算法思想：依次遍歷兩個鏈表到尾結(jié)點(diǎn)時，并不能保證兩個鏈表同時到達(dá)尾結(jié)點(diǎn)。這是因為兩個鏈表的

長度不同。假設(shè)一個鏈表比另一個鏈表長k個結(jié)點(diǎn)，我們先在長鏈表上遍歷k個結(jié)點(diǎn)，之后同步遍歷兩個鏈表。這

樣我們就能夠保證它們同時到達(dá)最終一個結(jié)點(diǎn)了。由于兩個鏈表從第一個公共結(jié)點(diǎn)到鏈表的尾結(jié)點(diǎn)都是重合的。所

以它們確定同時到達(dá)第一個公共結(jié)點(diǎn)。于是得到算法思路：

①遍歷兩個鏈表求的它們的長度LI,L2；

②比較LI,L2,找出較長的鏈表，并求L=|L1-L2|；

③先遍歷長鏈表的L各結(jié)點(diǎn)；

15

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

④同步遍歷兩個鏈表，直至找到相同結(jié)點(diǎn)或鏈表結(jié)束。

(2)算法的C語言代碼描述

LinkListSearch_First_Common(LinkListLI,LinkListL2){

//本算法實(shí)現(xiàn)線性時間內(nèi)找到兩個單鏈表的第一個公共結(jié)點(diǎn)

intlenl=Length(LI);,len2=Length(L2);

LinkListlongList,shortlist;//分別指向較長和較短的鏈表

if(lenl>len2){

longList=Ll->next;

shortlist=L2->next;

L=lenl-len2;〃表長之差

)

else{

longList=L2->next;

shortlist=Ll->next;

L=len2-lenl;〃表長之差

)

While(L-)

longList=longList->next;

while(longList!=NULL){

if(longList==shortList)//同步找尋共同結(jié)點(diǎn)

returnlongList;

else{

longList=longList->next;

shortlist=shortlist->next;

}

}//while

returnNULL;

)

(3)算法的時間困難度為O(lenl+len2),空間困難度為0(1)。

43.【解析】

(1)MIPS=CPU主頻xlO/CPI=8OM/4=2O；平均每條指令訪存1.5次,Cache的命中率為99%,故每秒Cache

缺失的次數(shù)=20Mxl.5xl%=300000(次)；

(2)在不運(yùn)用DMA傳送的狀況下，全部主存的存取操作都須要經(jīng)過CPU,所以主存帶寬至少應(yīng)為

20M/sxl.5x4B=120MB/s,

由于頁式虛擬存儲方式的頁表始終位于內(nèi)存，則產(chǎn)生缺頁異樣的只能是指令的訪存。每秒產(chǎn)生缺頁中斷

20M/sx1.5x0.0005%=150次。因此平均每秒發(fā)出的DMA懇求次數(shù)至少是150x4KB/4B=150K次。

(3)優(yōu)先響應(yīng)DMA懇求。DMA通常連接高速I/O設(shè)備，若不剛好處理可能丟失數(shù)據(jù)。

(4)當(dāng)4體低位交叉存儲器穩(wěn)定運(yùn)行時，能供應(yīng)的最大帶寬為4x4B/50ns=320MB/s。

44.【解析】

(1)x的機(jī)器碼為岡11011111B,即指令執(zhí)行前(RI)=FDFFH,右移1位后位1111111011111111B,

即指令執(zhí)行后(RI)=FEFFHo

(2)至少須要4+(5-1)=8個時鐘周期數(shù)。

(3)Is的ID段被堵塞的緣由：因為|3與11和h都存在數(shù)據(jù)相關(guān)，需等到11和|2將結(jié)果寫回寄存器后，13才能

16

2023年全國碩士探討生入學(xué)統(tǒng)一考試T算機(jī)專業(yè)基礎(chǔ)綜合試題

讀寄存器內(nèi)容，所以b的ID段被堵塞。

k的IF段被堵塞的緣由：因為k的前--條指令h在ID段被堵塞，所以h的IF段被堵塞。

(4)因2*x操作有左移和加法兩種實(shí)現(xiàn)方法，故x=x*2+a對應(yīng)的指令序列為

11LOADRI,岡

12LOADR2,[a]

13SHLRI〃或者ADDRI,R1

14ADDRI,R2

15STORER2,岡

這5條指令在流水線中執(zhí)行過程如下圖所示。

時間單元

指令1234567891011121314151617

11IFIDEXMWB

12IFIDEXMWB

13IFIDEXMWB

14