2019年考研408計算機學(xué)科專業(yè)基礎(chǔ)綜合真題及答案

2019年全國碩士研究生招生考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題一、單項選擇題:1~40小題,每小題2分,共80分。下列每題給出的四個選項中,只有一個選項符合試題要求。1、設(shè)n就是描述問題規(guī)模的非負(fù)整數(shù),下列程序段的時間復(fù)雜度就是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轉(zhuǎn)化為對應(yīng)的二又樹BT,則下列對BT的遍歷中,其遍歷序列與T的后根遍歷序列相同的就是A、先序遍歷3、對n個互不相同的符號進行哈夫曼編碼。若生成的哈夫曼樹共有115個結(jié)點,則n的值就是A、56B、57C、58D、60B、中序遍歷C、后序遍歷D、按層遍歷4、在任意一棵非空平衡二又樹(AVL樹)T1中,刪除某結(jié)點v之后形成平衡二又樹T2,再將w插入T2形成平衡二又樹T3。下列關(guān)于T1與T3的敘述中,正確的就是I、若v就是T1的葉結(jié)點,則T1與T3可不能相同Ⅱ、若v不就是T1的葉結(jié)點,則T1與T3一定不相同Ⅲ、若v不就是T1的葉結(jié)點,則T1與T一定相同3A、僅IB、僅IIC、僅I、ⅡD、僅I、Ⅲ5、下圖所示的AOE網(wǎng)表示一項包含8個活動的工程?；顒觗的最早開始時間與最遲開始時間分別就是6、用有向無環(huán)圖描述表達(dá)式(x+y)*((x+y)/x),需要的頂點個數(shù)至少就是A、5B、6C、8D、97、選擇一個排序算法時,除算法的時空效率外,下列因素中,還需要考慮的就是I、數(shù)據(jù)的規(guī)模A、僅ⅢⅡ、數(shù)據(jù)的存儲方式B、僅I、ⅡⅢ、算法的穩(wěn)定性V、數(shù)據(jù)的初始狀態(tài)C、僅Ⅱ、Ⅲ、IVD、I、Ⅱ、Ⅲ、Ⅳ8、現(xiàn)有長度為11且初始為空的散列表HT,散列函數(shù)就是H(key)=key%7,采用線性探查(線性探測再散列)法解決沖突將關(guān)鍵字序列87,40,30,6,11,22,98,20依次插入到HT后,HT查找失敗的平均查找長度就是A、4B、5、25C、6D、6、299、設(shè)主串T=“abaabaabcabaabc”,模式串S=“abaabc”,采用KMP算法進行模式匹配,到匹配成功時為止,在匹配過程中進行的單個字符間的比較次數(shù)就是A、9B、10C、12D、1510、排序過程中,對尚未確定最終位置的所有元素進行一遍處理稱為一“趟”。下列序列中,不可就能是快速排序第二趟結(jié)果的就是A、5,2,16,12,28,60,32,72C、2,12,16,5,28,32,72,60B、2,16,5,28,12,60,32,72D、5,2,12,28,16,32,72,6011、12、設(shè)外存上有120個初始?xì)w并段,進行12路歸并時,為實現(xiàn)最佳歸并,需要補充的虛段個數(shù)就是A、1B、2C、3D、4下列關(guān)于馮·諾依曼結(jié)構(gòu)計算機基本思想的敘述中,錯誤的就是A、程序的功能都通過中央處理器執(zhí)行指令實現(xiàn)B、指令與數(shù)據(jù)都用二進制表示,形式上無差別C、指令按地址訪問,數(shù)據(jù)都在指令中直接給出D、程序執(zhí)行前,指令與數(shù)據(jù)需預(yù)先存放在存儲器中考慮以下C語言代碼:13、unsignedshortusi=65535;shortsi=usi;執(zhí)行上述程序段后,si的值就是A、-1B、-32767C、-32768D、-6553514、下列關(guān)于缺頁處理的敘述中,錯誤的就是A、缺頁就是在地址轉(zhuǎn)換時CPU檢測到的一種異常B、缺頁處理由操作系統(tǒng)提供的缺頁處理程序來完成C、缺頁處理程序根據(jù)頁故障地址從外存讀入所缺失的頁D、缺頁處理完成后回到發(fā)生缺頁的指令的下一條指令執(zhí)行15、16、某計算機采用大端方式,按字節(jié)編址。某指令中操作數(shù)的機器數(shù)為1234FF00H,該操作數(shù)采用基址尋址方式,形式地址(用補碼表示)為FF12H,基址寄存器內(nèi)容為F0000000H,則該操作數(shù)的LSB(最低有效字節(jié))所在的地址就是A、F000FF12HB、F000FF15HC、EFFFFF12HD、EFFFFF15H下列有關(guān)處理器時鐘脈沖信號的敘述中,錯誤的就是A、時鐘脈沖信號由機器脈沖源發(fā)出的脈沖信號經(jīng)整形與分頻后形成B、時鐘脈沖信號的寬度稱為時鐘周期,時鐘周期的倒數(shù)為機器主頻C、時鐘周期以相鄰狀態(tài)單元間組合邏輯電路的最大延遲為基準(zhǔn)確定D、處理器總就是在每來一個時鐘脈沖信號時就開始執(zhí)行一條新的指令17、18、某指令功能為R[r2]←R[r1]+M[R[r0]],其兩個源操作數(shù)分別采用寄存器、寄存器間接尋址方式。對于下列給定部件I、通用寄存器組(GPRs)Ⅲ、存儲器(Memory),該指令在取數(shù)及執(zhí)行過程中需要用到的就是Ⅱ、算術(shù)邏輯單元(ALU)Ⅳ、指令譯碼器(ID)A、僅I、ⅡB、僅I、Ⅱ、ⅢC、僅ⅡD、僅I、Ⅲ、Ⅳ在采用“取指、譯碼/取數(shù)、執(zhí)行、訪存、寫回”5段流水線s2、s3與t2表示寄存器編號。、Ⅲ、IV的處理器中,執(zhí)行如下指令序列,其中s0、s1、I1:adds2,s1,s0I2:loads3,0(t2)I3:adds2,s2s3I4:stores2,0(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]下列指令對中,不存在數(shù)據(jù)冒險的就是A、I1與I3B、I2與I3一臺計算機采用3通道存儲器總線,配套的內(nèi)存條型號為DDR3-1333,即內(nèi)存條所接插的存儲器總線的工作頻率為1333MHz、總線寬度為64位,則存儲器總線的總帶寬大約就是C、64GB/sD、96GB/sC、I2與I4D、I3與I419、20、假定A、10、66GB/s下列關(guān)于磁盤B、32GB/s存儲器的敘述中,錯誤的就是A、磁盤B、扇區(qū)中包含C、磁盤存儲器的最小讀寫單位為一個字節(jié)D、磁盤存儲器由磁盤控制器、磁盤驅(qū)動器與盤片組成某設(shè)備以中斷方式與CPU進行數(shù)據(jù)交換,CPU主頻為1GHz,設(shè)備接口中的數(shù)據(jù)緩沖寄存器為32位,設(shè)備的數(shù)據(jù)傳輸率為50kB/s。若每次中斷開銷(包括中斷響應(yīng)與中斷處理)為1000個時鐘周期,則CPU用于該設(shè)備輸入/輸出的時間占整個CPU時間的百分比最多就是A、1、25%B、2、5%C、5%下列關(guān)于DMA方式的敘述中,正確的就是I、DMA傳送前由設(shè)備驅(qū)動程序設(shè)置傳送參II、數(shù)據(jù)傳送前由DMA控制器請求總線使用權(quán)的格式化容量比非格式化容量小數(shù)據(jù)、地址與校驗等信息21、22、D、12、5%數(shù)Ⅲ、數(shù)據(jù)傳送由DMA控制器直接控制總線完成IV、DMA傳送結(jié)束后的處理由中斷服務(wù)程序完成A、僅I、ⅡB、僅Ⅰ、Ⅲ、ⅣC、僅Ⅱ、Ⅲ、IVD、I、Ⅱ、Ⅲ、IV23、下列關(guān)于線程的描述中,錯誤的就是

