【2020】【分析计算、算法分析】

关键字：

无相连通图、Prim算法最小生成树、哈希函数、线性探测法、平均查找长度

线性表删除、队列元素判断、二叉排序树

三、分析计算

1.对于一个带权连通无向图G，可以采用Prim算法构造出从某个顶点v出发的最小生成树，问该最小生成树是否一定包含从顶点v到其他所有顶点的最短路径。如果回答是，请予以证明；如果回答不是，请给出反例。

不一定；反例如下：图中从顶点0到顶点2的最短路径应是8，而不是10。

 2.设有一组关键字{32，13，49，24，38，21，4，12}，其哈希函数为：H（key）=key%7，采用开放地址法的线性探查法解决冲突，试在0~9的哈希地址空间中对该关键字序列构造哈希表，并求等概率下查找成功和查找不成功的平均查找长度。

1）模为7,0-6不成功次数进行计算

2）

查找成功:

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

查找失败：

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

四、算法分析

1.下面算法的功能：从线性表中删除自第i个元素开始的k个元素，其中线性表采用顺序存储结构存储。请在空白处填入正确的语句。

例子：

 2.下面算法的功能：判断两个队列是否“相等”（其中对应的数据均相等）的功能。请在空白处填入正确的语句。

//下面是队列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中。