Quiz
13. Graph Topoligical Sorting
Create a free account to finish this quiz
Save your progress and see your final score.
Already have an account? Sign in
Questions in this quiz (15)
1a topological sort can be done on a cyclic graph.
- ATrue
- BFalse
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
- ATrue
- BFalse
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?
- ATrue
- BFalse
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.- ATrue
- BFalse
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
Information
- Description
- Algorithms and Data Structures | Test 3 Review | CSCI-3110-002 MTSU
- Author
- Mena Sargios
- Language
- English
- Views
- 54
- Tags
- Rating
- No ratings yet Rate this quiz