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

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

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

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

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

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```

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

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

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;
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```
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;
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;
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;
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;
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;
}```