2025年考研计算机考研编程难题解析（含答案）

2025年考研计算机考研编程难题解析（含答案）考试时间：______分钟总分：______分姓名：______一、编写一个函数`mergeIntervals(intervals[]Interval)`，合并所有重叠的区间。其中，`Interval`是一个结构体，定义如下：```gotypeIntervalstruct{StartintEndint}```输入一个区间列表`intervals`，其中的区间按照`Start`属性升序排列。合并后的区间列表也应该按照`Start`属性升序排列，且不包含任何重叠的区间。请给出该函数的Go语言实现。在实现中，你需要清晰地描述你的算法思路，并说明你的时间复杂度和空间复杂度。二、给定一个由`'a'`到`'z'`小写字母组成的字符串`s`，以及一个整数`k`。你需要找到`s`中长度为`k`的子串，使得子串中`'a'`到`'z'`的字母各不相同的最多个数。请你返回这个最多的个数。例如，`s="abcabcbb"`,`k=3`。可能的子串有"abc","bca","cab","abc","bcb","cbb"。其中"abc"和"cab"包含3个不同的字母，是最大的。返回`3`。请设计一个高效算法解决这个问题，并分析你的算法的时间复杂度。三、设计一个数据结构`LRUCache`，用来模拟最近最少使用（LRU）缓存。缓存可以存储最多`capacity`个键值对。实现`LRUCache`类：*`LRUCache(intcapacity)`以正整数`capacity`初始化缓存。*`intget(intkey)`返回缓存中键`key`对应的值（如果不存在，则返回`-1`）。*`voidput(intkey,intvalue)`如果键`key`已存在，则更新其值；如果键不存在，则添加该键值对。当缓存容量达到上限时，应该驱逐最久未使用（LRU）的缓存项。请给出该数据结构的Python实现。你可以选择使用哈希表和双向链表相结合的方式来设计，并简要说明你的设计思路。四、假设你要设计一个简单的文件系统，其中每个文件或目录都可以表示为树结构，根节点为`'/'`。文件和目录的名字由小写字母组成，且名字唯一。目录下可以包含文件或其他目录。你需要支持以下两种操作：1.`cdpath`：更改当前工作目录。`path`是一个绝对路径或相对路径。如果是绝对路径，它以`'/'`开头；如果是相对路径，它以`'.'`或`'..'`开头。`'.'`表示当前目录，`'..'`表示上一级目录。路径中可能包含多个目录名，由`'/'`分隔。如果`path`无效（例如，试图访问一个不存在的目录），则保持当前目录不变。2.`ls`：列出当前工作目录下的所有文件和目录名，按照名称升序排列。请给出这两种操作的Python实现。你可以设计合适的数据结构来表示文件系统，并实现上述功能。五、编写一个函数`topKFrequent(nums[]int,kint)[]int`，返回`nums`数组中出现频率最高的`k`个元素。你可以假设`nums`中的元素都是整数，且`k`始终有效，即`1<=k<=nums.length`。请给出该函数的Python实现。在实现中，你可以考虑使用哈希表来统计频率，并使用合适的数据结构（如堆）来找到频率最高的`k`个元素。请分析你的算法的时间复杂度和空间复杂度。六、考虑一个有向无环图（DAG），其中节点代表任务，有向边代表任务之间的依赖关系（即箭头指向的任务必须在箭头源任务完成后才能执行）。给定一个DAG和每个任务的执行时间，你需要计算完成所有任务所需的最短时间。请设计一个算法来解决这个问题。你需要明确你的输入和输出。假设输入以邻接列表的形式给出，其中每个节点的出边信息已知。请给出算法的主要步骤，并分析其时间复杂度。试卷答案一、```gofuncmergeIntervals(intervals[]Interval)[]Interval{iflen(intervals)==0{returnnil}//首先按起点排序sort.Slice(intervals,func(i,jint)bool{returnintervals[i].Start<intervals[j].Start})merged:=make([]Interval,0)//初始化第一个区间current:=intervals[0]merged=append(merged,current)fori:=1;i<len(intervals);i++{//如果当前区间的终点大于等于下一个区间的起点，发生重叠ifcurrent.End>=intervals[i].Start{//合并区间，更新当前区间的终点为两者终点最大值current.End=max(current.End,intervals[i].End)}else{//不重叠，将当前区间加入结果，更新current为下一个区间current=intervals[i]merged=append(merged,current)}}returnmerged}funcmax(a,bint)int{ifa>b{returna}returnb}```解析思路：首先对区间列表按起点进行排序。然后初始化一个空的结果列表`merged`。遍历排序后的区间列表，使用一个`current`变量来跟踪当前正在合并的区间。对于每个新区间，如果它与`current`区间重叠（即`current.End>=intervals[i].Start`），则更新`current`的终点为两者终点中的较大值。如果不重叠，则将`current`区间加入`merged`，并将新区间设为新的`current`。最后返回`merged`。时间复杂度O(nlogn)来自排序，空间复杂度O(n)用于存储结果。二、```pythondefmaxUniqueLetters(s:str,k:int)->int:max_count=0left=0char_count={}forrightinrange(len(s)):#更新当前右边界字符的计数char_count[s[right]]=char_count.get(s[right],0)+1#如果窗口大小大于k，移动左边界whileright-left+1>k:char_count[s[left]]-=1ifchar_count[s[left]]==0:delchar_count[s[left]]left+=1#窗口大小为k时，计算不同字符的数量ifright-left+1==k:max_count=max(max_count,len(char_count))returnmax_count```解析思路：使用滑动窗口技术。初始化左指针`left`为0，右指针`right`从0开始遍历字符串`s`。使用一个字典`char_count`来记录当前窗口中字符的频率。对于每个`right`，将`s[right]`的频率加一。如果窗口大小（`right-left+1`）大于`k`，则移动左指针`left`，并相应减少`char_count`中`s[left]`的频率，如果频率为0则删除该键值对。当窗口大小等于`k`时，计算`char_count`的长度（即不同字符的数量），并更新`max_count`。遍历结束后返回`max_count`。时间复杂度O(n)，空间复杂度O(1)（因为字母只到'z'，字典大小有限）。三、```pythonclassNode:def__init__(self,key=None,value=None):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}#创建伪头部和伪尾部self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):#将节点添加到头部后面node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):#移除节点prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):#将节点移动到头部self._remove_node(node)self._add_node(node)def_pop_tail(self):#弹出尾部节点res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1#使用节点self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:#创建新节点new_node=Node(key,value)self.cache[key]=new_nodeself._add_node(new_node)#如果超出容量，删除尾部节点iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:#更新节点node.value=valueself._move_to_head(node)```解析思路：使用哈希表`cache`存储键到节点的映射，以便O(1)时间复杂度访问。使用双向链表（DoublyLinkedList）维护节点的使用顺序，最近使用的节点靠近头部。链表包含一个伪头部`head`和一个伪尾部`tail`，它们不存储实际数据。`_add_node`将节点插入链表头部，`_remove_node`从链表中移除节点，`_move_to_head`将节点移动到链表头部，`_pop_tail`移除链表尾部节点（即最久未使用节点）。`get`操作先从哈希表查找节点，如果找到则将其移动到头部并返回值，否则返回`-1`。`put`操作先尝试从哈希表获取节点，如果不存在则创建新节点并插入链表头部，同时加入哈希表；如果节点存在，则更新值并将其移动到头部。如果插入后缓存大小超过`capacity`，则移除尾部节点并从哈希表中删除对应的键。时间复杂度均为O(1)。四、```pythonclassFileSystem:def__init__(self):self.current_path=['']#使用列表表示路径，根目录是空字符串defcd(self,path:str)->None:ifpath=='/':self.current_path=['']returnparts=path.split('/')i=0forpartinparts:ifpart=='.':continueelifpart=='..':i=max(0,i-1)else:i+=1self.current_path=self.current_path[:i]+[part]defls(self)->List[str]:#返回当前路径下的所有文件和目录名，按字母序#这里简化为返回当前路径列表的排序版本returnsorted(self.current_path)```解析思路：使用一个列表`current_path`来表示当前工作目录的路径，其中每个元素是一个目录名，根目录用一个空字符串表示。`cd`操作根据输入的`path`更新`current_path`。如果`path`是`'/'`，则重置为根目录。如果`path`是相对路径，则遍历`path`的每个部分：`'.'`忽略，`'..'`表示回到上一级（`i`减一，但不小于0），其他部分表示进入下一级（`i`加一）。`ls`操作返回当前路径下的所有文件和目录名，这里简化为返回`current_path`列表的排序版本。实际应用中，`ls`可能需要从文件系统中获取实际文件和目录列表并排序。时间复杂度主要在排序上，为O(nlogn)，其中n是`current_path`的长度。五、```pythonfromcollectionsimportCounteri