数据结构习题课第876章

1、第8章图关于如图所示的无向图，试给出：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毗邻矩阵1010100001100000110000000001000000100000100000010V3）毗邻表连通重量1：2：图所示的是某个无向图的毗邻表，试：1）画出此图；2）写出从极点A开始的DFS遍历结果；3）写出从极点A开始的BFS遍历结果。1）图毗邻

2、表对应的无向图如图所示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）挨次从这些毗邻点出发，接见它们的所有未被接见的毗邻点;依此类推，直

3、到图中所有接见过的极点的毗邻点都被接见；A，B，C，D，F，E，G对如图所示的连通图，分别用Prim和Kruskal算法结构其最小生成树。解：（1）Prime算法的基本思路、步骤P167Prim算法的基本步骤以下：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）采纳Kru

4、skal算法求解最小生成树时第一要对边进行由小到大进行排序，此题对边进行排序的结果是：（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算法，结构最小生成树的过程如图关于如图所示的有向网，用Dijkstra路径，并写出履行算法过程中距离向量方法求从极点d与路径向量A到图中其余极点的最短p的状态变化状况。解：Dijkstra算法的基本思想：把图中所有极点分红两组，第一组包含已确立最短路径的极点，初始时只含有一个源点，记为会合S；第二组包含还没有确立最短路径的极点，

5、记为V-S。按最短路径长度递加的次序逐一把V-S中的极点加到S中去，直至从v0出发可以抵达的所有极点都包含到S中。在这个过程中，总保持从v0到第一组（S）各极点的最短路径都不大于从v0到第二组（V-S）的任何极点的最短路径长度，第二组的极点对应的距离值是从v0到此极点的只包含第一组（S）的极点为中间极点的最短路径长度。关于S中随意一点j，v0到j的路径长度皆小于v0到（V-S）中随意一点的路径长度。(后边四行需要在会合S加上E)从表中可以看出源点A到其余各极点的最短距离及路径为：AB：48路径：ABAC：57路径：ADFCAD：15路径：ADAE：28路径：AEAF：48路径：ADFAG：38

6、路径：ADG试写出如图所示的AOV网的4个不同样的拓扑序列。(这里也有点问题，等候老师再次解说)解：拓扑排序过程：输入AOV网络。令n为极点个数。在AOV网络中选一个没有直接前驱（入度为0）的极点,并输出之;从图中删去该极点,同时删去所有它发出的有向边;重复以上(2)、(3)步,直到所有极点均已输出，拓扑有序序列形成，拓扑排序达成；图所示的AOV网的4个不同样的拓扑序列为：（1）ABDCEFGIH（2）ABDECFGIH3）DABCEFGIH4）DAECBFGIH计算如图所示的AOE网中各极点所表示的事件的发生时间ve(j)，vl(j)，各边所表示的活动的开始时间e(i)，l(i)，并找出其重

7、点路径。解：(1):e（i）：表示活动ai的最早开始时间。（i）：表示活动最迟开始时间的向量。重点活动特点：e（i）=l（i）l（j）-e（j）的值表示达成活动aj的时间余量，提早达成非重点活动其实不可以提升整个工程的进度。事件可能的最早开始时间ve（i）：关于某一事件vi，它可能的最早发生时间事件赞成的最晚发生时间vl（i）：关于某一事件vi，它赞成的最晚发生时间是在保证准时达成整个工程的前提下，该事件最晚必然发生的时间可以得出：第7章二叉树选择题。1）前序遍历和中序遍历结果同样的二叉树为（F）；前序遍历和后序遍历结果同样的二叉树为（B）。A一般二叉树B只有根结点的二叉树C根结点无左孩子的二

8、叉树D根结点无右孩子的二叉树E所有结点只有左子树的二叉树F所有结点只有右子树的二叉树。2）以下相关二叉树的说法正确的选项是（B）。A二叉树的度为2B一棵二叉树的度可以小于2C二叉树中最罕有一个结点的度为2D二叉树中任一个结点的度均为23）一棵完满二叉树上有1001个结点，此中叶子结点的个数为（D）。A250B500C254D501注：1023为深度是10的满二叉树，有512个叶子结点，1001比1023少22个节点。因此有512-22+22/2=501片叶子4）一棵完满二叉树有999个结点，它的深度为（B）。A9B10C11D12（5）一棵拥有5层的满二叉树所包含的结点个数为（B）。A15B3

9、1C63D32用一维数组寄存完满二叉树：ABCDEFGHI，则后序遍历该二叉树的结点序列为HIDEBFGCA）。已知一棵二叉树的中序遍历的结果为ABCEFGHD，后序遍历的结果为ABFHGEDC，试画出此二叉树。解：已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试画出此二叉树解：试编写一个函数，将一棵给定二叉树中所有结点的左、右儿女交换。解：#includevoidchange(bintreet)bintreep;if(t)p=t-lchild;t-lchild=t-rchild;t-rchild=p;change(t-lchild);change(t-rchil

10、d);intmain()bintreet;creat(&t);/*成立二叉树t的储蓄结构*/preorder(t);change(t);printf(n);preorder(t);假定二叉树采纳链式方式储蓄，root为其根结点，p指向二叉树中的随意一个结点，编写一个求从根结点到p所指结点之间路径长度的函数。解：在后序遍历非递归算法中，当接见的结点为p时，其先人点正好所有在栈中，此时栈中结点的个数就是根结点到p所指结点之间路径长度。#include#includetypedefchardatatype;typedefstructnode/*二叉树结点定义*/datatypedata;struct

11、node*lchild,*rchild;bintnode;typedefbintnode*bintree;typedefstructstackbintreedata100;inttag100;inttop;seqstack;voidcreat(bintree*t);/*函数Depth，功能：求根结点到x的路径长度*/intDepth(bintreet,datatypex)seqstacks;inti=0,j;=0;while(t|!=0)while(t)=t;=0;+;t=t-lchild;while0&);t=;if(t-data=x)return;/此时栈中的结点都是x的先人结点if0)t

12、=;=1;t=t-rchild;elset=NULL;第6章树树最适适用来表示拥有（有序）性和（层次）性的数据。在选择储蓄结构时，既要考虑数据值自己的储蓄，还需要考虑（数据间关系）的储蓄。关于一棵拥有n个结点的树，该树中所有结点的度数之和为（n-1）。已知一棵树如图所示，试回答以下问题：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的后代结点。

13、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试写出图所示树的前序遍历

14、、后序遍历和层次遍历的结果。答：前序遍历：ABEFGHICDJKL后序遍历：EGHIFBCJKDLA层次遍历：ABCDLEFJKGHI假定树采纳指针方式的孩子表示法表示，试编写一个非递归函数，实现树的后序遍历算法。答：#includeintPostOrderByStack(TreeNode*root)TreeNode*temp;TreeNode*stackMAXLEN;/childSeq表示目前打印到了此树第几个孩子，inttop,childSeqMAXLEN;inti;top=-1;/初始化空栈temp=root;while(1)while(temp!=NULL)for(i=0;ichildi!=NULL)childSeq+top=i+1;stacktop=temp;temp=temp-childi;break;假如此节点是叶子节点，则输出该结点if(i=MAXN)printf(%5c,temp-key);temp=NULL;break;while(top!=-1)for(i=childSeqtop;ichildi!=NULL)temp=stacktop-childi;childSeqtop=i+1