2025年大學《信息與計算科學》專業(yè)題庫——信息與計算科學專業(yè)實驗課程設(shè)計考試時間：______分鐘總分：______分姓名：______一、設(shè)計一個算法，用于在給定的包含重復(fù)元素的整數(shù)數(shù)組中找到出現(xiàn)次數(shù)最多的元素及其出現(xiàn)次數(shù)。要求算法首先返回出現(xiàn)次數(shù)最多的元素，如果多個元素出現(xiàn)次數(shù)相同且最多，則返回其中任意一個即可。請描述該算法的思想，并用偽代碼表示算法的主要步驟。二、已知一個無向連通圖G=(V,E)，其中V為頂點集合，E為邊集合。請編寫一個函數(shù)，實現(xiàn)對該圖進行深度優(yōu)先搜索（DFS）。函數(shù)的輸入為圖G和一個起始頂點v∈V，輸出為從頂點v出發(fā)遍歷圖G所訪問的頂點序列（按訪問的先后順序）。要求使用遞歸方式實現(xiàn)DFS。三、使用Python語言，實現(xiàn)一個簡單的文件加密/解密程序。程序要求用戶輸入一個文件路徑、一個密鑰（密鑰為非負整數(shù)），并選擇加密或解密操作。對于加密操作，程序應(yīng)讀取指定文件的內(nèi)容（假設(shè)文件內(nèi)容為ASCII字符），將每個字符的ASCII碼值加上密鑰值，得到新的字符，并將新字符寫入到一個新的文件中（文件名為原文件名后加“.enc”）。對于解密操作，程序應(yīng)執(zhí)行與加密相反的操作，將每個字符的ASCII碼值減去密鑰值，并將結(jié)果寫入新文件（文件名為原文件名去掉“.enc”）。請寫出實現(xiàn)該功能的代碼框架和主要邏輯。四、考慮如下遞推關(guān)系式：f(n)=2*f(n-1)+3*f(n-2)，其中f(0)=1,f(1)=2。請編寫一個函數(shù)，計算該遞推關(guān)系式的第n項值（n為非負整數(shù)）。為了提高計算效率，函數(shù)應(yīng)避免使用簡單的遞歸方式（可能導(dǎo)致大量重復(fù)計算）。請描述你采用的優(yōu)化方法，并給出相應(yīng)的代碼實現(xiàn)。五、假設(shè)你要使用線性回歸模型來擬合一組二維數(shù)據(jù)點（x_i,y_i）(i=1,2,...,n)，其中x_i是自變量，y_i是因變量。請推導(dǎo)出正規(guī)方程（NormalEquation）來求解線性回歸模型的參數(shù)（斜率w和截距b），使得模型對數(shù)據(jù)的平方誤差之和最小。假設(shè)輸入的數(shù)據(jù)點集合為D={(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}。請寫出正規(guī)方程的具體形式，并解釋其中各項的含義。試卷答案一、算法思想：1.初始化一個空的字典（或哈希表）來存儲每個元素及其出現(xiàn)的次數(shù)。2.遍歷數(shù)組中的每個元素。3.對于當前元素，在字典中查找其鍵（元素值）。-如果鍵不存在，則在字典中添加該鍵，并將其值設(shè)置為1。-如果鍵存在，則將該鍵對應(yīng)的值加1。4.遍歷完成后，字典中存儲了所有元素及其出現(xiàn)次數(shù)。5.初始化兩個變量，`max_count`用于存儲最大的出現(xiàn)次數(shù)（初始為0），`max_element`用于存儲出現(xiàn)次數(shù)最多的元素（初始為None）。6.再次遍歷字典的鍵值對。7.對于每個鍵值對（元素,次數(shù)），如果次數(shù)大于`max_count`，則更新`max_count`為該次數(shù)，并將`max_element`更新為該元素。8.遍歷完成后，`max_element`即為出現(xiàn)次數(shù)最多的元素之一，`max_count`為其出現(xiàn)次數(shù)。偽代碼：```functionfindMostFrequentElement(arr):count_dict=newDictionary()max_count=0max_element=None//Step2&3:Countoccurrencesforelementinarr:ifelementnotincount_dict:count_dict[element]=1else:count_dict[element]+=1//Step4,5&7:Findelementwithmaxcountforelement,countincount_dict.items():ifcount>max_count:max_count=countmax_element=element//Step8:Returnresultreturnmax_element,max_count```二、DFS函數(shù)偽代碼：```functionDFS(G,v,visited)://Step1:Markthecurrentnodeasvisitedvisited[v]=true//Step2:Outputthecurrentnode(oraddtooutputlist)outputv//or:result.append(v)//Step3:ForeachadjacentnodewofvforeachwinG.adjacentVertices(v)://Step4:Ifwhasnotbeenvisitedifnotvisited[w]://Step5:RecursivelyperformDFSonwDFS(G,w,visited)```實現(xiàn)要點：1.參數(shù)：圖G（通常用鄰接表或鄰接矩陣表示），起始頂點v，一個用于記錄頂點訪問狀態(tài)的數(shù)組`visited`（初始全為false）。2.遞歸調(diào)用：核心在于`ifnotvisited[w]:DFS(G,w,visited)`這一步，確保每個頂點只被訪問一次。3.輸出：可以在訪問頂點時直接輸出，或?qū)⑵涮砑拥浇Y(jié)果列表中。三、Python代碼框架與邏輯：```pythonimportosdefprocess_file(input_filepath,key,mode='encrypt'):"""mode:'encrypt'or'decrypt'"""#Checkiffileexistsifnotos.path.exists(input_filepath):print(f"Error:File'{input_filepath}'notfound.")returnoutput_filepath=input_filepathifmode=='encrypt':output_filepath=input_filepath+".enc"elifmode=='decrypt':ifnotinput_filepath.endswith(".enc"):print(f"Error:Fordecryption,inputfilemustendwith'.enc'.")returnoutput_filepath=input_filepath[:-4]#Remove".enc"try:withopen(input_filepath,'r',encoding='ascii')asinfile:content=infile.read()result=[]forcharincontent:ifchar.isascii():#EnsurecharacterisASCIIascii_val=ord(char)ifmode=='encrypt':new_ascii=(ascii_val+key)%128#Modulo128tostayinASCIIrangeelifmode=='decrypt':new_ascii=(ascii_val-key)%128new_char=chr(new_ascii)result.append(new_char)else:#Handlenon-ASCIIcharactersifneeded,orskipresult.append(char)#Orhandleerrorwithopen(output_filepath,'w',encoding='ascii')asoutfile:outfile.write(''.join(result))print(f"Processingcomplete.Outputsavedto'{output_filepath}'.")exceptExceptionase:print(f"Anerroroccurred:{e}")#Exampleusage:#process_file('example.txt',5,'encrypt')#process_file('example.enc',5,'decrypt')```四、優(yōu)化方法：使用動態(tài)規(guī)劃（DynamicProgramming）的方法，避免遞歸調(diào)用中的重復(fù)計算。通過自底向上的方式，存儲已經(jīng)計算出的f(i)值，直接復(fù)用。代碼實現(xiàn)：```pythondefcomputeFibonacciOptimized(n):ifn<0:returnNone//Orraiseerror#Basecasesifn==0:return1ifn==1:return2#Initializealisttostorecomputedvalues(memoization)#f[0]=1,f[1]=2f=[0]*(n+1)f[0],f[1]=1,2#Fillthetableiterativelyfrombottomtotopforiinrange(2,n+1):f[i]=2*f[i-1]+3*f[i-2]returnf[n]```五、正規(guī)方程推導(dǎo)與形式：目標：求解參數(shù)`w`和`b`，使得線性模型`y=wx+b`對數(shù)據(jù)點`(x_i,y_i)`的平方誤差之和`S=Σ(y_i-(wx_i+b))^2`最小。步驟：1.誤差函數(shù)：`E(w,b)=(1/2)*Σ(y_i-(wx_i+b))^2`2.最小化條件：對`w`和`b`分別求偏導(dǎo)數(shù)，并令其為0。*對`w`求偏導(dǎo)：`?E/?w=Σ(y_i-(wx_i+b))*(-x_i)=0``Σ(y_i*x_i)-w*Σ(x_i^2)-b*Σ(x_i)=0`*對`b`求偏導(dǎo)：`?E/?b=Σ(y_i-(wx_i+b))*(-1)=0``Σ(y_i)-w*Σ(x_i)-b*n=0`(其中n是數(shù)據(jù)點的數(shù)量)3.求解線性方程組：將上面兩個方程整理為關(guān)于`w`和`b`的線性方程組：*`Σ(x_i^2)*w+Σ(x_i)*b=Σ(y_i*x_i)`*`Σ(x_i)*w+n*b=Σ(y_i)`4.正規(guī)方程形式：將上述方程組寫成矩陣形式`X^TX*θ=X^Ty`，其中：*`θ=[w,b]^T`是參數(shù)向量。*`X`是設(shè)計矩陣，其形式為：```X=|x_11||x_21||...1||x_n1|```(每一行對應(yīng)一個數(shù)據(jù)點`(x_i,y_i)`，第一列是`x_i`值，第二列全是1對應(yīng)截距`b`)。*`y`是因變量向量：