算法是計算機(jī)編程當(dāng)中很重要的一個內(nèi)容，但它同時也是令很多同學(xué)感到比較有挑戰(zhàn)的部分。今天我們主要給大家分享一些本科階段的算法真題和答案解析，有需要的小伙伴們，建議收藏起來噢，或許會對你的算法作業(yè)和考試有一定的幫助。

一、算法真題(解題思路題目最后)

(一)Asymptotics & Recurrences

eg1：通過增加增長的順序來對以下功能進(jìn)行排序。即，找到滿足g1 = O(g2)、g2 = O(g3)、g3 = O(g4)、g4 = O(g5)、g5 = O(g6)、g6 = O(g7)、g1、g8的任意配置g1、g2、g3、g4)、g5、g6、g68、g7)、g7 = O(g8)。

eg2：找到一個遞歸T (n) = T(n/3)+ T(2n/3)+ Θ(n)的解決方案。

eg3：找到以下遞歸式的漸近解。用Θ符號來表達(dá)你的答案，并給出一個簡短的理由。

(二)True/False

判斷題，你認(rèn)為下面的表述是T正確還是F錯誤?

eg1：二進(jìn)制插入排序(使用二進(jìn)制搜索來查找每個插入點的插入排序)需要O(n log n)總操作。

eg2：在合并排序執(zhí)行樹中，在樹的每個級別上完成的工作量大致相同。

eg3：在BST中，我們可以在O (1)時間內(nèi)找到給定元素的下一個最小元素。

eg4：在AVL樹中，在插入操作期間，最多需要兩個旋轉(zhuǎn)。

eg5：計數(shù)排序是一種穩(wěn)定的、就地的排序算法。

eg6：在最小堆中，任何元素的下一個最大元素都可以在O(log n)時間中找到。

eg7：乘法滿足簡單的一致哈希假設(shè)。

eg8：雙哈希滿足一致哈希假設(shè)。

eg9：python生成器可用于迭代具有O (1)內(nèi)存的潛在無限可數(shù)集。

二、真題答案&思路分析

(一)

eg1：f1(n),f5(n),f3(n),f8(n),f7(n),f6(n),f4(n),f2(n).

分析：我們計算這個問題的分?jǐn)?shù)為ROUND(10·L-1/N-1)，其中N是函數(shù)的數(shù)量(這個例子的N=8)，L是我們的解和學(xué)生的答案之間的最長公共子序列的長度。最長公共子序列背后的直覺是，我們想從學(xué)生的答案中剔除盡可能少的函數(shù)，這樣剩下的函數(shù)將被正確地排序。誰說6.006歲的員工并不好?我們使用L?1N1來規(guī)范化分?jǐn)?shù)，因為一個完全錯誤的答案仍然會使?與正確的答案共享一個長度為1的共同子序列。最長的公共子序列可以使用動態(tài)編程來計算，這將在學(xué)期末的6.006中教授。

eg2：繪制遞歸樹。在每一層上，做Θ(n)工作。級別數(shù)是log3/2 n = Θ(lg n)，所以猜測T (n) = Θ(n lg n)，并使用替代方法來驗證猜測。

eg3：T(n) = Θ(log n).

分析：為了看到這一點，請注意，如果我們用T (n)不斷替換T (n)的公式來擴(kuò)展T (n)，我們得到：

(二)

eg1：F

雖然二進(jìn)制插入排序提高了為下一個被插入的元素找到正確位置所需的時間，但它可能仍然需要O (n)個時間來執(zhí)行所需的交換時間。這導(dǎo)致了一個O(n2)運行時間，與插入排序相同。

eg2：T

eg3：F

找到下一個最小的元素，即前身，可能需要沿著樹的高度向下移動，使運行時間為O (h)。

eg4：T

eg5：F

計算排序是穩(wěn)定的。但是，它并不到位，因為我們必須騰出額外的空間來存儲各種元素的計數(shù)。這個空間需求會隨著輸入的大小的增加而增加。此外，我們必須做一個單獨的輸出數(shù)組來使用計數(shù)排序產(chǎn)生答案。

eg6：F

最小堆不能提供O(log n)時間內(nèi)的下一個最大元素。要找到下一個最大的元素，我們需要做一個線性的，O (n)，搜索通過堆的數(shù)組。

eg7：F

我們并不知道滿足簡單均勻哈希假設(shè)的哈希函數(shù)。

eg8：F

這些筆記指出，雙哈希關(guān)系“很接近”。雙哈希只提供了n2個排列，而不是n!。

eg9：T
以上就是本科階段的算法真題講解，希望對大家有所幫助。課程學(xué)習(xí)中遇到難題，歡迎咨詢留求藝的專業(yè)老師!