A graph with no edges is known as empty graph
A. True
B. False
ANSWER: A
Degree of any vertex of a graph is
A. Number of vertices in a graph
B. The number of edges incident with the vertex
C. Number of edges in a graph
D. Number of vertices adjacent to that vertices
ANSWER: B
If the origin and terminus of a walk are same, the walk is known as
A. Open
B. Closed
C. Path
D. None of these
ANSWER: B
The complete graph with 4 vertices has k edges where k is
A. 3
B. 4
C. 5
D. 6
ANSWER: D
A graph with one vertex and no edges is
A. Multigraph
B. Digraph
C. Isolated graph
D. Trivial graph
ANSWER: D
Breadth First Search is equivalent to which of the traversal in the Binary Trees?
A. Pre-order Traversal
B. Post-order Traversal
C. Level-order Traversal
D. In-order Traversal
ANSWER: C
Time Complexity of Breadth First Search is? (V – number of vertices, E – number of
edges)
A. O(V + E)
B. O(V)
C. O(E)
D. O(V*E)
ANSWER: A
The Data structure used in standard implementation of Breadth First Search is?
A. Stack
B. Queue
C. Linked List
D. Tree
ANSWER: B
The Breadth First Search traversal of a graph will result into?
A. Linked List
B. Tree
C. Graph with back edges
D. Arrays
ANSWER: B
Which of the following is not an application of Breadth First Search?
A. Finding shortest path between two nodes
B. Finding bipartiteness of a graph
C. GPS navigation system
D. Path Finding
ANSWER: D
The Data structure used in standard implementation of Breadth First Search is?
A. Tree
B. Linked List
C. Queue
D. Stack
ANSWER: D
When the Depth First Search of a graph is unique?
A. When the graph is a Binary Tree
B. When the graph is a Linked List
C. When the graph is a n-ary Tree
D. When the graph is a ternary Tree
ANSWER: B
In Depth First Search, how many times a node is visited?
A. Once
B. Twice
C. Equivalent to number of indegree of the node
D. Thrice
ANSWER: C
A vertex in a graph, on the removal of whose increases the number of connected
components is called?
A. Articulation point
B. Bridge
C. Edge connectivity
D. Independent set
ANSWER: A
Which of the following algorithm can be used for finding articulation points in a
graph?
A. Simplex algorithm
B. Aging algorithm
C. Tarjan’s algorithm
D. DSW algorithm
ANSWER: C
In which of the following applications can we use the concept of articulation
points?
A. Designing a microprocessor
B. Designing a router
C. Designing a network
D. Designing a building
ANSWER: C
Which of the following algorithm design techniques is used in the quick sort
algorithm?
Dynamic programming
B. Backtracking
C. Divide and conquer
D. Greedy method
ANSWER: C
Which of the following sorting algorithms is the fastest?
A. Merge sort
B. Quick sort
C. Insertion sort
D. Shell sort
ANSWER: B
What is the worst case time complexity of a quick sort algorithm?
A. O(N)
B. O(N log N)
C. O(N2)
D. O(log N)
ANSWER: C
Which of the following sorting algorithms is used along with quick sort to sort the
sub arrays?
A. Merge sort
B. Shell sort
C. Insertion sort
D. Bubble sort
ANSWER: C
What is the advantage of recursive approach than an iterative approach?
A. Consumes less memory
B. Less code and easy to implement
C. Consumes more memory
D. More code has to be written
ANSWER: B
Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid
values(corresponding array elements) in the first and second levels of recursion?
A. 90 and 99
B. 90 and 94
C. 89 and 99
D. 89 and 94
ANSWER: A
What is the worst case complexity of binary search using recursion?
A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n2)
ANSWER: B
Which of the following is not an application of binary search?
A. To find the lower/upper bound in an ordered sequence
B. Union of intervals
C. Debugging
D. To search in unordered list
ANSWER: D
Merge sort uses which of the following technique to implement sorting?
A. backtracking
B. greedy algorithm
C. divide and conquer
D. dynamic programming
ANSWER: C
What is the average case time complexity of merge sort?
A. O(n log n)
B. O(n2)
C. O(n2 log n)
D. O(n log n2)
ANSWER: A
Which of the following method is used for sorting in merge sort?
A. merging
B. partitioning
C. selection
D. exchanging
ANSWER: A
Strassen’s algorithm is a/an_____________ algorithm.
A. Non- recursive
B. Recursive
C. Approximation
D. Accurate
ANSWER: B
Strassen’s matrix multiplication algorithm follows ___________ technique.
A. Greedy technique
B. Dynamic Programming
C. Backtracking
D. Divide and Conquer
ANSWER: D
What is the recurrence relation used in Strassen’s algorithm?
A. 7T(n/2) + Theta(n2)
B. 8T(n/2) + Theta(n2)
C. 7T(n/2) + O(n2)
D. 8T(n/2) + O(n2)
ANSWER: A
