IGCSE計算機科學2024-2025年模擬試卷（數據結構與程序邏輯）——算法競賽實戰指南一、選擇題（每題2分，共20分）1.下列哪種排序算法的平均時間復雜度是O(nlogn)？A.冒泡排序B.選擇排序C.快速排序D.插入排序2.以下哪個數據結構支持高效的查找、插入和刪除操作？A.鏈表B.樹C.數組D.棧3.在二叉搜索樹中，以下哪個操作的時間復雜度是O(n)？A.查找B.插入C.刪除D.遍歷4.以下哪個算法是用來檢測鏈表中是否存在環的？A.快慢指針法B.鄰接表法C.深度優先搜索D.廣度優先搜索5.以下哪個數據結構可以用來存儲優先級隊列？A.隊列B.棧C.二叉樹D.堆6.以下哪個算法是貪心算法的一種？A.冒泡排序B.快速排序C.最小生成樹D.動態規劃7.以下哪個數據結構可以用來實現廣度優先搜索？A.鏈表B.棧C.隊列D.樹8.以下哪個算法是用于解決最短路徑問題的？A.冒泡排序B.快速排序C.Dijkstra算法D.動態規劃9.以下哪個數據結構可以用來實現深度優先搜索？A.鏈表B.棧C.隊列D.樹10.以下哪個算法是用來解決背包問題的？A.冒泡排序B.快速排序C.動態規劃D.Dijkstra算法二、簡答題（每題10分，共20分）1.簡述快速排序算法的基本思想。2.簡述二叉搜索樹的特點及其查找、插入和刪除操作的時間復雜度。三、編程題（共40分）1.編寫一個使用冒泡排序算法對整數數組進行排序的Python函數。2.編寫一個使用快速排序算法對整數數組進行排序的C++函數。四、編程題（每題20分，共40分）1.編寫一個Python函數，實現一個簡單的棧數據結構，包括入棧（push）、出棧（pop）、查看棧頂元素（peek）和判斷棧是否為空（is_empty）的方法。2.編寫一個C++函數，實現一個簡單的隊列數據結構，包括入隊（enqueue）、出隊（dequeue）、查看隊首元素（front）和判斷隊列是否為空（is_empty）的方法。五、應用題（每題20分，共40分）1.假設有一個整數數組，包含一些重復的元素。編寫一個函數，使用哈希表來找出數組中重復的元素，并返回一個包含所有重復元素的新數組。2.設計一個程序，模擬一個簡單的電話簿系統。使用鏈表來實現電話簿的數據結構，并實現以下功能：-添加一個新的聯系人（包括姓名和電話號碼）-刪除一個聯系人-查找聯系人的電話號碼-顯示所有聯系人的列表六、論述題（每題20分，共40分）1.論述遞歸算法的基本思想及其在解決復雜問題中的應用。2.討論分治算法的原理，并舉例說明如何將一個復雜問題分解為更小的子問題，以及如何合并子問題的解來得到原問題的解。本次試卷答案如下：一、選擇題答案及解析：1.C解析：快速排序的平均時間復雜度是O(nlogn)，因為它采用分治策略，將大問題分解為小問題，然后合并結果。2.B解析：樹結構如二叉搜索樹支持高效的查找、插入和刪除操作，因為它們通過比較鍵值來快速定位元素。3.A解析：在二叉搜索樹中，查找操作的時間復雜度是O(logn)，在最壞的情況下（完全不平衡的樹）是O(n)。4.A解析：快慢指針法可以檢測鏈表中是否存在環，通過一個指針以2倍速度移動，如果它們相遇，則存在環。5.D解析：堆是一種特殊的完全二叉樹，可以用數組來表示，它支持高效的優先級隊列操作。6.C解析：最小生成樹是一種貪心算法，通過選擇最小的邊來構建無環的樹，以連接所有頂點。7.C解析：隊列是一種先進先出（FIFO）的數據結構，適合實現廣度優先搜索，其中隊列用于存儲待訪問的節點。8.C解析：Dijkstra算法是一種圖搜索算法，用于找到從源點到所有其他點的最短路徑。9.B解析：棧是一種后進先出（LIFO）的數據結構，適合實現深度優先搜索，其中棧用于存儲待訪問的節點。10.C解析：動態規劃是一種解決問題的方法，通過將問題分解為重疊子問題來解決原問題，背包問題是動態規劃的典型應用。二、簡答題答案及解析：1.解析：快速排序的基本思想是選取一個基準元素，將數組分為兩部分，使得左側的所有元素都不大于基準，右側的所有元素都不小于基準，然后遞歸地對這兩部分進行快速排序。2.解析：二叉搜索樹的特點是每個節點的左子樹的值都小于該節點的值，右子樹的值都大于該節點的值。查找、插入和刪除操作的時間復雜度通常為O(logn)，但在最壞的情況下（完全不平衡的樹）可能達到O(n)。三、編程題答案及解析：1.Python函數實現冒泡排序：```pythondefbubble_sort(arr):n=len(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr```解析：該函數通過嵌套循環遍歷數組，比較相鄰元素，并在必要時交換它們的位置，以達到排序的目的。2.C++函數實現快速排序：```cppvoidquick_sort(intarr[],intlow,inthigh){if(low<high){intpivot=arr[high];inti=(low-1);for(intj=low;j<=high-1;j++){if(arr[j]<pivot){i++;std::swap(arr[i],arr[j]);}}std::swap(arr[i+1],arr[high]);intpi=i+1;quick_sort(arr,low,pi-1);quick_sort(arr,pi+1,high);}}```解析：該函數使用遞歸方法實現快速排序，選擇最后一個元素作為基準，將數組分為兩部分，然后對這兩部分遞歸排序。四、編程題答案及解析：1.Python函數實現棧：```pythonclassStack:def__init__(self):self.items=[]defpush(self,item):self.items.append(item)defpop(self):ifnotself.is_empty():returnself.items.pop()returnNonedefpeek(self):ifnotself.is_empty():returnself.items[-1]returnNonedefis_empty(self):returnlen(self.items)==0```解析：該類實現了棧的基本操作，包括入棧、出棧、查看棧頂元素和判斷棧是否為空。2.C++函數實現隊列：```cpp#include<iostream>#include<vector>usingnamespacestd;classQueue{private:vector<int>items;public:voidenqueue(intitem){items.push_back(item);}intdequeue(){if(!is_empty()){returnitems[0];}return-1;//表示隊列為空}intfront(){if(!is_empty()){returnitems[0];}return-1;//表示隊列為空}boolis_empty(){returnitems.empty();}};```解析：該類實現了隊列的基本操作，包括入隊、出隊、查看隊首元素和判斷隊列是否為空。五、應用題答案及解析：1.Python函數找出數組中重復的元素：```pythondeffind_duplicates(arr):duplicates=[]hash_set=set()fornuminarr:ifnuminhash_set:duplicates.append(num)else:hash_set.add(num)returnduplicates```解析：該函數使用一個集合來存儲已經出現過的元素，如果發現一個元素已經在集合中，則它是一個重復的元素。2.C++電話簿系統實現：```cpp#include<iostream>#include<vector>#include<map>usingnamespacestd;classPhoneBook{private:map<string,string>contacts;public:voidadd_contact(conststring&name,conststring&number){contacts[name]=number;}voidremove_contact(conststring&name){contacts.erase(name);}stringfind_number(conststring&name){if(contacts.find(name)!=contacts.end()){returncontacts[name];}return"Contactnotfound";}voiddisplay_contacts(){for(constauto&pair:contacts){cout<<pair.first<<":"<<pair.second<<endl;}}};``