PAGE共5頁第3頁系系專業(yè)班級姓名學號課程：算法設計與分析（啟用前保密）題號一二三四五總分得分一、選擇題（每題2分，共10分）1．下列說法正確的是（）。A．算法就是程序，程序就是算法。B．算法和程序都能直接在計算機上執(zhí)行C．算法能直接在計算機上執(zhí)行。D．程序能直接在計算機上執(zhí)行。2．對于函數(shù)f(n)=logn2，g(n)=logn+5，下列說法錯誤的是（）。A．f(n)=(g(n))B．f(n)=(g(n))C．f(n)=(g(n))D．以上說法不全對3．用貪心算法解決背包問題時的貪心策略是（）。A．重量小的物品優(yōu)先裝入背包。B．價值大的物品優(yōu)先裝入背包。C．單位重量的價值大的物品優(yōu)先裝入背包。D．單位重量的價值小的物品優(yōu)先裝入背包。4．回溯法求解n個頂點的圖的最大團問題時，算法的復雜度是（）。A．O(nmn)B.O(n2)C.O(n2n)C.O(2n)5．給定有序序列T[]={1,4,6,8,10,12}，現(xiàn)在要用二分搜索算法查找給定元素x=8是否出現(xiàn)在序列T中，元素x要和序列元素比較（）次能夠得出結論。A．5B．3C．4D．2二、填空題（每空2分，共30分）1．算法是由若干條指令組成的有窮序列，且滿足輸入、輸出、、和能行性共5條性質。2．用二分搜索算法在一個有序序列a[1:n]中查找某指定元素x是否存在。在查找的過程中，假定當前查找的范圍是a[low:high]，其中1≤low≤high≤n。分治策略中的分解操作是。3．用A[1:n]表示A1…An連乘，用動態(tài)規(guī)劃求解A[1:n]時，計算各子問題最優(yōu)值的復雜度是。4．回溯法算法框架中定義問題的解空間時，解的形式是；解空間結構的組織形式通常有、、。5．分支限界法中，從活結點表中選擇下一個擴展結點的不同方式導致了不同的分支限界法，最常見的有和。6．一般情況下，可將隨機化算法大致分成4類，分別是、、和蒙特卡羅算法。系專業(yè)班級姓名系專業(yè)班級姓名學號8．給定一個網絡G=(V,E)及其上的可行流flow，假設網絡G上的某條(v,w)的流量為95，容量為95，那么該邊對應于殘流網絡中反方向的一條邊，它的容量為。三、簡答題（每小題5分，共20分）1．簡述蒙特卡羅算法的特點并舉例說明。2．簡述分治法的基本思想。3．簡述哈夫曼編碼算法的思想。4．簡述動態(tài)規(guī)劃算法的基本要素。系系專業(yè)班級姓名學號1．（5分）采用合并排序的思想將給定序列T[1:9]={5,3,8,2,1,9,23,12,6}由小到大排序。(要求：只寫出首次分解得到兩個子問題的過程、遞歸的結果、子問題的解合并成原問題的解的過程)2．（5分）請用Kruskal算法求解下圖所示的最小生成樹（要求：寫出生成最小生成樹的過程）系專業(yè)班級姓名學號3．（9分）有0-1背包問題如下：n=4，c=12，P=（18，15，8，12），W=（10，2系專業(yè)班級姓名學號4．（11分）用增廣路算法找出下圖所示網絡的最大流，其中，頂點1為源點，頂點6為匯點，邊上的權為(cap,flow)。（要求：解答體現(xiàn)在網絡中標號過程和找到的增廣路，每一次增流后的可行流及最后的最大流。按頂點序號由小到大的原則選擇已標號未檢查的點）系系專業(yè)班級