Category: Data Structures & Algorithms Objective Questions

250+ TOP MCQs on Search an Element in a Linked List using Recursion and Answers

Data Structure Questions and Answers for Entrance exams on “Search an Element in a Linked List using Recursion”.

1. Which of the following methods can be used to search an element in a linked list?
a) Iterative linear search
b) Iterative binary search
c) Recursive binary search
d) Normal binary search

Answer: a
Clarification: Iterative linear search can be used to search an element in a linked list. Binary search can be used only when the list is sorted.

2. Consider the following code snippet to search an element in a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
              return 1;
           _________;
      }
      return 0;
}

Which of the following lines should be inserted to complete the above code?
a) temp = next
b) temp->next = temp
c) temp = temp->next
d) return 0

Answer: c
Clarification: The line “temp = temp->next” should be inserted to complete the above code.

3. What does the following code do?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
              return 1;
           temp = temp->next;
      }
      return 0;
}
int main()
{
      int arr[5] = {1,2,3,4,5};
      int n = 5,i;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      struct Node *temp;
      temp = head;
      for(i=0; i<n; i++)
      {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
      }
      int ans = linear_search(60);
      if(ans == 1)
      printf("Found");
      else
      printf("Not found");
      return 0;
}

a) Finds the index of the first occurrence of a number in a linked list
b) Finds the index of the last occurrence of a number in a linked list
c) Checks if a number is present in a linked list
d) Checks whether the given list is sorted or not
View Answer

Answer: c
Clarification: The above code checks if a number is present in a linked list.

4. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
             return 1;
           temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[5] = {1,2,3,4,5};
     int n = 5,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(-1);
     if(ans == 1)
     printf("Found");
     else
     printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error
View Answer

Answer: b
Clarification: Since the number -1 is not present in the linked list, the program prints not found.

5. What is the time complexity of the following implementation of linear search on a linked list?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp != 0)
      {
           if(temp->val == value)
             return 1;
           temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[5] = {1,2,3,4,5};
     int n = 5,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(-1);
     if(ans == 1)
     printf("Found");
     else
     printf("Not found");
     return 0;
}

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
View Answer

Answer: b
Clarification: The time complexity of the above implementation of linear search on a linked list is O(n).

6. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(int value)
{
      struct Node *temp = head->next;
      while(temp -> next != 0)
      {
            if(temp->val == value)
            return 1;
            temp = temp->next;
      }
      return 0;
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(60);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error

Answer: b
Clarification: The condition in the while loop “temp->next == 0”, checks if the current element is the last element. If the current element is the last element, the value of the current element is not compared with the value to be searched. So, even though the number 6 is present in the linked list, it will print not found.

7. Can binary search be applied on a sorted linked list in O(Logn) time?
a) No
b) Yes

Answer: a
Clarification: Since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in O(Logn) time.

8. What will be time complexity when binary search is applied on a linked list?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b
Clarification: The time complexity will be O(n) when binary search is applied on a linked list.

9. Consider the following recursive implementation of linear search on a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return _________;
}

Which of the following lines should be inserted to complete the above code?
a) 1
b) 0
c) linear_search(temp, value)
d) linear_search(temp->next, value)
Answer: d
Clarification: The line “linear_search(temp->next, value)”, should be inserted to complete the above code.

10. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
     return 0;
}

a) Found
b) Not found
c) Compile time error
d) Runtime error

Answer: a
Clarification: Since the element 6 is present in the linked list, the program prints “Found”.

11. How many times is the function linear_search() called when the following code is executed?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
    return 0;
}

a) 5
b) 6
c) 7
d) 8

Answer: b
Clarification: The function linear_search() is called 6 times when the above code is executed.

