2021年全國碩士研究生入學統(tǒng)一考試計算機科學與技術學科聯(lián)考

2021年全國碩士研究生招生考試 55計算帕學科專業(yè)基礎試題 皂一、單項選擇題：1-40小題，每小題2分，共80分。下列每題給 fb的四個選項中｀只有一個選項是最符合題目要求的。_l.已知頭指針h指向一個帶頭結點的非空單循環(huán)鏈表，結點結構為_二，其中nefit是指向直桵后繼結點的指針，p是尾指針，q是臨時指針?，F(xiàn)要刪除該鏈表的第一個元素，正確的語句序列是h->nefil=h->next->nexl; q=h->next; free(q);q=h->next; h->next=h->next->next; fiee(q);q=t; t=->nex; i(p!=qp=h; fe);q)p=h;q=h->next; q)p=h;Q‘'u2?lSgsD'slSgQ‘'u2?lSgsD'slSgsl',2s4.AC．．D已知二維數(shù)組A按行優(yōu)先方式存儲，每個元素占川l個存儲單．．D若元素[OJO]10,A[3][3]的存儲地址是220.則元素A[5][5]的存儲地川奾IL300A.IL300.301 ，某森林F對應的二義樹為'/''若?的先忭迪歷序列是a.h.d、c.e,，f,中序地歷序列是I,,d,IIA.1,t!,g,C:,f,中序地歷序列是I,,d,IIA.1B.一·.3 D.4二叉樹有個葉，其權（八分別為1,162,30,則其最第1／18頁小的帶權路徑長度(?'PL)小的帶權路徑長度(?'PL)C.208T入關鍵字2C.208T入關鍵字23后，根中的關鍵字是給定平衡二叉樹如下圖所示，抇16C.23

B.20-}一56-}一562全生考和專礎ACB.2AC第2／18頁A.26,3,14,6 n.25,3,I4,6 57C.21,3,14,6 D.15,3,14,69.在一棵高度為3的3階B樹中，根為第1層，若笫2層中有4個關鍵字，則該樹的結點個數(shù)最多是A.11C.A.11C.9D.810.設數(shù)組S[]=j93,946,3729,J46,151301,485,236327,43,892!,采用最低位優(yōu)先(LSD)基數(shù)排序將S排列成升序序列。第l趟分配、收集后，元素372之前、之后緊鄰的元素分別是A.43,892 B.236,301C.301,892 D.485301將關鍵字6,9,1,5,8,4,7依次插入到初始為空的大根堆H中，得到的H是A.9,8,7,6,5,4,19,8,7,5,6,4,1

B.9,8,7,5,6,1,4D.9,6,7,5,8,4,1B.9.3xJ0B.9.3xJ015次A9.3x1013次I3.已知帶符號整數(shù)川補碼表示，變隊．｀、y、z的機器數(shù)分別為FFFDFFFDfl、FFDFH、7FFCH,下列結論中，正確的是若x、y和z為無符號整數(shù)，則z<x<y若x、y和z<'}孕z若x、y和z為帶符號整數(shù)，則x<y<z若x、y和z為帶符號整數(shù)，則y<x<z14下列數(shù)伯中，不能川IEEE754浮點格式粘確表示的是0.1.25第3／18頁15.某計算機的存儲器總線中有24位地址15.某計算機的存儲器總線中有24位地址線和32位數(shù)據(jù)線，按字編若000000HFFFFH為RAM區(qū)，則需要址，字長為32位。512fix8位的RAM芯片數(shù)為A.8è.32若計貨機主存地址為32位，按字節(jié)編址，Cache數(shù)據(jù)區(qū)大小為32KB.32B,采川直桵映射方式和回寫(W百teBack)策略，則Cache行的位數(shù)至少是A.275

