北京大學(xué)2025年計(jì)算機(jī)科學(xué)與技術(shù)（軟件工程）專業(yè)入學(xué)考試試題及答案考試時(shí)間：______分鐘總分：______分姓名：______一、請簡述數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列的基本定義、核心操作（至少列出三種）及其區(qū)別。結(jié)合具體例子，說明棧和隊(duì)列在哪些典型問題中有所應(yīng)用。二、給定以下遞歸函數(shù)定義：```functionFibonacci(n):ifn<=0:return0elseifn==1:return1else:returnFibonacci(n-1)+Fibonacci(n-2)```請分析該函數(shù)的時(shí)間復(fù)雜度。為了提高其效率，可以采用哪些常見方法？請簡述其中一種方法的原理，并說明其時(shí)間復(fù)雜度。三、解釋操作系統(tǒng)的內(nèi)存管理中，分頁（Paging）和分段（Segmentation）兩種方式的區(qū)別。請分別說明它們各自可能帶來的問題（如外部碎片、內(nèi)部碎片等），并簡要說明如何解決分頁中的外部碎片問題。四、在TCP/IP網(wǎng)絡(luò)模型中，請簡述數(shù)據(jù)從應(yīng)用層傳輸?shù)轿锢韺拥倪^程中，在每一層（應(yīng)用層、傳輸層、網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層、物理層）發(fā)生的處理或封裝的主要變化。假設(shè)客戶端向服務(wù)器發(fā)送一個(gè)HTTP請求，請描述該請求在傳輸層被封裝成IP數(shù)據(jù)包的過程中，IP頭部包含哪些關(guān)鍵信息。五、請定義數(shù)據(jù)庫中的“范式”（NormalForm）。為什么需要將數(shù)據(jù)庫設(shè)計(jì)遵循范式？簡述第一范式（1NF）和第三范式（3NF）的主要要求，并說明滿足3NF的設(shè)計(jì)相較于只滿足1NF的設(shè)計(jì)，在減少數(shù)據(jù)冗余和更新異常方面有什么優(yōu)勢。六、閱讀以下用Python編寫的代碼片段：```pythondeffind_max_pair(numbers):iflen(numbers)<2:returnNonemax_pair=(numbers[0],numbers[1])max_product=max_pair[0]*max_pair[1]foriinrange(len(numbers)):forjinrange(i+1,len(numbers)):product=numbers[i]*numbers[j]ifproduct>max_product:max_product=productmax_pair=(numbers[i],numbers[j])returnmax_pair```請分析該函數(shù)的目的是什么。指出該函數(shù)實(shí)現(xiàn)中存在的效率問題，并簡述如何改進(jìn)以提高其查找最大乘積對的速度。七、在軟件開發(fā)過程中，什么是“敏捷開發(fā)”（AgileDevelopment）？它與傳統(tǒng)的“瀑布模型”（WaterfallModel）相比，在項(xiàng)目計(jì)劃、開發(fā)流程、團(tuán)隊(duì)協(xié)作和交付方式等方面有哪些顯著的不同？請結(jié)合軟件開發(fā)的實(shí)際情況，說明敏捷開發(fā)的優(yōu)勢體現(xiàn)在哪些方面。八、請解釋什么是“面向?qū)ο笤O(shè)計(jì)”（Object-OrientedDesign,OOD）中的“單一職責(zé)原則”（SingleResponsibilityPrinciple,SRP）。為什么遵循SRP原則有助于提高軟件的可維護(hù)性和可擴(kuò)展性？請給出一個(gè)簡單的例子說明違反SRP原則可能帶來的問題。九、設(shè)計(jì)一個(gè)簡單的在線圖書商店的注冊功能模塊。請描述該模塊需要實(shí)現(xiàn)的核心功能（至少包括用戶輸入信息、信息校驗(yàn)、用戶創(chuàng)建、賬號(hào)激活等關(guān)鍵步驟）。在設(shè)計(jì)中，請考慮至少兩個(gè)可能的技術(shù)選型（如前端框架、后端語言/框架、數(shù)據(jù)庫），并簡述選擇這些技術(shù)的原因。十、假設(shè)你需要開發(fā)一個(gè)需要處理大量并發(fā)訪問的小型社交網(wǎng)絡(luò)應(yīng)用。請簡述在系統(tǒng)設(shè)計(jì)時(shí)，你可能會(huì)考慮哪些關(guān)鍵的技術(shù)或架構(gòu)方面的問題（例如，如何設(shè)計(jì)用戶認(rèn)證系統(tǒng)以應(yīng)對高并發(fā)？如何存儲(chǔ)和查詢用戶動(dòng)態(tài)信息？如何保證消息的實(shí)時(shí)性？），并針對其中一個(gè)問題，提出你的初步解決方案思路。試卷答案一、棧：先進(jìn)后出（LIFO）的數(shù)據(jù)結(jié)構(gòu)。核心操作：壓棧（Push）、彈棧（Pop）、查看棧頂（Peek/Top）。隊(duì)列：先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。核心操作：入隊(duì)（Enqueue）、出隊(duì)（Dequeue）、查看隊(duì)首。區(qū)別：棧是LIFO，隊(duì)列是FIFO；棧通常只允許在棧頂進(jìn)行操作，隊(duì)列允許在隊(duì)頭隊(duì)尾操作。應(yīng)用：棧用于函數(shù)調(diào)用棧、表達(dá)式求值（中綴轉(zhuǎn)后綴）、括號(hào)匹配、深度優(yōu)先搜索（DFS）路徑記錄等；隊(duì)列用于任務(wù)調(diào)度、消息隊(duì)列、廣度優(yōu)先搜索（BFS）路徑記錄、打印隊(duì)列等。例如，瀏覽器回退功能使用棧，而任務(wù)按提交順序執(zhí)行使用隊(duì)列。二、該遞歸函數(shù)的時(shí)間復(fù)雜度為O(2^n)。因?yàn)槊空{(diào)用Fibonacci(n)都會(huì)生成兩個(gè)新的調(diào)用Fibonacci(n-1)和Fibonacci(n-2)，形成指數(shù)級(jí)增長的遞歸樹。提高效率的方法有：備忘錄法（Memoization）或動(dòng)態(tài)規(guī)劃（DynamicProgramming）。備忘錄法原理：使用一個(gè)表（數(shù)組或哈希表）存儲(chǔ)已計(jì)算過的Fibonacci值，當(dāng)函數(shù)被調(diào)用時(shí)，首先檢查結(jié)果是否已存在，存在則直接返回，否則計(jì)算并存入表再返回。時(shí)間復(fù)雜度降為O(n)。三、分頁：將邏輯地址空間（用戶視角）和物理地址空間（內(nèi)存物理塊）都劃分為固定大小的頁（Page）和塊（Frame），通過頁表進(jìn)行映射。分段：將邏輯地址空間根據(jù)程序的邏輯結(jié)構(gòu)（如代碼段、數(shù)據(jù)段、堆棧段）劃分為不同的段（Segment），段的大小可以不固定。問題：分頁可能產(chǎn)生內(nèi)部碎片（分配的內(nèi)存塊大于實(shí)際需求，剩余部分浪費(fèi)）；分段可能導(dǎo)致外部碎片（不同段大小不匹配，導(dǎo)致內(nèi)存空間雖足夠但無法分配給新段）。分段的外部碎片問題：可以通過段共享（相同邏輯段的進(jìn)程使用同一塊物理段）或段置換（將不再使用的段移出內(nèi)存）來解決。四、應(yīng)用層：數(shù)據(jù)被封裝成HTTP請求或響應(yīng)。傳輸層：HTTP數(shù)據(jù)被封裝成TCP段（Segment），頭部包含源/目的端口號(hào)、序列號(hào)、確認(rèn)號(hào)、標(biāo)志位（如SYN,ACK）、窗口大小、校驗(yàn)和等。網(wǎng)絡(luò)層：TCP段被封裝成IP數(shù)據(jù)包（Packet），頭部包含源/目的IP地址、協(xié)議類型（TCP）、頭部校驗(yàn)和、TTL、標(biāo)識(shí)、標(biāo)志、片偏移、頭部長度等。數(shù)據(jù)鏈路層：IP數(shù)據(jù)包被封裝成幀（Frame），頭部包含目標(biāo)/源MAC地址、類型字段，尾部包含F(xiàn)CS校驗(yàn)碼。物理層：幀被轉(zhuǎn)換成比特流（0和1），通過物理媒介（如網(wǎng)線、光纖）傳輸。五、范式：數(shù)據(jù)庫設(shè)計(jì)中的規(guī)范化形式，旨在減少數(shù)據(jù)冗余、避免數(shù)據(jù)更新異常、確保數(shù)據(jù)一致性。需要遵循范式：通過將數(shù)據(jù)規(guī)范化，可以消除冗余，節(jié)省存儲(chǔ)空間，防止因數(shù)據(jù)冗余引起的插入、刪除、更新異常。1NF：要求每個(gè)屬性都是原子值，即不可再分。3NF：要求滿足1NF和2NF（非主屬性完全函數(shù)依賴于主鍵），且非主屬性之間不存在傳遞函數(shù)依賴。優(yōu)勢：滿足3NF的設(shè)計(jì)相較于只滿足1NF，可以確保非主屬性只依賴于主鍵，消除了非主屬性對主鍵的部分依賴和傳遞依賴，從而徹底消除了插入、刪除、更新異常的可能性，數(shù)據(jù)結(jié)構(gòu)更穩(wěn)定。六、目的：在給定數(shù)字列表中查找乘積最大的兩個(gè)數(shù)，并返回這對數(shù)。效率問題：該函數(shù)使用了雙重循環(huán)，時(shí)間復(fù)雜度為O(n^2)，對于大數(shù)據(jù)集效率低下。改進(jìn)方法：可以首先對數(shù)組進(jìn)行排序（O(nlogn)），然后只需比較排序后數(shù)組末尾相鄰兩個(gè)元素（最大值與次大值）的乘積，或者遍歷一次數(shù)組，記錄當(dāng)前遇到的最大值和次大值（O(n)）。這兩種方法時(shí)間復(fù)雜度均為O(n)。七、敏捷開發(fā)：一種迭代、增量式的軟件開發(fā)方法，強(qiáng)調(diào)適應(yīng)性、協(xié)作、快速響應(yīng)變化和盡早交付可工作的軟件。與傳統(tǒng)瀑布模型相比：計(jì)劃上更短、更靈活，按迭代周期進(jìn)行；流程上更強(qiáng)調(diào)跨職能團(tuán)隊(duì)協(xié)作和持續(xù)反饋，而非嚴(yán)格的階段劃分；交付上更頻繁，早期就交付可用軟件，并根據(jù)反饋調(diào)整后續(xù)開發(fā)；團(tuán)隊(duì)協(xié)作上更緊密，成員角色界限模糊。優(yōu)勢：能更快響應(yīng)需求變化、降低項(xiàng)目風(fēng)險(xiǎn)、提高客戶滿意度、促進(jìn)團(tuán)隊(duì)溝通和滿意度。八、單一職責(zé)原則（SRP）：一個(gè)類（或模塊、函數(shù)）應(yīng)該只有一個(gè)引起它變化的原因。原因：遵循SRP可以降低類的復(fù)雜度，使其更內(nèi)聚、更易于理解；當(dāng)需要修改功能時(shí)，影響范圍更小，降低了引入錯(cuò)誤的風(fēng)險(xiǎn)；便于測試，可以針對單一職責(zé)進(jìn)行獨(dú)立測試；提高了代碼的可維護(hù)性和可擴(kuò)展性，因?yàn)樾薷牟粫?huì)波及不相關(guān)的部分。例子：一個(gè)“用戶”類，如果同時(shí)負(fù)責(zé)處理用戶信息（如保存、加載）和用戶權(quán)限驗(yàn)證，那么任何關(guān)于權(quán)限邏輯的修改都可能需要修改用戶類，違反SRP。應(yīng)將其拆分為“用戶信息管理類”和“權(quán)限驗(yàn)證類”。九、核心功能：用戶輸入用戶名、密碼、郵箱等信息；系統(tǒng)校驗(yàn)輸入信息的格式（如密碼強(qiáng)度、郵箱格式）、有效性（如用戶名是否已存在）和唯一性（如郵箱是否已被注冊）；通過校驗(yàn)后，系統(tǒng)生成用戶ID、加密存儲(chǔ)用戶密碼和基本信息，創(chuàng)建用戶賬號(hào)記錄；系統(tǒng)向用戶郵箱發(fā)送激活鏈接或驗(yàn)證碼，用戶點(diǎn)擊鏈接或輸入驗(yàn)證碼完成賬號(hào)激活。技術(shù)選型1：前端框架可選React/Vue.js（提供豐富的UI組件和交互支持）；后端語言/框架可選Node.js/Express（快速開發(fā)，適合I/O密集型）或Python/Django（開發(fā)效率高，生態(tài)完善）；數(shù)據(jù)庫可選PostgreSQL/MySQL（關(guān)系型，數(shù)據(jù)結(jié)構(gòu)清晰）。原因：React/Vue提供良好的用戶體驗(yàn)和開發(fā)效率；Express/Django成熟穩(wěn)定，開發(fā)快速；PostgreSQL/MySQL功能強(qiáng)大，支持事務(wù)，適合存儲(chǔ)結(jié)構(gòu)化用戶數(shù)據(jù)。技術(shù)選型2：前端框架可選Angular（功能全面，適合大型應(yīng)用）；后端語言/框架可選Java/SpringBoot（企業(yè)級(jí)應(yīng)用常用，穩(wěn)定成熟）；數(shù)據(jù)庫可選MongoDB（NoSQL，靈活性高，適合存儲(chǔ)非結(jié)構(gòu)化用戶動(dòng)態(tài)）。原因：Angular提供強(qiáng)大的前端工程能力；Java/SpringBoot生態(tài)完善，適合高并發(fā)場景；MongoDB靈活處理用戶動(dòng)態(tài)的多樣化數(shù)據(jù)結(jié)構(gòu)。十、關(guān)鍵問題：用戶認(rèn)證系統(tǒng)高并發(fā)、數(shù)據(jù)存儲(chǔ)與查詢效率、消息實(shí)時(shí)性。解決方案思路