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

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

　　(一)Asymptotics & Recurrences

　　eg1：通過(guò)增加增長(zhǎng)的順序來(lái)對(duì)以下功能進(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：找到一個(gè)遞歸T (n) = T(n/3)+ T(2n/3)+ Θ(n)的解決方案。

　　eg3：找到以下遞歸式的漸近解。用Θ符號(hào)來(lái)表達(dá)你的答案，并給出一個(gè)簡(jiǎn)短的理由。

　　(二)True/False

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

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

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

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

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

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

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

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

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

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

　　二、真題答案&思路分析

　　(一)

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

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

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

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

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

　　(二)

　　eg1：F

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

　　eg2：T

　　eg3：F

　　找到下一個(gè)最小的元素，即前身，可能需要沿著樹(shù)的高度向下移動(dòng)，使運(yùn)行時(shí)間為O (h)。

　　eg4：T

　　eg5：F

　　計(jì)算排序是穩(wěn)定的。但是，它并不到位，因?yàn)槲覀儽仨汄v出額外的空間來(lái)存儲(chǔ)各種元素的計(jì)數(shù)。這個(gè)空間需求會(huì)隨著輸入的大小的增加而增加。此外，我們必須做一個(gè)單獨(dú)的輸出數(shù)組來(lái)使用計(jì)數(shù)排序產(chǎn)生答案。

　　eg6：F

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

　　eg7：F

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

　　eg8：F

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

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