2025年計(jì)算機(jī)四級編程考題試題及答案一、選擇題1.下列關(guān)于算法復(fù)雜度的描述，正確的是（）A.算法的時(shí)間復(fù)雜度與問題的規(guī)模無關(guān)B.算法的空間復(fù)雜度是指算法執(zhí)行過程中所需要的額外存儲空間C.算法的時(shí)間復(fù)雜度和空間復(fù)雜度一定是相互矛盾的D.一個(gè)算法的時(shí)間復(fù)雜度是指算法執(zhí)行的具體時(shí)間答案：B解析：-選項(xiàng)A：算法的時(shí)間復(fù)雜度是問題規(guī)模的函數(shù)，與問題規(guī)模密切相關(guān)，所以A錯(cuò)誤。-選項(xiàng)B：算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的額外存儲空間，這是空間復(fù)雜度的定義，B正確。-選項(xiàng)C：算法的時(shí)間復(fù)雜度和空間復(fù)雜度并不一定相互矛盾，有些情況下可以通過一定的優(yōu)化同時(shí)降低時(shí)間和空間復(fù)雜度，C錯(cuò)誤。-選項(xiàng)D：算法的時(shí)間復(fù)雜度是指算法執(zhí)行的基本操作次數(shù)，而不是具體時(shí)間，因?yàn)榫唧w時(shí)間受硬件等多種因素影響，D錯(cuò)誤。2.有一個(gè)棧，初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5依次入棧，然后再依次出棧，則出棧順序是（）A.5、4、3、2、1B.1、2、3、4、5C.4、5、3、2、1D.1、3、2、4、5答案：A解析：棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)。元素1、2、3、4、5依次入棧后，棧內(nèi)元素從棧底到棧頂依次為1、2、3、4、5。出棧時(shí)，最后入棧的元素先出棧，所以出棧順序?yàn)?、4、3、2、1。3.以下關(guān)于二叉樹的說法，錯(cuò)誤的是（）A.滿二叉樹一定是完全二叉樹B.完全二叉樹一定是滿二叉樹C.二叉樹的第i層最多有$2^{i-1}$個(gè)節(jié)點(diǎn)（i≥1）D.深度為k的二叉樹最多有$2^{k}-1$個(gè)節(jié)點(diǎn)（k≥1）答案：B解析：-選項(xiàng)A：滿二叉樹是指除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹，完全二叉樹是指除了最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干節(jié)點(diǎn)，所以滿二叉樹一定是完全二叉樹，A正確。-選項(xiàng)B：完全二叉樹不一定是滿二叉樹，例如最后一層節(jié)點(diǎn)沒有填滿的情況，B錯(cuò)誤。-選項(xiàng)C：根據(jù)二叉樹的性質(zhì)，二叉樹的第i層最多有$2^{i-1}$個(gè)節(jié)點(diǎn)（i≥1），C正確。-選項(xiàng)D：深度為k的二叉樹最多有$2^{k}-1$個(gè)節(jié)點(diǎn)（k≥1），這是二叉樹節(jié)點(diǎn)總數(shù)的最大值公式，D正確。4.對長度為n的線性表進(jìn)行冒泡排序，最壞情況下的時(shí)間復(fù)雜度是（）A.O(1)B.O(n)C.O(n^2)D.O(log?n)答案：C解析：冒泡排序在最壞情況下，即初始序列為逆序時(shí)，需要比較和交換的次數(shù)最多。對于長度為n的線性表，需要進(jìn)行n-1趟排序，第i趟排序需要比較n-i次，總的比較次數(shù)為$\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$，時(shí)間復(fù)雜度為O(n^2)。5.以下關(guān)于圖的說法，正確的是（）A.有向圖的鄰接矩陣一定是對稱矩陣B.無向圖的鄰接矩陣一定是對稱矩陣C.圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的時(shí)間復(fù)雜度一定不同D.圖的拓?fù)渑判蛑荒苡糜谟邢驘o環(huán)圖答案：BD解析：-選項(xiàng)A：有向圖的鄰接矩陣不一定是對稱矩陣，因?yàn)橛邢驁D的邊是有方向的，只有當(dāng)有向圖是對稱有向圖時(shí)，鄰接矩陣才是對稱矩陣，A錯(cuò)誤。-選項(xiàng)B：無向圖的邊沒有方向，對于任意兩個(gè)頂點(diǎn)i和j，如果存在邊(i,j)，則一定存在邊(j,i)，所以無向圖的鄰接矩陣一定是對稱矩陣，B正確。-選項(xiàng)C：圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷在使用鄰接矩陣存儲圖時(shí)，時(shí)間復(fù)雜度都是O(V^2)，使用鄰接表存儲圖時(shí)，時(shí)間復(fù)雜度都是O(V+E)，其中V是頂點(diǎn)數(shù)，E是邊數(shù)，C錯(cuò)誤。-選項(xiàng)D：拓?fù)渑判蚴菍τ邢驘o環(huán)圖的頂點(diǎn)進(jìn)行排序，使得對于圖中的任意一條有向邊(u,v)，頂點(diǎn)u在排序中都出現(xiàn)在頂點(diǎn)v之前，所以拓?fù)渑判蛑荒苡糜谟邢驘o環(huán)圖，D正確。二、填空題1.設(shè)循環(huán)隊(duì)列的容量為50（序號從0到49），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)操作后，有front=16，rear=5，則該循環(huán)隊(duì)列中元素的個(gè)數(shù)為______。答案：39解析：循環(huán)隊(duì)列中元素個(gè)數(shù)的計(jì)算公式為：(rear-front+容量)%容量。將front=16，rear=5，容量=50代入公式，得到(5-16+50)%50=39。2.若一棵二叉樹的前序遍歷序列為ABCDE，中序遍歷序列為CBADE，則該二叉樹的后序遍歷序列為______。答案：CBEDA解析：-前序遍歷的順序是根節(jié)點(diǎn)->左子樹->右子樹，中序遍歷的順序是左子樹->根節(jié)點(diǎn)->右子樹。-由前序遍歷序列ABCDE可知，A是根節(jié)點(diǎn)。在中序遍歷序列CBADE中，A左邊的C、B是左子樹的節(jié)點(diǎn)，右邊的D、E是右子樹的節(jié)點(diǎn)。-對于左子樹，前序遍歷是BC，中序遍歷是CB，所以B是左子樹的根節(jié)點(diǎn)，C是B的左子節(jié)點(diǎn)。-對于右子樹，前序遍歷是DE，中序遍歷是DE，所以D是右子樹的根節(jié)點(diǎn)，E是D的右子節(jié)點(diǎn)。-后序遍歷的順序是左子樹->右子樹->根節(jié)點(diǎn)，所以后序遍歷序列為CBEDA。3.已知一個(gè)有序表為(12,18,24,35,47,50,62,83,90,115,134)，當(dāng)用二分查找法查找值為90的元素時(shí)，需要比較______次才能查找成功。答案：2解析：-二分查找的基本思想是將有序表中間位置的元素與查找元素進(jìn)行比較，如果相等則查找成功；如果中間元素大于查找元素，則在左半部分繼續(xù)查找；如果中間元素小于查找元素，則在右半部分繼續(xù)查找。-第一次比較：有序表有11個(gè)元素，中間位置為(0+10)/2=5，對應(yīng)元素是50，50<90，所以在右半部分(62,83,90,115,134)繼續(xù)查找。-第二次比較：右半部分有5個(gè)元素，中間位置為(6+10)/2=8，對應(yīng)元素是90，查找成功。4.設(shè)哈希表的地址范圍是[0,9]，哈希函數(shù)為H(key)=key%10，采用線性探測法解決沖突。將關(guān)鍵字序列(26,25,72,38,8,18,59)依次存儲到哈希表中，則關(guān)鍵字59存儲的地址是______。答案：9解析：-計(jì)算各關(guān)鍵字的哈希地址：-H(26)=26%10=6-H(25)=25%10=5-H(72)=72%10=2-H(38)=38%10=8-H(8)=8%10=8，發(fā)生沖突，采用線性探測法，下一個(gè)地址為(8+1)%10=9-H(18)=18%10=8，發(fā)生沖突，依次探測(8+1)%10=9，(9+1)%10=0-H(59)=59%10=9，發(fā)生沖突，依次探測(9+1)%10=0，(0+1)%10=1，(1+1)%10=2，(2+1)%10=3，(3+1)%10=4，(4+1)%10=5，(5+1)%10=6，(6+1)%10=7，(7+1)%10=8，(8+1)%10=9，找到空閑位置。5.已知一個(gè)有向圖的鄰接矩陣為：\[\begin{bmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\end{bmatrix}\]則該有向圖的拓?fù)渑判蛐蛄袨開_____。答案：1->2->3->4解析：-拓?fù)渑判虻牟襟E是：-選擇一個(gè)入度為0的頂點(diǎn)并輸出。-從圖中刪除該頂點(diǎn)和所有以它為起點(diǎn)的有向邊。-重復(fù)上述步驟，直到圖中沒有入度為0的頂點(diǎn)。-由鄰接矩陣可知，頂點(diǎn)1的入度為0，輸出頂點(diǎn)1。刪除頂點(diǎn)1和以它為起點(diǎn)的邊后，頂點(diǎn)2的入度為0，輸出頂點(diǎn)2。刪除頂點(diǎn)2和以它為起點(diǎn)的邊后，頂點(diǎn)3的入度為0，輸出頂點(diǎn)3。刪除頂點(diǎn)3和以它為起點(diǎn)的邊后，頂點(diǎn)4的入度為0，輸出頂點(diǎn)4。所以拓?fù)渑判蛐蛄袨?->2->3->4。三、算法設(shè)計(jì)題1.編寫一個(gè)函數(shù)，實(shí)現(xiàn)將一個(gè)單鏈表反轉(zhuǎn)的功能。單鏈表的節(jié)點(diǎn)結(jié)構(gòu)如下：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next```答案：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):prev=Nonecurr=headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev```解析：-該函數(shù)使用迭代的方法反轉(zhuǎn)單鏈表。-初始化prev為None，curr為頭節(jié)點(diǎn)。-在循環(huán)中，首先保存curr的下一個(gè)節(jié)點(diǎn)next_node，然后將curr的next指針指向prev，接著更新prev為curr，curr為next_node。-最后返回prev，即反轉(zhuǎn)后的鏈表的頭節(jié)點(diǎn)。2.編寫一個(gè)函數(shù)，判斷一個(gè)字符串是否是回文串?；匚拇侵刚x和反讀都相同的字符串。```pythondefisPalindrome(s):pass```答案：```pythondefisPalindrome(s):s=''.join(filter(str.isalnum,s)).lower()returns==s[::-1]```解析：-首先使用`filter(str.isalnum,s)`過濾掉字符串s中的非字母和數(shù)字字符，然后使用`join`方法將過濾后的字符連接成一個(gè)新的字符串。-接著使用`lower`方法將字符串轉(zhuǎn)換為小寫。-最后比較原字符串和反轉(zhuǎn)后的字符串是否相等，如果相等則是回文串，返回True，否則返回False。3.編寫一個(gè)函數(shù)，實(shí)現(xiàn)兩個(gè)有序數(shù)組的合并。```pythondefmergeSortedArrays(nums1,m,nums2,n):pass```其中，nums1的長度為m+n，前m個(gè)元素是有序的，后n個(gè)元素為0；nums2的長度為n，元素是有序的。要求將nums2合并到nums1中，使nums1成為一個(gè)有序數(shù)組。答案：```pythondefmergeSortedArrays(nums1,m,nums2,n):p1=m-1p2=n-1p=m+n-1whilep1>=0andp2>=0:ifnums1[p1]>nums2[p2]:nums1[p]=nums1[p1]p1-=1else:nums1[p]=nums2[p2]p2-=1p-=1whilep2>=0:nums1[p]=nums2[p2]p2-=1p-=1returnnums1```解析：-從后往前比較nums1和nums2的元素，將較大的元素放到nums1的末尾。-使用三個(gè)指針p1、p2和p，p1指向nums1的最后一個(gè)有效元素，p2指向nums2的最后一個(gè)元素，p指向nums1的最后一個(gè)位置。-當(dāng)p1和p2都大于等于0時(shí)，比較nums1[p1]和nums2[p2]，將較大的元素放到nums1[p]的位置，并更新相應(yīng)的指針。-如果p2還有剩余元素，將其依次放到nums1的前面。四、綜合應(yīng)用題1.假設(shè)有一個(gè)電商系統(tǒng)，需要設(shè)計(jì)一個(gè)商品庫存管理模塊。該模塊需要實(shí)現(xiàn)以下功能：-商品的添加：將新商品信息（包括商品ID、名稱、庫存數(shù)量等）添加到系統(tǒng)中。-商品的查詢：根據(jù)商品ID查詢商品的信息。-商品的庫存更新：根據(jù)商品ID更新商品的庫存數(shù)量。-商品的刪除：根據(jù)商品ID刪除商品的信息。請使用Python實(shí)現(xiàn)該商品庫存管理模塊。答案：```pythonclassInventoryManagement:def__init__(self):self.inventory={}defadd_product(self,product_id,name,quantity):ifproduct_idinself.inventory:print(f"商品ID{product_id}已存在，無法重復(fù)添加。")else:self.inventory[product_id]={"name":name,"quantity":quantity}print(f"商品ID{product_id}已成功添加。")defquery_product(self,product_id):ifproduct_idinself.inventory:product=self.inventory[product_id]print(f"商品ID:{product_id},名稱:{product['name']},庫存數(shù)量:{product['quantity']}")else:print(f"商品ID{product_id}不存在。")defupdate_quantity(self,product_id,new_quantity):ifproduct_idinself.inventory:self.inventory[product_id]["quantity"]=new_quantityprint(f"商品ID{product_id}的庫存數(shù)量已更新為{new_quantity}。")else:print(f"商品ID{product_id}不存在，無法更新庫存。")defdelete_product(self,product_id):ifproduct_idinself.inventory:delself.inventory[product_id]print(f"商品ID{product_id}已成功刪除。")else:print(f"商品ID{product_id}不存在，無法刪除。")測試代碼inventory_manager=InventoryManagement()inventory_manager.add_product(1,"手機(jī)",100)inventory_manager.query_product(1)inventory_manager.update_quantity(1,200)inventory_manager.query_product(1)inventory_manager.delete_product(1)inventory_manager.query_product(1)```解析：-定義一個(gè)`InventoryManagement`類，使用一個(gè)字典`inventory`來存儲商品信息，鍵是商品ID，值是一個(gè)包含商品名稱和庫存數(shù)量的字典。-`add_product`方法用于添加新商品，如果商品ID已存在則提示無法重復(fù)添加，否則添加商品信息并提示添加成功。-`query_product`方法用于查詢商品信息，如果商品ID存在則輸出商品信息，否則提示商品不存在。-`update_quantity`方法用于更新商品的庫存數(shù)量，如果商品ID存在則更新庫存數(shù)量并提示更新成功，否則提示商品不存在無法更新。-`delete_product`方法用于刪除商品信息，如果商品ID存在則刪除商品信息并提示刪除成功，否則提示商品不存在無法刪除。2.現(xiàn)有一個(gè)文件系統(tǒng)，文件和文件夾以樹形結(jié)構(gòu)組織。每個(gè)文件夾可以包含文件和子文件夾，每個(gè)文件有一個(gè)唯一的名稱和大小。請?jiān)O(shè)計(jì)一個(gè)Python類來表示這個(gè)文件系統(tǒng)，并實(shí)現(xiàn)以下功能：-計(jì)算指定文件夾下所有文件的總大小。-查找指定名稱的文件，并返回其所在的文件夾路徑。```pythonclassFileSystemNode:def__init__(self,name,is_file,size=0):=nameself.is_file=is_fileself.size=sizeself.children=[]classFileSystem:def__init__(self,root):self.root=rootdefcalculate_total_size(self,folder):passdeffind_file_path(self,file_name):pass```答案：```pythonclassFileSystemNode:def__init__(self,name,is_file,size=0):=nameself.is_file=is_fileself.size=sizeself.children=[]classFileSystem:def__init__(self,root):self.root=rootdefcalculate_total_size(self,folder):total_size=0forchildinfolder.children:ifchild.is_file:total_size+=child.sizeelse:total_size+=self.calculate_total_size(child)returntotal_sizedeffind_file_path(self,file_name):defdfs(node,path):ifnode.is_file:if==file_name:returnpath+"/"+else:forchildinnode.children:result=dfs(child,path+"/"+)ifresult:returnresultreturnNonereturndfs(self.root,"")測試代碼創(chuàng)建文件系統(tǒng)root=FileSystemNode("root",False)folder1=FileSystemNode("folder1",