274D.25758-58-02》士生考試計科算專業(yè)大綱I.指令寄存器 II.微指令寄存器m.基址寄存器 N.標志／狀態(tài)寄存器下列關于數(shù)據(jù)通路的敘述中，錯誤的是數(shù)據(jù)通路包含ALU等組合邏輯（操作）元件數(shù)據(jù)通路包含寄存器等時序邏輯（狀態(tài)）元件數(shù)據(jù)通路不包含用于異楷串件檢測及響應的電路數(shù)機通路中的數(shù)據(jù)流動路徑山，控制伈號進行控制下列關于總線的敘述中，估誤的是總線是在兩個或多個部件之間進行數(shù)趴交換的傳愉介質同步總線山時鐘估勺定時，時鐘肋沖不一定等于工作頻率異步總線由腥手伈號定時，一次lht手過和完成一位數(shù)據(jù)交換突發(fā)(Burst)傳送總線串務可以在總線上迕紋傳送多個數(shù)剿下列選項中，不屈于1/0拔口的是0.打印機適配器第4／18頁D.可編程中斷控制器一c.D.可編程中斷控制器一異常事件在當前指令執(zhí)行過程中進行檢測，中斷誚求則在當前指入執(zhí)行后進行檢測。下列事件中，相應處理程序執(zhí)行后，必須匝到當前指令重新執(zhí)行的是D.打印機缺紙下列是關于多重中斷系統(tǒng)中CPU響應中斷的敘述，其中錯誤D.打印機缺紙的是的是僅在用戶態(tài)（執(zhí)行用戶程序）下，CPU才能檢測和響應中斷CP只有在檢測到中斷請求信號后，才會進入中斷響應周期c.進入中斷響應周期時，CPU定處于中斷允許（開中斷）狀態(tài)D.若P測到中斷請求信號，則一定存在未被屏蔽的中斷源請求信號請求信號下列指令中，只能在內核態(tài)執(zhí)行的是C.數(shù)據(jù)傳送指令 D.設置斷點指令下列操作中，操作系統(tǒng)在創(chuàng)建新進程時，必須完成的是I.II.皿設置進程狀態(tài)為執(zhí)行態(tài){又I.皿 D.、mIV.進程阻塞隊列下列內核的數(shù)據(jù)結構或程序中，分時系統(tǒng)實現(xiàn)時間片輪轉調度需要使用的是IV.進程阻塞隊列II.進程控制塊m.進程就緒隊列進程控制塊C.僅I、Il、m

n.時鐘中斷處理程序..僅I、Il、W某系統(tǒng)中磁盤的磁道數(shù)為2000199)磁頭當前在184號磁道第5／18頁上。上。川戶進程捉出的磁盤訪問誚求對應的磁迫號依次為184、187、17?、182、1FF。若采川服短尋迫時間優(yōu)先冊度符法(SfiTF)宅成磁盤訪問，則磁頭移動的臥商（磁迫數(shù)）是ì.41A.37 B.ì.41D.D.42下列咑件中，可能引起進程調度和序執(zhí)行的是I.中斷處理結束m進程執(zhí)行結束I.中斷處理結束

N.進程的時間片用兀II.進程陽塞D. I、IIm和WII.進程陽塞某詰求分頁存儲系統(tǒng)的頁大小為4KB,按字節(jié)編址。系統(tǒng)給進程P分配2個固定的頁框，并采用改進型Clock置換算法，進程P頁表的部分內容如下表所示。頁號 頁框號

