250+ TOP MCQs on Pigeonhole Sort and Answers

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

1. How many comparisons will be made to sort the array arr={1,5,3,8,2} using pigeonhole sort?
a) 5
b) 7
c) 9
d) 0

Answer: d
Clarification: As pigeonhole sort is an example of a non-comparison sort so it is able to sort an array without making any comparison. So 0 comparisons are required.

2. Which of the following is a non-comparison sort?
a) heap sort
b) quick sort
c) merge sort
d) pigeonhole sort

Answer: d
Clarification: Heap sort, merge sort and quick sort are examples of comparison sort as it needs to compare array elements in order to sort an array. Whereas pigeonhole sort is a non-comparison based sort.

3. In which of the following case pigeonhole sort is most efficient?
a) when range of input is less than number of elements
b) when range of input is more than number of elements
c) when range of input is comparable to the number of elements
d) when the given array is almost sorted
Answer: c
Clarification: Pigeonhole sort is a non-comparison based sort. It is most efficient in the case where the number of elements are comparable to the input range.

4. What is the space complexity of pigeonhole sort (k=range of input)?
a) O(n*k)
b) O(n)
c) O(k)
d) O(n+k)
Answer: d
Clarification: Pigeonhole sort algorithm requires two arrays. The first one is required to store the input elements so its size is n. The second one is the pigeonhole array and has a size equal to range k. Overall space complexity becomes O(n+k).

5. The auxiliary array used in pigeonhole sorting is called ______________
a) bucket
b) pigeon
c) hole
d) pigeonhole

Answer: d
Clarification: The auxiliary array used in pigeonhole sorting is called pigeonhole. It is used to store every element in its corresponding hole.

6. Pigeonhole sort is a stable sorting algorithm.
a) true
b) false
View Answer

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

7. Pigeonhole sort is an in place sorting algorithm.
a) true
b) false

Answer: b
Clarification: Pigeonhole sort requires space of O(n+k). So it does not qualify to be an in place sorting algorithm.

8. What is the average time complexity of pigeonhole sort (k=range of input)?
a) O(n)
b) O(n+k)
c) O(n2)
d) O(n*k)

Answer: b
Clarification: Time complexity of pigeonhole sort is O(n+k). It has two loops. One of the loops runs from 0 to range(k) and the other one runs from 0 to n so the time complexity becomes O(n+k).

9. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case?
a) quick sort
b) insertion sort
c) pigeonhole sort
d) bubble sort
Answer: c
Clarification: The time complexity of pigeonhole remains unvaried in all three cases. It is given by O(n+k). But it is efficient only when the number of elements is comparable to the input range.

10. Choose the correct statement from the following.
a) pigeonhole sort is a comparison based sort
b) any comparison based sorting can be made stable
c) quick sort is not a comparison based sort
d) any comparison based sort requires at least O(n2) time

Answer: b
Clarification: Any comparison based sorting technique can be made stable by considering the position as criteria while making comparisons. Pigeonhole sort is a stable sort.

11. What is the advantage of pigeonhole sort over merge sort?
a) pigeonhole sort has lesser time complexity when range is comparable to number of input elements
b) pigeonhole sort has lesser space complexity
c) counting sort is not a comparison based sorting technique
d) pigeonhole sort is adaptive

Answer: a
Clarification: Pigeonhole sort is efficient in the cases where the range is comparable to a number of input elements as it performs sorting in linear time. Whereas merge sort takes O(n log n) in any case.

12. Which of the following function represents pigeonhole sort correctly?
a)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[r]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < r; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

b)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[n]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < r; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

c)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[r]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < n; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

d)

void Sorting(int arr[], int n) 
{ 
 
	int minimum = arr[0], maximum = arr[0]; 
	for (int i = 1; i < n; i++) 
	{ 
		if (arr[i] < minimum) 
			minimum = arr[i]; 
		if (arr[i] > maximum) 
			maximum = arr[i]; 
	} 
	int r = maximum - minimum + 1; 
	vector<int> p_holes[n]; 
	for (int i = 0; i < n; i++) 
		p_holes[arr[i]-minimum].push_back(arr[i]); 
	int ind = 0; 
	for (int i = 0; i < n; i++) 
	{ 
	    vector<int>::iterator it; 
	    for (it = p_holes[i].begin(); it != p_holes[i].end(); ++it) 
			arr[ind++] = *it; 
	} 
}

