第七章 图分析Word格式.docx
- 文档编号:986150
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:12
- 大小:350.56KB
第七章 图分析Word格式.docx
《第七章 图分析Word格式.docx》由会员分享,可在线阅读,更多相关《第七章 图分析Word格式.docx(12页珍藏版)》请在冰点文库上搜索。
(1)图的邻接矩阵为
7.9试列出题7.9图中全部可能的拓扑有序序列,并指出应用7.5.1节中算法TopologicalSort求得的是哪一个序列(注意:
应先确定其存储结构)。
StatusTopologicalSort(ALGraphG)
FindIndegree(G,indegree);
//对各顶点求入度
InitStack(S);
For(i=0;
i<
G.vexnum;
i++)//建0入度顶点栈S
If(!
Indegree[i])Push(S,i);
//入度为0者进栈
count=0;
//对输出顶点计数
while(!
StackEmpty(s)){
Pop(S,i);
printf(i,G.vertices[i].data);
++count;
//输出i号顶点并计数
for(p=G.vertices[i].firstarc;
p;
p=p->
nextarc){
k=p->
adjvex;
//对i号顶点的每个邻接点的入度减1
if(!
(--indegree[k]))Push(S,k);
//入度减为0,则入栈
}
if(count<
G.vexnum)returnERROR;
//该有向图有回路
elsereturnOK;
求得561234
7.11试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。
7.22③试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。
注意:
算法中涉及的图的基本操作必须在此存储结构上实现。
intvisited[MAXSIZE];
//指示顶点是否在当前路径上
intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if(i==j)return1;
//i就是j
else
visited[i]=1;
for(p=G.vertices[i].firstarc;
nextarc)
visited[k]&
&
exist_path(k,j))return1;
//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7.23③同7.22题要求。
试基于图的广度优先搜索策略写一算法。
intexist_path_BFS(ALGraphG,inti,intj)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
InitQueue(Q);
EnQueue(Q,i);
QueueEmpty(Q))
DeQueue(Q,u);
visited[u]=1;
if(k==j)return1;
visited[k])EnQueue(Q,k);
}//while
return0;
}//exist_path_BFS
第9章查找
9.2试分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找,以查关键字等于e,f和g的过程。
1)查找e的过程如下:
2)查找f的过程
3)查找g的过程
9.3画出对长度为10的有续表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。
9.9已知如下所示长度为12的表(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
(1)试按表中元素的顺序依次插入一查初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
(3)按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。
(1)求得的二叉排序树如下图所示:
在等概率情况下查找成功的平均查找长度为:
ASL成功=(1+2*2+3*3+4*3+5*2+6*1)/12=42/12=3.5
(2)分析:
对表中元素进行排序后,其实就变成了对长度为12的有序表进行折半查找了,那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。
所以可求出:
ASL成功=(1+2*2+4*3+5*4)/12=37/12
(3)平衡二叉树的构造过程
平衡二叉树为
9.21在地址空间为0~16的散列区中,对以下关键字序列构造两哈希表:
(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
(1)用线性探测开放定址法处理冲突;
(2)用链地址法处理。
并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。
设哈希函数为H(x)=i/2取整,其中i为关键字中第一个字母在字母表中的序号。
(1)因为:
H(Jan)=5;
H(Feb)=3;
H(Mar)=6;
H(Apr)=0;
H(May)=6;
H1(May)=7;
H(June)=5;
H1(June)=6;
H2(June)=7;
H3(June)=8
H(July)=5;
H1(July)=6;
H2(July)=7;
H3(July)=8;
H4(July)=9;
H(Aug)=0;
H1(Aug)=1
H(Sep)=9;
H1(Sep)=10
H(Oct)=7;
H1(Oct)=8;
H2(Oct)=9;
H3(Oct)=10;
H4(Oct)=11;
H(Nov)=7;
H1(Nov)=8;
H2(Nov)=9;
H3(Nov)=10;
H4(Nov)=11;
H5(Nov)=12;
H(Dec)=2
所以,用线性探测开放定址法处理冲突构造的哈希表如下图所示:
012345678910111213141516
Apr
Aug
Dec
Feb
Jan
Mar
May
June
July
Sep
Oct
Nov
Ci:
121111245256
并求得:
ASL成功=(1*5+2*3+4+5*2+6)/12=31/12
ASL不成功=(5+4+3+2+1+9+8+7+6+5+4+3+2+1)/14=60/14
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(2)用链地址法处理冲突构造的哈希表如下图所示:
^
并求得:
ASL成功=(1*7+2*4+3)/12=18/12
ASL不成功=(1*3+2*3+3)/14=12/14
9.25假设顺序表按关键字自大至小有序,试改写教科书9.1.1节中的顺序查找算法,将监视哨设在高下标端。
然后画出描述此查找过程的判定树,分别求出等概率下查找成功和不成功的平均查找长度。
(1)顺序表的存储结构描述:
Typedefstruct{
Keytypekey;
}Elemtype;
//记录类型;
typedefstruct{
Elemtype*elem;
intlength;
}SSTable;
//顺序表类型;
按要求所得算法如下:
intSearch(SSTableST,Keytypekey)
{ST.elem[ST.length].key=key;
for(i=0;
key<
ST.elem[i].key;
i++);
if(i==ST.length)return0;
elseif(key==ST.elem[i].key)returni;
elsereturn0;
}
(2)按此查找过程的判定树如下图所示:
(3)等概率下的查找成功与查找不成功的平均查找长度分别为:
、
ASL成功=(1+2+3+….+n)/n=(n+1)/2
ALS不成功=(2+3+…+n+(n+1))/n=(n+2)/2
9.26试将折半查找的算法改成递归算法。
intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法
if(low>
high)return0;
//查找不到时返回0
mid=(low+high)/2;
if(ST.elem[mid].key==key)returnmid;
elseif(ST.elem[mid].key>
key)
returnSearch_Bin_Recursive(ST,key,low,mid-1);
elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);
}//Search_Bin_Recursive
9.32已知一棵二叉排序树上所有关键字中的最小值为-max,最大值为max,又-max<
x<
max。
编写具有如下功能的函数:
求该二叉树上小于x且最靠近x的值a和大于x且最靠近x的b。
intlast=0;
voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
if(T->
lchild)MaxLT_MinGT(T->
lchild,x);
//本算法仍是借助中序遍历来实现
if(last<
x&
T->
data>
=x)//找到了小于x的最大元素
printf("
a=%d\n"
last);
=x&
x)//找到了大于x的最小元素
b=%d\n"
T->
data);
last=T->
data;
rchild)MaxLT_MinGT(T->
rchild,x);
}//MaxLT_MinGT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七章 图分析 第七 分析
![提示](https://static.bingdoc.com/images/bang_tan.gif)