12. What is the time complexity of the following recursive implementation of linear search?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int linear_search(struct Node *temp,int value)
{
      if(temp == 0)
         return 0;
      if(temp->val == value)
         return 1;
      return linear_search(temp->next, value);
}
int main()
{
     int arr[6] = {1,2,3,4,5,6};
     int n = 6,i;
     head = (struct Node*)malloc(sizeof(struct Node));
     head->next = 0;
     struct Node *temp;
     temp = head;
     for(i=0; i<n; i++)
     {
           struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next = newNode;
           temp = temp->next;
     }
     int ans = linear_search(head->next,6);
     if(ans == 1)
       printf("Found");
     else
       printf("Not found");
    return 0;
}

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

Answer: b
Clarification: The time complexity of the above recursive implementation of linear search is O(n).

250+ TOP MCQs on Longest Increasing Subsequence and Answers

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

1. The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it’s length is maximum. This problem can be solved using __________
a) Recursion
b) Dynamic programming
c) Brute force
d) Recursion, Dynamic programming, Brute force

Answer: d
Clarification: The longest increasing subsequence problem can be solved using all of the mentioned methods.

2. Find the longest increasing subsequence for the given sequence:
{10, -10, 12, 9, 10, 15, 13, 14}
a) {10, 12, 15}
b) {10, 12, 13, 14}
c) {-10, 12, 13, 14}
d) {-10, 9, 10, 13, 14}

Answer: d
Clarification: The longest increasing subsequence is {-10, 9, 10, 13, 14}.

3. Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a) 5
b) 4
c) 3
d) 6
View Answer

Answer: d
Clarification: The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it’s length is 6.

4. For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
a) True
b) False

Answer: b
Clarification: For a given sequence, it is possible that there is more than one subsequence with the longest length.
Consider, the following sequence: {10,11,12,1,2,3}:
There are two longest increasing subsequences: {1,2,3} and {10,11,12}.

5. The number of increasing subsequences with the longest length for the given sequence are:
{10, 9, 8, 7, 6, 5}
a) 3
b) 4
c) 5
d) 6

Answer: d
Clarification: Each array element individually forms a longest increasing subsequence and so, the length of the longest increasing subsequence is 1. So, the number of increasing subsequences with the longest length is 6.

6. In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?
a) O(n)
b) O(n2)
c) O(n!)
d) O(2n)

Answer: d
Clarification: The time required to find all the subsequences of a given sequence is 2n, where ‘n’ is the number of elements in the sequence. So, the time complexity is O(2n).

7. Complete the following dynamic programming implementation of the longest increasing subsequence problem:

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     ___________;  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

a) tmp_max = LIS[j]
b) LIS[i] = LIS[j]
c) LIS[j] = tmp_max
d) tmp_max = LIS[i]

Answer: a
Clarification: tmp_max is used to store the maximum length of an increasing subsequence for any ‘j’ such that: arr[j] < arr[i] and 0 < j < i.
So, tmp_max = LIS[j] completes the code.

8. What is the time complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

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

Answer: c
Clarification: The time complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n2).

9. What is the space complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

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

Answer: b
Clarification: The above dynamic programming implementation uses space equal to the length of the sequence. So, the space complexity of the above dynamic programming implementation used to find the length of the longest increasing subsequence is O(n).

10. What is the output of the following program?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      {
	    tmp_max = 0;
	    for(j = 0; j < i; j++)
	    {
	        if(arr[j] < arr[i])
	        {
		     if(LIS[j] > tmp_max)
		       tmp_max = LIS[j];
	        }
            }
	    LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	  if(LIS[i] > max)
	      max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

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

11. What is the value stored in LIS[5] after the following program is executed?

#include
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      {
	   tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		     if(LIS[j] > tmp_max)
		     tmp_max = LIS[j];
	        }
	   }
	   LIS[i] = tmp_max + 1;
       }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	 if(LIS[i] > max)
	     max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

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

Answer: c
Clarification: The value stored in LIS[5] after the program is executed is 4.

contest

250+ TOP MCQs on Monoalphabetic Cipher and Answers

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Monoalphabetic Cipher”.

