Category: Data Structures & Algorithms Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Bottom-Up Mergesort”.

1. Merge sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming

Answer: c
Clarification: Merge sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two halves and applies merge sort algorithm to each half individually after which the sorted versions of these halves are merged together.

2. What is the average case time complexity of standard merge sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)

Answer: a
Clarification: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. This can be solved using master’s theorem and is found equal to O(n log n).

3. What is the auxiliary space complexity of standard merge sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)

Answer: c
Clarification: The merging of two sorted arrays requires an additional space of n due to which the auxiliary space requirement of merge sort is O(n). Thus merge sort is not an in place sorting algorithm.

4. What is the auxiliary space complexity of bottom up merge sort?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: b
Clarification: The auxiliary space complexity of bottom up merge sort is same as standard merge sort as both uses the same algorithm for merging the sorted arrays which takes o(n) space. But bottom up merge sort does not need to maintain a call stack.

5. What is the average time complexity of bottom up merge sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)

Answer: a
Clarification: The merge function in the bottom up merge sort takes O(n) time which is placed inside the for loop. The loop runs for O(log n) time, thus the overall time complexity of the code becomes O(n log n).

6. Merge sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging

Answer: a
Clarification: Merge sort implements sorting by merging the sorted versions of smaller parts of the array. Thus its method of sorting is called merging.

7. Bottom up merge sort uses recursion.
a) true
b) false

Answer: b
Clarification: Bottom up merge sort uses the iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on.

8. Bottom up merge sort is a stable sort.
a) true
b) false
Answer: a
Clarification: Bottom up merge sort like standard merge sort is a stable sort. This implies that the relative position of equal valued elements in the input and sorted array remain same.

9. Choose the correct statement about bottom up merge sort from the following?
a) bottom up merge sort has greater time complexity than standard merge sort
b) bottom up merge sort has lesser time complexity than standard merge sort
c) bottom up merge sort saves auxiliary space required on call stack
d) bottom up merge sort uses recursion.
Answer: c
Clarification: Bottom up merge sort unlike standard merge sort uses an iterative algorithm for sorting. Thus, it saves auxiliary space required by the call stack.

10. Choose the correct option from the following that represents bottom up merge sort function?
a)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);		
			merge(Arr, temp, left, mid, right);
		}
	}
}

b)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

c)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

d)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

View Answer

Answer: a
Clarification: Bottom up merge sort uses iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on. The process of merging the sorted arrays is same as in standard merge sort.

and Answers.

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

1. Which one of the following sorting algorithm requires recursion?
a) pigeonhole sort
b) strand sort
c) insertion sort
d) counting sort
Answer: b
Clarification: Strand sort requires the use of recursion for implementing its algorithm. On the other hand, the sorting algorithms given in the remaining options use iterative methods.

2. Strand sort is most efficient for data stored in?
a) linked list
b) arrays
c) trees
d) graphs
Answer: a
Clarification: Strand sort is most efficient when data is stored in a linked list as it involves many insertions and deletions which is performed quite efficiently with the help of a linked list. Using an array would increase time complexity significantly.

3. In which of the following case strand sort is most efficient?
a) when input array is already sorted
b) when input array is reverse sorted
c) when input array is large
d) when input array is has randomly spread elements

Answer: a
Clarification: The best case of strand sort occurs when the input array is already sorted. In this case, it has linear time complexity.

4. What is the auxiliary space complexity of strand sort?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)

Answer: a
Clarification: The auxiliary space complexity of strand sort is O(n). It is because a sub-list of size n has to be maintained.

5. Which of the following sorting algorithm is not in place?
a) quick sort
b) strand sort
c) cycle sort
d) heap sort

Answer: b
Clarification: Strand sort has an auxiliary space complexity of O(n). So it is not an in place sorting algorithm.

6. Strand sort is a comparison based sorting algorithm.
a) true
b) false
Answer: a
Clarification: Pigeonhole sort is an example of a comparison based sorting algorithm. This is because it compares the value of elements present in a list in order to sort them.

7. Strand sort is a stable sorting algorithm.
a) true
b) false

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

8. What is the average time complexity of strand sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n² log n)

Answer: c
Clarification: Average case time complexity of strand sort is O(n2). So it is not as efficient as quick sort or merge sort.

9. What is the best case time complexity of strand sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n² log n)

Answer: a
Clarification: Best case time complexity of strand sort is O(n). It occurs in the case where the input array is already sorted.