Answer: a
Clarification: In pigeonhole sort, we first find the maximum and minimum elements. Then we place the elements in their corresponding holes and then finally put them back into the original array. This sorts the given input.

 
 

13. Which of the following algorithm takes linear time for sorting?
a) pigeonhole sort
b) heap sort
c) comb sort
d) cycle sort

Answer: a
Clarification: Pigeonhole sort has a linear time complexity of O(n+k). Whereas all other given options have a non linear time complexity. But it should be noted that pigeonhole sort may not be efficient in every case.

250+ TOP MCQs on Euclid’s Algorithm and Answers

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

1. Euclid’s algorithm is used for finding ___________
a) GCD of two numbers
b) GCD of more than three numbers
c) LCM of two numbers
d) LCM of more than two numbers

Answer: a
Clarification: Euclid’s algorithm is basically used to find the GCD of two numbers. It cannot be directly applied to three or more numbers at a time.

2. Who invented Euclid’s algorithm?
a) Sieve
b) Euclid
c) Euclid-Sieve
d) Gabriel lame
Answer: b
Clarification: Euclid invented Euclid’s algorithm. Sieve provided an algorithm for finding prime numbers. Gabriel lame proved a theorem in Euclid’s algorithm.

3. If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?
a) 12
b) 6
c) 4
d) 2

Answer: c
Clarification: Euclid’s algorithm states that the GCD of two numbers does not change even if the bigger number is replaced by a difference of two numbers. So, GCD of 16 and 12 and 12 and (16-12)=4 is the same.

4. Which of the following is not an application of Euclid’s algorithm?
a) Simplification of fractions
b) Performing divisions in modular arithmetic
c) Solving quadratic equations
d) Solving diophantine equations

Answer: c
Clarification: Solving quadratic equations is not an application of Euclid’s algorithm whereas the rest of the options are mathematical applications of Euclid’s algorithm.

5. The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero.
a) True
b) False

Answer: a
Clarification: The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero. This improvement in efficiency was put forth by Gabriel Lame.

6. According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?
a) Less than five times the number of digits
b) More than five times the number of digits
c) Less than two times the number of digits
d) More than two times the number of digits

Answer: a
Clarification: The Euclid’s algorithm requires less than five times the number of digits. It runs by dividing two numbers. It stops when a remainder zero is reached.

7. Which of the following is the correct mathematical application of Euclid’s algorithm?
a) Determination of prime numbers
b) Lagrange’s four square theorem
c) Cauchy-Euler theorem
d) Residue theorem

Answer: b
Clarification: Lagrange’s four square theorem is one of the mathematical applications of Euclid’s algorithm and it is the basic tool for proving theorems in number theory. It can be generalized into other types of numbers like the Gaussian integers.

8. If GCD of two numbers is 1, then the two numbers are said to be ________
a) Co-prime numbers
b) Prime numbers
c) Composite numbers
d) Rational numbers

Answer: a
Clarification: If GCD of two numbers is 1, they are called as co-prime or relatively prime numbers. It does not mean that they are prime numbers. They don’t have any prime factors in common.

9. What is the total running time of Euclid’s algorithm?
a) O(N)
b) O(N log M)
c) O(N log N)
d) O(log N +1)

Answer: a
Clarification: The total running time of Euclid’s algorithm according to Lame’s analysis is found to be O(N).

10. Euclidean algorithm does not require the calculation of prime factors.
a) True
b) False
View Answer

Answer: a
Clarification: Euclid’s algorithm does not require the calculation of prime factors. We derive the answer straight away using formula. And also, factorization is complex.

11. What is the formula for Euclidean algorithm?
a) GCD (m,n) = GCD (n, m mod n)
b) LCM(m,n)=LCM(n, m mod n)
c) GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o)
d) LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o)

Answer: a
Clarification: The formula for computing GCD of two numbers using Euclidean algorithm is given as GCD (m,n)= GCD (n, m mod n). It is used recursively until zero is obtained as a remainder.

12. What is the total running time of the binary GCD algorithm?
a) O(N)
b) O(N2)
c) O(log N)
d) O(N log N)

Answer: b
Clarification: Binary GCD algorithm is a sub division of Euclidean algorithm with more faster operations. Its running time is given by O(N2).

13. What is the GCD of 20 and 12 using Euclid’s algorithm?
a) 8
b) 2
c) 4
d) 6

