考研408計算機學科專業(yè)基礎綜合真題及答案

1、時間：二O二一年七月二十九日2019年全國碩士研究生招生考試之樊仲川億創(chuàng)作時間：二O二一年七月二十九日計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題一、單項選擇題：140小題，每小題2分，共80分.下列每題給出的 四個選項中，只有一個選項合適試題要求.設n是描述問題規(guī)模的非負整數(shù)，下列程序段的時間龐雜度是x=0;while(n=(x+l)*(x+l) x=x+l ;A. O(log n)B. O(n1/2)C. O(n)D. O(n2).若將一棵樹T轉化為對應的二又樹BT,則下列對BT的遍歷中，具遍歷序列與T的后根遍歷序列相同的是A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷.對n個互不

2、相同的符號進行哈夫曼編碼.若生成的哈夫曼樹共有115個結點，則n的值是A. 56 B. 57 C. 58 D. 60.在任意一棵非空平衡二又樹(AVL樹)T1中，刪除某結點v之后形成 平衡二又樹T2,再將w拔出T2形成平衡二又樹 T3.下列關于T1 與T3的敘述中，正確的是.若v是T1的葉結點，則T1與T3可能不相同H .若v不是T1的葉結點，則T1與T3一定不相同田.若v不是T1的葉結點，則T1與T3 一定相同、m需要的頂點個數(shù)至少A.僅 I B. 僅 II C. 僅 I、H D.僅、m需要的頂點個數(shù)至少.下圖所示的 AOE網暗示一項包含 8個活動的工程.活動d的最早開始時間和最遲開始時間辨

3、別是A. 3 和 7B. 12 和 12C. 12 和 14D. 15 和 15 6.用有向無環(huán)圖描述表達式(x+y)*(x+y)/x),是A. 5B. 6C. 8D. 9時間：二。二一年七月二十九日時間：二O二一年七月二十九日.選擇一個排序算法時，除算法的時空效率外，下列因素中，還需要考 慮的是A.僅 m B.僅 I、n C.僅 n、m、ivd. I 、n、m、w.現(xiàn)有長度為11且初始為空的散列表 HT,散列函數(shù)是H(key)=key%7, 采取線性探查(線性探測再散列)法解決沖突將關頭字序列87,40,30,6,11,22,98,20 依次拔出到 HT后,HT查找失敗的平均 查找長度是.設

4、主串 T= abaabaabcabaabC ,模式串S= abaabc，采取 KMP算法進行模式匹配，到匹配成功時為止，在匹配過程中進行的單 個字符間的比較次數(shù)是A. 9B. 10C. 12D. 1510.排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一 “趟”.下列序列中，不成能是快速排序第二趟結果的是A. 5,2,16,12,28,60,32,72B. 2,16,5,28,12,60,32,72C. 2,12,16,5,28,32,72,60D. 5,2,12,28,16,32,72,60.設外存上有120個初始歸并段，進行12路歸并時，為實現(xiàn)最佳歸 并，需要彌補的虛段個數(shù)是 A

5、. 1 B. 2 C. 3 D. 4.下列關于馮諾依曼結構計算機基本思想的敘述中，錯誤的是A.程序的功效都通過中央處理器執(zhí)行指令實現(xiàn)B.指令和數(shù)據(jù)都用二進制暗示，形式上無不同C.指令按地址拜訪，數(shù)據(jù)都在指令中直接給出D.程序執(zhí)行前，指令和數(shù)據(jù)需預先存放在存儲器中.考慮以下C語言代碼：unsigned short usi=65535;short si=usi ；執(zhí)行上述程序段后,si的值是A. -1 B. -32767 C. -32768 D. -65535.下列關于缺頁處理的敘述中，錯誤的是A.缺頁是在地址轉換時 CPU僉測到的一種異常B.缺頁處理由操縱系統(tǒng)提供的缺頁處理程序來完成C.缺頁處理

6、程序按照頁毛病地址從外存讀入所缺失的頁D.缺頁處理完成后回到產生缺頁的指令的下一條指令執(zhí)行時間：二O二一年七月二十九日時間：二O二一年七月二十九日.某計算機采取大端方法，按字節(jié)編址.某指令中操縱數(shù)的機器數(shù)為1234 FF00H,該操縱數(shù)采取基址尋址方法，形式地址(用補碼暗 示)為FF12H,基址寄存器內容為F000 0000H,則該操縱數(shù)的LSB(最低有效字節(jié))所在的地址是A. F000 FF12H B. F000 FF15H C. EFFF FF12H D. EFFFFF15H.下列有關處理器時鐘脈沖信號的敘述中，錯誤的是A.時鐘脈沖信號由機器脈沖源收回的脈沖信號經整形和分頻后 形成B.時鐘

