2016年acm竞赛题目及答案

2016年acm竞赛题目及答案一、选择题（每题5分，共20分）1.在ACM竞赛中，以下哪个算法的时间复杂度是O(nlogn)？A.冒泡排序B.快速排序C.线性搜索D.选择排序答案：B2.在ACM竞赛中，以下哪个数据结构最适合存储稀疏矩阵？A.数组B.链表C.哈希表D.树答案：B3.在ACM竞赛中，以下哪个算法用于解决旅行商问题（TSP）？A.动态规划B.贪心算法C.深度优先搜索D.遗传算法答案：D4.在ACM竞赛中，以下哪个算法用于解决背包问题？A.动态规划B.贪心算法C.深度优先搜索D.遗传算法答案：A二、填空题（每题5分，共30分）1.在ACM竞赛中，快速排序算法的时间复杂度在最坏情况下是________。答案：O(n^2)2.在ACM竞赛中，哈夫曼编码是一种________编码方法。答案：最优前缀3.在ACM竞赛中，图的深度优先搜索（DFS）算法的时间复杂度是________。答案：O(V+E)4.在ACM竞赛中，Dijkstra算法用于求解图中的________问题。答案：最短路径5.在ACM竞赛中，二叉树的遍历方法有前序遍历、中序遍历和________遍历。答案：后序6.在ACM竞赛中，KMP算法用于解决字符串的________问题。答案：模式匹配三、编程题（每题20分，共40分）1.给定一个整数数组arr，长度为n，请编写一个函数，找出数组中最长的连续子数组，使得子数组中所有元素的和等于给定的值sum。如果不存在这样的子数组，请返回空数组。```pythondeflongest_subarray(arr,sum):你的代码```答案：```pythondeflongest_subarray(arr,sum):max_length=0current_sum=0start=0hashmap={0:-1}forend,numinenumerate(arr):current_sum+=numifcurrent_sum-suminhashmap:max_length=max(max_length,end-hashmap[current_sum-sum])hashmap[current_sum]=endreturnarr[hashmap[current_sum-sum]+1:end+1]ifmax_length>0else[]```2.给定一个二叉树的根节点root，请编写一个函数，按照前序遍历的顺序返回二叉树的节点值。```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorderTraversal(root):你的代码```答案：```pythondefpreorderTraversal(root):ifnotroot:return[]result=[]stack=[root]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult```四、算法题（每题30分，共30分）1.给定一个整数n，请编写一个函数，计算n的阶乘。```pythondeffactorial(n):你的代码```答案：```pythondeffactorial(n):ifn==0orn==1: