Category: Data Structures & Algorithms Objective Questions

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

1. Which of the following is an advantage of recursive bubble sort over its iterative version?
a) it has better time complexity
b) it has better space complexity
c) it is easy to implement
d) it has no significant advantage

Answer: d
Clarification: Recursive bubble sort has no significant advantage over iterative bubble sort. It is just a different way to implement the same.

2. Bubble sort is also known as ___________
a) stupid sort
b) ship sort
c) sinking sort
d) shell sort

Answer: c
Clarification: Bubble sort is also referred to as sinking sort. It continuously compares the value of adjacent elements as it traverses through an array and swaps the elements which are out of order.

3. What will be the recurrence relation of the code of recursive bubble 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: The recurrence relation of the code of recursive bubble sort is T(n) = T(n-1) + n. It can be solved by the method of substitution and is found to be equal to n².

4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Bubble sort
d) Heap sort
Answer: c
Clarification: Out of the given options bubble sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.

5. Which of the following is a variation of bubble sort?
a) selection sort
b) odd even sort
c) cocktail sort
d) stupid sort

Answer: b
Clarification: Odd even sort is a variation of bubble sort. But unlike bubble sort, odd even sort traverses the array in two phases- odd phase and even phase.

6. Recursive bubble sort is a comparison based sort.
a) true
b) false
View Answer

Answer: a
Clarification: In bubble 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 bubble sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: The overall recurrence relation of recursive bubble sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n²).

8. What is the best case time complexity of recursive bubble sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
Answer: a
Clarification: The best case time complexity of recursive bubble sort is O(n). It occurs in the case when the input is already/almost sorted.

9. What is the worst case time complexity of recursive bubble sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
Answer: c
Clarification: The overall recurrence relation of recursive bubble sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n²).

10. What are the number of swaps required to sort the array arr={1, 2, 4, 3, 7, 5, 6} using recursive bubble sort?
a) 0
b) 1
c) 2
d) 3
Answer: d
Clarification: The first swap takes place between 4 and 3 then the second swap takes place between 7 and 5 and then finally 6 and 7 are swapped which sorts our array.

11. What will be the base case for the code of recursive bubble sort?
a)

b)

c)

d)

View Answer

Answer: c
Clarification: The most appropriate condition for the base case of recursive bubble sort is when n equal 1 then return. It is because we know that an array with only 1 element is always sorted.

12. What is the auxiliary space complexity of recursive bubble sort?
a) O(n)
b) O(1)
c) O(n log n)
d) O(n²)
Answer: b
Clarification: The auxiliary space required by recursive bubble sort is O(1). So it qualifies as an in-place sorting algorithm.

13. Bubble sort is an adaptive sorting algorithm.
a) true
b) false

Answer: a
Clarification: Bubble sort is an adaptive algorithm. It is because the time complexity of the algorithm improves when the input array is almost sorted.

14. Which of the following sorting algorithm is in place?
a) recursive bubble sort
b) merge sort
c) radix sort
d) counting sort

Answer: a
Clarification: Out of the given options recursive bubble sort is the only algorithm which is in place. It is because the auxiliary space required by recursive bubble sort is O(1).

15. Choose the correct function for recursive bubble sort?
a)

void rec_bubbleSort(int arr[], int n) 
{ 	
	if (n == 1) 
		return;	
	for (int i=0; i<n-1; i++) 
		if (arr[i] > arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
	rec_bubbleSort(arr, n-1); 
}

b)

void rec_bubbleSort(int arr[], int n) 
{ 	
	if (n == 2) 
		return; 	
	for (int i=0; i<n-1; i++) 
		if (arr[i] > arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
	rec_bubbleSort(arr, n-1); 
}

c)

void rec_bubbleSort(int arr[], int n) 
{ 
	if (n == 1) 
		return; 	
	for (int i=0; i<n-1; i++) 
		if (arr[i] < arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
 
	rec_bubbleSort(arr, n-1); 
}

d)

void rec_bubbleSort(int arr[], int n) 
{ 
	if (n == 2) 
		return; 	
	for (int i=0; i<n-1; i++) 
		if (arr[i] < arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
 
	rec_bubbleSort(arr, n-1); 
}

Answer: a
Clarification: The base case of the recursive bubble sort should be 1 when equal 1 then return. It is because we know that an array with only 1 element is always sorted. Also, we need to swap the adjacent elements which are out of order.

Data Structures & Algorithms Multiple Choice Questions on “Cross Product”.

1. Cross product is a mathematical operation performed between ________________
a) 2 scalar numbers
b) a scalar and a vector
c) 2 vectors
d) any 2 numbers

