Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Fractional Knapsack Problem”.

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

Answer: b
Clarification: Fractional knapsack problem is also called continuous knapsack problem. Fractional knapsack is solved using dynamic programming.

2. 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
Clarification: Greedy algorithm is used to solve this problem. We first sort items according to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. At the end, we add the next item as much as we can.

3. 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
Clarification: The objective is to fill the knapsack of some given volume with different materials such that the value of selected items is maximized.

4. Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible
b) Both are the same
c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming
d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

Answer: d
Clarification: In fractional knapsack problem we can partially include an item into the knapsack whereas in 0/1 knapsack we have to either include or exclude the item wholly.

5. Time complexity of fractional knapsack problem is ____________
a) O(n log n)
b) O(n)
c) O(n²)
d) O(nW)

Answer: a
Clarification: As the main time taking a step is of sorting so it defines the time complexity of our code. So the time complexity will be O(n log n) if we use quick sort for sorting.

6. Fractional knapsack problem can be solved in time O(n).
a) True
b) False

Answer: a
Clarification: It is possible to solve the problem in O(n) time by adapting the algorithm for finding weighted medians.

7. 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
Clarification: The value/weight ratio are-{2,3,4}. So we include the second and third items wholly into the knapsack. This leaves only 5 units of volume for the first item. So we include the first item partially.
Final value = 20+30+(40/4)=60.

8. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
a) True
b) False

Answer: a
Clarification: As fractional knapsack gives extra liberty to include the object partially which is not possible with 0/1 knapsack, thus we get better results with a fractional knapsack.

9. 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
Clarification: The main time taking step is to sort the items according to their value/weight ratio. It defines the time complexity of the code.

10. 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
Clarification: Assuming items to be divisible-
The value/weight ratio are {3, 2, 4}.So we include third and first items wholly. So, now only 15 units of volume are left for second item. So we include it partially.
Final volume = 20+60+50x(15/25)=80+30=110
Assuming items to be indivisible- In this case we will have to leave one item due to insufficient capacity.
Final volume = 60 + 20 = 80.

& Algorithms.

Multiple Choice Questions and Answers.

Data Structure Multiple Choice Questions on “Longest Common Subsequence”.

1. 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
Clarification: Both recursion and dynamic programming can be used to solve the longest subsequence problem.

2. 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
Clarification: The longest common subsequence is “PRTPQRS” and its length is 7.

3. 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
Clarification: To find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string.

4. Longest common subsequence is an example of ____________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer

Answer: b
Clarification: Longest common subsequence is an example of 2D dynamic programming.

5. What is the time complexity of the brute force algorithm used to find the longest common subsequence?
a) O(n)
b) O(n²)
c) O(n³)
d) O(2ⁿ)

Answer: d
Clarification: The time complexity of the brute force algorithm used to find the longest common subsequence is O(2ⁿ).

6. Consider the following dynamic programming implementation of the longest common subsequence problem:

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
            for(j = 1; j <= len2; j++)
            {
                 if(str1[i-1] == str2[j - 1])
                  ______________;
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
            }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = " abcedfg", str2[] = "bcdfh";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

Which of the following lines completes the above code?
a) arr[i][j] = 1 + arr[i][j].
b) arr[i][j] = 1 + arr[i – 1][j – 1].
c) arr[i][j] = arr[i – 1][j – 1].
d) arr[i][j] = arr[i][j].

Answer: b
Clarification: The line, arr[i][j] = 1 + arr[i – 1][j – 1] completes the above code.

7. What is the time complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
            for(j = 1; j <= len2; j++)
            {
                 if(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
            }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = " abcedfg", str2[] = "bcdfh";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

a) O(n)
b) O(m)
c) O(m + n)
d) O(mn)

Answer: d
Clarification: The time complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

8. What is the space complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
            for(j = 1; j <= len2; j++)
            {
                 if(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
            }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = " abcedfg", str2[] = "bcdfh";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

a) O(n)
b) O(m)
c) O(m + n)
d) O(mn)

Answer: d
Clarification: The space complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

9. What is the output of the following code?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
          for(j = 1; j <= len2; j++)
          {
              if(str1[i-1] == str2[j - 1])
                  arr[i][j] = 1 + arr[i - 1][j - 1];
              else
                  arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

a) 3
b) 4
c) 5
d) 6
Answer: b
Clarification: The program prints the length of the longest common subsequence, which is 4.

10. 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
Clarification: The length of the longest common subsequence is 4. But ‘fgmna’ is not the longest common subsequence as its length is 5.

