算法設計與分析試題

一、概念題
1．隊列??? 2． 完全二叉樹??? 3．堆??????? 4．P類問題????? 5.NP問題

二、程序填空題
1．寬度優先圖周游算法
procedure bft(g，n)
????? ／／g的寬度優先周游／／
????????? declare visited(n)
????????? for i?1 to n do? ／／將所有結點標記為未訪問／／
??????????????????? ⑴????????
????????? repeat
????????? for i<--1 to n do? ／／反復調用bfs／／
??????????? if visited(i)＝0 then????? ⑵????????? endif
????????? repeat???
??????? end bft
2．找一個圖的所有m—著色方案?
???? procedure? mcoloring(k)
／／這是圖著色的一個遞歸回溯算法。圖g用它的布爾鄰接矩陣graPh(1：n，1：n)表示。它計算并打印出符合以下要求的全部解，把整數1，2，…，m分配給圖中各個結點且使相鄰近的結點的有不同的整數。k是下一個要著色結點的下標。／／
global integer? m，n，x(1：n)boolean? graPh(1；n，1：n)
integer k
loop? ／／產生對x(k)所有的合法賦值。／／
??? call nextvalue(k)。//將一種合法的顏色分配給x(k)／／
??? if???? ⑴???????? then? exit? endif? ／／沒有可用的顏色了／／???
???? if???? ⑵??????
????? then print(x)? ／／至多用了m種顏色分配給n個結點／／??
???? else call? mcoloring ??? endif
??? repeat
??? end mcoloring
算法設計與分析作業
問答題
1.算法的重要的5個特征是什么？
2.解釋貪心法的基本思想，并用貪心法解決如下背包問題。
背包問題：n=4,M=50,
(p1,p2,p3,p4)=(15,10,25,18), (w1,w2,w3,w4)=(20,15,15,20)
3. 請用Prim方法求下圖所示的最小生成樹。（請寫出該方法的基本思想和主要中間過程）。?

4.求三角形面積：給出三角形的三個邊長為a，b，c，求三角形的面積。
5. 猜名次：五個學生A、B、C、D、E參加某一項比賽。甲、乙兩人在猜測比賽的結果。甲猜的名次順序為A、B、C、D、E，結果沒有猜中任何一個學生的名次，也沒有猜中任何一對相鄰名次（所謂一對相鄰名次，是指其中一對選手在名次上鄰接。例如１與２，或者２與３ 等）。乙猜的名次順序為D、A、E、C、B，結果猜中了兩個學生的名次，并猜對了兩對學生名次是相鄰的。問比賽結果如何？答案為：E、D、A、C、B。乙猜對C、B為最后兩名，兩對 相鄰為（D、A）、（C、B））。

提示：設五名選手A、B、C、D、E的編號分別為1、2、3、4、5。用五個變量c1、c2、c3、 c4、c5標記第一名至第五名。算法仍用窮盡法。其中處理相鄰問題用一個兩位數表示，即DA、AE、EC、CB分別用41、15、53、32表示，并按兩位數比較判斷相鄰問題。