Answer: c
Clarification: GCD(m,n)=GCD(n, m mod n)
GCD(20,12)=GCD( 12,8)
= GCD(8,4)
= GCD(4,0) = 4.

250+ TOP MCQs on Best First Search and Answers

Data Structures & Algorithms Multiple Choice Questions on “Best First Search”.

1. Is Best First Search a searching algorithm used in graphs.
a) True
b) False

Answer: a
Clarification: Best First Search is a searching algorithm used in graphs. It explores it by choosing a node by heuristic evaluation rule. It is used in solving searching for related problems.

2. Who described this Best First Search algorithm using heuristic evaluation rule?
a) Judea Pearl
b) Max Bezzel
c) Franz Nauck
d) Alan Turing

Answer: a
Clarification: The best first search algorithm using heuristic evaluation rule or function was proposed by an Israeli – American computer scientist and philosopher Judea Pearl.

3. Which type of best first search algorithm was used to predict the closeness of the end of path and its solution?
a) Greedy BFS
b) Divide and Conquer
c) Heuristic BFS
d) Combinatorial
Answer: a
Clarification: The greedy best first search algorithm was used to predict the closeness of the end of the path and its solution by some of the computer scientists.

4. What is the other name of the greedy best first search?
a) Heuristic Search
b) Pure Heuristic Search
c) Combinatorial Search
d) Divide and Conquer Search

Answer: b
Clarification: The greedy best first search algorithm was used to predict the closeness of the end of the path and its solution by some of the computer scientists. It is also known as Pure Heuristic Search.

5. Which algorithm is used in graph traversal and path finding?
a) A*
b) C*
c) D*
d) E*

Answer: a
Clarification: In computer science A* algorithm is used in graph traversal and path finding. It is a process of node finding in between a path. It is an example of the best first search.

6. Which algorithm is used to find the least cost path from source node to destination node?
a) A* BFS
b) C* BFS
c) D* BFS
d) B* BFS

Answer: d
Clarification: In computer science, B* algorithm is used to find the least cost path between the source node and the destination node. It is an example of the best first search.

7. Which of the following is an example of Best First Search algorithm?
a) A*
b) B*
c) C*
d) Both A* and B*

Answer: d
Clarification: In computer science, A* algorithm is used in graph traversal and path finding. It is a process of node finding in between a path. B* algorithm is used to find the least cost path between the source node and the destination node.

8. Which of the following is the greedy best first search?
a) Pure Heuristic Search
b) A*
c) B*
d) Both A* and B*

Answer: a
Clarification: Pure Heuristic Search is also called greedy best first search while A* and B* search algorithms are not greedy best first search.

9. Which of the following scientists didn’t publish A* algorithm?
a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner

Answer: d
Clarification: Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who first published the A* search algorithm which uses heuristics for better performance. Hans Berliner published B* algorithm.

10. Who published the B* search algorithm?
a) Peter Hart
b) Nils Nilsson
c) Bertram Raphael
d) Hans Berliner

Answer: d
Clarification: Hans Berliner was a Computer Science professor who first published the B* search algorithm in 1979. While Peter Hart Nils Nilsson Bertram Raphael are the three scientists of SRI International who first published the A* search algorithm which uses heuristics for better performance.

250+ TOP MCQs on Properties of Bipartite Graphs and Answers

Data Structures & Algorithms Multiple Choice Questions on “Properties of Bipartite Graphs”.

1. Which type of graph has no odd cycle in it?
a) Bipartite
b) Histogram
c) Cartesian
d) Pie
Answer: a
Clarification: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. Odd length cycle means a cycle with the odd number of vertices in it.

2. What type of graph has chromatic number less than or equal to 2?
a) Histogram
b) Bipartite
c) Cartesian
d) Tree
Answer: b
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is chromatic number.

3. Which of the following is the correct type of spectrum of the bipartite graph?
a) Symmetric
b) Anti – Symmetric
c) Circular
d) Exponential

Answer: a
Clarification: The spectrum of the bipartite graph is symmetric in nature. The spectrum is the property of graph that are related to polynomial, Eigen values, Eigen vectors of the matrix related to graph.

4. Which of the following is not a property of the bipartite graph?
a) No Odd Cycle
b) Symmetric spectrum
c) Chromatic Number Is Less Than or Equal to 2
d) Asymmetric spectrum

