2026年四川大学计算机科学专业面试试题含答案

2026年四川大学计算机科学专业面试试题含答案一、编程题（共3题，每题20分，总计60分）1.编程题（20分）题目：请用Python实现一个函数，输入一个正整数`n`，输出所有小于或等于`n`的素数的列表。要求不使用任何第三方库，时间复杂度尽可能低。示例输入：pythonn=10示例输出：python[2,3,5,7]答案与解析：pythondefsieve_of_eratosthenes(n):ifn<2:return[]is_prime=[True](n+1)is_prime[0]=is_prime[1]=Falseforiinrange(2,int(n0.5)+1):ifis_prime[i]:forjinrange(ii,n+1,i):is_prime[j]=Falsereturn[ifori,primeinenumerate(is_prime)ifprime]示例调用print(sieve_of_eratosthenes(10))#输出：[2,3,5,7]解析：采用埃拉托斯特尼筛法（SieveofEratosthenes），时间复杂度为`O(nloglogn)`，适用于较大数值的素数筛选。首先初始化一个布尔数组`is_prime`，标记所有数是否为素数，然后从2开始遍历，将所有倍数标记为非素数。最后返回所有标记为`True`的索引（即素数）。2.编程题（20分）题目：请用C++实现一个无重复字符的最长子串查找函数，输入一个字符串`s`，返回最长子串的长度。要求不使用任何库函数，时间复杂度为`O(n)`。示例输入：cpps="abcabcbb"示例输出：cpp3答案与解析：cppinclude<iostream>include<vector>include<unordered_map>usingnamespacestd;intlength_of_longest_substring(strings){unordered_map<char,int>char_index;intleft=0,max_len=0;for(intright=0;right<s.size();++right){if(char_index.find(s[right])!=char_index.end()){left=max(left,char_index[s[right]]+1);}char_index[s[right]]=right;max_len=max(max_len,right-left+1);}returnmax_len;}intmain(){strings="abcabcbb";cout<<length_of_longest_substring(s)<<endl;//输出：3return0;}解析：使用滑动窗口技术，`left`和`right`分别表示窗口的左右边界。使用哈希表记录字符的最新位置，当发现重复字符时，将`left`移动到重复字符的下一个位置。时间复杂度为`O(n)`，空间复杂度为`O(m)`（`m`为字符集大小）。3.编程题（20分）题目：请用Java实现一个二叉树的最大深度计算函数，输入一个二叉树的根节点，返回其最大深度。要求不使用递归，时间复杂度为`O(n)`。示例输入：javaTreeNoderoot=newTreeNode(3);root.left=newTreeNode(9);root.right=newTreeNode(20);root.right.left=newTreeNode(15);root.right.right=newTreeNode(7);示例输出：java3答案与解析：javaimportjava.util.LinkedList;importjava.util.Queue;classTreeNode{intval;TreeNodeleft,right;TreeNode(intx){val=x;}}publicclassMaxDepthBinaryTree{publicintmaxDepth(TreeNoderoot){if(root==null)return0;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);intdepth=0;while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){TreeNodenode=queue.poll();if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}depth++;}returndepth;}publicstaticvoidmain(String[]args){TreeNoderoot=newTreeNode(3);root.left=newTreeNode(9);root.right=newTreeNode(20);root.right.left=newTreeNode(15);root.right.right=newTreeNode(7);MaxDepthBinaryTreesolution=newMaxDepthBinaryTree();System.out.println(solution.maxDepth(root));//输出：3}}解析：使用层序遍历（BFS）计算二叉树的最大深度，通过队列实现。每次遍历一层，深度加1，直到队列为空。时间复杂度为`O(n)`，空间复杂度为`O(n)`。二、算法题（共2题，每题15分，总计30分）1.算法题（15分）题目：给定一个包含`n`个整数的数组`nums`和一个目标值`target`，请找出数组中和为目标值的三元组数量。要求不使用重复的三元组，时间复杂度尽可能低。示例输入：pythonnums=[-1,0,1,2,-1,-4],target=0示例输出：python3答案与解析：pythondefthree_sum(nums,target):nums.sort()n=len(nums)count=0foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:current_sum=nums[i]+nums[left]+nums[right]ifcurrent_sum==target:count+=1whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1elifcurrent_sum<target:left+=1else:right-=1returncount示例调用print(three_sum([-1,0,1,2,-1,-4],0))#输出：3解析：先对数组排序，然后使用双指针法遍历数组。对于每个元素`nums[i]`，使用`left`和`right`分别指向`i`后面的元素，计算三数之和。若等于`target`，则计数并跳过重复元素；若小于`target`，则移动`left`；否则移动`right`。时间复杂度为`O(n^2)`。2.算法题（15分）题目：请设计一个算法，判断一个字符串是否是另一个字符串的子串。要求不使用任何内置函数，时间复杂度尽可能低。示例输入：pythons1="hello",s2="ll"示例输出：pythonTrue答案与解析：pythondefis_substring(s1,s2):n,m=len(s1),len(s2)ifm==0:returnTrueifn<m:returnFalseforiinrange(n-m+1):ifs1[i:i+m]==s2:returnTruereturnFalse示例调用print(is_substring("hello","ll"))#输出：True解析：使用滑动窗口法，遍历`s1`的前`n-m+1`个字符，检查`s1`中从当前位置开始的长度为`m`的子串是否与`s2`相同。若相同则返回`True`，否则继续遍历。时间复杂度为`O(nm)`。三、系统设计题（共1题，25分）1.系统设计题（25分）题目：请设计一个简单的短URL生成系统，要求：1.输入一个长URL，输出一个短URL；2.短URL应具有唯一性且长度尽可能短；3.支持短URL到长URL的解析；4.系统需考虑高并发场景下的性能和可用性。示例输入：plaintext长URL：/path/to/resource?query=123示例输出：plaintext短URL：http://short.url/abc123解析过程：1.将长URL哈希为唯一标识（如SHA-256）；2.对哈希值进行编码（如Base62）生成短标识；3.将短标识与长URL映射存储（如Redis）；4.解析时通过短标识查询长URL。答案要点：1.哈希算法：使用SHA-256保证唯一性，避免冲突；2.编码方式：采用Base62（字母+数字）将哈希值压缩为短标识；3.存储方案：使用Redis或内存缓存存