Data Structure And Algorithm

Sorting
1. How many passes does an insertion sort algorithm consist of?
a) N
b) N-1
c) N+1
d) N2
Answer:b) N-1

2. Which of the following algorithm implementations is similar to that of an insertion sort?

a) Binary heap
b) Quick sort
c) Merge sort
d) Radix sort
Answer:a) Binary heap

3. What is the average case running time of an insertion sort algorithm?

a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Answer:d) O(N2)

4. What is the average number of inversions in an array of N distinct numbers?

a) N(N-1)/4
b) N(N+1)/2
c) N(N-1)/2
d) N(N-1)/3
Answer:a) N(N-1)/4
.
5. What is the running time of an insertion sort algorithm if the input is pre-sorted?
a) O(N2)
b) O(N log N)
c) O(N)
d) O(M log N)
Answer:c) O(N)

6. What will be the number of passes to sort the elements using insertion sort?
14, 12,16, 6, 3, 10
a) 6
b) 5
c) 7
d) 1
Answer:b) 5

7. For the following question, how will the array elements look like after second pass?
34, 8, 64, 51, 32, 21
a) 8, 21, 32, 34, 51, 64
b) 8, 32, 34, 51, 64, 21
c) 8, 34, 51, 64, 32, 21
d) 8, 34, 64, 51, 32, 21
Answer:d) 8, 34, 64, 51, 32, 21

8. Which of the following real time examples is based on insertion sort?

a) arranging a pack of playing cards
b) database scenarios and distributes scenarios
c) arranging books on a library shelf
d) real-time systems
Answer:a) arranging a pack of playing cards

9. In C, what are the basic loops required to perform an insertion sort?

a) do- while
b) if else
c) for and while
d) for and if
Answer:c) for and while

10. Which of the following options contain the correct feature of an insertion sort algorithm?
a) anti-adaptive
b) dependable
c) stable, not in-place
d) stable, adaptive
Answer:d) stable, adaptive

11. Which of the following sorting algorithms is the fastest for sorting small arrays?
a) Quick sort
b) Insertion sort
c) Shell sort
d) Heap sort
Answer:b) Insertion sort

12. For the best case input, the running time of an insertion sort algorithm is?
a) Linear
b) Binary
c) Quadratic
d) Depends on the input
Answer:a) Linear

13. Which of the following examples represent the worst case input for an insertion sort?
a) array in sorted order
b) array sorted in reverse order
c) normal unsorted array
d) large array
Answer:b) array sorted in reverse order

14. Which of the following is correct with regard to insertion sort?

a) insertion sort is stable and it sorts In-place
b) insertion sort is unstable and it sorts In-place
c) insertion sort is stable and it does not sort In-place
d) insertion sort is unstable and it does not sort In-place
Answer:a) insertion sort is stable and it sorts In-place

15. Which of the following sorting algorithm is best suited if the elements are already
sorted?
a) Heap Sort
b) Quick Sort
c) Insertion Sort
d) Merge Sort
Answer:c) Insertion Sort

16. Which of the following is good for sorting arrays having less than 100 elements?
a) Quick Sort
b) Selection Sort
c) Merge Sort
d) Insertion Sort
Answer:d) Insertion Sort

17. Which of the following is not an exchange sort?

a) Bubble Sort
b) Quick Sort
c) Partition-exchange Sort
d) Insertion Sort
Answer:d) Insertion Sort

18. What is an in-place sorting algorithm?

a) It needs O(1) or O(logn) memory to create auxiliary locations
b) The input is already sorted and in-place
c) It requires additional storage
d) It requires additional space
Answer:a) It needs O(1) or O(logn) memory to create auxiliary locations

19. In the following scenarios, when will you use selection sort?
a) The input is already sorted
b) A large file has to be sorted
c) Large values need to be sorted with small keys
d) Small values need to be sorted with large keys
Answer:c) Large values need to be sorted with small keys

20. What is the worst case complexity of selection sort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:d) O(n2)

21. What is the advantage of selection sort over other sorting techniques?
a) It requires no additional storage space
b) It is scalable
c) It works best for inputs which are already sorted
d) It is faster than any other sorting technique
Answer:a) It requires no additional storage space

22. What is the average case complexity of selection sort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:d) O(n2)

23. What is the disadvantage of selection sort?

a) It requires auxiliary memory
b) It is not scalable
c) It can be used for small keys
d) It takes linear time to sort the elements
Answer:b) It is not scalable

24. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection
sort respectively are __________
a) 5 and 4
b) 4 and 5
c) 2 and 4
d) 2 and 5
Answer:a) 5 and 4

25. What is the best case complexity of selection sort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:d) O(n2)

26. What is an external sorting algorithm?

a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
Answer: a) Algorithm that uses tape or disk during the sort

27. What is an internal sorting algorithm?

a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
Answer:b) Algorithm that uses main memory during the sort

28. What is the worst case complexity of bubble sort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:d) O(n2)

29. What is the average case complexity of bubble sort?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:d) O(n2)

30. Which of the following is not an advantage of optimised bubble sort over other sorting
techniques in case of sorted elements?
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) Consumes less time
Answer:c) Detects whether the input is already sorted

31. 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) divide and conquer

32. Which of the following method is used for sorting in merge sort?
a) merging
b) partitioning
c) selection
d) exchanging
Answer:a) merging

