2025年廈門(mén)信息學(xué)競(jìng)賽真題本文借鑒了近年相關(guān)經(jīng)典試題創(chuàng)作而成，力求幫助考生深入理解測(cè)試題型，掌握答題技巧，提升應(yīng)試能力。---一、選擇題（每題2分，共20分）1.下列關(guān)于算法復(fù)雜度的說(shuō)法，正確的是：A.算法的時(shí)間復(fù)雜度和空間復(fù)雜度總是成反比B.任何算法的時(shí)間復(fù)雜度都可以通過(guò)優(yōu)化降到O(1)C.算法的最優(yōu)解一定對(duì)應(yīng)最優(yōu)的時(shí)間復(fù)雜度D.空間復(fù)雜度為O(n)的算法，其時(shí)間復(fù)雜度一定大于O(1)2.下列數(shù)據(jù)結(jié)構(gòu)中，最適合用于實(shí)現(xiàn)快速查找的是：A.鏈表B.堆C.二叉搜索樹(shù)D.冒泡排序3.以下哪個(gè)是遞歸算法的典型特征？A.使用循環(huán)結(jié)構(gòu)B.需要大量?jī)?nèi)存空間C.可以解決所有問(wèn)題D.通過(guò)函數(shù)調(diào)用自身來(lái)解決問(wèn)題4.在數(shù)據(jù)庫(kù)中，以下哪個(gè)操作主要用于確保數(shù)據(jù)的一致性和完整性？A.查詢B.插入C.更新D.事務(wù)5.以下哪個(gè)是面向?qū)ο缶幊痰乃拇蠡咎匦灾?？A.復(fù)雜性B.封裝C.效率D.并發(fā)性6.以下哪個(gè)協(xié)議主要用于互聯(lián)網(wǎng)上的文件傳輸？A.FTPB.SMTPC.TCPD.HTTP7.在編程語(yǔ)言中，以下哪個(gè)關(guān)鍵字用于定義類？A.functionB.classC.defD.struct8.以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)是先進(jìn)先出（FIFO）的？A.棧B.隊(duì)列C.鏈表D.堆9.以下哪個(gè)是機(jī)器學(xué)習(xí)中的常見(jiàn)算法？A.遞歸下降解析B.決策樹(shù)C.邏輯回歸D.哈希表10.以下哪個(gè)是網(wǎng)絡(luò)安全中常用的加密算法？A.RSAB.MD5C.AESD.SHA-256---二、填空題（每空1分，共10分）1.在Python中，用于輸入數(shù)據(jù)的函數(shù)是_______。2.數(shù)據(jù)結(jié)構(gòu)中的“?！笔且环N_______的數(shù)據(jù)結(jié)構(gòu)。3.算法的“時(shí)間復(fù)雜度”通常用大O表示法來(lái)描述_______。4.數(shù)據(jù)庫(kù)的三范式包括第一范式（1NF）、第二范式（2NF）和_______。5.在面向?qū)ο缶幊讨?，將?shù)據(jù)封裝在類中，并通過(guò)_______來(lái)訪問(wèn)這些數(shù)據(jù)。6.網(wǎng)絡(luò)協(xié)議中的TCP協(xié)議是一種_______的傳輸協(xié)議。7.在編程中，用于定義函數(shù)的關(guān)鍵字是_______。8.數(shù)據(jù)結(jié)構(gòu)中的“隊(duì)列”是一種_______的數(shù)據(jù)結(jié)構(gòu)。9.機(jī)器學(xué)習(xí)中的“過(guò)擬合”是指模型對(duì)訓(xùn)練數(shù)據(jù)擬合得_______。10.網(wǎng)絡(luò)安全中，用于驗(yàn)證用戶身份的常見(jiàn)技術(shù)是_______。---三、簡(jiǎn)答題（每題5分，共20分）1.簡(jiǎn)述算法的時(shí)間復(fù)雜度和空間復(fù)雜度的含義及其重要性。2.解釋什么是遞歸算法，并舉例說(shuō)明其應(yīng)用場(chǎng)景。3.描述數(shù)據(jù)庫(kù)事務(wù)的基本特性及其在保證數(shù)據(jù)完整性中的作用。4.說(shuō)明面向?qū)ο缶幊讨械姆庋b、繼承、多態(tài)分別是什么，并舉例說(shuō)明。---四、編程題（每題15分，共30分）1.編寫(xiě)一個(gè)Python函數(shù)，實(shí)現(xiàn)快速排序算法。輸入一個(gè)整數(shù)列表，輸出排序后的列表。2.編寫(xiě)一個(gè)Python函數(shù)，實(shí)現(xiàn)二叉搜索樹(shù)的插入操作。輸入一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn)和一個(gè)要插入的值，輸出插入新節(jié)點(diǎn)后的二叉搜索樹(shù)。---五、綜合應(yīng)用題（20分）設(shè)計(jì)一個(gè)簡(jiǎn)單的圖書(shū)管理系統(tǒng)，要求實(shí)現(xiàn)以下功能：1.添加新書(shū)：輸入書(shū)名、作者、ISBN，將新書(shū)信息添加到系統(tǒng)中。2.查詢圖書(shū)：根據(jù)書(shū)名或作者查詢圖書(shū)信息。3.刪除圖書(shū)：根據(jù)ISBN刪除圖書(shū)信息。4.顯示所有圖書(shū)信息。請(qǐng)用Python實(shí)現(xiàn)該系統(tǒng)，并編寫(xiě)相應(yīng)的代碼。---答案和解析一、選擇題1.D-算法的時(shí)間復(fù)雜度和空間復(fù)雜度不一定成反比，A錯(cuò)誤；任何算法的時(shí)間復(fù)雜度不一定都能降到O(1)，B錯(cuò)誤；算法的最優(yōu)解不一定對(duì)應(yīng)最優(yōu)的時(shí)間復(fù)雜度，C錯(cuò)誤；空間復(fù)雜度為O(n)的算法，其時(shí)間復(fù)雜度不一定大于O(1)，D正確。2.C-鏈表查找效率低，堆適用于堆排序，二叉搜索樹(shù)適合快速查找，冒泡排序是排序算法，不是數(shù)據(jù)結(jié)構(gòu)，故選C。3.D-遞歸算法通過(guò)函數(shù)調(diào)用自身來(lái)解決問(wèn)題，A和B是循環(huán)和遞歸的區(qū)別，C錯(cuò)誤，D正確。4.D-事務(wù)操作用于確保數(shù)據(jù)的一致性和完整性，A、B、C是數(shù)據(jù)庫(kù)的基本操作，但D是正確答案。5.B-封裝是面向?qū)ο缶幊痰乃拇蠡咎匦灾唬珹、C、D不是面向?qū)ο蟮幕咎匦浴?.A-FTP用于文件傳輸，SMTP用于郵件傳輸，TCP是傳輸層協(xié)議，HTTP用于網(wǎng)頁(yè)傳輸，故選A。7.B-Python中用class定義類，function定義函數(shù)，def定義函數(shù)，struct在C中定義結(jié)構(gòu)體。8.B-棧是后進(jìn)先出（LIFO），隊(duì)列是先進(jìn)先出（FIFO），鏈表和堆不是特定順序的數(shù)據(jù)結(jié)構(gòu)。9.B-決策樹(shù)是機(jī)器學(xué)習(xí)中的常見(jiàn)算法，A是解析算法，C是統(tǒng)計(jì)學(xué)習(xí)方法，D是哈希表的應(yīng)用。10.C-AES是常用的對(duì)稱加密算法，RSA是公鑰加密算法，MD5和SHA-256是哈希算法。二、填空題1.input()2.后進(jìn)先出（LIFO）3.算法執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)的變化趨勢(shì)4.第三范式（3NF）5.訪問(wèn)器（getter和setter）6.面向連接的7.def8.先進(jìn)先出（FIFO）9.過(guò)于精確10.身份驗(yàn)證三、簡(jiǎn)答題1.算法的時(shí)間復(fù)雜度描述了算法執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)的變化趨勢(shì)，通常用大O表示法描述。空間復(fù)雜度描述了算法執(zhí)行過(guò)程中所需內(nèi)存空間隨輸入規(guī)模增長(zhǎng)的變化趨勢(shì)。它們的重要性在于幫助我們?cè)u(píng)估算法的效率，選擇合適的算法解決實(shí)際問(wèn)題。2.遞歸算法是通過(guò)函數(shù)調(diào)用自身來(lái)解決問(wèn)題的算法。遞歸算法通常用于解決具有遞歸結(jié)構(gòu)的問(wèn)題，如樹(shù)的遍歷、斐波那契數(shù)列的計(jì)算等。應(yīng)用場(chǎng)景包括：樹(shù)的遍歷、圖的搜索、分治算法等。3.數(shù)據(jù)庫(kù)事務(wù)的基本特性包括原子性、一致性、隔離性和持久性（ACID）。原子性指事務(wù)中的所有操作要么全部完成，要么全部不完成；一致性指事務(wù)執(zhí)行后數(shù)據(jù)庫(kù)狀態(tài)保持一致；隔離性指并發(fā)執(zhí)行的事務(wù)互不干擾；持久性指事務(wù)一旦提交，其結(jié)果就永久保存在數(shù)據(jù)庫(kù)中。事務(wù)在保證數(shù)據(jù)完整性中起著重要作用，確保數(shù)據(jù)庫(kù)在并發(fā)環(huán)境下的一致性和可靠性。4.封裝是指將數(shù)據(jù)和方法封裝在類中，并通過(guò)訪問(wèn)器（getter和setter）來(lái)訪問(wèn)這些數(shù)據(jù)，隱藏內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。繼承是指一個(gè)類可以繼承另一個(gè)類的屬性和方法，實(shí)現(xiàn)代碼復(fù)用。多態(tài)是指不同類的對(duì)象對(duì)同一消息做出不同響應(yīng)，提高代碼的靈活性和可擴(kuò)展性。例如，動(dòng)物類可以繼承生物類，貓和狗可以重寫(xiě)動(dòng)物的叫聲方法，實(shí)現(xiàn)多態(tài)。四、編程題1.快速排序算法```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)測(cè)試print(quick_sort([3,6,8,10,1,2,1]))```2.二叉搜索樹(shù)插入操作```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinsert_into_bst(root,val):ifrootisNone:returnTreeNode(val)ifval<root.val:root.left=insert_into_bst(root.left,val)else:root.right=insert_into_bst(root.right,val)returnroot測(cè)試root=Nonevalues=[5,3,8,1,4]forvalinvalues:root=insert_into_bst(root,val)```五、綜合應(yīng)用題```pythonclassBook:def__init__(self,title,author,isbn):self.title=titleself.author=authorself.isbn=isbnclassBookManager:def__init__(self):self.books=[]defadd_book(self,title,author,isbn):new_book=Book(title,author,isbn)self.books.append(new_book)print(f"Book'{title}'added.")defquery_books(self,query):results=[bookforbookinself.booksifquery.lower()inbook.title.lower()orquery.lower()inbook.author.lower()]ifresults:forbookinresults:print(f"Title:{book.title},Author:{book.author},ISBN:{book.isbn}")else:print("Nobooksfound.")defdelete_book(self,isbn):self.books=[bookforbookinself.booksifbook.isbn!=isbn]print(f"BookwithISBN{isbn}deleted.")defdisplay_books(self):ifself.books:forbookinself.books:print(f"Title:{book.title},Author:{book.author},ISBN:{book.isbn}")else:print("Nobooksinthesystem.")測(cè)試manager=BookManager()manager.add_book("TheGreatGatsby","F.ScottFitzgerald","1234