Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “GCD and LCM using Recursion – 2”.

1. LCM is also called as ________
a) GCD
b) SCM
c) GCF
d) HCF

Answer: b
Clarification: GCD (Greatest Common Divisor), GCF (Greatest Common Factor), HCF (Highest Common Factor) is not an alias for LCM. LCM is also called as Smallest Common Multiple(SCM).

2. What is the LCM of 8 and 13?
a) 8
b) 12
c) 20
d) 104

Answer: d
Clarification: 104 is the smallest positive integer that is divisible by both 8 and 12.

3. Which is the smallest number of 3 digits that is divisible by 2, 4, 8?
a) 100
b) 102
c) 116
d) 104
Answer: d
Clarification: LCM of 2, 4, 8 is 8. So check for the number that is divisible by 8. So 104 is the smallest number that is divisible by 2, 4, 8.

4. Which of the following is also known as LCM?
a) Lowest Common Divisor
b) Least Common Multiple
c) Lowest Common Measure
d) Highest Common Multiple
Answer: a
Clarification: Least Common Multiple is also known as LCM or Lowest Common Multiple.

5. What is the LCM of two coprime numbers?
a) 1
b) 0
c) Addition of two coprime numbers
d) Multiplication of two coprime numbers

Answer: d
Clarification: Coprime numbers have GCD 1. While LCM of coprime numbers is the product of those two coprime numbers.

6. In terms of Venn Diagram, which of the following expression gives LCM (Given A ꓵ B ≠ Ø)?
a) Multiplication of A U B terms
b) Multiplication of A ꓵ B terms
c) Multiplication of A*B terms
d) Multiplication of A-B terms
Answer: a
Clarification: In terms of Venn Diagram, the LCM is given by the Union of two sets. So A U B gives the LCM. While A ꓵ B gives the GCD.

7. What is the LCM according to the given Venn Diagram?

a) 2
b) 3
c) 180
d) 6
View Answer

Answer: c
Clarification: In terms of Venn Diagram, the LCM is given by the Union of two sets. So A U B gives the LCM. So product of all the terms is 180.

8. What is the lcm (a, b)?
a) a + b
b) gcd (a-b, b) if a>b
c) lcm (b, a)
d) a – b

Answer: c
Clarification: Since the LCM function is commutative, so lcm (a, b) = lcm (b, a).

9. What is the LCM of 48, 18, 6?
a) 12²
b) 12*2
c) 3
d) 6

Answer: a
Clarification: The LCM of 48, 18, 6 is 144 and 12² is 144.

10. Is 9 and 28 coprime number.
a) True
b) False

Answer: a
Clarification: Coprime numbers have GCD 1 and LCM is the product of the two given terms. So 9 and 28 are coprime numbers.

11. What is the following expression, lcm (a, lcm (b, c) equal to?
a) lcm (a, b, c)
b) a*b*c
c) a + b + c
d) lcm (lcm (a, b), c)

Answer: d
Clarification: Since LCM function follows associativity, hence lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c).

12. Is lcm an associative function.
a) True
b) False

Answer: a
Clarification: The lcm function is an associative function as lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c).

13. Which is the correct term of the given relation, lcm (a, b) * gcd (a, b) =?
a) |a*b|
b) a + b
c) a – b
d) a / b

Answer: a
Clarification: The lcm is closely related to gcd as lcm (a, b) * gcd (a, b) = |a*b|.

14. What is the following expression, lcm (a, gcd (a, b)) equal to?
a) a
b) b
c) a*b
d) a + b
Answer: a
Clarification: Since the lcm function follows absorption laws so lcm (a, gcd (a, b)) equal to a.

15. Which algorithm is the most efficient numerical algorithm to obtain lcm?
a) Euler’s Algorithm
b) Euclid’s Algorithm
c) Chebyshev Function
d) Partial Division Algorithm
Answer: b
Clarification: The most efficient way of calculating the lcm of a given number is using Euclid’s algorithm which computes the lcm in much lesser time compared to other algorithms.

contest

Data Structure Multiple Choice Questions on “0/1 Knapsack Problem”.

