2025年華為筆試題庫及答案一、算法與數(shù)據(jù)結(jié)構(gòu)1.題目：給定一個(gè)單鏈表的頭節(jié)點(diǎn)head，實(shí)現(xiàn)一個(gè)函數(shù)將鏈表從中間節(jié)點(diǎn)處反轉(zhuǎn)后半部分（若鏈表長(zhǎng)度為偶數(shù)，以第n/2個(gè)節(jié)點(diǎn)為中間節(jié)點(diǎn)）。例如，輸入1>2>3>4>5，中間節(jié)點(diǎn)為3，反轉(zhuǎn)后為1>2>3>5>4；輸入1>2>3>4，中間節(jié)點(diǎn)為2，反轉(zhuǎn)后為1>2>4>3。答案及解析：步驟1：找到中間節(jié)點(diǎn)。使用快慢指針法，快指針每次走兩步，慢指針每次走一步，當(dāng)快指針到達(dá)末尾時(shí)，慢指針指向中間節(jié)點(diǎn)（偶數(shù)長(zhǎng)度時(shí)為前半部分最后一個(gè)節(jié)點(diǎn)）。步驟2：分割鏈表為前半部分（頭到中間節(jié)點(diǎn)）和后半部分（中間節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)到末尾）。步驟3：反轉(zhuǎn)后半部分鏈表。步驟4：將前半部分的尾節(jié)點(diǎn)（中間節(jié)點(diǎn)）的next指向反轉(zhuǎn)后的后半部分頭節(jié)點(diǎn)。代碼實(shí)現(xiàn)（Python）：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_mid(head):ifnotheadornothead.next:returnhead找中間節(jié)點(diǎn)slow,fast=head,headwhilefast.nextandfast.next.next:slow=slow.nextfast=fast.next.nextmid=slow分割后半部分second=mid.nextmid.next=None斷開前半部分反轉(zhuǎn)后半部分prev,curr=None,secondwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_node連接前半部分和反轉(zhuǎn)后的后半部分mid.next=prevreturnhead```2.題目：給定一個(gè)整數(shù)數(shù)組nums和一個(gè)整數(shù)k，找出數(shù)組中和至少為k的最短非空子數(shù)組的長(zhǎng)度。如果不存在這樣的子數(shù)組，返回1。答案及解析：本題需使用前綴和+單調(diào)隊(duì)列優(yōu)化。前綴和數(shù)組s，其中s[i]表示前i個(gè)元素的和。對(duì)于每個(gè)j，尋找最小的i<j，使得s[j]s[i]>=k，且ji最小。維護(hù)一個(gè)單調(diào)遞增的隊(duì)列，保證隊(duì)列中的前綴和是遞增的，這樣當(dāng)s[j]s[q[0]]>=k時(shí)，后續(xù)的j'更大，q[0]不可能成為更優(yōu)解，可以彈出。代碼實(shí)現(xiàn)（Java）：```javapublicintshortestSubarray(int[]nums,intk){intn=nums.length;long[]s=newlong[n+1];for(inti=0;i<n;i++)s[i+1]=s[i]+nums[i];Deque<Integer>q=newArrayDeque<>();intres=n+1;for(intj=0;j<=n;j++){while(!q.isEmpty()&&s[j]s[q.peekFirst()]>=k){res=Math.min(res,jq.pollFirst());}while(!q.isEmpty()&&s[j]<=s[q.peekLast()]){q.pollLast();}q.addLast(j);}returnres<=n?res:1;}```二、操作系統(tǒng)3.題目：某系統(tǒng)采用可變分區(qū)存儲(chǔ)管理，內(nèi)存初始為100MB，分配采用首次適應(yīng)算法。依次執(zhí)行以下操作：分配20MB，分配30MB，釋放20MB，分配40MB，釋放30MB，分配10MB。請(qǐng)畫出每一步內(nèi)存分配后的分區(qū)狀態(tài)（用表格表示）。答案及解析：|步驟|操作|內(nèi)存分區(qū)狀態(tài)（起始地址:大小/狀態(tài)）||||||初始||0:100MB（空閑）||1|分配20MB|0:20MB（占用）,20:80MB（空閑）||2|分配30MB|0:20MB（占用）,20:30MB（占用）,50:50MB（空閑）||3|釋放20MB|0:20MB（空閑）,20:30MB（占用）,50:50MB（空閑）||4|分配40MB|0:20MB（空閑）,20:30MB（占用）,50:40MB（占用）,90:10MB（空閑）||5|釋放30MB|0:20MB（空閑）,20:30MB（空閑）,50:40MB（占用）,90:10MB（空閑）||6|分配10MB|0:20MB（空閑）,20:30MB（空閑）,50:40MB（占用）,90:10MB（占用）|4.題目：某系統(tǒng)有3個(gè)進(jìn)程P1、P2、P3，4類資源R1R4，數(shù)量分別為6、5、7、8。當(dāng)前資源分配情況如下：|進(jìn)程|Max（最大需求）|Allocation（已分配）||||||P1|[4,2,3,5]|[2,1,1,2]||P2|[3,3,3,3]|[1,1,2,1]||P3|[5,2,2,4]|[2,0,2,2]|計(jì)算系統(tǒng)當(dāng)前是否處于安全狀態(tài)，若安全給出安全序列；若不安全說明原因。答案及解析：步驟1：計(jì)算Need矩陣（Need=MaxAllocation）：P1:[2,1,2,3]P2:[2,2,1,2]P3:[3,2,0,2]步驟2：計(jì)算Available（總資源已分配總和）：已分配總和：R1=2+1+2=5；R2=1+1+0=2；R3=1+2+2=5；R4=2+1+2=5總資源：[6,5,7,8]→Available=[65,52,75,85]=[1,3,2,3]步驟3：模擬銀行家算法尋找安全序列：檢查P1：Need=[2,1,2,3]>Available[1,3,2,3]（R1需求2>可用1）→不可行檢查P2：Need=[2,2,1,2]>Available[1,3,2,3]（R1需求2>可用1）→不可行檢查P3：Need=[3,2,0,2]>Available[1,3,2,3]（R1需求3>可用1）→不可行所有進(jìn)程均無法滿足需求，系統(tǒng)處于不安全狀態(tài)。三、計(jì)算機(jī)網(wǎng)絡(luò)5.題目：簡(jiǎn)述TCP四次揮手的過程，并說明TIME_WAIT狀態(tài)的作用及常見持續(xù)時(shí)間。答案及解析：四次揮手過程：（1）客戶端發(fā)送FIN=1，seq=u，進(jìn)入FIN_WAIT_1狀態(tài)，表示客戶端無數(shù)據(jù)發(fā)送。（2）服務(wù)器收到后發(fā)送ACK=1，ack=u+1，seq=v，進(jìn)入CLOSE_WAIT狀態(tài)，表示已收到客戶端關(guān)閉請(qǐng)求。（3）服務(wù)器數(shù)據(jù)發(fā)送完畢后，發(fā)送FIN=1，ACK=1，seq=w，ack=u+1，進(jìn)入LAST_ACK狀態(tài)。（4）客戶端收到后發(fā)送ACK=1，ack=w+1，seq=u+1，進(jìn)入TIME_WAIT狀態(tài)；服務(wù)器收到ACK后關(guān)閉連接，客戶端等待2MSL（最長(zhǎng)報(bào)文段壽命）后關(guān)閉。TIME_WAIT作用：確保最后一個(gè)ACK報(bào)文能到達(dá)服務(wù)器，若服務(wù)器未收到會(huì)重發(fā)FIN，客戶端可再次發(fā)送ACK。防止“迷路”的報(bào)文段出現(xiàn)在后續(xù)連接中，避免與新連接的數(shù)據(jù)混淆。常見持續(xù)時(shí)間：2MSL（通常為60秒）。6.題目：某公司網(wǎng)絡(luò)拓?fù)淙缦拢嚎偛浚?92.168.1.0/24）與分公司（192.168.2.0/24）通過路由器R1（總部側(cè)IP：192.168.1.1）和R2（分公司側(cè)IP：192.168.2.1）互聯(lián)，R1與R2之間通過廣域網(wǎng)線路連接，IP分別為10.0.0.1（R1）和10.0.0.2（R2）。要求總部和分公司能互相訪問內(nèi)部網(wǎng)絡(luò)，需在R1和R2上配置什么類型的路由？寫出具體配置命令（假設(shè)使用CiscoIOS）。答案及解析：需配置靜態(tài)路由或動(dòng)態(tài)路由（如RIP、OSPF）。此處以靜態(tài)路由為例：R1配置：iproute192.168.2.0255.255.255.010.0.0.2（指向分公司網(wǎng)絡(luò)的下一跳為R2的廣域網(wǎng)IP）R2配置：iproute192.168.1.0255.255.255.010.0.0.1（指向總部網(wǎng)絡(luò)的下一跳為R1的廣域網(wǎng)IP）驗(yàn)證：通過showiproute命令查看路由表是否包含目標(biāo)網(wǎng)絡(luò)。四、數(shù)據(jù)庫系統(tǒng)7.題目：某電商數(shù)據(jù)庫有以下表結(jié)構(gòu)：用戶表（User）：UID（主鍵，INT），Uname（VARCHAR），RegTime（DATETIME）訂單表（Order）：OID（主鍵，INT），UID（外鍵，INT），Amount（DECIMAL），OrderTime（DATETIME）商品表（Goods）：GID（主鍵，INT），Gname（VARCHAR），Price（DECIMAL）訂單商品表（OrderGoods）：OID（外鍵，INT），GID（外鍵，INT），Quantity（INT），主鍵（OID,GID）查詢要求：統(tǒng)計(jì)2024年注冊(cè)的用戶中，訂單總金額超過1000元且購買過至少3種不同商品的用戶信息（UID，Uname，總金額，商品種類數(shù)）。答案及解析：步驟1：篩選2024年注冊(cè)的用戶（User.RegTimebetween'20240101'and'20241231'）。步驟2：關(guān)聯(lián)訂單表，計(jì)算每個(gè)用戶的總金額（sum(Order.Amount)）。步驟3：通過訂單商品表統(tǒng)計(jì)每個(gè)用戶購買的不同商品數(shù)（count(distinctOrderGoods.GID)）。步驟4：過濾總金額>1000且商品種類數(shù)>=3的用戶。SQL語句：```sqlSELECTu.UID,u.Uname,SUM(o.Amount)AS總金額,COUNT(DISTINCTog.GID)AS商品種類數(shù)FROMUseruJOINOrderoONu.UID=o.UIDJOINOrderGoodsogONo.OID=og.OIDWHEREu.RegTimeBETWEEN'20240101'AND'20241231'GROUPBYu.UID,u.UnameHAVINGSUM(o.Amount)>1000ANDCOUNT(DISTINCTog.GID)>=3;```8.題目：簡(jiǎn)述數(shù)據(jù)庫索引的優(yōu)缺點(diǎn)，以及B+樹索引與哈希索引的適用場(chǎng)景。答案及解析：優(yōu)點(diǎn)：加速數(shù)據(jù)查詢，減少全表掃描時(shí)間。確保數(shù)據(jù)唯一性（唯一索引）。優(yōu)化連接操作（JOIN時(shí)使用索引加速關(guān)聯(lián)）。缺點(diǎn)：增加存儲(chǔ)開銷（索引需要額外空間）。寫入、更新、刪除操作變慢（需維護(hù)索引結(jié)構(gòu)）。過度索引可能導(dǎo)致查詢優(yōu)化器選擇錯(cuò)誤索引，影響性能。B+樹索引適用場(chǎng)景：范圍查詢（如WHEREpriceBETWEEN100AND200）。排序查詢（ORDERBY、GROUPBY）。等值查詢（WHEREid=123）。適合大多數(shù)OLTP場(chǎng)景（在線事務(wù)處理）。哈希索引適用場(chǎng)景：等值查詢（僅支持=、IN等精確匹配）。鍵值對(duì)存儲(chǔ)場(chǎng)景（如緩存系統(tǒng)）。不支持范圍查詢和排序，適用于讀多寫少且查詢條件為等值的場(chǎng)景。五、綜合編程題9.題目：實(shí)現(xiàn)一個(gè)LRU（最近最少使用）緩存，要求支持以下操作：get(key)：獲取鍵對(duì)應(yīng)的值，若不存在返回1，存在則將該鍵標(biāo)記為最近使用。put(key,value)：插入或更新鍵值對(duì)，若緩存容量已滿，則刪除最久未使用的鍵值對(duì)。要求時(shí)間復(fù)雜度為O(1)。答案及解析：LRU緩存需用雙向鏈表維護(hù)訪問順序（頭部為最近使用，尾部為最久未使用），并用哈希表（字典）快速查找節(jié)點(diǎn)。雙向鏈表支持O(1)時(shí)間刪除節(jié)點(diǎn)和插入到頭部，哈希表支持O(1)時(shí)間查找節(jié)點(diǎn)。Python實(shí)現(xiàn)（使用OrderedDict簡(jiǎn)化，但需手動(dòng)實(shí)現(xiàn)以體現(xiàn)原理）：```pythonclassListNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.cap=capacityself.size=0self.cache={}虛擬頭尾節(jié)點(diǎn)self.head=ListNode()self.tail=ListNode()self.head.next=self.tailself.tail.prev=self.headdefmove_to_head(self,node):斷開原位置node.prev.next=node.nextnode.next.prev=node.prev插入頭部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedefadd_to_head(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedefremove_tail(self):node=self.tail.prevself.cache.pop(node.key)node.prev.next=self.tailself.tail.prev=node.prevreturnnodedefget(self,key:int)>int:ifkeynotinself.cache:return1node=self.cache[key]self.move_to_head(node)returnnode.valuedefput(self,key:int,value:int)>None:ifkeyinself.cache:node=self.cache[key]node.value=valueself.move_to_head(node)else:new_node=ListNode(key,value)self.cache[key]=new_nodeself.add_to_head(new_node)self.size+=1ifself.size>self.cap:self.remove_tail()self.size=1```10.題目：給定一個(gè)字符串s和一個(gè)整數(shù)k，找出s中包含至少k個(gè)不同字符的最長(zhǎng)子串的長(zhǎng)度。例如，s="abcabc",k=2，最長(zhǎng)子串為"abcab"（長(zhǎng)度5），包含a、b、c三個(gè)不同字符？不，示例錯(cuò)誤，正確示例應(yīng)為s="abcabc",k=2時(shí)，最長(zhǎng)子串是"abca"（長(zhǎng)度4，包含a、b、c？不，k=2要求至少2個(gè)不同字符，實(shí)際最長(zhǎng)應(yīng)為整個(gè)字符串，因?yàn)榘?個(gè)不同字符，滿足≥2。正確示例應(yīng)為s="aabbcc",k=2，最長(zhǎng)子串為"aabbc"（長(zhǎng)度5，包含a、b、c？不，需重新舉例）。正確示例：s="aaabbb",k=2，最長(zhǎng)子串是"aaabbb"（長(zhǎng)度6，包含a、b）。答案及解析：使用滑動(dòng)窗口+哈希表。維護(hù)左右指針，右指針擴(kuò)展窗口，當(dāng)窗口內(nèi)不同字符數(shù)≥k時(shí)，記錄長(zhǎng)度；當(dāng)不同字符數(shù)<k時(shí)，左指針右移。需注意要找的是至少k個(gè)不同字符的最長(zhǎng)子串，因此當(dāng)窗口內(nèi)字符數(shù)>k時(shí)，仍可能是候選。優(yōu)化方法：遍歷所有可能的不同字符數(shù)t（t從k到總不同字符數(shù)），對(duì)每個(gè)t求恰好t個(gè)不同字符的最長(zhǎng)子串，取最大值。但更高效的方式是直接維護(hù)滑動(dòng)窗口。代碼實(shí)現(xiàn)（Java）：```javapublicintlongestSubstring(Strings,intk){Map<Character,Integer>count=newHashMap<>();intleft=0,right=0,maxLen=0,unique=0;while(right<s.length()){charc=s.charAt(right);if(count.getOrDefault(c,0)==0)unique++;count.put(c,count.getOrDefault(c,0)+1);right++;while(unique>=k){maxLen=Math.max(maxLen,rightleft);charleftC=s.charAt(left);count.put(leftC,count.get(leftC)1);if(count.get(leftC)==0)unique;left++;}}returnmaxLen;}//上述代碼錯(cuò)誤，因?yàn)楫?dāng)unique>k時(shí)，可能存在更長(zhǎng)的子串。正確方法應(yīng)使用固定不同字符數(shù)的滑動(dòng)窗口，例如對(duì)于t從k到maxUnique，求恰好t個(gè)不同字符的最長(zhǎng)子串，再取最大值。//正確實(shí)現(xiàn)如下（以t為當(dāng)前目標(biāo)