Answer: d
Clarification: A graph is known to be bipartite if it has odd length cycle number. It also has symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2.

5. Which one of the following is the chromatic number of bipartite graph?
a) 1
b) 4
c) 3
d) 5

Answer: a
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number.

6. Which graph has a size of minimum vertex cover equal to maximum matching?
a) Cartesian
b) Tree
c) Heap
d) Bipartite

Answer: d
Clarification: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.

7. Which theorem gives the relation between the minimum vertex cover and maximum matching?
a) Konig’s Theorem
b) Kirchhoff’s Theorem
c) Kuratowski’s Theorem
d) Kelmans Theorem

Answer: a
Clarification: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.

8. Which of the following is not a property of perfect graph?
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Line Graph

Answer: d
Clarification: TThe Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as a perfect graph in graph theory. Normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph.

9. Which of the following graphs don’t have chromatin number less than or equal to 2?
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Wheel graph

Answer: d
Clarification: The perfect bipartite graph has chromatic number 2. Also, the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as perfect graph in graph theory. Wheel graph Wn has chromatin number 3 if n is odd and 4 if n is even.

10. Which of the following has maximum clique size 2?
a) Perfect graph
b) Tree
c) Histogram
d) Cartesian

Answer: a
Clarification: The perfect bipartite graph has clique size 2. Also, the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.

11. What is the chromatic number of compliment of line graph of bipartite graph?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The perfect bipartite graph has chromatic number 2. So the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph has chromatic number 2.

12. What is the clique size of the line graph of bipartite graph?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The perfect bipartite graph has clique size 2. So the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.

13. It is possible to have a negative chromatic number of bipartite graph.
a) True
b) False

Answer: b
Clarification: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number. But the chromatic number cannot be negative.

14. Every Perfect graph has forbidden graph characterization.
a) True
b) False

Answer: a
Clarification: Berge theorem proves the forbidden graph characterization of every perfect graphs. Because of that reason every bipartite graph is perfect graph.

15. Which structure can be modelled by using Bipartite graph?
a) Hypergraph
b) Perfect Graph
c) Hetero Graph
d) Directed Graph

Answer: a
Clarification: A combinatorial structure such as Hypergraph can be made using the bipartite graphs. A hypergraph in graph theory is a type of graph in which edge can join any number of vertices.

250+ TOP MCQs on Largest and Smallest Number in an Array using Recursion and Answers

Data Structure online test on “Largest and Smallest Number in an Array using Recursion”.

1. Which of the following methods can be used to find the largest and smallest element in an array?
a) Recursion
b) Iteration
c) Both recursion and iteration
d) No method is suitable
Answer: c
Clarification: Both recursion and iteration can be used to find the largest and smallest element in an array.

2. Consider the following iterative code snippet to find the largest element:

int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
          if(________)
          max_element = arr[i];
      return max_element;
}

Which of the following lines should be inserted to complete the above code?
a) arr[i] > max_element
b) arr[i] < max_element
c) arr[i] == max_element
d) arr[i] != max_element
Answer: a
Clarification: The line “arr[i] > max_element” should be inserted to complete the above code snippet.

3. Consider the following code snippet to find the smallest element in an array:

int get_min_element(int *arr, int n)
{
      int i, min_element = arr[0];
      for(i = 1; i < n; i++)
        if(_______)
          min_element = arr[i];
      return min_element;
}

Which of the following lines should be inserted to complete the above code?
a) arr[i] > min_element
b) arr[i] < min_element
c) arr[i] == min_element
d) arr[i] != min_element
Answer: b
Clarification: The line “arr[i] < min_element” should be inserted to complete the above code.

4. What is the output of the following code?

#include
int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] > max_element)
          max_element = arr[i];
      return max_element;
}
int get_min_element(int *arr, int n)
{
      int i, min_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] < min_element)
          min_element = arr[i];
      return min_element;
}
int main()
{
     int n = 7, arr[7] = {5,2,4,7,8,1,3};
     int max_element = get_max_element(arr,n);
     int min_element = get_min_element(arr,n);
     printf("%d %d",max_element,min_element);
     return 0;
}

a) 5 3
b) 3 5
c) 8 1
d) 1 8

Answer: c
Clarification: The program prints the values of the largest and the smallest elements in the array, which are 8 and 1 respectively.