10. What is the worst case time complexity of strand sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(n² log n)

Answer: c
Clarification: Worst case time complexity of strand sort is O(n²). It occurs in the case where the input array is in reverse sorted order.

11. Strand sort algorithm used which of the following method for sorting a list?
a) merging
b) selection
c) insertion
d) partitioning

Answer: b
Clarification: Strand sort uses the method of selection for sorting any given list. This is because it selects the strands of elements from the input list which are sorted.

12. Which of the following is an adaptive sorting algorithm?
a) heap sort
b) strand sort
c) selection sort
d) merge sort

Answer: b
Clarification: Strand sort is an adaptive sorting algorithm. This is because it gives a better performance when the input list is almost sorted.

and Answers.

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

1. Which of the following is an advantage of recursive bubble sort over its iterative version?
a) it has better time complexity
b) it has better space complexity
c) it is easy to implement
d) it has no significant advantage

Answer: d
Clarification: Recursive bubble sort has no significant advantage over iterative bubble sort. It is just a different way to implement the same.

2. Bubble sort is also known as ___________
a) stupid sort
b) ship sort
c) sinking sort
d) shell sort

Answer: c
Clarification: Bubble sort is also referred to as sinking sort. It continuously compares the value of adjacent elements as it traverses through an array and swaps the elements which are out of order.

3. What will be the recurrence relation of the code of recursive bubble sort?
a) T(n) = 2T(n/2) + n
b) T(n) = 2T(n/2) + c
c) T(n) = T(n-1) + n
d) T(n) = T(n-1) + c
Answer: c
Clarification: The recurrence relation of the code of recursive bubble sort is T(n) = T(n-1) + n. It can be solved by the method of substitution and is found to be equal to n².

4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Bubble sort
d) Heap sort
Answer: c
Clarification: Out of the given options bubble sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.

5. Which of the following is a variation of bubble sort?
a) selection sort
b) odd even sort
c) cocktail sort
d) stupid sort

Answer: b
Clarification: Odd even sort is a variation of bubble sort. But unlike bubble sort, odd even sort traverses the array in two phases- odd phase and even phase.

6. Recursive bubble sort is a comparison based sort.
a) true
b) false
View Answer

Answer: a
Clarification: In bubble sort, we need to compare elements in order to find the minimum element in each iteration. So we can say that it uses comparisons in order to sort the array. Thus it qualifies as a comparison based sort.

7. What is the average case time complexity of recursive bubble sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: The overall recurrence relation of recursive bubble sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n²).

8. What is the best case time complexity of recursive bubble sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
Answer: a
Clarification: The best case time complexity of recursive bubble sort is O(n). It occurs in the case when the input is already/almost sorted.

9. What is the worst case time complexity of recursive bubble sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)
Answer: c
Clarification: The overall recurrence relation of recursive bubble sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n²).

10. What are the number of swaps required to sort the array arr={1, 2, 4, 3, 7, 5, 6} using recursive bubble sort?
a) 0
b) 1
c) 2
d) 3
Answer: d
Clarification: The first swap takes place between 4 and 3 then the second swap takes place between 7 and 5 and then finally 6 and 7 are swapped which sorts our array.

11. What will be the base case for the code of recursive bubble sort?
a)

b)

c)

d)

View Answer

Answer: c
Clarification: The most appropriate condition for the base case of recursive bubble sort is when n equal 1 then return. It is because we know that an array with only 1 element is always sorted.

12. What is the auxiliary space complexity of recursive bubble sort?
a) O(n)
b) O(1)
c) O(n log n)
d) O(n²)
Answer: b
Clarification: The auxiliary space required by recursive bubble sort is O(1). So it qualifies as an in-place sorting algorithm.

13. Bubble sort is an adaptive sorting algorithm.
a) true
b) false

Answer: a
Clarification: Bubble sort is an adaptive algorithm. It is because the time complexity of the algorithm improves when the input array is almost sorted.

14. Which of the following sorting algorithm is in place?
a) recursive bubble sort
b) merge sort
c) radix sort
d) counting sort

Answer: a
Clarification: Out of the given options recursive bubble sort is the only algorithm which is in place. It is because the auxiliary space required by recursive bubble sort is O(1).

15. Choose the correct function for recursive bubble sort?
a)