A、內(nèi)核級線程的調(diào)度由操作系統(tǒng)完成B、操作系統(tǒng)為每個用戶級線程建立一個線程控制塊C、用戶級線程間的切換比內(nèi)核級線程間的切換效率高D、用戶級線程可以在不支持內(nèi)核級線程的操作系統(tǒng)上實現(xiàn)24、下列選項中,可能將進程喚醒的事件就是I、I/O結(jié)束A、僅IⅡ、B、僅Ⅲ某進程退出臨界區(qū)C、僅I、ⅡD、Ⅲ、當(dāng)前進程的時間片用完I、Ⅱ、Ⅲ25、下列關(guān)于系統(tǒng)調(diào)用的敘述中,正確的就是I、在執(zhí)行系統(tǒng)調(diào)用服務(wù)程序的過程中,CPU處于內(nèi)核態(tài)Ⅱ、操作系統(tǒng)通過提供系統(tǒng)調(diào)用避免用戶程序直接訪問外設(shè)Ⅲ、不同的操作系統(tǒng)為應(yīng)用程序提供了統(tǒng)一的系統(tǒng)調(diào)用接口IV、系統(tǒng)調(diào)用就是操作系統(tǒng)內(nèi)核為應(yīng)用程序提供服務(wù)的接口A、僅I、IV26、下列選項中,可用于文件系統(tǒng)管理空閑磁盤塊的數(shù)據(jù)結(jié)構(gòu)就是I、位圖Ⅱ、索引節(jié)點Ⅲ、空閑磁盤塊鏈Ⅳ、文件分配表(FAT)A、僅I、ⅡB、僅Ⅰ、Ⅲ、ⅣC、僅l、ⅢD、僅Ⅱ、Ⅲ、Ⅳ27、系統(tǒng)算法進行進程調(diào)度。就緒隊列Q1采用時間片輪轉(zhuǎn)調(diào)度算法,時間片為10ms;就緒隊列Q2采用短進程優(yōu)先調(diào)度算法;系統(tǒng)優(yōu)先調(diào)度Q1隊列中的進程,當(dāng)Q1為空時系統(tǒng)才會調(diào)度Q2中的進程;新創(chuàng)建的進程首先進入Q1;Q1中的進程執(zhí)行一個時間片后,若未結(jié)束,則轉(zhuǎn)入Q2。若當(dāng)前Q1、Q2為空,系統(tǒng)依次創(chuàng)建進程Pl、P2后即開始進程調(diào)度程P1、P2在系統(tǒng)中的平均等待時間為A、25msB、20msB、僅II、IIIC、僅I、Ⅱ、IVD、僅I、Ⅲ、Ⅳ采用二級反饋隊列調(diào)度Pl、P2需要的CPU時間分別為30ms與20ms,則進C、15msD、10ms28、在分段存儲管理系統(tǒng)中,用共享段表描述所有被共享的段。若進程P1與P2共享段S,下列敘述中,錯誤的就是A、在物理內(nèi)B、段S在P1與P2中應(yīng)該具有相同的段號C、P1與P2共享段S在共享段表中的段表項D、P1與P2都不再使用段S時才回收段S所占的內(nèi)29、某系統(tǒng)采用LRU頁置換算法與局部置換策略,若系統(tǒng)為進程0,1,2,7,0,5,3,5,0,2,7,6,則進程訪問上述頁的過程中,產(chǎn)生頁置換的總次數(shù)就是A、B、C、30、下列關(guān)于死鎖的敘述中,正確的就是I、可以通過剝奪進程II、死鎖的預(yù)防方法能確保系統(tǒng)不發(fā)生死鎖III、銀行家算法可以判斷系統(tǒng)就是否處于死鎖狀態(tài)當(dāng)系統(tǒng)出現(xiàn)死鎖時,必然有兩個或兩個以上的進程處于阻塞態(tài)A、僅II、ⅢB、僅I、Ⅱ、ⅣC、僅I、Ⅱ、ⅢD、31、某計算機主存按字節(jié)編址,采用二級分頁存儲管理,地址結(jié)構(gòu)如下所示存中僅保存一份段S的內(nèi)容存空間P預(yù)分配了4個頁框,進程P訪問頁號的序列為345D、6資源解除死鎖Ⅳ、僅I、Ⅲ、Ⅳ頁目錄號(10位)頁號(10位)頁內(nèi)偏移(12位)虛擬地址20501225H對應(yīng)的頁目錄號、頁號分別就是A、081H、101H32、在下列A、首次適應(yīng)算法B、081H、401HC、201H、101HD、201H、401H動態(tài)分區(qū)分配算法中,最容易產(chǎn)生內(nèi)存碎片的就是C、最佳適應(yīng)算法D、循環(huán)首次適應(yīng)算法B、最壞適應(yīng)算法33、OSI參考模型的第5層(自下而上)完成的主要功能就是A、差錯控制B、路由選C、會話管理示轉(zhuǎn)換34、100BaseT快速以太網(wǎng)使用的A、雙絞線B、35、對于滑動窗口協(xié)議,如果分組序號采用擇D、數(shù)據(jù)表導(dǎo)向傳輸介質(zhì)就是單模光纖C、多模光纖D、同軸電纜3比特編號,發(fā)送窗口大小為5,則接收窗口最大就是

