2025年考研計(jì)算機(jī)技術(shù)基礎(chǔ)理論模擬試卷（含答案）考試時(shí)間：______分鐘總分：______分姓名：______一、單項(xiàng)選擇題（每小題2分，共20分。下列每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的。請(qǐng)將正確選項(xiàng)前的字母填在答題卡相應(yīng)位置上。）1.設(shè)有棧S和隊(duì)列Q，初始時(shí)均為空。依次對(duì)棧進(jìn)行入棧操作a,b,c，然后依次將棧中的元素全部出棧并入隊(duì)Q，接著再依次對(duì)隊(duì)列Q進(jìn)行出隊(duì)操作。則隊(duì)列Q中的元素排列順序?yàn)椋ǎ?。A.a,b,cB.c,b,aC.b,c,aD.a,c,b2.已知一個(gè)棧的輸入序列為1,2,3,4,5，則通過?？梢詫?shí)現(xiàn)輸出序列3,1,4,2,5的出棧順序是（）。A.3,2,1,4,5B.3,1,2,5,4C.3,1,4,2,5D.1,2,3,4,53.在下列數(shù)據(jù)結(jié)構(gòu)中，適合用于表示稀疏矩陣的是（）。A.線性表B.二維數(shù)組C.鏈隊(duì)列D.三元組表4.設(shè)數(shù)組A[1..m,1..n]按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，若元素A[i,j]（1≤i≤m,1≤j≤n）的地址為L(zhǎng)oc(A[1,1])+(i-1)*n+(j-1)，則元素A[1,1]在內(nèi)存中的地址為（）。A.Loc(A[1,1])B.Loc(A[1,1])+n-1C.Loc(A[1,1])+nD.Loc(A[1,1])-15.在下列關(guān)于二叉樹的敘述中，正確的是（）。A.完全二叉樹一定不是滿二叉樹B.滿二叉樹一定不是完全二叉樹C.如果一個(gè)非空二叉樹是滿二叉樹，那么它的結(jié)點(diǎn)數(shù)一定是奇數(shù)D.如果一個(gè)非空二叉樹是完全二叉樹，那么它的最下一層從左到右的結(jié)點(diǎn)可能不是連續(xù)的6.對(duì)一個(gè)長(zhǎng)度為n的無序序列進(jìn)行冒泡排序，在最壞情況下需要的比較次數(shù)為（）。A.nB.n+1C.n(n-1)/2D.n(n+1)/27.下列關(guān)于操作系統(tǒng)的敘述中，錯(cuò)誤的是（）。A.操作系統(tǒng)是系統(tǒng)軟件的核心B.操作系統(tǒng)提供了用戶與計(jì)算機(jī)硬件之間的接口C.操作系統(tǒng)可以提高計(jì)算機(jī)系統(tǒng)的資源利用率D.操作系統(tǒng)的主要目標(biāo)是提高計(jì)算機(jī)的運(yùn)行速度8.在下列進(jìn)程狀態(tài)轉(zhuǎn)換中，不可能直接發(fā)生的是（）。A.運(yùn)行態(tài)->就緒態(tài)B.就緒態(tài)->運(yùn)行態(tài)C.運(yùn)行態(tài)->等待態(tài)D.等待態(tài)->運(yùn)行態(tài)9.在虛擬內(nèi)存管理中，常用的頁面置換算法有（）。A.最優(yōu)置換算法B.先進(jìn)先出置換算法（FIFO）C.最近最少使用置換算法（LRU）D.以上都是10.在TCP/IP協(xié)議簇中，負(fù)責(zé)將IP地址轉(zhuǎn)換為物理地址的協(xié)議是（）。A.IP協(xié)議B.TCP協(xié)議C.UDP協(xié)議D.ARP協(xié)議二、填空題（每空2分，共20分。請(qǐng)將答案填在答題卡相應(yīng)位置上。）1.數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合，其邏輯結(jié)構(gòu)主要分為_________結(jié)構(gòu)和_________結(jié)構(gòu)兩大類。2.在隊(duì)列中，插入元素的操作稱為_________，刪除元素的操作稱為_________。3.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度最多為_________。4.快速排序算法的平均時(shí)間復(fù)雜度為_________。5.進(jìn)程控制塊（PCB）是進(jìn)程存在的唯一標(biāo)識(shí)，它通常包含進(jìn)程狀態(tài)、進(jìn)程標(biāo)識(shí)符、程序計(jì)數(shù)器以及_________等信息。6.在分時(shí)系統(tǒng)中，時(shí)間片輪轉(zhuǎn)調(diào)度算法的主要目的是_________。7.設(shè)有n個(gè)資源R，m個(gè)進(jìn)程P，采用銀行家算法進(jìn)行死鎖避免時(shí)，必須滿足條件：對(duì)于每一個(gè)進(jìn)程Pi，其需求矩陣Wi的每一行元素與已分配矩陣Ai的相應(yīng)行元素之和不超過資源矩陣R的最大值向量Max。8.在TCP/IP協(xié)議簇中，傳輸層有兩個(gè)重要的協(xié)議：TCP和UDP，其中_________協(xié)議提供可靠的、面向連接的數(shù)據(jù)傳輸服務(wù)。9.互聯(lián)網(wǎng)中的路由器工作在_________層，其主要功能是在不同的網(wǎng)絡(luò)之間轉(zhuǎn)發(fā)數(shù)據(jù)包。10.以太網(wǎng)（Ethernet）是一種常用的局域網(wǎng)（LAN）技術(shù)，它采用_________介質(zhì)訪問控制方法，允許網(wǎng)絡(luò)上的多個(gè)設(shè)備共享傳輸介質(zhì)。三、判斷題（每小題2分，共10分。請(qǐng)將答案（正確填“√”，錯(cuò)誤填“×”）填在答題卡相應(yīng)位置上。）1.遞歸算法一定能轉(zhuǎn)化為非遞歸算法。（）2.在線性鏈表中，插入和刪除操作比在順序表中更高效。（）3.線性表可以是空表。（）4.若一個(gè)進(jìn)程調(diào)用了P操作，則該進(jìn)程的狀態(tài)一定會(huì)從就緒態(tài)變?yōu)檫\(yùn)行態(tài)。（）5.在理想情況下，Cache的命中率可以達(dá)到100%。（）四、簡(jiǎn)答題（每小題5分，共20分。請(qǐng)將答案寫在答題卡相應(yīng)位置上。）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別。2.什么是樹的深度？什么是樹的高度？3.什么是操作系統(tǒng)的進(jìn)程調(diào)度？簡(jiǎn)述進(jìn)程調(diào)度的功能。4.簡(jiǎn)述計(jì)算機(jī)網(wǎng)絡(luò)OSI參考模型的數(shù)據(jù)鏈路層的主要功能。五、計(jì)算題（每小題10分，共20分。請(qǐng)將答案寫在答題卡相應(yīng)位置上。）1.設(shè)有一個(gè)順序存儲(chǔ)的線性表L，元素依次為(12,23,36,47,58,69,80)。請(qǐng)寫出對(duì)L進(jìn)行二分查找(查找元素36)的查找過程，并說明比較次數(shù)。2.假設(shè)某計(jì)算機(jī)系統(tǒng)有一個(gè)主存，其容量為256MB，采用頁式存儲(chǔ)管理，頁大小為4KB。若某進(jìn)程的地址空間大小為128KB，其中一部分地址空間被劃分為以下三個(gè)頁面：*頁面0：已分配，物理塊號(hào)100*頁面1：已分配，物理塊號(hào)101*頁面2：未分配請(qǐng)問該進(jìn)程當(dāng)前在主存中占用了多少物理塊？其頁表應(yīng)如何表示這三個(gè)頁面？（假設(shè)頁表項(xiàng)只包含物理塊號(hào)）六、綜合應(yīng)用題（每小題15分，共30分。請(qǐng)將答案寫在答題卡相應(yīng)位置上。）1.設(shè)有三個(gè)并發(fā)進(jìn)程P1,P2,P3，它們都需要執(zhí)行一個(gè)共享資源S。資源S初始時(shí)可用1個(gè)單位。為了防止發(fā)生死鎖，請(qǐng)?jiān)O(shè)計(jì)一個(gè)同步機(jī)制（使用P、V操作），確保這三個(gè)進(jìn)程能夠正確地訪問資源S。2.簡(jiǎn)述TCP協(xié)議的可靠數(shù)據(jù)傳輸機(jī)制是如何工作的。主要包含哪些關(guān)鍵技術(shù)？（請(qǐng)結(jié)合TCP報(bào)文段的序列號(hào)、確認(rèn)號(hào)、SYN、ACK、RST等標(biāo)志位的作用進(jìn)行說明）---試卷答案一、單項(xiàng)選擇題1.C2.C3.D4.C5.D6.D7.D8.D9.D10.D二、填空題1.線性非線性2.入隊(duì)出隊(duì)3.n4.O(n^2)（注：快速排序平均復(fù)雜度為O(nlogn)，但題目選項(xiàng)未出現(xiàn)，此處按常規(guī)選擇題可能存在的印刷錯(cuò)誤或考察其他排序如冒泡的復(fù)雜度O(n^2)填寫，實(shí)際考研中應(yīng)以O(shè)(nlogn)為準(zhǔn)，若無O(nlogn)選項(xiàng)則需核實(shí)題目）5.資源分配表6.提高系統(tǒng)的吞吐量7.資源最大需求量8.TCP9.網(wǎng)絡(luò)10.CSMA/CD三、判斷題1.×2.×3.√4.×5.×四、簡(jiǎn)答題1.答：棧是先進(jìn)后出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，其插入和刪除操作都限定在表的同一端進(jìn)行；隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，其插入操作在表的一端進(jìn)行，刪除操作在另一端進(jìn)行。2.答：樹的深度是指樹根到某個(gè)結(jié)點(diǎn)的最長(zhǎng)路徑上經(jīng)過的邊數(shù)；樹的高度是指樹中結(jié)點(diǎn)的最大深度，通常指樹根的深度。3.答：進(jìn)程調(diào)度是指操作系統(tǒng)動(dòng)態(tài)地把CPU的使用權(quán)分配給某個(gè)就緒態(tài)進(jìn)程的過程。其功能包括：從就緒隊(duì)列中選擇一個(gè)進(jìn)程，并將CPU的使用權(quán)分配給它，即將進(jìn)程的狀態(tài)由就緒態(tài)變?yōu)檫\(yùn)行態(tài)。4.答：數(shù)據(jù)鏈路層的主要功能包括：幀的封裝與解封裝（將網(wǎng)絡(luò)層數(shù)據(jù)包封裝成幀）、差錯(cuò)控制（通過校驗(yàn)碼等方式檢測(cè)并糾正傳輸中的錯(cuò)誤）、流量控制（控制數(shù)據(jù)傳輸速率，防止快速發(fā)送方淹沒慢速接收方）、介質(zhì)訪問控制（在多結(jié)點(diǎn)共享傳輸介質(zhì)的網(wǎng)絡(luò)中，決定哪個(gè)結(jié)點(diǎn)可以使用介質(zhì)）。五、計(jì)算題1.答：二分查找過程如下：*初始：low=1,high=7,mid=(1+7)/2=4。L[mid]=58≠36。因?yàn)?6<58，所以搜索左半部分。更新high=mid-1=3。*第二次：low=1,high=3,mid=(1+3)/2=2。L[mid]=47≠36。因?yàn)?6<47，所以搜索左半部分。更新high=mid-1=1。*第三次：low=1,high=1,mid=(1+1)/2=1。L[mid]=23≠36。因?yàn)?6>23，所以搜索右半部分。更新low=mid+1=2。*此時(shí)low>high，查找失敗。比較次數(shù)為3次。2.答：*進(jìn)程地址空間大小為128KB，頁大小為4KB，則需頁數(shù)128KB/4KB=32頁。*已分配頁面0和頁面1，共占用2個(gè)物理塊（因?yàn)轫撁?對(duì)應(yīng)物理塊100，頁面1對(duì)應(yīng)物理塊101）。*頁面2未分配，不占用物理塊。*該進(jìn)程當(dāng)前在主存中占用了2個(gè)物理塊。*頁表表示：*頁面0：物理塊號(hào)100*頁面1：物理塊號(hào)101*頁面2：未分配（或用特定標(biāo)記表示，如“-1”或“空”）六、綜合應(yīng)用題1.答：使用信號(hào)量S初始化為1（表示資源S有1個(gè)單位可用），P操作和V操作定義如下：P(S):S=S-1;V(S):S=S+1;同步機(jī)制如下：P1:P(S);//申請(qǐng)資源S...執(zhí)行操作...V(S);//釋放資源SP2:P(S);//申請(qǐng)資源S...執(zhí)行操作...V(S);//釋放資源SP3:P(S);//申請(qǐng)資源S...執(zhí)行操作...V(S);//釋放資源S其中，P操作（Proberen，測(cè)試）用于申請(qǐng)資源，若S>0，則S減1，進(jìn)程繼續(xù)執(zhí)行；若S=0，則進(jìn)程阻塞，等待資源。V操作（Verhogen，增加）用于釋放資源，S加1，若此時(shí)有阻塞的進(jìn)程，則選擇一個(gè)喚醒繼續(xù)執(zhí)行。該機(jī)制保證了在任何時(shí)刻最多只有一個(gè)進(jìn)程能獲得資源S，從而避免了死鎖。2.答：TCP協(xié)議的可靠數(shù)據(jù)傳輸機(jī)制主要通過以下關(guān)鍵技術(shù)實(shí)現(xiàn)：*序列號(hào)（SequenceNumber）和確認(rèn)號(hào)（AcknowledgmentNumber）：TCP將數(shù)據(jù)分成多個(gè)段進(jìn)行傳輸。每個(gè)段都包含一個(gè)序列號(hào)，該序列號(hào)是當(dāng)前段中數(shù)據(jù)字節(jié)流的第一個(gè)字節(jié)的編號(hào)。接收方收到數(shù)據(jù)段后，會(huì)發(fā)送一個(gè)確認(rèn)段，其中包含一個(gè)確認(rèn)號(hào)，該確認(rèn)號(hào)表示接收方期望收到的下一個(gè)字節(jié)的序列號(hào)。通過序列號(hào)和確認(rèn)號(hào)，發(fā)送方可以知道哪些數(shù)據(jù)已被接收方確認(rèn)，哪些數(shù)據(jù)需要重傳。*超時(shí)重傳（TimeoutRetransmission）：發(fā)送方在發(fā)送數(shù)據(jù)段后會(huì)啟動(dòng)一個(gè)計(jì)時(shí)器。如果在計(jì)時(shí)器超時(shí)之前沒有收到接收方的確認(rèn)，發(fā)送方會(huì)認(rèn)為數(shù)據(jù)段丟失或確認(rèn)段丟失，于是重新發(fā)送該數(shù)據(jù)段。超時(shí)時(shí)間通?；谕禃r(shí)間（RTT）估算。*快速重傳（FastRetransmit）：基于累積確認(rèn)機(jī)制，接收方在收到一個(gè)失序的數(shù)據(jù)段時(shí)，會(huì)緩存該數(shù)據(jù)段，并向上層交付按序到達(dá)的數(shù)據(jù)。當(dāng)接收方收到一個(gè)失序段的確認(rèn)時(shí)，它會(huì)檢查緩存，如果發(fā)現(xiàn)缺少多個(gè)連續(xù)的失序段，它會(huì)立即發(fā)送一個(gè)探測(cè)報(bào)文（僅包含ACK，序列號(hào)為缺失段的最小序列號(hào)），如果探測(cè)報(bào)文在超時(shí)前未被確認(rèn)，則進(jìn)行重傳。這比等待超時(shí)更高效。*校驗(yàn)和（Checksum）：TCP報(bào)文段包含一個(gè)校驗(yàn)和字段，用于檢測(cè)數(shù)據(jù)在傳輸過程中是否發(fā)生錯(cuò)誤。接收方會(huì)計(jì)算接收到的報(bào)文段的校驗(yàn)和，如果計(jì)算結(jié)果不為零，則認(rèn)為報(bào)文段已損壞，會(huì)丟棄該報(bào)文段，并向發(fā)送方發(fā)送一個(gè)失序段的確認(rèn)（如果適用），迫使發(fā)送方重傳該報(bào)文段。