Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Substring Searching Algorithm”.

1. Which of the following is a sub string of “”?
a) SANO
b) FOUND
c) SAND
d) FOND
Answer: b
Clarification: A sub string is a subset of another string. So “FOUND” is the only possible sub string out of the given options.

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

#include 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: The given code describes the naive method of finding a pattern in a string. So the output will be 3 as the given sub string begins at that index in the pattern.

3. What will be the worst case time complexity of the following code?

#include 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

a) O(n)
b) O(m)
c) O(m * n)
d) O(m + n)

Answer: c
Clarification: The given code describes the naive method of pattern searching. By observing the nested loop in the code we can say that the time complexity of the loop is O(m*n).

4. What will be the auxiliary space complexity of the following code?

#include 
using namespace std; 
 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

a) O(n)
b) O(1)
c) O(log n)
d) O(m)

Answer: b
Clarification: The given code describes the naive method of pattern searching. Its auxiliary space requirement is O(1).

5. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n)
b) O(n*m)
c) O(m)
d) O(log n)

Answer: c
Clarification: KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.

6. What will be the best case time complexity of the following code?

#include 
using namespace std; 
void func(char* str2, char* str1) 
{ 
	int m = strlen(str2); 
	int n = strlen(str1); 
 
	for (int i = 0; i <= n - m; i++) 
        { 
		int j; 
 
 
		for (j = 0; j < m; j++) 
			if (str1[i + j] != str2[j]) 
				break; 
 
		if (j == m) 
			cout << i << endl; 
	} 
} 
 
int main() 
{ 
	char str1[] = "1253234"; 
	char str2[] = "323"; 
	func(str2, str1); 
	return 0; 
}

a) O(n)
b) O(m)
c) O(m * n)
d) O(m + n)

Answer: b
Clarification: The given code describes the naive method of pattern searching. The best case of the code occurs when the first character of the pattern does not appear in the text at all. So in such a case, only one iteration is required thus time complexity will be O(m).

7. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n + m)
b) O(m)
c) O(n)
d) O(m * n)

Answer: a
Clarification: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n) where m is the length of text and n is the length of the pattern.

8. What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n + m)
b) O(m)
c) O(n)
d) O(m * n)

Answer: b
Clarification: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for maintaining Z array.

9. The naive pattern searching algorithm is an in place algorithm.
a) true
b) false

Answer: a
Clarification: The auxiliary space complexity required by naive pattern searching algorithm is O(1). So it qualifies as an in place algorithm.

10. Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
a) true
b) false

Answer: a
Clarification: The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp and naive pattern searching algorithm have the same worst case time complexity.

Data Structures & Algorithms Multiple Choice Questions on “Heapsort – 2”.

1. Heap sort is an implementation of ____________ using a descending priority queue.
a) insertion sort
b) selection sort
c) bubble sort
d) merge sort

Answer: b
Clarification: Heap sort is an implementation of selection sort using the input array as a heap representing a descending priority queue. Heap sort algorithm is divided into two phase. In first phase the max-heap is created and the second phase (selection phase) deletes the elements from the priority queue using siftdown operation.

2. Which one of the following is false?
a) Heap sort is an in-place algorithm
b) Heap sort has O(nlogn) average case time complexity
c) Heap sort is stable sort
d) Heap sort is a comparison-based sorting algorithm
Answer: c
Clarification: Heap sort is a comparison based sorting algorithm and has time complexity O(nlogn) in the average case. Heap sort is an in-place algorithm as it needs O(1) of auxiliary space. Heap sort uses heap and operations on heap can change the relative order of items with the same key values. Therefore, Heap sort is not a stable sort.

3. The essential part of Heap sort is construction of max-heap. Consider the tree shown below, the node 24 violates the max-heap property. Once heapify procedure is applied to it, which position will it be in?

a) 4
b) 5
c) 8
d) 9

Answer: d
Clarification: In max-heap element at each node is smaller than or equal to the element at its parent node. On applying the heapify procedure on item at position 2, it will be in position 9 as shown below.