存在位 訪問位 修改位60志202全國生?；鵌:存在，0:60志202全國生專基o 。 ... ．．．o 。 。20H。234 l80fl I I L．．． ... ...若P訪問虛擬地址為02AOIH的存儲t)t元，則經地址變換后得到的物理地址見B.B.IIC.J0AOIH D.80AO111在采川二級頁表的分頁系統(tǒng)中，CPU頁表拈址寄存監(jiān)中的內容是當前進程的一級頁表的起始f.l?擬地址第6／18頁c.當前進程的c.當前進程的二級頁表的起始虛擬地址D.當前進程的二級頁表的起始物理地址錄dir下有文件file錄dir下有文件file1,則為刪除該文件內核不必完成的工作是刪除file1的快捷方寸釋放file1的文件控制塊釋放file1占用的磁盤空間刪除目錄dir中與fi1e1對應的目錄項A.2若系統(tǒng)中有11(11?2個進程，每個進程均需要使用某類臨界資源2個，則系統(tǒng)不會發(fā)生死鎖所需的該類資源總數(shù)至少是A.2nn+I

2n下列選項中，通過系統(tǒng)調用完成的操作是頁置換D.生成隨機整數(shù)在TCP/IP參考模型中，由傳輸層相鄰的下一層實現(xiàn)的主要功能是能是C.端到端報文段傳輸 D.結點到結點流獄控制若下圖為一段差分曼徹斯特編碼估號波形，則其編碼的二進制位串是B.110I000l第7／18頁C.00IO11I0 D.10110110現(xiàn)將個JP網(wǎng)絡劃分為3個子網(wǎng)，若其中個子網(wǎng)是28/26,則下列網(wǎng)絡中，不可能是另外兩個子網(wǎng)之的是A./25

B./2662＿試業(yè)基究生計算士研若路由器向MTU=800B的鏈路轉發(fā)一個總長度為162＿試業(yè)基究生計算士研A.796,0 B.796,I.8000 D.800,1某網(wǎng)絡中的所有路由器均采用距離向批路由算法計算路由。若路由器E與鄰居路由器A、B、C和D之間的直接鏈路距離分別是8、IO、12和6,且E收到鄰居路由器的距離向量如下表所示，則路由器E更新后的到達目的網(wǎng)絡NellNet4的距離分別是目的網(wǎng)絡A的距離向盤B的距離向耳C的距離向扯D的距離向扭NetLl22Net212353028Net3241630824A.9,IO,12,6B.9,IO,28,20C.9,20,12,20D.9,20,28,20Net4若客戶首先向服務器發(fā)送NTP迕接，則當客戶收到服務器發(fā)送的FIN段并向服務器發(fā)送了ACK段后，客戶的Net4CLOSE_WAIT J.TME_/AlTD.FIN_WAIT_2若大小為12B的應用層數(shù)據(jù)分別通過1個UDP數(shù)據(jù)報和1個第8／18頁TCP段傳輸，則該UDP數(shù)據(jù)報和TCP段實現(xiàn)的有效載荷（應用 63B.B.37.5%,37.5%D.P0.0%37.5%云數(shù)據(jù)）最大傳輸效率分別是A.37.5%1?.7%C.?0.,17%假設主機甲通過TCP向主機乙發(fā)送數(shù)據(jù)，部分過和如下圖所7八o甲在I。時刻發(fā)送了一個序號se云數(shù)據(jù)）最大傳輸效率分別是A.37.5%1?.7%C.?0.,17%?carcvwnd500?caI。三B數(shù)據(jù)seq6ake=50rvw今B11A.501-1000C.701-1000

B.601-1100D.801-1100?二、綜合應用題：?(15分）已知無向迕汕I冬IC山頂從u \I和邊從E組成、1￡1>0、蘭G中度為奇數(shù)的頂點個數(shù)為不大于2的aij數(shù)時、C存在包含所H邊且長度為I1·徑稱為:悄徑）（、設圖（，、采川仙，類朋定義從III、:typfidefstiufiInum?tc尤s,111111I·s;／／圖中實際的頂點數(shù)和邊婁rVeitict!sifit[V];／／頂點表。 MAXV為已定義常正第9／18頁intEdge[MAXY][MAXY];IMGraIMGraph;計法：ntLrh),判斷G是否存在EL路徑，若存在，則返回I0。要求：(I)給出算法的基本設計思想。根據(jù)設計思想，采用C或C++語言描述符法，關鍵之處給出注釋。說明你所設計算法的時間復雜度和空間復雜度。(8分）已知某排序算法如下：*count;íoidcmpCountSort(inta[],intb[],intn)int1*count;count=(int*)allocszeo(in)*n;newint[n];for(i=O;i<n;i++)for(i=i<nl;i+)frj=i+l;j<n+)elseb[coun=a[;[elseb[coun=a[;count;for(i=O;i<n;i++count;｝請回答下列問題。(I)若有inta[]I25IO,25IO,cmpCountfiort(ab,P)后數(shù)組h中的內容是什么？

則調用6464202該算法是穩(wěn)定的嗎？若是，則闡述理山；否則，修改為穩(wěn)定排第10／18頁(15分）假定計算機M16位，按字節(jié)編址，連接CPU和主存的系統(tǒng)總線中地址線為20位、數(shù)據(jù)線為8位，采用16位定長指令字，指令格式及其說明如下：格式 6位 2位2位2位 4位 指令功能或指令類型說明R刑I1JIJ

000000 rs rt rdoplop2 rs rt 1mmopltfirget

[]冬-[]opI[t]含ALU運算、條件轉移和訪存操作3類指令PC的低10target其中，oplop3為操作碼，rs、rt和rd為通用寄存器編號，Rr]表示寄存器r的內容，imm為立即數(shù)，target為轉移目標的形式地址。請回答下列問題。(I)ALU的寬度是多少位？可尋址主存空間大小為多少字節(jié)？(MAR)和主存數(shù)據(jù)寄存器(MDR分別應有多少位？R型格式最多可定義多少種操作?I型和J型格式總共最多可定義多少種操作？通用寄存器最多有多少個？假op]00100011時，分別表示帶符號整數(shù)減法和帶符號整數(shù)乘法指令，則指令0182H的功能是什么（參考上述指令功能說明的格式進行描述）？若1、2、3中前內容分為130521-1、1、0020H.則分別執(zhí)行指令0182H和0183H后，3號通川寄存器內容各是什么？各自結果是否溢出？(4)若采用1型格式的訪存指令中imm(偏移員）為帶符號整數(shù)，則地址計算時應對imm進行零擴展還是符號擴展？(5)無條件轉移指令可以采用上述哪種指令格式？(8分）假設計算機M24位，按字節(jié)編址；采用分頁第11／18頁304KB;Tfiil2路組相聯(lián)方式和LRU替換策略，共8組。祔回答下列問題。(1)徘擬地址中哪幾位表示虛頁號？哪幾位表示頁內地址？已知訪問TLB時加頁號高位部分用作TLil標記，低位部分用作TLB組號，M的虛擬地址中哪幾位是TLB標記？哪幾組號？TLB初始時為空，訪問的虛頁號依次為IO、12、167、26、4、1220,在此過程中，哪一個虛頁號對應的TLB表項被替換？說明理由。M32TLB表項的位數(shù)增加幾位？增加幾位？(7分）下表給出了整型信號量S的wait()和signal()操作的功能描述，以及采用開／關中斷指令實現(xiàn)信號扭操作互斥的兩種方法。功能描述方法l方法23emapkore3;3emapkore3;3emapkore3;(Ifiait(3lI3c=l;關中斷；關中斷；，｝fikile(3c=0l;開中斷；關中斷；II開中斷；開中斷；開中斷；I6666202究大綱3=33=3+$·I S=3+I，開中斷；開中斷；I 第12／18頁

I=3cI;=3cI;fi訥回答下列問題。 67皂一(I)為什么在wait()和signal()操作中對信號批S的訪問必須互皂一(2)分別說明方法l和方法2是否正確。 若不正確，誚說明理山。(3)用戶程序能否使用開／關中斷指令實現(xiàn)臨界區(qū)互斥？為 (8分）某計貨機用硬盤作為啟動盤，硬盤第一個扇區(qū)存放主引導記錄，其中包含磁盤引導程序和分區(qū)表。磁盤引導程序用于選擇要引導哪個分區(qū)的操作系統(tǒng)，分區(qū)表記錄硬盤上各分區(qū)的位置等描述信息。硬盤被劃分成若干個分區(qū)，每個分區(qū)的第一個扇區(qū)存放分區(qū)引導程序，用于引導該分區(qū)中的操作系統(tǒng)。系統(tǒng)采用多階段引導方式，除了執(zhí)行磁盤引導程序和分區(qū)引導程序外，還需要執(zhí)行ROM中的引導程序。請回答下列問題。 系統(tǒng)啟動過程中操作系統(tǒng)的初始化程序、分區(qū)引導程序、ROM中的引導程序、磁盤引導程序的執(zhí)行順序是什么？把硬盤制作為啟動盤時，需要完成操作系統(tǒng)的安裝、磁盤的物理格式化、邏輯格式化、對磁盤進行分區(qū)，執(zhí)行這4個操作的正確順序是什么？磁盤扇區(qū)的劃分和文件系統(tǒng)根目錄的建立分別是在第(2)問的哪個操作中完成的？ (9分）某網(wǎng)絡拓撲如題47圖所示，以太網(wǎng)交換機S通過路由器R與Internet互聯(lián)。路山湍部分倓口、本地域名服務器、Hl、H2的IP地址和MAC地址如圖中所示。在I。時刻HI的AR?表和SH1在此刻利川瀏覽器通過域名請求訪問fieb服務器，在lI時刻(tI>t。)S第一次收到了封裝HITP誚求報文的以太網(wǎng)幀，假設從t。到tI期間網(wǎng)絡未發(fā)生任何與此次Web訪問無關的網(wǎng)絡通信。第13／18頁R子InternetR子m器ole5?5192.168.1.l/25m器ole5?5本地域名服務器26/2500-11-22-33-44-bb.

192.168.I.3/2500-11-22-33-44-dd/2500-11-22-33-44-cc題47圖請回答下列問題。ttI期間，Hl除了HTTP之外還運行了哪個應用層協(xié)議？從應用層到數(shù)據(jù)鏈路層，該應用層協(xié)議報文是通過哪些協(xié)議進行逐層封裝的？換若S<MAC，則II時刻表的內容是什么？換丿火t。到tI期間，H2

·少會儀收到兒個與此次\Vfib訪問相關68＿68＿綱的幀？桵收到的見什么幀？幀的目的MAC地址是什么？的幀？桵收到的見什么幀？幀的目的MAC地址是什么？第14／18頁2021年全國碩士研究生招生考試S92021年全國碩士研究生招生考試5.B計算機學科專業(yè)基礎試題參考答案 皂5.B1.1.D6.D2.2.D7.A

8.9.A19.C3.B8.9.A19.CCC11.B12.D13.D14.A15.C16.A17.D18.C2fl.A21.B22.A23.B24.B25.C26.C27.D28.C29.B30.A1.C32.C33.B34.A36.B37.D38.B39.D40.C二、綜合應用題二、綜合應用題35.B算法的基本設計思想35.B對于采用鄰接矩陣存儲的無向圖，鄰接矩陣每一行（列）中非零元素的個數(shù)為本行（列）可以依次計算連通圖G中各頂點的度，并記錄度為奇數(shù)的頂點個數(shù)，若個1'否則返回0。(2)算法實現(xiàn)r"tlsEzrTtEL(MCrn;flC)／／采用鄰拔矩I作存儲，判斷圖是否存在WL路徑r"tn×?r××,r,j,c+""t=D;hur(r=0;rc”."?mv?ilr???;r++)h?sj=;jc."?mi;j+.II依次計貨各個頂點的度.II依次計貨各個頂點的度第15／18頁j];j];ff!=0)／／對度為奇數(shù)的頂點計數(shù)count++;count++;if(count==0II count==2)／／不存在EL路／／不存在EL路徑，返回O

return1;returnO;

／／存在EL路徑，返回l(3)算法的時間復雜度和空間復雜度本參考答案給出的算法的時間復雜度是O(n2),空間復雜度C1)b[J=l-1o,1o,11,19,25,25I元素之間的比較次數(shù)是n(n-l)/2。不是。需要將程序中的if語句修改如下：[)cunt[j]+;elseou[(I)ALU的寬度為16位。可尋址主存空間大小為2:,0字節(jié)（或1Mil。存拙、M16位、2位和8位。IOIJ1型和JIOIJ0IB1=0000000IR[R[l]-H[2]。002[=B052l1-0008H=B04AH結果不溢出；執(zhí)行指令0113311后，R[3]=R[I]x第16／18頁R[2]=R[2]=B052H結果溢出。x應對imm進行符號擴展。(5)無條件轉移指令可以采用J30-12=18位表示虛頁號。12位表示頁內4KB=30-12=18位表示虛頁號。12位表示頁內地址。TLB28=23組，所以虛擬地址（或虛頁號）18-3=15TLB