Answer: c
Clarification: Cross product is a mathematical operation that is performed on 2 vectors in a 3D plane. It has many applications in computer programming and physics.

2. Cross product is also known as?
a) scalar product
b) vector product
c) dot product
d) multiplication

Answer: b
Clarification: Cross product is also known as a vector product. It is a mathematical operation that is performed on 2 vectors in 3D plane.

3. What is the magnitude of resultant of cross product of two parallel vectors a and b?
a) |a|.|b|
b) |a|.|b| cos(180)
c) |a|.|b| sin(180)
d) 1

Answer: c
Clarification: The resultant of cross product of 2 parallel vectors is always 0 as the angle between them is 0 or 180 degrees. So the answer is |a|.|b| sin(180).

4. What is the general formula for finding the magnitude of the cross product of two vectors a and b with angle θ between them?
a) |a|.|b|
b) |a|.|b| cos(θ)
c) |a|.|b| sin(θ)
d) |a|.|b| tan(θ)

Answer: c
Clarification: The general formula for finding the magnitude of cross product of two vectors is |a|.|b| sin(θ). Its direction is perpendicular to the plane containing a and b.

5. The concept of cross product is applied in the field of computer graphics.
a) true
b) false

Answer: a
Clarification: The concept of cross product find its application in the field of computer graphics. It can be used to find the winding of polygon about a point.

6. Which of the following equals the a x b ( a and b are two vectors)?
a) – (a x b)
b) a.b
c) b x a
d) – (b x a)

Answer: d
Clarification: The vector product a x b is equal to – (b x a). The minus sign shows that these vectors have opposite directions.

7. Cross product of two vectors can be used to find?
a) area of rectangle
b) area of square
c) area of parallelogram
d) perimeter of rectangle

Answer: c
Clarification: Cross product of two vectors can be used to find the area of parallelogram. For this, we need to consider the vectors as the adjacent sides of the parallelogram.

8. The resultant vector from the cross product of two vectors is _____________
a) perpendicular to any one of the two vectors involved in cross product
b) perpendicular to the plane containing both vectors
c) parallel to to any one of the two vectors involved in cross product
d) parallel to the plane containing both vectors

Answer: b
Clarification: The resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. In other words, it should be perpendicular to both the vectors involved in the cross product.

9. What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?
a) i + 2j + k
b) 2i + 3j + k
c) i + j – 5k
d) 2i – j – 5k

Answer: c
Clarification: We can find the cross product of the given vectors by solving the determinant.

10. What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k?
a) i + 2j + k
b) i – j – 5k
c) 0
d) 2i – j – 5k
Answer: c
Clarification: The given vectors are parallel to each other. The cross product of parallel vectors is 0 because sin(0) is 0.

11. Find the output of the following code.

#include  
using namespace std; 
void crossP(int A[], int B[], int cross[]) 
{ 
	cross[0] = A[1] * B[2] - A[2] * B[1]; 
	cross[1] = A[0] * B[2] - A[2] * B[0]; 
	cross[2] = A[0] * B[1] - A[1] * B[0]; 
}
int main() 
{ 
	int A[] = { 1, 2, 4 }; 
	int B[] = { 2, 3, 2 }; 
	int cross[3]; 
	crossP(A, B, cross); 
	for (int i = 0; i < 3; i++) 
		cout << cross[i] << " "; 
	return 0; 
}

a) 1 2 5
b) -1 -5 -3
c) -6 -8 -1
d) -8 -6 -1
Answer: d
Clarification: The given code calculates the cross product of the vectors stored in arrays A and B respectively. So the output will be -8 -6 -1.

12. Which of the following operation will give a vector that is perpendicular to both vectors a and b?
a) a x b
b) a.b
c) b x a
d) both a x b and b x a
Answer: d
Clarification: The resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. So both a x b and b x a will give a vector that is perpendicular to both vectors a and b.

Data Structures & Algorithms Multiple Choice Questions on “Maximum Bipartite Matching”.

1. _____________ is a matching with the largest number of edges.
a) Maximum bipartite matching
b) Non-bipartite matching
c) Stable marriage
d) Simplex

Answer: a
Clarification: Maximum bipartite matching matches two elements with a property that no two edges share a vertex.

