250+ TOP MCQs on LSD Radix Sort and Answers

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

1. Which of the following is the distribution sort?
a) Heap sort
b) Smooth sort
c) Quick sort
d) LSD radix sort

Answer: d
Clarification: In Distribution sort the inputted values are distributed to multiple intermediate structures which are then combined and placed on the output. And LSD radix sort distributes values into buckets based on the digits within values, so it is a distribution sort.

2. What is the worst case time complexity of LSD radix sort?
a) O(nlogn)
b) O(wn)
c) O(n)
d) O(n + w)
Answer: b
Clarification: Time complexity of LSD radix sort depends upon the word size and the number on items. It runs in O(wn) time in worst case, where n is the number of inputted elements and w is the number of digits in the largest number.

3. LSD radix sort requires _____ passes to sort N elements.
a) (w/logR)
b) N(w/logR)
c) (w/log(RN))
d) (wN/log(N))

Answer: a
Clarification: LSD radix sort sorts the N elements in (w/logR) passes where w is the number of digits in largest number and R(radix) is extra space required for performing the sorting operation.

4. Which of the following is false?
a) LSD radix sort is an integer sorting algorithm
b) LSD radix sort is a comparison sorting algorithm
c) LSD radix sort is a distribution sort
d) LSD radix sort uses bucket sort

Answer: b
Clarification: LSD radix sort uses bucket sort for grouping the keys based on the digits at that value. And as it grouped the keys based on the digits at that values, it is integer sorting algorithm.

5. Which of the following sorting algorithm is stable?
a) Heap sort
b) Selection sort
c) In-place MSD radix sort
d) LSD radix sort
Answer: d
Clarification: In LSD radix sort after sorting the multiple elements with the same key will be in the same order as they were in the input array. So LSD radix sort is stable sort.

6. LSD radix sort is faster than comparison sorts.
a) True
b) False

Answer: b
Clarification: LSD radix sort is faster than comparison sorts when the word size is less than logn. But LSD radix sort runs slowly for elements with larger word size and smaller radix.

7. Which of the following should be used to sort a huge database on a fixed-length key field?
a) Insertion sort
b) Merge sort
c) LSD radix sort
d) Quick sort
Answer: c
Clarification: LSD radix requires only w passes to sort a fixed-length string, where w is a length of the strings. So, LSD radix sort is best suited to sort a huge database on a fixed-length key field.

8. Which of the following is a combination of LSD and MSD radix sorts?
a) Forward radix sort
b) 3-way radix quick sort
c) Trie base radix sort
d) Flash sort

Answer: a
Clarification: Forward radix sort combines the advantages of LSD and MSD radix sort. Forward radix sort inspects a complete horizontal strip at a time just like LSD radix sort.

9. Which of the following is true for the LSD radix sort?
a) works best for variable length strings
b) accesses memory randomly
c) inner loop has less instructions
d) sorts the keys in left-to-right order

Answer: b
Clarification: LSD radix sort sorts the keys in right-to-left order, working with Least Significant Digit first. The inner loop has a lot of instructions and LSD radix sort is used to sort fixed-length strings.

10. LSD radix sort is in-place sorting algorithm.
a) False
b) True

Answer: a
Clarification: LSD radix is not an in-place sorting algorithm. It needs extra memory to store the elements in bucket and its worst case space complexity is O(w + R).

and Answers.

250+ TOP MCQs on Strassen’s Algorithm and Answers

Data Structures & Algorithms Multiple Choice Questions on “Strassen’s Algorithm”.

1. Strassen’s algorithm is a/an_____________ algorithm.
a) Non- recursive
b) Recursive
c) Approximation
d) Accurate

Answer: b
Clarification: Strassen’s Algorithm for matrix multiplication is a recursive algorithm since the present output depends on previous outputs and inputs.

2. What is the running time of Strassen’s algorithm for matrix multiplication?
a) O(n2.81)
b) O(n3)
c) O(n1.8)
d) O(n2)

Answer: a
Clarification: Strassen’s matrix algorithm requires only 7 recursive multiplications of n/2 x n/2 matrix and Theta(n2) scalar additions and subtractions yielding the running time as O(n2.81).

3. What is the running time of naïve matrix multiplication algorithm?
a) O(n2.81)
b) O(n4)
c) O(n)
d) O(n3)
View Answer

