《数据结构与算法6》由会员分享，可在线阅读，更多相关《数据结构与算法6（34页珍藏版）》请在金锄头文库上搜索。
1、 第六次作业 一、选择题 1、深度优先遍历类似与二叉树的 ： A先根遍历 B.中根遍历 C. 后根遍历 D 层次遍历 2、广度优先遍历类似与二叉树的 : A. 先根遍历 中根遍历 C. 后根遍历 D.层次遍历 、下列有关开放树（Free Tre)的说法错误的是 C : A.具有n个结点的开放树涉及n-1条边 . 开放树没有回路 C.开放树可以是非连通图 .在开放树中任意加一条边，一定会产生回路4、有关最小生成树,下列说法错误的是 : A 最小生成树是一棵开放树 B.最小生成树各边的和是所有生成树中最小的 . 任何图都只有一种最小生成树 D. 可以产生最小生成树的图,其边一定有权值 5、任何一种
2、无向连通图的最小生成树 ： A. 只有1棵 B. 1棵或多棵 C. 一定有多棵 D. 也许不存在 6、在如下图所示的图中,从顶点a出发,按深度优先遍历,则也许得到的一种顶点的序列为 C和 。 A a, b, e, d，f B. a, c， f, e, b，d . a， e, , c,f, D , e，d,f, c, b 7、在如上图所示的图中,从顶点出发，按广度优先遍历，则也许得到的一种顶点的序列为 。 A.a, b, e, c,d, f B. a， b,e, ，f, d . a， e， , c， f， d D. a, e， d,f, , 8、设网(带权的图)有个顶点和条边，则采用邻接表存储时
3、，求最小生成树的Pim算法的时间复杂度为 。 23A. O(n) B.O(n+e) C O(n) D O(n）9、设图有n个顶点和条边，求解最短途径的Foyd算法的时间复杂度为 。 2 A (n) BO（n+) C. （n) D. （n) 10、最小生成树是指 C 。 A. 由连通网所得到的边数至少的生成树。 B由连通网所得到的顶点数相对较少的生成树。 C.连通网中所有生成树中权值之和为最小的生成树。 D. 连通网的极小连通子图。 11、下面有关工程筹划的AE网的论述中,不对的的是 B 。 A. 核心活动不按期完毕就会影响整个工程的完毕时间。 B.任何一种核心活动提前完毕，那么整个工程将会提前
4、完毕。 C.所有核心活动都提前完毕,那么整个工程将会提前完毕。 D 某些核心工程若提前完毕,那么整个工程将会提前完毕。 12、在OE网中,始点和汇点的个数为 D 。 A.1个始点,若干个汇点B. 若干个始点,若干个汇点 C 若干个始点,1个汇点 D.1个始点，个汇点 、在下图所示的无向图中，从顶点v1开始采用Prim算法生成最小生成树，算法过程中产生的顶点顺序为 B 。 A. v1,v3，v4， 2, v, v B. v, v3, , v2,v5，v4 C. v1, v,v3, v,v5, v D. 1, v3， v6,v4,v2, 5 14、在上图所示的途中,采用Cruskal算法生成最小生
5、成树,过程中产生的边的顺序是 C 。 .（v1, v2）， (v2, v), （v5, v6), (v1， 5) B. (v1, v3), （2，）,(v2， v5),（v1， 4） C (1, ), (v2, v),(v, 6）, (v4, v5） D （v2, v), (1, 3), (v5， v), (v,v5) 15、如下图所示的图中，其中一种拓扑排序的成果是 。 A 1v2v3vv4v5v7v8 . 12v3v46vvC v1vvv5v2v3v7v . v1v62v3v7v8v4v 16、在下图所示的网中，活动a9的最早开始时间为 。 .13 B. 14 C. 15 D. 1 7、在
6、上图所示的OE网中,活动a4的最迟开始时间为 D A. 4 B. 5 C 6 7 二、填空题 1、图的遍历有 深度优先遍历 和广度优先遍历等措施。 2、在深度优先搜索和广度优先搜索中,都采用vitedi false 的方式设立第i个顶点为 new,而采用isitedi= te 的方式标记第i个结点为old。 3、由于深度优先算法的特点,深度优先往往采用 递归 的方式实现。 4、由于广度优先算法的特点，在广度优先实现过程中，往往要借助于另一种数据构造 队列 实现。 5、在深度优先搜索和广度优先搜索中，在搜索过程中所通过的边都称为 树边 。 6、连通并且无环路的无向图称为 开放树 。 、对于具有n
7、个顶点条边的连通图,运用Prim算法求其最小生成树的时间复杂度为 （n) ，运用Kucal算法求最小生成树的时间复杂度是 O() 。 8、顶点表达活动的网简称为 A ；边表达活动的网简称为 AE 。 9、一种具有n个顶点的无向连通图,其每条边的权重都是(0)，则其最小生成树的权重等于 （1)*a 。 三、已知一种连通图如下图所示，分别给出一种按深度优先遍历和广度优先遍历的顶点序列(假设从顶点v1出发）。并编程分别实现该图的邻接矩阵表达和邻接表表达，规定编写有关基本操作，并在主函数中求出深度优先序列和广度优先序列。 v1 v v4 v5 v6 0 0 1 0 1 v1 1 01 1 0 v2 0
8、 1 0 0 1 0 1 0 11 v 0 1 1 1 0 0 1 0 HEAD v v2 4 v v2 v1 v v4 5 v3 v v v 1 2v5 v6 v5 v v34 v v1 4 深度优先：v v2v3 v v4 v 广度优先:v1v2 v 6 v 5 #iclde iosrea include using namespace sd; typedef har VetexDta; typed it EdeDta; tyeef stct node ntajvex; EdgeDtacst; stutnod *et; EdgNode; tpedf strt VetexDatvre; Ed
9、geNode * fstege; Vertexde； typedef stru ertexNde vxlstuVertcs+1； n,; AdGah; / 邻接表表达 BOOLN vistedVrtic; i dfnNumVertice；/深度优先 voi DFravrse(r G) int i , cont = ； fr ( i = 0； i G.n； i+) vistedi =AE; or （ i = 0; iG.; i+ ) if ( ! visited ) DFS( &G, i1); oid DFS1(djGrap*G， in i） stic intount=0; EdgNde; co
10、uvitverex; vsitdi=TUE； dfnicoun+; p=G-exlsi.irsege; whi（1 ) f(！istpjvex ) D1(G, padjve); p=p-nex； f(p=NL) ek； int bnNmVertic;/广度优先od FS1 （AdjGrph *G, int k) EdgeNoe p; QUE Q; AKULL(); cou G-vexltk .vert; vsite k true; ENQEE (， Q）; wle ( !EPT() ) i = FROT（Q)-lment; DEUE(Q）; p=G-velisi.irteg; while （ p ) if （!vsted-djex ) cut Gexlist-adv.ertx; visie-djex =RE； QUUE ( p-adex , Q ）; p =p-net; nt main（） AdGrah G； IniADJraph(&）; VetData v6 = a,
