250+ TOP MCQs on Recursive Selection Sort and Answers

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

1. Which of the following sorting algorithm has best case time complexity of O(n2)?
a) bubble sort
b) selection sort
c) insertion sort
d) stupid sort

Answer: b
Clarification: Selection sort is not an adaptive sorting algorithm. It finds the index of minimum element in each iteration even if the given array is already sorted. Thus its best case time complexity becomes O(n2).

2. Which of the following is the biggest advantage of selection sort?
a) its has low time complexity
b) it has low space complexity
c) it is easy to implement
d) it requires only n swaps under any condition

Answer: d
Clarification: Selection sort works by obtaining least value element in each iteration and then swapping it with the current index. So it will take n swaps under any condition which will be useful when memory write operation is expensive.

3. What will be the recurrence relation of the code of recursive selection sort?
a) T(n) = 2T(n/2) + n
b) T(n) = 2T(n/2) + c
c) T(n) = T(n-1) + n
d) T(n) = T(n-1) + c

Answer: c
Clarification: Function to find the minimum element index takes n time.The recursive call is made to one less element than in the previous call so the overall recurrence relation becomes T(n) = T(n-1) + n.

4. Which of the following sorting algorithm is NOT stable?
a) Selection sort
b) Brick sort
c) Bubble sort
d) Merge sort

Answer: a
Clarification: Out of the given options selection sort is the only algorithm which is not stable. It is because the order of identical elements in sorted output may be different from input array.

5. What will be the best case time complexity of recursive selection sort?
a) O(n)
b) O(n2)
c) O(log n)
d) O(n log n)

Answer: b
Clarification: Selection sort’s algorithm is such that it finds the index of minimum element in each iteration even if the given array is already sorted. Thus its best case time complexity becomes O(n2).

6. Recursive selection sort is a comparison based sort.
a) true
b) false

Answer: a
Clarification: In selection sort we need to compare elements in order to find the minimum element in each iteration. So we can say that it uses comparisons in order to sort the array. Thus it qualifies as a comparison based sort.

7. What is the average case time complexity of recursive selection sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)

Answer: c
Clarification: The overall recurrence relation of recursive selection sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2). It is unvaried throughout the three cases.

8. What is the bidirectional variant of selection sort?
a) cocktail sort
b) bogo sort
c) gnome sort
d) bubble sort

Answer: a
Clarification: A bidirectional variant of selection sort is called cocktail sort. It’s an algorithm which finds both the minimum and maximum values in the array in every pass. This reduces the number of scans of the array by a factor of 2.

9. Choose correct C++ code for recursive selection sort from the following.
a)

#include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == 0) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] < a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 
 
	if (index == n) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x == index) 
	{	    
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	recursiveSelectionSort(arr, n); 	
	return 0; 
}

b)

#include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] < a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 
 
	if (index == n) 
        return; 	 
	int x = minIndex(a, index, n-1);	 
	if (x != index) 
	{
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	recursiveSelectionSort(arr, n); 	
	return 0; 
}

c)

#include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 
	return (a[i] > a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 	
	if (index == n) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x != index) 
	{	    
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
        recursiveSelectionSort(arr, n); 
	return 0; 
}

d)

 #include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] > a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 	
	if (index == 0) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x == index) 
	{	    
	    	swap(a[x], a[index]);
	}
 	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	recursiveSelectionSort(arr, n); 
        return 0; 
}

View Answer

Answer: b
Clarification: Using the function recursiveSelectionSort() we find the element that needs to be placed at the current index. For finding the minimum element index we use another function minIndex(). After finding the minimum element index the current element is swapped with this element in the function recursiveSelectionSort().

 

10. What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The first swap takes place between 1 and 5. The second swap takes place between 3 and 2 which sorts our array.

250+ TOP MCQs on Fibonacci using Dynamic Programming and Answers

Data Structure Multiple Choice Questions on “Fibonacci using Dynamic Programming”.

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

Answer: d
Clarification: Each of the above mentioned methods can be used to find the nth fibonacci term.

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

int fibo(int n)
    if n <= 1
	return n
    return __________

