Category: Data Structures & Algorithms Objective Questions

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

1. Cocktail sort is also known as ________________
a) bidirectional sort
b) bubble sort
c) brick sort
d) ripple sort

Answer: d
Clarification: Cocktail sort is also known by the name of ripple sort. It is also known by other names like – bidirectional bubble sort, cocktail shaker sort, shuttle sort, shuffle sort etc.

2. Cocktail sort is a variation of _____________
a) Bubble sort
b) Selection sort
c) Insertion sort
d) Gnome sort

Answer: a
Clarification: Cocktail sort is very similar to bubble sort. It works by traversing an array in both directions alternatively. It compares the adjacent elements in each iteration and swaps the ones which are out of order.

3. Auxiliary space requirement of cocktail sort is _____________
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)
Answer: c
Clarification: In cocktail sort manipulation is done on the input array itself. So no extra space is required to perform sorting. Thus it requires constant auxiliary space.

4. Which of the following sorting algorithm is NOT stable?
a) Quick sort
b) Cocktail sort
c) Bubble sort
d) Merge sort
Answer: a
Clarification: Out of the given options quick sort is the only algorithm which is not stable. Cocktail sort like bubble sort is a stable sorting algorithm.

5. Which of the following sorting algorithm is in place?
a) cocktail sort
b) merge sort
c) counting sort
d) radix sort
Answer: a
Clarification: Cocktail sort is an in place sorting technique as it only requires constant auxiliary space for manipulating the input array. Rest all other options are not in place.

6. Cocktail sort is a comparison based sort.
a) True
b) False

Answer: a
Clarification: Cocktail sort compares the value of different elements in the array for sorting. Thus, it is a comparison based sort.

7. Cocktail sort uses which of the following methods for sorting the input?
a) selection
b) partitioning
c) merging
d) exchanging

Answer: d
Clarification: Cocktail sort uses a method of exchanging as it swaps the elements which are out of order. This swapping is done in two phases i.e. forward phase and backward phase.

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

Answer: c
Clarification: Worst case complexity is observed when the input array is reverse sorted. This is the same as the worst case complexity of bubble sort.

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

Answer: a
Clarification: Best case complexity is observed when the input array is already sorted. This is the same as the best case complexity of bubble sort.

10. What is the average case time complexity of odd-even sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: Cocktail sort takes O(n²) time on average as it keeps on applying bubble sort on the elements in two phases until they are sorted. This is the same as the average time complexity of bubble sort.

11. How many iterations are required to sort the array arr={2,3,4,5,1} using bubble sort and cocktail sort respectively?
a) 4,2
b) 5,3
c) 5,2
d) 4,3
Answer: a
Clarification: Cocktail sort applies bubble sort in two phases until the array gets sorted. So here bubble sort will take 4 iterations to sort the given array whereas cocktail sort takes only 2 iterations. This shows cocktail sort has a comparatively better performance.

12. The following function represents which sorting?

void Sorting(int a[], int n) 
{ 
	bool swap = true; 
	int first = 0; 
	int last = n - 1; 
 
	while (swap) 
        { 
 
		swap = false; 
 
		for (int i = first; i < last;i++)
                { 
			if (a[i] > a[i + 1]) 
                        { 
				swap(a[i], a[i + 1]); 
				swap = true; 
			} 
		} 
 
		if (!swap) 
			break; 
 
		swap = false; 
 
		--last; 
 
 
		for (int i = last - 1; i >= first; i--)
                { 
			if (a[i] > a[i + 1]) 
                        { 
				swap(a[i], a[i + 1]); 
				swap = true; 
			} 
		} 
 
		++first; 
	} 
}

a) Bubble sort
b) Selection sort
c) Bidirectional bubble sort
d) Odd-even sort
Answer: c
Clarification: The given function represents bidirectional bubble sort also known as cocktail sort. In this sort, we apply bubble sort in two phases i.e. forward and backward phase until the array gets sorted.

13. Bubble sort performs better as compared to cocktail sort.
a) True
b) False
Answer: b
Clarification: Both bubble sort and cocktail sort has the same time complexities. But cocktail sort has a comparatively better performance.

and Answers.

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

