2025年計(jì)算機(jī)考研408專項(xiàng)（強(qiáng)化）考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每小題2分，共20分。下列每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的。）1.下列關(guān)于棧和隊(duì)列的說(shuō)法中，正確的是（）。A.棧是先進(jìn)先出（FIFO）的線性結(jié)構(gòu)，隊(duì)列是后進(jìn)先出（LIFO）的線性結(jié)構(gòu)。B.棧和隊(duì)列都是先進(jìn)先出（FIFO）的線性結(jié)構(gòu)。C.棧是后進(jìn)先出（LIFO）的線性結(jié)構(gòu)，隊(duì)列是先進(jìn)先出（FIFO）的線性結(jié)構(gòu)。D.棧和隊(duì)列都是后進(jìn)先出（LIFO）的線性結(jié)構(gòu)。2.若對(duì)長(zhǎng)度為n的線性表進(jìn)行冒泡排序，則在最好的情況下（線性表已經(jīng)有序）所需的比較次數(shù)為（）。A.nB.n-1C.n(n-1)/2D.03.在理想情況下，Cache的命中率為90%，主存與Cache的訪問(wèn)時(shí)間分別為100ns和1000ns，則訪問(wèn)主存的平均時(shí)間約為（）。A.100nsB.100ns+90%*900nsC.900nsD.1000ns4.計(jì)算機(jī)系統(tǒng)中，中斷向量表通常存放在（）。A.RAM中B.ROM中C.Cache中D.寄存器中5.采用分頁(yè)存儲(chǔ)管理方式時(shí)，地址結(jié)構(gòu)是（）。A.邏輯地址=機(jī)器地址B.物理地址=邏輯地址+偏移量C.邏輯地址=段號(hào)+段內(nèi)地址D.物理地址=頁(yè)號(hào)+頁(yè)內(nèi)地址6.在TCP/IP協(xié)議簇中，負(fù)責(zé)網(wǎng)絡(luò)層路由選擇和數(shù)據(jù)傳輸?shù)膮f(xié)議是（）。A.IPB.TCPC.UDPD.ICMP7.下列關(guān)于HTTP協(xié)議的說(shuō)法中，錯(cuò)誤的是（）。A.HTTP是應(yīng)用層協(xié)議，基于TCP傳輸。B.HTTP是無(wú)連接的協(xié)議。C.HTTP是可靠的、面向連接的協(xié)議。D.HTTP使用端口80進(jìn)行通信。8.在以太網(wǎng)中，沖突域是指（）。A.一個(gè)網(wǎng)段內(nèi)所有連接的設(shè)備。B.兩臺(tái)設(shè)備同時(shí)發(fā)送數(shù)據(jù)導(dǎo)致信號(hào)損壞的設(shè)備范圍。C.交換機(jī)端口所連接的所有設(shè)備。D.路由器連接的所有設(shè)備。9.下列數(shù)據(jù)傳輸方式中，傳輸速率最高的是（）。A.單工通信B.半雙工通信C.全雙工通信D.串行通信10.操作系統(tǒng)中，進(jìn)程調(diào)度算法的目的是（）。A.盡可能提高CPU的利用率。B.盡可能減少平均等待時(shí)間。C.盡可能提高吞吐量。D.以上都是。二、填空題（每空2分，共20分。）1.在深度為h的二叉樹中，最多有____個(gè)結(jié)點(diǎn)。2.采用快速排序算法對(duì)n個(gè)元素進(jìn)行排序，其平均時(shí)間復(fù)雜度為____。3.計(jì)算機(jī)硬件系統(tǒng)由____、運(yùn)算器、控制器和輸入/輸出設(shè)備五大部件組成。4.指令周期通常由____、取指令、譯碼和執(zhí)行四個(gè)階段組成。5.虛擬內(nèi)存是為了解決主存容量不足的問(wèn)題而采用的技術(shù)，它將____和輔存統(tǒng)一管理，給用戶提供了使用一個(gè)邏輯上連續(xù)的大內(nèi)存空間。6.在網(wǎng)絡(luò)層，負(fù)責(zé)將IP數(shù)據(jù)報(bào)從源主機(jī)傳輸?shù)侥康闹鳈C(jī)的路由器進(jìn)行路徑選擇和數(shù)據(jù)包轉(zhuǎn)發(fā)。7.TCP協(xié)議提供的是面向連接的、可靠的字節(jié)流傳輸服務(wù)。8.互聯(lián)網(wǎng)中的域名系統(tǒng)（DNS）負(fù)責(zé)將域名解析為相應(yīng)的IP地址。9.在多道程序設(shè)計(jì)中，操作系統(tǒng)將內(nèi)存劃分成若干個(gè)大小相等的區(qū)域，稱為____。10.死鎖產(chǎn)生的必要條件包括：互斥、占有并等待、非搶占和循環(huán)等待。三、簡(jiǎn)答題（每小題5分，共20分。）1.簡(jiǎn)述棧的基本操作及其應(yīng)用場(chǎng)景。2.簡(jiǎn)述操作系統(tǒng)引入虛擬內(nèi)存的主要目的及其優(yōu)勢(shì)。3.簡(jiǎn)述TCP協(xié)議頭部包含的主要字段及其作用。4.簡(jiǎn)述網(wǎng)絡(luò)分層模型的主要思想及其優(yōu)點(diǎn)。四、計(jì)算題（每小題10分，共20分。）1.設(shè)有一個(gè)棧，依次壓入元素A、B、C、D、E。請(qǐng)給出出棧序列的所有可能情況（假設(shè)棧允許后進(jìn)先出）。2.假設(shè)某計(jì)算機(jī)主存地址空間為1MB（220），采用4頁(yè)的頁(yè)式存儲(chǔ)管理，每頁(yè)大小為4KB（212）。若邏輯地址為1234H，計(jì)算其對(duì)應(yīng)的物理地址范圍。五、綜合應(yīng)用題（每小題15分，共30分。）1.假設(shè)一臺(tái)計(jì)算機(jī)的Cache采用直接映射方式，Cache容量為64KB，分為32組，每組4塊，塊大小為16B。主存容量為1MB，分為256組，每組4塊，塊大小為16B。當(dāng)CPU訪問(wèn)主存地址為A（用二進(jìn)制表示，高位為組號(hào)，中間為塊號(hào)，最低位為塊內(nèi)地址）時(shí)，請(qǐng)回答：（1）該地址在Cache中對(duì)應(yīng)的組號(hào)是多少？（2）如果該組在Cache中已命中，請(qǐng)給出相應(yīng)的物理主存地址。（3）如果該組未命中，請(qǐng)給出相應(yīng)的物理主存地址，并簡(jiǎn)述查找過(guò)程。2.假設(shè)兩個(gè)進(jìn)程P1和P2需要共享一個(gè)臨界資源R，它們各自的代碼片段如下所示：P1:while(true){entrySection1;//進(jìn)入臨界區(qū)代碼criticalSection1;//臨界區(qū)代碼exitSection1;//離開臨界區(qū)代碼}P2:while(true){entrySection2;//進(jìn)入臨界區(qū)代碼criticalSection2;//臨界區(qū)代碼exitSection2;//離開臨界區(qū)代碼}請(qǐng)說(shuō)明什么是臨界區(qū)？為了使進(jìn)程P1和P2能夠正確地訪問(wèn)臨界資源R，進(jìn)入臨界區(qū)的代碼（entrySection）應(yīng)滿足哪些基本要求？請(qǐng)?jiān)O(shè)計(jì)一個(gè)使用信號(hào)量的解決方案。---試卷答案一、選擇題1.C2.A3.B4.B5.D6.A7.C8.B9.C10.D二、填空題1.2^(h+1)-12.O(n^2)3.運(yùn)算器4.取指5.主存6.IP7.可靠8.解析9.頁(yè)10.循環(huán)等待三、簡(jiǎn)答題1.棧的基本操作及其應(yīng)用場(chǎng)景操作：主要包括壓入（Push）、彈出（Pop）、查看棧頂元素（Peek/Lookup）和判斷棧空（IsEmpty）。應(yīng)用場(chǎng)景：函數(shù)調(diào)用棧（保存局部變量和返回地址）、表達(dá)式求值（中綴轉(zhuǎn)后綴、后綴表達(dá)式求值）、括號(hào)匹配、深度優(yōu)先搜索（DFS）算法等。2.操作系統(tǒng)引入虛擬內(nèi)存的主要目的及其優(yōu)勢(shì)目的：解決主存容量不足的問(wèn)題，讓用戶程序感覺(jué)擁有一個(gè)連續(xù)、較大的內(nèi)存空間。優(yōu)勢(shì)：提高內(nèi)存利用率，允許運(yùn)行比實(shí)際物理內(nèi)存更大的程序，保護(hù)內(nèi)存，簡(jiǎn)化內(nèi)存管理。3.TCP協(xié)議頭部包含的主要字段及其作用主要字段：源端口、目的端口（標(biāo)識(shí)傳輸層連接）、序列號(hào)（保證數(shù)據(jù)順序和可靠性）、確認(rèn)號(hào)（確認(rèn)收到對(duì)方數(shù)據(jù)）、頭部長(zhǎng)度、標(biāo)志位（ACK,SYN,FIN,RST等，用于控制連接狀態(tài)和數(shù)據(jù)傳輸）、窗口大?。髁靠刂疲⑿ｒ?yàn)和（保證數(shù)據(jù)完整性）、緊急指針（Urg）等。4.網(wǎng)絡(luò)分層模型的主要思想及其優(yōu)點(diǎn)主要思想：將復(fù)雜的網(wǎng)絡(luò)功能劃分為若干個(gè)功能層，各層之間相互獨(dú)立，每層為上一層提供服務(wù)，并通過(guò)接口進(jìn)行交互。優(yōu)點(diǎn)：降低復(fù)雜度、促進(jìn)標(biāo)準(zhǔn)化、提高靈活性（某層技術(shù)變更不影響其他層）、易于實(shí)現(xiàn)和維護(hù)。四、計(jì)算題1.棧的出棧序列可能的出棧序列有：ABCDE,ABEDC,ACBED,ACEDB,AECDB,DEABC,EACBD,EBCAD,EDCBA。解析思路：棧是后進(jìn)先出（LIFO）結(jié)構(gòu)。從A、B、C、D、E依次壓入后，出棧序列的第一個(gè)元素只能是E或D（因?yàn)镈在E之前壓入）。若第一個(gè)出棧是E，則剩余序列BCDA需要能生成以A結(jié)尾的所有合法出棧序列。類似分析，若第一個(gè)出棧是D，則剩余序列BCA需要能生成以A結(jié)尾的所有合法出棧序列。通過(guò)遞歸或枚舉法可以找出所有滿足條件的序列。2.頁(yè)式存儲(chǔ)管理地址轉(zhuǎn)換邏輯地址：1234H=0001001000110100(二進(jìn)制)物理地址：[頁(yè)號(hào)][塊內(nèi)地址]頁(yè)面大小=4KB=2^12Bytes，故每頁(yè)有2^12=4096個(gè)地址，頁(yè)內(nèi)地址占12位。主存地址空間=1MB=2^20Bytes，頁(yè)數(shù)=2^20/2^12=2^8=256頁(yè)，頁(yè)號(hào)占8位。邏輯地址的8位高位為頁(yè)號(hào)(00010010)，12位低位為塊內(nèi)地址(00110100)。物理地址范圍：頁(yè)號(hào)*頁(yè)大小+0到頁(yè)號(hào)*頁(yè)大小+(頁(yè)大小-1)=(00010010*1000)H+00000000H到(00010010*1000)H+11111111H=1000H+00000000H到1000H+FFFFH=1000H到1FFFH解析思路：將邏輯地址按頁(yè)大?。?KB）劃分，高位部分是頁(yè)號(hào)，低位部分是頁(yè)內(nèi)地址（塊內(nèi)地址）。頁(yè)號(hào)用于在主存中查找對(duì)應(yīng)的頁(yè)框（塊），頁(yè)內(nèi)地址用于定位頁(yè)框內(nèi)的具體字節(jié)。物理地址由頁(yè)號(hào)對(duì)應(yīng)的頁(yè)框號(hào)（物理塊號(hào)）乘以頁(yè)框大小加上頁(yè)內(nèi)地址得到。計(jì)算時(shí)需注意位數(shù)對(duì)應(yīng)和進(jìn)制轉(zhuǎn)換。五、綜合應(yīng)用題1.Cache地址映射與查找(1)組號(hào)：Cache組數(shù)=32，組大小=4塊=2^2塊，主存組大小=4塊=2^2塊。采用直接映射，主存塊號(hào)直接映射到Cache塊號(hào)。主存地址A=[M組號(hào)][M塊號(hào)][M塊內(nèi)地址]。Cache組號(hào)=M組號(hào)AND(Cache組數(shù)-1)=M組號(hào)AND(32-1)=M組號(hào)AND31(二進(jìn)制11111)。解析思路：直接映射方式下，主存地址的高位部分（足夠表示主存組數(shù)）直接用作Cache的組號(hào)。這里主存有256組（2^8），Cache有32組（2^5），所以需要主存組號(hào)的前5位（2^5=32）作為Cache組號(hào)。M組號(hào)是主存地址的高8位，取其前5位即可。(2)命中物理地址：假設(shè)地址A在Cache中的組號(hào)為G'，則命中時(shí)物理地址=(Cache組號(hào)*Cache塊大小)+M塊內(nèi)地址=(G'*4*16B)+M塊內(nèi)地址=(G'*64B)+M塊內(nèi)地址=(G'*40H)+M塊內(nèi)地址解析思路：命中意味著主存地址A對(duì)應(yīng)的頁(yè)（塊）已在Cache的G'組中。物理地址由Cache組號(hào)（G'）決定其頁(yè)框號(hào)，再乘以頁(yè)框大小（塊大小），最后加上塊內(nèi)地址部分。塊大小為16B。(3)未命中查找過(guò)程：組號(hào)G=M組號(hào)AND31。查找Cache的G組，若該組塊0是空或存放的是其他塊號(hào)的數(shù)據(jù)，則未命中。若塊0未命中，查找塊1，依此類推，直到找到塊4。如果G組的塊0到塊4都未命中（即該組當(dāng)前存放的塊是其他不在A地址范圍內(nèi)的塊），則發(fā)生未命中。未命中時(shí)的物理地址=(G*4*16B)+M塊內(nèi)地址=(G*64B)+M塊內(nèi)地址=(G*40H)+M塊內(nèi)地址解析思路：直接映射未命中時(shí)，直接檢查Cache中對(duì)應(yīng)組號(hào)G的所有塊（塊0到塊4）。如果這些塊都不存放主存地址A對(duì)應(yīng)的塊，則整個(gè)查找過(guò)程失敗，為未命中。此時(shí)物理地址的計(jì)算與命中類似，但G是通過(guò)主存地址計(jì)算得到的實(shí)際組號(hào)。查找過(guò)程主要是判斷Cache的G組中是否有A對(duì)應(yīng)的塊。2.臨界區(qū)與信號(hào)量解決死鎖臨界區(qū)：指進(jìn)程中訪問(wèn)共享資源的那段代碼，這段代碼需要被互斥執(zhí)行，即同一時(shí)刻只能有一個(gè)進(jìn)程進(jìn)入并執(zhí)行。進(jìn)入臨界區(qū)代碼（entrySection）基本要求：1.互斥執(zhí)行：確保每次只有一個(gè)進(jìn)程能進(jìn)入臨界區(qū)。2.有進(jìn)有出：一旦進(jìn)程進(jìn)入臨界區(qū)，必須最終離開，不能無(wú)限期停留。3.盡快退出：不能在臨界區(qū)內(nèi)執(zhí)行過(guò)多的操作，應(yīng)盡快釋放臨界資源。4.避免饑餓：保證每個(gè)需要進(jìn)入臨界區(qū)的進(jìn)程最終都能進(jìn)入。信號(hào)量解決方案：```pseudosem=P1//初始化信號(hào)量為1P1:while(true){wait(sem);//P操作，請(qǐng)求資源，若sem>0則減1，否則阻塞P1entrySection1;//進(jìn)入臨界區(qū)criticalSection1;//臨界區(qū)signal(sem);//V操作，釋放資源，sem加1exitSection1;//離開臨界區(qū)}P2:while(true){wait(sem);//P操作entrySection2;//進(jìn)入臨界區(qū)criticalSection2;//臨界區(qū)signal(sem