4. The descending heap property is ___________
a) A[Parent(i)] = A[i]
b) A[Parent(i)] <= A[i]
c) A[Parent(i)] >= A[i]
d) A[Parent(i)] > 2 * A[i]

Answer: c
Clarification: The max-heap is also known as descending heap. Max-heap of size n is an almost complete binary tree of n nodes such that the element at each node is less than or equal to the element at its parent node.

5. What is its wort case time complexity of Heap sort?
a) O(nlogn)
b) O(n²logn)
c) O(n²)
d) O(n³)
Answer: a
Clarification: In Heap sort, the call to procedure build_Max-heap takes O(n) time and each of O(n) calls to the function max_Heapify takes O(logn) time. So the worst case complexity of Heap sort is O(nlogn).

6. In average case Heap sort is as efficient as the Quick sort.
a) True
b) False
Answer: b
Clarification: Quick sort is more efficient than Heap sort because experiments indicate that Heap sort requires twice as much time as Quick sort for randomly sorted input.

7. Choose the correct option to fill? X so that the code given below implements the Heap sort.

#include <stdio.h> 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
        heapify(arr, n, largest); 
    } 
} 
void heapSort(int arr[], int n) 
{ 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
    for (int i=n-1; i>=0; i--) 
    { 
        X;
        heapify(arr, i, 0); 
    } 
} 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        printf(“%d”,arr[i]);
    printf(“n”);	    
} 
int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    heapSort(arr, n); 
    printf(“Sorted array is n"); 
    printArray(arr, n); 
}

a) swap(arr[0], arr[n])
b) swap(arr[i], arr[n])
c) swap(arr[0], arr[i])
d) swap(arr[i], arr[2*i])

Answer: c
Clarification: Steps in heap sort are : (i) Build the max-heap, (ii) Swap the root element with the last element of the heap, (iii) Reduce the size of heap by 1 and heapify the root element, (iv) Repeat the steps form step number (v) until all the elements are sorted. Therefore the correct option is swap(arr[0], arr[i]).

8. Which one of the following is a variation of Heap sort?
a) Comb sort
b) Smooth sort
c) Binary tree sort
d) Shell sort

Answer: b
Clarification: Smooth sort is a variation of Heap sort. Smooth sort has O(nlogn) worst case time complexity like Heap sort. But Smooth sort takes O(n) time to sort the nearly sorted input array.

9. Introsort algorithm is combination of _____________
a) Quick sort and Heap sort
b) Quick sort and Shell sort
c) Heap sort and Merge sort
d) Heap sort and insertion sort

Answer: a
Clarification: Introsort is a hybrid sorting algorithm that combines Quick sort and Heap sort to retain advantages of both. It has worst case speed of Heap sort and average case speed of Quick sort.

10. How many elements can be sorted in O(logn) time using Heap sort?
a) O(1)
b) O(n/2)
c) O(logn/log(logn))
d) O(logn)
Answer: c
Clarification: The time complexity of Heap sort is O(klogk) for k input elements,
for k = logn/log(logn),
O(klogk) = O(logn/log(logn) * log(logn/log(logn)))
∴ O(klogk) = O(logn/log(logn) * (log(logn) – log(log(logn))))
= O(logn)
Hence the correct option is O(logn/log(logn)).

Data Structures & Algorithms Multiple Choice Questions on “Counting Sort”.

1. How many comparisons will be made to sort the array arr={1,5,3,8,2} using counting sort?
a) 5
b) 7
c) 9
d) 0

Answer: d
Clarification: As counting sort is an example of non comparison sort so it is able to sort an array without making any comparison.

2. Which of the following is not an example of non comparison sort?
a) bubble sort
b) counting sort
c) radix sort
d) bucket sort

Answer: a
Clarification: Bubble sort is not an example of non comparison sort as it needs to compare array elements in order to sort an array.

3. Which of the following sorting techniques is most efficient if the range of input data is not significantly greater than a number of elements to be sorted?
a) selection sort
b) bubble sort
c) counting sort
d) insertion sort
View Answer

