4. 具有n個(gè)頂點(diǎn)的有向圖最多有 n(n-1) 條邊，具有n個(gè)頂點(diǎn)的無向圖最多有 n(n-1)/2 邊。?

5. 對n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長度為? (n+1)/2

（1）HT存儲(chǔ)結(jié)構(gòu)的初態(tài)（2分）

節(jié)點(diǎn) Weight paremt lchild rchild

1 20 0 0 0

2 40 0 0 0

3 50 0 0 0

4 70 0 0 0

5 60 0 0 0

6 110 0 0 0

7 180 0 0 0

（2）HT存儲(chǔ)結(jié)構(gòu)的終態(tài)（2分）

節(jié)點(diǎn) Weight paremt lchild rchild

1 20 5 0 0

2 40 5 0 0

3 50 6 0 0

4 70 7 0 0

5 60 6 1 2

6 110 7 3 5

7 180 0 4 6

三，畫曼哈頓

（4）帶權(quán)路徑長度

WPL=70*1+50*2+20*3+40*3=350

根據(jù)上述存儲(chǔ)結(jié)構(gòu)，請給出：

（1）????? 從頂點(diǎn)C出發(fā)按廣度優(yōu)先遍歷的結(jié)果（2分）

CFBECA

（2）從頂點(diǎn)C出發(fā)按深度優(yōu)先遍歷的結(jié)果（3分）

?????? CFEABD

6．已知有向圖如下圖所示，請給出：

（1）鄰接矩陣

（2）鄰接表

（3）最小生成樹

（4）普里姆（ Prim）算法，加入頂點(diǎn)的順序

ACFDBE

（5）按克魯斯卡爾（Kruskal）算法，加入邊的順序

ACDFBE

?

12，2，16，30，28，10，16*，20，6，18

①??? ?直接插入排序

第一趟：[2,]12, 16，30，28，10，16*，20，6，18

第二趟：[2,12, ]16，30，28，10，16*，20，6，18

第三趟：[2,12, 16，]30，28，10，16*，20，6，18

第四趟：[2,12, 16，28，]30，10，16*，20，6，18

第五趟：[2, 10，12, 16，28，]30，16*，20，6，18

第六趟：[2, 10，12, 16，16*，]28，30，20，6，18

第七趟：[2, 10，12, 16，16*，20，]28，30，6，18

第八趟：[2, 6，10，12, 16，16*，20，28，]30，18

第九趟：[2, 6，10，12, 16，16*，18，20，28，]30

②??? ?冒泡排序

第一趟：2，12，16，28，10，16*，20， 6，18，[30]

第二趟：2，12，16，10，16*，20， 6，18，[28，30]

第三趟：2，12，10，16，16*， 6，18，[20，28，30]

第四趟：2，10，12，16， 6，16*，[18，20，28，30]

第五趟：2，10，12， 6，16，[16*，18，20，28，30]

第六趟：2，10， 6，12，[16，16*，18，20，28，30]

第七趟：2， 6，10，[12，16，16*，18，20，28，30]

第八趟：2， 6，[10，12，16，16*，18，20，28，30]

③ 簡單選擇排序

12，2，16，30，28，10，16*，20，6，18

第一趟：[2，12，16，30，28，10，16*，20，6，18

第二趟：[2，6，]16，30，28，10，16*，20，12，18

第三趟：[2，6，10，]30，28，16，16*，20，12，18

第四趟：[2，6，10，12，]28，16，16*，20，30，18

第五趟：[2，6，10，12，16，]28，16*，20，30，18

第六趟：[2，6，10，12，16，16*，]28，20，30，18

第七趟：[2，6，10，12，16，16*，18，]20，30，28

第八趟：[2，6，10，12，16，16*，18，20，]30，28

第九趟：[2，6，10，12，16，16*，18，20，28，30

?