2025年大學(xué)《信息與計算科學(xué)》專業(yè)題庫——信息與計算科學(xué)專業(yè)實踐活動考試時間：______分鐘總分：______分姓名：______一、基礎(chǔ)操作與編程實現(xiàn)1.編寫一個函數(shù)，接收一個非空整數(shù)數(shù)組`arr`和一個整數(shù)`target`，返回一個包含所有可以使`arr[i]+arr[j]==target`的數(shù)對`(i,j)`的列表。其中，`i!=j`。要求不重復(fù)使用同一個元素，你可以按順序返回答案。例如，給定數(shù)組`nums=[2,7,11,15]`，目標數(shù)`target=9`，函數(shù)應(yīng)返回`[[0,1]]`，因為`nums[0]+nums[1]==9`。2.設(shè)計一個棧（Stack）數(shù)據(jù)結(jié)構(gòu)，支持如下操作：*`push(x)`：將元素`x`壓入棧頂。*`pop()`：彈出棧頂元素。*`top()`：獲取棧頂元素。*`getMin()`：獲取棧中最小元素的值。請用Python或C++語言實現(xiàn)該數(shù)據(jù)結(jié)構(gòu)，要求`getMin`操作的時間復(fù)雜度為O(1)。二、算法設(shè)計與分析3.給定一個包含`n`個整數(shù)的數(shù)組`nums`，判斷該數(shù)組中是否存在三個元素a,b,c，使得a+b+c=0？請找出所有滿足條件且不重復(fù)的三元組。你可以假設(shè)每個輸入只對應(yīng)一個答案，但你可以重復(fù)使用數(shù)組中的不同元素。例如，給定數(shù)組`nums=[-1,0,1,2,-1,-4]`，滿足條件的三元組有`[-1,0,1]`和`[-1,-1,2]`。4.在一個二維網(wǎng)格`grid`中，每個單元格可以有不同的顏色（用整數(shù)表示）。我們需要找到所有大小至少為2x2的所有不同顏色的矩形。請返回矩形的數(shù)量。例如，給定`grid=[[1,0,1],[1,1,1],[1,0,1]]`，矩形數(shù)量為2。三、專業(yè)軟件/工具應(yīng)用5.假設(shè)你正在使用Python的NumPy庫進行數(shù)據(jù)分析。給定一個形狀為(10,10)的隨機整數(shù)數(shù)組`arr`（值域為`[0,100]`），請編寫代碼完成以下任務(wù)：*計算數(shù)組全局的最大值和最小值。*計算數(shù)組每一行的平均值，并將平均值低于全局平均值的行的索引輸出。*創(chuàng)建一個新的數(shù)組`b`，其元素為`arr`中每個元素減去其所在行的平均值的平方。*計算數(shù)組`b`的特征值（eigenvalues）。6.使用MATLAB或Python(withmatplotlib)對函數(shù)`f(x)=sin(x)*exp(-x^2/10)`在區(qū)間`[0,5]`上進行數(shù)值積分，計算其近似值。并繪制該函數(shù)在指定區(qū)間的圖像，要求圖像包含標題、坐標軸標簽，并適當設(shè)置坐標軸范圍以清晰展示函數(shù)形態(tài)。四、項目實踐與綜合應(yīng)用7.設(shè)計一個簡單的文本文件統(tǒng)計程序。程序應(yīng)能讀取一個指定的文本文件（假設(shè)文件編碼為UTF-8），統(tǒng)計并輸出以下信息：*文件中的總字符數(shù)（不包括空格和標點符號）。*文件中的總詞數(shù)（以空格、標點符號或換行符作為詞與詞之間的分隔）。*出現(xiàn)頻率最高的5個單詞及其出現(xiàn)次數(shù)（忽略大小寫，僅統(tǒng)計字母組成的單詞）。*要求程序能處理文件不存在或讀取錯誤的情況，并給出相應(yīng)的提示信息。8.假設(shè)你需要模擬一個簡單的銀行排隊系統(tǒng)。系統(tǒng)中有`k`個窗口，顧客按到達時間的先后順序依次進入隊列。當隊列中有顧客等待，且有空閑窗口時，隊列中的第一個顧客進入第一個空閑窗口；當有空閑窗口時，新到達的顧客立即進入該窗口；當所有窗口均忙時，新顧客排隊等待。請用Python編寫一個模擬程序，模擬`n`個顧客在`t`時間內(nèi)（以秒為單位）的排隊和服務(wù)過程，記錄每個顧客的等待時間和服務(wù)時間（假設(shè)每個顧客的服務(wù)時間固定為`service_time`秒）。最后輸出平均等待時間和平均服務(wù)時間。試卷答案一、基礎(chǔ)操作與編程實現(xiàn)1.解析思路:使用哈希表（字典）記錄每個數(shù)字及其索引。遍歷數(shù)組，對于每個元素`nums[i]`，計算`target-nums[i]`并在哈希表中查找。如果找到，則返回當前索引`i`和哈希表中記錄的索引。為避免重復(fù)元素產(chǎn)生重復(fù)數(shù)對，可以在查找前檢查當前元素是否等于前一個元素，如果是，則跳過或更新哈希表。```python#偽代碼示例deftwoSum(nums,target):num_map={}result=[]fori,numinenumerate(nums):complement=target-numifcomplementinnum_map:result.append([num_map[complement],i])num_map[num]=ireturnresult```2.解析思路:使用兩個棧。一個棧`stack`用于正常壓入和彈出操作。另一個輔助棧`min_stack`用于存儲當前棧中的最小值。壓入時，將元素`x`與`min_stack`的棧頂元素比較，如果`min_stack`為空或`x`小于等于`min_stack`棧頂元素，則將`x`也壓入`min_stack`。彈出時，如果彈出的元素等于`min_stack`棧頂元素，則`min_stack`也要彈出棧頂。`top()`操作直接返回`stack`棧頂元素。`getMin()`操作返回`min_stack`棧頂元素，時間復(fù)雜度為O(1)。```python#偽代碼示例classMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,x):self.stack.append(x)ifnotself.min_stackorx<=self.min_stack[-1]:self.min_stack.append(x)defpop(self):ifself.stack:top=self.stack.pop()iftop==self.min_stack[-1]:self.min_stack.pop()returntopdeftop(self):returnself.stack[-1]ifself.stackelseNonedefgetMin(self):returnself.min_stack[-1]ifself.min_stackelseNone```二、算法設(shè)計與分析3.解析思路:先對數(shù)組進行排序。排序后，使用雙指針法（或稱夾逼法）來查找三元組。固定一個數(shù)`nums[i]`，然后使用兩個指針`left`(初始化為`i+1`)和`right`(初始化為`n-1`)分別指向`nums`的左半部分和右半部分。計算`nums[i]+nums[left]+nums[right]`：*如果和等于0，找到了一個解，記錄下來，然后移動`left`和`right`指針，同時跳過重復(fù)元素。*如果和小于0，說明需要更大的數(shù)，因此將`left`指針右移。*如果和大于0，說明需要更小的數(shù)，因此將`right`指針左移。重復(fù)這個過程直到`left`大于`right`。排序的時間復(fù)雜度為O(nlogn)，雙指針遍歷的時間復(fù)雜度為O(n^2)，總體時間復(fù)雜度為O(n^2)。```python#偽代碼示例defthreeSum(nums):nums.sort()result=[]n=len(nums)foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnresult```4.解析思路:使用動態(tài)規(guī)劃。定義一個二維布爾數(shù)組`dp`，其中`dp[i][j]`表示從`(0,0)`到`(i,j)`的矩形區(qū)域是否所有單元格顏色相同。初始時，`dp[0][j]`和`dp[i][0]`由單行和單列決定。然后逐行逐列計算`dp[i][j]`，`dp[i][j]=dp[i-1][j]anddp[i][j-1]anddp[i-1][j-1]andgrid[i][j]==grid[i-1][j]==grid[i][j-1]==grid[i-1][j-1]`。如果`dp[i][j]`為`True`，則說明`(0,0)`到`(i,j)`的矩形區(qū)域顏色相同。最后統(tǒng)計所有滿足`dp[i][j]`為`True`且`i>=1`和`j>=1`的`(i,j)`對，即為不同顏色的矩形數(shù)量。時間復(fù)雜度為O(n^2*m^2)，其中n和m分別為網(wǎng)格的行數(shù)和列數(shù)。```python#偽代碼示例defcountSquares(grid):ifnotgridornotgrid[0]:return0n,m=len(grid),len(grid[0])dp=[[False]*mfor_inrange(n)]count=0foriinrange(n):forjinrange(m):ifgrid[i][j]==1:ifi==0orj==0:dp[i][j]=Trueelse:dp[i][j]=dp[i-1][j]anddp[i][j-1]anddp[i-1][j-1]andgrid[i][j]==grid[i-1][j]==grid[i][j-1]==grid[i-1][j-1]ifdp[i][j]:count+=1returncount```三、專業(yè)軟件/工具應(yīng)用5.解析思路:利用NumPy的廣播和聚合函數(shù)。*使用`np.max(arr)`和`np.min(arr)`獲取全局最大值和最小值。*使用`np.mean(arr,axis=1)`計算每行的平均值。然后使用`np.mean(arr)`計算全局平均值。比較每行的平均值與全局平均值，使用布爾索引`np.where`輸出滿足條件的行索引。*首先計算每行的平均值`row_means`。然后使用NumPy廣播，`arr-row_means`會自動擴展`row_means`以匹配`arr`的形狀，每個元素減去其所在行的平均值。最后使用`np.linalg.eigvals`函數(shù)計算結(jié)果數(shù)組`b`的特征值。```pythonimportnumpyasnp#偽代碼示例#假設(shè)arr已經(jīng)定義max_val=np.max(arr)min_val=np.min(arr)row_means=np.mean(arr,axis=1)global_mean=np.mean(arr)below_global_mean_indices=np.where(row_means<global_mean)[0]b=arr-row_means[:,np.newaxis]#或arr-row_means[:,None]eigenvalues=np.linalg.eigvals(b)```6.解析思路(PythonwithNumPy&Matplotlib):*使用`egrate.quad`函數(shù)進行數(shù)值積分，第一個參數(shù)是積分函數(shù)`lambdax:np.sin(x)*np.exp(-x2/10)`，第二個參數(shù)是積分區(qū)間`[0,5]`。*使用`numpy.linspace`生成`[0,5]`區(qū)間內(nèi)的若干點`x`，計算對應(yīng)的`y=np.sin(x)*np.exp(-x2/10)`值。*使用`matplotlib.pyplot.plot`繪制`x`和`y`的關(guān)系圖。*使用`plt.title`,`plt.xlabel`,`plt.ylabel`添加標題和坐標軸標簽。*使用`plt.xlim([0,5])`或`plt.ylim`適當設(shè)置坐標軸范圍。```pythonimportnumpyasnpfromegrateimportquadimportmatplotlib.pyplotasplt#偽代碼示例#積分deff(x):returnnp.sin(x)*np.exp(-x2/10)integral_result,_=quad(f,0,5)#繪圖x=np.linspace(0,5,400)y=f(x)plt.plot(x,y)plt.title('Plotofsin(x)*exp(-x^2/10)')plt.xlabel('x')plt.ylabel('f(x)')plt.xlim(0,5)#設(shè)置x軸范圍plt.grid(True)plt.show()```四、項目實踐與綜合應(yīng)用7.解析思路:使用Python的內(nèi)置文件操作和字符串方法。*使用`open`讀取文件，處理異常`FileNotFoundError`。*讀取文件內(nèi)容，轉(zhuǎn)換為字符串`text`。*使用`str.translate`和`str.lower`去除空格、標點符號并轉(zhuǎn)為小寫。*使用`str.split`按空白字符分割獲取單詞列表`words`。*使用`collections.Counter`統(tǒng)計單詞頻率。*對`Counter`對象進行`most_common(5)`獲取頻率最高的5個單詞及其計數(shù)。*統(tǒng)計字符數(shù)（不包括空格和標點）可以通過`sum(1forcintextifc.isalnum())`實現(xiàn)。*統(tǒng)計詞數(shù)就是`len(words)`。```pythonimportstringfromcollectionsimportCounter#偽代碼示例filename="input.txt"try:withopen(filename,'r',encoding='utf-8')asfile:text=file.read()#去除標點和空格，轉(zhuǎn)為小寫translator=str.maketrans('','',string.punctuation+'')cleaned_text=text.translate(translator).lower()words=cleaned_text.split()word_counts=Counter(words)most_common_5=word_counts.most_common(5)char_count=sum(1forcintextifc.isalnum())word_count=len(words)print(f"Totalalphanumericcharacters:{char_count}")print(f"Totalwords:{word_count}")print("Top5frequentwords:")forword,freqinmost_common_5:print(f"{word}:{freq}")exceptFileNotFoundError:print(f"Error:Thefile'{filename}'doesnotexist.")```8.解析思路:使用隊列（`collections.deque`或`queue.Queue`）模擬顧客隊列和窗口狀態(tài)。*初始化一個隊列`customer_queue`用于等待的顧客（包含顧客編號和到達時間）。*初始化一個列表`windows`，包含`k`個元素，表示每個窗口的狀態(tài)（`None`表示空閑，否則存儲正在服務(wù)的顧客編號及其服務(wù)結(jié)束時間）。*初始化變量`time`為0，`total_wait_time`和`total_service_time`為0，`served_customers`為0。*循環(huán)模擬直到`time==t`且`customer_queue`為空：*處理窗口:遍歷`windows`，對于每個非空的窗口，檢查其服務(wù)時間是否結(jié)束（`time>=window_end_time`）。如果結(jié)束，將該窗口置為`None`（空閑），并將該顧客的服務(wù)時間累加到`total_service_time`，`served_customers`加1。*安排新顧客:檢查`customer_queue`隊首顧客的到達時間是否小于等于當前時間`time`。如果是，將其出隊。*分配顧客:遍歷`windows`，找到第一個`None`的窗口，將其設(shè)置為當前顧客，記錄服務(wù)結(jié)束時間`window_end_time=time+service_time`。*時間推進:如果沒有顧客被分配（即所有窗口忙且沒有新顧客到達），時間`time`增加一個單位。否則，`time`更新為當前正在服務(wù)的顧客中最早結(jié)束服務(wù)的時間。*計算平均時間:如果`served_customers>0`，則`avg_wait_time=total_wait_time/served_customers`，`avg_service_time=total_service_time/served_customers`。否則，平均時間為0。```pythonfromcollectionsimportdequeimportqueue#偽代碼示例defsimulate_bank_queue(n,t,service_time):customer_queue=deque(range(n))#假設(shè)顧客編號從0到n-1windows=[None]*k#k個窗口，初始都空閑time=0total_wait_time=0total_service_time=0served_customers=0whiletime<torany(wisnotNoneforwinwindows):#處理窗口foriinrange(k):ifwindows[i]isnotNone:customer_id,window_end_time=windows[i]iftime>=window_end_time:#顧客服務(wù)完成total_service_time+=window_end_time-timeserved_customers+=1windows[i]=None#窗口空閑#安排新顧客whilecustomer_queueandcustomer_queue[0]<=time:customer_id=customer_queue.popleft()