2025年計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科期末考試試卷及答案一、單項(xiàng)選擇題（共15題，每題2分，共30分）1.對(duì)于長(zhǎng)度為n的無(wú)序數(shù)組，快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。A.O(n)B.O(nlogn)C.O(n2)D.O(n3)2.操作系統(tǒng)中，進(jìn)程從等待狀態(tài)轉(zhuǎn)換為就緒狀態(tài)的可能原因是（）。A.進(jìn)程時(shí)間片用完B.進(jìn)程獲得CPUC.I/O操作完成D.進(jìn)程調(diào)用exit()3.在TCP/IP協(xié)議棧中，HTTP協(xié)議屬于（）。A.網(wǎng)絡(luò)接口層B.網(wǎng)際層C.傳輸層D.應(yīng)用層4.關(guān)系數(shù)據(jù)庫(kù)中，若一個(gè)關(guān)系模式滿足所有非主屬性完全依賴于候選碼，則該模式至少屬于（）。A.1NFB.2NFC.3NFD.BCNF5.編譯過(guò)程中，詞法分析階段的主要任務(wù)是（）。A.識(shí)別語(yǔ)法錯(cuò)誤B.將源程序轉(zhuǎn)換為目標(biāo)代碼C.生成符號(hào)表D.識(shí)別單詞符號(hào)6.計(jì)算機(jī)組成原理中，直接尋址方式下，操作數(shù)的有效地址是（）。A.指令中的地址碼B.寄存器中的值C.內(nèi)存中的地址D.程序計(jì)數(shù)器的值7.機(jī)器學(xué)習(xí)中，以下屬于監(jiān)督學(xué)習(xí)的是（）。A.K-means聚類B.關(guān)聯(lián)規(guī)則挖掘C.支持向量機(jī)分類D.主成分分析8.軟件工程中，敏捷開(kāi)發(fā)的核心原則是（）。A.嚴(yán)格遵循需求文檔B.快速迭代與客戶反饋C.瀑布式階段劃分D.大規(guī)模文檔驅(qū)動(dòng)9.數(shù)據(jù)挖掘中，若某關(guān)聯(lián)規(guī)則的支持度為0.3，置信度為0.8，則表示（）。A.30%的事務(wù)包含規(guī)則前件，其中80%同時(shí)包含后件B.80%的事務(wù)包含規(guī)則前件，其中30%同時(shí)包含后件C.30%的事務(wù)同時(shí)包含前件和后件，80%的前件事務(wù)包含后件D.80%的事務(wù)同時(shí)包含前件和后件，30%的前件事務(wù)包含后件10.操作系統(tǒng)中，死鎖的必要條件不包括（）。A.互斥條件B.請(qǐng)求與保持條件C.不可搶占條件D.環(huán)路等待條件E.空閑讓進(jìn)條件11.某IP地址為0，其子網(wǎng)掩碼為，則該地址的網(wǎng)絡(luò)號(hào)是（）。A.B.C.0D.012.數(shù)據(jù)庫(kù)索引中，B+樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)的是（）。A.數(shù)據(jù)記錄的指針B.索引鍵值和數(shù)據(jù)記錄C.索引鍵值和子節(jié)點(diǎn)指針D.僅索引鍵值13.分治算法的核心步驟不包括（）。A.分解問(wèn)題B.遞歸求解子問(wèn)題C.合并子問(wèn)題解D.動(dòng)態(tài)規(guī)劃優(yōu)化14.操作系統(tǒng)文件系統(tǒng)中，inode結(jié)構(gòu)通常存儲(chǔ)的信息是（）。A.文件內(nèi)容B.文件元數(shù)據(jù)（如權(quán)限、大小、時(shí)間戳）C.文件路徑D.文件緩存15.計(jì)算機(jī)指令周期中，取指周期的主要操作是（）。A.從內(nèi)存讀取操作數(shù)B.從寄存器讀取指令C.從內(nèi)存讀取指令到指令寄存器D.執(zhí)行指令的運(yùn)算操作二、填空題（共10題，每題2分，共20分）1.TCP三次握手中，第二次握手的報(bào)文段包含的標(biāo)志位是______。2.數(shù)據(jù)庫(kù)事務(wù)的四個(gè)特性（ACID）是原子性、一致性、隔離性和______。3.操作系統(tǒng)調(diào)度算法中，短作業(yè)優(yōu)先（SJF）屬于______（搶占式/非搶占式）調(diào)度。4.計(jì)算機(jī)網(wǎng)絡(luò)中，DNS的主要作用是將______轉(zhuǎn)換為IP地址。5.線索二叉樹(shù)中，每個(gè)節(jié)點(diǎn)的左線索指向其______（前驅(qū)/后繼）節(jié)點(diǎn)（假設(shè)中序線索化）。6.編譯原理中，語(yǔ)法分析的輸入是______（詞法分析的輸出）。7.BP神經(jīng)網(wǎng)絡(luò)中，誤差反向傳播的核心是通過(guò)______調(diào)整神經(jīng)元權(quán)重。8.UML用例圖的基本元素包括用例、參與者和______。9.K-means聚類算法的核心是通過(guò)迭代優(yōu)化______（目標(biāo)函數(shù)）。10.虛擬內(nèi)存的理論基礎(chǔ)是______（局部性原理/并行性原理）。三、簡(jiǎn)答題（共5題，每題8分，共40分）1.簡(jiǎn)述虛擬內(nèi)存的工作原理及其優(yōu)點(diǎn)。2.比較TCP和UDP協(xié)議的特點(diǎn)，并分別列舉其典型應(yīng)用場(chǎng)景。3.說(shuō)明B樹(shù)與B+樹(shù)的主要區(qū)別，并解釋B+樹(shù)為何更適合作為數(shù)據(jù)庫(kù)索引結(jié)構(gòu)。4.進(jìn)程與線程的主要區(qū)別是什么？多線程編程適用于哪些場(chǎng)景？5.數(shù)據(jù)庫(kù)事務(wù)的隔離級(jí)別有哪些？不同隔離級(jí)別如何影響并發(fā)控制的性能與數(shù)據(jù)一致性？四、算法設(shè)計(jì)題（共3題，每題12分，共36分）1.給定一個(gè)帶權(quán)有向圖（頂點(diǎn)集合為V，邊集合為E，權(quán)值均為非負(fù)數(shù)），要求用Dijkstra算法求從源點(diǎn)s到所有其他頂點(diǎn)的最短路徑。請(qǐng)：（1）描述算法的核心步驟；（2）給出偽代碼實(shí)現(xiàn)；（3）分析時(shí)間復(fù)雜度（假設(shè)使用優(yōu)先隊(duì)列優(yōu)化）。2.動(dòng)態(tài)規(guī)劃算法常用于解決最優(yōu)化問(wèn)題。請(qǐng)針對(duì)最長(zhǎng)公共子序列（LCS）問(wèn)題：（1）定義狀態(tài)變量；（2）推導(dǎo)狀態(tài)轉(zhuǎn)移方程；（3）舉例說(shuō)明計(jì)算過(guò)程（如序列X=“ABCBDAB”，Y=“BDCAB”）。3.線索二叉樹(shù)是一種通過(guò)線索（指針）快速訪問(wèn)前驅(qū)和后繼的二叉樹(shù)結(jié)構(gòu)。假設(shè)二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體定義為：```ctypedefstructThreadNode{intdata;structThreadNodelchild,rchild;intltag,rtag;//0表示子節(jié)點(diǎn)，1表示線索}ThreadNode,ThreadTree;```要求設(shè)計(jì)中序線索二叉樹(shù)的遍歷算法（輸出節(jié)點(diǎn)數(shù)據(jù)序列），并說(shuō)明遍歷過(guò)程如何利用線索提高效率。五、綜合應(yīng)用題（共2題，每題15分，共30分）1.設(shè)計(jì)一個(gè)分布式電商系統(tǒng)的商品緩存方案。要求：（1）說(shuō)明緩存層的部署架構(gòu)（如集中式/分布式）；（2）選擇緩存一致性策略（如Cache-Aside、Write-Through等）并解釋其實(shí)現(xiàn)；（3）設(shè)計(jì)緩存失效策略（如TTL、LRU等）及多級(jí)緩存（如本地緩存+分布式緩存）的協(xié)同機(jī)制；（4）分析可能的緩存擊穿、穿透問(wèn)題及解決方案。2.設(shè)計(jì)一個(gè)在線教育平臺(tái)的數(shù)據(jù)庫(kù)架構(gòu)。要求：（1）繪制簡(jiǎn)化的ER圖（包含用戶、課程、教師、訂單四個(gè)實(shí)體及關(guān)鍵屬性）；（2）設(shè)計(jì)核心數(shù)據(jù)表結(jié)構(gòu)（如用戶表、課程表、訂單表），并說(shuō)明字段類型及約束；（3）提出索引優(yōu)化策略（如主鍵、外鍵、聯(lián)合索引）；（4）設(shè)計(jì)訂單支付事務(wù)的處理流程（需滿足ACID特性）。答案一、單項(xiàng)選擇題1.C2.C3.D4.B5.D6.A7.C8.B9.C10.E11.A12.B13.D14.B15.C二、填空題1.SYN+ACK2.持久性3.非搶占式4.域名5.前驅(qū)6.單詞符號(hào)序列7.梯度下降8.關(guān)聯(lián)關(guān)系9.簇內(nèi)誤差平方和10.局部性原理三、簡(jiǎn)答題1.虛擬內(nèi)存工作原理：利用磁盤空間模擬內(nèi)存，將進(jìn)程的部分?jǐn)?shù)據(jù)加載到內(nèi)存，其余暫存磁盤。通過(guò)頁(yè)表記錄頁(yè)的內(nèi)存/磁盤位置，當(dāng)訪問(wèn)缺失頁(yè)時(shí)觸發(fā)缺頁(yè)中斷，將目標(biāo)頁(yè)調(diào)入內(nèi)存（可能置換舊頁(yè)）。優(yōu)點(diǎn)：突破物理內(nèi)存限制，允許多進(jìn)程并發(fā)運(yùn)行；提高內(nèi)存利用率；簡(jiǎn)化程序開(kāi)發(fā)（無(wú)需手動(dòng)管理內(nèi)存）。2.TCP特點(diǎn)：面向連接、可靠傳輸（確認(rèn)重傳）、面向字節(jié)流、有擁塞控制；UDP特點(diǎn)：無(wú)連接、不可靠、面向數(shù)據(jù)報(bào)、低延遲；典型場(chǎng)景：TCP用于HTTP、SMTP（需可靠傳輸）；UDP用于視頻流、DNS（實(shí)時(shí)性優(yōu)先）。3.B樹(shù)與B+樹(shù)區(qū)別：B樹(shù)的節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)和索引鍵，葉子節(jié)點(diǎn)無(wú)順序；B+樹(shù)僅葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)（且有序），內(nèi)部節(jié)點(diǎn)僅存索引鍵，所有葉子節(jié)點(diǎn)通過(guò)指針連接。B+樹(shù)優(yōu)勢(shì)：范圍查詢效率高（可順序遍歷葉子節(jié)點(diǎn)）；索引更緊湊（內(nèi)部節(jié)點(diǎn)無(wú)數(shù)據(jù)）；適合磁盤存儲(chǔ)（減少I/O次數(shù)）。4.進(jìn)程與線程區(qū)別：進(jìn)程是資源分配的基本單位，線程是CPU調(diào)度的基本單位；進(jìn)程間獨(dú)立（通信需IPC），線程共享進(jìn)程資源（通信高效）；進(jìn)程切換開(kāi)銷大，線程切換開(kāi)銷小。多線程場(chǎng)景：I/O密集型任務(wù)（如Web服務(wù)器）、并行計(jì)算（如圖像處理）、需要共享狀態(tài)的任務(wù)（如實(shí)時(shí)數(shù)據(jù)處理）。5.隔離級(jí)別（從低到高）：讀未提交（ReadUncommitted）、讀已提交（ReadCommitted）、可重復(fù)讀（RepeatableRead）、串行化（Serializable）。影響：隔離級(jí)別越低，并發(fā)性能越高，但可能出現(xiàn)臟讀、不可重復(fù)讀、幻讀；級(jí)別越高，數(shù)據(jù)一致性越強(qiáng)，但并發(fā)性能下降（如串行化接近單線程）。四、算法設(shè)計(jì)題1.Dijkstra算法（1）核心步驟：①初始化距離數(shù)組dist[]（dist[s]=0，其余為∞），優(yōu)先隊(duì)列保存（距離，頂點(diǎn)）；②取出隊(duì)列中距離最小的頂點(diǎn)u，遍歷其鄰接頂點(diǎn)v，若dist[v]>dist[u]+weight(u,v)，則更新dist[v]并將v加入隊(duì)列；③重復(fù)直到隊(duì)列為空。（2）偽代碼：```pythondefdijkstra(graph,s):n=len(graph)dist=[inf]ndist[s]=0heap=[(0,s)]visited=[False]nwhileheap:current_dist,u=heapq.heappop(heap)ifvisited[u]:continuevisited[u]=Trueforv,weightingraph[u]:ifdist[v]>current_dist+weight:dist[v]=current_dist+weightheapq.heappush(heap,(dist[v],v))returndist```（3）時(shí)間復(fù)雜度：使用優(yōu)先隊(duì)列（堆），每次操作O(logn)，總時(shí)間O((V+E)logV)（V為頂點(diǎn)數(shù)，E為邊數(shù)）。2.LCS問(wèn)題（1）狀態(tài)變量：dp[i][j]表示X的前i個(gè)字符和Y的前j個(gè)字符的LCS長(zhǎng)度。（2）狀態(tài)轉(zhuǎn)移方程：若X[i-1]==Y[j-1]，則dp[i][j]=dp[i-1][j-1]+1；否則，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。（3）計(jì)算示例（X=“ABCBDAB”，Y=“BDCAB”）：構(gòu)造5×6的dp表（i=0~5，j=0~6）：-dp[0][j]=0，dp[i][0]=0；-i=1（X[0]=A），j=1（Y[0]=B）：不等，dp[1][1]=0；-i=2（X[1]=B），j=1（Y[0]=B）：相等，dp[2][1]=1；-最終dp[5][6]=4（LCS為“BCAB”或“BDAB”）。3.中序線索二叉樹(shù)遍歷算法（1）算法步驟：①找到中序遍歷的第一個(gè)節(jié)點(diǎn)（最左子節(jié)點(diǎn)）；②依次訪問(wèn)當(dāng)前節(jié)點(diǎn)的后繼：若rtag=1，直接通過(guò)rchild找到后繼；否則，找右子樹(shù)的最左子節(jié)點(diǎn)。（2）代碼實(shí)現(xiàn)：```cvoidinOrderTraverse(ThreadTreeT){ThreadNodep=T;while(p!=NULL){//找最左子節(jié)點(diǎn)（中序第一個(gè)節(jié)點(diǎn)）while(p->ltag==0)p=p->lchild;printf("%d",p->data);//訪問(wèn)后繼while(p->rtag==1&&p->rchild!=NULL){p=p->rchild;printf("%d",p->data);}p=p->rchild;//進(jìn)入右子樹(shù)（可能為子節(jié)點(diǎn)或線索）}}```（3）效率提升：通過(guò)線索直接跳轉(zhuǎn)前驅(qū)/后繼，無(wú)需遞歸或棧，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。五、綜合應(yīng)用題1.分布式電商緩存方案（1）部署架構(gòu)：采用“本地緩存（JVM緩存）+分布式緩存（Redis集群）”多級(jí)架構(gòu)。本地緩存用于高頻熱點(diǎn)數(shù)據(jù)（如秒殺商品），分布式緩存用于全局商品數(shù)據(jù)。（2）一致性策略：選擇Cache-Aside模式（讀：先查緩存，未命中則查數(shù)據(jù)庫(kù)并更新緩存；寫：先更新數(shù)據(jù)庫(kù)，再刪除緩存）。避免Write-Through的同步寫延遲，同時(shí)通過(guò)延遲雙刪（刪除緩存后等待一段時(shí)間再次刪除）解決主從數(shù)據(jù)庫(kù)同步導(dǎo)致的臟數(shù)據(jù)問(wèn)題。（3）失效策略：-TTL（生存時(shí)間）：普通商品緩存設(shè)置30分鐘~2小時(shí)，熱點(diǎn)商品設(shè)置更長(zhǎng)（如1天）；-LRU（最近最少使用）：Redis配置maxmemory-policy為allkeys-lru，淘汰冷數(shù)據(jù)；-協(xié)同機(jī)制：本地緩存設(shè)置更小的TTL（如5分鐘），并通過(guò)消息隊(duì)列（如Kafka）同步分布式緩存的更新事件，觸發(fā)本地緩存的主動(dòng)失效。（4）緩存問(wèn)題解決：-緩存擊穿（熱點(diǎn)key失效）：使用互斥鎖（如Redis的setnx）控制僅一個(gè)線程回源加載，其他線程等待；-緩存穿透（查詢不存在的key）：緩存空值（設(shè)置短TTL）或使用布隆過(guò)濾器預(yù)校驗(yàn)。2.在線教育平臺(tái)數(shù)據(jù)庫(kù)架構(gòu)（1）ER圖（簡(jiǎn)化）：-實(shí)體：用戶（用戶ID，姓名，手機(jī)號(hào)，注冊(cè)時(shí)間）；-課程（課程ID，名稱，教師ID，價(jià)格，創(chuàng)建時(shí)間）；-教師（教師ID，姓名，職稱，簡(jiǎn)介）；-訂單（訂單ID，用戶ID，課程ID，支付金額，支付狀態(tài)，支付時(shí)間）。-關(guān)系：用戶與訂單（1:N）；教師與課程（1:N）；用戶與課程（M:N，通過(guò)訂單關(guān)聯(lián)）。（2）核心表結(jié)構(gòu)：-用戶表（user）：user_id（BIGINT，主鍵），username（VARCHAR(50)），phon