void rec_bubbleSort(int arr[], int n) 
{ 	
	if (n == 1) 
		return;	
	for (int i=0; i<n-1; i++) 
		if (arr[i] > arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
	rec_bubbleSort(arr, n-1); 
}

b)

void rec_bubbleSort(int arr[], int n) 
{ 	
	if (n == 2) 
		return; 	
	for (int i=0; i<n-1; i++) 
		if (arr[i] > arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
	rec_bubbleSort(arr, n-1); 
}

c)

void rec_bubbleSort(int arr[], int n) 
{ 
	if (n == 1) 
		return; 	
	for (int i=0; i<n-1; i++) 
		if (arr[i] < arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
 
	rec_bubbleSort(arr, n-1); 
}

d)

void rec_bubbleSort(int arr[], int n) 
{ 
	if (n == 2) 
		return; 	
	for (int i=0; i<n-1; i++) 
		if (arr[i] < arr[i+1]) 
        { 
			swap(arr[i], arr[i+1]); 
        }
 
	rec_bubbleSort(arr, n-1); 
}

Answer: a
Clarification: The base case of the recursive bubble sort should be 1 when equal 1 then return. It is because we know that an array with only 1 element is always sorted. Also, we need to swap the adjacent elements which are out of order.

Data Structures & Algorithms Multiple Choice Questions on “Cross Product”.

1. Cross product is a mathematical operation performed between ________________
a) 2 scalar numbers
b) a scalar and a vector
c) 2 vectors
d) any 2 numbers

Answer: c
Clarification: Cross product is a mathematical operation that is performed on 2 vectors in a 3D plane. It has many applications in computer programming and physics.

2. Cross product is also known as?
a) scalar product
b) vector product
c) dot product
d) multiplication

Answer: b
Clarification: Cross product is also known as a vector product. It is a mathematical operation that is performed on 2 vectors in 3D plane.

3. What is the magnitude of resultant of cross product of two parallel vectors a and b?
a) |a|.|b|
b) |a|.|b| cos(180)
c) |a|.|b| sin(180)
d) 1

Answer: c
Clarification: The resultant of cross product of 2 parallel vectors is always 0 as the angle between them is 0 or 180 degrees. So the answer is |a|.|b| sin(180).

4. What is the general formula for finding the magnitude of the cross product of two vectors a and b with angle θ between them?
a) |a|.|b|
b) |a|.|b| cos(θ)
c) |a|.|b| sin(θ)
d) |a|.|b| tan(θ)

Answer: c
Clarification: The general formula for finding the magnitude of cross product of two vectors is |a|.|b| sin(θ). Its direction is perpendicular to the plane containing a and b.

5. The concept of cross product is applied in the field of computer graphics.
a) true
b) false

Answer: a
Clarification: The concept of cross product find its application in the field of computer graphics. It can be used to find the winding of polygon about a point.

6. Which of the following equals the a x b ( a and b are two vectors)?
a) – (a x b)
b) a.b
c) b x a
d) – (b x a)

Answer: d
Clarification: The vector product a x b is equal to – (b x a). The minus sign shows that these vectors have opposite directions.

7. Cross product of two vectors can be used to find?
a) area of rectangle
b) area of square
c) area of parallelogram
d) perimeter of rectangle

Answer: c
Clarification: Cross product of two vectors can be used to find the area of parallelogram. For this, we need to consider the vectors as the adjacent sides of the parallelogram.

8. The resultant vector from the cross product of two vectors is _____________
a) perpendicular to any one of the two vectors involved in cross product
b) perpendicular to the plane containing both vectors
c) parallel to to any one of the two vectors involved in cross product
d) parallel to the plane containing both vectors

Answer: b
Clarification: The resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. In other words, it should be perpendicular to both the vectors involved in the cross product.

9. What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k?
a) i + 2j + k
b) 2i + 3j + k
c) i + j – 5k
d) 2i – j – 5k

Answer: c
Clarification: We can find the cross product of the given vectors by solving the determinant.

10. What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k?
a) i + 2j + k
b) i – j – 5k
c) 0
d) 2i – j – 5k
Answer: c
Clarification: The given vectors are parallel to each other. The cross product of parallel vectors is 0 because sin(0) is 0.

11. Find the output of the following code.