1. What is the meaning of cipher in cryptography?
a) an algorithm that performs encryption
b) an algorithm that generates a secret code
c) an algorithm that performs encryption or decryption
d) a secret code

Answer: c
Clarification: Cipher is an algorithm for performing encryption or decryption. In cryptography, a set of defined steps are followed to generate ciphers.

2. Which of the following is a type of traditional cipher?
a) transportation cipher
b) transposition cipher
c) transforming cipher
d) vigenere cipher

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

3. 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.

4. Which of the following is a type of substitution cipher?
a) Mono alphabetic cipher
b) transposition cipher
c) transportation cipher
d) transforming cipher
Answer: a
Clarification: In substitution cipher the plain text is replaced by cipher text according to a fixed rule. There are two types of substitution cipher – Mono alphabetic and Poly alphabetic cipher.

5. Which of the following is not a type of mono alphabetic cipher?
a) additive cipher
b) multiplicative cipher
c) afffine cipher
d) hill cipher

Answer: d
Clarification: In mono alphabetic cipher each symbol of plain text is replaced by a particular respective symbol in the cipher text. There are three types of mono alphabetic ciphers- additive, multiplicative and affine.

6. Which of the following is not a type of poly alphabetic cipher?
a) Auto key cipher
b) Hill cipher
c) Playfair 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.

7. What will be the ciphered text for the input string “” with key string as “code” to the program of keyword cipher?
a) SCMBNUMERY
b) SSCMBNUMERY
c) NIFO
d) NILO
Answer: a
Clarification: Keyword cipher is type of mono alphabetic cipher. In this algorithm the letters {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z} by
{C,O,D,E,A,B,F,G,H,I,J,K,L,M,N,P,Q,R,S,T,U,V,W,X,Y,Z} respectively.

8. Which of the following is a type of transposition cipher?
a) Rail Fence cipher
b) Hill cipher
c) Rotor cipher
d) One time pad

Answer: a
Clarification: In transposition cipher the letters of the given data are shuffled in a particular order, fixed by a given rule. There are two types of transposition cipher – Rail fence cipher and Columnar transposition cipher.

9. What will be output for the given code?

#include 
using namespace std; 
string encrypter(string keyword) 
{ 
	string encoded = ""; 	
	bool arr[26] = {0}; 
	for (int i=0; i<keyword.size(); i++) 
	{ 
		if(keyword[i] >= 'A' && keyword[i] <= 'Z') 
		{ 		
			if (arr[keyword[i]-65] == 0) 
			{ 
				encoded += keyword[i]; 
				arr[keyword[i]-65] = 1; 
			} 
		} 
		else if (keyword[i] >= 'a' && keyword[i] <= 'z') 
		{ 
			if (arr[keyword[i]-97] == 0) 
			{ 
				encoded += keyword[i] - 32; 
				alpha[keyword[i]-97] = 1; 
			} 
		} 
	} 
	for (int i=0; i<26; i++) 
	{ 
		if(arr[i] == 0) 
		{ 
			arr[i]=1; 
			encoded += char(i + 65); 
		} 
	} 
	return encoded; 
} 
string ciphertxt(string msg, string encoded) 
{ 
	string cipher=""; 
	for (int i=0; i<msg.size(); i++) 
	{ 
		if (msg[i] >='a' && msg[i] <='z') 
		{ 
			int pos = msg[i] - 97; 
			cipher += encoded[pos]; 
		} 
		else if (msg[i] >='A' && msg[i] <='Z') 
		{ 
			int pos = msg[i] - 65; 
			cipher += encoded[pos]; 
		} 
		else
		{ 
			cipher += msg[i]; 
		} 
	} 
	return cipher; 
} 
int main() 
{ 
	string keyword; 
	keyword = "cipher"; 	
	string encoded = encrypter(keyword); 
	string message = "hello"; 
	cout  << ciphertxt(message,encoded) << endl; 
	return 0; 
}

