计算机科学与技术专业2026年算法题

计算机科学与技术专业2026年算法题算法题目（共5题，总分100分）1.单选题（共3题，每题5分，总分15分）背景说明：针对国内互联网行业高频面试场景，考察基本数据结构与算法知识。题目1（链表操作）：给定一个单链表，判断链表中是否存在环。若存在环，返回入环点的节点；若不存在环，返回`null`。请写出算法实现，并分析时间复杂度。示例输入：链表：1→2→3→4→2（此处2为已存在的环节点）示例输出：返回节点`2`题目2（动态规划）：假设你正在开发一个外卖平台，需要计算从用户当前位置到餐厅的最短路径（不考虑障碍物）。地图可以抽象为一张无向图，节点代表路口，边代表可走的道路，边权重为行走时间（单位：分钟）。请实现一个算法，计算最短路径长度，并给出时间复杂度分析。示例输入：图结构：-A→B（10分钟）-A→C（15分钟）-B→C（5分钟）-C→D（20分钟）示例输出：从A到D的最短路径为`A→B→C→D`，总时间`30分钟`题目3（贪心算法）：某电商平台正在进行促销活动，需要为用户推荐商品。规则如下：-用户最多可购买`k`件商品，每件商品有价格`p_i`和权重`w_i`。-目标是最大化商品总权重（即用户获得的价值最大化）。请设计一个贪心算法解决此问题，并说明贪心策略。示例输入：商品数量`n=5`，`k=3`，`p=[20,50,10,30,40]`，`w=[3,4,2,5,6]`示例输出：选择商品`B（50,4）`、`D（30,5）`、`E（40,6）`，总权重`15`2.编程题（共2题，每题35分，总分70分）背景说明：针对国内大型互联网公司（如腾讯、阿里、字节跳动）的在线编程题风格，考察实际工程应用能力。题目4（二叉树遍历与变形）：给定一个二叉树，请实现一个算法，将树中的所有左子树替换为右子树，然后返回新的二叉树结构。例如：示例输入：二叉树：1/\23/\\456示例输出：1/\32/\65/4题目5（字符串处理）：某外卖平台需要优化订单字符串的解析效率。订单字符串由多个订单号以逗号分隔（如`"A1,B2,C3"`），每个订单号包含字母和数字。请实现一个算法，统计每个订单号的出现频率，并按频率从高到低排序输出。示例输入：`"A1,B2,A1,C3,B2,B2,C3,A1"`示例输出：`{"B2":3,"A1":3,"C3":2}`答案与解析1.单选题答案与解析题目1（链表操作）：答案：pythonclassListNode:def__init__(self,x):self.val=xself.next=NonedefdetectCycle(head):ifnotheadornothead.next:returnNoneslow=headfast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:找到环，确定入环点slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：-使用快慢指针（Floyd判环算法）检测链表是否存在环。-若快指针与慢指针相遇，则链表有环，继续移动慢指针至头节点，再次相遇处为入环点。-时间复杂度`O(n)`，空间复杂度`O(1)`。题目2（动态规划）：答案：pythonimportheapqdefdijkstra(graph,start):distances={node:float('inf')fornodeingraph}distances[start]=0pq=[(0,start)]whilepq:current_dist,current_node=heapq.heappop(pq)ifcurrent_dist>distances[current_node]:continueforneighbor,weightingraph[current_node].items():distance=current_dist+weightifdistance<distances[neighbor]:distances[neighbor]=distanceheapq.heappush(pq,(distance,neighbor))returndistances解析：-使用Dijkstra算法求解单源最短路径。-优先队列（最小堆）优化时间复杂度至`O((E+V)logV)`。-适用于稀疏图和稠密图，适合外卖平台路口路径计算。题目3（贪心算法）：答案：pythondefknapsack(p,w,k):items=sorted(zip(p,w),key=lambdax:x[1]/x[0],reverse=True)total_weight=0result=[]forprice,weightinitems:iftotal_weight+weight<=k:total_weight+=weightresult.append(price)iflen(result)==k:breakreturnsum(result)解析：-贪心策略：按商品权重与价格的比值从高到低选择，直到达到容量上限。-时间复杂度`O(nlogn)`，适用于商品数量较少的场景。2.编程题答案与解析题目4（二叉树遍历与变形）：答案：pythonclassTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=NonedefreplaceLeftWithRight(root):ifnotroot:returnNonestack=[root]whilestack:node=stack.pop()node.left,node.right=node.right,node.leftifnode.left:stack.append(node.left)ifnode.right:stack.append(node.right)returnroot解析：-使用栈进行深度优先遍历，交换每个节点的左右子树。-时间复杂度`O(n)`，空间复杂度`O(n)`。题目5（字符串处理）：答案：pythonfromcollectionsimportCounterdefcountOrderFrequency(order_str):orders=order_str.split(',')freq=Counter(orders)sorted_freq=dict(sorted(freq.item