#include  
using namespace std; 
void crossP(int A[], int B[], int cross[]) 
{ 
	cross[0] = A[1] * B[2] - A[2] * B[1]; 
	cross[1] = A[0] * B[2] - A[2] * B[0]; 
	cross[2] = A[0] * B[1] - A[1] * B[0]; 
}
int main() 
{ 
	int A[] = { 1, 2, 4 }; 
	int B[] = { 2, 3, 2 }; 
	int cross[3]; 
	crossP(A, B, cross); 
	for (int i = 0; i < 3; i++) 
		cout << cross[i] << " "; 
	return 0; 
}

a) 1 2 5
b) -1 -5 -3
c) -6 -8 -1
d) -8 -6 -1
Answer: d
Clarification: The given code calculates the cross product of the vectors stored in arrays A and B respectively. So the output will be -8 -6 -1.

12. Which of the following operation will give a vector that is perpendicular to both vectors a and b?
a) a x b
b) a.b
c) b x a
d) both a x b and b x a
Answer: d
Clarification: The resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. So both a x b and b x a will give a vector that is perpendicular to both vectors a and b.

Data Structures & Algorithms Multiple Choice Questions on “Maximum Bipartite Matching”.

1. _____________ is a matching with the largest number of edges.
a) Maximum bipartite matching
b) Non-bipartite matching
c) Stable marriage
d) Simplex

Answer: a
Clarification: Maximum bipartite matching matches two elements with a property that no two edges share a vertex.

2. Maximum matching is also called as maximum cardinality matching.
a) True
b) False

Answer: a
Clarification: Maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges.

3. How many colours are used in a bipartite graph?
a) 1
b) 2
c) 3
d) 4
Answer: b
Clarification: A bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours.

4. What is the simplest method to prove that a graph is bipartite?
a) It has a cycle of an odd length
b) It does not have cycles
c) It does not have a cycle of an odd length
d) Both odd and even cycles are formed

Answer: c
Clarification: It is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length.

5. A matching that matches all the vertices of a graph is called?
a) Perfect matching
b) Cardinality matching
c) Good matching
d) Simplex matching

Answer: a
Clarification: A matching that matches all the vertices of a graph is called perfect matching.

6. What is the length of an augmenting path?
a) Even
b) Odd
c) Depends on graph
d) 1

Answer: b
Clarification: The length of an augmenting path in a bipartite graph is always said to be always odd.

7. In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?
a) Bipartite matching
b) Cardinality matching
c) Augmenting
d) Weight matching

Answer: c
Clarification: A simple path from a free vertex in V to a free vertex in U whose edges alternate between edges not in M and edges in M is called a augmenting path.

8. A matching M is maximal if and only if there exists no augmenting path with respect to M.
a) True
b) False

Answer: a
Clarification: According to the theorem discovered by the French mathematician Claude Berge, it means that the current matching is maximal if there is no augmenting path.

9. Which one of the following is an application for matching?
a) Proposal of marriage
b) Pairing boys and girls for a dance
c) Arranging elements in a set
d) Finding the shortest traversal path
View Answer

Answer: b
Clarification: Pairing boys and girls for a dance is a traditional example for matching. Proposal of marriage is an application of stable marriage problem.

10. Which is the correct technique for finding a maximum matching in a graph?
a) DFS traversal
b) BFS traversal
c) Shortest path traversal
d) Heap order traversal

Answer: b
Clarification: The correct technique for finding a maximum matching in a bipartite graph is by using a Breadth First Search(BFS).

11. The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?
a) Maximum- mass matching
b) Maximum bipartite matching
c) Maximum weight matching
d) Maximum node matching

Answer: c
Clarification: The problem is called as maximum weight matching which is similar to a bipartite matching. It is also called as assignment problem.

12. What is the total number of iterations used in a maximum- matching algorithm?
a) [n/2]
b) [n/3]
c) [n/2]+n
d) [n/2]+1

Answer: d
Clarification: The total number of iterations cannot exceed [n/2]+1 where n=|V|+|U| denoting the number of vertices in the graph.

13. What is the efficiency of algorithm designed by Hopcroft and Karp?
a) O(n+m)
b) O(n(n+m)
c) O(√n(n+m))
d) O(n+2)
Answer: c
Clarification: The efficiency of algorithm designed by Hopcroft and Karp is mathematically found to be O(√n(n+m)).

14. Who was the first person to solve the maximum matching problem?
a) Jack Edmonds
b) Hopcroft
c) Karp
d) Claude Berge
Answer: a
Clarification: Jack Edmonds was the first person to solve the maximum matching problem in 1965.

