Algorithms

1. Given an integer array of size N, we want to check if the array is sorted (in either ascending or
descending order). An algorithm solves this problem by making a single pass through the array
and comparing each element of the array only with its adjacent elements. The worst-case time
complexity of this algorithm is
(A) neither O(N) nor Ω(N)
(B) Both O(N) and Ω(N)
(C) Ω(N) but not O(N)
(D) O(N) but not Ω (N)
check if A is sorted. Let's say array is: 1,2,3,4,5,6,7 And I want to check if array is sorted or not. For checking
descending order its the best case as only one comparison is required. But for checking ascending order we
need to traverse the entire array (worst case). Right? Therefore the time complexity is theta(n) implying
option a as the answer

2. Let f and g be functions of natural numbers given by f(n)=n and g(n)=n2. Which of the
following statements is/are TRUE?
A) f ∈ O(g)
B) f ∈ Ω(g)
C) f ∈ o(g)
D) f ∈ Θ(g)
f(n) <= o(g(n)) so , n<=n^2 f(n) < o(g(n)) so , n<n^2

3. Which one of the following statements is TRUE for all positive functions f(n)?
A) f(n2) = Θ (f(n)2), when f(n) is a polynomial
B) f(n2) = o(f(n)2)
C) f(n2) = O(f(n)2), when f(n) is an exponential function
D) f(n2) = Ω(f(n)2)

4. Consider the following three functions.

n
f1 = 10 f2 = nlogn f3 = n√n
Which one of the following options arranges the functions in the increasing order of
asymptotic growth rate?
A) f3,f2,f1
B) f2,f1,f3
C) f1,f2,f3
D) f2,f3,f1

5. P) Towers of honoi with n disks = T(n)= 2T(n-1)+1 = Ɵ (2n) .

Q) Binary Search given n numbers n sorted numbers = T(n)= T(n/2)+1 = Ɵ (logn)
R) Heap sort given n numbers at the worst case = T(n)= 2T(n/2)+n = Ɵ (nlogn)
S) Addition of two nxn matrices = T(n)= 2T(n/2)+n2 = Ɵ (n2)
6. Consider the following functions from positive integers to real numbers:

10, √n, n, logn, 100/n.

The CORRECT arrangement of the above functions in increasing order of asymptotic
complexity is:
A) logn, 100/n, 10,√n, n
B) 100/n, 10, logn, √n, n
C) 10, 100/n, √n, logn, n
D) 100/n, logn, 10, √n, n
7. Consider the equality ∑i3 0 to n= X and the following choices for X:
I. Θ(n4)
II. Θ(n5)
III. O(n5)
IV. Ω(n3)
The equality above remains correct if X is replaced by
A) Only I
B) Only II
C) I or III or IV but not II
D) II or III or IV but not I
Sum of the cubes of the first n natural numbers is given by (n(n+1)/2)^2 which is Θ(n4). So, I, III and IV are correct.
II is wrong. ∴ (C) is correct.

8. Let W(n) and A(n) denote respectively, the worst case and average case running time of an
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

A) A(n)=Ω(W(n))
B) A(n)=Θ(W(n))

C) A (n)=O(W(n))

D) A(n)=o(W(n))

Worst case complexity can never be lower than the average case complexity, but it can be higher. So, (C) is the
answer. A(n)=O(W(n))

9. Two alternative packages A and B are available for processing a database having 10k records.
Package A requires 0.0001n^2 time units and package B requires 10nlogn time units to
process n records. What is the smallest value of k for which package B will be preferred
over A?
A) 12
B) 10
C) 6
D) 5
B <= A
k k k
⟹ 10 x 10 log 10 ≤ 0.0001(10 )2

⟹ 10k+1 k ≤ 0.0001×102k

⟹k ≤ 102k-k-1-4

⟹ k ≤ 10k-5

Trying the values, 5 doesn't satisfy this but 6 satisfies.

10. Arrange the following functions in increasing asymptotic order:
a. n1/3
b. en
c. n7/4
d. n log9 n
e. 1.0000001n
A) a, d, c, e, b
B) d, a, c, e, b
C) a, c, d, e, b
D) a, c, d, b, e