11. What is the value stored in arr[2][3] when the following code is executed?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
         return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
           for(j = 1; j <= len2; j++)
           {
                if(str1[i-1] == str2[j - 1])
                    arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                    arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
           }
      }
      return arr[len1][len2];
}
int main()
{
      char str1[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

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

Answer: a
Clarification: The value stored in arr[2][3] is 1.

12. What is the output of the following code?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lcs(char *str1, char *str2)
{
      int i,j,len1,len2;
      len1 = strlen(str1);
      len2 = strlen(str2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0; i <= len1; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len2; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len1; i++)
      {
           for(j = 1; j <= len2; j++)
           {
                if(str1[i-1] == str2[j - 1])
                   arr[i][j] = 1 + arr[i - 1][j - 1];
                else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
           }
      }
      return arr[len1][len2];
}
int main()
{
     char str1[] = "abcd", str2[] = "efgh";
     int ans = lcs(str1,str2);
     printf("%d",ans);
     return 0;
}

a) 3
b) 2
c) 1
d) 0

Answer: d
Clarification: The program prints the length of the longest common subsequence, which is 0.

contest

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

1. Which of the following cipher does not require a key for encrypting plain text?
a) atbash cipher
b) affine cipher
c) playfair cipher
d) vigenere cipher

Answer: a
Clarification: Out of the given options only atbash cipher does not require a key for encryption. Atbash cipher is an example of a substitution cipher.

2. Atbash cipher was originally used for encrypting _____________
a) english alphabet
b) greek alphabet
c) hebrew alphabet
d) hindi alphabet

Answer: c
Clarification: Atbash cipher was originally built to encrypt hebrew alphabet. But it can be used to encrypt any type of alphabets.

3. Which of the following cipher is a special case of affine cipher?
a) Vigenere cipher
b) Autokey cipher
c) Atbash cipher
d) Hill cipher
Answer: c
Clarification: Atbash cipher is a special case of affine cipher. We have to assume a=b=25 as the key in affine cipher to get the same encryption.

4. Choose the weakest cipher from the following?
a) vigenere cipher
b) rail fence cipher
c) hill cipher
d) atbash cipher
Answer: d
Clarification: Atbash cipher is the weakest cipher out of the given options. This is because it is a simple mono alphabetic substitution cipher with almost no security. It can be cracked without even knowing which technique has been used for encryption.

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

Answer: d
Clarification: Atbash cipher is the only mono alphabetic substitution cipher out of the given options. All the remaining options fall under the category of poly alphabetic cipher.

6. Atbash cipher is less secure than affine cipher.
a) True
b) False

Answer: a
Clarification: Affine cipher is more secure as compared to pigpen cipher. Atbash cipher is a special case of affine cipher and can be cracked without even knowing which technique has been used for encryption.

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

A - Z	  J - Q	    S - H
B - Y	  K - P	    T - G
C - X	  L - O	    U - F
D - W	  M - N	    V - E
E - V	  N - M	    W - D
F - U	  O - L	    X - C
G - T	  P - K	    Y - B
H - S	  Q - J	    Z - A
I - R	  R - I

8. Atbash cipher cannot be cracked until the exact type of encryption of ciphered text is known.
a) True
b) False

Answer: b
Clarification: Atbash cipher is a very weak cipher. It can be easily broken without even knowing the exact technique which has been used for encryption. We can just assume the ciphered text to be a substitution cipher in order to crack it.

9. What will be the ciphered text corresponding to plain text “SECRET” if atbash cipher is used for encryption?
a) VHIXVG
b) HVXIVG
c) HXVIVG
d) VIHXIV

A - Z	  J - Q	    S - H
B - Y	  K - P	    T - G
C - X	  L - O	    U - F
D - W	  M - N	    V - E
E - V	  N - M	    W - D
F - U	  O - L	    X - C
G - T	  P - K	    Y - B
H - S	  Q - J	    Z - A
I - R	  R - I

10. What will be the plain text corresponding to ciphered text “MAO” if atbash cipher is used for encryption?
a) NZL
b) IND
c) AUS
d) ENG

A - Z	  J - Q	    S - H
B - Y	  K - P	    T - G
C - X	  L - O	    U - F
D - W	  M - N	    V - E
E - V	  N - M	    W - D
F - U	  O - L	    X - C
G - T	  P - K	    Y - B
H - S	  Q - J	    Z - A
I - R     R - I

11. Which of the following is not true about atbash cipher?
a) it is a mono alphabetic substitution cipher
b) it can only be used to encrypt hebrew alphabet
c) it is a special case of affine cipher
d) it is weaker than playfair cipher

Answer: b
Clarification: Atbash cipher was originally built to encrypt hebrew alphabet. But it can be used to encrypt any type of alphabets.

Data Structures & Algorithms Multiple Choice Questions on “Hamming Code”.

