（1）  画出该有向图 G
（2） 试利用 Dijkstra 算法求 G 中从顶点 a 到其他各顶点间的最短路径，并给出求解过程。 答：
（1）
 




（2）

终点
Dist    b    c    d    e    f    g    S
k=1    15
(a,b)    2
(a,c)    12
(a,d)                {a,c}
k=2    15
(a,b)        12
(a,d)    10
(a,c,e)    6
(a,c,f)        {a,c,f}
k=3    15
(a,b)        11
(a,c,f,d)    10
(a,c,e)        16
(a,c,f,g)    {a,c,f,e}
k=4    15
(a,b)        11
(a,c,f,d)            16
(a,c,f,g)    {a,c,f,e,d}
k=5    15
(a,b)                    14
(a,c,f,d,g)    {a,c,f,e,d,g}
k=6    15
(a,b)                        {a,c,f,e,d,g,b}

6.下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村 庄能使各村庄总体交通代价最小？
4

 
解： 该图的邻接矩阵如下：
0    13    ゥ    4   
13    0    1    5    5
A= ゥ    0    1    2
4    ゥ    1    2    0   
ゥ    6    3    0
利用 Floyd 算法可求得两顶点之间最短路径长度。最后求得：
 

0    13    16    4    18
12    0    11    8    5
A4 = 16    29    0    12    34
4    17    12    0    22
7    20    6    3    0
从 A4 中可求得每对村庄之间的最少交通代价。假设医院建在 i 村庄时，其他各村庄往返总 的交通代价如下所示：
医院建在村庄 0 时，各村庄往返总的交通代价为 12+16+4+7+13+16+4+18=90； 医院 建在村庄 1 时，各村庄往返总的交通代价为 13+29+17+20+12+11+8+5=115； 医院建
在村庄 2 时，各村庄往返总的交通代价为 16+11+12+6+16+29+12+34=136； 医院建在 村庄 3 时，各村庄往返总的交通代价为 4+8+12+3+4+17+12+22=82； 医院建在村庄 4 时，各村庄往返总的交通代价为 18+5+34+22+7+20+6+3=115。 显然，把医院建在村 庄 3 时总体交通代价最少。
（三）算法设计题

1.设计一个算法，求无向图 G（采用邻接表存储）的连通分量个数。 解法一：采用深度优 先遍历方法。算法如下：
void DFS(AGraph *G, int v)
{
ArcNode *p;
visited[v]=1;    //置已访问标记
prinf(”%d”,v);    //输出被访问顶点的编号
p=G->adjlist[v].firstarc;    //p 指向顶点 v 的第一条边的终结点
while (p!=NULL)
{
if (visited[p->adjvex]==0)    //若 p->adjvex 顶点未访问，递归访问它
DFS(G,p->adjvex);
p=p->nextarc;    //p 指向顶点 v 的下一条边的终结点
}
}
int ConnNum1(AGraph *G)    //求图 G 的连通分量
{
int i, num=0;
for (i=0; i<G->n; i++) visited[i]=0;
for (i=0; i<G->n; i++) if (visited[i]==0)
{
DFS(G,i);    //调用 DFS 算法
num++;
}
return(num);
 
}
解法二：采用广度优先遍历方法。算法如下：
void BFS(AGraph *G, int v)
{
ArcNode *p;
int Qu[MAXV]，front=0, rear=0;    //定义循环队列并初始化 int w,i;
for (i=0; i<G->n; i++)    visited[i]=0;    //访问标志数组初始化 prinf(”2%d”,v);        //输出被访问顶点的编号
visited[v]=1;    //置已访问标记 rear=(rear+1)%MAXV;
Qu[rear]=v;    //v 入队
while (front!=rear)    //若队列不空时循环
{
front=(front+1)%MAXV;
w=Qu[front];    //出队并赋予 w
p=G->adjlist[w].firstarc;    //找与顶点 w 邻接的第一个顶点
while (p!=NULL)
{
if (visited[p->adjvex]==0)    //若当前邻接顶点未被访问
{
printf(”%2d”, p->adjvex);    //访问相邻顶点
visited[p->adjvex]=1;    //置该顶点已被访问的标志
rear=(rear+1)%MAXV;    //该顶点入队 Qu[rear]= p->adjvex;
}
p=p->nextarc;    //找下一个邻接顶点
}
}
printf(”\n”);
}
int ConnNum2(AGraph *G)    //求图 G 的连通分量
{
int i, num=0;
for (i=0; i<G->n; i++) visited[i]=0;
for (i=0; i<G->n; i++) if (visited[i]==0)
{
BFS(G,i);    //调用 BFS 算法
num++;
}
return(num);
}
 
