Have an account?
Skip to Content
Build your own quiz
Suggestions for you
30 questions
Show Answers
See Preview
- 1. Multiple Choice
BFT uses which data structure?
stack
tree
queue
hash
- 2. Multiple Choice
For the given graph(G), which of the following statements is true?
G is not a connected graph
The vertex connectivity of the graph is 2
G is a complete graph
The edge connectivity of the graph is 1
- 3. Multiple Choice
The depth first traversal of a graph will result into
Graph with back edges
Array
Linked List
Tree
- 4. Multiple Choice
Most Efficient Time Complexity of Topological Sorting is? (V – number of vertices, E – number of edges)
O(V + E)
O(V)
O(E)
O(V*E)
- 5. Multiple Choice
What is the time complexity of BFT? (v– number of vertices, e – number of edges)
O(e)
O(v*e)
O(v + e)
O(v)
- 6. Multiple Choice
Topological sort is equivalent to which of the traversals in trees?
Pre-order traversal
Post-order traversal
In-order traversal
Level-order traversal
- 7. Multiple Choice
The given Graph is regular. True or False?
True
False
- 8. Multiple Choice
BFS follow
first in last out
first in first out
last in first out
- 9. Multiple Choice
What is the space complexity for DFT?
O(v)
O(v + e)
O(e)
O(v*e)
- 10. Multiple Choice
What is the number of edges present in a complete graph having n vertices?
n
(n*(n+1))/2
(n*(n-1))/2
(n*(n-1))
- 11. Multiple Choice
DFT is equivalent to which of the traversal in the Binary Trees?
Post-order traversal
In-order traversal
Pre-order traversal
Level-order traversal
- 12. Multiple Choice
Which of the following is not an application of BFT?
GPS navigation
Peer to Peer network
Finding bipartiteness of a graph
Finding shortest path between two nodes
- 13. Multiple Choice
Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?
BFT
Prim's Minimum Spanning Tree Algorithm
Kruskal's Minimum Spanning Tree Algorithm
DFT
- 14. Multiple Choice
The maximum degree of any vertex in a single graph with N vertices is
N
N-1
N+1
2N+1
- 15. Multiple Choice
A graph G is called a ________ if it is a connected acyclic graph?
Cyclic graph
Regular graph
Tree
Not a graph
- 16. Multiple Choice
For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is
ne
2n
2e
e^n
- 17. Multiple Choice
Graph traversal is different from a tree traversal, because
Trees are not connected
Graphs may have loops
Trees have roots
None of these
- 18. Multiple Choice
Graphs are represented using ___________
Adjacency tree
Adjacency linked list
Adjacency graph
Adjacency queue
- 19. Multiple Choice
A graph having an edge from each vertex to every other vertex is called a ___________
Tightly Connected
Strongly Connected
Weakly Connected
Loosely Connected
- 20. Multiple Choice
Consider the following graph.
If we run breadth first search on this graph starting at any vertex, which one of the following is a possible order for visiting the nodes ?
MNOPQR
NQMPOR
QMNPRO
QMNPOR
- 21. Multiple Choice
Which of the following is not a topological ordering of the following graph ?
123456
132456
132645
324165
- 22. Multiple Choice
In the given graph identify the cut vertices.
A and D
B and C
E and D
C and E
- 23. Multiple Choice
What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?
(n*(n+1))/2
n*(n+1)
(n*(n-1))/2
n*(n-1)
- 24. Multiple Choice
A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
15
1
3
11
- 25. Multiple Choice
On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?
Depends on the number of vertices
Depends on the number of edges
It depends on both the number of edges and vertices
Is independent of both the number of edges and vertices
- 26. Multiple Choice
Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degrees of all vertices is even
P Only
Q Only
Both P and Q
Neither P nor Q
- 27. Multiple Choice
What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
n
n-2
0
2
- 28. Multiple Choice
This graph will have a Euler's Circuit. True or False?
True
False
- 29. Multiple Choice
Which of the following is useful in traversing a given graph by breadth first search?
List
Set
Queue
Stack
- 30. Multiple Choice
In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices. True or False?
True
False
- Answer choicesTagsAnswer choicesTags