Answer: d
Clarification: The traditional matrix multiplication algorithm takes O(n3) time. The number of recursive multiplications involved in this algorithm is 8.

4. Strassen’s matrix multiplication algorithm follows ___________ technique.
a) Greedy technique
b) Dynamic Programming
c) Divide and Conquer
d) Backtracking

Answer: c
Clarification: Strassen’s matrix multiplication algorithm follows divide and conquer technique. In this algorithm the input matrices are divided into n/2 x n/2 sub matrices and then the recurrence relation is applied.

5. The number of scalar additions and subtractions used in Strassen’s matrix multiplication algorithm is ________
a) O(n2.81)
b) Theta(n2)
c) Theta(n)
d) O(n3)

Answer: b
Clarification: Using Theta(n2) scalar additions and subtractions, 14 matrices are computed each of which is n/2 x n/2. Then seven matrix products are computed recursively.

6. Running time of Strassen’s algorithm is better than the naïve Theta(n3) method.
a) True
b) False

Answer: a
Clarification: Strassen’s Algorithm requires only 7 recursive multiplications when compared with the naïve Theta(n3) method which reuires 9 recursive multiplications to compute the product.

7. Given the program of naïve method.

for i=1 to n do
   for j=1 to n do
       Z[i][j]=0;
       for k=1 to n do 
            ___________________________

Fill in the blanks with appropriate formula
a) Z[i][j] = Z[i][j] + X[i][k]*Y[k][j]
b) Z[i][j] = Z[i][j] + X[i][k] + Y[k][j]
c) Z[i][j] = Z[i][j] * X[i][k]*Y[k][j]
d) Z[i][j] = Z[i][j] * X[i][k] + Y[k][j]

Answer: a
Clarification: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns. The element in each row of one matrix is multiplied with each element in the column of the second matrix. The computed value is placed in the new matrix Z[i][j].

8. Who demonstrated the difference in numerical stability?
a) Strassen
b) Bailey
c) Lederman
d) Higham

Answer: d
Clarification: The difference in the numerical stability was demonstrated by Higham. He overemphasized that Strassen’s algorithm is numericaly unstable for some applications.

9. What is the recurrence relation used in Strassen’s algorithm?
a) 7T(n/2) + Theta(n2)
b) 8T(n/2) + Theta(n2)
c) 7T(n/2) + O(n2)
d) 8T(n/2) + O(n2)

Answer: a
Clarification: The recurrence relation used in Strassen’s algorithm is 7T(n/2) + Theta(n2) since there are only 7 recursive multiplications and Theta(n2) scalar additions and subtractions involved for computing the product.

10. Who discussed techniques for reducing the memory requirements for Strassen’s algorithm?
a) Strassen
b) Lederman
c) Bailey
d) Higham
Answer: c
Clarification: The submatrices formed at the levels of recursion consume space. Hence in order to overcome that Bailey discussed techniques for reducing the memory required.

11. What is the formula to calculate the element present in second row, first column of the product matrix?
a) M1+M7
b) M1+M3
c) M2+M4 – M5 + M7
d) M2+M4

Answer: d
Clarification: The element at second row, first column can be found by the formula M2 + M4, where M2 and M4 can be calculated by
M2= (A(2,1) + A(2,2)) B(1,1)
M4=A(2,2)(B(1,2) – B(1,1)).

12. Strassen’s Matrix Algorithm was proposed by _____________
a) Volker Strassen
b) Andrew Strassen
c) Victor Jan
d) Virginia Williams

Answer: a
Clarification: Strassen’s matrix multiplication algorithm was first published by Volker Strassen in the year 1969 and proved that the n3 general matrix multiplication algorithm wasn’t optimal.

13. How many iterating statements are involved in the naïve method of matrix multiplication?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns in a matrix. The element in each row of the first matrix is multiplied with each element in the column of the second matrix.

14. Strassen’s algorithm is quite numerically stable as the naïve method.
a) True
b) False

Answer: b
Clarification: Strassen’s algorithm is too numerically unstable for some applications. The computed result C=AB satisfies the inequality with a unit roundoff error which corresponds to strong stability inequality(obtained by replacing matrix norms with absolute values of the matrix elements).

