人工智能编程挑战赛测试题目及参考答案

人工智能编程挑战赛测试题目及参考答案第一部分：编程基础（共5题，每题10分，总分50分）题目1（10分）：编写一个Python函数，接收一个整数列表作为输入，返回该列表中所有奇数的平方和。例如，输入`[1,2,3,4,5]`，输出应为`1²+3²+5²=35`。题目2（10分）：实现一个简单的文本编辑器功能，接收两个字符串`s1`和`s2`，以及一个操作类型`op`（`"insert"`或`"delete"`）。若`op`为`"insert"`，将`s2`插入到`s1`的指定位置`index`（从0开始）；若`op`为`"delete"`，删除`s1`中从`index`开始的`length`个字符。输出操作后的字符串。题目3（10分）：给定一个字符串`s`，判断其是否为回文串（忽略大小写和空格）。若为回文串，返回`True`；否则返回`False`。例如，`s="Aman,aplan,acanal:Panama"`应返回`True`。题目4（10分）：编写一个函数，接收一个正整数`n`，返回一个列表，其中包含从1到`n`的所有斐波那契数列中的偶数（不包括大于`n`的数）。例如，`n=10`时，输出`[2,8]`。题目5（10分）：实现一个简单的加密函数，接收一个字符串`s`和一个整数`key`，对字符串进行凯撒密码加密（字母循环移位，非字母字符不变）。例如，`s="Hello,World!"`，`key=3`，输出`"Khoor,Zruog!"`。第二部分：算法与数据结构（共5题，每题10分，总分50分）题目6（10分）：给定一个无重复元素的整数数组`nums`和一个目标值`target`，编写函数返回`target`在数组中的索引。若不存在，返回`-1`。例如，`nums=[5,7,2,9,4]`，`target=9`，输出`3`。题目7（10分）：实现一个二叉树的前序遍历（根-左-右）的迭代版本，不使用递归。提供树的节点定义：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right题目8（10分）：编写一个函数，接收一个字符串列表`words`，返回其中最长的“最长公共前缀”。例如，`words=["flower","flow","flight"]`，输出`"fl"`。题目9（10分）：实现一个LRU（最近最少使用）缓存，支持`get`和`put`操作。使用哈希表和双向链表结合实现，要求`get`和`put`均为O(1)时间复杂度。题目10（10分）：给定一个字符串`s`，判断其是否为有效括号字符串（只包含`()`、`[]`、`{}`，且括号正确配对）。例如，`s="{[()]}"`应返回`True`。第三部分：实际应用（共5题，每题10分，总分50分）题目11（10分）：假设你是一名电商平台的开发者，需要实现一个推荐系统。给定用户购买历史`history`（列表形式，如`["apple","banana","apple","orange"]`），返回用户可能感兴趣的商品列表（出现频率最高的3个商品）。若多个商品频率相同，按字母顺序排列。题目12（10分）：编写一个函数，接收一个字符串`s`，统计其中每个字母（区分大小写）和数字的出现次数，返回一个字典。例如，`s="a1B2c3"`，输出`{"a":1,"1":1,"B":1,"2":1,"c":1,"3":1}`。题目13（10分）：实现一个简单的文本分类器，给定文本`text`和分类标签`labels`（列表形式），返回每个标签的文档频率（即包含该标签的文档数占总文档数的比例）。例如，`labels=["spam","ham","spam","ham"]`，输出`{"spam":0.5,"ham":0.5}`。题目14（10分）：假设你正在开发一个交通信号灯控制系统，需要根据车流量动态调整信号灯时长。编写一个函数，接收当前时间`current_time`（字符串，如`"14:30"`）和车流量数据`traffic`（字典形式，如`{"green":5,"yellow":2,"red":8}`），返回当前信号灯状态（`"green"`、`"yellow"`或`"red"`）。规则：若当前时间在信号灯时长内，返回当前状态；否则根据车流量最高的状态返回。题目15（10分）：编写一个函数，接收一个包含多个子列表的二维列表`matrix`，返回其转置矩阵。例如，`matrix=[[1,2,3],[4,5,6]]`，输出`[[1,4],[2,5],[3,6]]`。参考答案及解析第一部分：编程基础题目1（10分）：pythondefsum_of_odds_squared(nums):returnsum(x2forxinnumsifx%2!=0)解析：-列表推导式遍历`nums`，筛选奇数`x`，计算其平方`x2`，最后用`sum`求和。-例如，`[1,2,3,4,5]`→`1²+3²+5²=1+9+25=35`。题目2（10分）：pythondeftext_editor(s1,s2,op,index,length=None):ifop=="insert":returns1[:index]+s2+s1[index:]elifop=="delete":returns1[:index]+s1[index+length:]else:raiseValueError("Invalidoperation")解析：-`"insert"`：将`s2`插入`s1`的`index`位置，即`s1[:index]+s2+s1[index:]`。-`"delete"`：删除`s1`中从`index`开始的`length`个字符，即`s1[:index]+s1[index+length:]`。-例如，`s1="Hello"`,`s2="World"`,`op="insert"`,`index=5`→`"HelloWorld"`。题目3（10分）：pythondefis_palindrome(s):s=''.join(c.lower()forcinsifc.isalnum())returns==s[::-1]解析：-去除空格和大小写，转换为小写`s.lower()`，过滤非字母数字`c.isalnum()`，然后检查是否为回文`s==s[::-1]`。-例如，`"Aman,aplan,acanal:Panama"`→`amanaplanacanalpanama`→回文。题目4（10分）：pythondefeven_fibonacci(n):a,b=0,1result=[]whileb<=n:ifb%2==0:result.append(b)a,b=b,a+breturnresult解析：-使用斐波那契数列迭代生成器，检查偶数`b%2==0`，加入结果列表。-例如，`n=10`→`0,1,1,2,3,5,8`→`[2,8]`。题目5（10分）：pythondefcaesar_cipher(s,key):result=[]forcins:ifc.isalpha():offset=65ifc.isupper()else97new_char=chr((ord(c)-offset+key)%26+offset)result.append(new_char)else:result.append(c)return''.join(result)解析：-对字母字符循环移位，大写字母`A-Z`（ASCII65-90），小写字母`a-z`（ASCII97-122）。-例如，`"Hello,World!"`,`key=3`→`"Khoor,Zruog!"`。第二部分：算法与数据结构题目6（10分）：pythondefsearch(nums,target):fori,numinenumerate(nums):ifnum==target:returnireturn-1解析：-遍历列表`nums`，若找到`target`则返回索引`i`，否则返回`-1`。-例如，`nums=[5,7,2,9,4]`,`target=9`→`3`。题目7（10分）：pythondefpreorder_iterative(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult解析：-使用栈模拟递归，先访问根节点，再右子树后左子树入栈。-例如，`root=[1,2,3]`→`[1,2,3]`。题目8（10分）：pythondeflongest_common_prefix(words):ifnotwords:return""prefix=words[0]forwordinwords[1:]:whilenotword.startswith(prefix):prefix=prefix[:-1]ifnotprefix:return""returnprefix解析：-初始前缀为第一个单词，逐个单词比较，缩短前缀直到匹配或为空。-例如，`["flower","flow","flight"]`→`"fl"`。题目9（10分）：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.order=[]defget(self,key):ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key,value):ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：-使用哈希表`cache`存储键值对，双向列表`order`记录访问顺序。-`get`时移动到末尾，`put`时先删除最久未使用项（若超出容量）。题目10（10分）：pythondefvalid_parentheses(s):stack=[]mapping={')':'(','}':'{',']':'['}forcins:ifcinmapping.values():stack.append(c)elifcinmapping:ifnotstackorstack.pop()!=mapping[c]:returnFalseelse:returnFalsereturnnotstack解析：-使用栈匹配括号，左括号入栈，右括号与栈顶比较。若栈为空或匹配失败返回`False`。-例如，`"{[()]}"`→`True`。第三部分：实际应用题目11（10分）：pythonfromcollectionsimportCounterdeftop_n_items(history,n=3):counter=Counter(history)returncounter.most_common(n)解析：-使用`Counter`统计商品频率，`most_common(n)`返回频率最高的`n`个商品。-例如，`["apple","banana","apple","orange"]`→`[('apple',2),('banana',1),('orange',1)]`。题目12（10分）：pythondefcount_chars(s):return{c:s.count(c)forcinset(s)}解析：-使用字典推导式，对字符串中每个唯一字符`c`统计出现次数`s.count(c)`。-例如，`"a1B2c3"`→`{'a':1,'1':1,'B':1,'2':1,'c':1,'3':1}`。题目13（10分）：pythondefdoc_frequency(labels):total=len(labels)freq={}forlabelinset(labels):freq[label]=labels.count(label)/totalreturnfreq解析：-统计每个标签的出现次数，除以总文档数`total`得到文档频率。-例如，`["spam","ham","spam","ham"]`→`{'spam':0.5,'ham':0.5}`。题目14（10分）：pythondeftraffic_l