五、查找

大纲要求：

（一） 查找的基本概念
（二） 顺序查找法
（三） 折半查找法
（四） B-树
（五） 散列（Hash）表及其查找
（六） 查找算法的分析及应用 知识点：
1．线性表上的查找。对于顺序表采用顺序查找方法，逐个比较，顺序表设置了监视哨使 查 找效率大大提高。对于有序顺序表采用折半查找法，其判定树是唯一的。对于索引结 构， 采用索引顺序查找算法，此算法综合了上述两者的优点，既能较快速地查找，又 能适应 动态变化的要求。注意这三种查找的平均查找长度。掌握顺序查找和折半查找算 法的实现
，其中，折半查找还要特别注意适用条件以及其递归实现方法。
2． B-树是多路平衡外查找树，用于文件系统。要能手工模拟 B-树插入和删除关键字使 B-
树增高和降低，会推导 B-树的平均查找长度。
3．散列表的查找算法。基本思想是：根据当前待查找数据的特征，以记录关键字为自变 量
，设计一个散列函数，该函数对关键字进行转换后，其解释结果为待查的地址。熟练 掌握散列函数的设计，冲突解决方法的选择及冲突处理过程的描述。散列表中关键字的 查找只能用散列函数来计算，不能顺序查找，也不能折半查找。在闭散列法解决冲突的 情况下，元素删除也只能做标记，不能物理地删除。理想情况下，散列表的平均查找长 度是 O(1)，优于其他查找方法。

练习题：

（一）选择题：

1.        某顺序存储的表格中有 90000 个元素，已按关键字值额定升序排列，假定对每个元素 进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时， 平均比较次数约为（    C    ）
A．25000    B．30000
C．45000    D．90000
2. 适用于折半查找的表的存储方式及元素排列要求为( D ) A．链接方 式存储，元素无序    B．链接方式存储，元素有序 C．顺序方式存储，元素无序    D．顺序方式存储，元素有序
3.    散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数
是一对一的关系，则选择好的（    D    ）方法是散列文件的关键。
A. 散列函数        B. 除余法中的质数
C. 冲突处理        D. 散列函数和冲突处理
 
4.    每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函 数值对应结点的存储位置，该存储方式是（    D    ）存储方式
A. 顺序    B．链接
C．索引    D．散列
5.    如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可以采用（A ） 查找法。
A．分块    B. 顺序
C. 二分    D. 散列

（二）应用题

1. 设 散 列 表 的 长 度 为 13 ， 散 列 函 数 为 H(K)=K%13 ， 给 定 的 关 键 字 序 列 为 ：
19，14，23，01，68，20，84，27，55，11，10，79。试画出用线性探测再散列解决冲突 时所构成的散列表。并求等概率情况下这两种方法查找成功和查找不成功时的平均查找长 度。
答： 线性探测再散列的散列表
：
0    1    2    3    4    5    6    7    8    9    10    11    12

    14    1    68    27    55    19    20    84    79    23    11    10
    1    2    1    4    3    1    1    3    9    1    1    3

查找成功的平均长度为 ASL=1/12（1*6+2*1+3*3+4*1+9）=2.5 查找不 成功的平均长度为 ASL=1/13（1+2+3+4…….+13）=7



2．为什么说当装填因子非常接近 1 时，线性探查类似于顺序查找?为什么说当装填因子比 较小(比如 α=0.7 左右)时，散列查找的平均查找时间为 O(1)?
答：
当 α 非常接近 1 时，整个散列表几乎被装满。由于线性探查法在关键字同义时解决冲突的 办法是线性地向后查找，当整个表几乎装满时，它就很类似于顺序查找了。