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

2019年考研408計

算機學科專業(yè)基礎綜

合真題及答案

2019年全國碩士研究生招生考試

計算機科學與技術學科聯考

計算機學科專業(yè)基礎綜合試題一、單項選擇題：1~40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項符合試題要求。1.設n是描述問題規(guī)模的非負整數，下列程序段的時間復雜度是1.x=0；while(n>=(x+l)*(x+l))x=x+l；A.O(logn)B.O(n1/2)C.O(n)D.O(n2)2.若將一棵樹T轉化為對應的二又樹BT，則下列對BT的遍歷中，其遍歷序列與T的后根遍歷序列相同的是2.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷3.4.5.6.A.56B.57C.58D.60在任意一棵非空平衡二又樹(AVL3.4.5.6.A.56B.57C.58D.60在任意一棵非空平衡二又樹(AVL樹)L中，刪除某結點v之后形成平衡二又樹T2，再將w插入T2形成平衡二又樹T3。下列關于T1與丁3的敘述中I.若v是L的葉結點，則L與T3可能不相同II.若v不是L的葉結點，則T1與T3一定不相同III.若v不是L的葉結點，則T1與T3一定相同A.僅IB.僅II下圖所示的AOE網表示一項包含8個活動的工程。活動d的最早開始時間和最遲開始時間分別是A.3和7B.12和12C.12和14D.15和15用有向無環(huán)圖描述表達式(x+y)*((x+y)/x)，需要的頂點個數至少是1313C.僅I、II正確的是7.8.9.7.8.9.A.5B.6C.8D.9選擇一個排序算法時，除算法的時空效率外，下列因素中，還需要考慮的是數據的規(guī)模II.數據的存儲方式III.算法的穩(wěn)定性V.數據的初始狀態(tài)A.僅IB.僅I、IIC.僅II、III、IVD.I、II、III、W現有長度為11且初始為空的散列表HT,散列函數是H(key)=key%7，采用線性探查(線性探測再散列)法解決沖突將關鍵字序列87,40，30，6，11，22，98，20依次插入到HT后，HT查找失敗的平均查找長度是A.4B.5.25C.6D.6.29設主串T="abaabaabcabaabc”，模式串S="abaabc”，采用KMP算法進行模式匹配，到匹配成功時為止，在匹配過程中進行的單個字符間的比較次數是A.9B.10C.12D.15排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一“趟”。下列序列中，不可能是快速排序第二趟結果的是A.9A.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路歸并時，為實現最佳歸并，需要補充的虛段個數是

1B.2C.3D.4下列關于馮?諾依曼結構計算機基本思想的敘述中，錯誤的是A?程序的功能都通過中央處理器執(zhí)行指令實現指令和數據都用二進制表示，形式上無差別指令按地址訪問，數據都在指令中直接給出程序執(zhí)行前，指令和數據需預先存放在存儲器中考慮以下C語言代碼：unsignedshortusi=65535；shortsi=usi；執(zhí)行上述程序段后，si的值是A.-1B.-32767C.-32768D.-65535下列關于缺頁處理的敘述中，錯誤的是缺頁是在地址轉換時CPU檢測到的一種異常缺頁處理由操作系統(tǒng)提供的缺頁處理程序來完成缺頁處理程序根據頁故障地址從外存讀入所缺失的頁缺頁處理完成后回到發(fā)生缺頁的指令的下一條指令執(zhí)行某計算機采用大端方式，按字節(jié)編址。某指令中操作數的機器數為1234FF00H，該操作數采用基址尋址方式，形式地址(用補碼表示)為FF12H，基址寄存器內容為F0000000H，則該操作數的LSB(最低有效字節(jié))所在的地址是A.F000FF12HB.F000FF15HC.EFFFFF12HD.EFFFFF15H下列有關處理器時鐘脈沖信號的敘述中，錯誤的是時鐘脈沖信號由機器脈沖源發(fā)出的脈沖信號經整形和分頻后形成時鐘脈沖信號的寬度稱為時鐘周期，時鐘周期的倒數為機器主頻時鐘周期以相鄰狀態(tài)單元間組合邏輯電路的最大延遲為基準確定處理器總是在每來一個時鐘脈沖信號時就開始執(zhí)行一條新的指令17.某指令功能為R[r2]-R[r1]+M[R[r0]]，其兩個源操作數分別采用寄存器、寄存器間接尋址方式。對于下列給定部件，該指令在取數及執(zhí)行過程中需要用到的是I.通用寄存器組(GPRs)II.算術邏輯單元(ALU)存儲器(Memory)W.指令譯碼器(ID)A.僅I、IIB.僅I、II、IIIC.僅II、III、IVD.僅I、III、W在采用“取指、譯碼/取數、執(zhí)行、訪存、寫回”5段流水線的處理器中，執(zhí)行如下指令序列，其中s0、s1、s2、I1：add列，其中s0、s1、s2、I1：adds2，s1，s0I2：loads3，0(t2)I3：adds2，s2s3I4：stores2，0(t2)s3和t2表示寄存器編號//R[s2]—R[s1]+R[s0]//R[s3]—M[R[t2]+0]//R[s2]—R[s2]+R[s3]//M[R[t2]+0]—R[s2]下列指令對中，不存在數據冒險的是A.I1和I3B.I2和I3C.I2和I4D.I3和I4假定一臺計算機采用3通道存儲器總線，配套的內存條型號為DDR3-1333，即內存條所接插的存儲器總線的工作頻率為1333MHz、總線寬度為64位，則存儲器總線的總帶寬大約A.10.66GB/sB.32GB/sC.64GB/sD.96GB/s下列關于磁盤存儲器的敘述中，錯誤的是磁盤的格式化容量比非格式化容量小

扇區(qū)中包含數據、地址和校驗等信息磁盤存儲器的最小讀寫單位為一個字節(jié)磁盤存儲器由磁盤控制器、磁盤驅動器和盤片組成某設備以中斷方式與CPU進行數據交換，CPU主頻為1GHz，設備接口中的數據緩沖寄存器為32位，設備的數據傳輸率為50kB/s。若每次中斷開銷(包括中斷響應和中斷處理)為1000個時鐘周期，則CPU用于該設備輸入/輸出的時間占整個CPU時間的百分比最多是A.1.25%B.2.5%C.5%D.12.5%下列關于DMA方式的敘述中，正確的是DMA傳送前由設備驅動程序設置傳送參數數據傳送前由DMA控制器請求總線使用權數據傳送由DMA控制器直接控制總線完成DMA傳送結束后的處理由中斷服務程序完成A.僅I、IIB.僅I、III、WC.僅II、III、IVD.I、II、III、IV下列關于線程的描述中，錯誤的是內核級線程的調度由操作系統(tǒng)完成操作系統(tǒng)為每個用戶級線程建立一個線程控制塊C?用戶級線程間的切換比內核級線程間的切換效率高D.用戶級線程可以在不支持內核級線程的操作系統(tǒng)上實現I.當前進程的時間下列選項中，可能將進程喚醒的事件是I.當前進程的時間I.I/O結束II.某進程退出臨界區(qū)片用完A.僅IB.僅IC.僅I、IID.I、II、III下列關于系統(tǒng)調用的敘述中，正確的是在執(zhí)行系統(tǒng)調用服務程序的過程中，CPU處于內核態(tài)操作系統(tǒng)通過提供系統(tǒng)調用避免用戶程序直接訪問外設I.不同的操作系統(tǒng)為應用程序提供了統(tǒng)一的系統(tǒng)調用接口系統(tǒng)調用是操作系統(tǒng)內核為應用程序提供服務的接口A.僅I、IVB.僅II、IIIC.僅I、II、IVD.僅I、III、W下列選項中，可用于文件系統(tǒng)管理空閑磁盤塊的數據結構是I.位圖II.索引節(jié)點I.空閑磁盤塊鏈W.文件分配表(FAT)A.僅I、IIB.僅I、I、WC.僅l、ID.僅II、I、W系統(tǒng)采用二級反饋隊列調度算法進行進程調度。就緒隊列Q1采用時間片輪轉調度算法，時間片為10ms；就緒隊列Q2采用短進程優(yōu)先調度算法；系統(tǒng)優(yōu)先調度Q1隊列中的進程，當Q1為空時系統(tǒng)才會調度Q2中的進程；新創(chuàng)建的進程首先進入Q1；Q1中的進程執(zhí)行一個時間片后，若未結束，則轉入。2。若當前Q1、Q2為空，系統(tǒng)依次創(chuàng)建進程Pl、P2后即開始進程調度Pl、P2需要的CPU時間分別為30ms和20ms，則進程P1、P2在系統(tǒng)中的平均等待時間為A.25msB.20msC.15msD.10ms在分段存儲管理系統(tǒng)中，用共享段表描述所有被共享的段。若進程P1和P2共享段S,下列敘述中，錯誤的是在物理內存中僅保存一份段S的內容段S在P1和P2中應該具有相同的段號P1和P2共享段S在共享段表中的段表項P1和P2都不再使用段S時才回收段S所占的內存空間某系統(tǒng)采用LRU頁置換算法和局部置換策略，若系統(tǒng)為進程P預分配了4個頁框，進程P訪問頁號的序列為0，1，2，7，0，5，3，5，0，2，7，6，則進程訪問上述頁的過程中，產生頁置換的總次數是A.3B.4C.5D.6下列關于死鎖的敘述中，正確的是可以通過剝奪進程資源解除死鎖死鎖的預防方法能確保系統(tǒng)不發(fā)生死鎖銀行家算法可以判斷系統(tǒng)是否處于死鎖狀態(tài)W.當系統(tǒng)出現死鎖時，必然有兩個或兩個以上的進程處于阻塞態(tài)A.僅II、IIIB.僅I、II、WC.僅I、II、IIID.僅I、III、W某計算機主存按字節(jié)編址，采用二級分頁存儲管理，地址結構如下所示頁目錄號（10位）頁號（10位）頁內偏移（12位）虛擬地址20501225H對應的頁目錄號、頁號分別是A.081H、101HB.081H、401HC.201H、101HD.201H、401H在下列動態(tài)分區(qū)分配算法中，最容易產生內存碎片的是A.首次適應算法B.最壞適應算法C.最佳適應算法D.循環(huán)首次適應算法OSI參考模型的第5層（自下而上）完成的主要功能是A.差錯控制B.路由選擇C.會話管理D.數據表示轉換100BaseT快速以太網使用的導向傳輸介質是A.雙絞線B.單模光纖C.多模光纖D.同軸電纜對于滑動窗口協(xié)議，如果分組序號采用3比特編號，發(fā)送窗口大小為5,則接收窗口最大是A.2B.3C.4D.5假設一個采用CSMA/CD協(xié)議的100Mbps局域網，最小幀長是128B，則在一個沖突域內兩個站點之間的單向傳播延時最多是A.2.56psB.5.12psC.10.24psD.20.48ps若將101.200.16.0/20劃分為5個子網，則可能的最小子網的可分配IP地址數是A.126B.254C.510D.1022

a胸I:段超時題38圖時間■某客戶通過一個TCP連接向服務器發(fā)送數據的部分過程如題38圖所示?？蛻粼趖0時刻第一次收到確認序列號ack_seq=100的段，并發(fā)送序列號seq=100的段，但發(fā)生丟失。若TCP支持快速重傳，則客戶重新發(fā)送seq=100段的時刻是a胸I:段超時題38圖時間■A.t1B.t2C.t3D.t4若主機甲主動發(fā)起一個與主機乙的TCP連接，甲、乙選擇的初始序列號分別為2018和2046，則第三次握手TCP段的確認序列號是A.2018B.2019C.2046D.2047下列關于網絡應用模型的敘述中，錯誤的是A.在P2P模型中，結點之間具有對等關系B.在客戶/服務器(C/S)模型中，客戶與客戶之間可以直接通信在C/S模型中，主動發(fā)起通信的是客戶，被動通信的是服務器在向多用戶分發(fā)一個文件時，P2P模型通常比C/S模型所需時間短二、綜合應用題：41~47小題，共70分。(13分)設線性表L=(a1，a2,a...，an-2,a-1，a。)采用帶頭結點的單鏈表保存，鏈表中結點定義如下：typedefstructnode{intdata；structnode*next；}NODE；請設計一個空間復雜度為O(1)且時間上盡可能高效的算法，重新排列L中的各結點，得到線性表L'=(a1,an，a2，an1，a3，an2...)。要求：給出算法的基本設計思想根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。說明你所設計的算法的時間復雜度。(10分)請設計一個隊列，要求滿足：①初始時隊列為空；②入隊時，允許增加隊列占用空間；③出隊后，出隊元素所占用的空間可重復使用，即整個隊列所占用的空間只增不減；④人隊操作和出隊操作的時間復雜度始終保持為O(1)。請回答下列問題：該隊列應該選擇鏈式存儲結構，還是順序存儲結構？畫出隊列的初始狀態(tài)，并給出判斷隊空和隊滿的條件畫出第一個元素入隊后的隊列狀態(tài)。給出入隊操作和出隊操作的基本過程。(8分)有n(n>3)位哲學家圍坐在一張圓桌邊，每位哲學家交替地就餐和思考。在圓桌中心有m(m>1)個碗，每兩位哲學家之間有1根筷子。每位哲學家必須取到一個碗和兩側的筷子之后，才能就餐，進餐完畢，將碗和筷子放回原位，并繼續(xù)思考。為使盡可能多的哲學家同時就餐，且防止出現死鎖現象，請使用信號量的P、V操作(wait()、signal()操作)描述上述過程中的互斥與同步，并說明所用信號量及初值的含義。

(7分)某計算機系統(tǒng)中的磁盤有300個柱面，每個柱面有10個磁道，每個磁道有200個扇區(qū)，扇區(qū)大小為512B。文件系統(tǒng)的每個簇包含2個扇區(qū)。請回答下列問題：磁盤的容量是多少？假設磁頭在85號柱面上，此時有4個磁盤訪問請求，簇號分別為：100260、60005、101660和110560。若采用最短尋道時間優(yōu)先(SSTF)調度算法，則系統(tǒng)訪問簇的先后次序是什么？第100530簇在磁盤上的物理地址是什么？將簇號轉換成磁盤物理地址的過程是由I/O系統(tǒng)的什么程序完成的？45.(16分)已知f(n)=n！=nx(n-l)x(n-2)x???x2x1，計算f(n)的C語言函數fl的源程序(陰影部分)及其在32位計算機M上的部分機器級代碼如下:inLPl(inin)IL00401(KM837D08017E17IwruiK[Ml[pijp+8130040I01E140&WI02I15004010241600401025el5treturni；21837D08017E17IwruiK[Ml[pijp+8130040I01E140&WI02I15004010241600401025el5treturni；21O&4OIO35fffiJ7圖2600401044)IPtfe址192I郵I.伽留款M同美:rnues.L而中地址;11馳.岫由】莊梃6就隊網關:捋丸I斌L6519(N44IQ302()。削】也ifisJ.13&JXO.MX：191.168LLIPlfe*T9￡,l6H1.3i'26航認ll0040I01B/0040I01Cmurnra4f|(虛擬地址、機器指令和匯編指令，計算機M按字節(jié)編址，cingidwirind卜1.『ebp-*8]〔IjRfl+35h(00401055>30004(1104A其中，機器級代碼行包括行號、H(UU4UKXKIJmAh(0040103a)int型數據占32位。請回答下列問題:計算f(10)需要調用函數f1多少次？執(zhí)行哪條指令會遞歸調用f1？上述代碼中，哪條指令是條件轉移指令？哪幾條指令一定會使程序跳轉執(zhí)行？根據第16行call指令，第17行指令的虛擬地址應是多少？已知第16行call指令采用相對尋址方式，該指令中的偏移量應是多少(給出計算過程)？已知第16行call指令的后4字節(jié)為偏移量，M采用大端還是小端方式？f(13)=6227020800，但f1(13)的返回值為1932053504,為什么兩者不相等？要使f1(13)能返回正確的結果，應如何修改f1源程序？第19行imuleax,ecx表示有符號數乘法，乘數為R[eax]和R[ecx]，當乘法器輸出的高、低32位乘積之間滿足什么條件時，溢出標志OF=1？要使CPU在發(fā)生溢出時轉異常處理，編譯器應在imul指令后加一條什么指令？46.(7分)對于題45,若計算機M的主存地址為32位，采用分頁存儲管理方式，頁大小為4KB，則第1行push指令和第30行ret指令是否在同一頁中(說明理由)？若指令Cache有64行，采用4路組相聯映射方式，主存塊大小為64B，則32位主存地址中，哪幾位表示塊內地址？哪兒位表示Cache組號？哪幾位表示標記(tag)信息？讀取第16行call指令時，只可能在指令Cache的哪一組中命中(說明理由)？47.(9分)某網絡拓撲如題47圖所示，其中R為路由器，主機H1?H4的IP地址配置以及R的各接口IP地址配置如圖中所示?，F有若干臺以太網交換機(無VLAN功能)和路由器兩類網絡互連設備可供選擇。請回答下列問題：設備1、設備2和設備3分別應選擇什么類型網絡設備？設備1、設備2和設備3中，哪幾個設備的接口需要配置IP地址？并為對應的接口配置正確的IP地址。為確保主機H1?H4能夠訪問Internet，R需要提供什么服務？若主機H3發(fā)送一個目的地址為192.168.1.127的IP數據報，網絡中哪幾個主機會接收該數據報？一、單項選擇題B2.B5.C6.A7.D10.DB12.C15.D16.D17.B20.C21.A22.D25.C26.B27.C30.B31.A32.C35.B36.B37.B40.B2019年全國碩士研究生招生考試計算機科學與技術學科聯考計算機學科專業(yè)基礎綜合試題參考答案“=〃K怡|訕響十?恩的建-十數度納.成.3.C4.A8.C9.B13.A14.D18.C19.B23.B24.C28.B29.C33.C34.A38.C39.DCHWiA點//qUli"］后r沒的第一個敏據非疽=NULL：xhilf(q!-NULL)"將謎杰后宇粉的靖點拈入列指花伐置1=t|—；//rIJt向后華段的T"—於納或.^->nr-xl■=函；//將，所'Kf站戒插氏到m所指站點走后二、綜合應用題41.【答案要點】算法的基本設計思想：算法分3步完成。第1步，采用兩個指針交替前行，找到單鏈表的中間結點；第2步，將單鏈表的后半段結點原地逆置；第3步，從單鏈表前后兩段中依次各取一個結點，按要求重排。算法實現：voidcbangie.JifiHNODE*It)INODE*p,*qp*t.*士p=q=h?while!(!=NULL}//尋找中何結點(3)算法的時間復雜度：參考答案的時間復雜度為O(n)。42.【答案要點】采用鏈式存儲結構(兩段式單向循環(huán)鏈表)，隊頭指針為front，隊尾指針為rear。初始時，創(chuàng)建只有一個空閑結點的兩段式單向循環(huán)鏈表，頭指針front與尾指針rear均指向空閑結點。如下圖所示。隊空的判定條件：front==rear。隊滿的判定條件：front==rear->next。(3)插入第一個元素后的隊列狀態(tài)：q=q-；if〔q->nrsl!■NULLhi■曠”心i;//q走1明曲p=p-m偵//p走一步q=廣小網；〃p所指拮點為中何墻為后半段世戕p—Xi=while(q!=NULL)7/捋怯衷后平既逆斗p-Miexl=U=r；(4)操作的基本過程:大也操機；師在r^「ri?面桶人一個新的空陽缺點；人聯元矣促擊劇gr所梢結點中=IMTfI心u返回洋隊崖作.若〔front-=re-Hf)//險空蛔山眥欠敗.返回：取所指引點中佃元素hFreinI-；>n心上；返回ta43.【答案要點】〃信號量semaphorebowl；//用于協(xié)調哲學家對碗的使用semaphorechopsticks[n]；〃用于協(xié)調哲學家對筷子的使用for(inti=0；i<n；i++)chopsticks[i].value=1；//設置兩個哲學家之間筷子的數量bowl.value=min(n-1，m)；//bowl.valueWn-1,確保不死鎖CoBeginwhile(True)(〃哲學家i的程序思考；P(bowl)；//取碗P(chopsticks[i])；〃取.左邊筷子P(chopsticks[(i+l)MODn])；〃取右邊筷子就餐；(chopsticks[i])；(chopsticks[(i+1)MODn])；V(bowl)；}CoEnd【答案要點】磁盤容量=(300x10x200x512/1024)KB=3x105KB依次訪問的簇是100260、101660、110560、60005。第100530簇在磁盤上的物理地址由其所在的柱面號、磁頭號、扇區(qū)號構成其所在的柱面號為[100530/(10x200/2)[=100。100530%(10x200/2)=530,磁頭號為[530/(200/2)[=5。扇區(qū)號為(530x2)%200=60。將簇號轉換成磁盤物理地址的過程由磁盤驅動程序完成?！敬鸢敢c】計算f(l0)需要調用函數