2025年大學《信息與計算科學》專業(yè)題庫——信息與計算科學專業(yè)實驗教學考試時間：______分鐘總分：______分姓名：______一、簡述數(shù)值計算中誤差的來源有哪些？并說明減少舍入誤差和截斷誤差的主要方法。二、為什么說牛頓迭代法在根的附近收斂速度比二分法快？請從迭代公式和收斂速度的角度進行比較說明。三、給定數(shù)據(jù)點(1,3),(2,6),(3,11),(4,18)。分別用線性插值和二次插值求函數(shù)在x=2.5處的近似值。寫出插值公式，并計算結(jié)果。四、編寫一個函數(shù)，實現(xiàn)快速排序算法。輸入?yún)?shù)為一個整數(shù)數(shù)組，輸出參數(shù)為排序后的數(shù)組。要求在函數(shù)內(nèi)部完成排序，不使用庫函數(shù)。五、計算定積分∫[0,1]e^(-x^2)dx的近似值。要求使用辛普森法則，并將積分區(qū)間等分為4段進行計算。六、假設(shè)一個簡單的線性回歸模型為y=β?+β?x+ε，其中ε服從均值為0的正態(tài)分布。請寫出使用最小二乘法估計參數(shù)β?和β?的公式。七、解釋什么是算法的時間復雜度和空間復雜度。分別給出以下兩個函數(shù)的時間復雜度：```pythondeffunc1(n):sum=0foriinrange(n):sum+=ireturnsumdeffunc2(n):result=1foriinrange(1,n+1):result*=ireturnresult```八、設(shè)計一個實驗方案，用于測試不同排序算法（如冒泡排序、選擇排序、插入排序）在處理大規(guī)模隨機數(shù)據(jù)時的效率。說明需要收集哪些數(shù)據(jù)，以及如何分析這些數(shù)據(jù)以比較算法性能。試卷答案一、誤差來源主要包括：舍入誤差（數(shù)值運算過程中的精度損失）和截斷誤差（用近似公式代替精確公式產(chǎn)生的誤差）。減少舍入誤差的方法有使用更高精度的數(shù)據(jù)類型、改善算法的數(shù)值穩(wěn)定性等；減少截斷誤差的方法有提高算法的精度（如使用泰勒展開更高階項）、使用更精確的數(shù)值方法等。二、牛頓迭代法的迭代公式為x???=x?-f(x?)/f'(x?)。若初始值x?在根α附近，且f'(α)≠0，則牛頓迭代法具有二階收斂速度，即誤差大致按平方速度減小。而二分法每次迭代將區(qū)間長度減半，其收斂速度是線性的（誤差大致減半）。因此，在根的附近，牛頓迭代法的收斂速度明顯快于二分法。三、線性插值：過點(1,3)和(2,6)，插值公式為L?(x)=(x-2)/(1-2)*3+(x-1)/(2-1)*6=-3x+9。L?(2.5)=-3*2.5+9=1.5。二次插值：過點(1,3),(2,6),(3,11)，插值公式為L?(x)=((x-2)(x-3)/(1-2)(1-3))*3+((x-1)(x-3)/(2-1)(2-3))*6+((x-1)(x-2)/(3-1)(3-2))*11=-x2+5x-2。L?(2.5)=-(2.5)2+5*2.5-2=-6.25+12.5-2=4.25。四、```pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)```*解析思路：采用分治策略。選擇一個基準值（pivot），將數(shù)組劃分為小于、等于、大于基準值的三部分。遞歸地對小于和大于基準值的部分進行排序，最后將排序好的三部分合并。*五、將[0,1]區(qū)間等分為4段，每段寬度h=(1-0)/4=0.25。節(jié)點為0,0.25,0.5,0.75,1。使用辛普森法則公式∫[a,b]f(x)dx≈(h/3)[f(a)+4f(a+h)+4f(a+2h)+f(b)]計算如下：∫[0,1]e^(-x^2)dx≈(0.25/3)[e^(0)+4e^(-0.25^2)+4e^(-0.5^2)+e^(-1^2)]≈(1/12)[1+4e^(-0.0625)+4e^(-0.25)+e^(-1)]≈(1/12)[1+4*0.9394+4*0.7788+0.3679]≈(1/12)[1+3.7576+3.1152+0.3679]≈(1/12)*8.2407≈0.6867六、最小二乘法估計參數(shù)公式：β?=[n*Σ(xi*yi)-Σxi*Σyi]/[n*Σ(xi2)-(Σxi)2]β?=(Σyi-β?*Σxi)/n其中，n為樣本數(shù)量，xi,yi為數(shù)據(jù)點的橫縱坐標。七、時間復雜度是指算法執(zhí)行時間隨輸入規(guī)模n的增長趨勢。func1(n)中有一個循環(huán)，執(zhí)行n次。時間復雜度為O(n)。func2(n)中有一個循環(huán)，執(zhí)行n次。時間復雜度為O(n)。八、實驗方案：1.準備數(shù)據(jù)：生成不同規(guī)模（如1000,10000,100000）的隨機整數(shù)數(shù)組作為待排序數(shù)據(jù)。2.選擇算法：確定要測試的算法（冒泡、選擇、插入）。3.測試執(zhí)行：對每種規(guī)模的數(shù)據(jù)，分別使用三種排序算法進行排序。使用高精度計時器（如Python的time.perf_counter()）記錄每種算法從開始到結(jié)束的總耗時。4.收集數(shù)據(jù)：記錄下每種規(guī)模