2024年全國碩士探討生入學統(tǒng)一考試計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

計算機科學與技術學科聯(lián)考

計算機學科專業(yè)基礎綜合試題

（科目代碼408）

1

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

要求。

I.求整數n(nX))階乘的算法如下，其時間困難度是

intfact(intn)

{

if(n<=l)return1;

returnn*facl(n-1);

)

A.O(log2n)B.O(n)C.(nlog2n)D.O(n>)

2.已知操作符包括中、<、，*，、/、(和將中綴表達式a+b-a*((cd)/e-f)+g轉換為等價的后綴表達式ab+acd+e/f-*-g+

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

大個數是

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

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

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

4.若平衡二叉樹的高度為6,且全部豐葉結點的平衡因子均為1,則該平衡二叉樹的結點總數為

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

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

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

6.若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該圖拓撲序列的結論是

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

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

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

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

2

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

8.下列關于最小生成樹的說法中，正確的是

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

II.權值最小的邊確定會出現在全部的最小生成樹中

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

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

A.僅IR僅n「.僅I、niD.僅II、IV

9.設有一棵3階B樹，如下圖所示。刪除關鍵字78得到一棵新B樹，其最右葉結點所含的關鍵字是

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

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

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

I.簡潔先擇排序H.希爾排序in.快速排序iv堆排序v.二路歸并排序

A.僅kIlkIVB.僅I、IlkV

C.僅H、III、IVD.僅in、IV、V

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

A.排序的總趟數B.元素的移動次數

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

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

提高50%,I/O速度不變，則運行基準程序A所耗費的時間是

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

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

unsignedshortx=65530;

unsignedinty=x;

得到y(tǒng)的機器數為

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

A.00007FFAB.0000FFFAC.FFFF7FFAD.FFFFFFFA

14.float類型（即IEEE754單精度浮點數格式）能表示的最大正整數是

A.2126-2103B.2127-2lO?C.2127-2103D.2l28-2lO4

15.某計算機存儲器按字節(jié)編址，采納小端方式存放數據。假定編譯器規(guī)定int和short型長度分別為32位和16位,

并II.數據按動界對齊存儲。某C語言和序段如下：

struct（

inta;

charb;

shortc;

}record;

record.a=273;

若record變量的首地址為0Xc008,則低至0Xc008中內容及record.c的地址分別為

A.0x00.OxCOODB.0x00、OxCOOE

C.0x1KOxCOODD.0x1KOxCOOE

16.下列關于閃存（FlashMemory）的敘述中，錯誤的是

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

B.存儲元由MOS管組成，是一種半導體存儲器

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

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

17.假設某計算機按字編址，Cache有4個行，Cache和主存之間交換的塊為I個字。若Cache的內容初始為空，

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

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

18.某計算機的限制器采納微程序限制方式，微指令中的操作限制字段采納字段干脆編碼法，共有33個微吩咐，

構成5個互斥類，分別包含7、3、12、5和6個微吩咐，則操作限制字段至少有

A.5位B.6位C.15位D.33位

19.某同步總線的時鐘頻率為100MHz,寬度為32位,地址/數據線嵬用,每傳送一次地址或者數據占用一個時鐘

周期。若該總線支持突發(fā)（猝發(fā)）傳輸方式，則一次“主存寫”總線事務傳輸128位數據所須要的時間至少是

A.20nsB.40nsC.50nsD.80ns

20.下列關于USB總線特性的描述中，錯誤的是

4

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

A.可實現外設的即插即用和熱拔插

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

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

D.同時可傳輸2位數據，數據傳輸率高

21.下列選項中，在I/O總線的數據線上傳輸的信息包括

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

A.僅LIIB.僅LIIIC.僅ILIIID.kIRIII

22.響應外部中斷的過程中，中斷隱指令完成的操作,除愛護斷點外，還包括

I.關中斷H.保存通用寄存器的內容HL形成中斷服務程序入口地址并送PC

