2026年计算机编程面试题模拟测试

2026年计算机编程面试题模拟测试一、编程基础（3题，每题10分，共30分）题目1（Java基础）：编写一个Java方法，实现将一个字符串中的所有空格替换为`%20`。假设字符串的长度足够容纳替换后的结果，且输入字符串只包含字母和空格。示例输入：`"HelloWorld"`示例输出：`"Hello%20World"`要求：1.不能使用Java自带的`replace`方法。2.时间复杂度不超过O(n)。题目2（C++基础）：用C++实现一个函数，检查一个整数是否为完全平方数。如果是，返回`true`；否则返回`false`。示例输入：`16`示例输出：`true`示例输入：`14`示例输出：`false`要求：1.不能使用库函数，如`sqrt`。2.空间复杂度为O(1)。题目3（Python基础）：编写一个Python函数，接受一个列表作为参数，返回列表中所有奇数的平方和。示例输入：`[1,2,3,4,5]`示例输出：`35`（即1²+3²+5²=1+9+25=35）要求：1.不能使用列表推导式。2.忽略列表中的负数。二、数据结构与算法（5题，每题15分，共75分）题目4（链表操作-Java/C++）：给定一个单链表，反转链表并返回反转后的头节点。示例输入：`1->2->3->4->5`示例输出：`5->4->3->2->1`要求：1.不能使用递归。2.时间复杂度为O(n)，空间复杂度为O(1)。题目5（动态规划-Python/Java）：给定一个整数数组`nums`和一个整数`target`，返回数组中和为目标`target`的所有唯一组合。组合中的数字可以重复排列。示例输入：`nums=[2,3,6,7]`,`target=7`示例输出：`[[2,2,3],[7]]`要求：1.解集不能包含重复的组合。2.可以假设`nums`中的所有数字都是正整数。题目6（二叉树遍历-C++/Java）：实现二叉树的层序遍历（即按层次从左到右遍历）。示例输入：3/\920/\157示例输出：`[3,9,20,15,7]`要求：1.使用队列实现。2.不能使用递归。题目7（贪心算法-Python/C++）：给定一个非负整数数组`nums`，将数组中的元素按非递减顺序排列。示例输入：`[5,2,6,1]`示例输出：`[1,2,5,6]`要求：1.不能使用内置的排序函数。2.使用快速排序的贪心策略实现。题目8（哈希表应用-Java/Python）：设计一个LRU（LeastRecentlyUsed）缓存系统，支持`get`和`put`操作。缓存容量为`capacity`。示例输入：-`put(1,1)`-`put(2,2)`-`get(1)`→返回`1`-`put(3,3)`→压缩最久未使用的元素-`get(2)`→返回`2`示例输出：`1`和`2`要求：1.`get`操作返回键对应的值，如果不存在则返回-1。2.`put`操作将键值对插入缓存，如果键已存在则更新值，如果超出容量则删除最久未使用的元素。三、系统设计（2题，每题20分，共40分）题目9（分布式系统-针对互联网行业）：设计一个高并发的短链接生成系统。要求：1.链接长度尽可能短（如`http://short.url/abcd`）。2.支持高并发访问（每秒百万级请求）。3.保证唯一性且可快速反向解析为原始链接。要求：1.说明主要技术选型（如数据库、缓存、算法）。2.分析可能的性能瓶颈及解决方案。题目10（数据库设计-针对金融行业）：设计一个用于交易流水记录的数据库表。要求：1.表中记录每笔交易的ID、用户ID、金额、交易时间、交易状态（成功/失败）。2.支持按用户ID和交易时间范围快速查询。3.考虑数据量增长时的扩展性（如分库分表）。要求：1.写出表结构（字段、类型、索引）。2.说明如何应对数据量增长（如分区键选择）。答案与解析一、编程基础题目1（Java）：javapublicStringreplaceSpaces(Strings){if(s==null)returnnull;intspaceCount=0;//先统计空格数量for(charc:s.toCharArray()){if(c=='')spaceCount++;}//创建新字符串char[]result=newchar[s.length()+spaceCount2];intindex=0;for(charc:s.toCharArray()){if(c==''){result[index++]='%';result[index++]='2';result[index++]='0';}else{result[index++]=c;}}returnnewString(result);}解析：1.先遍历一次字符串统计空格数量，因为替换后长度会变化。2.使用字符数组进行替换，时间复杂度为O(n)，空间复杂度为O(n)。3.避免使用`replace`方法，直接按字符处理。题目2（C++）：cppboolisPerfectSquare(intnum){if(num<0)returnfalse;longleft=0,right=num;while(left<=right){longmid=left+(right-left)/2;longsquare=midmid;if(square==num)returntrue;if(square<num)left=mid+1;elseright=mid-1;}returnfalse;}解析：1.使用二分查找法判断平方根是否为整数。2.避免使用`sqrt`函数，通过比较平方值实现。3.时间复杂度为O(logn)，空间复杂度为O(1)。题目3（Python）：pythondefsum_of_odds_square(nums):total=0fornuminnums:ifnum%2!=0:total+=numnumreturntotal解析：1.遍历列表，忽略偶数，计算奇数的平方并累加。2.不使用列表推导式，符合题目要求。3.时间复杂度为O(n)，空间复杂度为O(1)。二、数据结构与算法题目4（链表反转）：javapublicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurrent=head;while(current!=null){ListNodenext=current.next;current.next=prev;prev=current;current=next;}returnprev;}解析：1.使用三个指针（prev,current,next）实现原地反转。2.时间复杂度为O(n)，空间复杂度为O(1)。3.避免递归以防止栈溢出。题目5（组合总和）：pythondefcombinationSum(nums,target):res=[]nums.sort()defbacktrack(start,path,target):iftarget==0:res.append(path.copy())returnforiinrange(start,len(nums)):ifnums[i]>target:breakifi>startandnums[i]==nums[i-1]:continuepath.append(nums[i])backtrack(i+1,path,target-nums[i])path.pop()backtrack(0,[],target)returnres解析：1.先排序去重，避免重复组合。2.使用回溯法，剪枝条件为当前数字大于目标值或与前一个数字相同。3.时间复杂度取决于数字的排列组合数量。题目6（二叉树层序遍历）：pythonfromcollectionsimportdequedeflevelOrder(root):ifnotroot:return[]res=[]queue=deque([root])whilequeue:level=[]for_inrange(len(queue)):node=queue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres解析：1.使用队列实现BFS，按层次遍历。2.时间复杂度为O(n)，空间复杂度为O(n)。3.避免递归以适应大规模数据。题目7（快速排序贪心策略）：cppvoidquickSort(intarr[],intleft,intright){if(left>=right)return;intpivot=arr[right];inti=left-1;for(intj=left;j<right;j++){if(arr[j]<=pivot){i++;swap(arr[i],arr[j]);}}swap(arr[i+1],arr[right]);quickSort(arr,left,i);quickSort(arr,i+2,right);}解析：1.快速排序的核心是分区操作，选择右端为枢轴。2.贪心策略在于每次选择比枢轴小的元素交换到左边。3.时间复杂度为O(nlogn)，空间复杂度为O(logn)。题目8（LRU缓存）：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeynotinself.cache:return-1self.order.remove(key)self.order.append(key)returnself.cache[key]defput(self,key:int,value:int)->None: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)解析：1.使用哈希表存储键值对，维护一个双向排列的`order`列表记录访问顺序。2.`get`操作将键移到末尾表示最近使用。3.`put`操作先移除最久未使用的键（头部），然后插入新键。三、系统设计题目9（短链接系统）：技术选型：1.编码算法：使用62进制（a-z,A-Z,0-9）将ID转换为短链接，如`http://short.url/1aBc`。2.数据库：使用自增ID，通过Redis缓存热点链接，减少数据库查询。3.分布式架构：使用Nginx负载均衡，配合多台后端服务器处理请求。性能瓶颈与解决方案：1.ID生成：使用Snowflake算法生成唯一ID，避免冲突。2.缓存穿透：对不存在的链接使用布隆过滤器提前拦截。3.高并发：使用限流熔断机制防止系统过载。题目10（交易流水数据库设计）：表结构：sqlCREATETABLEtrade_records(idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,amountDECIMAL(10,2)NOTNULL,trade_timeTIMES