2025年計算機考研真題深度解析集考試時間：______分鐘總分：______分姓名：______一、1.設(shè)有五個元素a,b,c,d,e的序列，依次進行插入排序（從小到大），請簡述將元素e插入到已排序序列[a,b,c,d]中的具體過程，并說明比較次數(shù)。2.什么是平衡二叉樹？以AVL樹為例，解釋進行一次單旋（右旋或左旋）操作的目的，并說明旋轉(zhuǎn)后如何保持樹的平衡性質(zhì)。3.簡述冒泡排序、快速排序和歸并排序的基本思想，并比較它們在最好、最壞和平均情況下的時間復(fù)雜度。二、1.在單總線結(jié)構(gòu)的計算機中，若數(shù)據(jù)通路寬度為32位，指令周期分為取指、譯碼、執(zhí)行三個階段。取指和譯碼階段不需要訪問存儲器，執(zhí)行階段需要訪問存儲器讀取數(shù)據(jù)。假設(shè)取指和譯碼階段耗時分別為1個時鐘周期，執(zhí)行階段耗時為3個時鐘周期，且訪存操作（讀或?qū)懀┖臅r為2個時鐘周期，不考慮其他控制開銷。請計算執(zhí)行以下指令序列所需的總時鐘周期數(shù)（假設(shè)指令均需訪存執(zhí)行）：*LOADR1,[1000];從地址1000讀數(shù)據(jù)到寄存器R1*LOADR2,[2000];從地址2000讀數(shù)據(jù)到寄存器R2*ADDR3,R1,R2;將R1和R2內(nèi)容相加結(jié)果存入R3*STORER3,[3000];將R3內(nèi)容寫入地址30002.解釋什么是總線主控？在典型的CPU-主存系統(tǒng)中，誰通常是總線主控？請說明理由。三、1.設(shè)有一個進程共有5個頁面，其內(nèi)存分配情況如下（頁號從0開始）：*進程A：頁框0,2,3被分配。*進程B：頁框1,4被分配。*進程C：頁框2,4未被分配（空閑）。當(dāng)進程A需要訪問第4頁時發(fā)生缺頁中斷，當(dāng)前內(nèi)存中進程A的頁（頁框0和頁框3）和進程B的頁（頁框1和頁框4）都需要置換。若采用LRU（最近最少使用）算法進行頁面置換，請說明將哪個進程的哪個頁先被置換出去，并簡述選擇該頁的理由。2.什么是操作系統(tǒng)的內(nèi)核？簡述操作系統(tǒng)內(nèi)核的主要功能和它在計算機系統(tǒng)中的地位。3.在TCP協(xié)議中，若一個TCP連接的接收窗口大小為4KB，發(fā)送方已發(fā)送的確認號為2012，接收方希望接收從序列號2000開始的數(shù)據(jù)。請解釋接收方發(fā)送的確認號是什么？若發(fā)送方收到該確認后，立即發(fā)送了兩個連續(xù)的數(shù)據(jù)段，第一個數(shù)據(jù)段包含序列號2012和2013的數(shù)據(jù)，第二個數(shù)據(jù)段包含序列號2014和2015的數(shù)據(jù)，這兩個數(shù)據(jù)段發(fā)送完畢后，發(fā)送方通告的窗口大小是多少（假設(shè)接收方?jīng)]有其他數(shù)據(jù)發(fā)送，且后續(xù)沒有收到新的確認）？四、1.解釋OSI參考模型的七層結(jié)構(gòu)及其主要功能。簡述數(shù)據(jù)在從應(yīng)用層向下傳輸?shù)轿锢韺拥倪^程中，各層是如何添加和移除頭部信息的。2.以太網(wǎng)（Ethernet）使用CSMA/CD介質(zhì)訪問控制方法。請簡述CSMA/CD的基本工作原理。當(dāng)兩臺主機同時開始發(fā)送數(shù)據(jù)時，它們?nèi)绾螜z測沖突并采取行動？3.解釋IP地址和MAC地址在計算機網(wǎng)絡(luò)中的作用和區(qū)別。為什么在TCP/IP協(xié)議棧中需要同時使用這兩種地址？五、1.請定義指針和引用（引用）在C++中的概念，并簡述它們的主要區(qū)別和使用場景。2.寫一個C++函數(shù)，該函數(shù)接受一個指向整數(shù)數(shù)組的指針和數(shù)組的大小，計算并返回該數(shù)組中所有元素的平均值。如果數(shù)組為空（大小為0），則返回0。不得使用標(biāo)準(zhǔn)庫函數(shù)計算平均值。3.定義一個C++類`Point`，用于表示二維空間中的點。該類應(yīng)至少包含：*兩個私有成員變量`x`和`y`，分別存儲點的橫縱坐標(biāo)。*一個公有構(gòu)造函數(shù)，可以接受兩個參數(shù)初始化`x`和`y`。*一個公有成員函數(shù)`distanceTo`，用于計算當(dāng)前點與另一個`Point`對象之間的歐幾里得距離，并返回該距離值。六、1.解釋TCP協(xié)議中的三次握手過程。請畫出狀態(tài)轉(zhuǎn)換圖，并說明每一步的目的和通信雙方的確認狀態(tài)。2.簡述HTTP協(xié)議的請求方法（如GET,POST,PUT,DELETE）的基本概念和區(qū)別。一個HTTPGET請求和一個HTTPPOST請求在處理和安全性方面通常有何不同？3.什么是子網(wǎng)劃分（Subnetting）？請解釋為什么需要進行子網(wǎng)劃分，并說明子網(wǎng)掩碼在其中的作用。試卷答案一、1.將元素e與d,c,b依次比較：*e<d，比較1次，e插入到d前面，序列變?yōu)閇a,b,c,e,d]。*e>c，比較2次，不操作，序列保持[a,b,c,e,d]。*e>b，比較3次，不操作，序列保持[a,b,c,e,d]。*e<a，比較4次，e插入到a前面，最終序列變?yōu)閇e,a,b,c,d]?？偣脖容^次數(shù)為4次。2.平衡二叉樹是左右子樹高度差絕對值不超過1的二叉搜索樹。進行單旋操作的目的是調(diào)整因插入或刪除節(jié)點導(dǎo)致失衡的子樹，使其恢復(fù)平衡。例如右旋：適用于插入發(fā)生在節(jié)點右子樹的右子樹，導(dǎo)致該節(jié)點右子樹高度比左子樹高2。右旋將該節(jié)點與其右子節(jié)點交換父節(jié)點位置，并將原父節(jié)點的左子樹（如果存在）變?yōu)樾赂腹?jié)點的右子樹。旋轉(zhuǎn)后，新父節(jié)點的高度與原節(jié)點高度之差不超過1，且其左右子樹高度之差絕對值不超過1，從而保持整個樹的平衡。3.冒泡排序：通過重復(fù)遍歷待排序序列，比較相鄰元素，若逆序則交換，直到?jīng)]有逆序?qū)Αr間復(fù)雜度：最好O(n)，最壞O(n^2)，平均O(n^2)?？焖倥判颍哼x擇一個基準(zhǔn)元素，將序列劃分為兩部分，使得左部分所有元素小于基準(zhǔn)，右部分所有元素大于基準(zhǔn)，然后遞歸地對兩部分進行快速排序。時間復(fù)雜度：最好O(nlogn)，最壞O(n^2)，平均O(nlogn)。歸并排序：將待排序序列遞歸分解為子序列，直到子序列長度為1，然后合并子序列，每次合并時將兩個有序子序列合并為一個有序序列。時間復(fù)雜度：最好、最壞、平均均為O(nlogn)。二、1.指令執(zhí)行順序及時鐘周期：*LOADR1,[1000]：取指(1)+譯碼(1)+訪存(2)+執(zhí)行(3)=7周期。*LOADR2,[2000]：取指(1)+譯碼(1)+訪存(2)+執(zhí)行(3)=7周期。*ADDR3,R1,R2：取指(1)+譯碼(1)+執(zhí)行(3)=5周期。*STORER3,[3000]：取指(1)+譯碼(1)+訪存(2)+執(zhí)行(3)=7周期?？倳r鐘周期數(shù)=7+7+5+7=26周期。2.總線主控是指引和控制系統(tǒng)總線操作的主設(shè)備。在典型的CPU-主存系統(tǒng)中，CPU通常是總線主控。因為CPU需要頻繁地與主存進行數(shù)據(jù)交換（讀取指令、讀取/寫入數(shù)據(jù)），它負責(zé)發(fā)起總線請求、獲得總線使用權(quán)，并控制數(shù)據(jù)在總線上的傳輸。三、1.根據(jù)LRU算法，選擇最久未使用的頁進行置換。進程A當(dāng)前使用的頁是0和3。進程B當(dāng)前使用的頁是1和4?？臻e頁是2和4。因為需要置換進程A的頁，比較進程A使用的頁0和3：頁0最后使用是在LOADR1,[1000]后，頁3最后使用是在分配頁框3時。若假設(shè)在訪問第4頁前未訪問過頁0和3，則LRU策略下通常優(yōu)先置換更早分配或更早使用的頁。若假設(shè)訪問順序是LOADR1,[1000](用0),LOADR2,[2000](用1),訪問第4頁(用4)，則頁0最后使用。因此，應(yīng)將進程A的頁0先置換出去。選擇頁0的理由是其（在此假設(shè)情境下）是進程A中最后被訪問的頁。2.操作系統(tǒng)內(nèi)核是操作系統(tǒng)的核心部分，運行在特權(quán)級，直接管理硬件資源，提供系統(tǒng)調(diào)用接口。主要功能包括進程管理（調(diào)度、創(chuàng)建、終止）、內(nèi)存管理（分配、回收、保護）、設(shè)備管理（驅(qū)動、控制、分配）、文件系統(tǒng)管理以及提供系統(tǒng)調(diào)用接口等。它在計算機系統(tǒng)中處于基礎(chǔ)地位，是用戶程序與硬件之間的橋梁。3.接收方發(fā)送的確認號是`2000|(窗口大小<<12)`。因為接收窗口大小為4KB(4096)，即`4096=2^12`。所以接收方發(fā)送的確認號=`2000|(4096)`=`2000|0x1000`=`0x3000`。發(fā)送方收到確認號0x3000后，通告的窗口大小為`接收方總緩沖區(qū)大小-已接收但未確認的數(shù)據(jù)大小`。假設(shè)接收方總緩沖區(qū)大小為8KB(8192)，已接收但未確認的數(shù)據(jù)是序列號2000-2007的數(shù)據(jù)（共8字節(jié)）。則通告窗口大小=`8192-8=8184`。若表示為2的冪，則`8184=2^13-16`，但通常窗口通告以2的冪或其減去一定值表示。這里直接計算差值，通告窗口大小為8184。四、1.OSI七層模型：應(yīng)用層（用戶接口）、表示層（數(shù)據(jù)格式）、會話層（建立/管理連接）、傳輸層（端到端連接）、網(wǎng)絡(luò)層（路由選擇）、數(shù)據(jù)鏈路層（介質(zhì)訪問/幀傳輸）、物理層（比特傳輸）。各層在數(shù)據(jù)發(fā)送時添加對應(yīng)層頭部信息（包含地址、控制、校驗等），接收時移除。發(fā)送：應(yīng)用層->表示層->會話層->傳輸層->網(wǎng)絡(luò)層->數(shù)據(jù)鏈路層->物理層。接收：物理層->數(shù)據(jù)鏈路層->網(wǎng)絡(luò)層->傳輸層->會話層->表示層->應(yīng)用層。2.CSMA/CD（載波偵聽多路訪問/沖突檢測）工作原理：發(fā)送前先偵聽信道是否空閑。若空閑則發(fā)送，若忙則等待。發(fā)送過程中持續(xù)監(jiān)聽信道，若檢測到?jīng)_突（發(fā)送信號與監(jiān)聽信號不一致），則立即停止發(fā)送，并發(fā)送一個短暫沖突加強信號。隨后隨機退避一段時間后重發(fā)。沖突解決：同時發(fā)送的主機檢測到?jīng)_突后都停止發(fā)送，并執(zhí)行退避算法。3.IP地址是網(wǎng)絡(luò)層地址，用于在不同網(wǎng)絡(luò)間路由數(shù)據(jù)包，是邏輯地址。MAC地址是數(shù)據(jù)鏈路層地址，用于同一局域網(wǎng)內(nèi)識別具體設(shè)備接口，是物理地址。在TCP/IP協(xié)議棧中，需要IP地址實現(xiàn)跨網(wǎng)絡(luò)尋址和路由，需要MAC地址實現(xiàn)同一鏈路上的幀交付。五、1.指針是C/C++中一種變量，存儲內(nèi)存地址，通過地址間接訪問和操作內(nèi)存數(shù)據(jù)。引用是C++中一種別名機制，是已定義變量的另一個名稱，它本身不占用內(nèi)存空間，必須與一個有效對象綁定。區(qū)別：指針可以指向NULL，可以重新指向其他對象；引用必須初始化且不能改變所引用的對象。2.```cppdoubleaverage(int*array,intsize){if(size==0)return0;doublesum=0;for(inti=0;i<size;++i){sum+=array[i];}returnsum/size;}```3.```cppclassPoint{private:doublex,y;public:Point(doublepx,doublepy):x(px),y(py){}//構(gòu)造函數(shù)doubledistanceTo(constPoint&other)const{doubledx=x-other.x;doubledy=y-other.y;returnsqrt(dx*dx+dy*dy);//歐幾里得距離}};```六、1.TCP三次握手：1.客戶端發(fā)送SYN=1,序列號seq=x的連接請求報文段給服務(wù)器。進入SYN_SENT狀態(tài)。2.服務(wù)器收到請求，若同意連接，回復(fù)SYN=1,ACK=1,序列號seq=y,確認號ack=x+1的報文段。進入SYN_RCVD狀態(tài)。3.客戶端收到確認，發(fā)送SYN=0,ACK=1,確認號ack=y+1的報文段。進入ESTABLISHED狀態(tài)。服務(wù)器收到確認后也進入ESTABLISHED狀態(tài)。狀態(tài)轉(zhuǎn)換圖（文字描述）：SYN_SENT->(收到SYN+ACK)ESTABLISHED；SYN_RCVD->(收到ACK)ESTABLISHED。目的：客戶端發(fā)起連接，服務(wù)器確認，客戶端再次確認，雙方確認對方可達并可通信。2.HTTP請求方法：*GET：用于請求獲取資源。請求參數(shù)在URL中（?之后）。無副作用，可緩存。*POST：用于提交數(shù)據(jù)以供服務(wù)器處理（如創(chuàng)建/更新資源）。請求參數(shù)在請求體中。有副作用，不可緩存。*PUT：用于更新指定資源或創(chuàng)建資源（若URL不存在）。請求體包含完整資源數(shù)據(jù)。*D