2025年大學(xué)《信息與計算科學(xué)》專業(yè)題庫——信息與計算科學(xué)的實踐環(huán)節(jié)考試時間：______分鐘總分：______分姓名：______一、編程題（每題25分，共50分）1.編寫一個Python函數(shù)，實現(xiàn)快速排序算法。該函數(shù)接收一個整數(shù)列表作為輸入，返回排序后的列表。請展示函數(shù)定義，并在函數(shù)外部調(diào)用該函數(shù)對列表`[34,7,23,32,5,62]`進(jìn)行排序，打印排序前后的列表。2.編寫一個C++函數(shù)，計算一個給定正整數(shù)n的所有正因數(shù)的和。例如，如果n=12，其正因數(shù)為1,2,3,4,6,12，和為28。請展示函數(shù)定義，并在主函數(shù)中調(diào)用該函數(shù)計算數(shù)字30的所有正因數(shù)之和，并輸出結(jié)果。二、算法設(shè)計題（每題25分，共50分）1.假設(shè)你有一個包含n個元素的整數(shù)數(shù)組，其中所有元素都是正數(shù)，并且數(shù)組中的每個元素都只出現(xiàn)一次。設(shè)計一個算法，找出數(shù)組中出現(xiàn)次數(shù)最多的元素。請描述你的算法思路，并用自然語言清晰地解釋算法的每一步。不需要編寫代碼，但要說明你需要的輔助數(shù)據(jù)結(jié)構(gòu)（如果有的話）以及每個步驟的時間復(fù)雜度分析（最好）。2.描述一個算法，用于在一個大小為mxn的二維矩陣中查找一個特定的整數(shù)x。該矩陣中的元素是按行優(yōu)先順序存儲的，并且每一行的元素都是升序排列的，每一列的元素也是升序排列的。請用自然語言清晰地解釋你的算法思路，并分析該算法在最壞情況下的時間復(fù)雜度。不需要編寫代碼。試卷答案一、編程題1.Python代碼：```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)original_list=[34,7,23,32,5,62]sorted_list=quick_sort(original_list)print("Originallist:",original_list)print("Sortedlist:",sorted_list)```解析思路：快速排序是一種分治算法?；舅枷胧沁x擇一個基準(zhǔn)值（pivot），然后將數(shù)組分為三個部分：小于基準(zhǔn)值的元素、等于基準(zhǔn)值的元素、大于基準(zhǔn)值的元素。接著對小于和大于基準(zhǔn)值的兩部分遞歸地進(jìn)行快速排序。上述代碼使用了列表推導(dǎo)式來創(chuàng)建三個列表，并使用遞歸調(diào)用`quick_sort`函數(shù)進(jìn)行排序。最后打印原始列表和排序后的列表。2.C++代碼：```cpp#include<iostream>usingnamespacestd;intsum_of_divisors(intn){intsum=0;for(inti=1;i<=n;++i){if(n%i==0){sum+=i;}}returnsum;}intmain(){intresult=sum_of_divisors(30);cout<<"Sumofdivisorsof30:"<<result<<endl;return0;}```解析思路：計算一個正整數(shù)n的所有正因數(shù)的和，可以通過遍歷從1到n的所有整數(shù)，檢查每個整數(shù)是否能整除n。如果能整除，則將該整數(shù)加到總和中。上述代碼定義了一個`sum_of_divisors`函數(shù)，使用一個for循環(huán)遍歷所有可能的因數(shù)，并使用`if`語句檢查是否能整除n。最后在`main`函數(shù)中調(diào)用該函數(shù)計算30的因數(shù)和，并輸出結(jié)果。二、算法設(shè)計題1.算法思路：使用哈希表（或字典）來記錄每個元素出現(xiàn)的次數(shù)。遍歷數(shù)組，對于每個元素，如果它在哈希表中已經(jīng)存在，則將其對應(yīng)的計數(shù)加1；如果它不存在，則將其添加到哈希表中，并設(shè)置計數(shù)為1。遍歷結(jié)束后，遍歷哈希表，找到計數(shù)最大的元素，即為出現(xiàn)次數(shù)最多的元素。輔助數(shù)據(jù)結(jié)構(gòu)：哈希表（或字典），鍵為數(shù)組中的元素，值為該元素出現(xiàn)的次數(shù)。時間復(fù)雜度分析：遍歷數(shù)組的時間復(fù)雜度為O(n)，遍歷哈希表的時間復(fù)雜度最壞情況下為O(n)。因此，總的時間復(fù)雜度為O(n)。2.算法思路：從矩陣的右上角（或左上角）開始。比較當(dāng)前元素與目標(biāo)值x。如果當(dāng)前元素等于x，則找到目標(biāo)值，算法結(jié)束。如果當(dāng)前元素大于x，則向左移動（因為當(dāng)前列的元素都大于x）。如果當(dāng)前元素小于x，則向下移動（因為當(dāng)前行的元素都小于x）。重復(fù)上述步驟，直到找到目標(biāo)值或超出矩陣邊界。由于矩陣的每行每列都是有序的，因此每次移動可以排除