A.僅LIIB.僅LIIIC.僅II、IHD.LIRIII

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

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

24.中斷處理和子程序調用都須要壓棧以愛護現場,中斷處理確定會保存而子程序調用不須要保存其內容的是

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

C.通用數據寄存器D.通用地址寄存器

25.下列關于虛擬存儲器的敘述中，正確的是

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

C.虛擬存儲容量只受外存容量的限制D.虛擬存儲容量只受內存容量的限制

26.操作系的I/O子系統(tǒng)通常由四個層次組成，每一層明確定義了與鄰近層次的接口，其合理的層次組織排列依次

是

A.用戶級I/O軟件、設備無關軟件、設備驅動程序、中斷處理程序

B.用戶級I/O軟件、設備無關軟件、中斷處理程序、設備驅動程序

C.用戶級I/O軟件、設備驅動程序、設備無關軟件、中斷處理程序

D.用戶級I/O軟件、中斷處理程序、設備無關軟件、設備驅動程序

27.假設5個進程PO、Pl、P2、P3、P4共享三類資源RI、R2、R3,這些資源總數分別為18、6、22。TO時刻的

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

5

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

己安排資源資源最大需求

進程

R1R2R3RIR2R3

P03235510

P1403536

P24054011

P3204425

P43144一24

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

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

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

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

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

III.read系統(tǒng)調用的參數應包含文件的名稱

A.僅I、IIB.僅I、IIIC.僅ILIIID.I、II和III

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

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

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

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

A.240msB.26CiiisC.340msD.360ms

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

A.在進程結束時能進行處理機調度

B.創(chuàng)建新進程后能進行處理機調度

C.在進程處于臨界區(qū)時不能進行處理機調度

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

31.下列關于進程和線程的敘述中，正確的是

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

B,線程是資源安排的基本單位，進程是調度的基本單位

C.系統(tǒng)級線程和用戶級線程的切換都鄉(xiāng)更要內核的支持

D.同一進程中的各個線程擁有各自不同的地址空間

32.下列選項中，不能改善磁盤設備LO性能的是

6

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

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

33.在TCP/IP體系結構中,干脆為ICMP供應服務協(xié)議的是

A.PPPB.IPC.UDPD.TCP

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

A.機械特性B.功能特性C.過程特性D.電氣特性

35.以太網的MAC協(xié)議供應的是

A.無連接的不行靠的服務B.無連接的牢靠的服務

C.有連接的牢靠的服務D.有連接的不行靠的服務

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

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

比特數至少為

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

37.下列關于IP路由器功能的描述中.正確的是

I.運行路由協(xié)議，設備路由表

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

in.對收到的IP分組頭進行差錯校驗，確保傳輸的IP分組不丟失

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

A.僅III、IVB.僅I、【I、IIIC.僅I、II、IVD.I、【【、in、IV

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

A.依據IP地址查詢MAC地址B.依據MAC地址查詢IP地址

C.依據域名查詢IP地址D.依據IP地址查詢域名

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

址可以是

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

可以是

7

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

MF”的.用戶2的

卻什邛務器郵什與絳將

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

C.POP3、SMTP、SMTPD.SMTP.SMTP、POP3

二、綜合應用題：第41-47題，共70分。請將答案寫在答題紙指定位置上。

41.(1()分)設有6個有序表A、B、C、D、E、F,分別含有1()、35、40、50、60和200個數據元素，各表中元素

按升序排列。要求通過5次兩兩合并，將6個表最終合并成1個升序表，并在最壞狀況下比較的總次數達到最小。

請問答下列問題。

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

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

8

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

42.（13分）假定采納帶頭結點的單鏈表保存單詞，當兩個單詞有相同為后綴時，則可共享相同的后綴存儲空間,

例如，“l(fā)oading”和“being”的存儲映像如下圖所示。

stri

、rji->nT-<T

str2M-i-Hn>iii---------------------------?帔ng人

bep

Idatanext