1. The most common hamming codes are a generalized version of?
a) Hamming(7, 4) code
b) Hamming(8, 4) code
c) Hamming(6, 3) code
d) Hamming(5, 7) code

Answer: a
Clarification: The most common hamming codes generalize to form hamming(7, 4) code. It encodes four bits of data into seven bits by adding three parity bits.

2. What is the minimal Hamming distance between any two correct codewords?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: c
Clarification: Since we use a generalized version of Hamming(7, 4) code, the minimal hamming distance is 3. It cannot correct burst errors.

3. Why do we require hamming codes?
a) Error correction
b) Encryption only
c) Decryption
d) Bit stuffing

Answer: a
Clarification: Hamming codes are used for the purpose of error detection and correction. It is also used for channel encoding and decoding. They are linear-error correcting codes.

4. Hamming codes can be used for both single-bit error and burst error detection and correction.
a) True
b) False

Answer: b
Clarification: Hamming bits are suitable only for single-bit error detection and correction and two bit error detection. It is very unlikely to detect burst errors.

5. Who invented Hamming codes?
a) Richard Hamming
b) Ross Hamming
c) Shannon
d) Huffman

Answer: a
Clarification: Richard W. Hamming invented hamming codes in Bell Telephone Laboratory to minimize the errors in punched card readers. Huffman invented huffman codes. Shannon invented Shannon-Fanno codes.

6. What is the total block length ‘n’ of a Hamming code?
a) 2^r
b) 2^r-1
c) 2^r-1-1
d) 2^r+1
View Answer

Answer: b
Clarification: Hamming codes are a class of binary linear codes, hence r>=2. For a hamming(7, 4) code, the block length ‘n’ is 2^r-1 where r is the parity bit. Here, r=3.

7. What is the message length ‘k’ of a Hamming(7,4) code?
a) 2^r-1
b) 2^r-r+1
c) 2^r-r-1
d) 2^r+1-r
Answer: c
Clarification: Hamming codes are a class of binary linear codes, hence r>=2. For a hamming(7,4) code, the message length ‘k’ is 2^r-r-1 where r is the parity bit. Here, r=3.

8. What is the rate of hamming codes?
a) 1-[r/(2^r-1)]
b) 1-(r/2^r)
c) 1+(r/2^r)
d) r/2^r+1

Answer: a
Clarification: Rate of a hamming code is message length divided by block length (i.e.) 2^r-r-1/2^r-1 = 1-[r/(2^r-1)]. It is the highest rate for a minimum distance of three.

9. A two-out-of-five code consists of _________
a) Two 0s and three 1s
b) Three 0s and two 1s
c) Four 0s and one 1s
d) One 0s and four 1s

Answer: b
Clarification: A two-out-of-five code consists of three 0s and two 1s. Hence, it contains ten possible combinations to represent digits from 0-9.

10. Including a parity bit along with the data surely detects the errors.
a) true
b) false

Answer: b
Clarification: If error has occurred in a data string, parity will change inorder to indicate errors. However, if the error occurs in parity bit, the error goes undetected.

11. ________ is the mechanism of sending data bits multiple times to ensure consistency.
a) Repetition
b) Duplication
c) Mirroring
d) Redundancy

Answer: a
Clarification: Repeating data bits multiple times is done to ensure consistency. If the data bit to be sent is a 1, a n=3 repetition code will send 111. If the bits are not the same, an error has occurred.

12. An Extended hamming code is also called as __________
a) SEDDEC
b) SEDDED
c) SECDED
d) SECDEC

Answer: c
Clarification: An Extended Hamming code is also called as SECDED (Single Error Correction Double Error Detection). The most popular codes are (72, 64) code and (127,120) code.

13. What is the code rate of a repetition Hamming code (3, 1)?
a) 1
b) 3
c) 1/3
d) 1.3

Answer: c
Clarification: The code rate of a repetition hamming code is the second number divided by the first number. Here, it is 1/3.

14. For a hamming code of parity bit m=8, what is the total bits and data bits?
a) (255, 247)
b) (127, 119)
c) (31, 26)
d) (0, 8)

Answer: a
Clarification: Total bits are computed as, 2^m-1 = 2⁸-1 =255.
Data bits are computed as 2^m-m-1= 2⁸-8-1= 247.

15. What is the rate of the hamming code of parity bit m=8?
a) 0.94
b) 0.92
c) 0.90
d) 0.97
Answer: d
Clarification: For a hamming code of parity bit 8, total bits = 255 and data bits = 247. Rate= data bits/ total bits
= 247/255 = 0.969 = 0.97.

contest

Data Structures & Algorithms Multiple Choice Questions on “Bottom-Up Mergesort”.

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