33. Which of the following is not a variant of merge sort?

a) in-place merge sort
b) bottom up merge sort
c) top down merge sort
d) linear merge sort
Answer:d) linear merge sort
34. Choose the incorrect statement about merge sort from the following?
a) it is a comparison based sort
b) it is an adaptive algorithm
c) it is not an in place algorithm
d) it is stable algorithm
Answer:b) it is an adaptive algorithm

35. Which of the following is not in place sorting algorithm by default?

a) merge sort
b) quick sort
c) heap sort
d) insertion sort
Answer:a) merge sort

36. Which of the following is not a stable sorting algorithm?

a) Quick sort
b) Cocktail sort
c) Bubble sort
d) Merge sort
Answer:a) Quick sort

37. Which of the following stable sorting algorithm takes the least time when applied to an
almost sorted array?
a) Quick sort
b) Insertion sort
c) Selection sort
d) Merge sort
Answer:d) Merge sort

38. Merge sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
Answer:c) divide and conquer

39. Merge sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging
Answer:a) merging

40. Which of the following sorting algorithms is the fastest?

a) Merge sort
b) Quick sort
c) Insertion sort
d) Shell sort
Answer:b) Quick sort
42. Which of the following methods is the most effective for picking the pivot element?
a) first element
b) last element
c) median-of-three partitioning
d) random element
Answer:c) median-of-three partitioning

43. How many sub arrays does the quick sort algorithm divide the entire array into?
a) one
b) two
c) three
d) four
Answer:b) two

44. Which is the worst method of choosing a pivot element?

a) first element as pivot
b) last element as pivot
c) median-of-three partitioning
d) random element as pivot
Answer:a) first element as pivot

45. Quick sort is a __________

a) greedy algorithm
b) divide and conquer algorithm
c) dynamic programming algorithm
d) backtracking algorithm
Answer:b) divide and conquer algorithm

46. Which one of the following sorting algorithm is best suited to sort an array of 1 million
elements?
a) Bubble sort
b) Insertion sort
c) Merge sort
d) Quick sort
Answer: d) Quick sort

47. Quick sort is a space-optimised version of ____

a) Bubble sort
b) Selection sort
c) Insertion sort
d) Binary tree sort
Answer:d) Binary tree sort

48. QuickSort can be categorized into which of the following?

a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming
Answer:b) Divide and conquer

49. Which of the following is not true about QuickSort?

a) in-place algorithm
b) pivot position can be changed
c) adaptive sorting algorithm
d) can be implemented as a stable sort
Answer:b) pivot position can be changed

50. On which algorithm is heap sort based on?

a) Fibonacci heap
b) Binary tree
c) Priority queue
d) FIFO
Answer:c) Priority queue

51. How many arrays are required to perform deletion operation in a heap?
a) 1
b) 2
c) 3
d) 4
Answer:b) 2

52. Heap sort is an implementation of ____________ using a descending priority queue.

a) insertion sort
b) selection sort
c) bubble sort
d) merge sort
Answer:b) selection sort

53. Which one of the following is false?

a) Heap sort is an in-place algorithm
b) Heap sort has O(nlogn) average case time complexity
c) Heap sort is stable sort
d) Heap sort is a comparison-based sorting algorithm
Answer:c) Heap sort is stable sort

54. Which one of the following is a variation of Heap sort?

a) Comb sort
b) Smooth sort
c) Binary tree sort
d) Shell sort
Answer:b) Smooth sort
.
55. Introsort algorithm is combination of _____________
a) Quick sort and Heap sort
b) Quick sort and Shell sort
c) Heap sort and Merge sort
d) Heap sort and insertion sort
Answer:a) Quick sort and Heap sort

56. What is the alternate name of bucket sort?

a) group sort
b) radix sort
c) bin sort
d) uniform sort
Answer:c) bin sort

57. Which of the following non-comparison sort can also be considered as a comparison
based sort?
a) counting sort
b) MSD radix sot
c) bucket sort
d) pigeonhole sort
Answer:c) bucket sort

58. Which of the following is not true about bucket sort?

a) It is a non comparison based integer sort
b) It is a distribution sort
c) It can also be considered as comparison based sort
d) It is in place sorting algorithm
Answer:d) It is in place sorting algorithm

59. Which of the following don’t affect the time complexity of bucket sort?
a) algorithm implemented for sorting individual buckets
b) number of buckets used
c) distribution of input
d) input values
Answer:d) input values
.
60. Bucket sort is most efficient in the case when __________
a) the input is non uniformly distributed
b) the input is uniformly distributed
c) the input is randomly distributed
d) the input range is large
Answer:b) the input is uniformly distributed

61. Bucket sort is a generalization of which of the following sort?

a) LSD radix sort
b) Pigeonhole sort
c) Counting sort
d) MSD radix sort
Answer:b) Pigeonhole sort

62. Which of the following is the distribution sort?

a) Heap sort
b) Smooth sort
c) Quick sort
d) LSD radix sort

Answer: d) LSD radix sort

63. Which of the following sorting algorithm is stable?

a) Heap sort
b) Selection sort
c) In-place MSD radix sort
d) LSD radix sort
Answer:d) LSD radix sort

