2025年大學二年級計算機科學上學期算法試卷考試時間：______分鐘總分：______分姓名：______一、選擇題（每題2分，共20分。請將正確選項的字母填在題后的括號內(nèi)）1.下列關于算法復雜度的說法中，正確的是（）。a)算法的實際執(zhí)行時間取決于算法的輸入規(guī)模和實現(xiàn)語言b)復雜度僅描述算法執(zhí)行所需的時間c)O(f(n))表示算法的最快執(zhí)行時間d)對于同一個問題，只有一種算法復雜度最低2.若一個算法的時間復雜度為O(n^2)，則當輸入規(guī)模n增加一倍時，其執(zhí)行時間大約增加（）。a)1倍b)2倍c)3倍d)4倍3.在下列排序算法中，平均情況下和最壞情況下的時間復雜度都是O(n^2)的是（）。a)歸并排序b)快速排序c)插入排序d)堆排序4.下列數(shù)據(jù)結(jié)構(gòu)中，最適合用來實現(xiàn)棧的是（）。a)鏈表b)數(shù)組c)哈希表d)樹5.在一個長度為n的有序數(shù)組中查找一個不存在的元素，采用二分查找方法，其比較次數(shù)的最壞情況是（）。a)O(1)b)O(logn)c)O(n)d)O(nlogn)6.下列關于遞歸的說法中，錯誤的是（）。a)遞歸函數(shù)必須包含遞歸調(diào)用語句b)遞歸函數(shù)必須有一個明確的終止條件c)遞歸思考將問題分解為規(guī)模更小的相同問題d)遞歸通常比循環(huán)更高效7.在具有n個節(jié)點的單鏈表中，刪除一個已知值的節(jié)點，其最壞情況下的時間復雜度是（）。a)O(1)b)O(logn)c)O(n)d)O(n^2)8.對于二叉搜索樹，下列性質(zhì)中錯誤的是（）。a)左子樹上所有節(jié)點的值均小于根節(jié)點的值b)右子樹上所有節(jié)點的值均大于根節(jié)點的值c)左右子樹也都是二叉搜索樹d)樹中一定存在一個節(jié)點，其左子樹和右子樹的高度差大于19.廣度優(yōu)先搜索（BFS）算法通常使用（）來實現(xiàn)。a)棧b)隊列c)堆d)哈希表10.已知數(shù)組A={5,1,8,3,2}，對其執(zhí)行一次冒泡排序（從小到大），排序后的第一個元素是（）。a)1b)2c)3d)5二、判斷題（每題1分，共10分。請在題后的括號內(nèi)填“√”表示正確，“×”表示錯誤）1.算法的空間復雜度僅與算法執(zhí)行過程中臨時占用的存儲空間有關。（）2.快速排序在最壞情況下的時間復雜度是O(n^2)，但平均情況下的時間復雜度是O(nlogn)。（）3.隊列是一種先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。（）4.插入排序是一種穩(wěn)定的排序算法。（）5.在任何情況下，二分查找都比順序查找更高效。（）6.遞歸算法通常需要比非遞歸算法更多的棧空間。（）7.哈希表的平均查找時間復雜度可以達到O(1)。（）8.樹的節(jié)點可以有多個父節(jié)點。（）9.深度優(yōu)先搜索（DFS）算法可以使用?；蜿犃衼韺崿F(xiàn)。（）10.冒泡排序是一種分治策略的排序算法。（）三、簡答題（每題5分，共15分）1.簡述大O表示法的基本思想及其主要用途。2.請分別說明棧和隊列的基本操作（至少三種）及其邏輯含義。3.比較歸并排序和快速排序的特點（至少兩點），并說明它們各自適用于什么情況。四、算法設計題（每題10分，共20分）1.設計一個算法，計算一個非負整數(shù)n的所有因子（包括1和n本身）之和。請用偽代碼或C/C++/Java等你熟悉的語言描述該算法的主要步驟。2.假設你有一個只包含正整數(shù)的數(shù)組A，請你設計一個算法，找出數(shù)組中第二大的元素。如果數(shù)組中所有元素都相同，則不存在第二大的元素，算法應返回一個特殊標記（如-1）。請用偽代碼或C/C++/Java等你熟悉的語言描述該算法的主要步驟。五、編程題（每題15分，共30分）1.請編寫一個函數(shù)，實現(xiàn)快速排序算法。該函數(shù)應接受一個整數(shù)數(shù)組作為輸入，并原地（in-place）對該數(shù)組進行排序。要求在函數(shù)內(nèi)部實現(xiàn)快速排序的邏輯。2.請編寫一個函數(shù)，實現(xiàn)二分查找算法。該函數(shù)應接受一個按升序排列的整數(shù)數(shù)組和一個目標值作為輸入，如果數(shù)組中存在目標值，則返回其索引；如果不存在，則返回-1。要求在函數(shù)內(nèi)部實現(xiàn)二分查找的邏輯。試卷答案一、選擇題1.a解析：算法復雜度描述的是算法效率隨輸入規(guī)模增長的趨勢，實際執(zhí)行時間受硬件、實現(xiàn)語言等多種因素影響。復雜度分析關注的是增長速度，而非絕對時間。O(f(n))描述的是增長上界，并非最快時間。算法可能有多種復雜度，取決于不同情況下的表現(xiàn)。2.d解析：O(n^2)表示執(zhí)行時間與n的平方成正比。當n翻倍時，新的輸入規(guī)模為2n，執(zhí)行時間約為(2n)^2/n^2=4倍。3.c解析：插入排序和選擇排序在最好（已排序）情況下均為O(n)，在最壞（逆序）和平均情況下均為O(n^2)。歸并排序和堆排序在最好、最壞、平均情況下均為O(nlogn)。4.b解析：數(shù)組支持隨機訪問，實現(xiàn)棧的push和pop操作（通常在末尾）非常高效。鏈表雖然也能實現(xiàn)棧，但push/pop涉及指針操作，可能比數(shù)組略慢或需要更多空間。5.c解析：二分查找每次將搜索區(qū)間減半。最壞情況（查找失敗且元素最接近）需要經(jīng)過log2(n)次比較，當n次比較后區(qū)間大小變?yōu)?時，即為log2(n)+1次。由于通常計數(shù)從1開始，最壞情況比較次數(shù)為O(logn)。順序查找最壞情況比較n次。6.d解析：遞歸不一定比循環(huán)更高效。遞歸可能帶來額外的函數(shù)調(diào)用開銷和?？臻g消耗，對于某些問題，循環(huán)可能是更優(yōu)或更節(jié)省資源的選擇。7.c解析：在單鏈表中查找要刪除的節(jié)點需要遍歷鏈表，最壞情況是待刪除節(jié)點是最后一個節(jié)點，需要遍歷n個節(jié)點。找到節(jié)點后，刪除操作本身是O(1)。8.d解析：二叉搜索樹的性質(zhì)包括：左子樹所有節(jié)點值<根節(jié)點值<右子樹所有節(jié)點值；左右子樹也都是二叉搜索樹。樹的平衡性（高度差不超過1）是平衡二叉搜索樹（如AVL樹、紅黑樹）的特性，而非普通二叉搜索樹的性質(zhì)。9.b解析：BFS的核心思想是逐層遍歷，符合隊列先進先出的特性。使用?？梢詫崿F(xiàn)DFS。10.b解析：冒泡排序從前往后比較相鄰元素，將較大的元素向后移動。初始數(shù)組為{5,1,8,3,2}，第一次比較5和1，交換得到{1,5,8,3,2}，第一個元素變?yōu)?。二、判斷題1.√解析：算法的空間復雜度是指算法運行時所需存儲空間的大小，包括輸入數(shù)據(jù)所占空間、輔助變量所占空間以及遞歸調(diào)用?？臻g等。臨時占用空間是空間復雜度的一部分。2.√解析：快速排序的時間復雜度與其分治過程的結(jié)果有關。平均情況下，每次劃分能將問題規(guī)模大致減半，符合遞歸樹模型的高度logn，每層處理n個節(jié)點，故為O(nlogn)。最壞情況發(fā)生在每次劃分只能減少一個元素（如已排序數(shù)組且選擇固定基準），遞歸深度為n，每層仍處理n個節(jié)點，復雜度為O(n^2)。3.√解析：隊列遵循先進先出（First-In,First-Out,FIFO）原則，最早進入的元素最先被移除。4.√解析：插入排序在插入元素時，會將其與前面的已排序元素比較，如果待插入元素與前面某個元素相等，則保持它們原有的相對順序不變，因此是穩(wěn)定的。5.×解析：二分查找要求待查找的序列必須是有序的。對于無序序列，二分查找不適用，順序查找可能是更合適的選擇（盡管效率較低）。在序列無序時，順序查找的時間復雜度為O(n)，可能比二分查找（O(logn)）更高效。6.√解析：遞歸函數(shù)的每一次調(diào)用都需要在調(diào)用棧上保存其局部變量和返回地址。遞歸調(diào)用的次數(shù)越多，棧的深度就越深，占用的?？臻g就越大。7.√解析：理想情況下，哈希表通過計算鍵的哈希值直接定位到存儲位置，實現(xiàn)常數(shù)時間O(1)的平均查找。即使考慮沖突解決（如鏈地址法、開放地址法），通過合適的哈希函數(shù)和沖突處理，平均查找時間仍可保持O(1)或接近O(1)。8.×解析：根據(jù)樹的定義，樹是一種非線性結(jié)構(gòu)，其中每個節(jié)點（除根節(jié)點外）有且僅有一個父節(jié)點。如果節(jié)點有多個父節(jié)點，則該結(jié)構(gòu)不再是樹，而是有向圖或更一般的數(shù)據(jù)結(jié)構(gòu)。9.√解析：DFS的核心是探索一條路徑直到無法繼續(xù)，然后再回溯。這與棧的后進先出（LIFO）特性非常契合，可以用棧模擬DFS過程。雖然也可以用隊列模擬（得到BFS），但用棧模擬DFS更直觀。10.×解析：冒泡排序的基本思想是通過重復遍歷待排序序列，比較相鄰元素并交換位置，將較大的元素逐漸“冒泡”到序列的末尾。它是一種交換排序，不是分治排序。分治策略將問題分解為子問題，分別解決，再合并結(jié)果（如歸并排序）。三、簡答題1.大O表示法的基本思想是用一個函數(shù)的增長趨勢來描述算法運行時間或所需空間隨輸入規(guī)模增長的變化規(guī)律，忽略常數(shù)因子和低階項。其主要用途是方便地比較不同算法在輸入規(guī)模很大時的效率差異，關注算法的“漸近”性能，從而選擇適合特定問題的算法。2.棧的基本操作包括：*push(x)：將元素x壓入棧頂。邏輯含義是使x成為新的棧頂元素。*pop()：移除棧頂元素并返回它。邏輯含義是訪問并移除當前棧頂?shù)脑亍?top()或peek()：返回棧頂元素的值，但不移除它。邏輯含義是查看當前棧頂元素。隊列的基本操作包括：*enqueue(x)：將元素x加入隊尾。邏輯含義是使x成為新的隊尾元素。*dequeue()：移除隊首元素并返回它。邏輯含義是訪問并移除當前隊首的元素。*front()或peek()：返回隊首元素的值，但不移除它。邏輯含義是查看當前隊首元素。棧是LIFO（后進先出）結(jié)構(gòu)，適用于需要“后處理”的場景。隊列是FIFO（先進先出）結(jié)構(gòu)，適用于需要“先處理”的場景。3.歸并排序和快速排序的比較：*穩(wěn)定性：歸并排序是穩(wěn)定的排序算法，相等元素的相對順序不變?？焖倥判蛲ǔＪ遣环€(wěn)定的排序算法，相等元素的相對順序可能改變。*時間復雜度：快速排序的平均和最好情況時間復雜度為O(nlogn)，但最壞情況為O(n^2)（如已排序數(shù)組且選擇固定基準）。歸并排序的最好、平均、最壞情況時間復雜度均為O(nlogn)。*空間復雜度：歸并排序需要額外的存儲空間來合并子數(shù)組，空間復雜度為O(n)?？焖倥判蚴窃嘏判颍臻g復雜度為O(logn)用于遞歸棧），不需要額外存儲空間。歸并排序適用于需要穩(wěn)定排序且空間允許的情況?？焖倥判蜻m用于對空間要求嚴格且平均性能要求高的情況，可以通過選擇好的基準來避免最壞情況。四、算法設計題1.偽代碼：FunctionSumOfFactors(n)Ifn<=0ThenReturn0//處理非正整數(shù)情況EndIfsum=0Fori=1TonStep1IfnModi==0Thensum=sum+iEndIfNextiReturnsumEndFunction//主要步驟：初始化和為0；遍歷從1到n的所有整數(shù)i；檢查i是否為n的因子（n能被i整除）；如果是，則累加到和中；返回最終的和。2.偽代碼：FunctionFindSecondLargest(A)IfLength(A)<2ThenReturn-1//元素不足兩個，不存在第二大的EndIffirstMax=A[0]secondMax=-1Fori=1ToLength(A)-1IfA[i]>firstMaxThensecondMax=firstMaxfirstMax=A[i]ElseIfA[i]>secondMaxAndA[i]!=firstMaxThensecondMax=A[i]EndIfNextiReturnsecondMaxEndFunction//主要步驟：初始化firstMax為第一個元素，secondMax為-1；遍歷數(shù)組A的其余元素；對于當前元素A[i]：如果A[i]大于firstMax，則更新secondMax為舊的firstMax，然后更新firstMax為A[i]；如果A[i]小于firstMax且大于secondMax（且不等于firstMax），則更新secondMax為A[i]；返回secondMax。如果所有元素都相等，secondMax保持為-1。五、編程題1.C++示例：#include<vector>voidquickSort(std::vector<int>&A,intlow,inthigh){if(low<high){//Partitionthearrayaroundthepivotintpivot=A[high];inti=low-1;for(intj=low;j<high;j++){if(A[j]<=pivot){i++;std::swap(A[i],A[j]);}}std::swap(A[i+1],A[high]);intpartitionIndex=i+1;//RecursivelysortelementsbeforeandafterpartitionquickSort(A,low,partitionIndex-1);quickSort(A,partitionInde