Answer: c
Clarification: Time complexity of counting sort is given as O(n+k) where n is the number of input elements and k is the range of input. So if range of input is not significantly larger than number of elements in the array then it proves to be very efficient.

4. What is the auxiliary space requirement of counting sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n+k) k=range of input

Answer: d
Clarification: Counting sort uses two extra arrays to get the input array sorted. First array is required to store the count of all the elements which fall in the range of input data elements, so its size is k. The second array is required to store the input elements in sorted manner, so its size is n. Thus overall auxiliary space required becomes O(n+k).

5. It is not possible to implement counting sort when any of the input element has negative value.
a) True
b) False
View Answer

Answer: b
Clarification: It is possible to extend the counting sort algorithm for negative numbers as well. In such a case we store the minimum element at the 0th index.

6. Which of the following sorting techniques is stable?
a) quick sort
b) counting sort
c) heap sort
d) selection sort
View Answer

Answer: b
Clarification: Counting sort is an example of stable sorting algorithm as the elements with identical values appear in the same order in the output array as they were in the input array.

7. Which of the following uses the largest amount of auxiliary space for sorting?
a) Bubble sort
b) Counting sort
c) Quick sort
d) Heap sort

Answer: b
Clarification: Counting sort requires auxiliary space of O(n+k) whereas quick sort, bubble sort and heap sort are in place sorting techniques. Thus counting sort requires most auxiliary space.

8. What is the average time complexity of counting sort?
a) O(n)
b) O(n+k) k=range of input
c) O(n²)
d) O(n log n)

Answer: b
Clarification: Time complexity of counting sort is O(n+k) as counting the occurrence of each element in the input range takes k time and then finding the correct index value of each element in the sorted array takes n time.

9. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case?
a) quick sort
b) insertion sort
c) counting sort
d) gnome sort

Answer: c
Clarification: The time complexity of counting sort remains unvaried in all the three cases. It is given by O(n+k).

10. Which of the following statement is true about comparison based sorting?
a) counting sort is a comparison based sort
b) any comparison based sorting can be made stable
c) bubble sort is not a comparison based sort
d) any comparison based sort requires at least O(n²) time

Answer: b
Clarification: Any comparison based sorting technique can be made stable by considering a position as criteria while making comparisons.

11. Counting sort is often used as a sub routine for radix sort.
a) true
b) false
View Answer

Answer: a
Clarification: Counting sort is used as a sub routine for radix sort as it is a stable and non comparison based sorting algorithm.

12. What is the advantage of counting sort over quick sort?
a) counting sort has lesser time complexity when range is comparable to number of input elements
b) counting sort has lesser space complexity
c) counting sort is not a comparison based sorting technique
d) it has no advantage

Answer: a
Clarification: Counting sort is very efficient in the cases where range is comparable to number of input elements as it performs sorting in linear time.

13. which of the following represents the algorithm of counting sort correctly?
a)

  function countingSort(array, k) is
  count ← new array of k zeros
  for i = 1 to length(array) do
    count[array[i]] ← count[array[i]] + 1
  for i = 2 to k do
    count[i] ← count[i] + count[i +1]
  for i = length(array) downto 1 do
    output[count[array[i]]] ← array[i]
    count[array[i]] ← count[array[i]] - 1
  return output

b)

  function countingSort(array, k) is
  count ← new array of k zeros
  for i = 1 to length(array) do
    count[array[i]] ← count[array[i]] + 1
  for i = 2 to k do
    count[i] ← count[i] + count[i - 1]
  for i = length(array) downto 1 do
    output[count[array[i]]] ← array[i]
    count[array[i]] ← count[array[i]] - 1
  return output

c)

  function countingSort(array, k) is
  count ← new array of k zeros
  for i = 1 to length(array) do
    count[array[i]] ← count[array[i]] + 1
  for i = 1 to k do
    count[i] ← count[i] + count[i - 1]
  for i = length(array) downto 1 do
    output[count[array[i]]] ← array[i]
    count[array[i]] ← count[array[i]] - 1
  return output