11. The time taken by binary search algorithm to search a key in a sorted array of n elements is
A) O(logn)
B) O(n)
C) O(nlogn)
D) O(n2) Binary search is always for sorted array , and it takes A) O(log n) time

12. Exponentiation is a heavily used operation in public key cryptography. Which of the following
options is the tightest upper bound on the number of multiplications required to compute
bn mod m , 0≤b ,n ≤ m ?
A) O(logn)
B) O(√n)
C) O(n/logn)
D) O(n)
First find out b^2 which will require 1 multiplication(b*b)..store the value of b^2(say in variable 'a') for further use...

b^4 can be find out using a*a ie 1 multiplication, therefore total of 2 multiplication (including step 1). Store the value of b^4 in
variable 'c' for further use.

Similarly b^8 can be calculated by c*c i.e 1 multiplication and total of 3 multiplication (including step 2)....and so on. Therefore O(log
n) is the complexity for the no. of multiplications required.

13. If T1=O(1), give the correct matching for the following pairs:
(M) Tn=Tn−1+n (U) Tn=O(n)
(N) Tn=Tn/2+n (V) Tn=O(nlogn)
(O) Tn=Tn/2+nlogn (W) Tn=O(n2 )
(P) Tn=Tn-1+logn (X) Tn=O(log2 n)
A. M-W, N-V, O-U, P-X
B. M-W, N-U, O-X, P-V
C. M-V, N-W, O-X, P-U
D. M-W, N-U, O-V, P-X
Wrong choices as O and P has same (V)
14. Let T(n) be the recurrence relation defined as follows:
T(0)=1,T(1)=2, and T(n)=5T(n−1)−6T(n−2) for n≥2
Which one of the following statements is TRUE?
A) T(n)= Θ(2n) // only this satisfies for 0 and 1 values
B) T(n)=Θ(n2n)
C) T(n)=Θ(3n)
D) T(n)=Θ(n3n)

15. The master theorem

A) assumes the subproblems are unequal sizes
B) can be used if the subproblems are of equal size
C) cannot be used for divide and conquer algorithms
D) cannot be used for asymptotic complexity analysis

16. For parameters a and b, both of which are ω(1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is
A) Θ(logalogbn)
B) Θ(logabn)
C) Θ(logblogan)
D) Θ(log2log2n)

Now, T(n)=T(n1/a)+1

= T(n1/a^2)+1+1 [∵ T(n1/a) = T(n1/a^2)+1]

= T(n1/a^3 )+1+1+1 [∵T(n1/a^2 ) = T(n1/a^3 )+1]

After k iterations, T(n)= T(n1/a^k ) + k

When n1/a^k = b , i.e., 1/ak logn = logb

⟹ ak = logn/logb

⟹ k = logalogbn
17. The running time of an algorithm is given by:
T(n)=T(n−1)+T(n−2)−T(n−3), if n>3 = n, otherwise
Then what should be the relation between T(1),T(2),T(3), so that the order of the algorithm is
constant?
A) T(1) =T(2)=T(3)
B) T(1 )+T(3)=2T(2)
C) T(1) −T(3)=T(2)
D) T(1) +T(2)=T(3)
For sufficiently large n, T(n)=T(n−1)+T(n−2)−T(n−3)
If the order of the algorithm for which above recurrence is applicable for the time complexity, is a constant,
T(n)=T(n−1). ⟹ T(n)=T(n)+T(n−2)−T(n−3)
⟹T(n−2)=T(n−3)

Going like this, we must have T(1)=T(2)=T(3) which is option A

18. The recurrence relation that arises in relation with the complexity of binary search is:
A) T(n)=2T(n/2)+k , k is a constant
B) T(n)=T(n/2)+k , k is a constant
C) T(n)=T(n/2) + logn
D) T(n)=T(n/2) + n
Searching for only half of list. Leading T(n/2) + constant time in comparing and finding mid element