a) bejjm
b) LFPDAR
c) BEJJM
d) lfpdar

Answer: c
Clarification: The given code is the implementation of keyword cipher. It is an example of mono alphabetic cipher. The given string is always converted into an uppercase ciphered text.

10. What will be output for the given code taking input string as “”?

package com..setandstring;
import java.util.Scanner;
public class MonoalphabeticCipher
{
      public static char p[]  = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
                                  'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                                  'u', 'v', 'w', 'x', 'y', 'z' };
      public static char ch[] = { 'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P',
                                  'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'Z',
                                  'X', 'C', 'V', 'B', 'N', 'M' };
      public static String doEncryption(String s)
      { 
           char c[] = new char[(s.length())];
           for (int i = 0; i < s.length(); i++)
           {
                for (int j = 0; j < 26; j++)
                { 
                     if (p[j] == s.charAt(i))
                     {
                         c[i] = ch[j];
                          break;
                     }
                }
            }  return (new String(c));
        }   
        public static void main(String args[])
        {
             Scanner sc = new Scanner(System.in);
             System.out.println("Enter the message: ");
             String en = doEncryption(sc.next().toLowerCase());
             System.out.println("Encrypted message: " + en);
             sc.close();
         }
}

a) Encrypted message: LQFYGXFRKN
b) Encrypted message: NKRFXGYFQL
c) Encrypted message: lqfygxfrkn
d) Encrypted message: nkrfxgyfql

Answer: a
Clarification: The given code is an example of mono-alphabetic cipher. The code replaces the letters of the input string by corresponding keyboard letters.

11. In which of the following cipher the plain text and the ciphered text does not have same number of letters?
a) keyword cipher
b) vigenere cipher
c) transposition cipher
d) additive cipher
View Answer

Answer: b
Clarification: In transposition cipher and mono alphabetic cipher the number of letters in the plain text and ciphered text remain same. But in poly alphabetic cipher the number of letters change. So here as vigenere cipher is the only poly alphabetic cipher so it will be the answer.

and Answers.

250+ TOP MCQs on Bifid Cipher and Answers

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

1. What is the period in bifid cipher?
a) length of blocks in which the plain text is divided before encryption
b) number of letters after which the key is repeated
c) number of blocks into which the plain text is divided before encryption
d) number of keys used for encryption
Answer: a
Clarification: Polybius square is similar to substitution cipher. It is also known by the name of Polybius checkboard.

2. Which of the following cipher uses polybius square?
a) bifid cipher
b) beaufort cipher
c) trithemius cipher
d) gronsfeld cipher

Answer: a
Clarification: Bifid cipher uses polybius square for encrypting the plain text. Bifid cipher combines polybius square cipher with transposition.

3. Bifid cipher combines transposition with which of the following cipher?
a) Polybius square cipher
b) Playfair cipher
c) gronsfeld cipher
d) trifid cipher

Answer: a
Clarification: Bifid cipher combines polybius square cipher with transposition. It uses fractionation to obtain diffusion.

4. What will be the key square in bifid cipher for the key “”?
a)

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

b)

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

c)

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

d)

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

Answer: a
Clarification: For forming the key square from the given key we first add the letters of the key in the square by omitting the repeated letters and then we add the remaining letters of the English alphabet. Usually, I and J are combined together.

 
 

5. Trifid cipher encrypts the plain text by using bifid cipher twice.
a) true
b) false

Answer: b
Clarification: Trifid cipher is a variation of bifid cipher. The only difference between them is that trifid cipher uses a 3×3 key square instead of 5×5 square.

6. Bifid square combines autokey square with transposition.
a) true
b) false

Answer: b
Clarification: Bifid square combines polybius square with transposition. So the given statement is false.

7. What will be the ciphered text corresponding to “” if bifid cipher is used for encryption with key as “KEY” with period as 5?
a) SBPISZTKZH
b) PLNSOWGKQM
c) SELFQEXBHM
d) YFSGWNFBW

