2025年大學(xué)《信息與計(jì)算科學(xué)》專業(yè)題庫(kù)——信息與計(jì)算科學(xué)專業(yè)本科生畢業(yè)答辯考試時(shí)間：______分鐘總分：______分姓名：______一、請(qǐng)闡述線性代數(shù)中特征值與特征向量的定義，并說(shuō)明它們?cè)谇蠼獬Ｎ⒎址匠探M、矩陣對(duì)角化以及數(shù)據(jù)降維（如主成分分析）等領(lǐng)域的應(yīng)用。二、什么是數(shù)據(jù)結(jié)構(gòu)中的“平衡”二叉搜索樹(shù)？以AVL樹(shù)或紅黑樹(shù)為例，簡(jiǎn)述其如何通過(guò)旋轉(zhuǎn)操作維持平衡，并說(shuō)明這種平衡對(duì)于提高查找、插入和刪除操作效率的重要性。三、設(shè)函數(shù)f=x3-3x+1在區(qū)間[-2,2]上滿足拉格朗日中值定理，請(qǐng)求出定理中的中間點(diǎn)ξ的取值范圍。四、什么是數(shù)值計(jì)算中的“數(shù)值穩(wěn)定性”？請(qǐng)以歐拉法或龍格-庫(kù)塔法求解初值問(wèn)題為例，分析其數(shù)值穩(wěn)定性的特點(diǎn)，并說(shuō)明為何在某些情況下需要采用更穩(wěn)定的數(shù)值方法。五、簡(jiǎn)述“貪心算法”的基本思想。舉例說(shuō)明一種你熟悉的貪心算法（如活動(dòng)選擇、最小生成樹(shù)算法中的Prim或Kruskal算法、哈夫曼編碼等），描述該算法的求解過(guò)程，并分析其適用條件。六、什么是機(jī)器學(xué)習(xí)中的“過(guò)擬合”現(xiàn)象？請(qǐng)從模型復(fù)雜度、訓(xùn)練數(shù)據(jù)量和特征選擇等角度分析導(dǎo)致過(guò)擬合的原因，并列舉至少三種常用的避免過(guò)擬合的技術(shù)方法。七、請(qǐng)比較并說(shuō)明快速排序（QuickSort）和歸并排序（MergeSort）兩種排序算法在時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性以及適用場(chǎng)景上的主要異同點(diǎn)。八、什么是圖論中的“最短路徑問(wèn)題”？請(qǐng)分別描述迪杰斯特拉（Dijkstra）算法和貝爾曼-福特（Bellman-Ford）算法的基本思想，并指出它們各自適用于解決哪種類型的邊權(quán)重（有負(fù)權(quán)邊或無(wú)負(fù)權(quán)邊）的最短路徑問(wèn)題。九、設(shè)有一組數(shù)據(jù)點(diǎn)在二維空間中分布，請(qǐng)簡(jiǎn)述“K-均值聚類”（K-Means）算法的基本步驟。在開(kāi)始聚類之前，通常需要預(yù)先指定聚類數(shù)目K。請(qǐng)?zhí)岢鲋辽賰煞N確定K值的方法，并簡(jiǎn)述其原理。十、什么是密碼學(xué)中的“對(duì)稱加密”和“非對(duì)稱加密”？請(qǐng)分別說(shuō)明這兩種加密方式的基本原理、密鑰使用方式，并各舉一個(gè)常見(jiàn)的應(yīng)用實(shí)例。試卷答案一、定義:設(shè)A是n階方陣，λ是標(biāo)量，若存在非零向量x，使得Ax=λx，則稱λ是矩陣A的特征值，x是矩陣A對(duì)應(yīng)于特征值λ的特征向量。應(yīng)用:1.求解常微分方程組:特征值和特征向量可用于求解具有常系數(shù)的線性齊次微分方程組。將方程組矩陣化為對(duì)角化形式，利用特征值求解特征方程，特征向量構(gòu)成基，可以簡(jiǎn)化求解過(guò)程。2.矩陣對(duì)角化:若矩陣A有n個(gè)線性無(wú)關(guān)的特征向量，則A可以相似對(duì)角化，即存在可逆矩陣P（其列向量為A的特征向量），使得P?1AP=D（D為對(duì)角矩陣，對(duì)角線元素為A的特征值）。對(duì)角化后，矩陣的冪運(yùn)算、行列式計(jì)算、指數(shù)函數(shù)等性質(zhì)的計(jì)算變得簡(jiǎn)單。3.數(shù)據(jù)降維（主成分分析PCA）:PCA的核心思想是找到數(shù)據(jù)協(xié)方差矩陣或相關(guān)矩陣的最大特征值對(duì)應(yīng)的特征向量，這些特征向量稱為主成分方向。較大的特征值對(duì)應(yīng)的方向代表數(shù)據(jù)方差最大的方向。通過(guò)將數(shù)據(jù)投影到這些少數(shù)幾個(gè)主成分方向上，可以達(dá)到降維的目的，同時(shí)保留數(shù)據(jù)的主要信息。二、平衡二叉搜索樹(shù)定義:平衡二叉搜索樹(shù)是一種特殊的二叉搜索樹(shù)，它通過(guò)維護(hù)樹(shù)中任意節(jié)點(diǎn)的左右子樹(shù)的高度差（平衡因子）在一個(gè)限定范圍內(nèi)（通常是[-1,1]或[0,1]），從而保證樹(shù)的高度大致保持在log?n量級(jí)，確保查找、插入、刪除等操作的時(shí)間復(fù)雜度在最壞情況下也是O(logn)。AVL樹(shù)/紅黑樹(shù)維持平衡方式(以AVL樹(shù)為例):主要通過(guò)旋轉(zhuǎn)操作來(lái)維持平衡。當(dāng)插入或刪除節(jié)點(diǎn)導(dǎo)致樹(shù)失去平衡時(shí)，根據(jù)失衡節(jié)點(diǎn)及其父節(jié)點(diǎn)的關(guān)系，進(jìn)行單旋轉(zhuǎn)（左旋或右旋）或雙旋轉(zhuǎn)（左-右旋或右-左旋）。旋轉(zhuǎn)操作能夠調(diào)整樹(shù)的結(jié)構(gòu)，使失衡節(jié)點(diǎn)的平衡因子恢復(fù)，并確保路徑上所有節(jié)點(diǎn)的平衡因子滿足AVL樹(shù)的定義。重要性:維持平衡可以防止二叉搜索樹(shù)退化為鏈表，確保所有基本操作（查找、插入、刪除）的時(shí)間復(fù)雜度均為O(logn)，從而提高大規(guī)模數(shù)據(jù)集上這些操作的效率。三、拉格朗日中值定理表述:若函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù)，在開(kāi)區(qū)間(a,b)內(nèi)可導(dǎo)，則存在至少一個(gè)點(diǎn)ξ∈(a,b)，使得f'(ξ)=[f(b)-f(a)]/(b-a)。幾何意義:函數(shù)f(x)在區(qū)間[a,b]上的圖像是一條連續(xù)曲線，則在曲線段上至少存在一點(diǎn)P(ξ,f(ξ))，該點(diǎn)處的切線斜率f'(ξ)等于連接曲線兩端點(diǎn)A(a,f(a))和B(b,f(b))的割線斜率[f(b)-f(a)]/(b-a)。求ξ范圍:對(duì)函數(shù)g(x)=x3-3x+1在區(qū)間[-2,2]上應(yīng)用拉格朗日中值定理。g'(x)=3x2-3。設(shè)ξ為滿足定理的中間點(diǎn)，則g'(ξ)=[g(2)-g(-2)]/(2-(-2))。g(2)=23-3*2+1=8-6+1=3。g(-2)=(-2)3-3*(-2)+1=-8+6+1=-1。割線斜率=(3-(-1))/(2-(-2))=4/4=1。所以，需要求解3ξ2-3=1。即3ξ2=4，ξ2=4/3。因此，ξ=±√(4/3)=±2/√3。由于ξ∈(-2,2)，所以ξ的取值范圍是(-2/√3,2/√3)。四、數(shù)值穩(wěn)定性定義:一個(gè)數(shù)值算法是數(shù)值穩(wěn)定的，如果初始數(shù)據(jù)的微小擾動(dòng)（或舍入誤差）在算法的后續(xù)計(jì)算過(guò)程中被控制住，不會(huì)隨著迭代次數(shù)的增加而無(wú)限放大，或者只以有限的速率增長(zhǎng)，使得最終結(jié)果仍然能較好地逼近真實(shí)解。以歐拉法為例分析:歐拉法公式：y_{n+1}=y_n+hf(x_n,y_n)?？紤]舍入誤差ε_(tái)n，實(shí)際計(jì)算為(y_n+ε_(tái)n)+hf(x_n,y_n)=y_{n+1}+ε_(tái){n+1}。ε_(tái){n+1}=ε_(tái)n+hf(x_n,y_n)。對(duì)于y'=f(x,y)=ax（a為常數(shù)），若y_n有誤差ε_(tái)n，則ε_(tái){n+1}=ε_(tái)n+ha*y_n=ε_(tái)n(1+ha)。若a>0且h>0，則|1+ha|>1，誤差會(huì)隨步長(zhǎng)h或系數(shù)a增大而放大，算法不穩(wěn)定。若a<0且h>0，則|1+ha|<1，誤差會(huì)隨迭代次數(shù)增加而減小，算法穩(wěn)定。對(duì)于一般方程，若|f(x,y)|或其局部增長(zhǎng)速率在解附近較大，且步長(zhǎng)h選擇不當(dāng)，歐拉法可能不穩(wěn)定。原因:舍入誤差在每一步計(jì)算中都會(huì)被傳播和累積。如果算法對(duì)初始誤差或計(jì)算過(guò)程中的誤差放大作用不大，則算法穩(wěn)定。更穩(wěn)定方法:如改進(jìn)歐拉法（梯形法則）、龍格-庫(kù)塔法（RK2,RK4等），它們通常通過(guò)使用更精確的估計(jì)或更多的計(jì)算來(lái)減小舍入誤差的累積，從而提高數(shù)值穩(wěn)定性。五、貪心算法思想:貪心算法在每一步選擇中都作出在當(dāng)前看來(lái)最優(yōu)（即最有利）的選擇，希望通過(guò)局部最優(yōu)的選擇達(dá)到全局最優(yōu)的結(jié)果。它做出每一步選擇時(shí)，并不考慮未來(lái)可能的后果，只貪心地選擇當(dāng)前最好選項(xiàng)。舉例：活動(dòng)選擇問(wèn)題問(wèn)題描述:給定n個(gè)活動(dòng)的集合S={a?,a?,...,a?}，其中每個(gè)活動(dòng)a?都有一個(gè)開(kāi)始時(shí)間s?和一個(gè)結(jié)束時(shí)間f?（s?<f?）。如果兩個(gè)活動(dòng)a?和a?不沖突（即a?的結(jié)束時(shí)間≤a?的開(kāi)始時(shí)間或a?的結(jié)束時(shí)間≤a?的開(kāi)始時(shí)間），則它們可以同時(shí)進(jìn)行。求集合S中的一個(gè)最大子集A，使得集合A中的活動(dòng)相互不沖突。求解過(guò)程:1.按照每個(gè)活動(dòng)結(jié)束時(shí)間f?的升序排序。2.選擇結(jié)束時(shí)間最早的活動(dòng)a?加入集合A。3.從剩下的活動(dòng)中，選擇與當(dāng)前集合A中最后一個(gè)選入的活動(dòng)不沖突，并且開(kāi)始時(shí)間最早的活動(dòng)，加入集合A。4.重復(fù)步驟3，直到?jīng)]有滿足條件的活動(dòng)為止。適用條件:貪心算法適用于具有“貪心選擇性質(zhì)”和“最優(yōu)子結(jié)構(gòu)性質(zhì)”的問(wèn)題。在本例中，按結(jié)束時(shí)間排序保證了貪心選擇性質(zhì)：選擇結(jié)束時(shí)間最早的活動(dòng)，不會(huì)阻礙后續(xù)選擇更多活動(dòng)。問(wèn)題本身也具有最優(yōu)子結(jié)構(gòu)：若A是最大不沖突活動(dòng)集合，且A包含活動(dòng)a?，則A去掉a?后，剩余部分的最大不沖突活動(dòng)集合與A去掉a?后的集合相同。六、過(guò)擬合定義:過(guò)擬合是指機(jī)器學(xué)習(xí)模型在訓(xùn)練數(shù)據(jù)上表現(xiàn)非常好（訓(xùn)練誤差很小），但在未見(jiàn)過(guò)的測(cè)試數(shù)據(jù)或新數(shù)據(jù)上表現(xiàn)很差（測(cè)試誤差顯著增大）的現(xiàn)象。模型學(xué)習(xí)到了訓(xùn)練數(shù)據(jù)中的噪聲和細(xì)節(jié)，而不是潛在的普遍規(guī)律。原因:1.模型復(fù)雜度過(guò)高:模型參數(shù)過(guò)多，能夠擬合訓(xùn)練數(shù)據(jù)中的每一個(gè)波動(dòng)，包括噪聲。2.訓(xùn)練數(shù)據(jù)量不足:模型在有限的數(shù)據(jù)中難以學(xué)習(xí)到泛化能力強(qiáng)的模式。3.特征選擇不當(dāng):包含過(guò)多冗余或不相關(guān)的特征，增加了模型的復(fù)雜度和過(guò)擬合風(fēng)險(xiǎn)。避免技術(shù)方法:1.正則化(Regularization):在損失函數(shù)中加入一個(gè)懲罰項(xiàng)，限制模型參數(shù)的大?。↙1正則化，參數(shù)稀疏；L2正則化，參數(shù)收縮）。如Ridge回歸、Lasso回歸。2.交叉驗(yàn)證(Cross-Validation):使用k折交叉驗(yàn)證等方法更可靠地評(píng)估模型在未見(jiàn)數(shù)據(jù)上的性能，幫助選擇合適的模型復(fù)雜度或超參數(shù)。3.減少特征維度:使用特征選擇技術(shù)（如相關(guān)性分析、卡方檢驗(yàn)、遞歸特征消除）或特征降維技術(shù)（如PCA）減少輸入特征的個(gè)數(shù)。七、比較:快速排序(QuickSort):*時(shí)間復(fù)雜度:平均O(nlogn)，最壞O(n2)（當(dāng)每次劃分都極不平衡時(shí)，如已排序數(shù)組選擇固定樞軸）。最好O(nlogn)（每次劃分都盡可能平衡）。*空間復(fù)雜度:遞歸實(shí)現(xiàn)平均O(logn)（?？臻g），最壞O(n)。非遞歸或迭代實(shí)現(xiàn)可優(yōu)化至O(logn)或O(1)。*穩(wěn)定性:不穩(wěn)定排序。相同元素的相對(duì)順序可能改變。*適用場(chǎng)景:通常作為C語(yǔ)言庫(kù)函數(shù)實(shí)現(xiàn)，效率高，原地排序（空間復(fù)雜度可優(yōu)化），適合大數(shù)組排序。歸并排序(MergeSort):*時(shí)間復(fù)雜度:穩(wěn)定O(nlogn)，無(wú)論最好、平均、最壞情況。*空間復(fù)雜度:O(n)，需要額外的空間來(lái)合并子數(shù)組。*穩(wěn)定性:穩(wěn)定排序。相同元素的相對(duì)順序不變。*適用場(chǎng)景:當(dāng)穩(wěn)定性是要求時(shí)（如需要保持記錄原始順序），或數(shù)據(jù)量太大無(wú)法放入內(nèi)存時(shí)（外排序），或需要保證最壞情況時(shí)間復(fù)雜度時(shí)。八、最短路徑問(wèn)題定義:在一個(gè)帶權(quán)圖中，尋找連接給定源點(diǎn)s和目標(biāo)點(diǎn)t（或所有其他點(diǎn)）之間的路徑，使得該路徑上所有邊的權(quán)重之和最小。Dijkstra算法思想:基于貪心策略，維護(hù)一個(gè)已確定最短路徑的頂點(diǎn)集合S和一個(gè)到源點(diǎn)s的距離集合dist。初始s∈S，dist[s]=0，dist[v]=∞（v≠s）。在每次迭代中，從未在S中的頂點(diǎn)中選取dist值最小的一個(gè)頂點(diǎn)u加入S。然后，更新所有與u相鄰且不在S中的頂點(diǎn)v的dist[v]值，即dist[v]=min(dist[v],dist[u]+w(u,v))，其中w(u,v)是u到v的邊權(quán)重。重復(fù)直到目標(biāo)點(diǎn)t被加入S或所有可達(dá)頂點(diǎn)都已加入S。Bellman-Ford算法思想:使用動(dòng)態(tài)規(guī)劃思想，迭代計(jì)算從源點(diǎn)s到所有其他頂點(diǎn)的最短路徑估計(jì)值。算法進(jìn)行V-1次迭代（V是頂點(diǎn)數(shù)），在第k次迭代中，嘗試用k條邊更新每個(gè)頂點(diǎn)的最短路徑估計(jì)值。對(duì)于每個(gè)頂點(diǎn)v，檢查是否存在一條通過(guò)k-1條邊到達(dá)v的前驅(qū)頂點(diǎn)u，使得從s到u的最短路徑估計(jì)值加上邊(u,v)的權(quán)重w(u,v)小于當(dāng)前v的最短路徑估計(jì)值。如果存在，則更新v的估計(jì)值。如果任何頂點(diǎn)的最短路徑估計(jì)值在k次迭代中發(fā)生更新，則繼續(xù)第k+1次迭代。適用場(chǎng)景:*Dijkstra算法適用于邊權(quán)重非負(fù)的圖。通常使用優(yōu)先隊(duì)列（堆）實(shí)現(xiàn)，可達(dá)最壞時(shí)間復(fù)雜度O((E+V)logV)。*Bellman-Ford算法適用于邊權(quán)重可正可負(fù)的圖，但需要檢測(cè)負(fù)權(quán)重環(huán)（若存在，則最短路徑無(wú)定義）。時(shí)間復(fù)雜度O(VE)。九、K-均值聚類步驟:1.初始化:隨機(jī)選擇K個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心（質(zhì)心）。2.分配:將每個(gè)數(shù)據(jù)點(diǎn)分配給距離其最近的聚類中心，形成K個(gè)初始簇。3.更新:對(duì)于每個(gè)簇，計(jì)算該簇內(nèi)所有數(shù)據(jù)點(diǎn)的均值，并將該均值作為新的聚類中心。4.迭代:重復(fù)步驟2和步驟3，直到聚類中心不再發(fā)生顯著變化，或者達(dá)到預(yù)設(shè)的最大迭代次數(shù)。確定K值方法:1.肘部法則(ElbowMethod):計(jì)算不同K值（從1到某個(gè)最大值）下的K-均值聚類總內(nèi)平方和（SSE，即所有點(diǎn)到其簇中心的距離平方和）。繪制K值與SSE的曲線。曲線開(kāi)始時(shí)隨著K值增加SSE快速下降，當(dāng)K值增大到某個(gè)點(diǎn)后，SSE下降速度明顯變緩，曲線形成一個(gè)“肘部”。這個(gè)“肘部”對(duì)應(yīng)的K值被認(rèn)為是比較合理的聚類數(shù)目。該方法直觀，但選擇可能帶有主觀性。2.輪廓系數(shù)法(SilhouetteCoefficient):對(duì)于每個(gè)數(shù)據(jù)點(diǎn)i，計(jì)算其與同簇內(nèi)其他點(diǎn)的平均距離a_i（凝聚度）和其到最近的非同簇內(nèi)點(diǎn)的平均距離b_i（分離度）。輪廓系數(shù)s_i=(b_i-a_