15. Compute the product matrix using Strassen’s matrix multiplication algorithm.
Given a11=1; a12=3;a21=5;a22=7
b11=8;b12=4;b21=6;b22=2
a) c11=20;c12=12;c21=100;c22=15
b) c11=22;c12=8;c21=90;c22=32
c) c11=15;c12=7;c21=80;c22=34
d) c11=26;c12=10;c21=82;c22=34
Answer: d
Clarification: The solution can be obtained by
C11=1*8 + 3*6 =8+18=26
C12=1*4 + 3*2 =4+6=10
C21=5*8 + 7*6 =40+42=82
C22= 5*4 + 7*2=20+14=34.

250+ TOP MCQs on Branch and Bound and Answers

Data Structures & Algorithms Multiple Choice Questions on “Branch and Bound”.

1. Branch and bound is a __________
a) problem solving technique
b) data structure
c) sorting algorithm
d) type of tree

Answer: a
Clarification: Branch and bound is a problem solving technique generally used for solving combinatorial optimization problems. Branch and bound helps in solving them faster.

2. Which of the following is not a branch and bound strategy to generate branches?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: d
Clarification: LIFO, FIFO and Lowest cost branch and bound are different strategies to generate branches. Lowest cost branch and bound helps us find the lowest cost path.

3. Which data structure is used for implementing a LIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list
Answer: a
Clarification: Stack is the data structure is used for implementing LIFO branch and bound strategy. This leads to depth first search as every branch is explored until a leaf node is discovered.

4. Which data structure is used for implementing a FIFO branch and bound strategy?
a) stack
b) queue
c) array
d) linked list

Answer: b
Clarification: Queue is the data structure is used for implementing FIFO branch and bound strategy. This leads to breadth first search as every branch at depth is explored first before moving to the nodes at greater depth.

5. Which data structure is most suitable for implementing best first branch and bound strategy?
a) stack
b) queue
c) priority queue
d) linked list

Answer: c
Clarification: Priority Queue is the data structure is used for implementing best first branch and bound strategy. Dijkstra’s algorithm is an example of best first search algorithm.

6. Which of the following branch and bound strategy leads to breadth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound
Answer: b
Clarification: LIFO, FIFO and Lowest cost branch and bound are different strategies to generate branches. FIFO branch and bound leads to breadth first search.

7. Which of the following branch and bound strategy leads to depth first search?
a) LIFO branch and bound
b) FIFO branch and bound
c) Lowest cost branch and bound
d) Highest cost branch and bound

Answer: a
Clarification: LIFO, FIFO and Lowest cost branch and bound are different strategies to generate branches. LIFO branch and bound leads to depth first search.

8. Both FIFO branch and bound strategy and backtracking leads to depth first search.
a) true
b) false
Answer: b
Clarification: FIFO branch and bound leads to breadth first search. Whereas backtracking leads to depth first search.

9. Both LIFO branch and bound strategy and backtracking leads to depth first search.
a) true
b) false

Answer: a
Clarification: Both backtrackings as well as branch and bound are problem solving algorithms. Both LIFO branch and bound strategy and backtracking leads to depth first search.

10. Choose the correct statement from the following.
a) branch and bound is more efficient than backtracking
b) branch and bound is not suitable where a greedy algorithm is not applicable
c) branch and bound divides a problem into at least 2 new restricted sub problems
d) backtracking divides a problem into at least 2 new restricted sub problems

Answer: c
Clarification: Both backtracking as well as branch and bound are problem solving algorithms. Branch and bound is less efficient than backtracking. Branch and bound divides a problem into at least 2 new restricted sub problems.

11. Which of the following can traverse the state space tree only in DFS manner?
a) branch and bound
b) dynamic programming
c) greedy algorithm
d) backtracking

Answer: d
Clarification: Both backtracking as well as branch and bound are problem solving algorithms. Branch and bound can traverse in DFS as well as BFS manner whereas backtracking only traverses in DFS manner.

& Algorithms.

here is

250+ TOP MCQs on Complete Bipartite Graph and Answers

Data Structures & Algorithms Multiple Choice Questions on “Complete Bipartite Graph”.

1. Which type of graph has all the vertex of the first set connected to all the vertex of the second set?
a) Bipartite
b) Complete Bipartite
c) Cartesian
d) Pie
Answer: b
Clarification: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. The complete bipartite graph has all the vertex of first set connected to all the vertex of second set.

2. Which graph is also known as biclique?
a) Histogram
b) Complete Bipartite
c) Cartesian
d) Tree

