My Report (&Account)

Generating Combinations Test


Correct Answer: 2 points | Wrong: -1 point
Grades: A* (100% score) | A (80%-99%) | B (60%-80%) | C (40%-60%) | D (0%-40%)
advertisement

1. What is the name given to the algorithm depicted in the pseudo code below?

procedure generate(n : integer, Arr : array):
    if n = 1 then
          output(Arr)
    else
        for i = 0; i <= n - 2; i ++ do
            generate(n - 1, Arr)
            if n is even then
                swap(Arr[i], Arr[n-1])
            else
                swap(Arr[0], Arr[n-1])
            end if
        end for
        generate(n - 1, Arr )
    end if

2. What will be the output of the following code?

#include <iostream>
#include<string>
using namespace std;
void func1(string input,string output)
{
    if(input.length()==0)
    {
        cout<<output<<",";
        return;
    }
    for(int i=0;i<=output.length();i++)
    func1(input.substr(1),output.substr(0,i) + input[0] + output.substr(i));
}

int main()
{
    char str[] = "AB";

	func1(str, "");
    return 0;
}

3. What will be the output of the following code?

#include <stdio.h> 
#include <string.h> 
#include<iostream>
using namespace std;
void swap(char *x, char *y) 
{ 
	char temp; 
	temp = *x; 
	*x = *y; 
	*y = temp; 
} 

void func(char *a, int l, int r) 
{ 
int i; 
if (l == r) 
	cout<<a<<” ,”; 
else
{ 
	for (i = l; i <= r; i++) 
	{ 
		swap((a+l), (a+i)); 
		func(a, l+1, r); 
		swap((a+l), (a+i)); 
	} 
} 
} 

int main() 
{ 
	char str[] = "AA"; 
	int n = strlen(str); 
	func(str, 0, n-1); 
	return 0; 
} 

4. What will be the output for following code?

#include <stdio.h> 
#include <string.h> 
#include<iostream>
using namespace std;
void swap(char *x, char *y) 
{ 
	char temp; 
	temp = *x; 
	*x = *y; 
	*y = temp; 
} 

void func(char *a, int l, int r) 
{ 
int i; 
if (l == r) 
	cout<<a<<” ,”; 
else
{ 
	for (i = l; i <= r; i++) 
	{ 
		swap((a+l), (a+i)); 
		func(a, l+1, r); 
		swap((a+l), (a+i)); 
	} 
} 
} 

int main() 
{ 
	char str[] = "AB"; 
	int n = strlen(str); 
	func(str, 0, n-1); 
	return 0; 
} 

5. How many permutations will be formed from the array arr={1,2,3}?

6. What will be the time complexity of the given code?

#include <stdio.h> 
#include <string.h> 
#include<iostream>
using namespace std;
void swap(char *x, char *y) 
{ 
	char temp; 
	temp = *x; 
	*x = *y; 
	*y = temp; 
} 

void func(char *a, int l, int r) 
{ 
int i; 
if (l == r) 
	cout<<a<<” ,”; 
else
{ 
	for (i = l; i <= r; i++) 
	{ 
		swap((a+l), (a+i)); 
		func(a, l+1, r); 
		swap((a+l), (a+i)); 
	} 
} 
} 

int main() 
{ 
	char str[] = "AB"; 
	int n = strlen(str); 
	func(str, 0, n-1); 
	return 0; 
} 

7. The dictionary ordering of elements is known as?

8. What will be the output of the code that generates permutations and also has the ability to handle duplicates, for the input str[]=”AA”?

9. Heap’s algorithm requires an auxiliary array to create permutations.

10. What is the time complexity of Heap’s algorithm?


 

Start practicing “1000 MCQs on DAA”, and once you are ready, you can take tests on all topics by attempting our “DAA Test Series”.

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.