5. What is the output of the following code?

#include
int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] > max_element)
          max_element = arr[i];
      return max_element;
}
int get_min_element(int *arr, int n)
{
      int i, min_element;
      for(i = 1; i < n; i++)
        if(arr[i] < min_element)
          min_element = arr[i];
      return min_element;
}
int main()
{
     int n = 7, arr[7] = {1,1,1,0,-1,-1,-1};
     int max_element = get_max_element(arr,n);
     int min_element = get_min_element(arr,n);
     printf("%d %d",max_element,min_element);
     return 0;
}

a) 1 -1
b) -1 1
c) 1 Garbage value
d) Depends on the compiler
Answer: c
Clarification: Since the min_element variable is not initialised, some compilers will auto initialise as 0 which produces -1 as output whereas some compilers won’t initialise automatically. In that case, the result will be a garbage value hence the output depends on the compiler.

6. What is the time complexity of the following iterative implementation used to find the largest and smallest element in an array?

#include
int get_max_element(int *arr,int n)
{
      int i, max_element = arr[0];
      for(i = 1; i < n; i++)
        if(arr[i] > max_element)
          max_element = arr[i];
      return max_element;
}
int get_min_element(int *arr, int n)
{
      int i, min_element;
      for(i = 1; i < n; i++)
        if(arr[i] < min_element)
          min_element = arr[i];
      return min_element;
}
int main()
{
     int n = 7, arr[7] = {1,1,1,0,-1,-1,-1};
     int max_element = get_max_element(arr,n);
     int min_element = get_min_element(arr,n);
     printf("%d %d",max_element,min_element);
     return 0;
}

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

Answer: b
Clarification: The time complexity of the above iterative implementation used to find the largest and the smallest element in an array is O(n).

7. Consider the following recursive implementation to find the largest element in an array.

int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return _______;
}

Which of the following lines should be inserted to complete the above code?
a) max_of_two(arr[idx], recursive_max_element(arr, len, idx))
b) recursive_max_element(arr, len, idx)
c) max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1))
d) recursive_max_element(arr, len, idx + 1)

Answer: c
Clarification: The line “max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1))” should be inserted to complete the above code.

8. What is the output of the following code?

#include
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1));
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
    int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10};
    int max_element = recursive_max_element(arr,n,idx);
    int min_element = recursive_min_element(arr,n,idx);
    printf("%d %d",max_element,min_element);
    return 0;
}

a) -1 10
b) 10 -1
c) 1 10
d) 10 1

Answer: b
Clarification: The program prints the values of the largest and the smallest element in the array, which are 10 and -1 respectively.

9. What is the time complexity of the following recursive implementation used to find the largest and the smallest element in an array?

#include
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1));
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
    int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10};
    int max_element = recursive_max_element(arr,n,idx);
    int min_element = recursive_min_element(arr,n,idx);
    printf("%d %d",max_element,min_element);
    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 recursive implementation used to find the largest and smallest element in an array is O(n).

10. How many times is the function recursive_min_element() called when the following code is executed?

int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
     int n = 10, idx = 0, arr[] = {5,2,6,7,8,9,3,-1,1,10};
     int min_element = recursive_min_element(arr,n,idx);
     printf("%d",min_element);
     return 0;
}

a) 9
b) 10
c) 11
d) 12
View Answer

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

11. What is the output of the following code?

#include
int max_of_two(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int min_of_two(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int recursive_max_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return max_of_two(arr[idx], recursive_max_element(arr, len, idx + 1));
}
int recursive_min_element(int *arr, int len, int idx)
{
      if(idx == len - 1)
      return arr[idx];
      return min_of_two(arr[idx], recursive_min_element(arr, len, idx + 1));
}
int main()
{
     int n = 5, idx = 0, arr[] = {1,1,1,1,1};
     int max_element = recursive_max_element(arr,n,idx);
     int min_element = recursive_min_element(arr,n,idx);
     printf("%d %d",max_element,min_element);
     return 0;
}

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

Answer: a
Clarification: The program prints the values of the largest and the smallest element in the array, which are 1 and 1.

and Answers.

250+ TOP MCQs on Coin Change Problem and Answers

Data Structure Multiple Choice Questions on “Coin Change Problem”.

1. You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________
a) Greedy algorithm
b) Dynamic programming
c) Divide and conquer
d) Backtracking

