2025年計(jì)算機(jī)408專項(xiàng)沖刺押題考試時(shí)間：______分鐘總分：______分姓名：______一、單項(xiàng)選擇題（每小題2分，共20分。下列每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的。請(qǐng)將正確選項(xiàng)前的字母填涂在答題卡相應(yīng)位置。）1.在下列數(shù)據(jù)結(jié)構(gòu)中，適合用來表示稀疏矩陣的是（）。A.鏈棧B.隊(duì)列C.稀疏矩陣壓縮存儲(chǔ)（三元組表）D.完全二叉樹2.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，依次對(duì)棧S和隊(duì)列Q進(jìn)行入棧、出棧、入隊(duì)、出隊(duì)、入棧、出棧操作，則棧S和隊(duì)列Q中的元素依次為（）。A.S:abc,Q:a,b,cB.S:ac,Q:a,b,cC.S:cba,Q:a,b,cD.S:bac,Q:a,b,c3.若一棵二叉樹的前序遍歷序列為ABCD，中序遍歷序列為BADC，則其后序遍歷序列為（）。A.DCBAB.BADCC.DBCAD.ADCB4.下列關(guān)于B樹和B+樹的說法中，正確的是（）。A.B樹和B+樹都是多路平衡搜索樹B.B樹的任何非葉結(jié)點(diǎn)的子樹數(shù)目都相等，B+樹不一定C.B+樹的所有數(shù)據(jù)記錄都存儲(chǔ)在葉結(jié)點(diǎn)中，B樹不一定D.B樹和B+樹都只能進(jìn)行插人和刪除操作，不能進(jìn)行查找操作5.圖G的鄰接矩陣為稀疏矩陣，則該圖一定是（）。A.無向圖B.有向圖C.稀疏圖D.空?qǐng)D6.對(duì)一個(gè)有n個(gè)頂點(diǎn)的無向圖進(jìn)行廣度優(yōu)先遍歷，其算法的時(shí)間復(fù)雜度為（）。A.O(n)B.O(n+e)C.O(e)D.O(n^2)7.下列排序算法中，worst-case時(shí)間復(fù)雜度不是O(n^2)的是（）。A.快速排序B.冒泡排序C.插入排序D.堆排序8.某計(jì)算機(jī)的Cache采用直接映射方式，Cache容量為16KB，主存容量為1MB，每個(gè)主存塊大小為4KB。則主存地址1000H所在塊在Cache中的塊號(hào)為（）。A.0B.16C.256D.40969.采用虛擬內(nèi)存管理技術(shù)的目的是（）。A.實(shí)現(xiàn)程序的浮動(dòng)加載B.提高主存利用率C.擴(kuò)大邏輯地址空間D.以上都是10.在TCP/IP協(xié)議簇中，負(fù)責(zé)將IP地址解析為物理地址的協(xié)議是（）。A.IP協(xié)議B.TCP協(xié)議C.UDP協(xié)議D.ARP協(xié)議二、簡(jiǎn)答題（每小題5分，共20分。）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別和共同點(diǎn)。2.解釋什么是數(shù)據(jù)結(jié)構(gòu)的“平攤性”，并舉例說明。3.在頁式存儲(chǔ)管理中，當(dāng)發(fā)生缺頁中斷時(shí)，操作系統(tǒng)通常需要執(zhí)行哪些操作？4.簡(jiǎn)述TCP協(xié)議與UDP協(xié)議的主要區(qū)別。三、計(jì)算題（每小題10分，共30分。）1.設(shè)有數(shù)據(jù)序列（12,56,87,99,34,78,56,23）。請(qǐng)分別寫出使用快速排序和歸并排序?qū)υ撔蛄羞M(jìn)行排序的第一趟（或前兩趟）結(jié)果。（假設(shè)快速排序以第一個(gè)元素為基準(zhǔn)，歸并排序采用2路歸并）2.一個(gè)計(jì)算機(jī)系統(tǒng)，主存容量為256MB，Cache容量為32KB，采用4路組相聯(lián)映射方式。若主存塊大小為16KB，Cache未命中時(shí)從主存讀取數(shù)據(jù)。請(qǐng)計(jì)算地址A2FCH所在數(shù)據(jù)塊在Cache中的標(biāo)記（Tag）和組號(hào)（SetIndex）。（假設(shè)物理地址由標(biāo)記Tag、組號(hào)SetIndex和塊內(nèi)地址Offset組成）3.設(shè)有一個(gè)網(wǎng)絡(luò)連接，其帶寬為1Mbps，傳播延遲為100ms。若使用TCP的慢啟動(dòng)算法，請(qǐng)計(jì)算發(fā)送窗口大小為2時(shí)，發(fā)送方可以發(fā)送多少字節(jié)的數(shù)據(jù)？（假設(shè)每字節(jié)傳輸時(shí)間忽略不計(jì)，忽略其他TCP機(jī)制的影響）四、綜合應(yīng)用題（每小題15分，共30分。）1.設(shè)有一個(gè)循環(huán)隊(duì)列，用數(shù)組Q[0..m-1]實(shí)現(xiàn)，初始時(shí)隊(duì)列為空（front=rear=m）。請(qǐng)寫出實(shí)現(xiàn)以下操作的算法偽代碼或描述：(1)入隊(duì)（Enqueue）操作(2)出隊(duì)（Dequeue）操作(3)判斷隊(duì)列是否為空操作2.假設(shè)一個(gè)計(jì)算機(jī)系統(tǒng)中有多個(gè)進(jìn)程需要訪問共享資源S，為了防止進(jìn)程競(jìng)爭(zhēng)條件，需要使用信號(hào)量機(jī)制進(jìn)行同步。請(qǐng)說明：(1)什么是進(jìn)程的競(jìng)爭(zhēng)條件？(2)什么是死鎖？死鎖產(chǎn)生的必要條件有哪些？(3)使用P、V操作（或信號(hào)量機(jī)制）描述如何實(shí)現(xiàn)進(jìn)程對(duì)共享資源S的互斥訪問。---試卷答案一、單項(xiàng)選擇題1.C2.D3.C4.A5.C6.B7.D8.C9.D10.D二、簡(jiǎn)答題1.區(qū)別：棧是先進(jìn)后出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只允許在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，只允許在隊(duì)頭進(jìn)行刪除操作，在隊(duì)尾進(jìn)行插入操作。共同點(diǎn)：棧和隊(duì)列都是線性數(shù)據(jù)結(jié)構(gòu)，都可以用數(shù)組或鏈表實(shí)現(xiàn)，都具有大小限制（如果用固定大小的數(shù)組實(shí)現(xiàn)）。2.平攤性：某些數(shù)據(jù)結(jié)構(gòu)的操作平均性能很好，但偶爾會(huì)執(zhí)行一些時(shí)間復(fù)雜度較高的操作，將這部分開銷攤銷到之前的許多次操作上，使得整體平均性能仍然很好。例如，帶有“刪除最小元素”操作的堆，每次插入操作是O(logn)，而刪除最小元素是O(logn)，但在執(zhí)行n次插入和1次刪除操作時(shí)，總時(shí)間復(fù)雜度是n*O(logn)+O(logn)=O(nlogn)，即每次操作的平均時(shí)間是O(1)。3.缺頁中斷處理：(1)硬件檢測(cè)到缺頁，將缺頁中斷請(qǐng)求信息傳遞給CPU。(2)CPU暫停當(dāng)前進(jìn)程執(zhí)行，保存現(xiàn)場(chǎng)。(3)操作系統(tǒng)根據(jù)缺頁中斷信息，查找所需頁面的磁盤地址。(4)調(diào)用磁盤調(diào)度程序，將包含所需頁面的磁盤塊讀入主存。(5)選擇一個(gè)主存中的頁框進(jìn)行替換（如果該頁框是修改過的，則需先寫回磁盤）。(6)更新頁表或頁目錄項(xiàng)，將新頁的物理地址填入。(7)恢復(fù)被中斷進(jìn)程的現(xiàn)場(chǎng)，繼續(xù)執(zhí)行。4.區(qū)別：TCP是面向連接的、可靠的、基于字節(jié)流的傳輸層協(xié)議，提供數(shù)據(jù)分段、重傳、流量控制、擁塞控制等功能；UDP是無連接的、不可靠的、基于數(shù)據(jù)報(bào)的傳輸層協(xié)議，不提供可靠性保證，速度快，開銷小。三、計(jì)算題1.快速排序：基準(zhǔn)：12。序列：[56,87,99,34,78,56,23,12]。第一趟結(jié)果（部分）：[34,23,12]|[56,87,99,78,56]（注意：快速排序結(jié)果不唯一，此處為一種可能結(jié)果，56與78交換）歸并排序：序列：[12,56,87,99,34,78,56,23]。第一趟歸并（以2為組）：[(12,56),(87,99),(34,78),(56,23)]。第二趟歸并（以4為組）：[(12,56,87,99),(34,56,23,78)]。（注意：歸并排序結(jié)果不唯一，此處為一種可能結(jié)果）2.計(jì)算：主存容量256MB->2^28Byte；Cache容量32KB->2^15Byte；塊大小16KB->2^14Byte。*組相聯(lián)：Cache容量/塊大小=32KB/16KB=2組。即組號(hào)為1位（0,1）。*標(biāo)記Tag=物理地址位數(shù)-組號(hào)位數(shù)-塊內(nèi)地址位數(shù)=28-1-14=13位。*地址A2FCH=1010001011111100B。塊內(nèi)地址Offset=14位（低14位）。組號(hào)SetIndex=1位（第14位，從0開始計(jì)數(shù)，即第15位是組號(hào)）。標(biāo)記Tag=高13位（第0位到第12位）。*標(biāo)記Tag=10100010111B=A27H。組號(hào)SetIndex=0B。塊內(nèi)地址Offset=11111100B=FC0H。3.計(jì)算：帶寬B=1Mbps=1*10^6bps。傳播延遲Tp=100ms=0.1s。*往返傳播延遲RTT=2*Tp=0.2s。*擁塞窗口Cwnd初始為1倍RTT帶寬=RTT*B=0.2s*1*10^6bps=2*10^5bits=25KB。*發(fā)送窗口大小為2，即實(shí)際可發(fā)送量受限于較小者：min(Cwnd,發(fā)送窗口)=min(25KB,2)。*由于題目中發(fā)送窗口大小為2，假設(shè)單位為字節(jié)，則發(fā)送方可以發(fā)送的字節(jié)數(shù)=2字節(jié)。四、綜合應(yīng)用題1.算法描述：(1)Enqueue(x):Q[rear]=x;rear=(rear+1)modm;如果(front==rear)則隊(duì)列為滿（或表示為front==(rear+1)modm）。(2)Dequeue():if(front==rear)then隊(duì)列為空;elsex=Q[front];front=(front+1)modm;returnx;(3)IsEmpty():if(front==rear)thenreturnTrue;elsereturnFalse;2.說明：(1)競(jìng)爭(zhēng)條件：當(dāng)多個(gè)進(jìn)程共享一個(gè)資源，且這些進(jìn)程都處于一個(gè)能夠改變共享資源狀態(tài)的循環(huán)中，如果它們同時(shí)進(jìn)入該循環(huán)，就可能會(huì)因?yàn)樵L問資源的順序不當(dāng)而導(dǎo)致程序狀態(tài)錯(cuò)誤或數(shù)據(jù)不一致。(2)死鎖：死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過程中，因爭(zhēng)奪資源而造