A、2B、3C、4D、536、假設(shè)一個采用CSMA/CD協(xié)議的100Mbps局域網(wǎng),最小幀長就是128B,則在一個沖突域內(nèi)兩個站點之間的單向傳播延時最多就是A、2、56μsD、20、48μs37、若將101、200、16、0/20劃分為5個子網(wǎng),則可能的最小子網(wǎng)的可分配IP地址數(shù)就是A、126B、254C、510D、1022B、5、12μsC、10、24μsD、t440、下列關(guān)于網(wǎng)絡(luò)應(yīng)用模型的敘述中,錯誤的就是A、在P2P模型中,結(jié)點之間具有對等關(guān)系B、在客戶/服務(wù)器(C/S)模型中,客戶與客戶之間可以直接通信C、在C/S模型中,主動發(fā)起通信的就是客戶,被動通信的就是服務(wù)器D、在向多用戶分發(fā)一個文件時,P2P模型通常比C/S模型所需時間短二、綜合應(yīng)用題:41~47小題,共70分。41、(13分)設(shè)線性表L=(a1,a2,a…,an-2,a-1,a。)采用帶頭結(jié)點的單鏈表保存,鏈表中結(jié)點定義如下:typedefstructnode{intdata;structnode*next;}NODE;請設(shè)計一個空間復(fù)雜度為O(1)且時間上盡可能高效的算法,重新排列L中的各結(jié)點,得到線性表L'=(a1,an,a2,an-1,a3,an-2…)。要求:(1)給出算法的基本設(shè)計思想(2)根據(jù)設(shè)計思想,采用C或C++語言描述算法,關(guān)鍵之處給出注釋。(3)說明您所設(shè)計的算法的時間復(fù)雜度。42、(10分)請設(shè)計一個隊列,要求滿足:①初始時隊列為空;②入隊時,允許增加隊列占用空間;③出隊后,出隊元素所占用的空間可重復(fù)使用,即整個隊列所占用的空間只增不減;④人隊操作與出隊操作的時間復(fù)雜度始終保持為O(1)。請回答下列問題:(1)該隊列應(yīng)該選擇鏈?zhǔn)酱?2)畫出隊列的初始狀態(tài),并給出判斷隊空與隊滿的條件(3)畫出第一個元素入隊后的隊列狀態(tài)。(4)給出入隊操作與出隊操作的基本過程。儲結(jié)構(gòu),還就是順序存儲結(jié)構(gòu)？43、(8分)有n(n≥3)位哲學(xué)家圍坐在一張圓桌邊,每位哲學(xué)家交替地就餐與思考。在圓桌中心有m(m≥1)個碗,每兩位哲學(xué)家之間有1根筷子。每位哲學(xué)家必須取到一個碗與兩側(cè)的筷子之后,才能就餐,進餐完畢,將碗與筷子放回原位,并繼續(xù)思考。為使盡可能多的哲學(xué)家同時就餐,且防止出現(xiàn)死鎖現(xiàn)象,請使用信號量的P、V操作(wait()、signal()操作)描述上述過程中的互斥與同步,并說明所用信號量及初值的含義。44、(7分)某計算機系統(tǒng)中的磁盤有300個柱面,每個柱面有10個磁道,每個磁道有200個扇區(qū),扇區(qū)大小為512B。文件系統(tǒng)的每個簇包含2個扇區(qū)。請回答下列問題:(1)磁盤的容量就是多少？(2)假設(shè)磁頭在85號柱面上,此時有4個磁盤訪問請求,簇號分別為:100260、60005、101660與110560。若采用最短尋道時間優(yōu)先(SSTF)調(diào)度算法,則系統(tǒng)訪問簇的先后次序就是什么？(3)第100530簇在磁盤上的物理地址就是什么？將簇號轉(zhuǎn)換成磁盤物理地址的過程就是由I/O系統(tǒng)的什么程序完成的？45、(16分)已知f(n)=n！=n×(n-l)×(n-2)×…×2×1,計算f(n)的C語言函數(shù)fl的源程序(陰影部分)及其在32位計算機M上的部分機器級代碼如下:其中,機器級代碼行包括行號請回答下列問題:(1)計算f(10)需要調(diào)用函數(shù)f1多少次？(2)上述代碼中,哪條指令就是哪幾條指令一定會使程序跳轉(zhuǎn)執(zhí)行？(3)根據(jù)第16行call指令,第17行指令的16行call指令采用相對尋址方式,多少(給出計算過程)？已知第16行call指令的后4字節(jié)為偏移量,M采用大、虛擬地址、機器指令與匯編指令,計算機M按字節(jié)編址,int型數(shù)據(jù)占32位。執(zhí)行哪條指令會遞歸調(diào)用f1？條件轉(zhuǎn)移指令？虛擬地址應(yīng)就是多少？已知第該指令中的偏移量應(yīng)就是端還就是小端方式？(4)f(13)=6227020800,但f1(13)的返回值為1932053504,為什么的結(jié)果,應(yīng)如何修改f1源程序？(5)第19行imuleax,ecx表示有符號數(shù)乘法間滿足什么條件時,溢出標(biāo)志OF=1？要使CPU在發(fā)生溢出時轉(zhuǎn)異常處理,編譯器應(yīng)在imul指令后加一兩者不相等？要使f1(13)能返回正確,乘數(shù)為R[eax]與R[ecx],當(dāng)乘法器輸出的高、低32位乘積之條什么指令？46、(7分)對于題45,若計算機M的主存地址為32位,采用分頁存儲管理方式,頁大小為4KB,則第1行push30行ret指令就是否在同一頁中(說明理由)？若指令Cache有64行,采用4路組相聯(lián)映射方式,指令與第主存塊大小為64B,則32位主存地址中,哪幾位表示塊內(nèi)地址？哪兒位表示Cache組號？哪幾位表示標(biāo)記(tag)信息？讀取第16行call指令時,只可能在指令Cache的哪一組中命中(說明理由)？47、(9分)某網(wǎng)絡(luò)拓?fù)淙珙}47圖所示,其中R為路由器,主機H1~H4的IP地址配置以及R的各接口IP地址配置如圖中所示?，F(xiàn)有若干臺以太網(wǎng)交換機(無VLAN功能)與路由器兩類網(wǎng)絡(luò)互連設(shè)備可供選擇。請回答下列問題:(1)設(shè)備1、設(shè)備2與設(shè)備3分別應(yīng)選擇什么類型網(wǎng)絡(luò)設(shè)備？(2)設(shè)備1、設(shè)備2與設(shè)備3中,哪幾個設(shè)備的接口需要配置IP地址？并為對應(yīng)的接口配置正確的IP地址。(3)為確保主機H1~H4能夠訪問Internet,R需要提供什么服務(wù)？(4)若主機H3發(fā)送一個目的地址為192、168、1、127的IP數(shù)據(jù)報,網(wǎng)絡(luò)中哪幾個主機會接收該數(shù)據(jù)報？2019年全國碩士研究生招生考試計算機科學(xué)與技術(shù)學(xué)科聯(lián)考計算機學(xué)科專業(yè)基礎(chǔ)綜合試題參考答案1、B5、C6、A10、D11、B15、D16、D20、C21、A25、C26、B30、B31、A35、B36、B40、B12、C17、B22、D27、C32、C37、B13、A18、C23、B28、B33、C38、C14、D19、B24、C29、C34、A39、D(3)算參考答案的時間復(fù)雜度為O(n)。法的時間復(fù)雜度:42、【答案要點】(1)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)(兩段式單向循環(huán)鏈表),隊頭指針為front,隊尾指針為rear。(2)初始時,創(chuàng)建只有一個空閑結(jié)點的兩段式單向循環(huán)鏈表,頭指針front與尾指針rear均指向空閑結(jié)點。如下圖所示。二、綜合應(yīng)用題41、【答案要點】(1)算法的基本設(shè)計思想:算法分3步完成。第1步,采用兩個指針交替前行,找到單鏈表的中間結(jié)點;第2步,將單鏈表的后半段結(jié)點原地逆置;第3步,從單鏈表前后兩段中依次各取一個結(jié)點,按要求重排。隊空的判定條件:front==rear。隊滿的判定條件:front==rear->next。(3)插入第一個元素后的隊列狀態(tài):(2)算法實現(xiàn):(4)操作的基本過程:43、【答案要點】//信號量semaphorebowl;//用于協(xié)調(diào)哲學(xué)家對碗的使用semaphorechopsticks[n];//用于協(xié)調(diào)哲學(xué)家對筷子的使用for(inti=0;i<n;i++)chopsticks[i]、value=1;//設(shè)置兩個哲學(xué)家之間筷子0040102AH。call指令采用相對尋址方式,即目標(biāo)地址=(PC)+偏移量,call指令的目標(biāo)地址為00401000H,所以bowl、value=min(n-1,m);//bowl、value≤n-1,確保不死偏移量=目標(biāo)地址-(PC)=00401000H-0040102AH=FFFFFFD6H。根據(jù)第16行call指令的偏移量字段為D6FFFF1025H+5=0040102AH,故第17行指令的虛擬地址就是的數(shù)量鎖FF,可確定M采用小端方式。(4)因為f(13)=6227020800,大于32位int型數(shù)據(jù)可表CoBeginwhile(True){思考;P(bowl);//取碗P(chopsticks[i]);//取左邊筷子P(chopsticks[(i+l)MODn]);//取右邊筷子就餐;V(chopsticks[i]);V(chopsticks[(i+1)MODn]);//哲學(xué)家i的程序示的最大值,因而f1(13)的返回值就是一個發(fā)生了溢出的結(jié)果。為使f1(13)能返可正確結(jié)果,可將函數(shù)改為double(或longlong或longdouble或float)。(5)若乘積的高33位為非全0或非全l,則OF=1編譯器應(yīng)該在imul指令后加一條“溢出自陷指令”,使得CPU自動