64. Which of the following is true for the LSD radix sort?
a) works best for variable length strings
b) accesses memory randomly
c) inner loop has less instructions
d) sorts the keys in left-to-right order
Answer:b) accesses memory randomly

65. What is the full form of MSD in MSD radix sort?

a) most significant digit
b) many significant digit
c) more significant digit
d) must significant digit
Answer:a) most significant digit

66. Which of the following combines qualities of MSD radix sort and LSD radix sort?
a) in-place MSD radix sort
b) stable MSD radix sot
c) 3 way radix quick sort
d) forward radix sort
Answer:d) forward radix sort

67. Which of the following is an alternate name of MSD radix sort?

a) bottom up radix sort
b) top down radix sort
c) forward radix sort
d) backward radix sort
Answer:b) top down radix sort

68. Which of the following is not true about MSD radix sort?
a) its processing starts from the most significant digit
b) it is not a stable sort
c) it is an in place sorting algorithm
d) it is non comparison based sort
Answer:c) it is an in place sorting algorithm
69. Which of the following statement is not a stable sorting algorithm?
a) LSD radix sort
b) MSD radix sort
c) Counting sort
d) Pigeonhole sort
Answer:b) MSD radix sort

Search
1. Where is linear searching used?
a) When the list has only a few elements
b) When performing a single search in an unordered list
c) Used all the time
d) When the list has only a few elements and When performing a single search in an
unordered list
Answer:d) When the list has only a few elements and When performing a single search in
an unordered list

2. What is the best case for linear search?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer:d) O(1)

3. What is the worst case for linear search?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer:c) O(n)

4. What is the best case and worst case complexity of ordered linear search?
a) O(nlogn), O(logn)
b) O(logn), O(nlogn)
c) O(n), O(1)
d) O(1), O(n)
Answer:d) O(1), O(n)

5. Which of the following is a disadvantage of linear search?

a) Requires more space
b) Greater time complexities compared to other searching algorithms
c) Not easy to understand
d) Not easy to implement
Answer:b) Greater time complexities compared to other searching algorithms

6. Is there any difference in the speed of execution between linear serach(recursive) vs

linear search(lterative)?
a) Both execute at same speed
b) Linear search(recursive) is faster
c) Linear search(Iterative) is faster
d) Cant be said
Answer:c) Linear search(Iterative) is faster

7. Is the space consumed by the linear search(recursive) and linear search(iterative) same?
a) No, recursive algorithm consumes more space
b) No, recursive algorithm consumes less space
c) Yes
d) Nothing can be said
Answer:a) No, recursive algorithm consumes more space

8. What is the worst case runtime of linear search(recursive) algorithm?

a) O(n)
b) O(logn)
c) O(n2)
d) O(nx)
Answer:a) O(n)

9. Linear search(recursive) algorithm used in _____________

a) When the size of the dataset is low
b) When the size of the dataset is large
c) When the dataset is unordered
d) Never used
Answer:a) When the size of the dataset is low

10. Can linear search recursive algorithm and binary search recursive algorithm be
performed on an unordered list?
a) Binary search can’t be used
b) Linear search can’t be used
c) Both cannot be used
d) Both can be used
Answer:a) Binary search can’t be used

11. What is the recurrence relation for the linear search recursive algorithm?
a) T(n-2)+c
b) 2T(n-1)+c
c) T(n-1)+c
d) T(n+1)+c
Answer:c) T(n-1)+c

12. 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) Less code and easy to implement
13. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
a) 5
b) 2
c) 3
d) 4
Answer: c) 3
14. 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) O(logn)

15. What is the average case time complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:b) O(logn)

16. 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) To search in unordered list

17. Binary Search can be categorized into which of the following?

a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming
Answer: b) Divide and conquer

18. What is the time complexity of binary search with iteration?

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:b) O(logn)

19. In which of the cases uniform binary search fails compared to binary search?
a) A table lookup is generally faster than an addition and a shift
b) Many searches will be performed on the same array
c) Many searches will be performed on several arrays of the same length
d) Complexity of code
Answer:d) Complexity of code
20. Given delta[4] is a global array and number of elements in the sorted array is 10, what
are the values in the delta array?
a) 4, 3, 1, 0
b) 5, 3, 1, 0
c) 4, 2, 1, 1
d) 5, 2, 1, 1
Answer: b) 5, 3, 1, 0
21. What is the time complexity of uniform binary search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer:b) O(logn)

22. How can Jump Search be improved?

a) Start searching from the end
b) Begin from the kth item, where k is the step size
c) Cannot be improved
d) Step size should be other than sqrt(n)
Answer: b) Begin from the kth item, where k is the step size

23. Which of the following false about Jump Search?

a) Jump Search is better than Linear Search
b) Useful when jumping back is more costly than jumping forward
c) Jump Search is worse than Binary Search
d) Jump search starts from the index 0 even though specified index is k
Answer:d) Jump search starts from the index 0 even though specified index is k

24. Depth 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: a) Pre-order Traversal
.
25. Time Complexity of DFS 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) O(V + E)

26. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree
Answer: a) Stack
27. The Depth First Search traversal of a graph will result into?
a) Linked List
b) Tree
c) Graph with back edges
d) Array
Answer: b) Tree

28. A person wants to visit some places. He starts from a vertex and then wants to visit
every vertex till it finishes from one vertex, backtracks and then explore other vertex from
same vertex. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s Algorithm
Answer: a) Depth First Search