1. The Knapsack problem is an example of ____________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer
Answer: b
Clarification: Knapsack problem is an example of 2D dynamic programming.

2. 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
Clarification: Brute force, Recursion and Dynamic Programming can be used to solve the knapsack problem.

3. 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
Clarification: The maximum value you can get is 160. This can be achieved by choosing the items 1 and 3 that have a total weight of 60.

4. Which of the following problems is equivalent to the 0-1 Knapsack problem?
a) You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value
b) You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized
c) You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S
d) You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value

Answer: b
Clarification: In this case, questions are used instead of items. Each question has a score which is same as each item having a value. Also, each question takes a time t which is same as each item having a weight w. You have to maximize the score in time T which is same as maximizing the value using a bag of weight W.

5. What is the time complexity of the brute force algorithm used to solve the Knapsack problem?
a) O(n)
b) O(n!)
c) O(2ⁿ)
d) O(n³)
View Answer

Answer: c
Clarification: In the brute force algorithm all the subsets of the items are found and the value of each subset is calculated. The subset of items with the maximum value and a weight less than equal to the maximum allowed weight gives the answer. The time taken to calculate all the subsets is O(2ⁿ).

6. The 0-1 Knapsack problem can be solved using Greedy algorithm.
a) True
b) False

Answer: b
Clarification: The Knapsack problem cannot be solved using the greedy algorithm.

7. Consider the following dynamic programming implementation of the Knapsack problem:

#include
int find_max(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
        ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                  ans[itm][w] = ______________;
               else
                  ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

Which of the following lines completes the above code?
a) find_max(ans[itm – 1][w – wt[itm – 1]] + val[itm – 1], ans[itm – 1][w])
b) find_max(ans[itm – 1][w – wt[itm – 1]], ans[itm – 1][w])
c) ans[itm][w] = ans[itm – 1][w];
d) ans[itm+1][w] = ans[itm – 1][w];

Answer: a
Clarification: find_max(ans[itm – 1][w – wt[itm – 1]] + val[itm – 1], ans[itm – 1][w]) completes the above code.

8. What is the time complexity of the following dynamic programming implementation of the Knapsack problem with n items and a maximum weight of W?

#include
int find_max(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
        ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                 ans[itm][w] = find_max(ans[itm - 1][w-wt[itm - 1]]+val[itm - 1], ans[itm - 1][w]);
               else
                  ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

a) O(n)
b) O(n + w)
c) O(nW)
d) O(n²)

Answer: c
Clarification: The time complexity of the above dynamic programming implementation of the Knapsack problem is O(nW).

9. What is the space complexity of the following dynamic programming implementation of the Knapsack problem?

#include
int find_max(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
        ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                ans[itm][w] = find_max(ans[itm - 1][w - wt[itm - 1]]+val[itm - 1], ans[itm - 1][w]);
               else
                ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

a) O(n)
b) O(n + w)
c) O(nW)
d) O(n²)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation of the Knapsack problem is O(nW).

10. What is the output of the following code?

#include
int find_max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int knapsack(int W, int *wt, int *val,int n)
{
     int ans[n + 1][W + 1];
     int itm,w;
     for(itm = 0; itm <= n; itm++)
         ans[itm][0] = 0;
     for(w = 0;w <= W; w++)
         ans[0][w] = 0;
     for(itm = 1; itm <= n; itm++)
     {
          for(w = 1; w <= W; w++)
          {
               if(wt[itm - 1] <= w)
                ans[itm][w] = find_max(ans[itm - 1][w-wt[itm - 1]]+val[itm - 1], ans[itm - 1][w]);
               else
                ans[itm][w] = ans[itm - 1][w];
          }
     }
     return ans[n][W];
}
int main()
{
     int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50;
     int ans = knapsack(W, w, v, 3);
     printf("%d",ans);
     return 0;
}

a) 120
b) 100
c) 180
d) 220

Answer: d
Clarification: The output of the above code is 220.

Data Structures & Algorithms Multiple Choice Questions on “Pigpen Cipher”.

1. Which of the following cipher replaces letters with symbols?
a) polybius square ciper
b) affine cipher
c) caesar cipher
d) pigpen cipher

