2025年計算機(jī)408真題深度模擬沖刺考試時間：______分鐘總分：______分姓名：______一、1.設(shè)有順序存儲的棧S和隊列Q，棧按順序存儲，棧底為數(shù)組下標(biāo)0處，棧頂為數(shù)組當(dāng)前最大下標(biāo)。隊列也按順序存儲，隊頭為數(shù)組下標(biāo)0處，隊尾為數(shù)組當(dāng)前最大下標(biāo)。初始時棧和隊列為空?，F(xiàn)有一序列元素A,B,C,D,E依次進(jìn)入隊列Q。每進(jìn)入一個元素后，若棧非空且棧頂元素與隊頭元素相同，則將棧頂元素出棧，并將隊頭元素出隊列。重復(fù)此過程，直到隊列為空。請問：最終棧中剩下的元素（按出棧順序列出）是什么？請給出推理過程。2.已知一棵二叉樹的前序遍歷序列為ABCD，中序遍歷序列為CBAD。請畫出該二叉樹的結(jié)構(gòu)圖。3.寫出快速排序算法的基本思想。并用偽代碼描述快速排序的核心遞歸過程。4.解釋什么是數(shù)據(jù)結(jié)構(gòu)的平攤分析。請以棧的push操作和pop操作為例，說明為什么棧的平攤分析是必要的。二、5.解釋什么是計算機(jī)系統(tǒng)的性能指標(biāo)CPI（每條指令執(zhí)行周期數(shù)）。影響CPI的主要因素有哪些？6.在一個采用請求分頁的虛擬內(nèi)存系統(tǒng)中，主存采用固定分配給每個進(jìn)程的方式。設(shè)主存容量為M頁，進(jìn)程P需要訪問的頁面序列為a1,a2,...,an。假設(shè)開始時主存為空。請解釋LRU（最近最少使用）頁面置換算法的基本思想。若M=3，n=8，頁面請求序列為3,1,4,1,5,9,2,6，請計算缺頁次數(shù)。7.在操作系統(tǒng)中，什么是臨界區(qū)？為什么需要臨界區(qū)？請簡述使用信號量機(jī)制實現(xiàn)進(jìn)程互斥的基本思想。8.比較說明虛擬內(nèi)存和物理內(nèi)存的主要區(qū)別。三、9.簡述CSMA/CD（載波偵聽多路訪問/沖突檢測）介質(zhì)訪問控制方法的基本工作原理及其適用場景。10.在TCP/IP協(xié)議簇中，網(wǎng)絡(luò)層負(fù)責(zé)將數(shù)據(jù)包從源主機(jī)傳輸?shù)侥繕?biāo)主機(jī)。請簡述IP協(xié)議的主要功能。一個IP數(shù)據(jù)報在傳輸過程中，其首部TTL（生存時間）字段的作用是什么？11.解釋TCP協(xié)議中三次握手建立連接的過程。為什么不能采用兩次握手？12.DNS（域名系統(tǒng)）的作用是什么？請簡述DNS解析一個域名（例如）的基本過程。四、13.解釋什么是網(wǎng)絡(luò)擁塞。簡述TCP協(xié)議中常用的三種擁塞控制策略：慢啟動、擁塞避免、快恢復(fù)。14.設(shè)有一個采用子網(wǎng)劃分的IPv4網(wǎng)絡(luò)，網(wǎng)絡(luò)地址為。該網(wǎng)絡(luò)使用掩碼92進(jìn)行子網(wǎng)劃分。請計算該網(wǎng)絡(luò)能夠劃分出的子網(wǎng)數(shù)量、每個子網(wǎng)的主機(jī)數(shù)量，并寫出其中兩個子網(wǎng)的地址范圍。15.HTTP協(xié)議和FTP協(xié)議都是應(yīng)用層協(xié)議。請比較它們在實現(xiàn)基本文件傳輸功能方面的主要區(qū)別。16.在以太網(wǎng)中，MAC地址是什么？請簡述以太網(wǎng)幀的基本結(jié)構(gòu)。五、17.設(shè)計一個算法，判斷一個給定的無向連通圖G是否包含環(huán)。請用偽代碼描述該算法，并說明算法的時間復(fù)雜度。18.設(shè)有n個任務(wù)需要在一個單處理器上執(zhí)行，每個任務(wù)i有固定的執(zhí)行時間ti。請問：按照什么順序執(zhí)行這些任務(wù)，能使它們的總完成時間（即最后一個任務(wù)完成的時間）最??？請給出該問題的基本解法思路。19.解釋什么是總線仲裁。在令牌環(huán)網(wǎng)中，總線仲裁是如何實現(xiàn)的？20.假設(shè)在一個計算機(jī)系統(tǒng)中，主存訪問時間為100納秒，Cache訪問時間為10納秒，主存與Cache之間采用直接映射方式，Cache容量為1024塊，塊大小為64字節(jié)。若發(fā)生了一次Cache未命中（即訪存請求未在Cache中找到所需數(shù)據(jù)），請問：從發(fā)出訪存請求到數(shù)據(jù)被讀入Cache并可用，總共需要多少時間？（不考慮替換和寫回等后續(xù)操作時間）試卷答案一、1.最終棧中剩下的元素是C。推理過程：元素按A,B,C,D,E的順序進(jìn)入隊列。進(jìn)入A、B后，?？?，不執(zhí)行操作。進(jìn)入C時，棧頂為空，不執(zhí)行操作，C留在棧中。進(jìn)入D時，棧頂C與隊頭C相同，棧頂C出棧，隊頭D出隊列。此時棧為空，進(jìn)入E時，?？?，不執(zhí)行操作。最終棧中只有最初進(jìn)入的C。2.該二叉樹結(jié)構(gòu)如下：```A/\BC\D\E```解析思路：前序遍歷序列為ABCD，故A為根節(jié)點。中序遍歷序列為CBAD，在中序遍歷中，C在B之前，說明C是B的左子節(jié)點。D在C之后，在A之前，說明D是A的右子節(jié)點。因此A有左子樹B和右子樹D。再來看B的子樹，中序序列CBAD中，B之后只有D，說明B沒有左子節(jié)點，只有右子節(jié)點C。所以樹的結(jié)構(gòu)如上所示。3.快速排序的基本思想是：通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分的關(guān)鍵字小，然后分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。核心遞歸過程偽代碼：```Quicksort(A,low,high):iflow<high:pivot=Partition(A,low,high)//將A[low..high]劃分，返回樞軸位置pivotQuicksort(A,low,pivot-1)//遞歸排序樞軸左邊的子序列Quicksort(A,pivot+1,high)//遞歸排序樞軸右邊的子序列Partition(A,low,high):pivot=A[high]//選擇最后一個元素作為樞軸i=low-1forj=lowtohigh-1:ifA[j]<=pivot:i=i+1swapA[i]withA[j]swapA[i+1]withA[high]returni+1```解析思路：快速排序是分治算法。核心是Partition過程，它選擇一個樞軸元素（通常選最后一個），并將其他元素重新排列，使得所有小于樞軸的元素都在它的左邊，所有大于樞軸的元素都在它的右邊，最后返回樞軸的最終位置。然后對左右兩個子區(qū)間遞歸進(jìn)行同樣的操作。4.平攤分析是用于分析數(shù)據(jù)結(jié)構(gòu)中一系列操作的平均性能的方法，其中某些操作可能執(zhí)行時間較長，但發(fā)生的頻率較低。棧的push和pop操作在?？臻g未滿或未空時執(zhí)行時間恒定為O(1)。但在棧空間滿時，push操作可能需要先執(zhí)行出棧（或特定策略）才能入棧，這時一次push操作可能需要執(zhí)行多次時間更長的操作。平攤分析可以證明，即使有少數(shù)操作是O(n)的，對于一系列連續(xù)的n次push和pop操作，平均每次操作的時間仍然是O(1)。解析思路：理解平攤分析的核心思想是“平均”，它將少數(shù)操作的高開銷分散到大量普通操作中。棧的push/pop操作序列中，滿棧/空棧情況是稀疏發(fā)生的，通過平攤分析可以得出平均性能是O(1)。二、5.CPI（每條指令執(zhí)行周期數(shù)）是衡量計算機(jī)執(zhí)行指令平均所需時鐘周期的指標(biāo)。它是計算機(jī)總執(zhí)行周期數(shù)除以指令總數(shù)。CPI=總執(zhí)行周期數(shù)/指令總數(shù)。影響CPI的主要因素包括：指令執(zhí)行所經(jīng)過的流水線級數(shù)、各流水線級的延遲、指令之間的數(shù)據(jù)相關(guān)（結(jié)構(gòu)冒險、數(shù)據(jù)冒險、控制冒險）以及處理器的分支預(yù)測準(zhǔn)確率等。6.LRU（最近最少使用）頁面置換算法的基本思想是：當(dāng)需要調(diào)入新頁面而主存已滿時，選擇最久未被使用（即最近最少被訪問過）的頁面進(jìn)行置換。若發(fā)生缺頁，則將該頁置換出去，并更新頁表或相關(guān)數(shù)據(jù)結(jié)構(gòu)以反映此頁現(xiàn)在已被使用過。M=3，n=8，序列3,1,4,1,5,9,2,6。缺頁序列：3,1,(4),1,(5),9,(2),6解析思路：按順序訪問頁面，維護(hù)一個大小為M=3的當(dāng)前在內(nèi)存的頁面集合（初始為空）。對于每個訪問的頁面，若頁面已在內(nèi)存，則更新其使用時間或位置（模擬LRU）。若頁面不在內(nèi)存，發(fā)生缺頁：*若內(nèi)存未滿，直接調(diào)入該頁。*若內(nèi)存已滿，則查找當(dāng)前集合中LRU頁面（最久未被訪問的頁面）進(jìn)行置換，并將新訪問的頁面調(diào)入。*根據(jù)此規(guī)則計算缺頁次數(shù)。訪問3：缺頁，內(nèi)存[3]。缺頁次數(shù)=1。訪問1：缺頁，內(nèi)存[3,1]。缺頁次數(shù)=2。訪問4：缺頁，內(nèi)存[1,4,3]。缺頁次數(shù)=3。LRU是1。訪問1：已在內(nèi)存，內(nèi)存[1,4,3]。缺頁次數(shù)=3。訪問5：缺頁，內(nèi)存[4,3,5]。缺頁次數(shù)=4。LRU是3。訪問9：缺頁，內(nèi)存[3,5,9]。缺頁次數(shù)=5。LRU是4。訪問2：缺頁，內(nèi)存[5,9,2]。缺頁次數(shù)=6。LRU是9。訪問6：缺頁，內(nèi)存[9,2,6]。缺頁次數(shù)=7。LRU是5。最終缺頁次數(shù)為7。7.臨界區(qū)是指進(jìn)程中訪問共享變量的那部分代碼片段，這部分代碼在任意時刻只能由一個進(jìn)程訪問。需要臨界區(qū)是因為共享資源（如變量、設(shè)備）的訪問需要互斥，防止多個進(jìn)程同時訪問導(dǎo)致數(shù)據(jù)不一致或邏輯錯誤。使用信號量機(jī)制實現(xiàn)進(jìn)程互斥的基本思想是：引入一個信號量S和一個初始值為1的進(jìn)程隊列。進(jìn)程進(jìn)入臨界區(qū)前必須執(zhí)行P(S)操作（等待，若S>0則減1，否則阻塞該進(jìn)程入隊），離開臨界區(qū)后執(zhí)行V(S)操作（釋放，將S加1，并喚醒隊列中一個阻塞的進(jìn)程）。通過P、V操作控制對臨界資源的互斥訪問。8.虛擬內(nèi)存是操作系統(tǒng)提供的一種內(nèi)存管理技術(shù)，它將邏輯地址空間（虛擬地址）映射到物理內(nèi)存（實地址），使得每個進(jìn)程都擁有獨立的、看似無限的地址空間。物理內(nèi)存是計算機(jī)中實際存在的、用于存儲程序和數(shù)據(jù)的主存儲器（通常是RAM）。主要區(qū)別在于：*地址空間：虛擬內(nèi)存提供比物理內(nèi)存大得多的邏輯地址空間。物理內(nèi)存地址空間受限于實際RAM容量。*管理者：虛擬內(nèi)存由操作系統(tǒng)管理。物理內(nèi)存由硬件和操作系統(tǒng)共同管理。*對象：虛擬內(nèi)存地址是邏輯的、抽象的。物理內(nèi)存地址是具體的、對應(yīng)的硬件地址。*作用：虛擬內(nèi)存支持更復(fù)雜的程序設(shè)計、實現(xiàn)內(nèi)存保護(hù)、簡化內(nèi)存分配回收、通過分頁/分段實現(xiàn)共享和保護(hù)。物理內(nèi)存是程序執(zhí)行的基礎(chǔ)載體。三、9.CSMA/CD（載波偵聽多路訪問/沖突檢測）的基本工作原理是：在發(fā)送數(shù)據(jù)前，站點先偵聽信道是否空閑。若空閑則發(fā)送；若忙則繼續(xù)偵聽。在發(fā)送過程中，站點持續(xù)檢測信道，若發(fā)現(xiàn)沖突（即自己發(fā)送的信號與信道上其他站點的信號疊加導(dǎo)致信號質(zhì)量下降），則立即停止發(fā)送，并發(fā)送一個短暫的沖突加強(qiáng)信號，然后執(zhí)行二進(jìn)制指數(shù)退避算法等待一個隨機(jī)時間后重試。適用場景：半雙工的共享介質(zhì)網(wǎng)絡(luò)，如傳統(tǒng)的以太網(wǎng)。解析思路：理解其三大步驟：先聽后發(fā)、邊發(fā)邊聽、沖突停發(fā)并退避。這是一種基于沖突檢測的隨機(jī)訪問協(xié)議。10.IP協(xié)議的主要功能是提供一種無連接的、不可靠的數(shù)據(jù)報交付服務(wù)。它負(fù)責(zé)將數(shù)據(jù)報從源主機(jī)通過中間網(wǎng)絡(luò)節(jié)點，最終交付給目標(biāo)主機(jī)。IP協(xié)議不保證數(shù)據(jù)報一定能到達(dá)、按順序到達(dá)或無差錯到達(dá)。一個IP數(shù)據(jù)報的TTL（生存時間）字段是一個八位計數(shù)器，其單位是跳數(shù)（hops）。每個路由器在處理一個IP數(shù)據(jù)報時，會將其TTL減1。當(dāng)TTL減到0時，該數(shù)據(jù)報會被丟棄，以防止數(shù)據(jù)報在網(wǎng)絡(luò)中無限循環(huán)。TTL的主要作用是限制數(shù)據(jù)報在網(wǎng)絡(luò)中的生存時間，防止因路由錯誤或網(wǎng)絡(luò)故障導(dǎo)致的數(shù)據(jù)報永久滯留。11.TCP協(xié)議中三次握手建立連接的過程如下：1.SYN:客戶端向服務(wù)器發(fā)送一個SYN（同步）包，包含客戶端的初始序列號ISN（InitialSequenceNumber）X。客戶端進(jìn)入SYN-SENT狀態(tài)。2.SYN-ACK:服務(wù)器收到SYN包后，若同意連接，則回復(fù)一個SYN-ACK包，包含服務(wù)器的初始序列號ISNY，以及確認(rèn)號ACK=X+1。服務(wù)器進(jìn)入SYN-RECEIVED狀態(tài)。3.ACK:客戶端收到SYN-ACK包后，向服務(wù)器發(fā)送一個ACK包，確認(rèn)號ACK=Y+1，序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號序列號