Which line would make the implementation complete?
a) fibo(n) + fibo(n)
b) fibo(n) + fibo(n – 1)
c) fibo(n – 1) + fibo(n + 1)
d) fibo(n – 1) + fibo(n – 2)

Answer: d
Clarification: Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a fibonacci sequence would be given by:
fibo(n) = fibo(n-1) + fibo(n-2).

3. What is the time complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n2)
c) O(n!)
d) Exponential
Answer: d
Clarification: The recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). So, the time complexity is given by:
T(n) = T(n – 1) + T(n – 2)
Approximately,
T(n) = 2 * T(n – 1)
= 4 * T(n – 2)
= 8 * T(n – 3)
:
:
:
= 2k * T(n – k)
This recurrence will stop when n – k = 0
i.e. n = k
Therefore, T(n) = 2n * O(0) = 2n
Hence, it takes exponential time.
It can also be proved by drawing the recursion tree and counting the number of leaves.

4. Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:

fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) 
+ fibonacci(3)	+ fibonacci(3) + fibonacci(2)
:
:
:

Which property is shown by the above function calls?
a) Memoization
b) Optimal substructure
c) Overlapping subproblems
d) Greedy

Answer: c
Clarification: From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.

5. What is the output of the following program?

#include
int fibo(int n)
{
      if(n<=1)
	 return n;
      return fibo(n-1) + fibo(n-2);
}
int main()
{   
      int r = fibo(50000);
      printf("%d",r); 
      return 0;
}

a) 1253556389
b) 5635632456
c) Garbage value
d) Runtime error

Answer: d
Clarification: The value of n is 50000. The function is recursive and it’s time complexity is exponential. So, the function will be called almost 250000 times. Now, even though NO variables are stored by the function, the space required to store the addresses of these function calls will be enormous. Stack memory is utilized to store these addresses and only a particular amount of stack memory can be used by any program. So, after a certain function call, no more stack space will be available and it will lead to stack overflow causing runtime error.

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

Answer: a
Clarification: The recursive implementation doesn’t store any values and calculates every value from scratch. So, the space complexity is O(1).

7. Consider the following code to find the nth fibonacci term:

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   __________
  	   __________
       return curFib

Complete the above code.
a)

prevFib = curFib
curFib = curFib

b)

prevFib = nextFib
curFib = prevFib

c)

prevFib = curFib
curFib = nextFib

d)

prevFib = nextFib
nextFib = curFib

Answer: c
Clarification: The lines, prevFib = curFib and curFib = nextFib, make the code complete.

 
 

8. What is the time complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

a) O(1)
b) O(n)
c) O(n2)
d) Exponential
Answer: b
Clarification: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

9. What is the space complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

a) O(1)
b) O(n)
c) O(n2)
d) Exponential
Answer: a
Clarification: To calculate the nth term, we just store the previous term and the current term and then calculate the next term using these two terms. It takes a constant space to store these two terms and hence O(1) is the answer.

10. What will be the output when the following code is executed?

#include
int fibo(int n)
{
      if(n==0)
         return 0;
      int i;
      int prevFib=0,curFib=1;
      for(i=1;i<=n-1;i++)
      {
           int nextFib = prevFib + curFib;
	   prevFib = curFib;
           curFib = nextFib;
      }
      return curFib;
}
int main()
{
      int r = fibo(10);  
      printf("%d",r);
      return 0;
}

a) 34
b) 55
c) Compile error
d) Runtime error
View Answer

Answer: b
Clarification: The output is the 10th fibonacci number, which is 55.

11. Consider the following code to find the nth fibonacci term using dynamic programming:

1. int fibo(int n)
2.   int fibo_terms[100000]  //arr to store the fibonacci numbers
3.   fibo_terms[0] = 0
4.   fibo_terms[1] = 1
5.		
6.   for i: 2 to n
7.	 fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.   return fibo_terms[n]

Which property is shown by line 7 of the above code?
a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure
View Answer

Answer: a
Clarification: We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.

12. Consider the following code to find the nth fibonacci term using dynamic programming:

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

Which technique is used by line 7 of the above code?
a) Greedy
b) Recursion
c) Memoization
d) Overlapping subproblems

Answer: c
Clarification: Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.

13. What is the time complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

a) O(1)
b) O(n)
c) O(n2)
d) Exponential