設strl和str2分別指向兩個單詞所在單鏈表的頭結點，鏈表結點結構為，請設計一個時間上盡

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

（1）給出算法的基本設計思想。

（2）依據設計思想，采納C或C++或JAVA語言描述算法，關鍵之處給出注釋。

（3）說明你所設計算法的時間困難度。

9

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

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

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

少達到多少才能滿意CPU的訪存要求？

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

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

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

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

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

50ns,則主存能供應的最大帶寬是多少？

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

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

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

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

加法指令ADDRs,Rd(Rs)+(Rd)->Rd

算術/邏輯左移SHLRd2*(Rd)->Rd

算術右移SHRRd(Rd)/2->Rd

取數指令LOADRd,mem(mcm)->Rd

存數指令STORERs,memRs->(incin)

10

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

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

技術處理數據相關，并且同一寄存器的讀和寫操作不能在同一個時鐘周期內進行。請回答下列問題。

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

示）

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

所需的時鐘周期數為多少？

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

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

11LOADRI,lai

12LOADR2,[b]

13ADDRI,R2

14STORER2,岡

時間明元

1234567891011121314

nIFIDEXMWB

12IFIDEXMWB

13IF10EXMWB

14IF10EXMWB

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

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

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

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

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

11

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

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

框將被系統(tǒng)回收，并放入到空閑頁框鏈尾，其中內容在下一次安排之前不清空。當放發(fā)生缺頁時，假如該頁曾

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

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

進程P依次訪問的〈虛擬頁號，訪問時刻＞為＜3,2＞、＜0,4＞、＜0,6＞、＜0,13＞、＜2,l4＞o請回答下列問

題。

（1）當虛擬頁為＜0,4＞時，對應的頁框號是什么？

（2）當虛擬頁為＜1,11＞時，對應的頁框號是什么？說明理由。

（3）當虛擬頁為＜2,14＞時，對應的頁框號是什么？說明理由。

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

12

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

46.（8分）某文件系統(tǒng)空間的最大容量為4TB（lTB=2u））,以磁盤塊為基本安排單位。磁盤塊大小為1KB。文件控

制塊（FCB）包含一個512B的索引表區(qū)。請回答下列問題。

3）假設索引表區(qū)僅采納干脆索引結構，索引表區(qū)存放文件占用的磁盤塊號，索引表項中塊號最少占多少字節(jié)？

可支持的單個文件最大長度是多少字節(jié)？

（2）假設索引表區(qū)采納如下結構：第0~7字節(jié)采納〈起始塊號，塊數〉格式表示文件創(chuàng)建時預安排的連續(xù)存儲

空間。其中起始塊號占6B,塊數占2B,剩余504字節(jié)采納干脆索引結構，一個索引項占6B,則可支持的單個文件

最大長度是多少字節(jié)？為了使單個文件的長度達到最大，請指出起始塊號和塊數分別所占字節(jié)數的合理值并說明理

由°

47.（9分）主機H通過快速以太網連接Internet,IP地址為，服務器S的IP地址為。H與

S運用TCP通信時，在H上捕獲的其中5個IP分組如題47-a表所示。

題47-a表

編號IP分組的前40字節(jié)內容（十六進制）

45000030019b40008006lde8c0a80008d3444750

1

0bd91388846b41c500000000700243805dbO0000

430000300000400031066e83d3444750cOa80008

2

1388Obd9eO599fef846b41c6701216dO37el0000

45(X)(X)28()19c40(X)8006IdefcOa800()8d344475()

3

ObdO1388846b41c6eO59Of50fl)43802b320000

45000038019d40008006IddecOa80008d3444750

4

0bd91388846b41c6eO599ffD50184380e6550000

45000028681140003106067ad3444750cOa80008

5

13880bd9eO599fm846b41d650ID16dO57d2()000

回答下列問題。

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

以太網傳輸時進行了填充？

（2）依據題47-a表中的IP分組，分析S已經收到的應用層數據字節(jié)數是多少？

