数据结构课程 课后习题答案

练习题及参考答案 ve(E)=MAX{ve(B)+1,ve(C)+2}=9， ve(G)=MAX{ve(E)+1,ve(F)+5}=11， vl(G)=11，vl(E)=vl(G)-1=10，

vl(C)=vl(E)-2=8，vl(B)=MIN{vl(E)-1,vl(C)-3}=5， vl(F)=MIN{vl(G)-5,vl(C)-1}=6，vl(D)=vl(F)-3=3， vl(A)=MIN{vl(B)-1,vl(C)-2,vl(D)-3}= 0; 则：l(FC)=vl(C)-1=7

所以，事件C的最早开始时间为7，活动FC的最迟开始时间为7。

（4）对于如图7.4所示的有向图G，给出它的4个不同的拓扑有序序列。

答：该图的4个不同的拓扑有序序列是：12345678，12354678，12347856，12347568（实际上不止4个）。

2 1 4 3 5 6 7 8 图7.4 一个有向图

4. 算法设计题

（1）假设图G采用邻接矩阵存储，给出图的深度优先遍历算法，并分析算法的时间复杂度。

解：基于图的邻接矩阵表示的深度优先遍历算法如下：

int visited[MAXVEX];

void DFS1(MatGraph g,int v) { }

int i;

visited[v]=1; printf(\for (i=0;i

DFS1(g,i);

//找顶点v的相邻点

//对于未访问过的顶点i进行递归

if (g.edges[v][i]!=0 && g.edges[v][i]!=INF && visited[i]==0)

（2）假设以邻接表作为图的存储结构，设计一个算法求出无向图G的连通分量个数。 解：采用DFS遍历的算法如下：

int getnum(AdjGraph *G) {

for (i=0;in;i++)

//求图G的连通分量

int i, n=0, visited[MAXVEX];

45

数据结构简明教程

}

visited[i]=0; if (visited[i]==0) { }

n++; DFS(G,i);

//对图g从顶点i开始进行深度优先遍历

for (i=0;in;i++)

return n;

（3）假设以邻接表作为图的存储结构，分别写出基于DFS和BFS遍历的算法来判别图G中顶点i和顶点j（i≠j）之间是否有路径。

解：先置全局变量visited[]为0，然后从顶点i开始进行某种遍历，遍历之后，若visited[j]=0，说明顶点i与顶点j之间没有路径；否则说明它们之间存在路径。

基于DFS遍历的算法如下：

int visited[MAXVEX]; { }

int k;

for (k=0;kn;k++)

visited[k]=0;

//从顶点i开始进行深度优先遍历

DFS(G,i);

//全局变量

int DFSTrave(AdjGraph *G,int i,int j)

if (visited[j]==0) return 0; else return 1;

基于BFS遍历的算法如下：

int visited[MAXVEX]; { }

int k;

for (k=0;kn;k++)

visited[k]=0;

//需将BFS算法中的visited[]定义改为全局变量

BFS(G,i);

//全局变量

int BFSTrave(AdjGraph *G,int i,int j)

if (visited[j]==0) return 0; else return 1;

上机实验题7

假设一个带权有向图采用邻接表存储。设计一个算法输出从顶点u到顶点v并经过顶点k的所有路径及其长度。并用相关数据进行测试。

解：采用基于深度优先遍历的递归算法求解，对应的程序如下：

#include

#include \ int visited[MAXVEX];

练习题及参考答案 //包含邻接表的基本运算函数

int Inpath(int k,int path[],int d) //判断path是否含有顶点k { }

void FindallPath(AdjGraph *G,int u,int v,int k,int path[],int d,int plength) //输出G中从u→v经过k的所有路径及其长度 { }

void main() {

AdjGraph *G; int n=6,e=11,i; int u=0,v=4,k=2; int path[MAXVEX],d=-1; int A[][MAXVEX]={

{0,50,10,INF,INF,INF}, {INF,0,15,50,10,INF}, {20,INF,0,15,INF,INF}, {INF,20,INF,0,35,INF}, ArcNode *p; int w,i; visited[u]=1; d++; path[d]=u; { }

p=G->adjlist[u].firstarc; while (p!=NULL) { }

visited[u]=0;

//回溯找所有简单路径

w=p->adjvex; { }

p=p->nextarc;

//p指向下一个相邻点

//相邻点的编号为w //增加路径长度

//递归调用

//回退时减去相应长度

if (visited[w]==0)

plength+=p->weight; plength-=p->weight;

FindallPath(G,w,v,k,path,d,plength);

//p指向u的第一个相邻点

//顶点u加入到路径中

if (u==v && d>=1 && Inpath(k,path,d)) //找到一条包含k的路径

printf(\路径:%d\for (i=1;i<=d;i++)

//输出找到一条路径并返回

printf(\→%d\

int i;

for (i=0;i<=d;i++)

if (path[i]==k)

return 1;

return 0;

printf(\长度为%d\\n\

47

数据结构简明教程

}

{INF,INF,INF,30,0,INF}, {INF,INF,INF,3,INF,0}};

//建立图7.30的邻接表

CreateGraph(G,A,n,e); for (i=0;in;i++)

visited[i]=0;

printf(\图G的存储结构:\\n\

printf(\从顶点%d到%d并经过顶点%d的所有路径及其长度:\\n\FindallPath(G,u,v,k,path,d,0); DestroyGraph(G);

练习题8

1. 单项选择题

（1）要进行顺序查找，则线性表（ ① ）；要进行二分查找，则线性表（ ② ）；要进行散列查找，则线性表（ ③ ）。某顺序表中有90000个元素，已按关键项的值的升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为（ ④ ），最大比较次数为（ ⑤ ）。

①②： A.必须以顺序方式存储 B.必须以链表方式存储 C.必须以散列方式存储 D.既可以以顺序方式，也可以以链表方式存储 E.必须以顺序方式存储且数据元素已按值递增或递减的次序排好 F.必须以链表方式存储且数据元素已按值递增或递减的次序排好 ④⑤： A.25000 B.30000 C.45000 D.90000 答：①D ②E ③C ④C ⑤D （2）链表适用于（ ）查找 A.顺序 B.二分法 C.顺序，也能二分法 D.随机 答：A

（3）折半查找有序表（4,6,10,12,20,30,50,70,88,100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。

A.20,70,30,50 B.30,88,70,50 C.20,50 D.30,88,50 答：A

（4）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。 A.3 B.4 C.5 D.6 答：C

（5）有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。

A. 35/12

B. 37/12

C. 39/12

D. 43/12