2025年大學《信息與計算科學》專業(yè)題庫——信息與計算科學的專業(yè)實踐考試時間：______分鐘總分：______分姓名：______一、選擇題（每小題2分，共10分）1.下列關于算法復雜度的說法中，正確的是（）。A.算法的時間復雜度與空間復雜度總是成正比。B.優(yōu)化算法的時間復雜度通常會導致空間復雜度的增加。C.算法的實際運行時間主要取決于算法的時間復雜度。D.算法的空間復雜度是指算法執(zhí)行過程中所需的內(nèi)存空間。2.在下列數(shù)據(jù)結構中，適合表示元素之間具有多對多關系的是（）。A.數(shù)組B.棧C.隊列D.圖3.下列關于快速排序算法的說法中，錯誤的是（）。A.快速排序是一種基于分治策略的排序算法。B.快速排序的平均時間復雜度為O(n^2)。C.快速排序的空間復雜度為O(logn)。D.快速排序是不穩(wěn)定的排序算法。4.在下列數(shù)據(jù)庫術語中，表示從關系中選擇滿足給定條件的元組的是（）。A.連接B.選擇C.投影D.連接5.下列關于機器學習算法的說法中，錯誤的是（）。A.決策樹是一種監(jiān)督學習算法。B.聚類算法是一種無監(jiān)督學習算法。C.支持向量機主要用于分類和回歸問題。D.神經(jīng)網(wǎng)絡是一種半監(jiān)督學習算法。二、填空題（每小題2分，共10分）1.在深度優(yōu)先搜索算法中，用于存儲已訪問節(jié)點的數(shù)據(jù)結構通常是________。2.算法的________是指算法執(zhí)行所需的內(nèi)存空間。3.在關系數(shù)據(jù)庫中，滿足ACID特性的數(shù)據(jù)庫事務具有________、原子性、持久性和隔離性。4.機器學習中，過擬合是指模型對訓練數(shù)據(jù)擬合得太好，而失去了對________數(shù)據(jù)的泛化能力。5.數(shù)字信號處理中，常用的濾波器類型有低通濾波器、高通濾波器、帶通濾波器和________。三、計算題（每小題5分，共10分）1.計算下列遞歸函數(shù)的遞歸式，并求其時間復雜度：functionfib(n):ifn<=2:return1else:returnfib(n-1)+fib(n-2)2.已知矩陣A和B如下，計算矩陣A和B的乘積C=AB：A=[[1,2],[3,4]]B=[[2,0],[1,2]]四、編程題（每小題10分，共20分）1.編寫一個函數(shù)，實現(xiàn)快速排序算法。輸入?yún)?shù)為一個整數(shù)數(shù)組，輸出參數(shù)為對數(shù)組進行快速排序后的結果。2.編寫一個Python程序，實現(xiàn)以下功能：讀取一個文本文件，統(tǒng)計文件中每個單詞出現(xiàn)的次數(shù)，并將結果按照出現(xiàn)次數(shù)從高到低排序輸出。假設單詞之間由空格分隔。五、綜合應用題（每小題15分，共30分）1.假設你正在開發(fā)一個推薦系統(tǒng)，用戶可以通過評分來表示對物品的喜好程度。請簡述使用協(xié)同過濾算法進行推薦的原理，并說明該算法的優(yōu)缺點。2.設計一個算法，實現(xiàn)圖像的灰度化處理。要求描述算法的基本步驟，并說明如何處理圖像中的彩色像素。試卷答案一、選擇題1.B2.D3.B4.B5.D二、填空題1.棧2.空間復雜度3.一致性4.測試5.阻塞濾波器三、計算題1.遞歸式：T(n)=T(n-1)+T(n-2)+O(1)時間復雜度：O(2^n)(斐波那契數(shù)列遞歸解法的時間復雜度為指數(shù)級)2.C=AB=[[1*2+2*1,1*0+2*2],[3*2+4*1,3*0+4*2]]=[[4,4],[10,8]]四、編程題1.(代碼略，參考快速排序算法實現(xiàn))2.(代碼略，參考文件讀取、字符串分割、字典統(tǒng)計、排序輸出)五、綜合應用題1.原理：協(xié)同過濾算法利用用戶之間的相似性或物品之間的相似性進行推薦?；谟脩舻膮f(xié)同過濾通過找到與目標用戶興趣相似的其他用戶，將這些相似用戶喜歡的物品推薦給目標用戶。基于物品的協(xié)同過濾通過找到與目標用戶喜歡的物品相似的物品，將這些相似物品推薦給目標用戶。優(yōu)點：簡單直觀，不需要物品的領域知識。缺點：可擴展性差，數(shù)據(jù)稀疏性問題，冷啟動問題。2.算法步驟：a.讀取圖像數(shù)據(jù)。b.遍歷圖像中的每個像素。c.對于每個像素，根據(jù)其RGB值計算灰度值。常用的灰度化公式有：-灰度值=0.299*R+0.587*G+0.114*B(加權平均法)-灰度值=(R