Category: Data Structures & Algorithms Objective Questions

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.

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

1. Which of the following is an example of an unstable sorting algorithm?
a) cycle sort
b) insertion sort
c) bubble sort
d) merge sort

Answer: a
Clarification: Out of the given options only cycle sort is an unstable sorting algorithm. This implies that the relative position of equal valued elements in the input and sorted array does not remain the same when we use cycle sort.

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

Answer: d
Clarification: The worst case performance of cycle sort is O(n²). It is because it has to make n comparisons for each element of the array.

3. What is the auxiliary space requirement of cycle sort?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)

Answer: b
Clarification: Cycle sort requires an auxiliary space of O(1). So this makes it an in-place sorting algorithm.

4. What is the best case time complexity of cycle sort?
a) O(n²)
b) O(n)
c) O(n log n)
d) O(1)
Answer: a
Clarification: Best case time complexity of cycle sort is O(n²). This shows that cycle sort is not an adaptive sorting algorithm and thus makes it undesirable when the given array is already almost sorted.

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

Answer: a
Clarification: The average case performance of cycle sort is O(n²). It is because it has to make n comparisons for each element of the array.

6. Cycle sort is an adaptive sorting algorithm.
a) true
b) false
Answer: b
Clarification: The time complexity of cycle sort is O(n²) in any case. So cycle sort algorithm is not adaptive, as it will take the same time to sort an already sorted array and any other randomly arranged array.

7. Which of the following sorting algorithm is in-place?
a) Merge sort
b) Cycle sort
c) Counting sort
d) Radix sort

Answer: b
Clarification: Cycle sort has an auxiliary space complexity of O(1). So it qualifies to be an in-place sort. All other given options are not in place sorting algorithm.

8. Which of the following is an advantage of cycle sort?
a) it can sort large arrays efficiently
b) it has a low time complexity
c) it requires minimal write operations
d) it is an adaptive sorting algorithm

Answer: c
Clarification: Cycle sort is a slow sorting algorithm as compared to quick sort, merge sort etc. and is also not adaptive. But it offers an advantage that it performs minimal write operations which can be very useful in a situation where the write operation is expensive.

9. Cycle sort is a comparison based sort.
a) true
b) false

Answer: a
Clarification: Cycle sort is a comparison based sorting algorithm. This is because it compares elements in order to sort them.

10. Which of the following sorting algorithm uses the method of insertion?
a) cycle sort
b) bubble sort
c) quick sort
d) selection sort

Answer: a
Clarification: Cycle sort is the only algorithm from the given ones that uses the method of insertion. Other than this, insertion sort also uses the method of insertion for sorting.

11. How many write operations will be required to sort the array arr={2,4,3,5,1} using cycle sort?
a) 4
b) 5
c) 6
d) 3

Answer: a
Clarification: Cycle sort requires a minimum number of write operations in order to sort a given array. So in this case, only 4 write operations will be required.

12. Which of the following algorithm is best suited for the case where swap operation is expensive?
a) bubble sort
b) cycle sort
c) cocktail sort
d) merge sort

Answer: b
Clarification: Cycle sort is a slow sorting algorithm but it requires a minimum number of write operations in order to sort a given array. So it is useful when the write/swap operation is expensive.

and Answers.

contest