d)

  function countingSort(array, k) is
  count ← new array of k zeros
  for i = 1 to length(array) do
    count[array[i]] ← count[array[i]] + 1
  for i = 2 to k do
    count[i] ← count[i] + count[i + 1]
  for i = length(array) downto 1 do
    output[count[array[i]]] ← array[i]
    count[array[i]] ← count[array[i]] - 1
  return output

Answer: b
Clarification: The first loop counts the number of occurrences of each element. Second loop performs prefix sum on count to determine position range where items having that key should be placed in. The third loop places each element at its correct position.

14. What is the disadvantage of counting sort?
a) counting sort has large time complexity
b) counting sort has large space complexity
c) counting sort is not a comparison based sorting technique
d) counting sort cannot be used for array with non integer elements

Answer: d
Clarification: Counting sort can only be used for arrays with integer elements because otherwise array of frequencies cannot be constructed.

15. Which of the following algorithm takes non linear time for sorting?
a) counting sort
b) quick sort
c) bucket sort
d) radix sort

Answer: b
Clarification: Quick sort requires O(n log n) time for sorting so it takes non linear time for sorting whereas counting sort, bucket sort and radix sort sorts in linear time.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Generating Permutations”.

1. The dictionary ordering of elements is known as?
a) Lexicographical order
b) Colexicographical order
c) Well order
d) Sorting

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

2. How many permutations will be formed from the array arr={1,2,3}?
a) 2
b) 4
c) 6
d) 8

Answer: c
Clarification: No.of permutations for an array of size n will be given by the formula nPn. So for the given problem, we have 3P3=6 or 3!=6.

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

Answer: c
Clarification: The number of permutations for the problem will be 6 according to the formula 3P3. When ordered in lexicographical manner these will be {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}.

4. 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

a) bubble sort
b) heap sort
c) heap’s algorithm
d) prim’s algorithm

Answer: c
Clarification: The given algorithm is called Heap’s algorithm. It is used for generating permutations of a given list.

5. Heap’s algorithm requires an auxiliary array to create permutations.
a) true
b) false
View Answer

Answer: b
Clarification: Heap’s algorithm does not require any extra array for generating permutations. Thus it is able to keep its space requirement to a very low level. This makes it preferable algorithm for generating permutations.

6. What is the time complexity of Heap’s algorithm?
a) O(n log n)
b) O(n²)
c) O(n*n!)
d) O(n!)

Answer: d
Clarification: The recurrence relation for the heap’s algorithm is given by the expression T(n)=n * T(n-1). It is calculated by using substitution method. It is found to be equal to O(n!).

7. What will be the output for following code?

#include  
#include  
#include
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; 
}

a) AB,BA,
b) BA,AB,
c) AB,BA
d) BA,AB,
Answer: a
Clarification: The given code prints the permutations of the an array. So there will be 2 permutations for an array of 2 elements. Note that the comma is printed even for the last permutation.

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

#include  
#include  
#include
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; 
}

a) O(n²)
b) O(n * n!)
c) O(n!)
d) O(n log n)

Answer: b
Clarification: The recurrence relation for the heap’s algorithm is given by the expression T(n)=n * T(n-1). But as each permutations takes n time to be printed so the overall complexity will be O(n*n!).

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

#include 
#include
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;
}

a) AA,BA,
b) AB,BA,
c) BA,AB,
d) AB,AB,

Answer: c
Clarification: The given code prints the permutations of the an array. So there will be 2 permutations for an array of 2 elements. In this code the difference is that BA is printed before AB. Note that the comma is printed even for the last permutation.

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

#include  
#include  
#include
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; 
}

a) AA,
b) AA,AA
c) A,A
d) AA,AA,

Answer: d
Clarification: The given code prints the permutations of the given array but it is not able to handle duplicates due to which it prints 2P2 permutations even in this case. So the output becomes AA,AA,.

11. What will be the output of the code that generates permutations and also has the ability to handle duplicates, for the input str[]=”AA”?
a) AA
b) AA,AA
c) A,A
d) A
Answer: a
Clarification: If a code is able to handle duplicates then the two A’s are not considered to be different elements due to which only one permutation will be formed. So the output will be AA only.