Answer: b
Clarification: The coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can be found by finding optimal solutions for subproblems). So, dynamic programming can be used to solve the coin change problem.

2. Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?
a) 20
b) 12
c) 6
d) 5

Answer: c
Clarification: Using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}.

3. Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
a) 14
b) 10
c) 6
d) 100

Answer: d
Clarification: Using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}. Similarly, four coins {4,4,1,1} will be selected to make a sum of 10. But, the optimal answer is three coins {4,3,3}. Also, five coins {4,4,4,1,1} will be selected to make a sum of 14. But, the optimal answer is four coins {4,4,3,3}. For a sum of 100, twenty-five coins {all 4’s} will be selected and the optimal answer is also twenty-five coins {all 4’s}.

4. Fill in the blank to complete the code.

#include
int main()
{
      int coins[10]={1,3,4},lookup[100000];
      int i,j,tmp,num_coins = 3,sum=100;
      lookup[0]=0;
      for(i = 1; i <= sum; i++)
      {
	   int min_coins = i;
	   for(j = 0;j < num_coins; j++)
	   {
	        tmp = i - coins[j];
	        if(tmp < 0)
	         continue;
	        if(lookup[tmp] < min_coins)
	       ______________;
	   }
	   lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

a) lookup[tmp] = min_coins
b) min_coins = lookup[tmp]
c) break
d) continue

Answer: b
Clarification: min_coins = lookup[tmp] will complete the code.

5. You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
a) O(N)
b) O(S)
c) O(N2)
d) O(S*N)
Answer: d
Clarification: The time complexity is O(S*N).

6. Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?
a) O(N)
b) O(S)
c) O(N2)
d) O(S*N)

Answer: b
Clarification: To get the optimal solution for a sum S, the optimal solution is found for each sum less than equal to S and each solution is stored. So, the space complexity is O(S).

7. You are given infinite coins of denominations 1, 3, 4. What is the total number of ways in which a sum of 7 can be achieved using these coins if the order of the coins is not important?
a) 4
b) 3
c) 5
d) 6
View Answer

Answer: c
Clarification: A sum of 7 can be achieved in the following ways:
{1,1,1,1,1,1,1}, {1,1,1,1,3}, {1,3,3}, {1,1,1,4}, {3,4}.
Therefore, the sum can be achieved in 5 ways.

8. You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Clarification: A sum of 7 can be achieved by using a minimum of two coins {3,4}.

9. You are given infinite coins of denominations 5, 7, 9. Which of the following sum CANNOT be achieved using these coins?
a) 50
b) 21
c) 13
d) 23

Answer: c
Clarification: One way to achieve a sum of 50 is to use ten coins of 5. A sum of 21 can be achieved by using three coins of 7. One way to achieve a sum of 23 is to use two coins of 7 and one coin of 9. A sum of 13 cannot be achieved.

10. You are given infinite coins of denominations 3, 5, 7. Which of the following sum CANNOT be achieved using these coins?
a) 15
b) 16
c) 17
d) 4

Answer: d
Clarification: Sums can be achieved as follows:
15 = {5,5,5}
16 = {3,3,5,5}
17 = {3,7,7}
we can’t achieve for sum=4 because our available denominations are 3,5,7 and sum of any two denominations is greater than 4.

11. What is the output of the following program?

#include
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=10;
      lookup[0]=0;
      for(i=1;i<=sum;i++)
      {
	    int min_coins = i;
	    for(j=0;j<num_coins;j++)
	    {
	         tmp=i-coins[j];
	         if(tmp<0)
	          continue;
	         if(lookup[tmp] < min_coins)
		 min_coins=lookup[tmp];
	    }
	    lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

a) 2
b) 3
c) 4
d) 5
Answer: b
Clarification: The program prints the minimum number of coins required to get a sum of 10, which is 3.

12. What is the output of the following program?

#include
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=14;
      lookup[0]=0;
      for(i=1;i<=sum;i++)
      {
	   int min_coins = i;
	   for(j=0;j<num_coins;j++)
	   { 
	         tmp=i-coins[j];
	         if(tmp<0)
		  continue;
	         if(lookup[tmp] < min_coins)
		 min_coins=lookup[tmp];
	   }
	   lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

a) 2
b) 3
c) 4
d) 5
Answer: c
Clarification: The program prints the minimum number of coins required to get a sum of 14, which is 4.

and Answers.