2026年四川大學(xué)計算機(jī)科學(xué)專業(yè)面試試題含答案一、編程題（共3題，每題20分，總計60分）1.編程題（20分）題目：請用Python實現(xiàn)一個函數(shù)，輸入一個正整數(shù)`n`，輸出所有小于或等于`n`的素數(shù)的列表。要求不使用任何第三方庫，時間復(fù)雜度盡可能低。示例輸入：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]示例調(diào)用print(sieve_of_eratosthenes(10))#輸出：[2,3,5,7]解析：采用埃拉托斯特尼篩法（SieveofEratosthenes），時間復(fù)雜度為`O(nloglogn)`，適用于較大數(shù)值的素數(shù)篩選。首先初始化一個布爾數(shù)組`is_prime`，標(biāo)記所有數(shù)是否為素數(shù)，然后從2開始遍歷，將所有倍數(shù)標(biāo)記為非素數(shù)。最后返回所有標(biāo)記為`True`的索引（即素數(shù)）。2.編程題（20分）題目：請用C++實現(xiàn)一個無重復(fù)字符的最長子串查找函數(shù)，輸入一個字符串`s`，返回最長子串的長度。要求不使用任何庫函數(shù)，時間復(fù)雜度為`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;}解析：使用滑動窗口技術(shù)，`left`和`right`分別表示窗口的左右邊界。使用哈希表記錄字符的最新位置，當(dāng)發(fā)現(xiàn)重復(fù)字符時，將`left`移動到重復(fù)字符的下一個位置。時間復(fù)雜度為`O(n)`，空間復(fù)雜度為`O(m)`（`m`為字符集大?。?.編程題（20分）題目：請用Java實現(xiàn)一個二叉樹的最大深度計算函數(shù)，輸入一個二叉樹的根節(jié)點，返回其最大深度。要求不使用遞歸，時間復(fù)雜度為`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）計算二叉樹的最大深度，通過隊列實現(xiàn)。每次遍歷一層，深度加1，直到隊列為空。時間復(fù)雜度為`O(n)`，空間復(fù)雜度為`O(n)`。二、算法題（共2題，每題15分，總計30分）1.算法題（15分）題目：給定一個包含`n`個整數(shù)的數(shù)組`nums`和一個目標(biāo)值`target`，請找出數(shù)組中和為目標(biāo)值的三元組數(shù)量。要求不使用重復(fù)的三元組，時間復(fù)雜度盡可能低。示例輸入：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示例調(diào)用print(three_sum([-1,0,1,2,-1,-4],0))#輸出：3解析：先對數(shù)組排序，然后使用雙指針法遍歷數(shù)組。對于每個元素`nums[i]`，使用`left`和`right`分別指向`i`后面的元素，計算三數(shù)之和。若等于`target`，則計數(shù)并跳過重復(fù)元素；若小于`target`，則移動`left`；否則移動`right`。時間復(fù)雜度為`O(n^2)`。2.算法題（15分）題目：請設(shè)計一個算法，判斷一個字符串是否是另一個字符串的子串。要求不使用任何內(nèi)置函數(shù)，時間復(fù)雜度盡可能低。示例輸入：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示例調(diào)用print(is_substring("hello","ll"))#輸出：True解析：使用滑動窗口法，遍歷`s1`的前`n-m+1`個字符，檢查`s1`中從當(dāng)前位置開始的長度為`m`的子串是否與`s2`相同。若相同則返回`True`，否則繼續(xù)遍歷。時間復(fù)雜度為`O(nm)`。三、系統(tǒng)設(shè)計題（共1題，25分）1.系統(tǒng)設(shè)計題（25分）題目：請設(shè)計一個簡單的短URL生成系統(tǒng)，要求：1.輸入一個長URL，輸出一個短URL；2.短URL應(yīng)具有唯一性且長度盡可能短；3.支持短URL到長URL的解析；4.系統(tǒng)需考慮高并發(fā)場景下的性能和可用性。示例輸入：plaintext長URL：/path/to/resource?query=123示例輸出：plaintext短URL：http://short.url/abc123解析過程：1.將長URL哈希為唯一標(biāo)識（如SHA-256）；2.對哈希值進(jìn)行編碼（如Base62）生成短標(biāo)識；3.將短標(biāo)識與長URL映射存儲（如Redis）；4.解析時通過短標(biāo)識查詢長URL。答案要點：1.哈希算法：使用SHA-256保證唯一性，避免沖突；2.編碼方式：采用Base62（字母+數(shù)字）將哈希值壓縮為短標(biāo)識；3.存儲方案：使用Redis或內(nèi)存緩存存