15. From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?

a) 5
b) 4
c) 3
d) 2
View Answer

Answer: a
Clarification: One of the solutions of the matching problem is given by a-w,b-v,c-x,d-y,e-z. Hence the answer is 5.

contest

Data Structure Questions and Answers for Campus interviews on “Decimal to Binary Conversion using Recursion”.

1. Which of the following is the binary representation of 100?
a) 1010010
b) 1110000
c) 1100100
d) 1010101

Answer: c
Clarification: 100 = 64 + 32 + 4 = 2⁶ + 2⁵ + 2² = 1100100.

2. Consider the following iterative code used to convert a decimal number to its equivalent binary:

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          _______;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 10;
     dec_to_bin(n);
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) n–
b) n /= 2
c) n /= 10
d) n++

Answer: b
Clarification: The line “n /= 2” should be inserted to complete the above code.

3. What is the output of the following code?

#include
void dec_to_bin(int n)
{
    int arr[31],len = 0,i;
    if(n == 0)
    {
        arr[0] = 0;
        len = 1;
    }
    while(n != 0)
    {
        arr[len++] = n % 2;
        n /= 2;
    }
    for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
    int n = 63;
    dec_to_bin(n);
    return 0;
}

a) 111111
b) 111011
c) 101101
d) 101010

Answer: a
Clarification: The program prints the binary equivalent of 63, which is 111111.

4. What is the output of the following code?

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          n /= 2;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 0;
     dec_to_bin(n);
     return 0;
}

a) 0
b) 1
c) Runtime error
d) Garbage value

Answer: a
Clarification: The program prints the binary equivalent of 0, which is 0.

5. What is the time complexity of the following code used to convert a decimal number to its binary equivalent?

#include
void dec_to_bin(int n)
{
      int arr[31],len = 0,i;
      if(n == 0)
      {
          arr[0] = 0;
          len = 1;
      }
      while(n != 0)
      {
          arr[len++] = n % 2;
          n /= 2;
      }
      for(i=len-1; i>=0; i--)
        printf("%d",arr[i]);
}
int main()
{
     int n = 0;
     dec_to_bin(n);
     return 0;
}

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

Answer: d
Clarification: The time complexity of the above code used to convert a decimal number to its binary equivalent is O(logn).

6. Consider the following recursive implementation used to convert a decimal number to its binary equivalent:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
          return;
        __________;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = 100,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) arr[len] = n
b) arr[len] = n % 2
c) arr[len++] = n % 2
d) arr[len++] = n

Answer: c
Clarification: The line “arr[len++] = n % 2” should be inserted to complete the above code.

7. Consider the following code:

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}

Which of the following lines is the base case for the above code?
a) if(n ==0 && len == 0)
b) if(n == 0)
c) if(n ==0 && len == 0) and if(n == 0)
d) if(n == 1)

Answer: c
Clarification: Both of the above mentioned lines are the base cases for the above code.

8. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = -100,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

a) -1100100
b) 1100100
c) 2’s complement of 1100100
d) Garbage value

Answer: d
Clarification: The program doesn’t handle negative inputs and so produces a garbage value.

9. What is the time complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}

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

Answer: d
Clarification: The time complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

10. What is the space complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}

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

Answer: d
Clarification: The space complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

11. What is the output of the following code?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
     int n = 111,i;
     recursive_dec_to_bin(n);
     for(i=len-1; i>=0; i--)
     printf("%d",arr[i]);
     return 0;
}

a) 1110111
b) 1001111
c) 1101111
d) 1010111

Answer: c
Clarification: The program prints the binary equivalent of 111, which is 1101111.

12. How many times is the function recursive_dec_to_bin() called when the following code is executed?

#include
int arr[31], len = 0;
void recursive_dec_to_bin(int n)
{
      if(n == 0 && len == 0)
      {
          arr[len++] = 0;
          return;
      }
      if(n == 0)
         return;
      arr[len++] = n % 2;
      recursive_dec_to_bin(n/2);
}
int main()
{
    int n = 111,i;
    recursive_dec_to_bin(n);
    for(i=len-1; i>=0; i--)
    printf("%d",arr[i]);
    return 0;
}

a) 7
b) 8
c) 9
d) 10

Answer: b
Clarification: The function recursive_dec_to_bin() is called 8 times when the above code is executed.