2. What is the average case time complexity of standard 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. This can be solved using master’s theorem and is found equal to O(n log n).

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

Answer: c
Clarification: The merging of two sorted arrays requires an additional space of n due to which the auxiliary space requirement of merge sort is O(n). Thus merge sort is not an in place sorting algorithm.

4. What is the auxiliary space complexity of bottom up merge sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: b
Clarification: The auxiliary space complexity of bottom up merge sort is same as standard merge sort as both uses the same algorithm for merging the sorted arrays which takes o(n) space. But bottom up merge sort does not need to maintain a call stack.

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

Answer: a
Clarification: The merge function in the bottom up merge sort takes O(n) time which is placed inside the for loop. The loop runs for O(log n) time, thus the overall time complexity of the code becomes O(n log n).

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

Answer: a
Clarification: Merge sort implements sorting by merging the sorted versions of smaller parts of the array. Thus its method of sorting is called merging.

7. Bottom up merge sort uses recursion.
a) true
b) false

Answer: b
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.

8. Bottom up merge sort is a stable sort.
a) true
b) false
Answer: a
Clarification: Bottom up merge sort like standard merge sort is a stable sort. This implies that the relative position of equal valued elements in the input and sorted array remain same.

9. Choose the correct statement about bottom up merge sort from the following?
a) bottom up merge sort has greater time complexity than standard merge sort
b) bottom up merge sort has lesser time complexity than standard merge sort
c) bottom up merge sort saves auxiliary space required on call stack
d) bottom up merge sort uses recursion.
Answer: c
Clarification: Bottom up merge sort unlike standard merge sort uses an iterative algorithm for sorting. Thus, it saves auxiliary space required by the call stack.

10. Choose the correct option from the following that represents bottom up merge sort function?
a)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);		
			merge(Arr, temp, left, mid, right);
		}
	}
}

b)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

c)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

d)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

View Answer

Answer: a
Clarification: Bottom up merge sort uses 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. The process of merging the sorted arrays is same as in standard merge sort.

and Answers.

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

1. Which one of the following sorting algorithm requires recursion?
a) pigeonhole sort
b) strand sort
c) insertion sort
d) counting sort
Answer: b
Clarification: Strand sort requires the use of recursion for implementing its algorithm. On the other hand, the sorting algorithms given in the remaining options use iterative methods.

2. Strand sort is most efficient for data stored in?
a) linked list
b) arrays
c) trees
d) graphs
Answer: a
Clarification: Strand sort is most efficient when data is stored in a linked list as it involves many insertions and deletions which is performed quite efficiently with the help of a linked list. Using an array would increase time complexity significantly.

3. In which of the following case strand sort is most efficient?
a) when input array is already sorted
b) when input array is reverse sorted
c) when input array is large
d) when input array is has randomly spread elements

Answer: a
Clarification: The best case of strand sort occurs when the input array is already sorted. In this case, it has linear time complexity.

4. What is the auxiliary space complexity of strand sort?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: The auxiliary space complexity of strand sort is O(n). It is because a sub-list of size n has to be maintained.

5. Which of the following sorting algorithm is not in place?
a) quick sort
b) strand sort
c) cycle sort
d) heap sort

Answer: b
Clarification: Strand sort has an auxiliary space complexity of O(n). So it is not an in place sorting algorithm.

6. Strand sort is a comparison based sorting algorithm.
a) true
b) false
Answer: a
Clarification: Pigeonhole sort is an example of a comparison based sorting algorithm. This is because it compares the value of elements present in a list in order to sort them.

7. Strand sort is a stable sorting algorithm.
a) true
b) false

Answer: a
Clarification: Strand sort is an example of a stable sorting algorithm. It is because the elements with identical values appear in the same order in the output array as they were in the input array.

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

Answer: c
Clarification: Average case time complexity of strand sort is O(n2). So it is not as efficient as quick sort or merge sort.

9. What is the best case time complexity of strand sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n² log n)

Answer: a
Clarification: Best case time complexity of strand sort is O(n). It occurs in the case where the input array is already sorted.

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

Answer: c
Clarification: Worst case time complexity of strand sort is O(n²). It occurs in the case where the input array is in reverse sorted order.

11. Strand sort algorithm used which of the following method for sorting a list?
a) merging
b) selection
c) insertion
d) partitioning

Answer: b
Clarification: Strand sort uses the method of selection for sorting any given list. This is because it selects the strands of elements from the input list which are sorted.

12. Which of the following is an adaptive sorting algorithm?
a) heap sort
b) strand sort
c) selection sort
d) merge sort

Answer: b
Clarification: Strand sort is an adaptive sorting algorithm. This is because it gives a better performance when the input list is almost sorted.

and Answers.