北京航空航天大學(xué)2025年計(jì)算機(jī)科學(xué)與技術(shù)（空天計(jì)算）研究生入學(xué)考試試題及答案考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每小題2分，共20分。請(qǐng)將正確選項(xiàng)填在題后的括號(hào)內(nèi)）1.下列數(shù)據(jù)結(jié)構(gòu)中，適合用來實(shí)現(xiàn)先進(jìn)先出（FIFO）數(shù)據(jù)結(jié)構(gòu)的是（）。A.棧B.隊(duì)列C.樹D.圖2.在二叉搜索樹中，每個(gè)節(jié)點(diǎn)的左子樹只包含小于該節(jié)點(diǎn)的值，右子樹只包含大于該節(jié)點(diǎn)的值。下列序列中，可以構(gòu)建成一棵二叉搜索樹的是（）。A.(8,3,10,1,6,14,4,7,13)B.(10,8,6,3,1,4,7,14,13)C.(3,8,1,6,4,10,14,7,13)D.(1,3,6,8,4,10,14,7,13)3.計(jì)算機(jī)中，Cache的目的是（）。A.提高主存的容量B.提高主存的讀寫速度C.增加CPU的運(yùn)算速度D.減少硬盤的讀寫次數(shù)4.在多道程序設(shè)計(jì)中，操作系統(tǒng)通過（）來管理多個(gè)進(jìn)程的執(zhí)行。A.通道B.中斷C.調(diào)度算法D.磁盤碎片整理5.下列關(guān)于TCP和UDP協(xié)議的描述中，正確的是（）。A.TCP提供面向連接的、可靠的傳輸服務(wù)，UDP提供面向無連接的、不可靠的傳輸服務(wù)B.TCP提供面向無連接的、不可靠的傳輸服務(wù)，UDP提供面向連接的、可靠的傳輸服務(wù)C.TCP和UDP都提供面向連接的、可靠的傳輸服務(wù)D.TCP和UDP都提供面向無連接的、不可靠的傳輸服務(wù)6.將十進(jìn)制數(shù)123轉(zhuǎn)換為二進(jìn)制數(shù)是（）。A.1111011B.1110111C.1100111D.10111117.在指令執(zhí)行過程中，將指令從內(nèi)存取到CPU的部件是（）。A.運(yùn)算器B.控制器C.存儲(chǔ)器D.總線8.下列關(guān)于操作系統(tǒng)的敘述中，錯(cuò)誤的是（）。A.操作系統(tǒng)是系統(tǒng)軟件的核心B.操作系統(tǒng)可以提高計(jì)算機(jī)系統(tǒng)的資源利用率C.操作系統(tǒng)可以為用戶程序提供方便的運(yùn)行環(huán)境D.操作系統(tǒng)可以代替編譯程序進(jìn)行程序翻譯9.在計(jì)算機(jī)網(wǎng)絡(luò)中，OSI參考模型的物理層主要負(fù)責(zé)（）。A.數(shù)據(jù)的加密和解密B.網(wǎng)絡(luò)層地址到物理地址的轉(zhuǎn)換C.數(shù)據(jù)幀的傳輸D.提供端到端的可靠數(shù)據(jù)傳輸10.在面向?qū)ο蟪绦蛟O(shè)計(jì)中，封裝的目的是（）。A.隱藏對(duì)象的內(nèi)部細(xì)節(jié)，提供公共接口B.提高對(duì)象的可重用性C.提高對(duì)象的可擴(kuò)展性D.減少對(duì)象的內(nèi)存占用二、填空題（每空2分，共20分。請(qǐng)將答案填在題中的橫線上）1.數(shù)據(jù)結(jié)構(gòu)中的“樹”是一種______結(jié)構(gòu)，它沒有環(huán)，且只有一個(gè)根節(jié)點(diǎn)。2.操作系統(tǒng)中，進(jìn)程的狀態(tài)轉(zhuǎn)換主要有______、阻塞和終止。3.計(jì)算機(jī)網(wǎng)絡(luò)分為廣域網(wǎng)、局域網(wǎng)和______三種類型。4.CPU的主要性能指標(biāo)之一是______，它表示CPU每秒能執(zhí)行的指令數(shù)。5.在二叉樹中，若一個(gè)節(jié)點(diǎn)只有左子節(jié)點(diǎn)沒有右子節(jié)點(diǎn)，則該節(jié)點(diǎn)的度為______。6.假設(shè)內(nèi)存地址為16位，則最多可以表示______個(gè)不同的地址。7.TCP/IP協(xié)議簇中，負(fù)責(zé)網(wǎng)絡(luò)層數(shù)據(jù)包傳輸?shù)膮f(xié)議是______。8.數(shù)據(jù)的存儲(chǔ)單位從大到小依次為：______、KB、MB、GB、TB。9.在C語言中，用于輸出整數(shù)到屏幕的函數(shù)是______。10.嵌入式系統(tǒng)通常具有______和實(shí)時(shí)性等特點(diǎn)。三、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別。2.解釋什么是虛擬內(nèi)存，并簡(jiǎn)述其實(shí)現(xiàn)原理。3.簡(jiǎn)述TCP協(xié)議三次握手的過程。4.什么是嵌入式系統(tǒng)？它與通用計(jì)算機(jī)系統(tǒng)有何主要區(qū)別？四、計(jì)算題（每題10分，共20分）1.計(jì)算下列遞歸函數(shù)的漸進(jìn)時(shí)間復(fù)雜度：T(n)=2T(n/2)+n，其中n為正整數(shù)，且T(1)=1。2.假設(shè)有一個(gè)循環(huán)隊(duì)列，使用數(shù)組Q[0...m-1]實(shí)現(xiàn)，隊(duì)頭指針為front，隊(duì)尾指針為rear。請(qǐng)寫出計(jì)算隊(duì)列當(dāng)前長(zhǎng)度的公式，并說明當(dāng)front<rear時(shí)和當(dāng)front>=rear時(shí)，隊(duì)列長(zhǎng)度如何計(jì)算。五、綜合應(yīng)用題（每題15分，共30分）1.設(shè)計(jì)一個(gè)算法，查找無序數(shù)組中最大的元素和最小的元素，要求只遍歷數(shù)組一次，請(qǐng)描述算法的思路，并用偽代碼表示。2.假設(shè)你需要為一個(gè)航天器設(shè)計(jì)一個(gè)簡(jiǎn)單的任務(wù)調(diào)度系統(tǒng)，該系統(tǒng)需要同時(shí)處理數(shù)據(jù)采集、指令執(zhí)行和通信三個(gè)任務(wù)。請(qǐng)簡(jiǎn)述你會(huì)采用哪種調(diào)度算法（如先來先服務(wù)、短作業(yè)優(yōu)先、輪轉(zhuǎn)等），說明選擇該算法的理由，并簡(jiǎn)要設(shè)計(jì)系統(tǒng)的主要工作流程。---試卷答案一、選擇題1.B2.C3.B4.C5.A6.A7.D8.D9.B10.A二、填空題1.樹形2.就緒3.城域網(wǎng)4.主頻5.16.655367.IP8.字節(jié)9.printf10.實(shí)時(shí)性三、簡(jiǎn)答題1.解析思路：棧是后進(jìn)先出（LIFO）結(jié)構(gòu)，只允許在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出（FIFO）結(jié)構(gòu)，允許在隊(duì)頭進(jìn)行刪除操作，在隊(duì)尾進(jìn)行插入操作。這是兩者最根本的區(qū)別。2.解析思路：虛擬內(nèi)存是利用硬盤空間模擬出更大的內(nèi)存空間，讓程序可以使用比實(shí)際物理內(nèi)存更大的地址空間。實(shí)現(xiàn)原理通常采用分頁或分段技術(shù)，將程序和數(shù)據(jù)分成多個(gè)頁面或段，部分不常用的頁面或段被暫時(shí)移到硬盤上的交換空間，當(dāng)需要時(shí)再換入物理內(nèi)存。3.解析思路：TCP三次握手是為了建立可靠的連接。過程如下：①客戶端發(fā)送SYN報(bào)文段（SYN=1,序號(hào)seq=x）給服務(wù)器，進(jìn)入SYN_SENT狀態(tài)；②服務(wù)器收到SYN報(bào)文段后，回復(fù)SYN+ACK報(bào)文段（SYN=1,ACK=1,確認(rèn)號(hào)ack=x+1,序號(hào)seq=y）給客戶端，進(jìn)入SYN_RCVD狀態(tài)；③客戶端收到SYN+ACK報(bào)文段后，發(fā)送ACK報(bào)文段（ACK=1,確認(rèn)號(hào)ack=y+1,序號(hào)seq=x+1）給服務(wù)器，進(jìn)入ESTABLISHED狀態(tài)。服務(wù)器收到ACK后也進(jìn)入ESTABLISHED狀態(tài)，連接建立。4.解析思路：嵌入式系統(tǒng)是專門為特定應(yīng)用設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)，通常集成在設(shè)備中，執(zhí)行特定功能。與通用計(jì)算機(jī)系統(tǒng)相比，嵌入式系統(tǒng)通常具有體積小、功耗低、成本較低、實(shí)時(shí)性要求高、軟件固化（嵌入式固件）等特點(diǎn)，且其硬件和軟件往往是高度集成和定制的。四、計(jì)算題1.解析思路：使用主定理或遞歸樹方法分析。這里n是2的冪，設(shè)n=2^k。T(n)=2T(n/2)+n=2T(2^(k-1))+2^k。遞歸展開：T(2^k)=2T(2^(k-1))+2^k=4T(2^(k-2))+2*2^k=...=2^kT(1)+k*2^k=2^k+k*2^k=O(k*2^k)。因?yàn)閗=log2(n)，所以T(n)=O(nlogn)。2.解析思路：隊(duì)列長(zhǎng)度等于元素總數(shù)。當(dāng)front<rear時(shí)，隊(duì)列元素從front到rear依次排列，長(zhǎng)度為rear-front。當(dāng)front>=rear時(shí)，表示隊(duì)頭指針在隊(duì)尾指針之后，隊(duì)列元素跨越了數(shù)組的末尾，從front開始排列到m-1，然后從0開始排列到rear，最后到達(dá)數(shù)組末尾。長(zhǎng)度為(m-front)+(rear+1)=m-front+rear+1。五、綜合應(yīng)用題1.解析思路：要一次遍歷找到最大和最小值，可以初始化兩個(gè)變量max和min，分別賦值為數(shù)組的第一個(gè)元素。然后從數(shù)組的第二個(gè)元素開始遍歷，對(duì)于每個(gè)元素a[i]，如果a[i]>max，則更新max=a[i]；如果a[i]<min，則更新min=a[i]。遍歷結(jié)束后，max和min即為所求的最大值和最小值。偽代碼：```functionfindMinMax(arr[],n):ifn==1:return(arr[0],arr[0])//最大最小值相同ifarr[0]>arr[1]:max=arr[0],min=arr[1]else:max=arr[1],min=arr[0]fori=2ton-1:ifarr[i]>max:max=arr[i]elseifarr[i]<min:min=arr[i]return(max,min)```2.解析思路：考慮到航天器任務(wù)通常有嚴(yán)格的實(shí)時(shí)性要求（如指令必須及時(shí)執(zhí)行，數(shù)據(jù)必須按時(shí)采集），且任務(wù)優(yōu)先級(jí)可能不同（如緊急指令優(yōu)先于常規(guī)數(shù)據(jù)采集），輪轉(zhuǎn)調(diào)度算法（RoundRobin）可能是比較合適的選擇。輪轉(zhuǎn)調(diào)度算法將所有就緒任務(wù)放入一個(gè)隊(duì)列，按順序依次讓每個(gè)任務(wù)執(zhí)行一個(gè)時(shí)間片（TimeSlice或Quantum）。選擇理由：簡(jiǎn)單易實(shí)現(xiàn)，能夠保證所有就緒任務(wù)都有機(jī)會(huì)執(zhí)行，并且提供了調(diào)節(jié)任務(wù)響應(yīng)時(shí)間的方法（通過調(diào)整時(shí)間片大?。?duì)于三個(gè)任務(wù)，可以按時(shí)間