7、脈沖信號的寬度稱為時鐘周期，時鐘周期的倒數(shù)為機器主頻C.時鐘周期以相鄰狀態(tài)單元間組合邏輯電路的最大延遲為基準 確定D.處理器總是在每來一個時鐘脈沖信號時就開始執(zhí)行一條新的 指令.某指令功效為 Rr2 Rr1+MRr0,其兩個源操縱數(shù)辨別采取寄存器、寄存器間接尋址方法.對于下列給定部件，該指令在取 數(shù)及執(zhí)行過程中需要用到的是I.通用寄存器組(GPRs)H .算術邏輯單元(ALU)(ID)m C.僅 n、m(ID)m C.僅 n、m、 IV D. 僅訪存、寫回” 5段流水線的處s0、s1、s2、s3 和 t2 暗示寄Rs1+Rs0MRt2+0Rs2+Rs3Rs2和 I4 D. I3 和 I4A.僅

8、 I、H B.僅 I、H、I、田、IV.在采取“取指、譯碼/取數(shù)、執(zhí)行、 理器中，執(zhí)行如下指令序列，其中 存器編號.I1 : add s2,s1,s0/Rs2I2 : load s3,0(t2)/Rs3I3 : add s2,s2 s3 /Rs2I4 : store s2,0 (t2)/MRt2+0下列指令對中，不存在數(shù)據(jù)冒險的是A. I1 和 I3 B. I2 和 I3 C. I2.假定一臺計算機采取3通道存儲器總線，配套的內存條型號為DDR3-1333,即內存條所接插的存儲器總線的任務頻率為 1333MHz總線寬度為64位，則存儲器總線的總帶寬大約是時間：二O二一年七月二十九日時間：二O二

9、一年七月二十九日A. 10.66 GB/s B. 32 GB/s C. 64 GB/s D. 96 GB/s.下列關于磁盤存儲器的敘述中，錯誤的是A.磁盤的格局化容量比非格局化容量小B.扇區(qū)中包含數(shù)據(jù)、地址和校驗等信息C.磁盤存儲器的最小讀寫單位為一個字節(jié)D.磁盤存儲器由磁盤控制器、磁盤驅動器和盤片組成.某設備以中斷方法與 CPU進行數(shù)據(jù)交換，CPU主頻為1 GHz,設備 接口中的數(shù)據(jù)緩沖寄存器為32位，設備的數(shù)據(jù)傳輸率為 50kB/s.若每次中斷開銷（包含中斷響應和中斷處理）為1000個時鐘周期 則CPU用于該設備輸入/輸出的時間占整個 CPU時間的百分比最 多是A. 1.25%B. 2.5

10、%C. 5%D. 12. 5%.下列關于DM防法的敘述中，正確的是DMA傳送前由設備驅動程序設置傳送參數(shù)m.數(shù)據(jù)傳送由DMA空制器直接控制總線完成A.僅 I、n B.僅 I、m、iv C.僅 n、m、 ivd. I 、n、田、 IV.下列關于線程的描述中，錯誤的是A.內核級線程的調度由操縱系統(tǒng)完成B.操縱系統(tǒng)為每個用戶級線程建立一個線程控制塊C.用戶級線程間的切換比內核級線程間的切換效率高D.用戶級線程可以在不支持內核級線程的操縱系統(tǒng)上實現(xiàn).下列選項中，可能將進程喚醒的事件是o結束n .某進程退出臨界區(qū)田.當前進程的時間片用完A.僅 舊.僅mC.僅I、n d. I、n、田.下列關于系統(tǒng)調用的敘

11、述中，正確的是I.在執(zhí)行系統(tǒng)調用辦事程序的過程中 ，CPU處于內核態(tài) n.操縱系統(tǒng)通過提供系統(tǒng)調用避免用戶程序直接拜訪外設 m.不合的操縱系統(tǒng)為應用程序提供了統(tǒng)一的系統(tǒng)調用接口A.僅 I、IV B. 僅 II、IIIC. 僅 I、n、IVD.僅 I、田、 IV.下列選項中，可用于文件系統(tǒng)辦理空閑磁盤塊的數(shù)據(jù)結構是時間：二O二一年七月二十九日時間：二O二一年七月二十九日I.位圖n .索引節(jié)點出.空閑磁盤塊鏈IV .文件分派表（FAT） A.僅 I、n B.僅 I、m、iv C.僅 1、m D. 僅 n、 田、IV.系統(tǒng)采取二級反應隊列調度算法進行進程調度.就緒隊列Q1采取時間片輪轉調度算法，時間