Answer: b
Clarification: For encrypting the plain text using bifid cipher we first form the polybius square with the help of given key. After this, the plain text is divided into blocks of length 5 and corresponding coordinates are noted. So the corresponding cipher text would be “PLNSOWGKQM”.

8. What will be the ciphered text corresponding to “ALGORITHM” if bifid cipher is used for encryption with key as “KEY” with a period as 5?
a) SBPISZTKZH
b) PLNSOWGKQM
c) SELFQEXBHM
d) YFSGWNFBW

Answer: d
Clarification: For encrypting the plain text using bifid cipher we first form the polybius square with the help of given key. After this, the plain text is divided into blocks of length 5 and corresponding coordinates are noted. So the corresponding cipher text would be “YFSGWNFBW”.

9. What will be the plain text corresponding to cipher text “XKS” if the bifid cipher is used with key as “KEY” and period as 5?
a) IND
b) USA
c) RSA
d) AUS

Answer: b
Clarification: The decryption in bifid cipher begins identically to encryption. Then we find the corresponding coordinates and then we get the plain text. So the plain text is “USA”.

10. What will be the plain text corresponding to ciphered text “BKC” if the bifid cipher is used for encryption with key as “KEY” and period 5?
a) MSD
b) SRT
c) KVK
d) VVS
View Answer

Answer: c
Clarification: The decryption in bifid cipher begins identically to encryption. Then we find the corresponding coordinates and then we get the plain text. So the plain text is “KVK”.

250+ TOP MCQs on Insertion Sort MCQs and Answers Pdf Download

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

1. Which of the following is correct with regard to insertion sort?
a) insertion sort is stable and it sorts In-place
b) insertion sort is unstable and it sorts In-place
c) insertion sort is stable and it does not sort In-place
d) insertion sort is unstable and it does not sort In-place

Answer: a
Clarification: During insertion sort, the relative order of elements is not changed. Therefore, it is a stable sorting algorithm. And insertion sort requires only O(1) of additional memory space. Therefore, it sorts In-place.

2. Which of the following sorting algorithm is best suited if the elements are already sorted?
a) Heap Sort
b) Quick Sort
c) Insertion Sort
d) Merge Sort

Answer: c
Clarification: The best case running time of the insertion sort is O(n). The best case occurs when the input array is already sorted. As the elements are already sorted, only one comparison is made on each pass, so that the time required is O(n).

3. The worst case time complexity of insertion sort is O(n2). What will be the worst case time complexity of insertion sort if the correct position for inserting element is calculated using binary search?
a) O(nlogn)
b) O(n2)
c) O(n)
d) O(logn)

Answer: b
Clarification: The use of binary search reduces the time of finding the correct position from O(n) to O(logn). But the worst case of insertion sort remains O(n2) because of the series of swapping operations required for each insertion.

4. Insertion sort is an example of an incremental algorithm.
a) True
b) False

Answer: a
Clarification: In the incremental algorithms, the complicated structure on n items is built by first building it on n − 1 items. And then we make the necessary changes to fix things in adding the last item. Insertion sort builds the sorted sequence one element at a time. Therefore, it is an example of an incremental algorithm.

5. Consider the code given below, which runs insertion sort:

void insertionSort(int arr[], int array_size)
{
  int i, j, value;
  for (i = 1; i < array_size; i++)
  {
          value = arr[i];
          j = i;
          while (________ )
          {
                   arr[j] = arr[j − 1];
                   j = j − 1;
          }
          arr[j] = value;
  }
}

Which condition will correctly implement the while loop?
a) (j > 0) || (arr[j − 1] > value)
b) (j > 0) && (arr[j − 1] > value)
c) (j > 0) && (arr[j + 1] > value)
d) (j > 0) && (arr[j + 1] < value)

