对于图4-1所示的有向图G，写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。 - itgle

题目

对于图4-1所示的有向图G，写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。

相似考题

1.拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，(52)为下图所示有向图的一个拓扑序列。A．1 2 3 4 5 6 7B．1 5 2 6 3 7 4C．5 1 2 6 3 4 7D．5 1 2 3 7 6 4

2.在程序的执行过程中，实现嵌套调用函数正确返回可以用(119)结构。A．队列B．栈C．树D．图

3.阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是：(1)初始时拓扑序列为空；(2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；(3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为vl，v2，…，vn，图G采用邻接表表示，其数据类型定义如下：define MAXVNUM 50 ／*最大顶点数*／typedef struct ArcNode｜／*表结点类型*／int adjvex；／*邻接顶点编号*／struct ArcNode*nextarc；／*指示下一个邻接顶点*／{ArcNode；typedef struct AdjList{ ／*头结点类型*／char vdata；／*顶点的数据信息*／ArcNode*firstarc；／*指向邻接表的第一个表结点*／}AdjList；typedef struct LinkedDigraph ／*图的类型*／int n：／*图中顶点个数*／AdjList Vhead[MAXVNUM]；／*所有顶点的头结点数组*／}LinkedDigraph；例如，某有向图G如图4-1所示，其邻接表如图4-2所示。函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示：【C代码】int*TopSort(LinkedDigraph G){ArcNode*P；／*临时指针，指示表结点*／Queue Q；／*临时队列，保存入度为0的顸点编号*／int k=0；／*临时变量，用作数组元素的下标*／int j=0，w=0；／*临时变量，用作顶点编号*／int*topOrder，*inDegree；topOrder=(int*)malloc((G．n+1)*sizeof(int))；／*存储拓扑序列中的顶点编号*／inDegree=(int*)malloc((G．n+1)*sizeof(int))；／*存储图G中各顶点的入度*／if(!inDegree｜｜!topOrder) return NULL；(1)；／*构造一个空队列*／for(j=1；j<=Gn；j++){ ／*初始化*／topOrder[j]=0；inDegree[j]=0；}for(j=1；j<=Gn；j++) ／*求图G中各顶点的入度*／for(p=G．Vhead[j]．firstarc；p；p=p->nextarc)inDegree[P->adjvex]+=1；for(j=i；j<=G．n；J++) ／*将图G中入度为0的顶点保存在队列中*／if(0==inDegree[j]) EnQueue(&Q，j)；while(! IsEmpty(Q)){(2); ／*队头顶点出队列并用w保存该顶点的编号*／topOrder[k++]=w；／*将顶点W的所有邻接顶点的入度减l(模拟删除顶点w及该顶点出发的弧的操作)*／for(p=G．Vhead[w]．firstarc；p；p=p->nextarc){(3)-=1；if(0== (4) ) EnQueue(&Q，P->adjvex)；}／*for*／｝/ * while*/free(inDegree)；if( (5) )return NULL；return topOrder；｝/*TopSort*/根据以上说明和C代码，填充C代码中的空(1)

4.如图所示的有向无环图可以得到的拓扑序列的个数是 ( )A．3B．4C．5D．6

更多“对于图4－1所示的有向图G,写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈, ”相关问题

第1题：

设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。
若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。

正确答案：(6)O(n+e) (7)O(n²)
(6)O(n+e) (7)O(n²) 解析：邻接表：对有n个顶点和e条弧的有向图而言，在拓扑排序中，若有向图无环，则每个顶点进出队列各一次，共执行e次，搜索算法时间复杂度是由n和e共同决定的，所以总的时间复杂度为O(n+e)。
当用邻接矩阵：对于每个顶点，查找相邻边的时间复杂度是O(n)，一共有n个顶点，所以总的时间复杂度是O(n²)。
第2题：

在程序的执行过程中，用______结构可以实现嵌套调用函数的正确返回。
A．队列
B．栈
C．树
D．图

正确答案：B
解析：栈是在同一端进行插入和删除运算的线性表，具有先进后出的特性。栈的这种特性正好适用函数嵌套调用的过程。(1)调用函数时：系统将为调用者构造一个由参数表和返回地址组成等信息的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则其活动记录还包括为局部变量分配的存储空间。(2)被调函数执行完毕时：系统将运行时刻栈顶的活动记录退栈，并根据退栈的活动记录中所保存的返回地址将程序的控制权转移给调用者继续执行。
第3题：

下列说法中正确的是（）。
A．在拓扑排序算法中，暂存入度为0的顶点可以用栈，也可以用队列。
B．AOV网的拓扑序列是唯一的。
C．若有向图的邻接矩阵中对角线以下元素均为0，则一定存在唯一的拓扑序列。
D．若一个有向图存在拓扑序列，则该图一定是强连通图。

在拓扑排序算法中，暂存入度为0的顶点可以用栈，也可以用队列。
第4题：

递归函数执行时，需要（）来提供支持。
A.栈
B.队列
C.有向图
D.二叉树

正确答案：A
第5题：

写出图题4-1的输出逻辑函数式。
图题4-1

答案：

相关内容