1. Which of the following is an advantage of binary insertion sort over its standard version?
a) it has better time complexity
b) it has better space complexity
c) it makes less number of comparisons
d) it has no significant advantage

Answer: c
Clarification: Binary insertion sort makes less number of comparisons as compared to the standard version of insertion sort. Binary insertion sort makes log n comparisons in the worst case as compared to n comparisons made in the standard version.

2. Binary Insertion sort is an online sorting algorithm.
a) True
b) False

Answer: a
Clarification: Binary Insertion sort does not require the entire input data at the beginning itself in order to sort the array. It rather creates a partial solution in every step, so future elements are not required to be considered. Hence it is an online sorting algorithm.

3. How many comparisons will be made in the worst case when an array of size n will be sorted by using a binary insertion sort algorithm?
a) n
b) 1
c) log n
d) n log n
Answer: c
Clarification: Binary insertion sort makes log n comparisons in the worst case. Whereas the standard version makes n comparisons in the worst case.

4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Binary insertion sort
d) Heap sort
Answer: c
Clarification: Out of the given options binary insertion 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 sorting algorithm uses a binary search?
a) radix sort
b) binary insertion sort
c) odd-even sort
d) bead sort

Answer: b
Clarification: Binary insertion sort makes use of a binary search algorithm. It is used to find the correct index in the array where the element should be inserted.

6. Binary insertion sort is a comparison based sort.
a) true
b) false
Answer: a
Clarification: In insertion 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 binary insertion sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: The time complexity does not change when we use binary insertion sort in place of standard insertion sort. So the average case time complexity is O(n²).

8. What is the best case time complexity of binary insertion 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 binary insertion 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 binary insertion sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: The time complexity does not change when we use binary insertion sort in place of standard insertion sort. So the worst case time complexity is O(n²).

10. Choose the correct statement regarding binary insertion sort?
a) It has a better time complexity as compared to the standard version
b) It has a better space complexity as compared to the standard version
c) it takes less number of comparisons in the best case as compared to the standard version
d) it takes less number of comparisons in the worst case as compared to the standard version

Answer: d
Clarification: Binary insertion sort has the advantage that it takes less number of comparisons in the worst case as compared to the standard version. In the best case, both standard insertion sort and binary insertion sort makes only 1 comparison.

11. What will be the base case in the function of binary search used in the code of binary insertion sort? (high and low are the rightmost and leftmost index of array respectively and item is the element whose correct position is to be determined by the binary search function)
a)

If(high<=low) 
{ 
    If(Item>a[low])
    return low+1;
    return low;
}

b)

If(high>=low)
{
    If(Item<a[low])
    return low+1;
    return low;
}

c)

If(high<=low)
{
    If(Item<a[low])
    return low;
    return low+1;
}

d)

If(high<=low)
{  
    If(Item>a[low])
    return low;
    return low+1;
}

Answer: c
Clarification: The base case of binary search has to be made such that even when the element is not found in the array the function still returns the required index back to the function of insertion sort.

12. What is the auxiliary space complexity of binary insertion sort?
a) O(n)
b) O(1)
c) O(n log n)
d) O(n²)
View Answer

Answer: b
Clarification: The auxiliary space required by a binary insertion sort is O(1). So it qualifies as an in place sorting algorithm.

13. Which of the following is an adaptive sorting algorithm?
a) binary insertion sort
b) merge sort
c) heap sort
d) selection sort
View Answer

Answer: a
Clarification: Binary insertion 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) binary insertion sort
b) merge sort
c) radix sort
d) counting sort
View Answer

Answer: a
Clarification: Out of the given options binary insertion 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 binary insertion sort?
a)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key; 
 
    for (int i = 1; i <=n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
       //function binarySearch() returns the index
        int index = binarySearch(a, key, 0, j);  
       //where the key should be inserted        
        while (j >= index) 
        { 
            a[j+1] = a[j]; 
            j--; 
        } 
        a[j+1] = key; 
    } 
}

b)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key; 
 
    for (int i = 1; i < =n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
        //function binarySearch() returns the index
        int index = binarySearch(a, key, j,0);  
        //where the key should be inserted
        while (j >= index) 
        { 
            a[j+1] = a[j]; 
            J++; 
        } 
        a[j+1] = key; 
    } 
}

