2025年大學(xué)《信息與計(jì)算科學(xué)》專業(yè)題庫——信息與計(jì)算科學(xué)專業(yè)實(shí)踐任務(wù)考試時(shí)間：______分鐘總分：______分姓名：______一、設(shè)計(jì)一個(gè)函數(shù)，接收一個(gè)字符串作為輸入，該字符串僅包含小寫字母和數(shù)字。函數(shù)需要找到并返回字符串中所有數(shù)字字符組成的子串的最大乘積。例如，對于輸入字符串"abc1234def56gh789"，函數(shù)應(yīng)返回"56"和"789"的乘積5040，并輸出這個(gè)最大乘積值。請描述你的算法思路，并用你熟悉的編程語言實(shí)現(xiàn)該函數(shù)。二、給定一個(gè)無向圖G=(V,E)，其中V是頂點(diǎn)集合，E是邊集合。假設(shè)圖G已經(jīng)以鄰接表的形式給出。請?jiān)O(shè)計(jì)一個(gè)算法，找出圖G中的所有連通分量，并輸出每個(gè)連通分量的頂點(diǎn)集合。要求算法的空間復(fù)雜度盡可能低。請描述你的算法思路。三、編寫一個(gè)函數(shù)，該函數(shù)接收一個(gè)整數(shù)n作為輸入，并生成一個(gè)nxn的矩陣。矩陣的對角線（從左上到右下）以及與對角線平行的次對角線（從右上到左下）上的元素值為1，其余元素值為0。例如，當(dāng)n=4時(shí)，生成的矩陣應(yīng)如下所示：```1001011001101001```請用你熟悉的編程語言實(shí)現(xiàn)該函數(shù)，并確保函數(shù)能夠處理n為奇數(shù)和偶數(shù)的情況。四、考慮如下遞推關(guān)系式：T(0)=1T(1)=2T(n)=T(n-1)+T(n-2)+T(n-3)，對于n>1其中T(n)表示第n項(xiàng)的值。編寫一個(gè)函數(shù)，使用循環(huán)而非遞歸的方式計(jì)算T(n)的值。請分析該函數(shù)的時(shí)間復(fù)雜度。五、假設(shè)你需要對一串測量數(shù)據(jù)進(jìn)行平滑處理，以減少噪聲干擾。請描述一種常用的平滑算法（如移動(dòng)平均法、中值濾波法等），并說明其基本原理。然后，假設(shè)你有一串包含噪聲的整數(shù)測量數(shù)據(jù)`data=[10,12,11,15,18,16,14,13,17,19]`，請使用你所描述的平滑算法（可以選擇其中一種進(jìn)行計(jì)算），計(jì)算得到平滑后的數(shù)據(jù)序列，并簡述計(jì)算過程。試卷答案一、算法思路：遍歷字符串，遇到數(shù)字字符時(shí)，將其加入當(dāng)前數(shù)字子串；遇到非數(shù)字字符時(shí)，計(jì)算當(dāng)前數(shù)字子串表示的數(shù)值，并與已記錄的最大乘積進(jìn)行比較，更新最大乘積。最后，對所有記錄的非空數(shù)字子串的數(shù)值進(jìn)行乘積計(jì)算，并返回其中的最大值。實(shí)現(xiàn)（偽代碼示例）：```functionfindMaxProductSubstring(s):max_product=0current_number_str=""forcharins:ifcharisdigit:current_number_str+=charelse:ifcurrent_number_str!="":num=convertToNumber(current_number_str)ifnum>0:ifmax_product==0ornum>max_product:max_product=num#同時(shí)計(jì)算所有數(shù)字的乘積ifcurrent_number_str!="":ifmax_product==0:max_product=numelse:max_product*=numcurrent_number_str=""#處理字符串末尾如果是數(shù)字的情況ifcurrent_number_str!="":num=convertToNumber(current_number_str)ifnum>0:ifmax_product==0ornum>max_product:max_product=numifcurrent_number_str!="":ifmax_product==0:max_product=numelse:max_product*=numreturnmax_product```二、算法思路：使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）。初始化一個(gè)visited集合記錄已訪問的頂點(diǎn)。選擇一個(gè)未訪問的頂點(diǎn)，以它為起點(diǎn)進(jìn)行DFS/BFS，將所有可達(dá)的頂點(diǎn)加入當(dāng)前連通分量，并標(biāo)記為已訪問。重復(fù)此過程，直到所有頂點(diǎn)都被訪問過。每次DFS/BFS完成后得到的一個(gè)頂點(diǎn)集合即為一個(gè)連通分量。三、實(shí)現(xiàn)（Python示例）：```pythondefgenerate_matrix(n):matrix=[[0for_inrange(n)]for_inrange(n)]foriinrange(n):matrix[i][i]=1#主對角線matrix[i][n-1-i]=1#次對角線returnmatrix```解析：創(chuàng)建一個(gè)nxn的二維列表（矩陣），初始化所有元素為0。然后，通過兩層循環(huán)遍歷矩陣的每個(gè)元素。對于位于第i行第i列的元素（主對角線）以及位于第i行第(n-1-i)列的元素（次對角線），將其值設(shè)置為1。四、實(shí)現(xiàn)（Python示例）：```pythondefcalculate_T(n):ifn==0:return1elifn==1:return2elifn==2:return4a,b,c=1,2,4foriinrange(3,n+1):a,b,c=b,c,a+b+creturnc```解析：首先處理n=0,1,2的基本情況。對于n>2的情況，使用循環(huán)，并初始化三個(gè)變量a,b,c分別存儲(chǔ)T(n-3),T(n-2),T(n-1)的初始值。在循環(huán)中，更新這三個(gè)變量為它們各自的后繼值，即T(n-2),T(n-1),T(n)，直到計(jì)算到T(n)。時(shí)間復(fù)雜度為O(n)，因?yàn)檠h(huán)執(zhí)行了n-2次。五、描述（以移動(dòng)平均法為例）：移動(dòng)平均法是一種簡單平滑技術(shù)，通過對時(shí)間序列數(shù)據(jù)中的連續(xù)若干期數(shù)據(jù)進(jìn)行平均，來消除短期波動(dòng)，揭示數(shù)據(jù)underlying的趨勢。其基本原理是賦予最近觀測值更高的權(quán)重或同等權(quán)重后進(jìn)行平均。例如，簡單移動(dòng)平均（SMA）對最近k期數(shù)據(jù)進(jìn)行算術(shù)平均；加權(quán)移動(dòng)平均（WMA）則對最近k期數(shù)據(jù)賦予不同權(quán)重（通常是遞減的）后求和；指數(shù)平滑（ES）則使用平滑系數(shù)α遞歸地計(jì)算，賦予近期數(shù)據(jù)更高權(quán)重。計(jì)算過程（以簡單移動(dòng)平均法，窗口大小k=3為例）：原始數(shù)據(jù)：[10,12,11,15,18,16,14,13,17,19]計(jì)算位置3的平均值：(10+12+11)/3=11.0計(jì)算位置4的平均值：(12+11+15)/3=13.0計(jì)算位置5的平均值：(11+15+18)/3=14.0計(jì)算位置6的平均值：(15+18+16)/3=16.0計(jì)算位置7的平均值：(18+16+14