12、片為10ms;就緒隊列 Q2采取短進程 優(yōu)先調度算法；系統(tǒng)優(yōu)先調度Q1隊列中的進程，當Q1為空時系統(tǒng)才會調度 Q2中的進程；新創(chuàng)建的進程首先進入Q1; Q1中的進程執(zhí)行一個時間片后，若未結束，則轉入Q2.若當前Qt Q2為 空，系統(tǒng)依次創(chuàng)建進程 Pl、P2后即開始進程調度 Pl、P2需要的 CPU時間辨別為30ms和20ms,則進程P1、P2在系統(tǒng)中的平均等 待時間為A. 25 msB. 20 msC. 15 msD. 10 ms.在分段存儲辦理系統(tǒng)中，用同享段表描述所有被同享的段.若進程P1和P2同享段S,下列敘述中，錯誤的是 A.在物理內存中僅保管一份段S的內容B.段S在P1和P2中應該具

13、有相同的段號P1和P2同享段S在同享段表中的段表項P1和P2都不再使用段S時才回收段S所占的內存空間.某系統(tǒng)采取LRU頁置換算法和局部置換戰(zhàn)略，若系統(tǒng)為進程 P預 分派了 4個頁框，進程P拜訪頁號的序列為 0,1,2,7,0,5,3,5,0,2,7,6,則進程拜訪上述頁的過程中，產生頁置換的總次數(shù)是A. 3 B. 4 C. 5 D. 6.下列關于死鎖的敘述中，正確的是IV.當系統(tǒng)出現(xiàn)死鎖時,必定有兩個或兩個以上的進程處于阻塞 態(tài)A.僅 II、m B. 僅 I、n、iv C.僅 I、n、m D. 僅 I、 田、IV.某計算機主存按字節(jié)編址，采取二級分頁存儲辦理，地址結構如 下所示頁目錄號（10位

14、）頁號（10位）頁內偏移（12位）虛擬地址20501225H對應的頁目錄號、頁號辨別是時間：二O二一年七月二十九日時間：二O二一年七月二十九日A. 081H、101HB. 081H、401HC. 201H、101HD. 201H、401H.在下列動態(tài)分區(qū)分派算法中，最容易產生內存碎片的是A.首次適應算法B.最壞適應算法C.最佳適應算法D.循環(huán)首 次適應算法. OSI參考模型的第5層(自下而上)完成的主要功效是A.錯誤控制B.路由選擇C.會話辦理D.數(shù)據(jù)暗示轉換A.雙絞線B.單模光纖C.多模光纖D.同軸電纜.對于滑動窗口協(xié)議，如果分組序號采取 3比特編號，發(fā)送窗口大小 為5,則接收窗口最大是A.

15、 2B. 3C. 4D. 5.假設一個采取 CSMA/C助議的100Mbps局域網，最小幀長是128B, 則在一個沖突域內兩個站點之間的單向傳播延時最多是A. 2.56 psB. 5.12 sC. 10.24 sD. 20.48 八.若將101.200.16.0/20 劃分為5個子網，則可能的最小子網的可 分派IP地址數(shù)是A. 126B. 254C. 510D. 1022.某客戶通過一個 TCP連接向辦事器發(fā)送 數(shù)據(jù)的部分過程如題 38圖所示.客戶在 t0時刻第一次收到確認序列號 ack_seq=100的段，并發(fā)送序列號 seq=100的段，但產生丟失.若TCP支持 快速重傳，則客戶重新發(fā)送

16、seq=100段 的時刻是A. t1B. t2C. t3D. t4.若主機甲主動倡議一個與主機乙的TCP連接，甲、乙選擇的初始序列號辨別為 2018和2046,則第三次握手 TCP段的 確認序列號是A. 2018B. 2019C. 2046D. 2047.下列關于網絡應用模型的敘述中，錯誤的是 A.在P2P模型中，結點之間具有對等關系 B.在客戶/辦事器(C/S)模型中，客戶與客戶之間可以直接通信 C.在C/S模型中，主動倡議通信的是客戶，主動通信的是辦事器時間：二O二一年七月二十九日時間：二O二一年七月二十九日D,在向多用戶分發(fā)一個文件時，P2P模型通常比C/S模型所需時 間短二、綜合應用題

