北航計算機(jī)科學(xué)與技術(shù)（空天計算）專業(yè)2025年考試試題及答案解析考試時間：______分鐘總分：______分姓名：______一、簡答題（每題8分，共32分）1.請簡述數(shù)據(jù)結(jié)構(gòu)中棧和隊列的基本特性，并各舉一個其在計算機(jī)系統(tǒng)或應(yīng)用程序中應(yīng)用的具體例子。2.操作系統(tǒng)中引入虛擬內(nèi)存的主要目的是什么？簡述頁面置換算法的基本思想，并比較LRU和FIFO兩種算法的優(yōu)缺點。3.以TCP協(xié)議為例，簡述三次握手過程及其在建立可靠連接中的作用。指出TCP協(xié)議為了保證數(shù)據(jù)傳輸?shù)目煽啃院晚樞蛐裕辽傩枰褂媚娜齻€主要的機(jī)制。4.嵌入式系統(tǒng)通常具有資源受限的特點，請列舉至少三種嵌入式系統(tǒng)中常用的實時操作系統(tǒng)（RTOS）設(shè)計特點，并說明選擇RTOS的原因。二、計算題（每題12分，共24分）5.設(shè)有數(shù)組元素A=[12,5,8,9,3,2,15,7]，請分別寫出使用快速排序和歸并排序?qū)進(jìn)行排序的簡要過程（無需寫完整代碼，只需描述關(guān)鍵步驟或關(guān)鍵元素的變動情況即可）。6.假設(shè)一個嵌入式系統(tǒng)中的實時任務(wù)T1和T2需要共享一個臨界資源。T1的優(yōu)先級為P1，T2的優(yōu)先級為P2（P1>P2）。請簡述采用基于優(yōu)先級的搶占式調(diào)度策略時，T1和T2在訪問臨界資源時可能遇到的問題（如優(yōu)先級反轉(zhuǎn)），并簡要說明一種解決該問題的方法（如優(yōu)先級繼承）的基本思想。三、綜合應(yīng)用題（每題18分，共36分）7.假設(shè)你需要設(shè)計一個用于衛(wèi)星地面站的數(shù)據(jù)處理模塊，該模塊需要實時接收來自某顆地球同步軌道衛(wèi)星的遙測數(shù)據(jù)流，并對數(shù)據(jù)進(jìn)行初步處理（如解碼、格式轉(zhuǎn)換）后存儲。請考慮該模塊在硬件選型、軟件架構(gòu)和系統(tǒng)設(shè)計方面可能需要考慮的關(guān)鍵因素，并簡要闡述你的設(shè)計思路。需要特別關(guān)注實時性、數(shù)據(jù)可靠性和處理效率這幾個方面。8.在航空航天領(lǐng)域，信息的安全性和保密性至關(guān)重要。請選擇一種常見的對稱加密算法（如DES、AES）或非對稱加密算法（如RSA），簡述其基本工作原理。然后，設(shè)想一個具體的場景（如地面控制中心與飛行器之間的指令傳輸），說明在該場景下如何運用你所選的加密算法來保證指令的機(jī)密性和完整性。試卷答案一、簡答題1.棧：基本特性是后進(jìn)先出（LIFO）。元素只能在棧頂進(jìn)行插入（push）和刪除（pop）操作。例子：函數(shù)調(diào)用棧，用于保存函數(shù)調(diào)用時的局部變量和返回地址；表達(dá)式求值，使用棧處理運算符和操作數(shù)。解析思路：首先明確棧LIFO的定義和操作位置。然后結(jié)合計算機(jī)科學(xué)中的典型應(yīng)用實例，如函數(shù)調(diào)用管理（系統(tǒng)自動使用）和表達(dá)式轉(zhuǎn)換/求值（算法設(shè)計中常用）。2.隊列：基本特性是先進(jìn)先出（FIFO）。元素在隊尾入隊（enqueue），在隊頭出隊（dequeue）。例子：打印隊列，管理等待打印的任務(wù)；消息隊列，在多線程或分布式系統(tǒng)中傳遞消息。解析思路：首先明確隊列FIFO的定義和操作位置。然后結(jié)合操作系統(tǒng)和應(yīng)用程序中的典型應(yīng)用實例，如任務(wù)調(diào)度、消息通信等。3.虛擬內(nèi)存目的：主要目的是讓應(yīng)用程序擁有比物理內(nèi)存更大的地址空間，提高內(nèi)存利用率，實現(xiàn)多個程序并發(fā)執(zhí)行。頁面置換算法思想：當(dāng)需要訪問的頁面不在內(nèi)存時，選擇一個頁面將其移出到磁盤（交換空間），以騰出空間給新的頁面。LRU（最近最少使用）：替換最長時間未被訪問的頁面。優(yōu)點：通常能較好地反映程序的局部性原理，性能較好。缺點：需要硬件支持（如棧）來高效追蹤頁面使用情況，實現(xiàn)復(fù)雜。FIFO（先進(jìn)先出）：替換最先進(jìn)入內(nèi)存的頁面。優(yōu)點：實現(xiàn)簡單。缺點：可能將經(jīng)常使用的頁面（即使它們進(jìn)入內(nèi)存時間較早）置換出去，導(dǎo)致性能不佳，存在Belady現(xiàn)象。解析思路：首先回答虛擬內(nèi)存的核心目的。然后解釋頁面置換的基本概念。接著分別闡述LRU和FIFO算法的原理，并清晰對比兩者的優(yōu)缺點。4.RTOS特點：（1）任務(wù)調(diào)度效率高，通常采用搶占式或輪轉(zhuǎn)式等簡單高效的調(diào)度算法；（2）提供豐富的系統(tǒng)服務(wù)接口，方便應(yīng)用程序開發(fā)；（3）資源管理能力強(qiáng)，對內(nèi)存、中斷、信號量等有精妙的管理機(jī)制；（4）代碼規(guī)模小，實時性好，可裁剪性強(qiáng)。選擇RTOS原因：航空航天任務(wù)通常具有實時性要求（如控制指令必須在規(guī)定時間內(nèi)執(zhí)行），系統(tǒng)資源（CPU、內(nèi)存、I/O）往往有限，需要專業(yè)操作系統(tǒng)進(jìn)行有效管理和調(diào)度，確保系統(tǒng)可靠、高效運行。解析思路：列舉RTOS區(qū)別于通用操作系統(tǒng)的幾個關(guān)鍵設(shè)計特點。然后解釋選擇RTOS是為了滿足航空航天應(yīng)用在實時性、資源受限環(huán)境下的特定需求。二、計算題5.快速排序過程：選擇基準(zhǔn)元素（如第一個元素12），經(jīng)過一輪劃分，數(shù)組可能變?yōu)閇5,8,3,2,7,9,15,12]。再對子數(shù)組[5,8,3,2,7]和[9,15,7,12]遞歸進(jìn)行快速排序（省略后續(xù)細(xì)節(jié)）。解析思路：快速排序核心是劃分。選擇一個基準(zhǔn)，將數(shù)組分為兩部分，使得左部分所有元素小于基準(zhǔn)，右部分所有元素大于基準(zhǔn)。描述過程中關(guān)鍵元素的變動情況或數(shù)組片段的形態(tài)變化即可。6.優(yōu)先級反轉(zhuǎn)問題：低優(yōu)先級任務(wù)L（P2）持有高優(yōu)先級任務(wù)H（P1）需要的資源，而一個中等優(yōu)先級任務(wù)M（P_mid，P1>P_mid>P2）就緒。此時，H需要資源但被阻塞，M雖然優(yōu)先級低于H，但由于L持有資源且L的優(yōu)先級低于M，M會持續(xù)運行，阻止H運行。這導(dǎo)致優(yōu)先級高的任務(wù)H反而等待優(yōu)先級低的任務(wù)L，違背了優(yōu)先級調(diào)度原則。解析思路：清晰描述優(yōu)先級反轉(zhuǎn)發(fā)生的條件：存在一個優(yōu)先級更高的任務(wù)被優(yōu)先級介于它們之間的任務(wù)阻塞。解釋為什么這種阻塞是不合理的，即低優(yōu)先級任務(wù)阻止了高優(yōu)先級任務(wù)的執(zhí)行。優(yōu)先級繼承思想：當(dāng)發(fā)生優(yōu)先級反轉(zhuǎn)時，將持有資源的低優(yōu)先級任務(wù)L的優(yōu)先級臨時提升到高優(yōu)先級任務(wù)H的優(yōu)先級（或兩者中的最高優(yōu)先級），直到它釋放資源。這樣，如果有更高優(yōu)先級的任務(wù)就緒，它能搶占L的執(zhí)行，從而讓H能夠盡快獲得資源繼續(xù)執(zhí)行。解析思路：首先準(zhǔn)確描述優(yōu)先級反轉(zhuǎn)現(xiàn)象及其場景。然后解釋其不合理之處。最后闡述優(yōu)先級繼承機(jī)制的基本原理，說明其如何解決該問題。三、綜合應(yīng)用題7.數(shù)據(jù)處理模塊設(shè)計考慮與思路：考慮因素：（1）實時性：數(shù)據(jù)接收和處理延遲必須滿足衛(wèi)星下行鏈路速率和地面站應(yīng)用需求，可能需要采用實時操作系統(tǒng)和硬件加速；（2）數(shù)據(jù)可靠性：需設(shè)計冗余接收、錯誤檢測與糾正（如CRC校驗、重傳機(jī)制）機(jī)制，確保數(shù)據(jù)完整性；（3）處理效率：算法需高效，可能涉及并行處理或流式處理技術(shù)，以匹配高速數(shù)據(jù)流；（4）資源限制：嵌入式平臺資源（CPU、內(nèi)存、存儲）有限，設(shè)計需注重軟硬件資源優(yōu)化；（5）接口兼容性：需與衛(wèi)星下行鏈路設(shè)備（天線、接收機(jī)）及地面應(yīng)用系統(tǒng)（數(shù)據(jù)庫、顯示終端）接口匹配；（6）可擴(kuò)展性與維護(hù)性：設(shè)計應(yīng)便于未來升級和故障排查。設(shè)計思路：采用分層架構(gòu)。底層負(fù)責(zé)與硬件對接，實現(xiàn)數(shù)據(jù)的實時捕獲和預(yù)處理（如FEC解碼）；中間層進(jìn)行核心數(shù)據(jù)處理（如格式轉(zhuǎn)換、數(shù)據(jù)清洗、解碼），可設(shè)計為基于事件的微服務(wù)架構(gòu)以提高并發(fā)處理能力；上層提供應(yīng)用接口，支持?jǐn)?shù)據(jù)存儲、查詢和可視化。關(guān)鍵在于選擇合適的硬件平臺（如高性能嵌入式CPU、FPGA）和實時操作系統(tǒng)，并針對數(shù)據(jù)處理任務(wù)進(jìn)行算法優(yōu)化和并行化設(shè)計。解析思路：從系統(tǒng)設(shè)計的角度，全面考慮實時性、可靠性、效率、資源、接口、可維護(hù)性等關(guān)鍵要素。然后提出一個清晰的結(jié)構(gòu)化設(shè)計思路，說明如何通過分層架構(gòu)和關(guān)鍵技術(shù)選型來滿足這些要求。8.加密算法選擇與應(yīng)用（以AES為例）：基本原理（AES）：AES是一種對稱加密算法，使用相同的密鑰進(jìn)行加密和解密。其基本結(jié)構(gòu)基于代數(shù)運算（主要是有限域運算），通過多層替換（Substitution）和置換（Permutation）操作（如SPN結(jié)構(gòu)中的輪函數(shù)）來混淆數(shù)據(jù)，實現(xiàn)保密性。密鑰長度有128位、192位、256位，輪數(shù)也不同，安全性隨密鑰長度增加而提高。應(yīng)用場景（指令傳輸）：在地面控制中心（GCC）向飛行器發(fā)送指令時，首先將指令明文和AES密鑰（雙方預(yù)先共享并可能通過安全信道交換或存儲在安全模塊中）輸入AES加密算法。AES生成密文輸出。GCC通過無線通信鏈路將密文發(fā)送給飛行器。飛行器端的接收系統(tǒng)使用相同的密鑰，將接收到的密文輸入AES解密算法，得到解密后的明文指令。這樣，即使通信鏈路被竊聽，攻擊者僅能得到無法直接解讀的密文，必須知道密鑰才能解密獲取指令內(nèi)容，從而保證了指令的機(jī)密性。為了保證完整性，可以在指令數(shù)據(jù)后附加由