Answer: b
Clarification: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

14. What is the space complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

int fibo(int n)
        int fibo_terms[100000]  //arr to store the fibonacci numbers
        fibo_terms[0] = 0
	fibo_terms[1] = 1
 
	for i: 2 to n
		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
 
	return fibo_terms[n]

a) O(1)
b) O(n)
c) O(n2)
d) Exponential

Answer: b
Clarification: To calculate the nth term, we store all the terms from 0 to n – 1. So, it takes O(n) space.

15. What will be the output when the following code is executed?

#include
int fibo(int n)
{
      int i;
      int fibo_terms[100];
      fibo_terms[0]=0;
      fibo_terms[1]=1;
      for(i=2;i<=n;i++)
          fibo_terms[i] = fibo_terms[i-2] + fibo_terms[i-1];
      return fibo_terms[n];
}
int main()
{
      int r = fibo(8);
      printf("%d",r);
      return 0;
}

a) 34
b) 55
c) Compile error
d) 21

Answer: d
Clarification: The program prints the 8th fibonacci term, which is 21.

and Answers.

250+ TOP MCQs on Minimum Insertions to form a Palindrome and Answers

Data Structure Assessment Questions and Answers on “Minimum Insertions to form a Palindrome”.

1. Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
a) Greedy algorithm
b) Recursion
c) Dynamic programming
d) Both recursion and dynamic programming
Answer: d
Clarification: Dynamic programming and recursion can be used to solve the problem.

2. In which of the following cases the minimum no of insertions to form palindrome is maximum?
a) String of length one
b) String with all same characters
c) Palindromic string
d) Non palindromic string
Answer: d
Clarification: In string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.

3. In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.
a) True
b) False

Answer: b
Clarification: In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. For example, consider the string “abc”. The string can be converted to “abcba” by inserting “a” and “b”. The number of insertions is two, which is equal to length minus one.

4. Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: b
Clarification: The string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. Thus, only one insertion is required.

5. Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: a
Clarification: The given string is already a palindrome. So, no insertions are required.

6. Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
a) Minimum number of jumps problem
b) Longest common subsequence problem
c) Coin change problem
d) Knapsack problems
View Answer

Answer: b
Clarification: A variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.

7. Consider the following dynamic programming implementation:

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return _____________;
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

Which of the following lines should be added to complete the code?
a) arr[len][len]
b) len + arr[len][len]
c) len
d) len – arr[len][len]

Answer: d
Clarification: arr[len][len] contains the length of the longest palindromic subsequence. So, len – arr[len][len] gives the minimum number of insertions required to form a palindrome.

8. What is the time complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(mn)

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

9. What is the space complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                 arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(mn)

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

10. What is the output of the following code?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

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

Answer: b
Clarification: The length of the longest palindromic subsequence is 3. So, the output will be 5 – 3 = 2.

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

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
         arr[i][0] = 0;
      for(i = 0; i <= len; i++)
         arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                 arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

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

Answer: a
Clarification: The value stored in arr[2][4] when the above code is executed is 2.

12. What is the output of the following code?

#include
#include
int max(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_ins(char *s)
{
      int len = strlen(s), i, j;
      int arr[len + 1][len + 1];
      char rev[len + 1];
      strcpy(rev, s);
      strrev(rev);
      for(i = 0;i <= len; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
              if(s[i - 1] == rev[j - 1])
                arr[i][j] = arr[i - 1][j - 1] + 1;
              else
                  arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return len - arr[len][len];
}
int main()
{
      char s[] = "efgfe";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

a) 0
b) 2
c) 4
d) 6

Answer: a
Clarification: Since the string “efgfe” is already a palindrome, the number of insertions required is 0.

& Algorithms.

and Answers.

250+ TOP MCQs on Rail Fence Cipher and Answers

Data Structures & Algorithms Multiple Choice Questions on “Rail Fence”.

1. What is the alternative name given to Rail fence cipher?
a) random cipher
b) matrix cipher
c) zig zag cipher
d) columnar cipher
View Answer

Answer: c
Clarification: Rail fence cipher is also known as zig zag cipher. It is so because the plain text gets ciphered by arranging the letters in a zig zag fashion.