29. Which of the following is not an application of Depth First Search?

a) For generating topological sort of a graph
b) For generating Strongly Connected Components of a directed graph
c) Detecting cycles in the graph
d) Peer to Peer Networks
Answer: d) Peer to Peer Networks
.
30. 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) When the graph is a Linked List

31. Regarding implementation of Depth First Search using stacks, what is the maximum
distance between two nodes present in the stack? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information
Answer: a) Can be anything

32. 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) Equivalent to number of indegree of the node

33. 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) Level-order Traversal

34. 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) O(V + E)

35. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree
Answer: b) Queue

36. 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) Tree

37. A person wants to visit some places. He starts from a vertex and then wants to visit
every place connected to this vertex and so on. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s algorithm
Answer: b) Breadth First Search

38. 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) Path Finding

39. When the Breadth 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) When the graph is a Linked List

40. In BFS, how many times a node is visited?

a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) Thrice
Answer: c) Equivalent to number of indegree of the node

41. Branch and bound is a __________

a) problem solving technique
b) data structure
c) sorting algorithm
d) type of tree
Answer: a) problem solving technique

42. Which of the following is not a branch and bound strategy to generate branches?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: d) Highest cost branch and bound

43. Which data structure is used for implementing a LIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
Answer: a) stack

44. Which data structure is used for implementing a FIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
Answer: b) queue

45. Which data structure is most suitable for implementing best first branch and bound
strategy?
a) stack
b) queue
c) priority queue
d) linked list
Answer: c) priority queue

46. Which of the following branch and bound strategy leads to breadth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: b) FIFO branch and bound
47. Which of the following branch and bound strategy leads to depth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: a) LIFO branch and bound

48. Choose the correct statement from the following.

a) branch and bound is more efficient than backtracking
b) branch and bound is not suitable where a greedy algorithm is not applicable
c) branch and bound divides a problem into at least 2 new restricted sub problems
d) backtracking divides a problem into at least 2 new restricted sub problems
Answer: c) branch and bound divides a problem into at least 2 new restricted sub problems

49. Which of the following can traverse the state space tree only in DFS manner?
a) branch and bound
b) dynamic programming
c) greedy algorithm
d) backtracking
Answer: d) backtracking

50. Which of the following is false in the case of a spanning tree of a graph G?
a) It is tree that spans G
b) It is a subgraph of the G
c) It includes every vertex of the G
d) It can be either cyclic or acyclic
Answer:d) It can be either cyclic or acyclic

51. Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees.
a) 15
b) 8
c) 16
d) 13
Answer:c) 16

52. The travelling salesman problem can be solved using _________

a) A spanning tree
b) A minimum spanning tree
c) Bellman – Ford algorithm
d) DFS traversal
Answer:b) A minimum spanning tree

53. Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the
following is true?
a)Graph M has no minimum spanning tree
b) Graph M has a unique minimum spanning trees of cost 2
c) Graph M has 3 distinct minimum spanning trees, each of cost 2
d) Graph M has 3 spanning trees of different costs
Answer: c) Graph M has 3 distinct minimum spanning trees, each of cost 2

54. Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has
distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum
weight. Then, which of the following is false?
a) Every minimum spanning tree of G must contain CD
b) If AB is in a minimum spanning tree, then its removal must disconnect G
c) No minimum spanning tree contains AB
d) G has a unique minimum spanning tree
Answer:c) No minimum spanning tree contains AB

55. Consider the graph shown below. Which of the following are the edges in the MST of
the given graph?

a) (a-c)(c-d)(d-b)(d-b)
b) (c-a)(a-d)(d-b)(d-e)
c) (a-d)(d-c)(d-b)(d-e)
d) (c-a)(a-d)(d-c)(d-b)(d-e)
Answer:c) (a-d)(d-c)(d-b)(d-e)

56. Which of the following is not the algorithm to find the minimum spanning tree of the
given graph?
a) Boruvka’s algorithm
b) Prim’s algorithm
c) Kruskal’s algorithm
d) Bellman–Ford algorithm
Answer:d) Bellman–Ford algorithm

57. Which of the following is false?

a) The spanning trees do not have any cycles
b) MST have n – 1 edges if the graph has n edges
c) Edge e belonging to a cut of the graph.
d) Removing one edge from the spanning tree will not make the graph disconnected
Answer:d) Removing one edge from the spanning tree will not make the graph
disconnected

Algorithm
1. Kruskal’s algorithm is used to ______
a) find minimum spanning tree
b) find single source shortest path
c) find all pair shortest path algorithm
d) traverse the graph
Answer:a) find minimum spanning tree

2. Kruskal’s algorithm is a ______

a) divide and conquer algorithm
b) dynamic programming algorithm
c) greedy algorithm
d) approximation algorithm
Answer:c) greedy algorithm

3. Consider the given graph.

What is the weight of the minimum spanning tree using the Kruskal’s algorithm?
a) 24
b) 23
c) 15
d) 19
Answer:d) 19

4. What is the time complexity of Kruskal’s algorithm?

a) O(log V)
b) O(E log V)
c) O(E2)
d) O(V log E)
Answer:b) O(E log V)

5. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected
first?

a) GF
b) DE
c) BE
d) BG
Answer:c) BE

