Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ’s – Generating Partitions

1 - Question

What is meant by integer partition?
a) representing an integer as sum of positive and negative real numbers
b) representing an integer as sum of positive and negative integers
c) representing an integer as sum of positive integers
d) representing an integer as sum of positive real numbers
View Answer

Answer: c
Explanation: Integer partition is the way of representing an integer as sum of positive integers. Partitions differing only in their order are considered to be same.


2 - Question

 How many partitions will be formed for the integer 3?
a) 2
b) 3
c) 4
d) 8
View Answer

Answer: b
Explanation: We need to find the combinations of positive integers which give 3 as their sum. These will be {3}, {2,1}, {1,1,1}. Thus the correct answer is 3.


3 - Question

What is meant by number theory?
a) study of integers
b) study of complex numbers
c) numerology
d) theory of origination of mathematics
View Answer

Answer: a
Explanation: Number theory is a branch of mathematics that deals with the study of integers. Partitioning of a number comes under the study of number theory.


4 - Question

Which of the following is true according to Ramanujan’s congruence?
a) No. of partitions are divisible by 5 for a number 3 more than a multiple of 5
b) No. of partitions are divisible by 5 for a number 4 more than a multiple of 5
c) No. of partitions are divisible by 5 for a number 2 more than a multiple of 5
d) No. of partitions are divisible by 5 for a number 1 more than a multiple of 5
View Answer

Answer: b
Explanation: Ramanujan’s congruence are some relations found for the no. of partitions of an integer. According to it, the number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5.


5 - Question

The no. of partitions of which of the following integer will be divisible by 5?
a) 3
b) 5
c) 9
d) 6
View Answer

Answer: c
Explanation: According to Ramanujan’s congruence number of partitions of an integer is divisible by 5 if that integer is 4 more than a multiple of 5. So out of the given options 9 is the only integer which satisfies this condition.


6 - Question

What is the output of the following code?

#include<iostream> 
using namespace std;
void printArray(int p[], int n)
{
	for (int i = 0; i <= n-1; i++)
	cout << p[i] << " ";
	cout << endl;
}
void func1(int n)
{
	int p[n];
	int k = 0;
	p[k] = n;
	while (true)
	{
		printArray(p, k+1);
		int rem_val = 0;
		while (k >= 0 && p[k] == 1)
		{
			rem_val += p[k];
			k--;
		}
		if (k < 0) return;
		p[k]--;
		rem_val++;
		while (rem_val > p[k])
		{
			p[k+1] = p[k];
			rem_val = rem_val - p[k];
			k++;
		}
		p[k+1] = rem_val;
		k++;
	}
}
int main()
{
int n=3;
	func1(n);
return 0;
}

a)

  3
  1 2
  1 1 1

b)

  1 1 1
  2 1
  3

c)

  1 1 1
  1 2
  3

d)

   3
   2 1
   1 1 1
View Answer

Answer: d
Explanation: The given code prints the partition of a number in decreasing order. This code uses the approach of dynamic programming.


7 - Question

 While generating partitions of integer 3 we consider 2 1 and 1 2 to be different partitions.
a) true
b) false
View Answer

Answer: b
Explanation: Partitions differing in order are considered to be same. Thus 2 1 and 1 2 are considered to be same when we generate partitions of integer 3.


8 - Question

What is the approach implemented in the following code?

#include<iostream> 
using namespace std;
void printArray(int p[], int n)
{
	for (int i = 0; i <= n-1; i++)
	cout << p[i] << " ";
	cout << endl;
}
void func1(int n)
{
	int p[n];
	int k = 0;
	p[k] = n;
	while (true)
	{
		printArray(p, k+1);
		int rem_val = 0;
		while (k >= 0 && p[k] == 1)
		{
			rem_val += p[k];
			k--;
		}
		if (k < 0) return;
		p[k]--;
		rem_val++;
		while (rem_val > p[k])
		{
			p[k+1] = p[k];
			rem_val = rem_val - p[k];
			k++;
		}
		p[k+1] = rem_val;
		k++;
	}
}
 
int main()
{
      int n;
      cin>>n;
      func1(n);
      return 0;
}

a) greedy approach
b) dynamic programming
c) recursion(divide and conquer)
d) backtracking
View Answer

Answer: b
Explanation: The given code prints the partition of a number in decreasing order. This code uses the approach of dynamic programming. We can also use recursion for fulfilling the same purpose.


9 - Question

What will be the output of the following code?

#include<iostream>
using namespace std;
int list[200];
void func(int n, int m = 0)
{
    int i;
    if(n == 0)
    {
         for(i = 0; i < m; ++i)
         printf("%d ", list[i]);
         printf("\n");
         return;
    }
    for(i = n; i > 0; --i)
    {
         if(m == 0 || i <= list[m - 1])
         {
             list[m] = i;
             func(n - i, m + 1);
         }
    }
 
}
int main()
{
int n=3;
	func(n,0);
return 0;
}

a)

  3
  2 1
  1 1 1

b)

  1 1 1
  2 1
  3

c)

  1 1 1
  1 2
  3

d)

   3
   1 2
   1 1 1
View Answer
Answer: a
Explanation: The given code prints the partition of a number in decreasing order. This code uses the approach of recursion. The same purpose can be fulfilled by using dynamic programming.


10 - Question

Which of the following correctly represents the code to print partitions of a number?
a)

#include<iostream>
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{
 
	if(n==0)
        {
for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
for(int i=k;i>0;i--)
        {
if(i>n)continue;
		print[idx]=i;
		partitn(n-i,i,idx+1);
}
}
int main()
{
int n;
	cin>>n;
	partitn(n,n,0);
return 0;
}

b)

#include<iostream>
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{
	if(n==0)
        {
for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
for(int i=k;i>0;i--)
        {
if(i>n)continue;
		print[idx]=i;
		partitn(n-i,i,idx+1);
}
}
int main()
{
int n;
	cin>>n;
	partitn(n,0,0);
return 0;
}

c)

#include<iostream>
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{
	if(n==0)
        {
for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
for(int i=k;i>0;i--)
        {
		print[idx]=i;
		partitn(n-i,i,idx+1);
}
}
int main()
{
int n;
	cin>>n;
	partitn(n,0,0);
return 0;
}

d)

#include<iostream>
using namespace std;
int print[200];
void partitn(int n,int k,int idx)
{
	if(n==0)
        {
for(int i=0;i<idx;i++)
			cout<<print[i]<<" ";
		cout<<endl;
	        return ;
        }
for(int i=k;i>0;i--)
        {
		print[idx]=i;
		partitn(n-i,i,idx+1);
}
}
int main()
{
int n;
	cin>>n;
	partitn(n,n,0);
return 0;
}
View Answer

Answer: a
Explanation: In the correct code we need to pass n as second argument in the function partitn() and need to check for the condition i>n. The code prints the partitions in decreasing order.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners