250+ TOP MCQs on Generating Subsets and Answers

Data Structures & Algorithms Multiple Choice Questions 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

Answer: b
Clarification: 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

Answer: d
Clarification: 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

Answer: c
Clarification: 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

Answer: c
Clarification: 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  
#include  
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

Answer: c
Clarification: 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  
#include  
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)

Answer: a
Clarification: 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  
#include  
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

Answer: b
Clarification: 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
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
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
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
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; 
}

Answer: c
Clarification: 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

Answer: b
Clarification: 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  
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  
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  
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  
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; 
}

Answer: a
Clarification: 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.

 
 

Leave a Reply

Your email address will not be published. Required fields are marked *