計(jì)算機(jī)程序員三級(jí)實(shí)操試題（附答案）一、字符串處理與回文子串統(tǒng)計(jì)問(wèn)題描述：給定一個(gè)由小寫字母組成的字符串s（長(zhǎng)度3≤s.length≤1000），要求完成以下任務(wù)：1.找出s中所有長(zhǎng)度≥3的回文子串；2.去重后按字典序排序；3.輸出排序后的子串列表。輸入示例：輸入："ababa"輸出示例：輸出：["aba","ababa","bab"]編程要求：-用Python編寫函數(shù)，函數(shù)簽名為`deffind_palindromes(s:str)->list`；-時(shí)間復(fù)雜度不超過(guò)O(n2)，n為字符串長(zhǎng)度；-需處理重復(fù)子串（如"ababa"中"aba"出現(xiàn)兩次，但結(jié)果僅保留一個(gè)）。二、二叉樹(shù)的路徑和驗(yàn)證問(wèn)題描述：給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn)root和一個(gè)整數(shù)target，判斷是否存在從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑，使得路徑上所有節(jié)點(diǎn)值的和等于target。葉子節(jié)點(diǎn)指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。輸入示例：二叉樹(shù)結(jié)構(gòu)（用層序遍歷表示）：[5,4,8,11,null,13,4,7,2,null,null,null,1]，target=22。對(duì)應(yīng)的樹(shù)結(jié)構(gòu)如下：```5/\48//\11134/\/721```輸出示例：輸出：True（路徑5→4→11→2的和為5+4+11+2=22）。編程要求：-用Python實(shí)現(xiàn)二叉樹(shù)節(jié)點(diǎn)類（classTreeNode），包含val、left、right屬性；-實(shí)現(xiàn)函數(shù)`defhas_path_sum(root:TreeNode,target:int)->bool`；-需處理空樹(shù)情況（若root為None且target為0，返回False）。三、圖的最短路徑計(jì)算問(wèn)題描述：給定一個(gè)無(wú)向無(wú)權(quán)圖的鄰接表（節(jié)點(diǎn)編號(hào)為0到n-1），以及起點(diǎn)start和終點(diǎn)end，計(jì)算從start到end的最短路徑長(zhǎng)度（邊數(shù)最少）。若無(wú)法到達(dá)，返回-1。輸入示例：鄰接表：[[1,2],[0,3],[0,4],[1,4],[2,3]]，start=0，end=4。對(duì)應(yīng)的圖結(jié)構(gòu)如下：0連接1、2；1連接0、3；2連接0、4；3連接1、4；4連接2、3。輸出示例：輸出：2（路徑0→2→4，共2條邊）。編程要求：-用Python編寫函數(shù)`defshortest_path(adj:list,start:int,end:int)->int`；-要求使用廣度優(yōu)先搜索（BFS）算法；-需處理start等于end的情況（返回0）。四、學(xué)生成績(jī)管理系統(tǒng)問(wèn)題描述：設(shè)計(jì)一個(gè)學(xué)生成績(jī)管理系統(tǒng)，支持以下功能：1.添加學(xué)生：輸入學(xué)生姓名（字符串，不重復(fù)）和3門課成績(jī)（整數(shù)，0-100）；2.查詢平均分：輸入學(xué)生姓名，返回其3門課的平均分（保留2位小數(shù)）；3.按總分排序：輸出所有學(xué)生按總分從高到低排序的列表（每個(gè)元素格式為"姓名:總分"）；4.統(tǒng)計(jì)不及格人數(shù)：返回3門課中至少1門不及格（成績(jī)<60）的學(xué)生數(shù)量。輸入輸出示例：添加學(xué)生："張三",[85,70,90]→系統(tǒng)記錄；添加學(xué)生："李四",[55,65,40]→系統(tǒng)記錄；查詢平均分（張三）→輸出81.67；按總分排序→輸出["張三:245","李四:160"]；統(tǒng)計(jì)不及格人數(shù)→輸出1（李四有2門不及格）。編程要求：-用Python類實(shí)現(xiàn)系統(tǒng)，類名為`GradeManager`；-添加學(xué)生方法名為`add_student(name:str,scores:list)`；-查詢平均分方法名為`get_average(name:str)->float`；-排序方法名為`sort_by_total()->list`；-統(tǒng)計(jì)方法名為`count_failed()->int`；-需處理重復(fù)姓名添加（提示"姓名已存在"并拒絕添加）。答案一、字符串處理與回文子串統(tǒng)計(jì)```pythondeffind_palindromes(s:str)->list:n=len(s)palindromes=set()用集合去重中心擴(kuò)展法defexpand(l,r):whilel>=0andr<nands[l]==s[r]:ifr-l+1>=3:palindromes.add(s[l:r+1])l-=1r+=1foriinrange(n):奇數(shù)長(zhǎng)度回文expand(i,i)偶數(shù)長(zhǎng)度回文（可能長(zhǎng)度≥3，如i=0,i+1=1時(shí)，長(zhǎng)度為2，不滿足，需后續(xù)擴(kuò)展）expand(i,i+1)按字典序排序returnsorted(palindromes)測(cè)試用例print(find_palindromes("ababa"))輸出：['aba','ababa','bab']```二、二叉樹(shù)的路徑和驗(yàn)證```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefhas_path_sum(root:TreeNode,target:int)->bool:ifnotroot:returnFalse空樹(shù)且target=0時(shí)也返回False到達(dá)葉子節(jié)點(diǎn)，檢查剩余值是否等于當(dāng)前節(jié)點(diǎn)值ifnotroot.leftandnotroot.right:returnroot.val==target遞歸檢查左右子樹(shù)returnhas_path_sum(root.left,target-root.val)orhas_path_sum(root.right,target-root.val)測(cè)試用例（構(gòu)建示例二叉樹(shù)）root=TreeNode(5)root.left=TreeNode(4,TreeNode(11,TreeNode(7),TreeNode(2)))root.right=TreeNode(8,TreeNode(13),TreeNode(4,None,TreeNode(1)))print(has_path_sum(root,22))輸出：True```三、圖的最短路徑計(jì)算```pythonfromcollectionsimportdequedefshortest_path(adj:list,start:int,end:int)->int:ifstart==end:return0n=len(adj)visited=[False]nqueue=deque()queue.append((start,0))(當(dāng)前節(jié)點(diǎn),路徑長(zhǎng)度)visited[start]=Truewhilequeue:node,dist=queue.popleft()forneighborinadj[node]:ifneighbor==end:returndist+1ifnotvisited[neighbor]:visited[neighbor]=Truequeue.append((neighbor,dist+1))return-1無(wú)法到達(dá)測(cè)試用例adj=[[1,2],[0,3],[0,4],[1,4],[2,3]]print(shortest_path(adj,0,4))輸出：2```四、學(xué)生成績(jī)管理系統(tǒng)```pythonclassGradeManager:def__init__(self):self.students={}姓名:{"scores":[],"total":int}defadd_student(self,name:str,scores:list):ifnameinself.students:print("姓名已存在")returniflen(scores)!=3ornotall(0<=s<=100forsinscores):print("成績(jī)格式錯(cuò)誤")returntotal=sum(scores)self.students[name]={"scores":scores,"total":total}defget_average(self,name:str)->float:ifnamenotinself.students:return-1.0姓名不存在total=self.students[name]["total"]returnround(total/3,2)defsort_by_total(self)->list:按總分降序排序，若總分相同則按姓名升序sorted_students=sorted(self.students.items(),key=lambdax:(-x[1]["total"],x[0]))return[f"{name}:{data['total']}"forname,datainsorted_students]defcount_failed(self)->int:count=0fordatainself.students.values():ifany(score<60forscoreindata["scores"]):count+=1returncount測(cè)試用例manager=GradeManager()manager.add_student("張三",[