19. Which one of the following correctly determines the solution of the recurrence relation
with T(1)=1?
T(n)=2T(n/2)+logn
A) Θ(n)
B) Θ(nlogn)
C) Θ(n2)
D)Θ(logn)
Put n=2 ; f(n)= logn ; a=2, b=2 nlogba = n So, Master theorem Case 1, and answer will be O(n)

20.The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem
with n discs is
A) T(n)=2T(n−2)+2
B) T(n)=2T(n−1)+n
C) T(n)=2T(n/2)+1
D) T(n)=2T(n−1)+1

21. Let T(n) be defined by T(1)=10 and T(n+1)=2n+T(n) for all integers n≥1. Which of the
following represents the order of growth of T(n) as a function of n?
A) O(n)
B) O(nlogn)
C) O(n2)
D)O(n3)
T(n+1)= 2n + T(n)  2n + 2(n-1) +T(n-1)  2n + 2(n-1) + T(n-2)…
 2(n+n-1+n-2) + T(1)  2*(n)(n-1)/2 +10  O(n^2) answer

22. Binary Search  T(n) = T(n/2) + 1

Merge Sort  T(n) = 2T(n/2) + cn
Quick Sort  T(n) = T(n-k) + T(k) + cn
Tower of Hanoi  T(n) = 2T(n-1) + 1

23. The running time of the following algorithm Procedure A(n)  If n⩽2 return (1) else
return (A(⌈sqrt(n)⌉)); is best described by
A) O(n)
B) O(logn)
C) O(loglogn)
D) O (1)

24. If n is a power of 2, then the minimum number of multiplications needed to compute an is

A) log2n
B) sqrt(n)
C) n−1
D) n
Correct Option: A (log2n)  an = (a2 )^n/2 One multiplication and recurrence on n/2. So, we get the recurrence relation for
the number of multiplications as
T(n)=T(n/2)+1.

25. Prim’s Algo for Minimum Spanning Tree  Greedy

Floyd Warshall  Dynamic Programming
Merge Sort  Divide and Conquer
Hamilitonian Circuit  Backtracking
Dijkstra’s Shortest Path  Greedy
Binary Search  Divide and Conquer
Backtracking Search on Design  DFS

26. Consider a sequence of 14 elements: A=[−5,−10,6,3,−1,−2,13,4,−9,−1,4,12,−3,0]. The

sequence sum S(i,j)=Σ(k=i to j)= A[k]. Determine the maximum of S(i,j), where 0≤i≤j<14.
(Divide and conquer approach may be used.)
Answer is  29
for [−5,−10,6,3,−1,−2,13,4,−9,−1,4,12,−3,0]  [-5,-15,-9,-6,-7,-9,4,8,-1,-2,2,14,9,9] will be prefix sum array.

Difference between sums will give us range sum queries (on the prefix sum array)
Hence, to maximize sum, find the maximum difference, which is clearly between 14 and -15 in our
prefix array.
14-(-15) = 29, which will be the final answer.

27. Of the following sort algorithms, which has execution time that is least dependant on initial
ordering of the input?

A) Insertion sort

B) Quick sort

C) Merge sort

D) Selection sort

In insertion sort, if the array is already sorted then it takes O(n). If the array is reverse sorted then it takes O(n2).

In quick sort, if the array is already sorted or sorted in the reverse order, then it takes O(n2).

The best and worst-case performance of the Selection sort is O(n2) only.
But in case the array is already sorted then fewer swaps take place.

In the case of Merge Sort, the time complexity is always O(nlogn) for all the cases.

In short, Merge sort is Non-Adaptive in nature but rest of algorithms are.

28. Consider the following array. 23 32 45 69 72 73 89 97 Which algorithm out of the

following options uses the least number of comparisons (among the array elements) to sort
the above array in ascending order?
A) Selection sort
B) Mergesort
C) Insertion sort
D) Quicksort using the last element as pivot
Correct Option: C (Insertion Sort)
Explanation:
The given array is already sorted in ascending order.
For already sorted array, different sorting algorithms behave as following:

Selection sort:
No matter how the data is arranged, there would always be comparisons and swaps made and so the time complexity
for best, average and worst case is: O(n2).