Answer: b
Clarification: A graph is known as complete bipartite graph if and only if it has all the vertex of first set connected to all the vertex of second set. Complete Bipartite graph is also known as Biclique.

3. Which term defines all the complete bipartite graph that are trees?
a) Symmetric
b) Anti – Symmetric
c) Circular
d) Stars

Answer: d
Clarification: Star is a complete bipartite graph with one internal node and k leaves. Therefore, all complete bipartite graph which is trees are known as stars in graph theory.

4. How many edges does a n vertex triangle free graph contains?
a) n2
b) n2 + 2
c) n2 / 4
d) n3

Answer: c
Clarification: A n vertex triangle free graph contains a total of n2 / 4 number of edges. This is stated by Mantel’s Theorem which is a special case in Turan’s theorem for r=2.

5. Which graph is used to define the claw free graph?
a) Bipartite Graph
b) Claw Graph
c) Star Graph
d) Cartesian Graph

Answer: b
Clarification: Star is a complete bipartite graph with one internal node and k leaves. Star with three edges is called a claw. Hence this graph is used to define claw free graph.

6. What is testing of a complete bipartite subgraph in a bipartite graph problem called?
a) P Problem
b) P-Complete Problem
c) NP Problem
d) NP-Complete Problem

Answer: d
Clarification: NP stands for nondeterministic polynomial time. In a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an NP-Complete Problem.

7. Which graph cannot contain K3, 3 as a minor of graph?
a) Planar Graph
b) Outer Planar Graph
c) Non Planar Graph
d) Inner Planar Graph
Answer: a
Clarification: Minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. Hence Planar graph cannot contain K3, 3 as a minor graph.

8. Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph?
a) (nm)1/2
b) (-nm)1/2
c) 0
d) nm

Answer: d
Clarification: The adjacency matrix is a square matrix that is used to represent a finite graph. Therefore, the Eigen values for the complete bipartite graph is found to be (nm)1/2, (-nm)1/2, 0.

9. Which complete graph is not present in minor of Outer Planar Graph?
a) K3, 3
b) K3, 1
c) K3, 2
d) K1, 1

Answer: c
Clarification: Minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. Hence Outer Planar graph cannot contain K3, 2 as a minor graph.

10. Is every complete bipartite graph a Moore Graph.
a) True
b) False

Answer: a
Clarification: In graph theory, Moore graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a Moore Graph.

11. What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value?
a) 1
b) n + m – 2
c) 0
d) 2

Answer: b
Clarification: The adjacency matrix is a square matrix that is used to represent a finite graph. The multiplicity of the adjacency matrix off complete bipartite graph with Eigen Value 0 is n + m – 2.

12. Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph?
a) n + m
b) n
c) 0
d) n*m

Answer: d
Clarification: The laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. Therefore, the Eigen values for the complete bipartite graph is found to be n + m, n, m, 0.

13. What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value?
a) 1
b) m-1
c) n-1
d) 0

Answer: b
Clarification: The laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. The multiplicity of the laplacian matrix of complete bipartite graph with Eigen Value n is m-1.

14. Is it true that every complete bipartite graph is a modular graph.
a) True
b) False

Answer: a
Clarification: Yes, the modular graph in graph theory is defined as an undirected graph in which all three vertices have at least one median vertex. So all complete bipartite graph is called modular graph.

15. How many spanning trees does a complete bipartite graph contain?
a) nm
b) mn-1 * nn-1
c) 1
d) 0
Answer: b
Clarification: Spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having minimum number of edges. So, there are a total of mn-1 * nn-1 spanning trees for a complete bipartite graph.

250+ TOP MCQs on Largest and Smallest Number in a Linked List using Recursion and Answers

Data Structure online quiz on “Largest and Smallest Number in a Linked List using Recursion”.

1. Which of the following methods can be used to find the largest and smallest number in a linked list?
a) Recursion
b) Iteration
c) Both Recursion and iteration
d) Impossible to find the largest and smallest numbers
View Answer

Answer: c
Clarification: Both recursion and iteration can be used to find the largest and smallest number in a linked list.

2. Consider the following code snippet to find the largest element in a linked list:

struct Node{
   int val;
   struct Node *next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(______)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = temp->next;
	  }
	  return max_num;
}

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

Answer: b
Clarification: The line “temp != 0” should be inserted to complete the above code.

3. Consider the following code snippet to find the smallest element in a linked list:

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