6. Which of the following edges form minimum spanning tree on the graph using kruskals
algorithm?

a) (B-E)(G-E)(E-F)(D-F)
b) (B-E)(G-E)(E-F)(B-G)(D-F)
c) (B-E)(G-E)(E-F)(D-E)
d) (B-E)(G-E)(E-F)(D-F)(D-G)
Answer:a) (B-E)(G-E)(E-F)(D-F)

7. Which of the following is true?

a) Prim’s algorithm can also be used for disconnected graphs
b) Kruskal’s algorithm can also run on the disconnected graphs
c) Prim’s algorithm is simpler than Kruskal’s algorithm
d) In Kruskal’s sort edges are added to MST in decreasing order of their weights

Answer:b) Kruskal’s algorithm can also run on the disconnected graphs

8. Which of the following is false about the Kruskal’s algorithm?

a) It is a greedy algorithm
b) It constructs MST by selecting edges in increasing order of their weights
c) It can accept cycles in the MST
d) It uses union-find data structure
Answer:c) It can accept cycles in the MST

9. Consider the following statements.

S1. Kruskal’s algorithm might produce a non-minimal spanning tree.
S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
a) S1 is true but S2 is false
b) Both S1 and S2 are false
c) Both S1 and S2 are true
d) S2 is true but S1 is false
Answer:d) S2 is true but S1 is false

10. Which of the following is true?

a) Prim’s algorithm initialises with a vertex
b) Prim’s algorithm initialises with a edge
c) Prim’s algorithm initialises with a vertex which has smallest edge
d) Prim’s algorithm initialises with a forest
Answer:a) Prim’s algorithm initialises with a vertex

11. Consider the given graph.

What is the weight of the minimum spanning tree using the Prim’s algorithm,starting from
vertex a?
a) 23
b) 28
c) 27
d) 11
Answer:c) 27

12. Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is
used?
a) O(log V)
b) O(V2)
c) O(E2)
d) O(V log E)
Answer:b) O(V2)

13. Prim’s algorithm is a ______

a) Divide and conquer algorithm
b) Greedy algorithm
c) Dynamic Programming
d) Approximation algorithm
Answer:b) Greedy algorithm

14. Consider the graph shown below.

Which of the following edges form the MST of the given graph using Prim’a algorithm,
starting from vertex 4.
a) (4-3)(5-3)(2-3)(1-2)
b) (4-3)(3-5)(5-1)(1-2)
c) (4-3)(3-5)(5-2)(1-5)
d) (4-3)(3-2)(2-1)(1-5)
Answer:d) (4-3)(3-2)(2-1)(1-5)

15. Prim’s algorithm is also known as __________

a) Dijkstra–Scholten algorithm
b) Borůvka’s algorithm
c) Floyd–Warshall algorithm
d) DJP Algorithm
Answer:d) DJP Algorithm

16. Prim’s algorithm can be efficiently implemented using _____ for graphs with greater
density.
a) d-ary heap
b) linear search
c) fibonacci heap
d) binary search
Answer:a) d-ary heap

17. Which of the following is false about Prim’s algorithm?

a) It is a greedy algorithm
b) It constructs MST by selecting edges in increasing order of their weights
c) It never accepts cycles in the MST
d) It can be implemented using the Fibonacci heap
Answer:b) It constructs MST by selecting edges in increasing order of their weights

18. Dijkstra’s Algorithm is used to solve _____________ problems.

a) All pair shortest path
b) Single source shortest path
c) Network flow
d) Sorting
Answer: b) Single source shortest path

19. Which of the following is the most commonly used data structure for implementing
Dijkstra’s Algorithm?
a) Max priority queue
b) Stack
c) Circular queue
d) Min priority queue
Answer: d) Min priority queue

20. What is the time complexity of Dijikstra’s algorithm?

a) O(N)
b) O(N3)
c) O(N2)
d) O(logN)
Answer: c) O(N2)

21. Dijkstra’s Algorithm cannot be applied on ______________

a) Directed and weighted graphs
b) Graphs having negative weight function
c) Unweighted graphs
d) Undirected and unweighted graphs
Answer: b) Graphs having negative weight function
22. How many priority queue operations are involved in Dijkstra’s Algorithm?
a) 1
b) 3
c) 2
d) 4
Answer: b) 3

23. How many times the insert and extract min operations are invoked per vertex?
a) 1
b) 2
c) 3
d) 0
Answer: a) 1

24. The maximum number of times the decrease key operation performed in Dijkstra’s
algorithm will be equal to ___________
a) Total number of vertices
b) Total number of edges
c) Number of vertices – 1
d) Number of edges – 1
Answer: b) Total number of edges

25. What is running time of Dijkstra’s algorithm using Binary min- heap method?
a) O(V)
b) O(VlogV)
c) O(E)
d) O(ElogV)
Answer: d) O(ElogV)

26. Consider the following graph.

If b is the source vertex, what is the minimum cost to reach f vertex?

a) 8
b) 9
c) 4
d) 6
Answer: d) 6
27. In the given graph, identify the shortest path having minimum cost to reach vertex E if A
is the source vertex.

a) a-b-e
b) a-c-e
c) a-c-d-e
d) a-c-d-b-e
Answer: b) a-c-e

28. Dijkstra’s Algorithm is the prime example for ___________

