This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Generating Partitions”.
1. 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
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. How many partitions will be formed for the integer 3?
a) 2
b) 3
c) 4
d) 8
View Answer
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. 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
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. 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
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. 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
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. 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 1View Answer
Explanation: The given code prints the partition of a number in decreasing order. This code uses the approach of dynamic programming.
7. While generating partitions of integer 3 we consider 2 1 and 1 2 to be different partitions.
a) true
b) false
View Answer
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. 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
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. 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 1View Answer
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. 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; }
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.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Programming MCQs
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