Answer: b
Clarification: In insertion sort, the element is A[j] is inserted into the correct position in the sorted sequence A[1… j – 1]. So, condition given in (j > 0) && (arr[j − 1] > value) will implement while loop correctly.

6. Which of the following is good for sorting arrays having less than 100 elements?
a) Quick Sort
b) Selection Sort
c) Merge Sort
d) Insertion Sort
View Answer

Answer: d
Clarification: The insertion sort is good for sorting small arrays. It sorts smaller arrays faster than any other sorting algorithm.

7. Consider an array of length 5, arr[5] = {9,7,4,2,1}. What are the steps of insertions done while running insertion sort on the array?
a) 7 9 4 2 1    4 7 9 2 1    2 4 7 9 1    1 2 4 7 9
b) 9 7 4 1 2    9 7 1 2 4    9 1 2 4 7    1 2 4 7 9
c) 7 4 2 1 9    4 2 1 9 7    2 1 9 7 4    1 9 7 4 2
d) 7 9 4 2 1    2 4 7 9 1    4 7 9 2 1    1 2 4 7 9
View Answer

Answer: a
Clarification: The steps performed while running insertion sort on given array are:
Initial : 9 7 4 2 1 key = 7
7 9 4 2 1 key = 4
4 7 9 2 1 key = 2
2 4 7 9 1 key = 1
1 2 4 7 9

In each step, the key is the element that is compared with the elements present at the left side to it.

8. Statement 1: In insertion sort, after m passes through the array, the first m elements are in sorted order.
Statement 2: And these elements are the m smallest elements in the array.
a) Both the statements are true
b) Statement 1 is true but statement 2 is false
c) Statement 1 is false but statement 2 is true
d) Both the statements are false

Answer: b
Clarification: In insertion sort, after m passes through the array, the first m elements are in sorted order but they are whatever the first m elements were in the unsorted array.

9. In insertion sort, the average number of comparisons required to place the 7th element into its correct position is ____
a) 9
b) 4
c) 7
d) 14

Answer: b
Clarification: On average (k + 1) / 2 comparisons are required to place the kth element into its correct position. Therefore, average number of comparisons required for 7th element = (7 + 1)/2 = 4.

10. Which of the following is not an exchange sort?
a) Bubble Sort
b) Quick Sort
c) Partition-exchange Sort
d) Insertion Sort

Answer: d
Clarification: In Exchange sorts, we compare each element of an array and swap those elements that are not in their proper position. Bubble Sort and Quick Sort are exchange sorts. Quick Sort is also called as Partition-exchange Sort. Insertion sort is not an exchange sort.

250+ TOP MCQs on Timsort and Answers

Data Structures & Algorithms Multiple Choice Questions on “Timsort”.

1. Which of the following is Python’s standard sorting algorithm?
a) quick sort
b) introsort
c) merge sort
d) tim sort

Answer: d
Clarification: Tim sort has been python’s standard sorting algorithm since its version 2.3. It is an example of hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.

2. Which of the following sorting algorithm is a constituent of tim sort?
a) selection sort
b) quick sort
c) merge sort
d) heap sort
Answer: c
Clarification: Tim sort is a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine. It is derived from insertion sort and merge sort.

3. Tim sort begins sorting the given array by using which of the following sorting algorithm?
a) selection sort
b) quick sort
c) insertion sort
d) merge sort

Answer: c
Clarification: Tim sort begins sorting any given array by using insertion sort for each run. The array is divided into smaller parts for this purpose, each part having a size equal to value of run. Then these small parts called runs are merged in order to obtain sorted array.

4. Which of the following sorting algorithm is stable?
a) Tim sort
b) Introsort
c) Quick sort
d) Heap sort

Answer: a
Clarification: Out of the given options Tim sort is the only algorithm which is stable. As both constituents of Tim sort (I.e insertion sort and merge sort) are stable so Tim sort also becomes stable.