2. Rail fence cipher is an example of ___________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher
View Answer

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

3. Encryption in Rail fence cipher is done using _____________
a) by arranging the letters in a zig zag fashion in a table
b) by randomly arranging letters
c) by arranging letters in vigenere table
d) by swapping adjacent letters

Answer: a
Clarification: Rail fence cipher is a transposition cipher. It encrypts a given plain text by arranging the letters in a zig zag fashion in a table.

4. Which of the following ciphers are created by shuffling the letters of a word?
a) substitution cipher
b) transposition cipher
c) vigenere cipher
d) hill cipher

Answer: b
Clarification: There are two types of traditional ciphers- Transposition and substitution cipher. In transposition cipher the letters of the given data are shuffled in a particular order, fixed by a given rule.

5. Which of the following is not a type of poly alphabetic cipher?
a) Autokey cipher
b) Hill cipher
c) One time pad cipher
d) Additive cipher
Answer:d
Clarification: In poly alphabetic cipher each symbol of plain text is replaced by a different cipher text regardless of its occurrence. Out of the given options, only additive cipher is not a poly alphabetic cipher.

6. Which of the following is are two types of traditional cipher?
a) transposition cipher and replacement cipher
b) transposition cipher and substitution cipher
c) transforming cipher and substitution cipher
d) transforming cipher and replacement cipher

Answer: b
Clarification: There are two types of a traditional cipher. First is transposition cipher and the second is substitution cipher.

7. The number of columns in the table used for encryption in rail fence cipher depends upon the given key value.
a) True
b) False

Answer: b
Clarification: The number of columns in the table of rail fence cipher is always equal to the number of letters in the plain text. It is independent of the given key value.

8. What will be the plain text corresponding to cipher text “SCSEMG” if rail fence cipher is used with key value 2?
a) MSGSEC
b) SECMSG
c) GSMSEC
d) SECGSM

Answer: b
Clarification: For decryption we reverse the process used in encryption.

So the resulting plain text is “SECMSG”.

9. Rail fence cipher is more secure than one time pad cipher.
a) True
b) False

Answer: b
Clarification: One time pad cipher is one of the most secure traditional cipher as it is almost impossible to crack. Rail fence cipher is not very hard to crack. Thus rail fence cipher is less secure than one time pad cipher.

10. In which of the following cipher the plain text and the ciphered text have same letters?
a) autokey cipher
b) rail fence cipher
c) vigenere cipher
d) additive cipher
Answer: b
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. So rail fence cipher will be the correct option.

11. What will be the ciphered text if rail fence cipher is used for encrypting the plain text “” with the key value given to be 2?
a) SNONRAFUDY
b) SORAFUDYNN
c) SNAUDNORFY
d)

Answer: a
Clarification: For encrypting a plain text using rail fence cipher we use a table having the number of rows equal to key value as shown below. Then we read along the rows to get the ciphered text.

So the ciphered text becomes “SNONRAFUDY”.

250+ TOP MCQs on First-in, First-out Algorithm (FIFO) and Answers

Data Structures & Algorithms Multiple Choice Questions on “First-in, First-out Algorithm (FIFO)”.

1. ________ is a typical online problem from the competitive analysis to determine the optimal solution.
a) Page replacement algorithm
b) Segmentation
c) Paging
d) Segmentation with paging

Answer: a
Clarification: Page replacement is a typical online problem from the competitive analysis. They determine which pages to page out or write to disk.

2. Which of the following is the simplest page replacement algorithm?
a) FIFO
b) Optimal page replacement
c) LRU replacement
d) Counting based replacement

Answer: a
Clarification: FIFO is the simplest page replacement algorithm since LRU and optimal replacement algorithms require past and future data patterns respectively.

3. __________ algorithm associates with each page the time when the page was brought into memory.
a) Optimal page replacement
b) FIFO
c) LRU replacement algorithm
d) Counting based replacement
View Answer

Answer: b
Clarification: FIFO algorithm associates with each page the time when the page was brought into memory. The new page is inserted at the tail of the queue.

4. As the number of frames available increases, the number of page faults decreases.
a) True
b) False
Answer: a
Clarification: One of the rules of the page replacement algorithm is that, as the number of frames available increases, the number of page faults decreases.