2. Maximum matching is also called as maximum cardinality matching.
a) True
b) False

Answer: a
Clarification: Maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges.

3. How many colours are used in a bipartite graph?
a) 1
b) 2
c) 3
d) 4
Answer: b
Clarification: A bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours.

4. What is the simplest method to prove that a graph is bipartite?
a) It has a cycle of an odd length
b) It does not have cycles
c) It does not have a cycle of an odd length
d) Both odd and even cycles are formed

Answer: c
Clarification: It is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length.

5. A matching that matches all the vertices of a graph is called?
a) Perfect matching
b) Cardinality matching
c) Good matching
d) Simplex matching

Answer: a
Clarification: A matching that matches all the vertices of a graph is called perfect matching.

6. What is the length of an augmenting path?
a) Even
b) Odd
c) Depends on graph
d) 1

Answer: b
Clarification: The length of an augmenting path in a bipartite graph is always said to be always odd.

7. In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?
a) Bipartite matching
b) Cardinality matching
c) Augmenting
d) Weight matching

Answer: c
Clarification: A simple path from a free vertex in V to a free vertex in U whose edges alternate between edges not in M and edges in M is called a augmenting path.

8. A matching M is maximal if and only if there exists no augmenting path with respect to M.
a) True
b) False

Answer: a
Clarification: According to the theorem discovered by the French mathematician Claude Berge, it means that the current matching is maximal if there is no augmenting path.

9. Which one of the following is an application for matching?
a) Proposal of marriage
b) Pairing boys and girls for a dance
c) Arranging elements in a set
d) Finding the shortest traversal path
View Answer

Answer: b
Clarification: Pairing boys and girls for a dance is a traditional example for matching. Proposal of marriage is an application of stable marriage problem.

10. Which is the correct technique for finding a maximum matching in a graph?
a) DFS traversal
b) BFS traversal
c) Shortest path traversal
d) Heap order traversal

Answer: b
Clarification: The correct technique for finding a maximum matching in a bipartite graph is by using a Breadth First Search(BFS).

11. The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?
a) Maximum- mass matching
b) Maximum bipartite matching
c) Maximum weight matching
d) Maximum node matching

Answer: c
Clarification: The problem is called as maximum weight matching which is similar to a bipartite matching. It is also called as assignment problem.

12. What is the total number of iterations used in a maximum- matching algorithm?
a) [n/2]
b) [n/3]
c) [n/2]+n
d) [n/2]+1

Answer: d
Clarification: The total number of iterations cannot exceed [n/2]+1 where n=|V|+|U| denoting the number of vertices in the graph.

13. What is the efficiency of algorithm designed by Hopcroft and Karp?
a) O(n+m)
b) O(n(n+m)
c) O(√n(n+m))
d) O(n+2)
Answer: c
Clarification: The efficiency of algorithm designed by Hopcroft and Karp is mathematically found to be O(√n(n+m)).

14. Who was the first person to solve the maximum matching problem?
a) Jack Edmonds
b) Hopcroft
c) Karp
d) Claude Berge
Answer: a
Clarification: Jack Edmonds was the first person to solve the maximum matching problem in 1965.

15. From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?

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

Answer: a
Clarification: One of the solutions of the matching problem is given by a-w,b-v,c-x,d-y,e-z. Hence the answer is 5.

contest

Data Structure Questions and Answers for Campus interviews on “Decimal to Binary Conversion using Recursion”.

1. Which of the following is the binary representation of 100?
a) 1010010
b) 1110000
c) 1100100
d) 1010101

Answer: c
Clarification: 100 = 64 + 32 + 4 = 2⁶ + 2⁵ + 2² = 1100100.

2. Consider the following iterative code used to convert a decimal number to its equivalent binary:

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          _______;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 10;
     dec_to_bin(n);
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) n–
b) n /= 2
c) n /= 10
d) n++

Answer: b
Clarification: The line “n /= 2” should be inserted to complete the above code.

3. What is the output of the following code?

#include
void dec_to_bin(int n)
{
    int arr[31],len = 0,i;
    if(n == 0)
    {
        arr[0] = 0;
        len = 1;
    }
    while(n != 0)
    {
        arr[len++] = n % 2;
        n /= 2;
    }
    for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
    int n = 63;
    dec_to_bin(n);
    return 0;
}

a) 111111
b) 111011
c) 101101
d) 101010

Answer: a
Clarification: The program prints the binary equivalent of 63, which is 111111.

4. What is the output of the following code?

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          n /= 2;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 0;
     dec_to_bin(n);
     return 0;
}

a) 0
b) 1
c) Runtime error
d) Garbage value

Answer: a
Clarification: The program prints the binary equivalent of 0, which is 0.

5. What is the time complexity of the following code used to convert a decimal number to its binary equivalent?

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          n /= 2;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 0;
     dec_to_bin(n);
     return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(logn)

Answer: d
Clarification: The time complexity of the above code used to convert a decimal number to its binary equivalent is O(logn).

6. Consider the following recursive implementation used to convert a decimal number to its binary equivalent:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
          return;
        __________;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = 100,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) arr[len] = n
b) arr[len] = n % 2
c) arr[len++] = n % 2
d) arr[len++] = n

Answer: c
Clarification: The line “arr[len++] = n % 2” should be inserted to complete the above code.

7. Consider the following code:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}

Which of the following lines is the base case for the above code?
a) if(n ==0 && len == 0)
b) if(n == 0)
c) if(n ==0 && len == 0) and if(n == 0)
d) if(n == 1)

Answer: c
Clarification: Both of the above mentioned lines are the base cases for the above code.

8. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = -100,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

a) -1100100
b) 1100100
c) 2’s complement of 1100100
d) Garbage value

Answer: d
Clarification: The program doesn’t handle negative inputs and so produces a garbage value.

9. What is the time complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}

a) O(1)
b) O(n)
c) O(n²)
d) O(logn)

Answer: d
Clarification: The time complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

10. What is the space complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}

a) O(1)
b) O(n)
c) O(n²)
d) O(logn)

Answer: d
Clarification: The space complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

11. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = 111,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

a) 1110111
b) 1001111
c) 1101111
d) 1010111

Answer: c
Clarification: The program prints the binary equivalent of 111, which is 1101111.

12. How many times is the function recursive_dec_to_bin() called when the following code is executed?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
    int n = 111,i;
    recursive_dec_to_bin(n);
    for(i=len-1; i>=0; i--)
    printf("%d",arr[i]);
    return 0;
}

a) 7
b) 8
c) 9
d) 10

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

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

1. Which of the following algorithms is the best approach for solving Huffman codes?
a) exhaustive search
b) greedy algorithm
c) brute force algorithm
d) divide and conquer algorithm

Answer: b
Clarification: Greedy algorithm is the best approach for solving the Huffman codes problem since it greedily searches for an optimal solution.

2. How many printable characters does the ASCII character set consists of?
a) 120
b) 128
c) 100
d) 98
Answer: c
Clarification: Out of 128 characters in an ASCII set, roughly, only 100 characters are printable while the rest are non-printable.

3. Which bit is reserved as a parity bit in an ASCII set?
a) first
b) seventh
c) eighth
d) tenth
Answer: c
Clarification: In an ASCII character set, seven bits are reserved for character representation while the eighth bit is a parity bit.

4. How many bits are needed for standard encoding if the size of the character set is X?
a) log X
b) X+1
c) 2X
d) X²

Answer: a
Clarification: If the size of the character set is X, then [log X] bits are needed for representation in a standard encoding.

5. The code length does not depend on the frequency of occurrence of characters.
a) true
b) false

Answer: b
Clarification: The code length depends on the frequency of occurrence of characters. The more frequent the character occurs, the less is the length of the code.

6. In Huffman coding, data in a tree always occur?
a) roots
b) leaves
c) left sub trees
d) right sub trees

Answer: b
Clarification: In Huffman encoding, data is always stored at the leaves of a tree inorder to compute the codeword effectively.

7. From the following given tree, what is the code word for the character ‘a’?

a) 011
b) 010
c) 100
d) 101

Answer: a
Clarification: By recording the path of the node from root to leaf, the code word for character ‘a’ is found to be 011.

8. From the following given tree, what is the computed codeword for ‘c’?

a) 111
b) 101
c) 110
d) 011

Answer: c
Clarification: By recording the path of the node from root to leaf, assigning left branch as 0 and right branch as 1, the codeword for c is 110.

9. What will be the cost of the code if character c_i is at depth d_i and occurs at frequency f_i?
a) c_if_i
b) ∫c_if_i
c) ∑f_id_i
d) f_id_i

Answer: c
Clarification: If character c_i is at depth d_i and occurs at frequency f_i, the cost of the codeword obtained is ∑f_id_i.

10. An optimal code will always be present in a full tree.
a) true
b) false

Answer: a
Clarification: An optimal tree will always have the property that all nodes are either leaves or have two children. Otherwise, nodes with one child could move up a level.

11. The type of encoding where no character code is the prefix of another character code is called?
a) optimal encoding
b) prefix encoding
c) frequency encoding
d) trie encoding

Answer: b
Clarification: Even if the character codes are of different lengths, the encoding where no character code is the prefix of another character code is called prefix encoding.

12. What is the running time of the Huffman encoding algorithm?
a) O(C)
b) O(log C)
c) O(C log C)
d) O( N log C)

Answer: c
Clarification: If we maintain the trees in a priority queue, ordered by weight, then the running time is given by O(C log C).

13. What is the running time of the Huffman algorithm, if its implementation of the priority queue is done using linked lists?
a) O(C)
b) O(log C)
c) O(C log C)
d) O(C²)
View Answer

Answer: d
Clarification: If the implementation of the priority queue is done using linked lists, the running time of Huffman algorithm is O(C²).

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

1. Which of the following methods can be used to solve the longest palindromic subsequence problem?
a) Dynamic programming
b) Recursion
c) Brute force
d) Dynamic programming, Recursion, Brute force
Answer: d
Clarification: Dynamic programming, Recursion, Brute force can be used to solve the longest palindromic subsequence problem.

2. Which of the following is not a palindromic subsequence of the string “ababcdabba”?
a) abcba
b) abba
c) abbbba
d) adba

Answer: d
Clarification: ‘adba’ is not a palindromic sequence.

3. For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence?
a) A string that is a palindrome
b) A string of length one
c) A string that has all the same letters(e.g. aaaaaa)
d) Some strings of length two
Answer: d
Clarification: A string of length 2 for eg: ab is not a palindrome.

4. What is the length of the longest palindromic subsequence for the string “ababcdabba”?
a) 6
b) 7
c) 8
d) 9

Answer: b
Clarification: The longest palindromic subsequence is “abbabba” and its length is 7.

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

Answer: b
Clarification: In the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. This takes exponential time.

6. For every non-empty string, the length of the longest palindromic subsequence is at least one.
a) True
b) False

Answer: a
Clarification: A single character of any string can always be considered as a palindrome and its length is one.

7. Longest palindromic subsequence is an example of ______________
a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer

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

8. Consider the following code:

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      ______________;
      int arr[len + 1][len + 1];
      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(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[len][len];
}
int main()
{
     char str1[] = "ababcdabba";
     int ans = lps(str1);
     printf("%d",ans);
     return 0;
}

Which of the following lines completes the above code?
a) strrev(str2)
b) str2 = str1
c) len2 = strlen(str2)
d) strlen(str2)

Answer: a
Clarification: To find the longest palindromic subsequence, we need to reverse the copy of the string, which is done by strrev.

9. What is the time complexity of the following dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      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(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[len][len];
}
int main()
{
     char str1[] = "ababcdabba";
     int ans = lps(str1);
     printf("%d",ans);
     return 0;
}

a) O(n)
b) O(1)
c) O(n²)
d) O(2)

Answer: c
Clarification: The time complexity of the above dynamic programming implementation to find the longest palindromic subsequence is O(n²).

10. What is the space complexity of the following dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      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(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[len][len];
}
int main()
{
     char str1[] = "ababcdabba";
     int ans = lps(str1);
     printf("%d",ans);
     return 0;
}

a) O(n)
b) O(1)
c) O(n²)
d) O(2)

Answer: c
Clarification: The space complexity of the above dynamic programming implementation to find the longest palindromic subsequence is O(n²).

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

#include
#include
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      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(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[len][len];
}
int main()
{
      char str1[] = "ababcdabba";
      int ans = lps(str1);
      printf("%d",ans);
      return 0;
}

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

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

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 lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      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(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[len][len];
}
int main()
{
      char str1[] = "abcd";
      int ans = lps(str1);
      printf("%d",ans);
      return 0;
}

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

Answer: b
Clarification: The program prints the length of the longest palindromic subsequence, which is 1.

13. 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 lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      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(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[len][len];
}
int main()
{
      char str1[] = "abdgkagdjbccbba";
      int ans = lps(str1);
      printf("%d",ans);
      return 0;
}

a) 5
b) 7
c) 9
d) 11

Answer: c
Clarification: The program prints the length of the longest palindromic subsequence, which is 9.

and Answers.