a) Greedy algorithm
b) Branch and bound
c) Back tracking
d) Dynamic programming
Answer: a) Greedy algorithm
29. The Bellmann Ford algorithm returns _______ value.
a) Boolean
b) Integer
c) String
d) Double
Answer: a) Boolean

30. Bellmann ford algorithm provides solution for ____________ problems.

a) All pair shortest path
b) Sorting
c) Network flow
d) Single source shortest path
Answer: d) Single source shortest path

31. How many solution/solutions are available for a graph having negative weight cycle?
a) One solution
b) Two solutions
c) No solution
d) Infinite solutions
Answer: c) No solution

32. What is the running time of Bellmann Ford Algorithm?

a) O(V)
b) O(V2)
c) O(ElogV)
d) O(VE)
Answer: d) O(VE)

33. How many times the for loop in the Bellmann Ford Algorithm gets executed?
a) V times
b) V-1
c) E
d) E-1
Answer: b) V-1

34. What is the basic principle behind Bellmann Ford Algorithm?

a) Interpolation
b) Extrapolation
c) Regression
d) Relaxation
Answer: d) Relaxation

35. Bellmann Ford Algorithm can be applied for _____________

a) Undirected and weighted graphs
b) Undirected and unweighted graphs
c) Directed and weighted graphs
d) All directed graphs
Answer: c) Directed and weighted graphs

36. Bellmann Ford algorithm was first proposed by ________

a) Richard Bellmann
b) Alfonso Shimbe
c) Lester Ford Jr
d) Edward F. Moore
Answer: b) Alfonso Shimbe

37. Consider the following graph. What is the minimum cost to travel from node A to node
C?
a) 5
b) 2
c) 1
d) 3
Answer: b) 2

38. In the given graph, identify the path that has minimum cost to travel from node a to node
f.

a) a-b-c-f
b) a-d-e-f
c) a-d-b-c-f
d) a-d-b-c-e-f
Answer: d) a-d-b-c-e-f

39. Bellmann Ford Algorithm is an example for ____________

a) Dynamic Programming
b) Greedy Algorithms
c) Linear Programming
d) Branch and Bound
Answer: a) Dynamic Programming

40. A graph is said to have a negative weight cycle when?

a) The graph has 1 negative weighted edge
b) The graph has a cycle
c) The total weight of the graph is negative
d) The graph has 1 or more negative weighted edges
Answer: c) The total weight of the graph is negative

41. Floyd Warshall’s Algorithm is used for solving ____________

a) All pair shortest path problems
b) Single Source shortest path problems
c) Network flow problems
d) Sorting problems
Answer: a) All pair shortest path problems

42. Floyd Warshall’s Algorithm can be applied on __________

a) Undirected and unweighted graphs
b) Undirected graphs
c) Directed graphs
d) Acyclic graphs
Answer: c) Directed graphs

43. What is the running time of the Floyd Warshall Algorithm?

a) Big-oh(V)
b) Theta(V2)
c) Big-Oh(VE)
d) Theta(V3)
Answer: d) Theta(V3)

44. What approach is being followed in Floyd Warshall Algorithm?

a) Greedy technique
b) Dynamic Programming
c) Linear Programming
d) Backtracking
Answer: b) Dynamic Programming

45. Floyd Warshall Algorithm can be used for finding _____________

a) Single source shortest path
b) Topological sort
c) Minimum spanning tree
d) Transitive closure
Answer: d) Transitive closure

46. What procedure is being followed in Floyd Warshall Algorithm?

a) Top down
b) Bottom up
c) Big bang
d) Sandwich
Answer: b) Bottom up

47. Floyd- Warshall algorithm was proposed by ____________

a) Robert Floyd and Stephen Warshall
b) Stephen Floyd and Robert Warshall
c) Bernad Floyd and Robert Warshall
d) Robert Floyd and Bernad Warshall
Answer: a) Robert Floyd and Stephen Warshall

48. Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested
loops?
a) Robert Floyd
b) Stephen Warshall
c) Bernard Roy
d) Peter Ingerman
Answer: d) Peter Ingerman
49. What happens when the value of k is 0 in the Floyd Warshall Algorithm?
a) 1 intermediate vertex
b) 0 intermediate vertex
c) N intermediate vertices
d) N-1 intermediate vertices
Answer: b) 0 intermediate vertex

50. In the given graph, what is the minimum cost to travel from vertex 1 to vertex 3?

a) 3
b) 2
c) 10
d) -3
Answer: d) -3

51. In the given graph, how many intermediate vertices are required to travel from node a to
node e at a minimum cost?
a) 2
b) 0
c) 1
d) 3
Answer: c) 1

52. What is the formula to compute the transitive closure of a graph?

a) tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))
b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))
c) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))
d) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))
Answer: b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))
53. Fractional knapsack problem is also known as __________
a) 0/1 knapsack problem
b) Continuous knapsack problem
c) Divisible knapsack problem
d) Non continuous knapsack problem
Answer: b) Continuous knapsack problem

54. Fractional knapsack problem is solved most efficiently by which of the following
algorithm?
a) Divide and conquer
b) Dynamic programming
c) Greedy algorithm
d) Backtracking
Answer: c) Greedy algorithm

55. What is the objective of the knapsack problem?