5. Which of the following page replacement algorithms return the minimum number of page faults?
a) LRU replacement algorithm
b) Optimal page replacement algorithm
c) FIFO
d) Counting based replacement

Answer: b
Clarification: Though FIFO is the simplest of all algorithms, optimal page replacement algorithm returns the minimum number of page faults.

6. Which of the following is the main drawback of FIFO page replacement algorithm?
a) Requirement of large memory
b) Frame allocation
c) Reduction in multiprogramming
d) Reduced optimality

Answer: c
Clarification: The main drawback of FIFO page replacement algorithm is that it reduces the level of multiprogramming and also causes Belady’s anomaly.

7. Which of the following is required to determine the number of page faults in FIFO?
a) Page number
b) Page frame number
c) Memory capacity
d) Segment number

Answer: b
Clarification: To determine the number of page faults in a page replacement algorithm using FIFO, we require page frame number.

8. In a FIFO algorithm, when a page is to be replaced, which of the following page is chosen?
a) Oldest page
b) Newest page
c) Frequently occurred page in past
d) Frequently occurred page in future

Answer: a
Clarification: In FIFO page replacement algorithm, when a page is to be replaced, the oldest page is chosen and replaced at the tail of the queue.

9. The cost required to execute a FIFO algorithm is expensive.
a) True
b) False

Answer: b
Clarification: The cost of a FIFO algorithm is cheap and intuitive and it is used in poor practical applications.

10. FIFO algorithm is used by __________ operating system.
a) Linux
b) Mac
c) Windows
d) VAX/VMS

Answer: d
Clarification: Of the following given operating systems, VAX/VMS uses a FIFO algorithm.

11. What is the competitive analysis of the FIFO algorithm?
a) k/k+1
b) k+1
c) k(k+1)
d) k/(k-h+1)

Answer: d
Clarification: The competitive analysis of a FIFO algorithm is mathematically found to be k/(k-h+1) where k and h are some constants used in page replacement and always, h<=k.

12. Under which of the following scenarios is page replacement algorithm required?
a) When total memory exceeds physical memory
b) To determine the number of frames for each process
c) When paging and segmentation are to be used
d) Execution of a process, not in memory

Answer: a
Clarification: An appropriate page replacement algorithm is required when the total memory requirements exceed the physical memory.

13. Consider a reference string:
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 3. Using FIFO algorithm, determine the number of page faults.
a) 12
b) 16
c) 14
d) 15

Answer: d
Clarification: For the given reference string of frame size 3, the number of page faults is calculated to be 15. It is explained in the diagram.
first-in-first-out-algorithm-fifo-questions-answers-q13

14. Consider a reference string:
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 4. Using FIFO algorithm, determine the number of page faults.
a) 12
b) 16
c) 10
d) 14
View Answer

Answer: c
Clarification: For the given reference string of frame size 4, the number of page faults is calculated to be 10. It is explained in the diagram.
first-in-first-out-algorithm-fifo-questions-answers-q14

15. _________ states that, on a page fault, the frame that has been in memory the longest is replaced.
a) Belady’s anomaly
b) Second chance algorithm
c) Partial second chance algorithm
d) LRU replacement algorithm

Answer: a
Clarification: Belady’s anomaly states that, on a page fault, the frame that has been in memory the longest is replaced. It occurs in FIFO algorithm.

and Answers.

250+ TOP MCQs on Fibonacci Search and Answers

Data Structure Multiple Choice Questions on “Fibonacci Search”.

1. Which algorithmic technique does Fibonacci search use?
a) Brute force
b) Divide and Conquer
c) Greedy Technique
d) Backtracking

Answer: b
Clarification: With every iteration, we divide the given array into two sub arrays(not necessarily equal).

2. Choose the recursive formula for the Fibonacci series.(n>=1)
a) F(n) = F(n+1) + F(n+2)
b) F(n) = F(n) + F(n+1)
c) F(n) = F(n-1) + F(n-2)
d) F(n) = F(n-1) – F(n-2)

Answer: c
Clarification: None.

3. Write a function for the Fibonacci search method.
a)

