Test
13. Graph Topoligical Sorting
Crea una cuenta gratis para terminar este test
Guarda tu progreso y consulta tu resultado final.
¿Ya tienes cuenta? Inicia sesión
Preguntas del test (15)
1a topological sort can be done on a cyclic graph.
- AVerdadero
- BFalso
2Select the correct definition.
Topological sorting:- AA) Given a cyclic digraph find a linear ordering of vertices such
that for all edges (v, w) in E, v procedes w in the ordering. - BB) Given an acyclic undirected graph find a linear ordering of nodes
such that for all vertices (v, w) in E, v proceeds w in the ordering - CC) Given an acyclic digraph find a quadratic ordering of nodes such
that for all edges (v, w) in E, v proceeds w in the ordering. - DD) Given an acyclic digraph find a linear ordering of nodes such
that for all edges (v, w) in E, v proceeds w in the ordering.
- AA) Given a cyclic digraph find a linear ordering of vertices such
3What is Topological Sorting?
- AIt is finding an ordering of an acyclic graph such that all edges proceed in order.
- Bnone of the above
4What is not part of algorithm for topological graph?
- AA. make a copy of the diagram
- BB.make a list l
- CC.make a q list
- DD.none of the above
5Any linear ordering of all of the vertices in which all the arrows go to the right is a valid solution.
The statemen is an example of:- AA.Big o notation
- BB.Ascending
- CC.Topological
- DD.Descending
6In the topological algorithm once you select a vertex V with an out outdegree of 0, where do you place the V in the list?
- AA) to the front of the list
- BB) the end of the list
- CC) the middle of the list
7The algorithm for topological sorting includes
- Aa. making a copy of the graph
- Bb. initializing a list
- Cc. selecting a vertex with an out degree of 0
- Dd. all of the above.
8What is any linear ordering of all of the verticies of a graph in which all
the arrows go to the right is a valid solution?- AA) Topological Sorting
- BB) Top-Down Sorting
- CC) Quick Sorting
- DD) None of the above
9Any linear Ordering of all vertices where all the arrows point to the left is a valid solution
- AVerdadero
- BFalso
10In order to perform a topilogical sort, the graph must be:
- AA. Cyclic
- BB. Acyclic
- CC. A tree
- DD. None of the above
11For any given directed acyclic graph, there could be ______ valid topological sorts.
- AA. only one
- BB. only two
- CC. many
- DD. none - topological sorts only work in cyclic graphs
12In an example of topological orders, which of the following is correct?
- AA. any nonlinear ordering of all of the vertices in which all the arrows go to the right
- BB. any linear ordering of all of the vertices in which all the arrows go to the right
- CC. any linear ordering of all of the vertices in which all the arrows go to the left
- DD. any linear ordering of all of the vertices in which all the arrows are static
13Is topological sorting possible if and only if the graph has no directed cycles?
- AVerdadero
- BFalso
14Is the example topological orders true or false?
Any linear ordering of all of the vertices in which all the arrows go to the
right is a valid solution.- AVerdadero
- BFalso
15Given this sudo-method:
list digraph::topoSort()
{
// make a copy of digraph G
// make a list l
// for each vertex in G
// select a vertex v with an outdegree of 2
// add v to the front of l
// delete v and it's edges from the digraph
}
What is the problem with this method?
- AWhen selecting a vertex to add to the sorted list, you must select a vertex with an outdegree of 0.
- Bnone of the above
Información
- Descripción
- Algorithms and Data Structures | Test 3 Review | CSCI-3110-002 MTSU
- Autor
- Mena Sargios
- Idioma
- English
- Visitas
- 54
- Etiquetas
- Valoración
- Aún sin valoraciones Valora este test