第7章自测题与答案

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！WORD格式可编辑第71（B）3.有8A．（C）4.有8A．（C）5.有8A．（B）A．栈B.队列C.树D.图（A）A．栈B.队列C.树D.图（C）0A．（D）0A．0243156B.0135642C.0423165D.0134256（B）10.已知图的邻接矩阵同上题0A（建议：0123456）专业知识整理分享WORD格式可编辑1专业知识整理分享WORD格式可编辑（D）0（A）0A．（A）14.深度优先遍历类似于二叉树的AB.中序遍历C.后序遍历D.层次遍历（D）15.广度优先遍历类似于二叉树的AB.中序遍历C.后序遍历D.层次遍历（A）AB.一棵或多棵C.一定有多棵D.可能不存在11.2.Gii3.nn)。4.ne5.neO(n+e)。6.G7.G8.9.ii0。10.2专业知识整理分享WORD格式可编辑211.neO(n+e)。)；若采用邻接12.neO(n+e)。13.2)；用克鲁14.用普里姆(Prim)算法求具有ne斯卡尔(Kruskal)算法的时间复杂度是e)。215.G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。16.G的最小生成树，最好用普里姆(Prim)算法来求解。17.用18.061.已知如图所示的有向图，请给出该图的:（123456（（3专业知识整理分享WORD格式可编辑19.（（a。可以直接由原始图画出最小生成树，而且最小生40559→35055a→b4→c3f→d6→e3→g2^专业知识整理分享WORD格式可编辑4专业知识整理分享WORD格式可编辑g→d5→f2→h6^h→c5→d4→g6^卡尔算法步骤(按边归并,堆排序)：—3--cf—3—ea—h取5—d,g—5--d20.121.a解：最短路径为：（a,c,f,e,d,g,b）5专业知识整理分享WORD格式可编辑G:（3用C22.489//最大值∞#defineMAX_VERTEX_NUM20//假设的最大顶点数（可取为//有向/无向图，有向/无向网TypedefstructArcCell{//弧（边）结点的定义VRTypeadj;//顶点间关系，无权图取1或InfoType*info;//该弧相关信息的指针Typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可AdjMatrixarcs;//邻接矩阵IntVernum,arcnum;//79a→b12→e4^b→a12→c20→e8→f9^c→b20→d15→g12^d→c15→g10^e→a4→b8→f6^f→b9→e6^g→c12→d102.解：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{if(v<0)returnERROR;//顶点数不能为负6专业知识整理分享WORD格式可编辑if(a<0)returnERROR;//边数不能为负{{}23.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。（如果要删除所ii0）GStatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G{{}vvi24.j≠intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图Gij是否有路径,是则返回1,否则返回0{j7专业知识整理分享WORD格式可编辑{{j解intvisited[MAXSIZE];//指示顶点是否在当前路径上intlevel＝1;//intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图Gij是否有路径,是则返回1,否则返回0{j{，jk的注intexist_path_len(ALGraphG,inti,intj,intk)//判断邻接表方式存储的