c)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key;   
    for (int i = 1; i <=n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
        //function binarySearch() returns the index
        int index = binarySearch(a, key, 0, j);  
        //where the key should be inserted        
        while (j <= index) 
        { 
            a[j+1] = a[j]; 
            j--; 
        } 
        a[j+1] = key; 
    } 
}

d)

void BinaryinsertionSort(int a[], int n) 
{ 
    int key; 
 
    for (int i = 1; i <=n-1; ++i) 
    { 
        int j = i - 1; 
        key = a[i]; 
        //function binarySearch() returns the index
        int index = binarySearch(a, key, 0, j); 
        //where the key should be inserted        
        while (j <= index) 
        { 
            a[j+1] = a[j]; 
            J++; 
        } 
        a[j+1] = key; 
    } 
}

Answer: a
Clarification: The code of binary insertion sort is same as the standard insertion sort except that we are finding the index where the key has to be inserted by using binary search. This reduces the number of comparisons.

Data Structures & Algorithms Multiple Choice Questions on “Quickhull”.

1. ___________ is a method of constructing a smallest polygon out of n given points.
a) closest pair problem
b) quick hull problem
c) path compression
d) union-by-rank

Answer: b
Clarification: Quick hull is a method of constructing a smallest convex polygon out of n given points in a plane.

2. What is the other name for quick hull problem?
a) convex hull
b) concave hull
c) closest pair
d) path compression
Answer: a
Clarification: The other name for quick hull problem is convex hull problem whereas the closest pair problem is the problem of finding the closest distance between two points.

3. How many approaches can be applied to solve quick hull problem?
a) 1
b) 2
c) 3
d) 4
Answer: b
Clarification: Most commonly, two approaches are adopted to solve quick hull problem- brute force approach and divide and conquer approach.

4. What is the average case complexity of a quick hull algorithm?
a) O(N)
b) O(N log N)
c) O(N²)
d) O(log N)

Answer: b
Clarification: The average case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N log N).

5. What is the worst case complexity of quick hull?
a) O(N)
b) O(N log N)
c) O(N²)
d) O(log N)

Answer: c
Clarification: The worst case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be O(N²).

6. What does the following diagram depict?

a) closest pair
b) convex hull
c) concave hull
d) path compression

Answer: b
Clarification: The above diagram is a depiction of convex hull, also known as quick hull, since it encloses n points into a convex polygon.

7. Which of the following statement is not related to quickhull algorithm?
a) finding points with minimum and maximum coordinates
b) dividing the subset of points by a line
c) eliminating points within a formed triangle
d) finding the shortest distance between two points

Answer: d
Clarification: Finding the shortest distance between two points belongs to closest pair algorithm while the rest is quickhull.

8. The quick hull algorithm runs faster if the input uses non- extreme points.
a) true
b) false
View Answer

Answer: a
Clarification: It is proved that the quick hull algorithm runs faster if the input uses non-extreme points and also, if it uses less memory.

9. To which type of problems does quick hull belong to?
a) numerical problems
b) computational geometry
c) graph problems
d) string problems
View Answer

Answer: b
Clarification: Quick hull problem and closest pair algorithms are some of the examples of computational problems.

10. Which of the following algorithms is similar to a quickhull algorithm?
a) merge sort
b) shell sort
c) selection sort
d) quick sort

Answer: d
Clarification: Quickhull algorithm is similar to a quick sort algorithm with respect to the run time average case and worst case efficiencies.

11. Who formulated quick hull algorithm?
a) Eddy
b) Andrew
c) Chan
d) Graham

Answer: a
Clarification: Eddy formulated quick hull algorithm. Graham invented graham scan. Andrew formulated Andrew’s algorithm and Chan invented Chan’s algorithm.

12. The time is taken to find the ‘n’ points that lie in a convex quadrilateral is?
a) O(N)
b) O(N log N)
c) O(N²)
d) O(log N)

Answer: a
Clarification: The time taken to find the ‘n’ points that lie in a convex quadrilateral is mathematically found to be O(N).

here is complete set of 1000+