Which of the following lines should be inserted to complete the above code?
a) temp > min_num
b) val > min_min
c) temp->val < min_num
d) temp->val > min_num

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

4. What is the output of the following code:

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = head->next;
	  }
	  return max_num;
}
int main()
{
      int n = 9, arr[9] ={5,1,3,4,5,2,3,3,1},i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head -> next =0;
      temp = head;
      for(i=0;i<n;i++)
      {
          newNode =(struct Node*)malloc(sizeof(struct Node));
          newNode->next = 0;
          newNode->val = arr[i];
          temp->next =newNode;
          temp = temp->next;
      }
      int max_num = get_max();
      printf("%d %d",max_num);
      return 0;
}

a) 5
b) 1
c) runtime error
d) garbage value

Answer: c
Clarification: The variable temp will always point to the first element in the linked list due to the line “temp = head->next” in the while loop. So, it will be an infinite while loop and the program will produce a runtime error.

5. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = temp->next;
	  }
	  return max_num;
}
int get_min()
{
      struct Node* temp = head->next;
	  int min_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val < min_num)
		    min_num = temp->val;
		temp = temp->next;
	  }
	  return min_num;
}
int main()
{
      int i, n = 9, arr[9] ={8,3,3,4,5,2,5,6,7};
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head -> next =0;
      temp = head;
      for(i=0;i<n;i++)
      {
          newNode =(struct Node*)malloc(sizeof(struct Node));
          newNode->next = 0;
          newNode->val = arr[i];
          temp->next =newNode;
          temp = temp->next;
      }
      int max_num = get_max();
      int min_num = get_min();
      printf("%d %d",max_num,min_num);
      return 0;
}

a) 2 2
b) 8 8
c) 2 8
d) 8 2
View Answer

Answer: d
Clarification: The program prints the largest and smallest elements in the linked list, which are 8 and 2 respectively.

6. What is the time complexity of the following iterative code used to find the smallest and largest element in a linked list?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int get_max()
{
      struct Node* temp = head->next;
	  int max_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val > max_num)
		    max_num = temp->val;
		temp = temp->next;
	  }
	  return max_num;
}
int get_min()
{
      struct Node* temp = head->next;
	  int min_num = temp->val;
	  while(temp != 0)
	  {
	        if(temp->val < min_num)
		    min_num = temp->val;
		temp = temp->next;
	  }
	  return min_num;
}
int main()
{
      int i, n = 9, arr[9] ={8,3,3,4,5,2,5,6,7};
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head -> next =0;
      temp = head;
      for(i=0;i<n;i++)
      {
          newNode =(struct Node*)malloc(sizeof(struct Node));
          newNode->next = 0;
          newNode->val = arr[i];
          temp->next =newNode;
          temp = temp->next;
      }
      int max_num = get_max();
      int min_num = get_min();
      printf("%d %d",max_num,min_num);
      return 0;
}

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

Answer: b
Clarification: The time complexity of the above iterative code used to find the largest and smallest element in a linked list is O(n).

7. Consider the following recursive implementation to find the largest element in a linked list:

struct Node
{
     int val;
     struct Node* next;
}*head;
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_get_max(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return max_of_two(______, _______);
}

Which of the following arguments should be passed to the function max_of two() to complete the above code?
a) temp->val,recursive_get_max(temp->next)
b) temp, temp->next
c) temp->val, temp->next->val
d) temp->next->val, temp

Answer: a
Clarification: The arguments {temp->val,recursive_get_max(temp->next)} should be passed to the function max_of_two() to complete the above code.

8. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_get_max(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return max_of_two(temp->val,recursive_get_max(temp->next));
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 9, arr[9] ={1,3,2,4,5,0,5,6,7},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int max_num = recursive_get_max(head->next);
     int min_num = recursive_get_min(head->next);
     printf("%d %d",max_num,min_num);
     return 0;
}

a) 7 1
b) 0 7
c) 7 0
d) 1 1

Answer: c
Clarification: The program prints the largest and the smallest elements in the linked list, which are 7 and 0 respectively.