Data Structures & Algorithms Multiple Choice Questions on “Kruskal’s Algorithm”.

1. Kruskal’s algorithm is used to ______
a) find minimum spanning tree
b) find single source shortest path
c) find all pair shortest path algorithm
d) traverse the graph

Answer: a
Clarification: The Kruskal’s algorithm is used to find the minimum spanning tree of the connected graph. It construct the MST by finding the edge having the least possible weight that connects two trees in the forest.

2. Kruskal’s algorithm is a ______
a) divide and conquer algorithm
b) dynamic programming algorithm
c) greedy algorithm
d) approximation algorithm

Answer: c
Clarification: Kruskal’s algorithm uses a greedy algorithm approach to find the MST of the connected weighted graph. In the greedy method, we attempt to find an optimal solution in stages.

3. Consider the given graph.

What is the weight of the minimum spanning tree using the Kruskal’s algorithm?
a) 24
b) 23
c) 15
d) 19

Answer: d
Clarification: Kruskal’s algorithm constructs the minimum spanning tree by constructing by adding the edges to spanning tree one-one by one. The MST for the given graph is,

So, the weight of the MST is 19.

4. What is the time complexity of Kruskal’s algorithm?
a) O(log V)
b) O(E log V)
c) O(E²)
d) O(V log E)
Answer: b
Clarification: Kruskal’s algorithm involves sorting of the edges, which takes O(E logE) time, where E is a number of edges in graph and V is the number of vertices. After sorting, all edges are iterated and union-find algorithm is applied. union-find algorithm requires O(logV) time. So, overall Kruskal’s algorithm requires O(E log V) time.

5. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?

a) GF
b) DE
c) BE
d) BG
View Answer

Answer: c
Clarification: In Krsuskal’s algorithm the edges are selected and added to the spanning tree in increasing order of their weights. Therefore, the first edge selected will be the minimal one. So, correct option is BE.

6. Which of the following edges form minimum spanning tree on the graph using kruskals algorithm?

a) (B-E)(G-E)(E-F)(D-F)
b) (B-E)(G-E)(E-F)(B-G)(D-F)
c) (B-E)(G-E)(E-F)(D-E)
d) (B-E)(G-E)(E-F)(D-F)(D-G)

Answer: a
Clarification: Using Krushkal’s algorithm on the given graph, the generated minimum spanning tree is shown below.

So, the edges in the MST are, (B-E)(G-E)(E-F)(D-F).

7. Which of the following is true?
a) Prim’s algorithm can also be used for disconnected graphs
b) Kruskal’s algorithm can also run on the disconnected graphs
c) Prim’s algorithm is simpler than Kruskal’s algorithm
d) In Kruskal’s sort edges are added to MST in decreasing order of their weights
Answer: b
Clarification: Prim’s algorithm iterates from one node to another, so it can not be applied for disconnected graph. Kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest. Kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm.

8. Which of the following is false about the Kruskal’s algorithm?
a) It is a greedy algorithm
b) It constructs MST by selecting edges in increasing order of their weights
c) It can accept cycles in the MST
d) It uses union-find data structure

Answer: c
Clarification: Kruskal’s algorithm is a greedy algorithm to construct the MST of the given graph. It constructs the MST by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. So, using Kruskal’s algorithm is never formed.

9. Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
a) True
b) False

Answer: b
Clarification: Prim’s algorithm outperforms the Kruskal’s algorithm in case of the dense graphs. It is significantly faster if graph has more edges than the Kruskal’s algorithm.

10. Consider the following statements.
S1. Kruskal’s algorithm might produce a non-minimal spanning tree.
S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
a) S1 is true but S2 is false
b) Both S1 and S2 are false
c) Both S1 and S2 are true
d) S2 is true but S1 is false

Answer: d
Clarification: In Kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components containing a vertex and adds the new edges. And Kruskal’s algorithm always finds the MST for the connected graph.

& Algorithms.