17、：4147小題，共70分.(13 分)設線性表 L=(a1,a2,a,an -2,a-1,a.)采取帶頭結點的單鏈表保管，鏈表中結點定義如下：typedef struct node int data ;struct node*next ； NODE;請設計一個空間龐雜度為 O(1)且時間上盡可能高效的算法，重新 排列L中的各結點，得到線性表L=(a1,an,a2,an-1,a3,an-2).要求：(1)給出算法的基本設計思想(2)按照設計思想，采取C或C+錯言描述算法，關頭之處給出注 釋.(3)說明你所設計的算法的時間龐雜度.(10分)請設計一個隊列，要求滿足：初始時隊列為空；入隊 時，允許增

18、加隊列占用空間；出隊后，出隊元素所占用的空間可重復使用，即整個隊列所占用的空間只增不減；人隊操縱和 出隊操縱的時間龐雜度始終堅持為O(1).請回答下列問題： TOC o 1-5 h z (1)該隊列應該選擇鏈式存儲結構，還是順序存儲結構？ (2)畫出隊列的初始狀態(tài)，并給出判斷隊空和隊滿的條件 (3)畫出第一個元素入隊后的隊列狀態(tài).(4)給出入隊操縱和出隊操縱的基本過程.(8分)有n(n n 3)位哲學家圍坐在一張圓桌邊，每位哲學家交替地就餐和思考.在圓桌中心有 m(m 1)個碗，每兩位哲學家之間有1根筷子.每位哲學家必須取到一個碗和兩側的筷子之后，才干就餐，進餐完畢，將碗和筷子放回原位，并繼續(xù)

19、思考.為使盡可能多 的哲學家同時就餐，且避免出現(xiàn)死鎖現(xiàn)象，請使用信號量的P、V操縱(wait() 、signal()操縱)描述上述過程中的互斥與同步，并說明所用信號量及初值的含義.(7分)某計算機系統(tǒng)中的磁盤有300個柱面，每個柱面有10個磁道，每個磁道有200個扇區(qū)，扇區(qū)大小為512B.文件系統(tǒng)的每個簇 包含2個扇區(qū).請回答下列問題：時間：二O二一年七月二十九日時間：二O二一年七月二十九日(1)磁盤的容量是多少？(2)假設磁頭在85號柱面上，此時有4個磁盤拜訪請求，簇號辨別 為：100260、60005、101660和110560.若采取最短尋道時 間優(yōu)先(SSTF)調度算法，則系統(tǒng)拜訪簇的

20、先后次序是什么？(3)第100530簇在磁盤上的物理地址是什么？將簇號轉換成磁盤 物理地址的過程是由I/O系統(tǒng)的什么程序完成的？.(16 分)已知 f(n)=n ! =nx (n -l) x (n - 2) x x 2x 1，計算 f(n)的 C語言函數(shù)fl的源程序(陰影部分)及其在32位計算機M上的部 分機器級代碼如下：其中，機器級代碼行包含行號、虛擬地址、機器指令和匯編指令，計算機M按字節(jié)編址，int型數(shù)據(jù)占32位.請回答下列問題： (1)計算f(10)需要調用函數(shù)f1多少次？執(zhí)行哪條指令會遞歸調 用f1 ?(2)上述代碼中，哪條指令是條件轉移指令？哪幾條指令一定會使 程序跳轉執(zhí)行？(3)

21、按照第16行call指令，第17行指令的虛擬地址應是多少？ 已知第16行call指令采取相對尋址方法，該指令中的偏移 量應是多少(給出計算過程)?已知第16行call指令的后4 字節(jié)為偏移量，M采取大端還是小端方法？f(13)=6227020800,但 f1(13)的前往值為 1932053504,為什么兩者不相等？要使f1(13)能前往正確的結果，應如何修改f1 源程序？(5)第19行imuleax,ecx暗示有符號數(shù)乘法，乘數(shù)為 Reax和Recx,當乘法器輸出的高、低 32位乘積之間滿足什么條件 時，溢出標記 OF=1?要使CPU在產生溢出時轉異常處理，編 譯器應在imul指令后加一條什

22、么指令？.(7分)對于題45,若計算機M的主存地址為32位，采取分頁存儲 辦理方法，頁大小為4KB,則第1行push指令和第30行ret指令 是否在同一頁中(說明理由)？若指令Cache有64行，采取4路組 相聯(lián)映射方法，主存塊大小為 64B,則32位主存地址中，哪幾位暗 示塊內地址？哪兒位暗示Cache組號？哪幾位暗示標識表記標幟(tag)信息？讀取第16行call指令時，只可能在指令 Cache的哪 一組中命中(說明理由)?.(9分)某網絡拓撲如題47圖所示，其中R為路由器，主機H1H4的時間：二O二一年七月二十九日時間：二O二一年七月二十九日IP地址配置以及 R的各接口 IP地址配置如圖