Answer: d
Clarification: Pigpen cipher encrypts the plain text by replacing each letter with a corresponding symbol. Pigpen cipher is an example of geometric substitution cipher.

2. Which of the following is not an alternative name of pigpen cipher?
a) pen cipher
b) freemason’s cipher
c) napoleon cipher
d) tic-tac-toe cipher

Answer: a
Clarification: Pigpen cipher is also known by the names like:- freemason’s cipher, napoleon cipher, tic-tac-toe cipher, masonic cipher. It is a cipher which is believed to be used by freemasons in the 18th century.

3. Which of the following cipher was used by freemasons?
a) Vigenere cipher
b) Autokey cipher
c) Pigpen cipher
d) Hill cipher
View Answer

Answer: c
Clarification: Pigpen cipher is believed to be used by freemasons in the 18th century. Pigpen cipher is an example of geometric substitution cipher.

4. Choose the weakest cipher from the following?
a) vigenere cipher
b) rail fence cipher
c) hill cipher
d) pigpen cipher
Answer: d
Clarification: Pigpen cipher is the weakest cipher out of the given options. This is because it is a simple geometric substitution cipher so can be easily cracked using frequency analysis.

5. Which of the following is not a poly alphabetic substitution cipher?
a) vigenere cipher
b) one time pad cipher
c) play fair cipher
d) pigpen cipher

Answer: d
Clarification: Pigpen cipher is the only non poly alphabetic substitution cipher out of the given options. It is an example of geometric substitution cipher.

6. Pigpen cipher is an example of?
a) Mono alphabetic substitution cipher
b) Transposition cipher
c) Poly alphabetic substitution cipher
d) Geometric substitution cipher

Answer: a
Clarification: Pigpen cipher encrypts the plain text by replacing each letter with a corresponding symbol. Pigpen cipher is an example of geometric substitution cipher.

7. Pigpen cipher is less secure than a vigenere cipher.
a) True
b) False
Answer: a
Clarification: Vigenere cipher is more secure as compared to pigpen cipher. It is because pigpen cipher is geometric substitution cipher and vigenere cipher is poly alphabetic substitution cipher.

8. Pigpen cipher is not susceptible to frequency analysis.
a) True
b) False
Answer: b
Clarification: Pigpen cipher is a very weak cipher as it just replaces letters with corresponding symbols. It can be easily broken using frequency analysis.

9. What will be the ciphered text corresponding to plain text “ACT” if pigpen cipher is used for encryption?
a) _| |_ >
b) |_ > |_
c) _| |_<
d) |_< _|
Answer: a
Clarification: Pigpen cipher replaces letters of the plain text with corresponding symbols. These symbols are fragment of a grid.

10. What will be the plain text corresponding to ciphered text “|_ _| >” if pigpen cipher is used for encryption?
a) cat
b) hat
c) dog
d) rat
Answer: a
Clarification: Pigpen cipher replaces letters of the plain text with corresponding symbols. So by using the grid we can replace these symbols by their corresponding letters which are “cat” here.

11. What is common between affine cipher and pigpen cipher.
a) both are mono alphabetic substitution cipher
b) both are poly alphabetic substitution cipher
c) both can be cracked using frequency analysis
d) both are transposition cipher

Answer: c
Clarification: Both affine cipher and pigpen cipher can be broken using frequency analysis. Pigpen cipher is an example of geometric substitution cipher.

contest

Data Structures & Algorithms Multiple Choice Questions on “Columnar Transposition”.

1. Which of the following is not a type of traditional cipher?
a) Substitution cipher
b) Transposition cipher
c) Mono alphabetic cipher
d) PKCS cipher

Answer: d
Clarification: There are two types of the traditional cipher. One is transposition cipher and the other is substitution cipher. Whereas PKCS is a modern asymmetric cipher.

2. Which of the following cipher uses two keys to encrypt data?
a) substitution cipher
b) transposition cipher
c) symmetric cipher
d) asymmetric cipher

Answer: d
Clarification: Asymmetric cipher makes use of 2 keys for the purpose of encryption. One is known as public key whereas other is called private key.