public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            while(fibCurrent < N)
            {
                int tmp = fibCurrent + fibPrev;
                fibPrev = fibCurrent;
                fibCurrent = tmp;
                N = N - (fibCurrent - fibPrev);
            }
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) high = mid - 1;
            else if (key > a[mid]) low = mid + 1;
            else return mid;
        }
        return -1;
}

b)

public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            int tmp = fibCurrent + fibPrev;
            fibPrev = fibCurrent;
            fibCurrent = tmp;
            N = N - (fibCurrent - fibPrev);
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) high = mid - 1;
            else if (key > a[mid]) low = mid + 1;
            else return mid;
        }
        return -1;
}

c)

public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            while(fibCurrent < N)
            {
                int tmp = fibCurrent + fibPrev;
                fibPrev = fibCurrent;
                fibCurrent = tmp;
                N = N - (fibCurrent - fibPrev);
            }
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) low = mid + 1;
            else if (key > a[mid]) high = mid - 1;
            else return mid;
        }
}

d)

public static int fibSearch(final int key, final int[] a) 
{
        int low = 0;
        int high = a.length - 1;
        int fibCurrent = 1;
        int fibPrev = 1;
        int N = a.length;
        while (low <= high) 
        {
            while(fibCurrent < N)
            {
                int tmp = fibCurrent + fibPrev;
                fibPrev = fibCurrent;
                fibCurrent = tmp;
                N = N - (fibCurrent - fibPrev);
            }
            final int mid = low + (high - low) - (fibCurrent + fibPrev);
            if      (key < a[mid]) low = mid - 1;
            else if (key > a[mid]) high = mid - 1;
            else return mid;
        }
}

Answer: a
Clarification: Here instead of choosing middle of the array as a point of array division, we use Fibonacci numbers, the division index are strictly between two Fibonacci numbers.

 
 

4. What is the time complexity of Fibonacci Search?
a) O(logn)
b) O(n)
c) O(n2)
d) O(nlogn)

Answer: a
Clarification: Since it divides the array into two parts, although not equal, its time complexity is O(logn), it is better than binary search in case of large arrays.

5. Which of the following is not an advantage of Fibonacci Search?
a) When the element being searched for has a non uniform access storage
b) Can be used in magnetic tapes
c) Can be used for large arrays which do not fit in the CPU cache or in the RAM
d) It can be applied efficiently on unsorted arrays
Answer: d
Clarification: When the speed of access depends on the location previously accessed, Fibonacci search is better compared to binary search as it performs well on those locations which have lower dispersion. Fibonacci search won’t work on unsorted arrays. The input should be a sorted array or array should be sorted before Fibonacci search.

6. What is the length of the step in jump search?
a) n
b) n/2
c) sqrt(n)
d) 1

Answer: c
Clarification: If the step size is 1, it becomes a linear search, if it is n, we reach the end of the list in just on step, if it is n/2, it becomes similar to binary search, therefore the most efficient step size is found to be sqrt(n).

7. Select the code snippet for Jump Search.
a)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step > size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step >= size) 
                {
			return -1;
		}
	}
	while (arr[prev] < key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}

b)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step < size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step >= size) 
                {
			return -1;
		}
	}
	while (arr[prev] < key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}

c)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step > size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step >= size) 
                {
			return -1;
		}
	}
	while (arr[prev] > key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}

d)

public int jumpSearch(int arr[], int key)
{
	int size = arr.length;
	int step = floor(sqrt(size));
	int prev = 0;
	while (arr[(step > size ? step : size)] < key) 
        {
		prev = step;
		step += floor(sqrt(size));
		if (step <= size) 
                {
			return -1;
		}
	}
	while (arr[prev] > key) 
        {
		prev++;
		if (prev == (step < size ? step : size)) 
                {
			return -1;
		}
	}
	if (arr[prev] == key) 
        {
		return prev;
	}
	return -1;
}

View Answer

Answer: b
Clarification: After finding the correct block of k elements, a sequential search is performed in this block.

 
 

8. What is the time complexity of Jump Search?
a) O(logn)
b) O(n)
c) O(sqrt(n))
d) O(nlogn)

Answer: c
Clarification: Since the size of the step is sqrt(n), the complexity is also obviously O(sqrt(n)).

complete set of 1000+