Insertion Sort:
When elements are already sorted in desired order, there are no swaps and the correct position of the element in the
sorted list is the current index itself. The time complexity is: O(n)
Number of comparisons =n−1
Comparisons in total :1+1+…+1 = n−1 ∈ Θ (n).

Merge Sort:
We are dividing the list into two halves, no matter if the list is sorted or not. But if the array is sorted, while merging
the list, there are no swaps merging results into an array itself. Thus, the best, average and worst case time complexity
is: O(nlogn) Number of comparisons, in all cases, will be O(nlogn)
Quick Sort:
If we use the last or first element as pivot, then Quick Sort will give worst case performance if the elements are in a
sorted or reverse sorted manner. So, for the given array in the question, Quick Sort will behave in worst manner and
will take O(n2) comparisons. The best and average case time complexity is: O(nlogn)
Number of comparisons, in best case, will be O(nlogn)  So, answer will be insertion sort.

29.An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element
is chosen uniformly at random. The probability that the pivot element gets placed in the worst
possible location in the first round of partitioning (rounded off to 2 decimal places) is
0.08
Worst case of quicksort, if pivot element is Minimum or Maximum.
Total elements =25
For worst case number of candidates =2  pivot is at extreme left or extreme right.  P = 2/25= 0.08

30. Given two sorted list of size M and N respectively. The number of comparisons needed the
worst case by the merge sort algorithm will be:
A) M × N
B) maximum of M and N
C) minimum of M and N
D) M+N−1 Worst Case comparisons is o(M+N-1) ; for best case is  min(M,N)

31. The number of swappings needed to sort the numbers 8,22,7,9,31,5,13 in ascending order
using bubble sort is
A) 11
B) 12
C) 13
D) 10
All swaps are in following order:
8,7,22,9,31,5,13  8,7,9,22,31,5,13  8,7,9,22,5,31,13  8,7,9,22,5,13,31  7,8,9,22,5,13,31  7,8,9,5,22,13,31
7,8,9,5,13,22,31  7,8,5,9,13,22,31  7,5,8,9,13,22,31  5,7,8,9,13,22,31

32.Which one of the following in-place sorting algorithms needs the minimum number of swaps?
A) Insertion Sort
B) Quick Sort
C) Heap Sort
D) Selection Sort

33. Algorithm design technique used in quicksort and mergesort algorithm is?
A) Dynamic programming
B) Backtracking
C) Divide and conquer
D) Greedy method

34.A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time
needed to sort 100 names will be approximately
A) 50.2 sec
B) 6.7 sec
C) 72.7 sec
D) 11.2 sec
Running time of quick sort = c n lg n  For n = 1000, we get
 100 = c * 1000 * lg 1000 => c = 0.01
So, for n = 100, we get running time = 0.01 * 100 * lg 100 = 6.7

35. The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are:

A) Θ(nlogn), Θ(nlogn) and Θ(n^2)

B) Θ(n^2), Θ(n^2) and Θ(nlogn)
C) Θ(n^2), Θ(nlogn) and Θ(nlogn)
D) Θ(n^2), Θ(nlogn) and Θ(n^2)

36. Assume that the algorithms considered here sort the input sequences in ascending order. If the
input is already in the ascending order, which of the following are TRUE?

A) Quicksort runs in Θ(n^2) time

B) Bubblesort runs in Θ(n^2) time
C) Mergesort runs in Θ(n) time
D) Insertion sort runs in Θ(n) time

37. If one uses straight two-way merge sort algorithm to sort the following elements in ascending
order: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after second
pass of the algorithm is:
A) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40
B) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17
C) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17
D) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40

38. Consider the following sorting algorithms.

A) Quicksort O(n^2)
B) Heapsort O(nlogn)
C) Mergesort O(nlogn)

Which of them perform in least time in the worst case?

39. Which of the following sorting algorithms has the minimum running time complexity in the
best and average case?
A) Insertion sort, Quick sort
B) Quick sort, Quick sort
C) Quick sort, Insertion sort
D) Insertion sort, Insertion sort

