期末的硝煙,最終在肅殺的考場(chǎng)里凝聚成冰冷的試卷。南江市夏日的熱浪被厚重的窗簾隔絕在外,階梯教室內(nèi),只有頭頂白熾燈管發(fā)出的嗡鳴,以及筆尖劃過(guò)紙張的沙沙聲,如同無(wú)數(shù)只蠶在啃噬著名為“時(shí)間”的桑葉。空氣凝滯,彌漫著消毒水味、紙張油墨味,以及更濃重的、名為“緊張”的無(wú)形壓力。
林默坐在自己的位置上,深吸一口氣,試圖平復(fù)擂鼓般的心跳。面前攤開(kāi)的,正是他最畏懼的——《數(shù)據(jù)結(jié)構(gòu)與算法》期末試卷。
目光掃過(guò)試卷,心猛地沉入谷底。
一、選擇題(略)
二、簡(jiǎn)答題:
1.簡(jiǎn)述二叉搜索樹(shù)的性質(zhì)。刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的BST節(jié)點(diǎn),詳細(xì)描述操作步驟及指針變化。
2.對(duì)比深度優(yōu)先搜索和廣度優(yōu)先搜索在圖遍歷中的特點(diǎn)、適用場(chǎng)景及實(shí)現(xiàn)方式(棧/隊(duì)列)。
三、算法設(shè)計(jì)與分析:
1.給定一個(gè)非負(fù)整數(shù)數(shù)組,設(shè)計(jì)一個(gè)高效算法找到和最大的連續(xù)子數(shù)組,描述算法思想(貪心或動(dòng)態(tài)規(guī)劃),寫(xiě)出偽代碼,并分析時(shí)間復(fù)雜度。
2.實(shí)現(xiàn)一個(gè)非遞歸的二叉樹(shù)中序遍歷算法(使用棧),寫(xiě)出C語(yǔ)言代碼片段(需定義樹(shù)節(jié)點(diǎn)結(jié)構(gòu))。
四、綜合應(yīng)用題:
利用并查集數(shù)據(jù)結(jié)構(gòu),解決一個(gè)關(guān)于網(wǎng)絡(luò)連通性的問(wèn)題(具體描述略),要求寫(xiě)出并查集核心操作的優(yōu)化實(shí)現(xiàn)(路徑壓縮/按秩合并),并分析其在問(wèn)題中的效率。
每一道題都像一把冰冷的匕首,精準(zhǔn)地刺向林默知識(shí)體系中最薄弱的部分。二叉搜索樹(shù)刪除的指針操作?他腦海中立刻浮現(xiàn)出自己上機(jī)實(shí)驗(yàn)時(shí)反復(fù)出現(xiàn)的“Segmentationfault”!DFS和BFS的棧隊(duì)列實(shí)現(xiàn)?遞歸他尚且磕磕絆絆,非遞歸更是噩夢(mèng)!最大子數(shù)組和?動(dòng)態(tài)規(guī)劃?他只在概念上勉強(qiáng)理解!非遞歸中序遍歷?指針在棧和樹(shù)節(jié)點(diǎn)間飛舞,想想就頭大!并查集?路徑壓縮?按秩合并?這些趙教授后期加速講過(guò)的內(nèi)容,在他腦中只是一團(tuán)模糊的概念!
汗水瞬間浸濕了后背。林默強(qiáng)迫自己冷靜,從相對(duì)熟悉的選擇題開(kāi)始。幾道基礎(chǔ)概念題尚能應(yīng)付,但涉及稍深的理解或邊界情況,他便開(kāi)始猶豫不決。時(shí)間在筆尖的遲疑中飛速流逝。
翻到簡(jiǎn)答題,面對(duì)BST刪除操作,他努力回憶顧清嘉在圖書(shū)館指點(diǎn)過(guò)的關(guān)鍵——“刪除節(jié)點(diǎn)后,父節(jié)點(diǎn)指針需重置”。他咬著筆桿,在草稿紙上畫(huà)著歪歪扭扭的樹(shù),標(biāo)注著指針。刪除節(jié)點(diǎn)、找前驅(qū)/后繼、指針重指,每一步都如履薄冰,生怕一個(gè)指針指錯(cuò)就滿盤皆輸。描述寫(xiě)得磕磕絆絆,邏輯勉強(qiáng)通順,但細(xì)節(jié)處自己都感覺(jué)漏洞百出。
DFS和BFS的對(duì)比,他只能寫(xiě)出最基礎(chǔ)的特點(diǎn),實(shí)現(xiàn)方式也只是簡(jiǎn)單提及棧和隊(duì)列,對(duì)于具體的棧操作模擬遞歸、隊(duì)列如何管理待訪問(wèn)節(jié)點(diǎn)等細(xì)節(jié),根本無(wú)力深入。
最煎熬的是算法設(shè)計(jì)與分析部分。
最大子數(shù)組和:他隱約記得課上提過(guò)“動(dòng)態(tài)規(guī)劃”和“當(dāng)前和、最大和”的概念(Kadane算法),但具體狀態(tài)轉(zhuǎn)移方程和邊界條件完全模糊。他嘗試寫(xiě)了個(gè)暴力求解(O(n2))的思路,偽代碼寫(xiě)得極其簡(jiǎn)陋,時(shí)間復(fù)雜度分析也底氣不足。貪心?他連貪心策略怎么設(shè)計(jì)都無(wú)從下手。
非遞歸中序遍歷:這簡(jiǎn)直是酷刑!他對(duì)著題目要求,大腦一片空白。棧怎么初始化?指針current指向根節(jié)點(diǎn),然后呢?循環(huán)條件是什么?何時(shí)訪問(wèn)節(jié)點(diǎn)?何時(shí)壓棧?何時(shí)彈棧?指針如何移動(dòng)?每一步的指針變化都如同亂麻。他硬著頭皮寫(xiě)了幾行代碼,定義結(jié)構(gòu)體,初始化棧,然后卡住了。指針在current、棧頂元素、左孩子、右孩子之間瘋狂打轉(zhuǎn),邏輯混亂不堪。他絕望地涂改著,草稿紙上畫(huà)滿了箭頭和叉叉,代碼片段如同被轟炸過(guò)的戰(zhàn)場(chǎng),慘不忍睹。
就在林默對(duì)著中序遍歷的代碼抓狂,額頭上冷汗涔涔時(shí),一個(gè)輕微的椅子移動(dòng)聲在前方響起,在寂靜的考場(chǎng)里顯得格外清晰。
林默下意識(shí)地抬頭。
只見(jiàn)斜前方,顧清嘉已經(jīng)合上了筆帽。她面前的試卷整潔得不可思議,答題區(qū)域?qū)懙脻M滿當(dāng)當(dāng),字跡清晰工整,邏輯圖示(如果有)也畫(huà)得一絲不茍。她沒(méi)有絲毫的猶豫或檢查,直接站起身,拿起試卷和文具,步履平穩(wěn)地走向講臺(tái)。
監(jiān)考老師似乎早已習(xí)慣,平靜地接過(guò)她的試卷,快速翻看了一下,微微點(diǎn)了點(diǎn)頭。
整個(gè)考場(chǎng)的目光,如同被磁石吸引,瞬間聚焦在她身上!那些還在苦思冥想、抓耳撓腮、對(duì)著難題愁眉苦臉的同學(xué),眼中充滿了難以置信、羨慕、甚至一絲絕望。才開(kāi)考多久?一個(gè)小時(shí)?一個(gè)半小時(shí)?她竟然做完了?而且看起來(lái)如此從容,仿佛只是完成了一份課后練習(xí)!
王胖坐在林默不遠(yuǎn)處,嘴巴張得能塞進(jìn)一個(gè)雞蛋,眼神呆滯地看著顧清嘉的背影,手中的筆“啪嗒”一聲掉在桌上。
李濤也猛地抬起頭,鏡片后的眼睛死死盯著那張被老師收走的試卷,臉上是混合著震驚和不甘的復(fù)雜表情,握著筆的手指因?yàn)橛昧Χ腹?jié)發(fā)白。
張偉則倒吸一口涼氣,低聲爆了句粗口:“臥槽……牲口啊。”
顧清嘉對(duì)身后的目光和低語(yǔ)恍若未聞。她交完卷,沒(méi)有片刻停留,甚至沒(méi)有回頭看一眼考場(chǎng),便徑直走出了教室門。陽(yáng)光透過(guò)走廊的窗戶,在她離開(kāi)的背影上投下一道長(zhǎng)長(zhǎng)的影子,然后隨著教室門的關(guān)閉而消失。
她的離開(kāi),像一塊巨石投入本就壓抑的池塘,激起了更大的漣漪。考場(chǎng)里響起一片壓抑不住的、倒吸涼氣和竊竊私語(yǔ)的聲音。
“太快了吧……”
“這就是學(xué)神嗎…”
“我第一道大題還沒(méi)寫(xiě)完…”
“完了完了,她這么早交卷,題目肯定很難…”
監(jiān)考老師敲了敲桌子,嚴(yán)肅道:“安靜!集中注意力!抓緊時(shí)間答題!”
議論聲被強(qiáng)行壓下,但彌漫在空氣中的焦慮和挫敗感卻更加濃重了。顧清嘉的提前交卷,像一記無(wú)形的重錘,狠狠砸在了許多還在苦苦掙扎的學(xué)生心上,包括林默。
林默看著自己試卷上那道只寫(xiě)了個(gè)開(kāi)頭就陷入混亂的非遞歸中序遍歷題,再看看顧清嘉那已經(jīng)空空如也的座位,一股巨大的無(wú)力感和自我懷疑再次洶涌襲來(lái)。差距!赤裸裸的、令人絕望的差距!他還在泥沼中掙扎求生,而對(duì)方已經(jīng)輕松登岸,甚至不屑于回頭看一眼身后的戰(zhàn)場(chǎng)。
他用力掐了一下自己的大腿,疼痛讓他稍微清醒了一些。沮喪和自憐解決不了任何問(wèn)題!他深吸一口氣,強(qiáng)迫自己將目光從那個(gè)空座位收回,重新聚焦在自己慘不忍睹的試卷上。非遞歸遍歷實(shí)在搞不定,只能放棄,爭(zhēng)取在其他題目上多拿點(diǎn)分!他咬著牙,將最后的時(shí)間投入到并查集那道綜合題上,試圖回憶起路徑壓縮和按秩合并的模糊概念,在草稿紙上畫(huà)著集合合并的圖示,努力拼湊出一些合理的解釋。
考場(chǎng)的掛鐘指針無(wú)情地轉(zhuǎn)動(dòng)著。白熾燈冰冷的光線下,有人奮筆疾書(shū),有人抓耳撓腮,有人眼神空洞。顧清嘉留下的那個(gè)空座位,像一個(gè)沉默的坐標(biāo),無(wú)聲地標(biāo)注著這個(gè)考場(chǎng)里殘酷的天塹。林默在彌漫著汗味和焦慮的空氣里,繼續(xù)著他艱難而笨拙的跋涉,每一筆落下,都帶著沉重的不甘和拼盡全力的掙扎。
考場(chǎng)風(fēng)云,有人已乘風(fēng)而去,有人仍在風(fēng)雨飄搖中奮力劃槳。