（3）若題47-a表中的某個IP分組在S發(fā)出時的前40字節(jié)如題47-b表所示，則該IP分組到ILH時經過了多

13

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

少個路由器?

題47-b表

來自S的分組45000028681140004006ecadd3444750ca760106

1388al08eO599ffO846b41d6501016dOb7d60000

注：/P分組頭和TCP段頭結構分別如題47m圖，題47-b圖所示中

II1IIIIIIIIIIIIi1IIIIIII11III

頭部

取本股務契型g長―

K次

懷心|

標識片偏移

tl7時間EL)杪設頭籌較總和

源IP地址

El的IPJftlt

題47-b圖TCP段頭結構

14

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

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

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

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

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

二、綜合應用題：41-47小題，共70分。

41.【解析】

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

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

長表示結點權重，構造的二叉樹的帶權路徑長度。故只需設計方案使得X最小。這樣受哈夫曼樹和最佳歸并樹思想

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

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

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

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

以N個葉子結點表示升序表，以外序表的表長表示結點權重，構造哈夫曼樹。合并時，從深度最大的結點所代

表的升序表起先合并，依深度次序始終進行到根結點。

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

結點表示升序表，以升序表的表長表示結點權重，構造的二叉樹的帶權路徑長度。依據哈夫尋樹的特點，上述設計

的比較次數是最小的。

42?【解析】

(I)算法思想：依次遍歷兩個鏈表到尾結點時，并不能保證兩個鏈表同時到達尾結點。這是因為兩個鏈表的

長度不同。假設一個鏈表比另一個鏈表長k個結點，我們先在長鏈表上遍歷k個結點，之后同步遍歷兩個鏈表。這

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

以它們確定同時到達第一個公共結點。于是得到算法思路：

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

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

③先遍歷長鏈表的L各結點；

15

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

④同步遍歷兩個鏈表，直至找到相同結點或鏈表結束。

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

LinkListSearch_First_Commor(LinkListLI,LinkListL2)(

//本算法實現線性時間內找到兩個單鏈表的第?個公共結點

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

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

if(lenl>len2){

longList=Ll->next;

short1ist=L2->next;

L=lenl-len2;//表長之差

)

else{

longList=L2->next;

short1ist=Ll->next;

L=len2-lenl;//表長之差

)

While(L-)

longList=longList->noxt;

while(longList!=NULL){

if(longList==shortList)//同步找尋共同結點

returnlongList;

else{

longList=longList->next;

short1ist=shortlist->next;

}

}//while

xtiLuxnNULL;

)

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

43?【解析】

(1)MIPS=CPU主頻xl()WCPI=80M/4=20；平均每條指令訪存1.5次,Cache的命中率為99%,故每秒Cache

缺失的次數=20MxI.5xl%=300000(次〕：

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

20M/sx|.5x4B=120MB/s.

由于頁式虛擬存儲方式的頁表始終位丁?內存，則產生缺頁異樣的只能是指令的訪存。每秒產生缺頁中斷

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

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

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

44.【解析】

(1)X的機器碼為岡林=111111011111B,即指令執(zhí)行前(RI)=FDFFH,右移1位后位1111111311111111B,

即指令執(zhí)行后(RD=FEFFH?

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

<3)13的ID段被堵塞的緣由：因為13與11和12都存在數據相關，需等到h和12將結果寫回寄存器后，13才能

16

2024年全國碩士探討生入學統(tǒng)一考試一計算機專業(yè)基礎綜合試題

讀寄存器內容，所以13的ID段被堵塞。

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

（4）因2*x操作有左移和加法兩種實現方法，故x=x*2+a對應的指令序列為

11LOADRI,[x]

12LOADR2,[a]

13SHLRI〃或者ADDRI,RI

14ADDRI,R2

ISSTORER2,[x]時間單元

指令1234567891011121314151617

ii5第旨令布航水純短技彳淞帶嫡理所示。

12IFIDEXMWB

13IFIDEXMWB

14