MCQ Quiz - CS - Algorithms - Graph Data Structures
* Required
Name
*
This is a required question
Full Address
*
This is a required question
Organisation Name
*
This is a required question
Email Address
*
(Your score will be emailed to you, so please fill correctly.)
This is a required question
You have an adjacency list for graph G, what is the time complexity to compute Graph transpose G^T
*
O (V+E)
O (V.E)
O (V)
O (E)
This is a required question
Suppose that a graph G = (V,E) is implemented using adjacency lists. What is the complexity of a breadth-first traversal of G?
*
O (|V |^2)
O (|V | |E|)
O (|V |^2|E|)
O (|V | + |E|)
This is a required question
What is generally true of Adjacency List and Adjacency Matrix representations of graphs?
*
Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
Lists require less space than matrices and they are faster to find the weight of an edge (v1, v2)
Lists require more space than matrices and they take longer to find the weight of an edge (v1, v2)
Lists require more space than matrices but are faster to find the weight of an edge (v1, v2)
This is a required question
Cross edge is:
*
(u, v) where u and v are not ancestor of one another
(u, v) where u is ancesstor of v and v is not descendent of u.
(u, v) where u and v are not ancestor or descendent of one another
(u, v) where u and v are either ancestor or descendent of one another.
This is a required question
Minimum no. of edges in a connected cyclic graph on n vertices is
*
n - 1
n
n + 1
None of the above
This is a required question
Which of the following is efficient in traversing a given graph by breadth first search?
*
List
Set
Stack
Queue
This is a required question
Maximum degree in any vector in a graph with n vertices is
*
n
n - 1
n + 1
2n - 1
This is a required question
A forest is
*
Set of n >= 0 joint trees which are connected with a root
Set of n >= 0 disjoint trees which are obtained when the root is removed
Set of n >= 0 disjoint nodes
None of the above
This is a required question
An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0‘s and (ii) non-diagonal elements are 1‘s. which one of the following is TRUE?
*
Graph G has no minimum spanning tree (MST)
Graph G has a unique MST of cost n-1
Graph G has multiple distinct MSTs, each of cost n-1
Graph G has multiple spanning trees of different costs
This is a required question
A digraph is strongly connected under what condition?
*
If for every pair of vertices u, v e V, u can reach v
If for every pair of vertices u, v e V, u can reach v and vice versa
If for at least one pair of vertex u, v e V, u can reach v and vice versa
If at least one third pair of vertices u, v e V, u can reach v and vice versa
This is a required question
Never submit passwords through Google Forms.