2. 计算机
  3. 阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是： ①访问顶点v； ②访问v的所有未被访问的邻接顶点w1，w2……，wk； ③依次从这

阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点v出发进行广度优先遍历的过程是： ①访问顶点v； ②访问v的所有未被访问的邻接顶点w1，w2……，wk； ③依次从这

admin2017-11-28  67
问题 阅读以下说明和代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
【说明】
图是很多领域中的数据模型，遍历是图的一种基本运算。从图中某顶点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[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。

【代码】
int BFSTraverse(Graph G)
{／／对图G进行广度优先遍历，图采用邻接矩阵存储
unsigned char*visited；  ／／visited[]用于存储图G中各顶点的访问标志，0表示未访问
int v，  w，  u；
QUEUE  Q；
／／申请存储顶点访问标志的空间，成功时将所申请空间初始化为0
visited=  (char*)calloc(G．vexnum，  sizeof(char))；
if  (   (1)    )
return 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；  wif  (G．arcs  !=0  &＆  (5)   )  {
／／w是u的邻接顶点且未访问过
printf(“％d”，w)；    ／／访问顶点w
visited[w]  =1；
EnQueue(＆Q，w)；
}
}
}
}
free(visited)；
return OK；
}／／BFSTraverse
选项
答案(1)!visited 或visited==NULL或visited=0或等效形式 (2)InitQueue(&Q) (3)EnQueue(&Q，V) (4)DeQueue(&Q，&u) (5)!visited[w]或visited[w]=0或visited[w]!=1或等效形式
解析 本题考查C程序中函数参数和数据结构的应用。
根据题目说明，首先需了解对图中顶点进行遍历的基本方式。深度优先和广度优先是对图进行遍历的两种方式。
以图4．1为例，从顶点a出发进行深度优先遍历的一种顺序为a，b，e，d，f，c。毫无疑问，第一个被访问的顶点为a，第二个为什么是b?这就与图的存储有关系了。若该图采用的是邻接矩阵存储，如图4-2所示，观察其中顶点a的邻接信息向量“011010”，其中的三个1分别表示b，c，e这三个顶点是a的邻接顶点，一般情况下对该向量从左向右扫描，因此b是a的第一个邻接顶点且还未被访问(根据访问标志)，所以访问a之后接下来访问b。接下来要去访问没有被访问过b的邻接顶点，再考察b的邻接信息向量“000011”，其中的两个1分别表示e，f是b的邻接顶点，而且这两个顶点都未访问过，所以第三个被访问的顶点是e，按照相同的思路，然后是d，f，最后访问顶点c。
如果是广度优先遍历，访问顶点a之后，接下来要访问所有a的所有的未被访问的邻接顶点，按照邻接矩阵存储，a的三个邻接顶点为b，c，e，依次访问这三个顶点后，接下来先访问b的邻接顶点(未被访问过的)，然后访问c的邻接顶点(未被访问过的)，最后访问e的邻接顶点(未被访问过的)，在该过程中用队列来暂存顶点，确保访问顶点的顺序。因此，广度优先遍历序列为a，b，c，e，f，d。
函数BFSTraverse(Graph G)对图G进行广度优先遍历。空(1)处判断函数calloc的返回值是否为空指针，应填入“!visited”或其等效形式。
空(2)处初始化一个空的队列，根据函数原型提供的信息，注意形参为指针参数，要求实参提供的是地址，因此应填入“InitQueue(&Q)”。
根据注释，空(3)处是向队列中加入元素v，根据函数原型提供的信息，注意第一个形参为指针参数，要求第一个实参提供的是地址，因此应填入“EnQueue(&Q，v)”。
根据注释，空(4)处是令队头元素出队列，根据函数原型提供的信息，注意两个形参都是指针参数，要求两个实参都提供地址，而第一个参数表示队列，第二个参数表示出队的队头元素，因此应填入“DeQueue(&Q，&u)”。
空(5)所在表达式中，“Garcs[w]!=0”说明w是u的邻接顶点，在w还未被访问的情况下(visited[w]==0)再访问顶点w，因此应填入“visited[w]=0”或其等效形式。
转载请注明原文地址:https://www.kaotiyun.com/show/a9jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)