Data Structures & Algorithms Multiple Choice Questions on “Minimum Cut”.

1. Which algorithm is used to solve a minimum cut algorithm?
a) Gale-Shapley algorithm
b) Ford-Fulkerson algorithm
c) Stoer-Wagner algorithm
d) Prim’s algorithm
View Answer

Answer: c
Clarification: Minimum cut algorithm is solved using Stoer-Wagner algorithm. Maximum flow problem is solved using Ford-Fulkerson algorithm. Stable marriage problem is solved using Gale-Shapley algorithm.

2. ___________ is a partition of the vertices of a graph in two disjoint subsets that are joined by atleast one edge.
a) Minimum cut
b) Maximum flow
c) Maximum cut
d) Graph cut

Answer: a
Clarification: Minimum cut is a partition of the vertices in a graph 4. in two disjoint subsets joined by one edge. It is a cut that is minimal in some sense.

3. Minimum cut algorithm comes along with the maximum flow problem.
a) true
b) false

Answer: a
Clarification: Minimum cut algorithm is considered to be an extension of the maximum flow problem. Minimum cut is finding a cut that is minimal.

4. What does the given figure depict?

a) min cut problem
b) max cut problem
c) maximum flow problem
d) flow graph
View Answer

Answer: a
Clarification: The given figure is a depiction of min cut problem since the graph is partitioned to find the minimum cut.

5. ______________ separates a particular pair of vertices in a graph.
a) line
b) arc
c) cut
d) flow

Answer: c
Clarification: A cut separates a particular pair of vertices in a weighted undirected graph and has minimum possible weight.

6. What is the minimum number of cuts that a graph with ‘n’ vertices can have?
a) n+1
b) n(n-1)
c) n(n+1)/2
d) n(n-1)/2

Answer: c
Clarification: The mathematical formula for a graph with ‘n’ vertices can at the most have n(n-1)/2 distinct vertices.

7. What is the running time of Karger’s algorithm to find the minimum cut in a graph?
a) O(E)
b) O(|V|²)
c) O(V)
d) O(|E|)

Answer: b
Clarification: The running time of Karger’s algorithm to find the minimum cut is mathematically found to be O(|V|²).

8. _____________ is a family of combinatorial optimization problems in which a graph is partitioned into two or more parts with constraints.
a) numerical problems
b) graph partition
c) network problems
d) combinatorial problems

Answer: b
Clarification: Graph partition is a problem in which the graph is partitioned into two or more parts with additional conditions.

9. The weight of the cut is not equal to the maximum flow in a network.
a) true
b) false

Answer: b
Clarification: According to max-flow min-cut theorem, the weight of the cut is equal to the maximum flow that is sent from source to sink.

10. __________ is a data structure used to collect a system of cuts for solving min-cut problem.
a) Gomory-Hu tree
b) Gomory-Hu graph
c) Dancing tree
d) AA tree

Answer: a
Clarification: Gomory-Hu tree is a weighted tree that contains the minimum cuts for all pairs in a graph. It is constructed in |V|-1 max-flow computations.

11. In how many ways can a Gomory-Hu tree be implemented?
a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: Gomory-Hu tree can be implemented in two ways- sequential and parallel.

12. The running time of implementing naïve solution to min-cut problem is?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N²)
Answer: d
Clarification: The running time of min-cut algorithm using naïve implementation is mathematically found to be O(N²).

13. What is the running time of implementing a min-cut algorithm using bidirected edges in a graph?
a) O(N)
b) O(N log N)
c) O(N⁴)
d) O(N²)
Answer: c
Clarification: The running time of a min-cut algorithm using Ford-Fulkerson method of making edges birected in a graph is mathematically found to be O(N⁴).

14. Which one of the following is not an application of max-flow min-cut algorithm?
a) network reliability
b) closest pair
c) network connectivity
d) bipartite matching

Answer: b
Clarification: Network reliability, connectivity and bipartite matching are all applications of min-cut algorithm whereas closest pair is a different kind of problem.

15. What is the minimum cut of the following network?

a) ({1,3},{4,3},{4,5})
b) ({1,2},{2,3},{4,5})
c) ({1,0},{4,3},{4,2})
d) ({1,2},{3,2},{4,5})

