2025年大學(xué)《信息與計(jì)算科學(xué)》專業(yè)題庫(kù)——信息與計(jì)算科學(xué)專業(yè)算法設(shè)計(jì)與分析考試時(shí)間：______分鐘總分：______分姓名：______一、填空題（每空3分，共30分）1.算法的時(shí)間復(fù)雜度通常用大O表示法來描述，它關(guān)注的是算法執(zhí)行時(shí)間隨輸入規(guī)模n增長(zhǎng)的變化趨勢(shì)，忽略__常數(shù)項(xiàng)__和__低階項(xiàng)__。2.在__分治法__策略中，核心思想是將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。3.快速排序算法的平均時(shí)間復(fù)雜度為__O(nlogn)__，最壞情況下的時(shí)間復(fù)雜度為__O(n^2)__。4.貪心算法在每一步都做出當(dāng)前看起來最優(yōu)的選擇，期望通過局部最優(yōu)解達(dá)到全局最優(yōu)解。但貪心算法能否得到最優(yōu)解，取決于問題的__貪心選擇性質(zhì)__和__最優(yōu)子結(jié)構(gòu)性質(zhì)__。5.動(dòng)態(tài)規(guī)劃算法適用于具有__重疊子問題__和__最優(yōu)子結(jié)構(gòu)__性質(zhì)的問題。6.對(duì)于一個(gè)遞歸函數(shù)`voidfun(intn)`，若其遞歸調(diào)用關(guān)系為`fun(n)=2*fun(n-1)+c`，且`fun(1)=a`（其中`a`和`c`為常數(shù)），則其時(shí)間復(fù)雜度T(n)滿足遞推關(guān)系`T(n)=2*T(n-1)+O(1)`，利用主定理分析可得其時(shí)間復(fù)雜度為__O(n)__。7.在線性表的三種基本操作（插入、刪除、查找）中，使用__鏈表__實(shí)現(xiàn)時(shí)，插入和刪除操作的平均時(shí)間復(fù)雜度可以達(dá)到__O(1)__，而使用__數(shù)組__實(shí)現(xiàn)時(shí)，查找操作的平均時(shí)間復(fù)雜度可以達(dá)到__O(1)__。8.一個(gè)無(wú)向圖G包含n個(gè)頂點(diǎn)和m條邊，若G是連通的，則其最小生成樹包含__n-1__條邊。9.哈夫曼編碼是一種基于__貪心算法__構(gòu)造的最優(yōu)前綴編碼，其目標(biāo)是使平均碼長(zhǎng)最短。10.深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是圖兩種最基本的遍歷算法，其中BFS利用了__隊(duì)列__數(shù)據(jù)結(jié)構(gòu)，而DFS通常使用__棧__（或遞歸調(diào)用棧）來實(shí)現(xiàn)。二、判斷題（每題2分，共20分，請(qǐng)?jiān)诖痤}卡上填涂正確選項(xiàng)：√表示正確，×表示錯(cuò)誤）1.任何算法的時(shí)間復(fù)雜度都可以表示為O(n^k)的形式，其中k是某個(gè)正整數(shù)。（）2.如果一個(gè)算法在最壞情況下的時(shí)間復(fù)雜度是O(nlogn)，那么它的平均時(shí)間復(fù)雜度也一定是O(nlogn)。（）3.分治法算法通常需要比其他方法更多的內(nèi)存空間。（）4.貪心算法一定能找到問題的最優(yōu)解。（）5.動(dòng)態(tài)規(guī)劃算法可以解決所有優(yōu)化問題。（）6.在任何情況下，使用鏈表實(shí)現(xiàn)的算法一定比使用數(shù)組實(shí)現(xiàn)的算法運(yùn)行得更快。（）7.圖的拓?fù)渑判蚴菍?duì)有向無(wú)環(huán)圖（DAG）頂點(diǎn)的一種線性排序，使得對(duì)于每一條有向邊(u,v)，頂點(diǎn)u都在頂點(diǎn)v之前。（）8.Dijkstra算法可以用來求解有向帶權(quán)圖中從一個(gè)頂點(diǎn)到所有其他頂點(diǎn)的最短路徑。（）9.并查集是一種適用于處理不交集合合并及查詢問題的數(shù)據(jù)結(jié)構(gòu)。（）10.拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度不高于O(V+E)。（）三、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述歸并排序算法的基本思想及其主要步驟。2.解釋什么是算法的“最優(yōu)子結(jié)構(gòu)”性質(zhì)，并舉例說明。3.描述使用棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)深度優(yōu)先搜索（DFS）的基本過程。4.什么是圖的“連通分量”？如何判斷一個(gè)無(wú)向圖是否連通？四、算法設(shè)計(jì)題（每題10分，共20分）1.設(shè)計(jì)一個(gè)算法，輸入為一個(gè)正整數(shù)n，輸出為斐波那契數(shù)列的第n項(xiàng)的值。斐波那契數(shù)列定義如下：F(1)=1,F(2)=1,且對(duì)于n>=3,F(n)=F(n-1)+F(n-2)。請(qǐng)分別給出該算法的遞歸實(shí)現(xiàn)和動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)（要求考慮效率）的偽代碼或C/C++/Java核心代碼片段（無(wú)需完整程序框架，只需包含核心邏輯）。2.假設(shè)我們要在一個(gè)無(wú)序的整數(shù)數(shù)組arr中查找是否存在一個(gè)元素，使得該元素左右兩側(cè)的元素之和相等。例如，在數(shù)組[1,7,8,3,2,1,5]中，元素3滿足其左側(cè)元素之和(1+7+8=16)等于其右側(cè)元素之和(2+1+5=8)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法來查找這樣的元素，并給出算法的基本思想及偽代碼或C/C++/Java核心代碼片段。五、算法分析題（每題15分，共30分）1.給定以下遞歸函數(shù)的偽代碼：```FunctionrecursiveSum(n)ifn==0thenreturn0elsereturnn+recursiveSum(n-1)```寫出該函數(shù)的遞推關(guān)系式T(n)。假設(shè)使用主定理分析，判斷其時(shí)間復(fù)雜度是O(n)、O(nlogn)還是O(n^2)？請(qǐng)簡(jiǎn)述分析過程。2.分析以下C++代碼片段中`maxProduct`函數(shù)的執(zhí)行時(shí)間復(fù)雜度：```cppintmaxProduct(int[]nums){intmaxProduct=nums[0];for(inti=0;i<nums.length;++i){for(intj=i+1;j<nums.length;++j){if(nums[i]*nums[j]>maxProduct){maxProduct=nums[i]*nums[j];}}}returnmaxProduct;}```請(qǐng)?jiān)敿?xì)說明你的分析過程。試卷答案一、填空題1.常數(shù)項(xiàng)低階項(xiàng)2.分治法3.O(nlogn)O(n^2)4.貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)5.重疊子問題最優(yōu)子結(jié)構(gòu)6.O(n)7.鏈表數(shù)組8.n-19.貪心算法10.隊(duì)列棧二、判斷題1.×2.×3.√4.×5.×6.×7.√8.×9.√10.√三、簡(jiǎn)答題1.歸并排序的基本思想是將一個(gè)包含n個(gè)元素的待排序序列，遞歸地分成兩個(gè)長(zhǎng)度大致相等的子序列，分別對(duì)這兩個(gè)子序列進(jìn)行歸并排序，然后將排序好的兩個(gè)子序列合并成一個(gè)最終的有序序列。主要步驟包括：分解（遞歸地將序列一分為二，直到子序列長(zhǎng)度為1）、合并（將兩個(gè)已排序的子序列合并成一個(gè)有序序列）。2.算法的“最優(yōu)子結(jié)構(gòu)”性質(zhì)是指一個(gè)問題的最優(yōu)解包含了其子問題的最優(yōu)解。例如，在最優(yōu)路徑問題中，如果從頂點(diǎn)u到頂點(diǎn)v的最優(yōu)路徑經(jīng)過頂點(diǎn)w，那么從u到w的最優(yōu)路徑，以及從w到v的最優(yōu)路徑，也必須分別是u到w和w到v的最優(yōu)路徑。3.使用棧實(shí)現(xiàn)DFS的基本過程是：從初始頂點(diǎn)出發(fā)，將其標(biāo)記為已訪問并入棧。當(dāng)棧非空時(shí)，彈出一個(gè)頂點(diǎn)v，訪問v（如果尚未訪問）。然后，對(duì)于v的所有未訪問的鄰接頂點(diǎn)u，將其標(biāo)記為已訪問并入棧。重復(fù)此過程直到棧為空。4.圖的“連通分量”是指無(wú)向圖中的極大連通子圖。一個(gè)極大連通子圖是圖中的連通子圖，并且無(wú)法再向任意方向擴(kuò)展而保持連通。判斷一個(gè)無(wú)向圖是否連通，可以對(duì)其進(jìn)行BFS或DFS遍歷，如果所有頂點(diǎn)都被訪問過，則該圖是連通的；否則，圖是不連通的。四、算法設(shè)計(jì)題1.遞歸實(shí)現(xiàn)偽代碼/C++核心代碼片段：```cppintfib_recursive(intn){if(n<=0)return0;//或returnn;如果F(0)=0if(n==1||n==2)return1;returnfib_recursive(n-1)+fib_recursive(n-2);}```解析思路：直接根據(jù)斐波那契數(shù)列的定義進(jìn)行遞歸調(diào)用。但這種方法效率極低，時(shí)間復(fù)雜度為O(2^n)。動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)偽代碼/C++核心代碼片段：```cppintfib_dynamic(intn){if(n<=0)return0;if(n==1)return1;intdp[2]={0,1};//用兩個(gè)變量或數(shù)組空間優(yōu)化for(inti=2;i<=n;++i){inttemp=dp[0]+dp[1];dp[0]=dp[1];dp[1]=temp;}returndp[1];}//或使用數(shù)組/*intfib_dynamic(intn){if(n<=0)return0;if(n==1)return1;intdp[n+1];dp[0]=0;dp[1]=1;for(inti=2;i<=n;++i){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}*/```解析思路：遞歸版本存在大量重復(fù)計(jì)算（如fib(4)會(huì)計(jì)算fib(2)兩次）。動(dòng)態(tài)規(guī)劃通過記錄已計(jì)算結(jié)果避免重復(fù)計(jì)算。可以使用遞推公式`F(n)=F(n-1)+F(n-2)`從底向上計(jì)算。為節(jié)省空間，可以使用兩個(gè)變量交替存儲(chǔ)前兩個(gè)斐波那契數(shù)。2.算法思想：遍歷數(shù)組中所有可能的數(shù)對(duì)(i,j)，其中i<j，計(jì)算它們的乘積，并記錄遇到的最大乘積。偽代碼/C++核心代碼片段：```cppintfindMaxProduct(int[]nums){intmaxProd=nums[0]*nums[1];//初始化為前兩個(gè)數(shù)的乘積for(inti=0;i<nums.length;++i){for(intj=i+1;j<nums.length;++j){intprod=nums[i]*nums[j];if(prod>maxProd){maxProd=prod;}}}returnmaxProd;}```解析思路：要找到數(shù)組中和它相鄰元素乘積最大的那個(gè)元素，最直接的方法是計(jì)算數(shù)組中每對(duì)位置不同且i<j的元素nums[i]和nums[j]的乘積，然后從中找出最大的那個(gè)。這意味著需要比較所有可能的數(shù)對(duì)，因此算法的時(shí)間復(fù)雜度與數(shù)對(duì)的數(shù)量成正比。五、算法分析題1.遞推關(guān)系式：T(n)=T(n-1)+O(1)（當(dāng)n>0時(shí)），初始條件T(0)=O(1)。時(shí)間復(fù)雜度：O(n)。解析思路：分析遞歸函數(shù)`recursiveSum(n)`的時(shí)間復(fù)雜度。對(duì)于輸入規(guī)模為n的問題，函數(shù)執(zhí)行一次n的乘法操作，然后遞歸調(diào)用自身處理規(guī)模為n-1的問題。因此，時(shí)間復(fù)雜度T(n)滿足遞推關(guān)系T(n)=T(n-1)+O(1)。這是一個(gè)一階線性遞推關(guān)系，其解為T(n)=T(0)+O(1)*n=O(n)。使用主定理分析，該遞推關(guān)系屬于形式f(n)=a*f(n/b)+g(n)的范疇，其中a=1,b=1,g(n)=O(1)。因?yàn)閘og_b(a)=log_1(1)=0，且g(n)是常數(shù)階O(1)，滿足g(n)=Θ(n^θ)，其中θ=0。根據(jù)主定理第三種情況，時(shí)間復(fù)雜度為Θ(n^θ)=Θ(n^0)=O(1)。但這里的遞推關(guān)系更準(zhǔn)確地描述了每次遞歸只做常數(shù)時(shí)間工作的情況，最終解是O(n)。2.時(shí)間復(fù)雜度：O(n^2)。解析思路：分析`maxProduct`函數(shù)的執(zhí)行時(shí)間。函數(shù)中包含一個(gè)嵌套的for循環(huán)。外