发布时间 : 星期二 文章数据结构课程 课后习题答案更新完毕开始阅读
练习题及参考答案 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;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;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;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;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;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