40. Let P be quicksort program to sort numbers in ascending order using the first element as the
pivot. Let t1 and t2 be the number of comparisons made by P for the
inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
A) t1=5
B) t1<t2
C) t1>t2
D) t1=t2
it would be t1>t2, because the first case is the worst case of quicksort i.e. minimum number is chosen as pivot.
Hence in the worst case the comparisons are high. Number of recursive calls remain the same, but in second case
the number of elements passed for the recursive call is less and hence the number of comparisons also less.

41. You have an array of n elements. Suppose you implement quicksort by always choosing the
central element of the array as the pivot. Then the tightest upper bound for the worst case
performance is
A) O(n^2)
B) O(nlogn)
C) Θ(nlogn)
D) O(n^3)
When we choose the first element as the pivot, the worst case of quick sort comes if the input is sorted- either
in ascending or descending order. Now, when we choose the middle element as pivot, sorted input no longer
gives worst case behavior. But, there will be some permutation of the input numbers which will be giving the
same worst case behavior. For example,

1234567
This array gives worst case behavior for quick sort when the first element is pivot.

6421357
This array gives the worst case behavior of O(n^2) if we take middle element as the pivot- each split will
be 1 element on one side and n−1 elements on other side. Similarly, for any input, we can have a permutation
where the behavior is like this. So, whichever element we take as pivot it gives worst case complexity
of O(n^2) as long as pivot is from a fixed position (not random position as in randomized quick sort).

42. How many comparisons are needed to sort an array of length 5 if a straight selection sort is
used and array is already in the opposite order?
A) 1
B) 10
C) 15
D) 20
So whatever order they are arranged the number of comparisons will be sum of n-1 terms.
Here n=5
So total comparisons= 4*(4+1)/2=10.

43. Which one of the following is the tightest upper bound that represents the number of swaps
required to sort n numbers using selection sort?
A) O(logn)
B) O(n)
C) O(nlogn)
D) O(n^2) In selection max you can do is n swaps..selecting the smallest element from all
the elements and replacing it correct position so O(n)
44. Selection sort algorithm design technique is an example of
A) Greedy method
B) Divide-and-conquer
C) Dynamic Programming
D) Backtracking

45. Which of the following sorting algorithms has the lowest worse-case complexity?
A) Merge sort
B) Bubble sort
C) Quick sort
D) Selection sort

46. The usual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to
identify the position where an element is to be inserted into the already sorted part of the array.
If, instead, we use binary search to identify the position, the worst case running time will
A) remain Θ(n^2)
B) become Θ(n(logn)^2)
C) become Θnlogn)
D) become Θ(n)
n insertion sort, with linear search, it takes

(worst case) n comparisons for searching the right position, and n swaps to make room to place the element.

Hence for n elements, a total of n×(n+n); n for search and n for swaps.

=Θ(2 n^2)=Θ(n^2)

If we replace it with binary search, it takes

(worst case) logn comparisons for searching the right position, and n swaps to make room to place the
element.

Hence for n elements, a total of n×(logn+n); n for search and n for swaps.

=Θ(n×logn+n^2)=Θ(n^2)

Hence, answer is A.

47. If one uses straight two-way merge sort algorithm to sort the following elements in
ascending order: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these
elements after second pass of the algorithm is:
A) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40
B) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17
C) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17
D) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40
48. A sorting technique is called stable if
A) it takes O(nlogn) time
B) it maintains the relative order of occurrence of non-distinct elements
C) it uses divide and conquer paradigm
D) it takes O(n) space

49. Selection: O(n)

Insertion sort : O(n^2)
Binary search : O(logn)
Merge sort : O(nlogn)
Here we are talking about the worst case time complexities of the given algorithms. Selection actually refers
to selection algorithm and not selection sort.

50. Quick-sort is run on two inputs shown below to sort in ascending order taking first element
as pivot
(i) 1,2,3,…n and (ii) n,n−1,n−2,…,2,1
Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
A) C1<C2
B) C1>C2
C) C1=C2
D) we cannot say anything for arbitrary n both are the worst cases of quick sort.

51. Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What
is the worst case complexity of sorting n numbers using Randomized quicksort?
A) O(n)
B) O(nlogn)
C) O(n^2)
D) O(n!)

52. Following algorithm(s) can be used to sort n in the range [1…n^3] in O(n) time
A) Heap sort
B) Quick sort
C) Merge sort
D) Radix sort
53. The complexity of comparison based sorting algorithms is:
A) Θ(nlogn)
B) Θ(n)
C) Θ(n^2)
D) Θ(n*sqrt(n)) heap sort is also come under comparison based algorithm so nlogn

54. Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time
taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of the
following holds?
A) t1=t2
B) t1>t2
C) t1<t2
D) t1=t2+5log5
Actually, in both the cases, it will take O(n^2) time for partition algorithm and O(n−1) time for subproblem. As n is
the number of inputs and in the 2nd case inputs are 5(greater than 1st one that is 4),  t1<t2.

55. Huffman tree is constructed for the following data :{A,B,C,D,E} with
frequency {0.17,0.11,0.24,0.33 and 0.15} respectively. 100 00 01 101 is decoded as
A) BACE
B) CADE
C) BAD
D) CADD Huffman Coding make min heap.

56. The minimum number of record movements required to merge five files A (with 10 records),
B (with 20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:
A) 165
B) 90 huffman coding
C) 75
D) 65
Arrange files in increasing order of records:

D  5 A  10 C 15 B 20 E 25
75
30 45
15 15C 20B 25E
5D 10A No. of movements =15+30+45+75=165.

57. Bellman-Ford algorithm ⟹ O(n*m). Assuming n as edges , m as vertices, for every vertex
we relax all edges. m∗n
Kruskal’s algorithm ⟹ O (mlogn)
Floyd-Warshall algorithm ⟹ Dynamic Programming Algo, O(n^3)
Topological sorting ⟹ boils down to DFS, O(n+m)
58. The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is
____16___.
Number of spanning trees in any complete graph (Kn) is (n)^(n−2), where n is a number of vertices.

here n=4∴ the number of spanning tree is (4)^(4−2) = 4^2 = 16

59. Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weight edge in G which is present in every minimum
spanning tree of G
S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which one of the following options is correct?
A) Both S1 and S2 are true
B) S1 is true and S2 is false
C) S1 is false and S2 is true
D) Both S1 and S2 are false
We can think of running the Kruskal’s algorithm for finding the Minimum Spanning Tree on graph G

While doing that, we sort the edges based on their weight and start selecting edges from the smallest weight (w
small for example).

Problem with S1: If we have multiple copies of small, then a specific w small weighted edge is not guaranteed to be
selected by Kruskal’s algorithm.

S2 is Correct: If the sorted order of the edges contains only distinct values, Kruskal’s algorithm will always select a
unique set of edges resulting in a unique minimum spanning tree.

60. Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ___3____.

 1st MST

 2nd MST

 3rd MST

∴ Total 3 MSTs are possible for the given graph.

61. Let G be a weighted connected undirected graph with distinct positive edge weights. If every
edge weight is increased by the same value, then which of the following statements is/are
TRUE?
P: Minimum spanning tree of G does not change.
Q: Shortest path between any pair of vertices does not change.
A) P only C) Q only
B) Neither P nor Q D) Both P and Q
62. The number of spanning trees for a complete graph with seven vertices is
A) 25
B) 75
C) 35
D) 22 x 5 formula is (n)^ (n-2)
63. What is the largest integer m such that every simple connected graph with n vertices
and n edges contains at least m different spanning trees?
A) 1
B) 2
C) 3
D) N
A graph is connected and has 'n' vertices and edges means, exactly one cycle is there.

Now we can make a different spanning tree by removing one edge from the cycle, one at a time.

Minimum cycle length can be 3, So, there must be at least 3 spanning trees in any such graph.

64. Consider a weighted complete graph G on the vertex set {v1,v2,.....vn} such that the weight
of the edge (vi,vj) is 2|i−j|. The weight of a minimum spanning tree of G is:

A) n−1