Answer: a
Clarification: The minimum cut of the given graph network is found to be ({1,3},{4,3},{4,5}) and its capacity is 23.

complete set of 1000+

Basic Data Structure Questions and Answers on “Length of a Linked List using Recursion”.

1. Consider the following iterative implementation used to find the length of a linked list:

struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(_____)
      {
          len++;
          temp = temp->next;
      }
      return len;
}

Which of the following conditions should be checked to complete the above code?
a) temp->next != 0
b) temp == 0
c) temp != 0
d) temp->next == 0

Answer: c
Clarification: The condition “temp != 0” should be checked to complete the above code.

2. What is the output of the following code?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(temp != 0)
      {
          len++;
          temp = temp->next;
      }
      return len;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = get_len();
      printf("%d",len);
      return 0;
}

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

Answer: b
Clarification: The program prints the length of the linked list, which is 5.

3. What is the time complexity of the following iterative implementation used to find the length of a linked list?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(temp != 0)
      {
          len++;
          temp = temp->next;
      }
      return len;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = get_len();
      printf("%d",len);
      return 0;
}

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

Answer: b
Clarification: The time complexity of the above iterative implementation used to find the length of a linked list is O(n).

4. What is the output of the following code?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(temp != 0)
      {
          len++;
          temp = temp->next;
      }
      return len;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      int len = get_len();
      printf("%d",len);
      return 0;
}

a) 0
b) Garbage value
c) Compile time error
d) Runtime error

Answer: a
Clarification: The program prints the length of the linked list, which is 0.

5. Which of the following can be the base case for the recursive implementation used to find the length of linked list?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(temp != 0)
      {
          len++;
          temp = temp->next;
      }
      return len;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      int len = get_len();
      printf("%d",len);
      return 0;
}

a) if(current_node == 0) return 1
b) if(current_node->next == 0) return 1
c) if(current_node->next == 0) return 0
d) if(current_node == 0) return 0

Answer: d
Clarification: The line “if(current_node == 0) return 0” can be used as a base case in the recursive implementation used to find the length of a linked list. Note: The line “if(current_node->next == 0) return 1” cannot be used because it won’t work when the length of the linked list is zero.

6. Which of the following lines should be inserted to complete the following recursive implementation used to find the length of a linked list?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return _____;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) recursive_get_len(current_node)
b) 1 + recursive_get_len(current_node)
c) recursive_get_len(current_node->next)
d) 1 + recursive_get_len(current_node->next)

Answer: d
Clarification: The line “1 + recursive_get_len(current_node->next)” should be inserted to complete the above code.

7. What is the output of the following code?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5,0}, n = 7, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) 6
b) 7
c) 8
d) 9
Answer: b
Clarification: The program prints the length of the linked list, which is 7.

8. What is the time complexity of the following code used to find the length of a linked list?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5,0}, n = 7, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) O(1)
b) O(n)
c) O(n²)
d) O(n³)
Answer: b
Clarification: To find the length of the linked list, the program iterates over the linked list once. So, the time complexity of the above code is O(n).

9. What is the output of the following code?

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5}, n = 6, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) 5
b) 6
c) 7
d) 8

Answer: b
Clarification: The program prints the length of the linked list, which is 6.

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

#include
#include
struct Node
{
      int val;
      struct Node *next;
}*head;
int recursive_get_len(struct Node *current_node)
{
      if(current_node == 0)
        return 0;
      return 1 + recursive_get_len(current_node->next);
}
int main()
{
      int arr[10] = {-1,2,3,-3,4,5}, n = 6, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      temp = head;
      for(i=0; i<n; i++)
      {
          newNode = (struct Node*)malloc(sizeof(struct Node));
          newNode->val = arr[i];
          newNode->next = 0;
          temp->next = newNode;
          temp = temp->next;
      }
      int len = recursive_get_len(head->next);
      printf("%d",len);
      return 0;
}

a) 5
b) 6
c) 7
d) 8

Answer: c
Clarification: The function is called “len + 1” times. Since the length of the linked list in the above code is 6, the function is called 6 + 1 = 7 times.

and Answers.

