8。2 对于如图8.33 所示的无向图，试给出： （1）图中每个顶点的度; （2)该图的邻接矩阵; （3）该图的邻接表; (4）该图的连通分量.
（1） D（V0)=2；D（V1)=2；D（V2）=3;D(V3)=3；D（V4）=2；D（V5）=1; D(V6)=1。
0101000010100010100001010000010110001011001010100(2）邻接矩阵1010100
001100000110000000001000000100000100000010vV（3）邻接表
（4）连通分量 1:
2：
8.5 图8.35 所示的是某个无向图的邻接表，试: （1)画出此图；
（2）写出从顶点A 开始的DFS 遍历结果; （3）写出从顶点A 开始的BFS 遍历结果。
（1)图8。35 邻接表对应的无向图如图8。35.1 所示
（2)
从顶点A 开始的DFS 遍历，深度优先遍历的基本思想:对于给定的图 G=（V，E），首先将V中每一个顶点都标记为未被访问,然后,选取一个源点vV将v标记为被访问,再递归地用深度优先搜索方法,依次搜索v的所有邻接点w。若w未曾访问过,则以w为新的出发点继续深度优先搜索遍历,如果从v出发所有路的顶点都已被访问过，则结束. A,B,C,F,E,G，D
从顶点A 开始的BFS 遍历，基本思想：对于给定的图G=（V，E），从图中某未访问过的顶点vi出发： 1)访问顶点vi；
2）访问 vi 的所有未被访问的邻接点w1 ,w2 , …wk ;
3)依次从这些邻接点出发，访问它们的所有未被访问的邻接点； 依此类推,直到图中所有访问过的顶点的邻接点都被访问; A,B，C，D，F，E，G
8.8 对如图8.36 所示的连通图，分别用Prim 和Kruskal算法构造其最小生成树。
解:（1)Prime 算法的基本思路、步骤P167 Prim算法的基本步骤如下：
（1）初始化:U=｛u0}，TREE=｛｝； (2)如果U=V(G），则输出最小生成树T，并结束算法；
(3）在所有两栖边中找一条权最小的边（u，v)（若候选两栖边中的最小边不止一条,可任选其中的一条），将边(u，v）加入到边集TREE中,并将顶点v并入集合U中.
(4）由于新顶点的加入，U的状态发生变化,需要对U与V—U之间的两栖边进行调整。
（5）转步骤（2）
Prim算法构造最小生成树过程：
（2）采用Kruskal 算法求解最小生成树时首先要对边进行由小到大进行排序,本题对边进行排序的结果是：（D,F）1、（C,F）2、（A,F）3、（A,C)4、（F，G）4、（D,E）4、(D，B）4、（C，D）5、（E,G）5、(A，D）6、（D,G）6、（A，B）7 。根据Kruskal 算法，构造最小生成树的过程如图
8。9 对于如图8。37 所示的有向网，用Dijkstra 方法求从顶点A 到图中其他顶点的最短路径,并写出执行算法过程中距离向量d 与路径向量p 的状态变化情况。
解：
Dijkstra算法的基本思想： 把图中所有顶点分成两组，第一组包括已确定最短路径的顶点，初始时只含有一个源点,记为集合S；第二组包括尚未确定最短路径的顶点，记为V—S。按最短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括到S中。在这个过程中，总保持从v0到第一组（S)各顶点的最短路径都不大于从v0到第二组（V—S)的任何顶点的最短路径长度，第二组的顶点对应的距离值是从v0到此顶点的只包括第一组(S)的顶点为中间顶点的最短路径长度.对于S中任意一点j，v0到j的路径长度皆小于v0到（V—S）中任意一点的路径长度。
（后面四行需要在集合S加上E)
从表中可以看出源点A 到其它各顶点的最短距离及路径为: A→B:48 路径：A→B
A→C：57 路径：A→D→F→C A→D：15 路径：A→D A→E：28 路径：A→E A→F：48 路径:A→D→F A→G:38 路径：A→D→G
8。10 试写出如图8.38 所示的AOV 网的4 个不同的拓扑序列。
（这里也有点问题，等待老师再次讲解） 解:拓扑排序过程：
1) 输入AOV网络。令 n 为顶点个数。
2) 在AOV网络中选一个没有直接前驱（入度为0）的顶点, 并输出之; 3) 从图中删去该顶点, 同时删去所有它发出的有向 边; 4） 重复以上（2）、（3）步， 直到
全部顶点均已输出，拓扑有序序列形成，拓扑排序完成; 图8.38 所示的AOV 网的4 个不同的拓扑序列为: （1)ABDCEFGIH (2）ABDECFGIH （3）DABCEFGIH （4）DAECBFGIH
8.11 计算如图8。39 所示的AOE 网中各顶点所表示的事件的发生时间ve(j)，vl（j）,各边所表示的活动的开始时间e(i)，l（i），并找出其关键路径。
解： (1）：e(i）：表示活动ai的最早开始时间。 l（i）：表示活动最迟开始时间的向量。 关键活动特征：e(i)=l（i）
l(j）—e(j)的值表示完成活动aj的时间余量，提前完成非关键活动并不能提高整个工程的进度。
事件可能的最早开始时间ve（i）：对于某一事件vi，它可能的最早发生时间 事件允许的最晚发生时间vl（i）:对于某一事件vi,它允许的最晚发生时间是在保证按时完成整个工程的前提下,该事件最晚必须发生的时间
可以得出:
第7章 二叉树
7.1 选择题.
（1）前序遍历和中序遍历结果相同的二叉树为（ F ）;前序遍历和后序遍历结果相同的二叉树为（ B ）.
A．一般二叉树 B．只有根结点的二叉树
C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树
E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树. （2)以下有关二叉树的说法正确的是( B ）。
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任一个结点的度均为2 (3）一棵完全二叉树上有1001 个结点，其中叶子结点的个数为（ D ）。 A．250 B．500 C．254 D．501
注:1023为深度是10的满二叉树，有512个叶子结点，1001比1023少22个节点.所以有512—22+22/2=501片叶子
(4）一棵完全二叉树有999 个结点,它的深度为( B ). A．9 B．10 C．11 D．12
(5）一棵具有5 层的满二叉树所包含的结点个数为（ B ）。 A．15 B．31 C．63 D．32
7。2 用一维数组存放完全二叉树:ABCDEFGHI，则后序遍历该二叉树的结点序列为( HIDEBFGCA ）.
7。10 已知一棵二叉树的中序遍历的结果为ABCEFGHD ， 后序遍历的结果为 ABFHGEDC，试画出此二叉树。 解：
7。11 已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF,试画出此二叉树 解：
7。14 试编写一个函数,将一棵给定二叉树中所有结点的左、右子女互换。 解：
#include ”bintree。h\" void change（bintree t) ｛ bintree p; if （t） ｛
p=t—〉lchild;
t—>lchild=t—〉rchild； t—〉rchild=p;
change（t—>lchild）； change（t—>rchild)； }
｝
int main(） ｛ bintree t；
creat（＆t）; /＊建立二叉树t 的存储结构＊/ preorder（t)； change（t)； printf（”\\n\"）; preorder（t）； ｝
7。18 假设二叉树采用链式方式存储，root 为其根结点，p 指向二叉树中的任意一个结点，编写一个求从根结点到p 所指结点之间路径长度的函数。
解：在后序遍历非递归算法中，当访问的结点为p 时，其祖先点正好全部在栈中，此时栈中结点的个数就是根结点到p 所指结点之间路径长度。 #include struct node ＊lchild,＊rchild； ｝bintnode; typedef bintnode ＊bintree； typedef struct stack ｛ bintree data［100］； int tag[100］; int top； ｝seqstack； void creat（bintree *t) ; /*函数Depth，功能：求根结点到x 的路径长度＊/ int Depth（bintree t，datatype x） ｛ seqstack s； int i=0,j； s.top=0； while（t ｜｜ s。top！=0） ｛ while（t) ｛ s。data[s.top]=t; s。tag［s.top]=0； s.top++; t=t—〉lchild; } while（s。top>0 &＆ s.tag[s.top—1］） ｛ s。top——； t=s。data［s.top]； if（t->data==x) return s.top; //此时栈中的结点都是x 的祖先结点 ｝ if(s。top〉0） { t=s。data［s。top—1]； s.tag［s.top—1]=1； t=t->rchild; ｝ else t=NULL; ｝ } 第6章 树 6。1 树最适合用来表示具有( 有序 ）性和( 层次 )性的数据。 6.2 在选择存储结构时，既要考虑数据值本身的存储，还需要考虑（ 数据间关系 ） 的存储。 6。3 对于一棵具有n 个结点的树，该树中所有结点的度数之和为（ n-1 ）。 6.4 已知一棵树如图6.11 所示，试回答以下问题: （1）树中哪个结点为根结点？哪些结点为叶子结点？ 答：A 是根结点；E,G，H，I，C,J,K，L 为叶结点。 (2）结点B 的双亲为哪个结点？其子女为哪些结点? 答：B 的双亲结点是A，其子女结点为E 和F。 （3）哪些结点为结点I 的祖先?哪些结点为结点B 的子孙? 答:F，B，A 是结点I 的祖先结点；E,F，G,H，I 是B 的子孙结点。 （4）哪些结点为结点D 的兄弟？哪些结点为结点K 的兄弟? 答：B,C,L 是结点D 的兄弟结点，J 是结点K 的兄弟结点。 （5)结点J 的层次为多少?树的高度为多少？ 答：结点J 的层次为3，树的高度为4。 （6)结点A、C 的度分别为多少？树的度为多少? 答:结点A 的度为4，结点C 的度是0，树的度是4。 （7）以结点B 为根的子树的高度为多少？ 答：以结点B 为根的子树的高度是3. (8)试给出该树的括号表示及层号表示形式。 答：该树的括号表示为：A（B(E，F（G，H，I)）,C，D(J，K）,L），该树的层号 表示为：10A,20B，30E,30F,40G，40H，40I，20C,20D，25J，25K，20L 6。5 试写出图6.11 所示树的前序遍历、后序遍历和层次遍历的结果。 答： 前序遍历：ABEFGHICDJKL 后序遍历：EGHIFBCJKDLA 层次遍历:ABCDLEFJKGHI 6。9 假设树采用指针方式的孩子表示法表示,试编写一个非递归函数,实现树的后序遍历算法。 答: #include \"tree.h” int PostOrderByStack （TreeNode ＊root） { TreeNode ＊temp; TreeNode *stack［MAXLEN]； // childSeq 表示当前打印到了此树第几个孩子, int top,childSeq[MAXLEN］； int i; top = —1； //初始化空栈 temp = root； while （1) ｛ while (temp != NULL) { for （i = 0；i < MAXN；i++) { if （temp—〉child［i] != NULL） { childSeq［++top］ = i + 1； stack[top] = temp； temp = temp—>child［i］； break; } } // 如果此节点是叶子节点,则输出该结点 if （i == MAXN） { printf (\"％5c”，temp—〉key）； temp = NULL； break； ｝ } while (top != —1 ） ｛ for （i = childSeq[top];i 〈 MAXN；i++） { if (stack[top]—〉child［i］ ！= NULL） ｛ temp = stack［top]—〉child[i]； childSeq［top] = i + 1; break； ｝ ｝ if (i == MAXN) { printf (”％5c”,stack[top］-〉key)； top—-； ｝ if （temp != NULL) ｛ break； } ｝ if (top == -1) ｛ return 1; } } ｝ int main （） ｛ char string［MAXLEN］； TreeNode ＊root = NULL； printf （”请用树的括号表示法输入一棵树:\\n”)； scanf （”%s”，string）； root = CreateTree （root,string）; PostOrderByStack (root）; return 0; ｝ 因篇幅问题不能全部显示，请点此查看更多更全内容