算法設(shè)計(jì)與分析試題

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

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

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

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