關鍵字：

無相連通圖、Prim算法最小生成樹、哈希函數(shù)、線性探測法、平均查找長度

線性表刪除、隊列元素判斷、二叉排序樹

三、分析計算

1.對于一個帶權連通無向圖G，可以采用Prim算法構造出從某個頂點v出發(fā)的最小生成樹，問該最小生成樹是否一定包含從頂點v到其他所有頂點的最短路徑。如果回答是，請予以證明；如果回答不是，請給出反例。

不一定；反例如下：圖中從頂點0到頂點2的最短路徑應是8，而不是10。

?2.設有一組關鍵字{32，13，49，24，38，21，4，12}，其哈希函數(shù)為：H（key）=key%7，采用開放地址法的線性探查法解決沖突，試在0~9的哈希地址空間中對該關鍵字序列構造哈希表，并求等概率下查找成功和查找不成功的平均查找長度。

1）模為7,0-6不成功次數(shù)進行計算

2）

查找成功:

(1+2+1+1+3+1+4+4)/8=17/8

查找失?。?/p>

(3+2+1+7+6+5+4)/7=4

四、算法分析

1.下面算法的功能：從線性表中刪除自第i個元素開始的k個元素，其中線性表采用順序存儲結構存儲。請在空白處填入正確的語句。

例子：

?2.下面算法的功能：判斷兩個隊列是否“相等”（其中對應的數(shù)據(jù)均相等）的功能。請在空白處填入正確的語句。

//下面是隊列Queue的主要操作

int QueueEmpty(Queue Q);?? ??? ??? ??? ?? ? //判斷隊列空否，1為空，0為不空

int GetHead(Queue Q,ElemTypes &x);? ? //通過x返回對頭元素的值

void EnQueue(Queue &Q.ElemType x);? ? //將新元素x插入到隊列的隊尾

void DeQueue(Queue Q);? ? ?? ?????//從隊列中退出對頭元素

3.閱讀下面的代碼，試說明針對二叉排序樹操作算法的功能。

將長度為n的順序表A插入到二叉排序樹T中。?