Data Structure Questions and Answers – Generating Combinations

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Generating Combinations”.

1. What is meant by the term lexicographical order?
a) dictionary ordering of elements
b) reverse dictionary ordering of elements
c) to sort according to value of first element
d) to sort according to value of last element
View Answer

Answer: a
Explanation: Lexicographical order is also known as dictionary order. It is a generalized method of the way words are alphabetically ordered in a dictionary.
advertisement

2. How many combinations of 2 elements will be formed from the array arr={1,2,3}?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: c
Explanation: No.of combinations of r elements for an array of size n will be given by the formula nCr. So for the given problem, we have 3C2=3.

3. What will be the lexicographical order of combinations of 2 elements each formed from the array arr={1,2,3}?
a) {{2,1},{3,2},{3,1}}
b) {{1,2},{2,3},{1,3}}
c) {{1,2},{1,3},{2,3}}
d) {{2,1},{3,1},{3,2}}
View Answer

Answer: c
Explanation: The number of combinations for the problem will be 3 according to the formula 3C2. When ordered in lexicographical manner these will be {{1,2},{1,3},{2,3}}.

4. What will be the auxiliary space requirement (excluding call stack) of the program to print combinations of r elements each from array of size n?
a) O(n*r)
b) O(n/r)
c) O(n)
d) O(r)
View Answer

Answer: d
Explanation: Code to print combinations will require an auxiliary space of O(r) other than call stack memory. This memory is required by an array that is used for storing combinations formed.

5. The code for printing combinations is in-place.
a) true
b) false
View Answer

Answer: b
Explanation: Code to print combinations will require an auxiliary space of O(r) other than call stack memory. So it is not an in-place algorithm.

6. What will be the time complexity of the code to print combinations?
a) O(n)
b) O(n2)
c) O(n log n)
d) O(2n)
View Answer

Answer: d
Explanation: The recurrence relation of the code to print combinations will be T(n)=2T(n-1)+k. It is found to be equal to O(2n).

7. What will be the output for the following code?

advertisement
#include<stdio.h> 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index+1, aux, i+1); 
	combination(arr, n, r, index, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

a) 1 2, 1 2, 2 2
b) 1 2, 1 2, 2 2 ,
c) 1 2, 2 1, 2 2 ,
d) 1 2, 2 1, 2 2
View Answer

Answer: b
Explanation: The given code prints the combinations of the given array in lexicographical order.The given code considers the duplicate 2s as different entities.Note that the comma is printed even for the last combination.

8. Which of the following code prints the combinations of a given array?
a)

#include <stdio.h> 
void combination(int arr[], int aux[], int start, int end, int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index <= r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end && end-i+1 >= r-index; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
}  
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

b)

#include <stdio.h> 
void combination(int arr[], int aux[], int start, int end, 
					int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end && end-i+1 >= r-index; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
} 
 
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

c)

advertisement
#include <stdio.h> 
void combination(int arr[], int aux[], int start, int end, 
					int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end ; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
} 
 
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

d)

#include <stdio.h> 
void combination(int arr[], int aux[], int start, int end, 
					int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, 
					int index, int r) 
{ 	
	if (index <= r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 
	for (int i=start; i<=end; i++) 
	{ 
		aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
} 
 
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}
View Answer
Answer: b
Explanation: In the code we start from first index (index = 0) in array aux and one by one fix elements at this index and recur for remaining indexes. Finally, when index becomes equal to r we print the combination.
 
 

9. Which of the following code prints the combinations of a given array?
a)

#include<stdio.h> 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index+1, aux, i+1); 
	combination(arr, n, r, index, aux, i+1); 
} 
 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

b)

#include<stdio.h> 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index+1, aux, i+1); 
	combination(arr, n, r, index+1, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

c)

advertisement
#include<stdio.h> 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index-1, aux, i+1); 
	combination(arr, n, r, index, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}

d)

#include<stdio.h> 
void combination(int arr[],int n,int r,int index,int aux[],int i); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
	combination(arr, n, r, 0, aux, 0); 
} 
void combination(int arr[], int n, int r, int index, int aux[], int i) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ",aux[j]); 
		printf(", "); 
		return; 
	} 
	if (i >= n) 
		return; 
	aux[index] = arr[i]; 
	combination(arr, n, r, index, aux, i+1); 
	combination(arr, n, r, index+1, aux, i+1); 
} 
int main() 
{ 
	int arr[] = {1, 2,2}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
	return 0; 
}
View Answer
Answer: a
Explanation: In this method we consider each method one by one and recur for two cases.In first case we include that element in our array and in second case we don’t .When the number of elements in the array aux[] becomes equal to r then we print that combination.
 
 

10. What will be the output for the following code?

#include <stdio.h> 
void combination(int arr[], int aux[], int start, int end, int index, int r); 
void print(int arr[], int n, int r) 
{ 	
	int aux[r]; 
        combination(arr, aux, 0, n-1, 0, r); 
}
void combination(int arr[], int aux[], int start, int end, int index, int r) 
{ 	
	if (index == r) 
	{ 
		for (int j=0; j<r; j++) 
			printf("%d ", aux[j]); 
		printf(", "); 
		return; 
	} 	
	for (int i=start; i<=end && end-i+1 >= r-index; i++) 
	{   aux[index] = arr[i]; 
		combination(arr, aux, i+1, end, index+1, r); 
	} 
}  
int main() 
{ 
	int arr[] = {1, 2, 3}; 
	int r = 2; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	print(arr, n, r); 
}

a) 1 2, 1 3, 2 3
b) 1 3,1 2,2 3,
c) 1 2, 1 3, 2 3,
d) 1 2,1 3,2 3,
View Answer

Answer: c
Explanation: The given code prints the combinations of the given array in lexicographical order.Note that the comma is printed even for the last combination.

11. What will be the output for the following code?

#include <stdio.h>
#include <stdlib.h>
void combination(int arr[], int aux[], int start, int end, int index, int r);
int compare (const void * a, const void * b)
{  return ( *(int*)a - *(int*)b );  }
void print(int arr[], int n, int r)
{
    int aux[r];
    qsort (arr, n, sizeof(int), compare);    
    combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end, int index, int r)
{
    if (index == r)
    {
        for (int i=0; i<r; i++)
            printf("%d " ,aux[i]);
        printf(", ");
        return;
    }    
    for (int i=start; i<=end && end-i+1 >= r-index; i++)
    {
        aux[index] = arr[i];
        combination(arr, aux, i+1, end, index+1, r);
        while (arr[i] == arr[i+1])
             i++;
    }
}
int main()
{
    int arr[] = {1, 2, 2};
    int r = 2;
    int n = sizeof(arr)/sizeof(arr[0]);
    print(arr, n, r);
}

a) 1 2, 1 2,2 2,
b) 1 2, 2 1, 2 2,
c) 1 2, 2 2,
d) 1 2, 2 2, 2 1,
View Answer

Answer: c
Explanation:The given code prints combination of the elements of a given array.But the difference here is that this code also handles duplicate elements due to which we get only 2 combinations instead of 3.

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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn