word版可編輯-北京大學(xué)算法設(shè)計(jì)與分析課期末試題精心整理(編輯修改稿)
2025-04-20 05:11 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 A) 對(duì)于系數(shù)a，必須滿(mǎn)足a ≥ 1B) 對(duì)于系數(shù)b，必須滿(mǎn)足b 1C) 若對(duì)于常數(shù)ε 0，f(n)=O(nlogbaε) ，則T(n)=Θ(nlogba) D) 若f(n)=O(nlogba) ，則T(n)=Θ(nlogbalogn) 4． 下列哪些問(wèn)題不能用貪心法求解？ （ ）A) 霍夫曼編碼問(wèn)題 B) 單源最短路徑問(wèn)題C) 01背包問(wèn)題 D) 最小生成樹(shù)問(wèn)題5． 可合并堆上可以不包含下列哪個(gè)操作？ （ ）A) DECREASEKEY(H, x, k) B) UNION(H1, H2)C) INSERT(H, x) D) EXTRACTMIN(H)6． 不同堆上插入操作最差情形下的開(kāi)銷(xiāo)或平攤開(kāi)銷(xiāo)， （ ）對(duì)二叉堆、二項(xiàng)堆和斐波那契堆，下列選項(xiàng)中描述錯(cuò)誤的是？A) 二叉堆為Θ(lg n) B) 二項(xiàng)堆為O(lg n)C) 斐波那契堆為Θ(1) D) 三種堆的開(kāi)銷(xiāo)都是Θ(lg n)7． 關(guān)于網(wǎng)絡(luò)流的割，下列選項(xiàng)中錯(cuò)誤的是？ （ ）割(S,T)是流網(wǎng)絡(luò)G=(V,E)的一個(gè)劃分，其中s∈S, t∈T。如果 f 是G上的流，那么流經(jīng)割的凈流量為f(S,T)，割(S,T)上的容量定義為c(S,T) 。A) | f | ≤ c(S, T) B) f(S, T) = | f |C) f(s, Vs) = | f | D) f(Ss, V) = | f |8． 下列隨機(jī)算法一定有解但解不一定正確的是？ （ ）A) Sherwood B) LasVegas C) MonteCarlo D) 三者都不是9． 在快速排序算法中引入隨機(jī)過(guò)程的主要目的是什么？ （ ）A) 改善確定性算法
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1