23、中所示.現(xiàn)有若干臺 以太網交換機(無VLAN功效)和路由器兩類網絡互連設備可供選 擇.請回答下列問題：(1)設備1、設備2和設備3辨別應選擇什么類型網絡設備？(2)設備1、設備2和設備3中，哪幾個設備的接口需要配置IP地址？并為對應的接口配置正確的IP地址.(3)為確保主機H1H4能夠于訪Internet,R 需要提供什么辦事？ 若主機H3發(fā)送一個目的地址為192.168.1.127的IP數(shù)據(jù)報,網絡中哪幾個主機會接收該數(shù)據(jù)報？2019年全國碩士研究生招生考試計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題參考答案、單項選擇題二、綜合應用題41、單項選擇題二、綜合應用題41.【答案要點】(1

24、)算法的基本設計思想：算法分3步完成.第1步，采取兩個指針交替前行，找到單鏈表的中間結點；第 2步,將單鏈表的后半段結點原地逆置；第3步，從單鏈表前后兩段中依次各取一個結點，按要求重排.(2)算法實現(xiàn)：串心rd rk由n臚屏|( MtSDI * li )NUDE * p4 * q, * r, *p 1whit ( 丁.! = NLUJ： )/ 尋找中間睛點jp -;/F9少nrH1 = N II J. s.hi- q I , NULL相械我口干門說打 r -fieXl =;pm E qsq = F? 狂Ff is 指 I訶 Wif ffl 的翔十收(KiJiPL 即插人世q = p ibrxt

25、 ； 4瓶IAi單的第十就據(jù)站以p-iw*Ai = NL LL：( q ! = HULL )將近裘埼牛股的母以M A利指定位:置1 = i ，/41指向后校的下一1T穌器 加 /轎i|所掰結以新人計3所特 精點;A3Xlrhl - “1 =”，瓶同|月爺門的下一f 八總q ,“(3)算法的時間龐雜度：參考答案的時間龐雜度為O(n).42.【答案要點】(1)采取鏈式存儲結構(兩段式單向循環(huán)鏈表), 隊頭指針為front,隊尾指針為rear.(2)初始時，創(chuàng)建只有一個空閑結點的兩段式 單向循環(huán)鏈表，頭指針front與尾指針rear均指時間：二O二一年七月二十九日時間：二O二一年七月二十九日向空閑結

26、點.如下圖所示人區(qū)押作;隊空的判定條件：front=rear.隊滿的判定條件： front=rear-next.(3)拔出第一個元素后的隊列狀態(tài)：向空閑結點.如下圖所示人區(qū)押作;隊空的判定條件：front=rear.隊滿的判定條件： front=rear-next.(3)拔出第一個元素后的隊列狀態(tài)：操縱的基本過程:磯作rsrJfr闈插入一個新的空閑排電；I大限比席維？1f到 mf所慚結點和；- rt*Li惜N |更回1 _,排作工若ikwrt - prtr)/隊審網出隊久收,送也h. J 所脩結也中的兀索Bjnmk =*Z*踞目ca.【答案要點】信號量semaphore bowl； 用于協(xié)調哲

27、學家對碗的使用semaphore chopsticksn ； / 用于協(xié)調哲學家對筷子的使用for(int i=0 ; in ; i+)chopsticksi.value=1 ; / 設置兩個哲學家之間筷子的數(shù)量bowl.value=min(n-1,m) ; /bowl.value-i1,確保不死鎖CoBeginwhile(True)/哲學家i的程序思考；P(bowl)； 取碗P(chopsticksi) ; / 取左邊筷子P(chopsticks(i+l)MODn) ; / 取右邊筷子就餐；V(chopsticksi);V(chopsticks(i+1)MODn);V(bowl);CoEnd

28、.【答案要點】 磁 盤 容 量二(300 X 10X 200X 512/1024)KB=3 X 105K B(2)依次拜訪的簇是 100 260、101 660、110 560、60 005.(3)第100 530簇在磁盤上的物理地址由其所 在的柱面號、磁頭號、扇區(qū)號組成其 所 在 的 柱 面 號 為 ? 100530/(10 X 200/2? =100.100530%(10X 200/2)=530, 磁 頭號為 ? 530/(200/2) ? =5.扇區(qū)號為(530 X 2)%200=60.將簇號轉換成磁盤物理地址的過程由磁盤驅 動程序完成.【答案要點】(1)計算f(l0)需要調用函數(shù)f1共10次執(zhí)行第 16行call指令會遞歸調用f1.(2)第12行jle指令是條件轉移指令.第16行 call指令、第20行jmp指令、第30行ret指 令一定會使程序跳轉執(zhí)行.(3)第16行call指令的下一條指令的地址為 0040 1