and Answers.

Data Structure Multiple Choice Questions on “Factorial using Recursion”.

1. In general, which of the following methods isn’t used to find the factorial of a number?
a) Recursion
b) Iteration
c) Dynamic programming
d) Non iterative / recursive

Answer: d
Clarification: In general we use recursion, iteration and dynamic programming to find the factorial of a number. We can also implement without using iterative / recursive method by using tgammal() method. Most of us never use it generally.

2. Which of the following recursive formula can be used to find the factorial of a number?
a) fact(n) = n * fact(n)
b) fact(n) = n * fact(n+1)
c) fact(n) = n * fact(n-1)
d) fact(n) = n * fact(1)

Answer: c
Clarification: fact(n) = n * fact(n – 1) can be used to find the factorial of a number.

3. Consider the following iterative implementation to find the factorial of a number. Which of the lines should be inserted to complete the below code?

int main()
{
    int n = 6, i;
    int fact = 1;
    for(i=1;i<=n;i++)
      _________;
    printf("%d",fact);
    return 0;
}

a) fact = fact + i
b) fact = fact * i
c) i = i * fact
d) i = i + fact
Answer: b
Clarification: The line “fact = fact * i” should be inserted to complete the above code.

4. Consider the following recursive implementation to find the factorial of a number. Which of the lines should be inserted to complete the below code?

int fact(int n)
{
     if(_________)
        return 1;
     return n * fact(n - 1);
}
int main()
{
      int n = 5;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

a) n = 0
b) n != 0
c) n == 0
d) n == 1

Answer: c
Clarification: The line “n == 0” should be inserted to complete the above code.
Note: “n == 1” cannot be used because it does not take care of the case when n = 0, i.e when we want to find the factorial of 0.

5. The time complexity of the following recursive implementation to find the factorial of a number is ________

int fact(int n)
{
     if(_________)
        return 1;
     return n * fact(n - 1);
}
int main()
{
      int n = 5;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)

Answer: b
Clarification: The time complexity of the above recursive implementation to find the factorial of a number is O(n).

6. What is the space complexity of the following recursive implementation to find the factorial of a number?

int fact(int n)
{
     if(_________)
        return 1;
     return n * fact(n - 1);
}
int main()
{
      int n = 5;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
View Answer

Answer: a
Clarification: The space complexity of the above recursive implementation to find the factorial of a number is O(1).

7. Consider the following recursive implementation to find the factorial of a number. Which of the lines is the base case?

int fact(int n)
{
     if(n == 0)
        return 1;
     return n * fact(n - 1);
}
int main()
{
      int n = 5;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

a) return 1
b) return n * fact(n-1)
c) if(n == 0)
d) if(n == 1)
View Answer

Answer: c
Clarification: The line “if(n == 0)” is the base case.

8. What is the output of the following code?

int fact(int n)
{
      if(n == 0)
        return 1;
      return n * fact(n - 1);
}
int main()
{
      int n = 0;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

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

Answer: b
Clarification: The program prints 0!, which is 1.

9. What is the output of the following code?

int fact(int n)
{
      if(n == 0)
        return 1;
      return n * fact(n - 1);
}
int main()
{
      int n = 1;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

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

Answer: b
Clarification: The program prints 1!, which is 1.

10. How many times will the function fact() be called when the following code is executed?

int fact(int n)
{
      if(n == 0)
        return 1;
      return n * fact(n - 1);
}
int main()
{
      int n = 5;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

a) 4
b) 5
c) 6
d) 7
View Answer

Answer: c
Clarification: The fact() function will be called 6 times with the following arguments:
fact(5), fact(4), fact(3), fact(2), fact(1), fact(0).

11. What is the output of the following code?

int fact(int n)
{
      if(n == 0)
        return 1;
      return n * fact(n - 1);
}
int main()
{
      int n = 5;
      int ans = fact(n);
      printf("%d",ans);
      return 0;
}

a) 24
b) 120
c) 720
d) 1

Answer: b
Clarification: The function prints 5!, which is 120.

complete set of 1000+