Data Structures & Algorithms Multiple Choice Questions on “Backtracking”.

1. Which of the problems cannot be solved by backtracking method?
a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem

Answer: d
Clarification: N-queen problem, subset sum problem, Hamiltonian circuit problems can be solved by backtracking method whereas travelling salesman problem is solved by Branch and bound method.

2. Backtracking algorithm is implemented by constructing a tree of choices called as?
a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree
Answer: a
Clarification: Backtracking problem is solved by constructing a tree of choices called as the state-space tree. Its root represents an initial state before the search for a solution begins.

3. What happens when the backtracking algorithm reaches a complete solution?
a) It backtracks to the root
b) It continues searching for other possible solutions
c) It traverses from a different route
d) Recursively traverses through the same route

Answer: b
Clarification: When we reach a final solution using a backtracking algorithm, we either stop or continue searching for other possible solutions.

4. A node is said to be ____________ if it has a possibility of reaching a complete solution.
a) Non-promising
b) Promising
c) Succeeding
d) Preceding

Answer: b
Clarification: If a node has a possibility of reaching the final solution, it is called a promising node. Otherwise, it is non-promising.

5. In what manner is a state-space tree for a backtracking algorithm constructed?
a) Depth-first search
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first

Answer: a
Clarification: A state-space tree for a backtracking algorithm is constructed in the manner of depth-first search so that it is easy to look into.

6. The leaves in a state-space tree represent only complete solutions.
a) true
b) false

Answer: b
Clarification: The leaves in a state space tree can either represent non-promising dead ends or complete solutions found by the algorithm.

7. In general, backtracking can be used to solve?
a) Numerical problems
b) Exhaustive search
c) Combinatorial problems
d) Graph coloring problems

Answer: c
Clarification: Backtracking approach is used to solve complex combinatorial problems which cannot be solved by exhaustive search algorithms.

8. Which one of the following is an application of the backtracking algorithm?
a) Finding the shortest path
b) Finding the efficient quantity to shop
c) Ludo
d) Crossword

Answer: d
Clarification: Crossword puzzles are based on backtracking approach whereas the rest are travelling salesman problem, knapsack problem and dice game.

9. Backtracking algorithm is faster than the brute force technique
a) true
b) false

Answer: a
Clarification: Backtracking is faster than brute force approach since it can remove a large set of answers in one test.

10. Which of the following logical programming languages is not based on backtracking?
a) Icon
b) Prolog
c) Planner
d) Fortran

Answer: d
Clarification: Backtracking algorithm form the basis for icon, planner and prolog whereas fortran is an ancient assembly language used in second generation computers.

11. The problem of finding a list of integers in a given specific range that meets certain conditions is called?
a) Subset sum problem
b) Constraint satisfaction problem
c) Hamiltonian circuit problem
d) Travelling salesman problem

Answer: b
Clarification: Constraint satisfaction problem is the problem of finding a list of integers under given constraints. Constraint satisfaction problem is solved using a backtracking approach.

12. Who coined the term ‘backtracking’?
a) Lehmer
b) Donald
c) Ross
d) Ford

Answer: a
Clarification: D.H. Lehmer was the first person to coin the term backtracking. Initially, the backtracking facility was provided using SNOBOL.

13. ___________ enumerates a list of promising nodes that could be computed to give the possible solutions of a given problem.
a) Exhaustive search
b) Brute force
c) Backtracking
d) Divide and conquer
Answer: c
Clarification: Backtracking is a general algorithm that evaluates partially constructed candidates that can be developed further without violating problem constraints.

14. The problem of finding a subset of positive integers whose sum is equal to a given positive integer is called as?
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem

Answer: b
Clarification: Subset sum problem is the problem of finding a subset using the backtracking algorithm when summed, equals a given integer.

15. The problem of placing n queens in a chessboard such that no two queens attack each other is called as?
a) n-queen problem
b) eight queens puzzle
c) four queens puzzle
d) 1-queen problem

Answer: a
Clarification: The problem of placing n-queens in a chessboard such that no two queens are vertical or horizontal or diagonal to each other is an n-queen problem. The problem only exists for n = 1, 4, 8.

and Answers.