网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
如果从无向图的任一顶点出发进行一次DFS遍历即可访问所有顶点，则该图一定是
A．完全图
B．连通图
C．有回路
D．一棵树
参考答案和解析
连通图
更多 “如果从无向图的任一顶点出发进行一次DFS遍历即可访问所有顶点，则该图一定是A．完全图B．连通图C．有回路D．一棵树” 相关考题
考题
● 若无向连通图 G 具有 n个顶点，则以下关于图 G的叙述中，错误的是（43）。（43）A.G 的边数一定多于顶点数B.G 的生成树中一定包含 n个顶点C.从 G 中任意顶点出发一定能遍历图中所有顶点D.G 的邻接矩阵一定是n阶对称矩阵
考题
阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。1. 【说明】实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。【算法】第一步：首先访问连通图G的指定起始顶点v；第二步：从V出发，访问一个与v(1)p，再从顶点P出发，访问与p(2)顶点q，然后从q出发，重复上述过程，直到找不到存在(3)的邻接顶点为止。第三步：回退到尚有(4)顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。因此，在这个算法中应设一个栈保存被(5)的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。
考题
● 对连通图进行遍历前设置所有顶点的访问标志为 false（未被访问） ，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true（已访问） ，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。 （40） 是下图的深度优先遍历序列。（40）A. 1 2 3 4 6 5B. 1 2 6 3 4 5C. 1 6 2 5 4 3D. 1 2 3 4 5 6
考题
以下关于图的遍历的叙述中，正确的是(61)。A.图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程B.图的深度优先遍历方法不适用于无向图C.使用队列对图进行广度优先遍历D.图中有回路时则无法进行遍历
考题
阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点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; vG.vexnum; v++){ if(!visited[v]){ //从顶点v出发进行广度优先遍历 printf(%d，v)； //访问顶点v并将其加入队列 visited[v]=1； （3） ； while(！isEmpty(Q)){ （4） ； //出队列并用u表示出队的元素 for(w=0;vG.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
考题
试题四（共 15 分）阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点 v出发进行广度优先遍历的过程是：①访问顶点 v；②访问 V 的所有未被访问的邻接顶点 W1 ,W2 ,..,Wk；③依次从这些邻接顶点 W1 ,W2 ,..,Wk 出发，访问其所有未被访问的邻接顶 点；依此类推，直到图中所有访问过的顶点的邻接顶点都得到访问。显然，上述过程可以访问到从顶点 V 出发且有路径可达的所有顶点。对于 从 v 出发不可达的顶点 u，可从顶点 u 出发再次重复以上过程,直到图中所有顶 点都被访问到。例如，对于图 4-1 所示的有向图 G，从 a 出发进行广度优先遍历，访问顶点 的一种顺序为 a、b、c、e、f、d。图 4-1
设图 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=l};代码中用到的队列运算的函数原型如表 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 } free(visited);return OK;)//BFSTraverse从下列的 2 道试题（试题五至试题六）中任选 1 道解答。请在答题纸上的 指定位置处将所选择试题的题号框涂黑。若多涂或者未涂题号框，则对题号最小 的一道试题进行评分。
考题
阅读下列说明和?C?代码，回答问题?1?至问题?2，将解答写在答题纸的对应栏内。
【说明】
一个无向连通图?G?点上的哈密尔顿（Hamiltion）回路是指从图?G?上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路劲。一种求解无向图上哈密尔顿回
路算法的基础私下如下：假设图?G?存在一个从顶点?V0?出发的哈密尔顿回路?V1——V2——V3——...——Vn-1——V0。算法从顶点?V0?出发，访问该顶点的一个未被访问的邻接顶点?V1，接着从顶点?V1?出发，访问?V1?一个未被访问的邻接顶点?V2，..。；对顶点?Vi，重复进行以下操作：访问?Vi?的一个未被访问的邻接接点?Vi+1；若?Vi?的所有邻接顶点均已被访问，则返回到顶点?Vi-1，考虑Vi-1?的下一个未被访问的邻接顶点，仍记为?Vi；知道找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。
【C?代码】
下面是算法的?C?语言实现。
（1）常量和变量说明
n :图?G?中的顶点数
c［］［］:图?G?的邻接矩阵
K:统计变量，当期已经访问的定点数为?k+1
x［k］:第?k?个访问的顶点编号，从?0?开始
Visited［x［k］］：第?k?个顶点的访问标志，0?表示未访问，1?表示已访问
⑵C?程序
【问题?1】（10?分）
根据题干说明。填充?C?代码中的空（1）~（5）。
【问题?2】（5?分）
根据题干说明和?C?代码，算法采用的设计策略为（ ），该方法在遍历图的顶点时，采用的
是（?）方法（深度优先或广度优先）。
考题
判断题对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。A
对B
错
热门标签
最新试卷