B) 2n−2

C) (n and 2) in one column

D) N^2

2(N-1) the spanning tree will traverse adjacent edges since they contain the least weight

65. 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?

A) Graph G has no minimum spanning tree (MST)

B) Graph G has unique MST of cost n−1
C) Graph G has multiple distinct MSTs, each of cost n−1
D) Graph G has multiple spanning trees of different costs

From the given data given graph is a complete graph with all edge weights 1. A MST will contain n−1 edges . Hence
weight of MST is n−1.

The graph will have multiple MST. In fact all spanning trees of the given graph wll be MSTs also since all edge
weights are equal.
66. Let G be an undirected connected graph with distinct edge weights. Let emax be the edge
with maximum weight and emin the edge with minimum weight. Which of the following
statements is false?

A) Every minimum spanning tree of G must contain emin

B) If emax is in a minimum spanning tree, then its removal must disconnect G

C) No minimum spanning tree contains emax

D) G has a unique minimum spanning tree (as has distinct edges)

67. All pairs shortest path  Dynamic Programming

Quick Sort  Divide and Conquer
Minimum weight spanning tree  Greedy
Connected Components  Depth-First Search

68. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear
time, the data structure to be used is:

A) Queue

B) Stack

C) Heap

D) B-Tree We can find single source shortest path in unweighted graph by using (BFS) algorithm
by using "Queue" data structure , in time O(m+n)

69. Djikstra’s algorithm is used to

A) Create LSAs

B) Flood an internet with information

C) Calculate the routing tables helps to find shortest paths for all

D) Create a link state database

70. What is the time complexity of Bellman-Ford single-source shortest path algorithm on a
complete graph of n vertices?

A) Θ(n2)

B) Θ(n2 logn)
C) Θ (n3)

D)Θ (n3logn)
71. Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected,
undirected graph. The tree T formed by the tree arcs is a data structure for computing

A) the shortest path between every pair of vertices.

B) the shortest path from W to every vertex in the graph.

C) the shortest paths from W to only those nodes that are leaves of T.

D) the longest path in the graph.

BFS always has a starting node. It does not calculate shortest path between every pair but it computes

shortest path between W and any other vertex.

72. Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path
algorithm?

P: Always finds a negative weighted cycle, if one exists.

Q: Finds whether any negative weighted cycle is reachable from the source.

A) P only

B) Q only

C) Both P and Q

D) Neither P nor Q

it can also be the case that there are some points which are not forming a cycle and are still unreachable from source,
those also will be at ∞ distance from the source from the beginning till end.

Hence, we won't be able to make a distinction among the cycle and such vertices. Thus, we say that this algorithm can
detect negative edge weight cycles only if they are reachable from the source.

73. Consider an undirected, unweighted graph G. Let a breadth-first traversal of G be done

starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths
from r to u and v respectively in G. If u is visited before v during the breadth-first traversal,
which of the following statements is correct?

A) d(r,u)<d(r,v)

B) d(r,u)>d(r,v)

C) d(r, u)≤d(r,v)
D) None of the above

74. Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting
depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex
visited after visiting u in the traversal. Which of the following statement is always true?

A) {u,v} must be an edge in G, and u is a descendant of v in T

B) {u,v} must be an edge in G, and v is a descendant of v in T

C) If {u,v} is not an edge in G then u is a leaf in T

D) If {u,v} is not an edge in G then u and v must have the same parent in

1. It is not necessary that there is an edge between them.

2. If there is no edge then u must be leaf
3. It is not always possible that u and v have same parent. But they have same ancestor.

75. Consider the following graph:

Among the following sequences:

A) abeghf

B) abfehg

C) abfhge

D) afghbe

Which are the depth-first traversals of the above graph?

76. In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The
number of connected components in G is

A) k

B) k+1

C) n−k−1

D) n−k formula

77. Consider the DAG with �={1,2,3,4,5,6} shown below.

Which of the following is not a topological ordering?

A) 1 2 3 4 5 6

B) 1 3 2 4 5 6

C) 1 3 2 4 6 5

D) 3 2 4 1 6 5