a) To get maximum total value in the knapsack
b) To get minimum total value in the knapsack
c) To get maximum weight in the knapsack
d) To get minimum weight in the knapsack
Answer: a) To get maximum total value in the knapsack

56. Time complexity of fractional knapsack problem is ____________

a) O(n log n)
b) O(n)
c) O(n2)
d) O(nW)
Answer: a) O(n log n)

57. Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of

knapsack=20. Find the maximum value output assuming items to be divisible.
a) 60
b) 80
c) 100
d) 40
Answer: a) 60

58. The main time taking step in fractional knapsack problem is ___________
a) Breaking items into fraction
b) Adding items into knapsack
c) Sorting
d) Looping through sorted items
Answer: c) Sorting

59. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of

knapsack=40. Find the maximum value output assuming items to be divisible and
nondivisible respectively.
a) 100, 80
b) 110, 70
c) 130, 110
d) 110, 80
Answer: d) 110, 80

60. Which of the problems cannot be solved by backtracking method?

a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem
Answer: d) travelling salesman problem

61. Backtracking algorithm is implemented by constructing a tree of choices called as?

a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree
Answer: a) State-space tree

62. What happens when the backtracking algorithm reaches a complete solution?
a) It backtracks to the root
b) It continues searching for other possible solutions
c) It traverses from a different route
d) Recursively traverses through the same route
Answer: b) It continues searching for other possible solutions
63. A node is said to be ____________ if it has a possibility of reaching a complete solution.
a) Non-promising
b) Promising
c) Succeeding
d) Preceding
Answer: b) Promising

64. In what manner is a state-space tree for a backtracking algorithm constructed?

a) Depth-first search
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first
Answer: a) Depth-first search

65. In general, backtracking can be used to solve?

a) Numerical problems
b) Exhaustive search
c) Combinatorial problems
d) Graph coloring problems
Answer: c) Combinatorial problems

66. Which one of the following is an application of the backtracking algorithm?

a) Finding the shortest path
b) Finding the efficient quantity to shop
c) Ludo
d) Crossword
Answer: d) Crossword

67. Which of the following logical programming languages is not based on backtracking?
a) Icon
b) Prolog
c) Planner
d) Fortran
Answer: d) Fortran

68. The problem of finding a list of integers in a given specific range that meets certain
conditions is called?
a) Subset sum problem
b) Constraint satisfaction problem
c) Hamiltonian circuit problem
d) Travelling salesman problem
Answer: b) Constraint satisfaction problem

69. Who coined the term ‘backtracking’?

a) Lehmer
b) Donald
c) Ross
d) Ford
Answer: a) Lehmer

70. ___________ enumerates a list of promising nodes that could be computed to give the
possible solutions of a given problem.
a) Exhaustive search
b) Brute force
c) Backtracking
d) Divide and conquer
Answer: c) Backtracking

71. The problem of finding a subset of positive integers whose sum is equal to a given
positive integer is called as?
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem
Answer: b) subset sum problem

72. The problem of placing n queens in a chessboard such that no two queens attack each
other is called as?
a) n-queen problem
b) eight queens puzzle
c) four queens puzzle
d) 1-queen problem
Answer: a) n-queen problem

73. In how many directions do queens attack each other?

a) 1
b) 2
c) 3
d) 4
Answer: c) 3

74. Placing n-queens so that no two queens attack each other is called?
a) n-queen’s problem
b) 8-queen’s problem
c) Hamiltonian circuit problem
d) subset sum problem
Answer: a) n-queen’s problem

75. Where is the n-queens problem implemented?

a) carom
b) chess
c) ludo
d) cards
Answer: b) chess

76. In n-queen problem, how many values of n does not provide an optimal solution?
a) 1
b) 2
c) 3
d) 4
Answer: b) 2

77. Which of the following methods can be used to solve n-queen’s problem?
a) greedy algorithm
b) divide and conquer
c) iterative improvement
d) backtracking
Answer: d) backtracking

78. Of the following given options, which one of the following is a correct option that
provides an optimal solution for 4-queens problem?
a) (3,1,4,2)
b) (2,3,1,4)
c) (4,3,2,1)
d) (4,2,3,1)
Answer: a) (3,1,4,2)

79. How many possible solutions exist for an 8-queen problem?

a) 100
b) 98
c) 92
d) 88
Answer: c) 92

80. How many possible solutions occur for a 10-queen problem?

a) 850
b) 742
c) 842
d) 724
Answer: d) 724

81. What is the domination number for 8-queen’s problem?

a) 8
b) 7
c) 6
d) 5
Answer: d) 5

82. Of the following given options, which one of the following does not provides an optimal
solution for 8-queens problem?
a) (5,3,8,4,7,1,6,2)
b) (1,6,3,8,3,2,4,7)
c) (4,1,5,8,6,3,7,2)
d) (6,2,7,1,4,8,5,3)
Answer: b) (1,6,3,8,3,2,4,7)
83. Which of the following is/are property/properties of a dynamic programming problem?
a) Optimal substructure
b) Overlapping subproblems
c) Greedy approach
d) Both optimal substructure and overlapping subproblems
Answer: d) Both optimal substructure and overlapping subproblems

84. If an optimal solution can be created for a problem by constructing optimal solutions for
its subproblems, the problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy
Answer: b) Optimal substructure