3. Asymmetric encryption is also known as?
a) Private key cryptography
b) Public key cryptography
c) Public private key cryptography
d) Traditional cryptography

Answer: b
Clarification: Asymmetric encryption is also known as public key cryptography. Asymmetric cipher makes use of 2 keys for the purpose of encryption.

4. Which of the following is an example of asymmetric encryption technique?
a) one-time pad
b) one-time password
c) DSA
d) blowfish

Answer: c
Clarification: Asymmetric cipher makes use of 2 keys for the purpose of encryption. DSA is an example of asymmetric encryption technique.

5. Columnar cipher falls under the category of?
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: c
Clarification: Columnar cipher is a transposition cipher. It falls under the category of transposition cipher as it encrypts the plain text by rearranging its letters.

6. Which of the following ciphered text would have NOT used transposition cipher for encryption of the plain text “CIPHER”?
a) EPIHRC
b) EHIPCR
c) DTIPRC
d) HRIPEC

Answer: c
Clarification: We know that transposition cipher encrypts the plain text by shuffling the letters of the plain text. So out of the given options, only “DTIPRC” does not have the same set of letters as “CIPHER”.

7. Which of the following cipher is formed by applying columnar transposition cipher twice?
a) Rail Fence cipher
b) Route cipher
c) Double transposition cipher
d) One time pad
View Answer

Answer: c
Clarification: Double transposition cipher is formed by applying columnar transposition cipher twice. For the purpose of encryption, we may use the same key twice or we can use two different keys.

8. In which of the following cipher the plain text and the ciphered text does not have the same set of letters?
a) route cipher
b) columnar transposition cipher
c) myszkowski cipher
d) additive cipher

Answer: d
Clarification: In transposition cipher, the letters remain the same in ciphered and plain text. Their position is only changed whereas in substitution cipher the letters become different in encrypted text. As additive cipher is the only non transposition cipher out of the given options so it will be the correct option.

9. Columnar transposition cipher is harder to crack as compared to double transposition cipher?
a) true
b) false
View Answer

Answer: b
Clarification: Double transposition cipher is formed by applying columnar transposition cipher twice. So it is harder to crack than a simple columnar transposition cipher.

10. How many columns do we need to have in the table, that is used for encryption in columnar transposition cipher when a given keyword is “SECRET” and plain text is “”?
a) 4
b) 5
c) 6
d) 7

Answer: c
Clarification: The number of columns in the table used for the purpose encryption in columnar transposition cipher will always be equal to the number of letters in the keyword. So in this case it will be equal to 6.

11. What will be the encrypted text corresponding to plain text “CLASSIFIED” using columnar transposition cipher with a keyword as “GAMES”?
a) LFDSIASECI
b) SECIAISDFL
c) CILFAISESD
d) LFSECIAISD
Answer: d
Clarification: For encrypting using columnar cipher we have to arrange the letters of the plain text in a table which has the same number of columns as the letters of the keyword. Then the letters of the keyword are arranged in alphabetical order and we read along each column.
3 1 4 2 5
G A M E S
C L A S S
I F I E D
So the ciphered text will be “IFSECIAISD”.

12. How many rows will the letters of the plain text occupy in the table, that is used for encryption in columnar transposition cipher when a given keyword is “SECRET” and plain text is “”?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: The number of columns in the table used for the purpose encryption in columnar transposition cipher will always be equal to the number of letters in the keyword.So when we will write the letters of the plain text row wise then there will be 2 rows of plain text in this case. The table is shown below :-
S E C R E T
1 S A N F O U
2 N D R Y

13. Which of the following statement is not true regarding columnar transposition cipher?
a) it is a weak cipher
b) probability of error is high while deciphering
c) it cannot be combined with other ciphers
d) it is a traditional symmetric cipher

Answer: c
Clarification: Although columnar transposition cipher is a weak cipher in itself. But it can be combined with other substitution ciphers so as to improve its security. The probability of error remains high while decoding columnar cipher as it is a lengthy process.

& Algorithms.

Multiple Choice Questions and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Merge Sort”.