5. Which of the following sorting algorithm is not in-place?
a) insertion sort
b) tim sort
c) quick sort
d) intro sort

Answer: b
Clarification: Tim sort is not an in-place sorting algorithm as it requires auxiliary space. It is because it requires to merge sorted runs which requires a third array of the size equal to the sum of the two runs.

6. Tim sort is a comparison based sort.
a) true
b) false

Answer: a
Clarification: Merge sort and insertion sort are comparison based sorts. Thus overall Tim sort also becomes a comparison based sort.

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

Answer: a
Clarification: Best case time complexity of Tim sort occurs when the input array is already sorted. In such a case only one run will be required.

8. What is the worst case time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)

Answer: b
Clarification: Worst case time complexity of Tim sort is O(n log n). It is because the worst complexity of merge sort is O(n log n) and insertion sort is only applied for small arrays.

9. What is the average time complexity of Tim sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)

Answer: b
Clarification: Average time complexity of Tim sort remains to be O(n log n). It is the same as the average case complexity of merge sort.

10. What is the auxiliary space requirement of Tim sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: a
Clarification: Tim sort is a hybrid of merge sort and insertion sort. It requires to merge sorted runs which require a third array of the size equal to the sum of the two runs. So in worst case the auxiliary space requirement will be O(n).

11. Which of the following algorithm is implemented internally in java when we use function arrays.sort()?
a) intro sort
b) quick sort
c) tim sort
d) merge sort

Answer: c
Clarification: Java makes use of Tim sort internally for implementing arrays.sort(). It is mainly due to the fastness of this algorithm in comparison to other comparison based sorts.

12. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for Tim sort implementation?
a) Because insertion sort is faster and adaptive
b) Because insertion sort requires less space
c) Because insertion sort is easy to implement
d) Because insertion sort is easy to understand

Answer: a
Clarification: When small arrays need to be sorted then insertion sort proves to be the best choice. Also, it is adaptive so it performs better than others when the given array is fully/partially sorted.

13. In which case will tim sort will work as an insertion sort?
a) when no. of elements are less than 64
b) when no. of elements are greater than 64
c) when no. of elements are less than size of run
d) when no. of elements are less than 32
Answer: c
Clarification: Tim sort uses a hybrid of insertion and merge sort. It reduces to insertion sort when the size of array is less than the size of run as insertion sort is efficient in sorting small arrays.

14. What is the usual size of a run in tim sort?
a) 32
b) less than 32
c) 32-64 depending on size of the array
d) 64

Answer: c
Clarification: Usually the size of the run is chosen somewhere between 32 and 64. The size of run is preferably chosen in powers of 2 in order to maintain balance while merging the sorted runs.

15. What will be the output of the given Java code?

import java.util.Arrays; 
public class SortExample 
{ 
	public static void main(String[] args) 
	{ 
		// Our arr contains 8 elements 
		int[] arr = {10,7,9,5,8,4}; 
		Arrays.sort(arr); 
		System.out.printf(Arrays.toString(arr)); 
	} 
}

a) [4,5,7,8,9,10]
b) [10,9,8,7,5,4]
c) 4,5,7,8,9,10
d) error

Answer: a
Clarification: The given program sorts the input in ascending order by using the function Arrays.sort(). It uses Tim sort internally.

16. What will be the output of the given Java code?

import java.util.Arrays; 
public class SortExample 
{ 
	public static void main(String[] args) 
	{ 
		int[] arr = {10,7,9,5,8,4}; 
		Arrays.sort(arr, 1, 3); 
		System.out.printf(Arrays.toString(arr)); 
	} 
}

a) [4,5,7,8,9,10]
b) [10,9,8,7,5,4]
c) [10,5,7,8,9,4]
d) [10,7,9,5,8,4]

Answer: d
Clarification: The given program sorts only a portion of the input array. It is done by passing two extra arguments to the function Arrays.sort(). It sorts the elements between index 1 and 2.

& Algorithms.

and Answers.