85. If a problem can be broken into subproblems which are reused several times, the
problem possesses ____________ property.
a) Overlapping subproblems
b) Optimal substructure
c) Memoization
d) Greedy

Answer: a) Overlapping subproblems

86. If a problem can be solved by combining optimal solutions to non-overlapping problems,
the strategy is called _____________
a) Dynamic programming
b) Greedy
c) Divide and conquer
d) Recursion
Answer: c) Divide and conquer

87. In dynamic programming, the technique of storing the previously calculated values is
called ___________
a) Saving value property
b) Storing value property
c) Memoization
d) Mapping
Answer: c) Memoization

88. When a top-down approach of dynamic programming is applied to a problem, it usually

_____________
a) Decreases both, the time complexity and the space complexity
b) Decreases the time complexity and increases the space complexity
c) Increases the time complexity and decreases the space complexity
d) Increases both, the time complexity and the space complexity
Answer: b) Decreases the time complexity and increases the space complexity
89. Which of the following problems is NOT solved using dynamic programming?
a) 0/1 knapsack problem
b) Matrix chain multiplication problem
c) Edit distance problem
d) Fractional knapsack problem
Answer: d) Fractional knapsack problem

90. Which of the following problems should be solved using dynamic programming?
a) Mergesort
b) Binary search
c) Longest common subsequence
d) Quicksort
Answer: c) Longest common subsequence

91. The following sequence is a fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21,…..
Which technique can be used to get the nth fibonacci term?
a) Recursion
b) Dynamic programming
c) A single for loop
d) Recursion, Dynamic Programming, For loops
Answer: d) Recursion, Dynamic Programming, For loops

92. Consider the recursive implementation to find the nth fibonacci number:

Int fibo (int n)

If n <=1
return n
return _____________

Which line would make the implementation complete?

a) fibo(n) + fibo(n)
b) fibo(n) + fibo(n – 1)
c) fibo(n – 1) + fibo(n + 1)
d) fibo(n – 1) + fibo(n – 2)
Answer: d) fibo(n – 1) + fibo(n – 2)

93. What is the time complexity of the recursive implementation used to find the nth
fibonacci term?
a) O(1)
b) O(n2)
c) O(n!)
d) Exponential
Answer: d) Exponential

94. What is the space complexity of the recursive implementation used to find the nth
fibonacci term?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer: a) O(1)

95. Find the maximum sub-array sum for the given elements.
{2, -1, 3, -4, 1, -2, -1, 5, -4}
a) 3
b) 5
c) 8
d) 6
Answer: b) 5

96. Find the maximum sub-array sum for the given elements.
{-2, -1, -3, -4, -1, -2, -1, -5, -4}
a) -3
b) 5
c) 3
d) -1
Answer: d) -1
97. What is the time complexity of the divide and conquer algorithm used to find the
maximum sub-array sum?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)
Answer: c) O(nlogn)

98. What is the space complexity of the divide and conquer algorithm used to find the
maximum sub-array sum?
a) O(n)
b) O(1)
c) O(n!)
d) O(n2)
Answer: b) O(1)
99. Find the longest increasing subsequence for the given sequence:
{10, -10, 12, 9, 10, 15, 13, 14}
a) {10, 12, 15}
b) {10, 12, 13, 14}
c) {-10, 12, 13, 14}
d) {-10, 9, 10, 13, 14}
Answer: d) {-10, 9, 10, 13, 14}

100. Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a) 5
b) 4
c) 3
d) 6
Answer: d) 6

101. The number of increasing subsequences with the longest length for the given
sequence are:
{10, 9, 8, 7, 6, 5}
a) 3
b) 4
c) 5
d) 6
Answer: d) 6

102. The Knapsack problem is an example of ____________

a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer
Answer: b) 2D dynamic programming

103. Which of the following methods can be used to solve the Knapsack problem?
a) Brute force algorithm
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
Answer: d) Brute force, Recursion and Dynamic Programming

104. You are given a knapsack that can carry a maximum weight of 60. There are 4 items
with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of
the items you can carry using the knapsack?
a) 160
b) 200
c) 170
d) 90
Answer: a) 160
105. What is the time complexity of the brute force algorithm used to solve the Knapsack
problem?
a) O(n)
b) O(n!)
c) O(2n)
d) O(n3)
Answer: c) O(2n)

106. Which of the following methods can be used to solve the longest common
subsequence problem?
a) Recursion
b) Dynamic programming
c) Both recursion and dynamic programming
d) Greedy algorithm
Answer: c) Both recursion and dynamic programming

107. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the
longest common subsequence?
a) 9
b) 8
c) 7
d) 6
Answer: c) 7

108. Which of the following problems can be solved using the longest subsequence
problem?
a) Longest increasing subsequence
b) Longest palindromic subsequence
c) Longest bitonic subsequence
d) Longest decreasing subsequence
Answer: b) Longest palindromic subsequence

109. Longest common subsequence is an example of ____________

a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer
Answer: b) 2D dynamic programming

110. What is the time complexity of the brute force algorithm used to find the longest
common subsequence?
a) O(n)
b) O(n2)
c) O(n3)
d) O(2n)
Answer: d) O(2n)

111. Which of the following is the longest common subsequence between the strings
“hbcfgmnapq” and “cbhgrsfnmq” ?
a) hgmq
b) cfnq
c) bfmq
d) fgmna
Answer: d) fgmna