1. 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
Clarification: Merge sort uses divide and conquer in order to sort a given array. This is because it divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together.

2. What is the average case time complexity of merge sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)

Answer: a
Clarification: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. It is found to be equal to O(n log n) using the master theorem.

3. What is the auxiliary space complexity of merge sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
View Answer

Answer: c
Clarification: An additional space of O(n) is required in order to merge two sorted arrays. Thus merge sort is not an in place sorting algorithm.

4. Merge sort can be implemented using O(1) auxiliary space.
a) true
b) false

Answer: a
Clarification: Standard merge sort requires O(n) space to merge two sorted arrays. We can optimize this merging process so that it takes only constant space. This version is known as in place merge sort.

5. What is the worst case time complexity of merge sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)
Answer: a
Clarification: The time complexity of merge sort is not affected by worst case as its algorithm has to implement the same number of steps in any case. So its time complexity remains to be O(n log n).

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

Answer: a
Clarification: Merge sort algorithm divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together. Thus its method of sorting is called merging.

7. What will be the best case time complexity of merge sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)

Answer: a
Clarification: The time complexity of merge sort is not affected in any case as its algorithm has to implement the same number of steps. So its time complexity remains to be O(n log n) even in the best case.

8. 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
View Answer

Answer: d
Clarification: In-place, top down and bottom up merge sort are different variants of merge sort. Whereas linear merge sort is not a possible variant as it is a comparison based sort and the minimum time complexity of any comparison based sort is O(n log n).

9. 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
Clarification: Merge sort is not an adaptive sorting algorithm. This is because it takes O(n log n) time complexity irrespective of any case.

10. 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
Clarification: Quick sort, heap sort, and insertion sort are in-place sorting algorithms, whereas an additional space of O(n) is required in order to merge two sorted arrays. Even though we have a variation of merge sort (to do in-place sorting), it is not the default option. So, among the given choices, merge sort is the most appropriate answer.

11. Which of the following is not a stable sorting algorithm?
a) Quick sort
b) Cocktail sort
c) Bubble sort
d) Merge sort

Answer: a
Clarification: Out of the given options quick sort is the only algorithm which is not stable. Merge sort is a stable sorting algorithm.

12. 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
Clarification: Insertion sort takes linear time to sort a partially sorted array. Though merge and quick sort takes O(n*logn) complexity to sort, merge sort is stable. Hence, Merge sort takes less time to sort partially sorted array.

13. Merge sort is preferred for arrays over linked lists.
a) true
b) false

Answer: b
Clarification: Merge sort is preferred for linked list over arrays. It is because in a linked list the insert operation takes only O(1) time and space which implies that we can implement merge operation in constant time.

14. Which of the following sorting algorithm makes use of merge sort?
a) tim sort
b) intro sort
c) bogo sort
d) quick sort

Answer: a
Clarification: Tim sort is a hybrid sorting algorithm as it uses more than one sorting algorithm internally. It makes use of merge sort and insertion sort.

15. Choose the correct code for merge sort.
a)

void merge_sort(int arr[], int left, int right) 
{ 
    if (left > right) 
    { 
 
        int mid = (right-left)/2; 
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
        merge(arr, left, mid, right); //function to merge sorted arrays
    } 
}

b)

void merge_sort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
 
        int mid = left+(right-left)/2; 
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
        merge(arr, left, mid, right); //function to merge sorted arrays
    } 
}

c)

void merge_sort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
 
        int mid = left+(right-left)/2; 
merge(arr, left, mid, right); //function to merge sorted arrays
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
 
    } 
}

d)

void merge_sort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
 
        int mid = (right-left)/2; 
merge(arr, left, mid, right); //function to merge sorted arrays
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
 
    } 
}

View Answer

Answer: b
Clarification: Merge sort first sorts the two halves of the array individually. Then it merges the two sorted halves in order to obtain sorted array.

16. Which of the following sorting algorithm does not use recursion?
a) quick sort
b) merge sort
c) heap sort
d) bottom up merge sort
Answer: d
Clarification: Bottom up merge sort uses the iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on.