This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Generating Subsets”.
1. What is meant by the power set of a set?
a) subset of all sets
b) set of all subsets
c) set of particular subsets
d) empty set
View Answer
Explanation: Power set of a set is defined as the set of all subsets. Ex- S={1,2} then P={{},{1},{2}{1,2}}.
2. Number of elements in the power set of set S={1,2,3} will be?
a) 2
b) 4
c) 6
d) 8
View Answer
Explanation: Power set of a set is defined as the set of all subsets. Number of elements in the power set of a set having n elements is given as 2n. Thus, here number of elements will be 23=8.
3. Number of elements in the power set of set S={1,2,2} will be?
a) 2
b) 4
c) 6
d) 8
View Answer
Explanation: For finding the number of elements in the power set of the given set we need to remove duplicates. So we will be left with 6 unique elements which will be P={{},{1},{2},{1,2},{2,2},{1,2,2}}.
4. Choose the correct statement for the following code segment?
bool check (int N) { if( N & (1 << i) ) return true; else return false; }
a) function returns true if N is odd
b) function returns true if N is even
c) function returns true if ith bit of N is set
d) function returns false if ith bit of N is set
View Answer
Explanation: As the value of 1 << i is 2i so the given function checks whether the ith bit of N is set or not. If it is set then the function returns true.
5. What will be the output for the following code?
#include <stdio.h> #include <math.h> void PowerSet(char *set, int set_size) { unsigned int pow_size = pow(2, set_size); int count, j; for(count = 0; count < pow_size; count++) { for(j = 0; j < set_size; j++) { if(count & (1<<j)) printf("%c", set[j]); } printf(","); } } int main() { char strset[] = {'a','b','c'}; PowerSet(strset, 3); return 0; }
a) a,b,ab,c,ac,bc,abc,
b) a,b,ab,c,ac,bc,abc
c) ,a,b,ab,c,ac,bc,abc,
d) ,abc,bc,ac,c,ab,b,a,
View Answer
Explanation: The given code prints the elements of power set of the given set strset[]. It uses binary counter of appropriate length in order to print corresponding subsets of the given set.
6. What will be the time complexity of the following code?
#include <stdio.h> #include <math.h> void PowerSet(char *set, int set_size) { unsigned int pow_size = pow(2, set_size); int count, j; for(count = 0; count < pow_size; count++) { for(j = 0; j < set_size; j++) { if(count & (1<<j)) printf("%c", set[j]); } printf(","); } } int main() { char strset[] = {'a','b','c'}; PowerSet(strset, 3); return 0; }
a) O(n 2n)
b) O(n2)
c) O(n log n)
d) O(2n) (n is the size of set)
View Answer
Explanation: In the given code we have a nested for loop. In this loop the outer loop runs 2n times and the inner loop runs n times. So the overall time complexity becomes n2n.
7. What will be the auxiliary space requirement of the following code?
#include <stdio.h> #include <math.h> void PowerSet(char *set, int set_size) { unsigned int pow_size = pow(2, set_size); int count, j; for(count = 0; count < pow_size; count++) { for(j = 0; j < set_size; j++) { if(count & (1<<j)) printf("%c", set[j]); } printf(","); } } int main() { char strset[] = {'a','b','c'}; PowerSet(strset, 3); return 0; }
a) O(n)
b) O(1)
c) O(n log n)
d) O(2n) (n is the size of set)
View Answer
Explanation: The given code prints the elements of power set of the given set strset[]. As this code does not require any extra space for generating the output so its auxiliary space requirement will be O(1).
8. Which of the following code prints the power set of a given set?
a)
#include<iostream> using namespace std; void Set(string str, int index = 0, string curr = "") { int n = str.size(); if (index == n) { cout << curr << endl; return; } Set(str, index , curr + str[index]); Set(str, index + 1, curr); } int main() { string str = "ab"; Set(str); return 0; }
b)
#include<iostream> using namespace std; void Set(string str, int index = 0, string curr = "") { int n = str.size(); if (index == n) { cout << curr << endl; return; } Set(str, index + 1, curr + str[index]); Set(str, index , curr); } int main() { string str = "ab"; Set(str); return 0; }
c)
#include<iostream> using namespace std; void Set(string str, int index = 0, string curr = "") { int n = str.size(); if (index == n) { cout << curr << endl; return; } Set(str, index + 1, curr + str[index]); Set(str, index + 1, curr); } int main() { string str = "ab"; Set(str); return 0; }
d)
#include<iostream> using namespace std; void Set(string str, int index = 0, string curr = "") { int n = str.size(); if (index == n) { cout << curr << endl; return; } Set(str, index , curr+str); Set(str, index + 1, curr); } int main() { string str = "ab"; Set(str); return 0; }
Explanation: In the correct version we are taking two cases for each element. In the first case the element is included in the subset and in the second case it is not included. So in this manner, we find all the subsets of the given set.
9. The number of elements in the power set increases when there are duplicates present in the set.
a) True
b) False
View Answer
Explanation: In case when duplicates are present in the set then the number of elements in the power set decreases. It is because we remove subsets with identical elements.
10. What of the following code prints the power set of a given set?
a)
#include <bits/stdc++.h> using namespace std; void Set(string str, int ind = -1, string curr = "") { int n = str.size(); if (ind == n) return; cout << curr << ","; for (int i = ind+ 1; i < n; i++) { curr += str[i]; Set(str, i, curr); curr.erase(curr.size() - 1); } return; } int main() { string str = "abc"; Set(str); return 0; }
b)
#include <bits/stdc++.h> using namespace std; void Set(string str, int ind = -1, string curr = "") { int n = str.size(); if (ind == 0) return; cout << curr << ","; for (int i = ind+ 1; i < n; i++) { curr += str[i]; Set(str, i, curr); curr.erase(curr.size() - 1); } return; } int main() { string str = "abc"; Set(str); return 0; }
c)
#include <bits/stdc++.h> using namespace std; void Set(string str, int ind = -1, string curr = "") { int n = str.size(); if (ind == n) return; cout << curr << ","; for (int i = ind+ 1; i < n; i++) { curr += str[i]; Set(str, i, curr); curr.erase(curr.size() -2); } return; } int main() { string str = "abc"; Set(str); return 0; }
d)
#include <bits/stdc++.h> using namespace std; void Set(string str, int ind = -1, string curr = "") { int n = str.size(); if (ind == n) return; cout << str << ","; for (int i = ind+ 1; i < n; i++) { curr += str[i]; Set(str, i, curr); curr.erase(curr.size() - 1); } return; } int main() { string str = "abc"; Set(str); return 0; }
Explanation: In the correct version of the code we are fixing a prefix and generate all corresponding subsets. Then after all subsets with a prefix are generated, we replace last character with one of the remaining character.
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.
- Check Design and Analysis of Algorithms Books
- Apply for Computer Science Internship
- Practice Programming MCQs
- Check Programming Books
- Practice Computer Science MCQs