9. What is the time complexity of the recursive implementation used to find the largest and smallest element in a linked list?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_get_max(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return max_of_two(temp->val,recursive_get_max(temp->next));
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 9, arr[9] ={1,3,2,4,5,0,5,6,7},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int max_num = recursive_get_max(head->next);
     int min_num = recursive_get_min(head->next);
     printf("%d %d",max_num,min_num);
     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 used to find the largest and smallest element in linked list is O(n).

10. What is the output of the following code?

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 5, arr[5] ={1,1,1,1,1},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int min_num = recursive_get_min(head->next);
     printf("%d",min_num);
     return 0;
}

a) 1
b) 0
c) compile time error
d) runtime error

Answer: a
Clarification: The program prints the smallest element in the linked list, which is 1.

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

#include
#include
struct Node
{
     int val;
     struct Node* next;
}*head;
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_get_min(struct Node* temp)
{
      if(temp->next == 0)
        return  temp->val;
      return min_of_two(temp->val,recursive_get_min(temp->next));
}
int main()
{
     int n = 5, arr[5] ={1,1,1,1,1},i;
     struct Node *temp, *newNode;
     head = (struct Node*)malloc(sizeof(struct Node));
     head -> next =0;
     temp = head;
     for(i=0;i<n;i++)
     {
           newNode =(struct Node*)malloc(sizeof(struct Node));
           newNode->next = 0;
           newNode->val = arr[i];
           temp->next =newNode;
           temp = temp->next;
     }
     int min_num = recursive_get_min(head->next);
     printf("%d",min_num);
     return 0;
}

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

Answer: b
Clarification: The function recursive_get_min() will be called 5 times when the above code is executed.

250+ TOP MCQs on Maximum Sum of Continuous Subarray and Answers

Data Structure Multiple Choice Questions on “Maximum Sum of Continuous Subarray – 1”.

1. Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
a) Dynamic programming
b) Two for loops (naive method)
c) Divide and conquer
d) Dynamic programming, naïve method and Divide and conquer methods

Answer: d
Clarification: Dynamic programming, naïve method and Divide and conquer methods can be used to solve the maximum sub array sum problem.

2. Find the maximum sub-array sum for the given elements.
{2, -1, 3, -4, 1, -2, -1, 5, -4}
a) 3
b) 5
c) 8
d) 6
View Answer

Answer: b
Clarification: The maximum sub-array sum is 5.

3. Find the maximum sub-array sum for the given elements.
{-2, -1, -3, -4, -1, -2, -1, -5, -4}
a) -3
b) 5
c) 3
d) -1

Answer: d
Clarification: All the elements are negative. So, the maximum sub-array sum will be equal to the largest element. The largest element is -1 and therefore, the maximum sub-array sum is -1.

4. Consider the following naive method to find the maximum sub-array sum:

#include
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

Which line should be inserted to complete the above code?
a) tmp_max = cur_max
b) break
c) continue
d) cur_max = tmp_max

Answer: d
Clarification: If the tmp_max element is greater than the cur_max element, we make cur_max equal to tmp_max, i.e. cur_max = tmp_max.

5. What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

#include
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

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

Answer: a
Clarification: The naive method uses two for loops. The outer loop runs from 0 to n,
i.e. i = 0 : n.
The inner loop runs from i to n, i.e. j = i : n.
Therefore, the inner loop runs:
n times when the outer loop runs the first time.
(n-1) times when the outer loop runs the second time.
:
:
:
2 times when the outer loop runs (n-1)th time.
1 time when the outer loop runs nth time.
Therefore, time complexity = n + (n-1) + (n-2) + …… + 2 + 1 = n * (n + 1) /2 = O(n2).

6. What is the space complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

#include
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

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

Answer: b
Clarification: The naive method uses only a constant space. So, the space complexity is O(1).

7. What is the output of the following naive method used to find the maximum sub-array sum?

#include
int main()
{
     int arr[1000] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	   tmp_max = 0;
	   for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	   {
	        tmp_max += arr[sub_arr_idx];
	        if(tmp_max > cur_max)
	        cur_max = tmp_max;
	   }
     }
     printf("%d",cur_max);
     return 0;
}

a) 6
b) 9
c) 7
d) 4
Answer: c
Clarification: The naive method prints the maximum sub-array sum, which is 7.

8. What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)
Answer: c
Clarification: The time complexity of the divide and conquer algorithm used to find the maximum sub-array sum is O(nlogn).

9. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(1)
c) O(n!)
d) O(n2)
Answer: b
Clarification: The divide and conquer algorithm uses a constant space. So, the space complexity is O(1).

and Answers.

contest