78. A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at
which vertex u is visited for the first time and f[u] the time at which the DFS call to the
vertex u terminates. Which of the following statements is always TRUE for all edges (u,v) in
the graph ?

A) d[u]<d[v]

B) d[u]<f[v]

C) f[u]<f[v]

D) f [u]>f[v] if we directly start DFS on V first, then I call DFS on X which visits U

79. The most efficient algorithm for finding the number of connected components in an
undirected graph on n vertices and m edges has time complexity

A) Θ(n)
B) Θ(m)

C) Θ(m+n)  DFS Algorithm

D) Θ(mn)

80. The Breadth First Search (BFS) algorithm has been implemented using the queue data
structure. Which one of the following is a possible order of visiting the nodes in the graph
below?

A) MNOPQR

B) NQMPOR

C) QMNROP

D) POQNMR

 As per BFS, if we start from M then RQN (immediate neighbors of M) have to come after it in any order but
in A here, O comes in between. So, it is not BFS.
 As per BFS, if we start from N then QMO has to come after it in any order but in B here, P comes. So, it is not
BFS.
 As per BFS, if we start from Q then MNOP has to come after it in any order but in C here, R comes. So, it is
not BFS.

But D is following the sequences.

81. Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running
time of Depth First Search on G, when G is represented as an adjacency matrix?

A) Θ(n)

B) Θ(n+m)

C) Θ(n^2) In adjacency matrix representation, graph is represented as an n∗n matrix

D) Θ(m^2). In adjacency list representation we traverse only the adjacent vertices of the vertex)

Therefore time complexity becomes O(n^2)

82. Suppose depth first search is executed on the graph below starting at some unknown vertex.
Assume that a recursive call to visit a vertex is made only after first checking that the vertex
has not been visited earlier. Then the maximum possible recursion depth (including the initial
call) is ___19____.
Total 21 nodes are there. 2 nodes require back track here in this question.

So, max recursion depth is 21−2=19

(Do DFS from extreme ends such that max recursion depth will occur. i.e., take leftmost top node as initial node
for DFS as shown in below image)

Note:- Backtrack means it reduces recursion depth in stack.

83. Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is ______6_______.

Here, start with a and end with f a - - - - f Blank spaces are to be filled with b, c, d, e such that b comes
before c, and d comes before e.
Number of ways to arrange will be = 4! / (2! * 2!)  6

84. Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is
a vertex t at a distance four from the root. If t is the nth vertex in this BFS traversal, then the
maximum possible value of n is _______
No of nodes at level 0(root) of tree ⇒1

No of nodes at level 1 of tree ⇒2

No of nodes at level 2 of tree ⇒4

No of nodes at level 3 of tree ⇒8

No of nodes at level 4 of tree ⇒16

Last node in level 4th is the node we are looking for  1+ 2 + 4 + 8 + 16  31 answer

85. Which of the following is application of Breath First Search on the graph?

A) Finding diameter of the graph

B) Finding bipartite graph

C) Both (a) and (b)

D) None of the above

1. Finding diameter of the graph.

2. Finding the bipartite graph.
3. Peer to peer networks.
4. Shortest Path and Minimum Spanning Tree for the unweighted graph.
5. Social Networking Websites.
6. Crawlers in Search Engines.
7. GPS Navigation Systems.
8. Broadcasting in Network.
9. In Garbage Collection.
10. Cycle detection in the undirected graph.
11. Ford Fulkerson algorithm.
12. Path finding.
13. Finding all nodes within a connected component

86. Consider a weighted, undirected graph with positive edge weights and let uv be an edge in the
graph. It is known that the shortest path from the source vertex s to u has weight 53 and the
shortest path from s to v has weight 65. Which one of the following statements is always
TRUE?

A) Weight (u,v) ≤ 12

B) Weight (u,v) = 12

C) Weight (u,v) ≥ 12

D) Weight (u,v) > 12

C. Weight (u,v)≥12

If weight (u,v)<12, then the min. weight of (s,v)=weight of (s,u)+ weight of (u,v)=53+(<12) will be less than 65.