此题为判断题(对,错)。
第1题:
此题为判断题(对,错)。
第2题:
此题为判断题(对,错)。
第3题:
调用一次深度优先遍历可以访问到图中的所有顶点。
此题为判断题(对,错)。
第4题:
阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型,遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是: ①访问顶点v; ②访问V的所有未被访问的邻接顶点W1 ,W2 ,..,Wk; ③依次从这些邻接顶点W1 ,W2 ,..,Wk出发,访问其所有未被访问的邻接顶点;依此类推,直到图中所有访问过的顶点的邻接顶点都得到访问。 显然,上述过程可以访问到从顶点V出发且有路径可达的所有顶点。对于从v出发不可达的顶点u,可从顶点u出发再次重复以上过程,直到图中所有顶点都被访问到。 例如,对于图4-1所示的有向图G,从a出发进行广度优先遍历,访问顶点的一种顺序为a、b、c、e、f、d。设图G采用数组表示法(即用邻接矩阵arcs存储),元素arcs[i][j]定义如下:图4-1的邻接矩阵如图4-2所示,顶点a~f对应的编号依次为0~5.因此,访问顶点a的邻接顶点的顺序为b,c,e。 函数BFSTraverse(Graph G)利用队列实现图G的广度优先遍历。 相关的符号和类型定义如下: define MaxN 50 /*图中最多顶点数*/ typedef int AdjMatrix[MaxN][MaxN]; typedef struct{ int vexnum, edgenum; /*图中实际顶点数和边(弧)数*/ AdjMatrix arcs; /*邻接矩阵*/ )Graph; typedef int QElemType; enum {ERROR=0;OK=1}; 代码中用到的队列运算的函数原型如表4-1所述,队列类型名为QUEUE。 表4-1 实现队列运算的函数原型及说明
【代码】 int BFSTraverse(Graph G) {//对图G进行广度优先遍历,图采用邻接矩阵存储 unsigned char*visited; //visited[]用于存储图G中各顶点的访问标志,0表示未访问 int v, w, u; QUEUEQ Q; ∥申请存储顶点访问标志的空间,成功时将所申请空间初始化为0 visited=(char*)calloc(G.vexnum, sizeof(char)); If( (1) ) retum ERROR; (2) ; //初始化Q为空队列 for( v=0; v<G.vexnum; v++){ if(!visited[v]){ //从顶点v出发进行广度优先遍历 printf("%d”,v); //访问顶点v并将其加入队列 visited[v]=1; (3) ; while(!isEmpty(Q)){ (4) ; //出队列并用u表示出队的元素 for(w=0;v<G.vexnum; w++){ if(G.arcs[u][w]!=0&& (5) ){ //w是u的邻接顶点且未访问过 printf("%d”, w); //访问顶点w visited[w]=1; EnQueue(&Q, w); } } } } free(visited); return OK; )//BFSTraverse
第5题:
第6题:
第7题:
若从无向图中任意一个顶点出发进行1次深度优先搜索便可以访问到该图的所有顶点,则该图一定是一个()。
第8题:
若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点,则该图一定是()图。
第9题:
如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()。
第10题:
非连通图
强连通图
连通图
完全图
第11题:
对
错
第12题:
对
错
第13题:
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。
1. 【说明】
实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。
【算法】
第一步:首先访问连通图G的指定起始顶点v;
第二步:从V出发,访问一个与v(1)p,再从顶点P出发,访问与p(2)顶点q,然后从q出发,重复上述过程,直到找不到存在(3)的邻接顶点为止。
第三步:回退到尚有(4)顶点,从该顶点出发,重复第二、三步,直到所有被访问过的顶点的邻接点都已被访问为止。
因此,在这个算法中应设一个栈保存被(5)的顶点,以便回溯查找被访问过顶点的未被访问过的邻接点。
第14题:
● 对连通图进行遍历前设置所有顶点的访问标志为 false(未被访问) ,遍历图后得到一个遍历序列,初始状态为空。深度优先遍历的含义是:从图中某个未被访问的顶点 v 出发开始遍历,先访问 v 并设置其访问标志为 true(已访问) ,同时将 v 加入遍历序列,再从 v 的未被访问的邻接顶点中选一个顶点,进行深度优先遍历;若 v的所有邻接点都已访问,则回到 v 在遍历序列的直接前驱顶点,再进行深度优先遍历,直至图中所有顶点被访问过。 (40) 是下图的深度优先遍历序列。
(40)
A. 1 2 3 4 6 5
B. 1 2 6 3 4 5
C. 1 6 2 5 4 3
D. 1 2 3 4 5 6
第15题:
图的深度优先遍历算法中需要设置一个标志数组,以便区分图中的每个顶点是否被访问过。
此题为判断题(对,错)。
第16题:
第17题:
第18题:
第19题:
对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点。
第20题:
对于任意一个图,从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点
第21题:
对
错
第22题:
对
错
第23题:
非连通
连通
强连通
有向