2025年考研計算機專業(yè)408真題試卷專項訓練及答案考試時間：______分鐘總分：______分姓名：______一、選擇題（每小題2分，共20分）1.下列關(guān)于線性表順序存儲結(jié)構(gòu)的敘述中，正確的是（）。A.插入和刪除操作都很方便B.邏輯上相鄰的元素物理上一定相鄰C.需要額外的存儲空間來表示元素之間的邏輯關(guān)系D.適用于經(jīng)常需要根據(jù)元素值進行查找的操作2.設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e依次進入棧S。若元素依次離開棧S和隊列Q，則離開棧S和隊列Q的元素序列分別為（）。A.a,b,c,d,e和a,b,c,d,eB.e,d,c,b,a和a,b,c,d,eC.e,d,c,b,a和e,d,c,b,aD.a,b,c,d,e和e,d,c,b,a3.在下列排序算法中，平均情況下時間復雜度最低的是（）。A.冒泡排序B.選擇排序C.插入排序D.快速排序4.已知一棵二叉樹的先根遍歷序列為ABCD，后根遍歷序列為CADB，則該二叉樹的根節(jié)點是（）。A.AB.BC.CD.D5.下列關(guān)于樹和二叉樹的敘述中，正確的是（）。A.樹和二叉樹都是線性結(jié)構(gòu)B.樹和二叉樹都是非線性結(jié)構(gòu)，且樹一定是二叉樹C.樹和二叉樹都是非線性結(jié)構(gòu)，且二叉樹一定是樹D.樹和二叉樹的定義完全相同6.哈希表解決沖突的鏈地址法是指（）。A.將所有關(guān)鍵字存儲在一個大的連續(xù)空間中B.將具有相同哈希地址的關(guān)鍵字存儲在同一個鏈表中C.將哈希表中的每個槽位看作一個指針，指向一個鏈表D.每個槽位存儲一個關(guān)鍵字及其比較函數(shù)7.操作系統(tǒng)引入虛擬內(nèi)存的主要目的是（）。A.實現(xiàn)內(nèi)存保護B.提高主存利用率C.實現(xiàn)多道程序設(shè)計D.擴展外存容量8.在分時系統(tǒng)中，提高響應(yīng)時間的主要途徑是（）。A.增加CPU速度B.增加內(nèi)存容量C.減少用戶數(shù)量D.優(yōu)先處理計算密集型任務(wù)9.文件系統(tǒng)中的“盤塊”（Block）是指（）。A.物理磁盤上的最小存儲單元B.邏輯磁盤上的最小存儲單元C.操作系統(tǒng)內(nèi)部管理的最小內(nèi)存單元D.用戶文件分配的最小單元10.下列關(guān)于TCP和UDP協(xié)議的敘述中，正確的是（）。A.TCP提供可靠的數(shù)據(jù)傳輸，UDP提供高效的數(shù)據(jù)傳輸B.TCP面向連接，UDP面向無連接C.TCP首部比UDP首部小D.TCP適用于實時性要求高的應(yīng)用，UDP適用于可靠性要求高的應(yīng)用二、填空題（每空2分，共20分）1.在單鏈表中，刪除某個節(jié)點p的關(guān)鍵步驟是找到p的前驅(qū)節(jié)點q，然后將q的指針指向p的下一個節(jié)點。2.二分查找算法要求數(shù)據(jù)序列必須有序，其時間復雜度為O(logn)。3.算法的空間復雜度是指執(zhí)行算法所需要的存儲空間，它包括輸入數(shù)據(jù)本身所占的空間和算法執(zhí)行過程中臨時占用的空間。4.操作系統(tǒng)的內(nèi)核是操作系統(tǒng)的核心部分，它駐留在內(nèi)存中，負責管理系統(tǒng)的各種資源。5.進程狀態(tài)通常包括新建狀態(tài)、就緒狀態(tài)、運行狀態(tài)和阻塞狀態(tài)。6.在頁式存儲管理中，地址映射過程需要使用頁表和頁表項。7.計算機網(wǎng)絡(luò)體系結(jié)構(gòu)的OSI模型共有七層，自下而上分別是物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會話層、表示層和應(yīng)用層。8.IP協(xié)議負責在互聯(lián)網(wǎng)中實現(xiàn)主機到主機的數(shù)據(jù)報傳輸。9.無連接的傳輸層協(xié)議是UDP。10.網(wǎng)橋工作在網(wǎng)絡(luò)的數(shù)據(jù)鏈路層。三、簡答題（每小題5分，共20分）1.簡述棧和隊列的主要區(qū)別。2.什么是平衡二叉樹？它為什么能夠保持較好的查找性能？3.操作系統(tǒng)如何實現(xiàn)內(nèi)存保護？4.簡述TCP協(xié)議如何保證數(shù)據(jù)傳輸?shù)目煽啃浴Ｋ?、計算題（每小題10分，共20分）1.設(shè)有一個順序存儲的線性表L，其元素依次為(12,23,36,47,58,69)?，F(xiàn)在要刪除元素36，請描述刪除操作的步驟（無需寫出完整代碼，只需說明過程和結(jié)果）。2.假設(shè)某計算機的頁表如下（頁號從0開始）：頁號|塊號----|----0|31|12|-3|4物理內(nèi)存塊號從0到7，若要訪問邏輯地址為1C0H的頁內(nèi)地址，請計算其對應(yīng)的物理地址（假設(shè)頁內(nèi)地址占10位）。五、綜合應(yīng)用題（每小題15分，共30分）1.已知一棵二叉樹的先根遍歷序列和中根遍歷序列分別為：先根序列ABDECFG，中根序列DBEACFG。請畫出該二叉樹的結(jié)構(gòu)圖。2.假設(shè)有一個磁盤請求序列為：98,183,37,122,14,124,65,67。若采用FCFS（先來先服務(wù)）、SSTF（最短尋道時間優(yōu)先）和SCAN（掃描）三種磁盤調(diào)度算法，請分別計算平均尋道長度（假設(shè)磁頭初始位于50道）。---試卷答案一、選擇題1.B解析：順序存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理內(nèi)存中也相鄰，便于隨機訪問，但插入和刪除操作需要移動大量元素，效率較低。2.D解析：棧是后進先出結(jié)構(gòu)，元素依次進入棧后按逆序離開；隊列是先進先出結(jié)構(gòu)，元素按進入順序離開。初始狀態(tài)為空，a,b,c,d,e依次進入棧，則離開棧的順序為e,d,c,b,a。元素依次進入隊列，則離開隊列的順序為a,b,c,d,e。3.D解析：快速排序在平均情況下的時間復雜度為O(nlogn)，優(yōu)于冒泡排序、選擇排序和插入排序的平均時間復雜度（均為O(n^2)）。4.A解析：根據(jù)二叉樹的遍歷性質(zhì)，先根遍歷的第一個元素A是根節(jié)點。在后根遍歷中，A位于C,D,B之后，說明C,D,B是A的子樹，且后根遍歷中A之前的部分（CADB）是A右子樹的后根遍歷序列，因此B是A的左子節(jié)點。5.C解析：樹和二叉樹都是非線性結(jié)構(gòu)。樹是任意節(jié)點有且只有一個父節(jié)點，而二叉樹是每個節(jié)點最多有兩個子節(jié)點，樹的定義比二叉樹更廣，任何一棵樹都可以轉(zhuǎn)換為對應(yīng)的二叉樹。6.B解析：鏈地址法是將具有相同哈希地址（沖突）的關(guān)鍵字存儲在同一個鏈表中。每個鏈表的頭指針存放在哈希表的相應(yīng)槽位中。7.B解析：虛擬內(nèi)存技術(shù)利用輔存擴展主存容量，提高主存的利用率，使得更多的程序可以同時運行或運行更大規(guī)模的程序。8.A解析：分時系統(tǒng)強調(diào)同時服務(wù)多個用戶，響應(yīng)時間（用戶等待時間）是關(guān)鍵指標。增加CPU速度可以更快地處理用戶請求，從而縮短響應(yīng)時間。9.A解析：盤塊（或稱物理塊、磁盤塊）是操作系統(tǒng)在磁盤管理中劃分的最小存儲單元，文件系統(tǒng)以盤塊為單位在磁盤上存儲數(shù)據(jù)。10.B解析：TCP提供可靠、面向連接的數(shù)據(jù)傳輸，而UDP提供快速、無連接的數(shù)據(jù)傳輸。TCP首部比UDP首部大，因為包含了序列號、確認號等保證可靠性的字段。TCP適用于可靠性要求高的應(yīng)用，UDP適用于實時性要求高且能容忍少量丟包的應(yīng)用（如視頻、音頻）。二、填空題1.前驅(qū)節(jié)點q，p的下一個節(jié)點解析：刪除節(jié)點p，需要找到其前驅(qū)節(jié)點q，修改q的指針指向p的下一個節(jié)點，從而將p從鏈中斷開。2.有序解析：二分查找算法依賴于數(shù)據(jù)的有序性，通過不斷將查找區(qū)間分成兩半來定位目標元素。3.空間復雜度，輸入數(shù)據(jù)本身所占的空間，算法執(zhí)行過程中臨時占用的空間解析：空間復雜度衡量算法運行所需存儲空間，包括存儲輸入數(shù)據(jù)的空間以及算法執(zhí)行時臨時變量、遞歸棧等占用的空間。4.內(nèi)核解析：操作系統(tǒng)內(nèi)核是系統(tǒng)的核心部分，直接管理硬件資源，提供基礎(chǔ)服務(wù)，是其他系統(tǒng)軟件和應(yīng)用軟件運行的基礎(chǔ)。5.狀態(tài)解析：進程在其生命周期內(nèi)會經(jīng)歷不同的狀態(tài)轉(zhuǎn)換，如創(chuàng)建、就緒、運行、阻塞、終止等。6.頁表，頁表項解析：頁式存儲管理通過頁表實現(xiàn)邏輯地址到物理地址的映射，頁表項存儲了頁號與物理塊號的對應(yīng)關(guān)系。7.OSI模型，物理層，數(shù)據(jù)鏈路層，網(wǎng)絡(luò)層，傳輸層，會話層，表示層，應(yīng)用層解析：OSI模型是國際標準化組織提出的網(wǎng)絡(luò)參考模型，共七層，從下到上分別為物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會話層、表示層和應(yīng)用層。8.主機到主機解析：IP協(xié)議的主要功能是在網(wǎng)絡(luò)層實現(xiàn)數(shù)據(jù)報在網(wǎng)絡(luò)中的傳輸，其目標是找到目標主機并交付數(shù)據(jù)報，即實現(xiàn)主機到主機的通信。9.UDP解析：UDP（UserDatagramProtocol）是一種無連接的、不可靠的傳輸層協(xié)議，不保證數(shù)據(jù)報的按序和可靠到達。10.數(shù)據(jù)鏈路層解析：網(wǎng)橋（Bridge）工作在OSI模型的數(shù)據(jù)鏈路層，根據(jù)MAC地址過濾和轉(zhuǎn)發(fā)數(shù)據(jù)幀，用于連接不同網(wǎng)段。三、簡答題1.答：棧是后進先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只允許在棧頂進行插入和刪除操作；隊列是先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，允許在隊尾插入元素，在隊頭刪除元素。棧適用于需要按特定順序處理元素的場景，隊列適用于需要按到達順序處理元素的場景。2.答：平衡二叉樹（如AVL樹、紅黑樹）是一種特殊的二叉搜索樹，通過維護樹中任意節(jié)點的左右子樹高度差不超過1（AVL）或滿足一定紅黑性質(zhì)，使得樹的高度大致保持在log(n)級別。這使得二叉搜索樹的查找、插入、刪除等操作的平攤時間復雜度都能保持在O(logn)，即使樹因插入刪除操作而變得不平衡，也能通過旋轉(zhuǎn)等操作快速恢復平衡。3.答：操作系統(tǒng)通過設(shè)置內(nèi)存保護機制實現(xiàn)內(nèi)存保護。例如，為每個進程分配獨立的虛擬地址空間，并通過硬件（如MMU）和軟件（如內(nèi)存管理單元中的頁表）將虛擬地址映射到物理地址。同時，設(shè)置訪問權(quán)限位（如讀、寫、執(zhí)行權(quán)限）在頁表項中，限制進程只能訪問其自身分配的內(nèi)存區(qū)域，并遵守設(shè)定的權(quán)限，防止進程非法訪問或破壞其他進程或操作系統(tǒng)的內(nèi)存空間。4.答：TCP協(xié)議保證數(shù)據(jù)傳輸可靠性的主要機制包括：①序列號和確認應(yīng)答（ACK）：TCP將數(shù)據(jù)分割成段，為每個段賦予序列號，接收方發(fā)送ACK確認收到數(shù)據(jù)，確保數(shù)據(jù)的順序和完整性；②超時重傳：發(fā)送方如果在規(guī)定時間內(nèi)未收到接收方的ACK，會認為數(shù)據(jù)丟失并重新發(fā)送該段；③數(shù)據(jù)校驗：TCP首部包含校驗和字段，用于檢測數(shù)據(jù)在傳輸過程中是否出錯；④流量控制：通過滑動窗口機制控制發(fā)送速率，防止發(fā)送方淹沒接收方；⑤連接管理：通過三次握手建立連接，四次揮手終止連接，確保連接的可靠建立和關(guān)閉。四、計算題1.答：線性表L順序存儲，刪除元素36的過程：首先找到元素36的存儲位置（假設(shè)起始地址為base，元素間隔為len，則36位于base+5*len處）。然后，將從36后面的元素（47,58,69）依次向前移動一個位置，覆蓋掉36和47，覆蓋過程為：base+6*len<-base+5*len,base+7*len<-base+6*len,base+8*len<-base+7*len。最后，將線性表的長度減1。刪除后，線性表L的新元素序列為(12,23,58,69)。2.答：邏輯地址1C0H的頁號是1C0H除以頁大?。僭O(shè)頁大小為4KB，即1000H），計算得頁號=1C0H/1000H=1CH/10=1CH/16=1D（十進制13）。頁內(nèi)地址是1C0H對頁大小的余數(shù)，計算得頁內(nèi)地址=1C0H%1000H=1C0H-(1CH*1000H/1000H)=1C0H-1CH00H=1C0H-1000H=200H。根據(jù)頁號1D（十進制13），查找頁表，1D對應(yīng)塊號4。因此，物理地址=塊號*塊大小+頁內(nèi)地址=4*1000H+200H=4000H+200H=4200H。所以，邏輯地址1C0H對應(yīng)的物理地址是4200H。五、綜合應(yīng)用題1.答：根據(jù)先根序列ABDECFG，A是根節(jié)點。在中根序列DBEACFG中，A之前的部分DBE是左子樹的中根遍歷序列，對應(yīng)的先根遍歷序列是DBE。左子樹DBE的先根序列DBE對應(yīng)的中根序列是BDE，可以確定B是D的父節(jié)點，E是B的右子節(jié)點。中根序列中BDE之后是ACFG，是右子樹的中根遍歷序列，對應(yīng)的先根遍歷序列是CFG。右子樹ACFG的先根序列CFG對應(yīng)的中根序列是ACFG，可以確定C是A的右子節(jié)點，F(xiàn)是C的右子節(jié)點，G是F的右子節(jié)點。根據(jù)以上分析，可以畫出二叉樹如下：```A/\BC\\EF\G```2.答：磁頭初始位于50道。①FCFS（先來先服務(wù)）：順序處理請求98,183,37,122,14,124,65,67。尋道序列：50→98→183→37→122→14→124→65→67。平均尋道長度=(|98-50|+|183-98|+|37-183|+|122-37|+|14-122|+|124-14|+|65-124|+|67-65|)/8=(48+85+146+85+108+110+59+2)/8=743/8=92.875道。②SSTF（最短尋道時間優(yōu)先）：每次選擇距離當前磁頭最近的請求。初始50。選擇37（距離50道），尋道50→37。磁頭在37。選擇65（距離37道），尋道37→65。磁頭在65。選擇67（距離65道），尋道65→67。磁頭在67。選擇98（距離67道），尋道67→98