发布时间 : 星期五 文章校本教材各章习题及答案更新完毕开始阅读6ee99662580102020740be1e650e52ea5518ce3a
Leafnum(T->lchild); Leafnum(T->rchild); } }
void Nodenum(Btree T) {/*求二叉树的总结点数*/ if(T) {
count++;
Nodenum(T->lchild); Nodenum(T->rchild); } }
int TreeDepth(Btree T) {/*求二叉树的深度*/ int ldep,rdep; if(T==NULL) return 0; else
{ldep=TreeDepth(T->lchild); rdep=TreeDepth(T->rchild); if(ldep>rdep) return ldep+1; else
return rdep+1; } } main() {Btree T;
char ch1,ch2,a; ch1='y';
while(ch1=='y'||ch1=='Y') {
printf(\ 1--------创建二叉树 *\ printf(\ 2--------先序遍历的序列 *\ printf(\ 3--------中序遍历的序列 *\ printf(\ 4--------后序遍历的序列 *\
printf(\ 5--------叶子结点数 *\ printf(\ 6--------总结点数 *\ printf(\ 7--------二叉树的深度 *\
printf(\ 0--------返回 *\printf(\printf(\ \scanf(\
getchar(); printf(\switch(ch2) { case '1':
printf(\输入二叉树的结点序列\
printf(\代表后续结点为空，按回车输入下一结点\ printf(\输入根结点\ T=createBT();
printf(\二叉树创建成功\\n\case '2':
printf(\先序遍历的序列为:\Preorder(T);break; case '3':
printf(\递归算法中序遍历的序列为:\Inorder(T);
printf(\采用非递归算法的中序遍历序列为:\\n\InOrderTraverse(T); break; case '4':
printf(\后序遍历的序列为:\Postorder(T);break; case '5': count=0; Leafnum(T);
printf(\叶子结点数为:%d\\n\break; case '6': count=0; Nodenum(T);
printf(\总结点数为:%d\\n\break; case '7':
printf(\二叉树的深度为:%d\break; case '0':
ch1='n';break; default :
printf(\输入有误\ } if(ch2!='0') {
printf(\按回车键，返回主菜单\\n\ a=getchar();
if(a!='\\xA'){getchar();ch1='n';} } } getch(); }
第七章 图
7.7总结与提高
7.7.1主要知识点
（1）图的相关概念，包括图、有向图、无向图、完全图、子图、连通图、度、入度、出度、简单回路和环等定义。
（2）图的各种存储结构，包括邻接矩阵和邻接表等。
（3）图的基本运算，包括创建图、输出图、深度优先遍历、广度优先遍历算法等。 （4）图的其他运算，包括最小生成树、最短路径、拓扑排序等算法。
7.7.2典型例题
1、对有五个结点{ A,B ,C,D,E}的图的邻接矩阵， ?010030?10???0????????60020??????10?0???????500??
（1）画出逻辑图； （2）画出图的邻接表存储；
（3）从顶点A出发，写出图基于邻接表的深度优先、广度优先遍历序列； （4）写出图可能的拓扑序列； （5）计算图的关键路径；
（6）画出按普里姆算法构造最小生成树的示意图。 解：
（1）逻辑图如图7-23的图（A所示；
B100A301050E60C2010DAB∧CDEB100... ... ... C30... ... ... E10... ... ... ∧BBD60... ... ... D∧∧20... ... ... ∧10... ... ... 50... ... ... （a） （b）
图7-23 邻接矩阵对应的逻辑图及邻接表
（2）图的邻接表存储如图7-23的图（B 所示；
（3）深度优先遍历序列：AB CDE；广度优先遍历序列：AB CED； （4）可能的拓扑序列：ACEDB 或AECDB ； （5）①事件的最早发生时间与最迟发生时间为：
ve vl A 0 0 C 30 40 E 10 40 D 60 90 B 100 100 ②活动的最早开始时间和最迟开始时间为：
ee el A-B 0 0 A-C 0 10 A-E 0 30 C-B 30 40 C-D 30 70 E-D 10 20 D-B 60 90 根据以上计算，得出关键活动为A-B ，这些活动构成一条关键路径，即A-B 。 （6）普里姆算法构造最小生成树的示意图如图7-24的（A~（D所示；
BBA10CDA3010CDEE(a)
BB10A3010EC20DA3010EC20D(b)
(c) 图7-24 普里姆算法构造最小生成树的示意图
(d)
2、下图7-25所示，是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：