2025年全國(guó)高校計(jì)算機(jī)專業(yè)學(xué)生面試指南及模擬題一、編程題（共5題，每題10分）題目1題目描述：實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)整數(shù)數(shù)組，返回該數(shù)組的中位數(shù)。假設(shè)數(shù)組長(zhǎng)度為奇數(shù)，中位數(shù)為排序后位于中間的數(shù)；若為偶數(shù)，中位數(shù)為中間兩個(gè)數(shù)的平均值。示例：輸入：`[3,1,2]`輸出：`2`輸入：`[1,2,3,4]`輸出：`2.5`代碼要求：-使用Python或C++實(shí)現(xiàn)-時(shí)間復(fù)雜度不超過O(nlogn)-考慮邊界條件（空數(shù)組、單元素?cái)?shù)組等）題目2題目描述：給定一個(gè)二叉樹，判斷其是否為平衡二叉樹。平衡二叉樹的定義是：對(duì)于任意節(jié)點(diǎn)，其左右子樹的高度差不超過1。示例：輸入樹：3/\920/\157輸出：True代碼要求：-使用任意語(yǔ)言實(shí)現(xiàn)-需要定義二叉樹節(jié)點(diǎn)結(jié)構(gòu)-時(shí)間復(fù)雜度不超過O(n)題目3題目描述：實(shí)現(xiàn)一個(gè)LRU（最近最少使用）緩存，支持get和put操作。緩存容量為固定值，當(dāng)緩存滿時(shí)，需要淘汰最久未使用的元素。示例：LRUCachecapacity=2put(1,1)//緩存是{1=1}put(2,2)//緩存是{1=1,2=2}get(1)//返回1put(3,3)//去除鍵2，緩存是{1=1,3=3}get(2)//返回-1(未找到)代碼要求：-使用哈希表和雙向鏈表實(shí)現(xiàn)-get和put操作時(shí)間復(fù)雜度為O(1)題目4題目描述：給定一個(gè)字符串，找到其中不重復(fù)的最長(zhǎng)子串的長(zhǎng)度。例如，輸入"abcabcbb"，輸出"abcbb"的長(zhǎng)度3。代碼要求：-使用Python或Java實(shí)現(xiàn)-時(shí)間復(fù)雜度為O(n)-需要考慮所有邊界情況題目5題目描述：實(shí)現(xiàn)一個(gè)二叉搜索樹（BST）的迭代后序遍歷。不使用遞歸或棧，可以使用Morris遍歷或其他方法。示例：輸入樹：4/\26/\/\1357輸出：1,3,2,5,6,7代碼要求：-使用任意語(yǔ)言實(shí)現(xiàn)-不能使用遞歸或顯式棧二、算法題（共5題，每題10分）題目1題目描述：給定一個(gè)正整數(shù)n，判斷其是否為完全平方數(shù)。不能使用內(nèi)置函數(shù)，需自己實(shí)現(xiàn)算法。示例：輸入：`16`輸出：`True`輸入：`14`輸出：`False`要求：-時(shí)間復(fù)雜度O(√n)-考慮n=0和n=1的特殊情況題目2題目描述：實(shí)現(xiàn)快速排序算法，要求不使用遞歸，使用迭代方式實(shí)現(xiàn)。示例：輸入：`[3,1,4,1,5,9,2,6,5,3,5]`輸出：`[1,1,2,3,3,4,5,5,5,6,9]`要求：-需要明確pivot的選擇策略-考慮原始數(shù)組已排序或完全隨機(jī)的情況題目3題目描述：給定兩個(gè)字符串s1和s2，找到它們的最長(zhǎng)公共子序列（LCS）的長(zhǎng)度。子序列不要求連續(xù)。示例：輸入：`s1="abcde"`,`s2="ace"`輸出：`3`（"ace"）要求：-使用動(dòng)態(tài)規(guī)劃方法-時(shí)間復(fù)雜度O(mn)，m和n為字符串長(zhǎng)度題目4題目描述：實(shí)現(xiàn)一個(gè)函數(shù)，輸入一個(gè)整數(shù)數(shù)組，返回該數(shù)組中的最長(zhǎng)連續(xù)遞增子序列的長(zhǎng)度。示例：輸入：`[1,3,5,4,7]`輸出：`3`（"1,3,5"或"4,7"）要求：-時(shí)間復(fù)雜度O(n)-考慮數(shù)組全遞增或全遞減的情況題目5題目描述：實(shí)現(xiàn)二分查找算法，要求在目標(biāo)值不存在時(shí)，返回最接近目標(biāo)值的元素位置。示例：輸入：`nums=[1,2,4,5,6,8]`,`target=7`輸出：`4`（值為8的位置）要求：-需要處理數(shù)組為空、所有元素小于target、所有元素大于target的情況三、系統(tǒng)設(shè)計(jì)題（共3題，每題15分）題目1題目描述：設(shè)計(jì)一個(gè)簡(jiǎn)單的微博系統(tǒng)，需要支持以下功能：1.用戶發(fā)布微博（限制長(zhǎng)度200字）2.用戶關(guān)注其他用戶3.用戶獲取自己關(guān)注的人的最新微博（時(shí)間復(fù)雜度要求O(1)的查看操作）4.系統(tǒng)需要支持至少1000個(gè)并發(fā)用戶要求：-說明系統(tǒng)架構(gòu)-選擇合適的數(shù)據(jù)結(jié)構(gòu)-考慮高并發(fā)解決方案題目2題目描述：設(shè)計(jì)一個(gè)短鏈接系統(tǒng)，要求：1.將長(zhǎng)URL轉(zhuǎn)換為短URL（如/abcd）2.通過短URL能反查到原始URL3.系統(tǒng)需要支持每天1億次的訪問量4.短鏈接需要具有一定的隨機(jī)性，避免沖突要求：-說明URL編碼方案-設(shè)計(jì)數(shù)據(jù)庫(kù)表結(jié)構(gòu)-考慮分布式部署方案題目3題目描述：設(shè)計(jì)一個(gè)實(shí)時(shí)推薦系統(tǒng)，場(chǎng)景為音樂播放平臺(tái)，要求：1.用戶播放歌曲后，系統(tǒng)需要實(shí)時(shí)推薦相似歌曲2.推薦算法需要考慮用戶歷史行為和歌曲特征3.系統(tǒng)需要支持至少100萬(wàn)用戶，每天處理10億次播放記錄4.推薦結(jié)果需要在2秒內(nèi)返回要求：-說明推薦算法原理-設(shè)計(jì)數(shù)據(jù)存儲(chǔ)方案-考慮系統(tǒng)性能優(yōu)化措施四、數(shù)據(jù)庫(kù)題（共3題，每題10分）題目1題目描述：設(shè)計(jì)一個(gè)圖書借閱系統(tǒng)數(shù)據(jù)庫(kù)，包含以下表：1.用戶表（用戶ID、姓名、電話）2.圖書表（圖書ID、書名、作者、庫(kù)存）3.借閱表（借閱ID、用戶ID、圖書ID、借閱時(shí)間、應(yīng)還時(shí)間、實(shí)際還書時(shí)間）要求：-定義各表的主鍵和外鍵-編寫SQL查詢：-查詢當(dāng)前借閱數(shù)量最多的前5名用戶-查詢所有已逾期未還的圖書題目2題目描述：假設(shè)已經(jīng)存在以下SQL查詢：sqlSELECTbook_name,COUNT(*)asborrow_countFROMbooksbJOINborrow_recordsbrONb.book_id=br.book_idGROUPBYbook_nameORDERBYborrow_countDESCLIMIT10;請(qǐng)解釋這條查詢的執(zhí)行過程，并說明如何優(yōu)化這條查詢的性能。要求：-分析查詢的JOIN操作-提出索引優(yōu)化建議-考慮數(shù)據(jù)庫(kù)分區(qū)方案題目3題目描述：設(shè)計(jì)一個(gè)訂單系統(tǒng)數(shù)據(jù)庫(kù)，包含訂單表和訂單明細(xì)表，要求：1.訂單表有主鍵和創(chuàng)建時(shí)間2.訂單明細(xì)表有外鍵關(guān)聯(lián)訂單表，包含商品ID和數(shù)量3.需要支持查詢某個(gè)時(shí)間范圍內(nèi)所有訂單的總金額要求：-編寫SQL查詢實(shí)現(xiàn)上述功能-說明如何處理高并發(fā)寫入場(chǎng)景-提出數(shù)據(jù)庫(kù)事務(wù)隔離級(jí)別建議五、系統(tǒng)設(shè)計(jì)題答案題目1答案系統(tǒng)架構(gòu)：采用微服務(wù)架構(gòu)，分為：1.API網(wǎng)關(guān)：處理所有前端請(qǐng)求，進(jìn)行路由轉(zhuǎn)發(fā)2.用戶服務(wù)：存儲(chǔ)用戶信息，實(shí)現(xiàn)關(guān)注功能3.微博服務(wù)：存儲(chǔ)微博內(nèi)容，支持發(fā)布和獲取操作4.緩存服務(wù)：Redis緩存最新微博，提高讀取性能5.消息隊(duì)列：Kafka異步處理關(guān)注關(guān)系變更數(shù)據(jù)結(jié)構(gòu)：-用戶表：用戶ID（主鍵）、用戶名、密碼（加密存儲(chǔ)）-關(guān)注關(guān)系：自增ID（主鍵）、用戶ID（外鍵）、被關(guān)注用戶ID（外鍵）-微博表：微博ID（主鍵）、用戶ID（外鍵）、內(nèi)容、發(fā)布時(shí)間-緩存：使用Redis存儲(chǔ)用戶關(guān)注的人的最新微博ID列表高并發(fā)方案：-API網(wǎng)關(guān)使用Nginx進(jìn)行負(fù)載均衡-用戶服務(wù)采用分庫(kù)分表（按用戶ID哈希）-微博服務(wù)使用RedisCluster作為分布式緩存-消息隊(duì)列異步處理關(guān)注關(guān)系變更，減輕微博服務(wù)壓力題目2答案URL編碼方案：采用62進(jìn)制編碼（a-z,A-Z,0-9），將長(zhǎng)URL轉(zhuǎn)換為6位短碼-原理：將長(zhǎng)URL的MD5值進(jìn)行Base62編碼-優(yōu)點(diǎn)：隨機(jī)性好，沖突概率低（約1/62^6）數(shù)據(jù)庫(kù)表結(jié)構(gòu)：sqlCREATETABLEshort_links(short_codeVARCHAR(6)PRIMARYKEY,--短碼，唯一long_urlVARCHAR(2048)NOTNULL,--長(zhǎng)URLcreated_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);分布式部署方案：-使用Consul進(jìn)行服務(wù)發(fā)現(xiàn)-關(guān)鍵字段（short_code）使用RedisCluster保證高可用-采用雪崩算法生成短碼，避免沖突-前端設(shè)置CDN加速短鏈接解析題目3答案推薦算法原理：-協(xié)同過濾：基于用戶歷史播放記錄，計(jì)算用戶相似度-內(nèi)容推薦：分析歌曲特征（流派、節(jié)奏等）進(jìn)行相似度匹配-混合推薦：結(jié)合用戶實(shí)時(shí)行為和內(nèi)容相似度，使用加權(quán)算法數(shù)據(jù)存儲(chǔ)方案：-用戶行為日志：HBase存儲(chǔ)原始播放記錄，支持快速查詢-用戶畫像：Elasticsearch索引用戶標(biāo)簽和歌曲特征-推薦結(jié)果：Redis緩存熱門推薦，Tair存儲(chǔ)個(gè)性化推薦性能優(yōu)化措施：-使用Flink實(shí)時(shí)計(jì)算用戶行為-推薦引擎采用分布式計(jì)算（SparkMLlib）-對(duì)熱門歌曲使用本地緩存，冷啟動(dòng)歌曲走遠(yuǎn)程緩存-推薦接口設(shè)置異步調(diào)用，通過消息隊(duì)列通知前端六、數(shù)據(jù)庫(kù)題答案題目1答案表結(jié)構(gòu)定義：sqlCREATETABLEusers(user_idINTAUTO_INCREMENTPRIMARYKEY,nameVARCHAR(50)NOTNULL,phoneVARCHAR(20)UNIQUENOTNULL);CREATETABLEbooks(book_idINTAUTO_INCREMENTPRIMARYKEY,book_nameVARCHAR(100)NOTNULL,authorVARCHAR(50),stockINTDEFAULT0);CREATETABLEborrow_records(borrow_idINTAUTO_INCREMENTPRIMARYKEY,user_idINT,book_idINT,borrow_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,due_timeDATE,return_timeDATE,FOREIGNKEY(user_id)REFERENCESusers(user_id),FOREIGNKEY(book_id)REFERENCESbooks(book_id));SQL查詢：sql--查詢當(dāng)前借閱數(shù)量最多的前5名用戶SELECT,COUNT(br.borrow_id)asborrow_countFROMusersuJOINborrow_recordsbrONu.user_id=br.user_idWHEREbr.return_timeISNULLGROUPBYu.user_idORDERBYborrow_countDESCLIMIT5;--查詢所有已逾期未還的圖書SELECTb.book_nameFROMbooksbJOINborrow_recordsbrONb.book_id=br.book_idWHEREbr.return_timeISNULLANDbr.due_time<CURDATE();題目2答案查詢執(zhí)行過程分析：1.JOIN操作：將books表和borrow_records表通過book_id進(jìn)行連接2.GROUPBY：按book_name分組，統(tǒng)計(jì)每個(gè)書名的借閱次數(shù)3.ORDERBY：按借閱次數(shù)降序排列4.LIMIT10：取前10個(gè)結(jié)果性能優(yōu)化建議：1.索引優(yōu)化：-books表的book_id加索引（已自動(dòng)創(chuàng)建）-borrow_records表的book_id加索引-borrow_records表的return_time加索引（用于篩選當(dāng)前借閱）2.查詢優(yōu)化：sqlSELECTbook_name,COUNT(*)asborrow_countFROMbooksbJOINborrow_recordsbrONb.book_id=br.book_idWHEREbr.return_timeISNULLGROUPBYbook_nameORDERBYborrow_countDESCLIMIT10;-增加`br.return_timeISNULL`篩選條件，減少JOIN數(shù)據(jù)量數(shù)據(jù)庫(kù)分區(qū)方案：-對(duì)borrow_records表按時(shí)間范圍分區(qū)（如按月分區(qū)）-對(duì)books表按作者分區(qū)（如果作者數(shù)量巨大）-使用分區(qū)裁剪技術(shù)，只掃描需要的分區(qū)題目3答案表結(jié)構(gòu)定義：sqlCREATETABLEorders(order_idBIGINTAUTO_INCREMENTPRIMARYKEY,order_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP,user_idINT);CREATETABLEorder_details(detail_idBIGINTAUTO_INCREMENTPRIMARYKEY,order_idBIGINT,product_idINT,quantityINT,priceDECIMAL(10,2),FOREIGNKEY(order_id)REFERENCESorders(order_id));SQL查詢：sqlSELECTSUM(od.quantity*od.price)astotal_amountFROMordersoJOINorder_detailsodONo.order_id=od.order_idWH