Category: Data Structures & Algorithms Objective Questions

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

1. Which of the following header file is a must to implement sleep sort algorithm?
a) string.h
b) math.hw
c) bios.h
d) windows.h

Answer: d
Clarification: To implement sleep sort algorithm we need functions like WaitForMultipleObjects(), _beginthread(). These are included in the header file windows.h.

2. Sleep sort does not work for ___________
a) negative numbers
b) large numbers
c) small numbers
d) positive numbers

Answer: a
Clarification: Sleep sort algorithm does not work for negative numbers. It is because thread cannot sleep for negative amount of time.

3. In how many comparisons does the array arr={1,4,2,3,5} gets sorted if we use sleep sort?
a) 5
b) 3
c) 1
d) 0

Answer: d
Clarification: Sleep sort makes different elements of the array to sleep for an amount of time that is proportional to its magnitude. So it does not require to perform any comparison in order to sort the array.

4. Sleep sort works by ___________
a) making elements to sleep for a time that is proportional to their magnitude
b) making elements to sleep for a time that is inversely proportional to their magnitude
c) partitioning the input array
d) dividing the value of input elements

Answer: a
Clarification: In sleep sort each element is made to sleep for a time that is proportional to its magnitude. Then the elements are printed in the order in which they wake up.

5. Sleep sort code cannot compile online because ___________
a) it has very high time complexity
b) it has very high space complexity
c) it requires multithreading process
d) online compilers are not efficient

Answer: c
Clarification: Sleep sort requires multithreading process for making the elements to sleep. This process happens in the background at the core of the OS and so cannot be compiled on an online compiler.

6. Time complexity of sleep sort can be approximated to be ___________
a) O(n + max(input))
b) O(n²)
c) O(n log n + max(input))
d) O(n log n)
Answer: c
Clarification: As the sleep() function creates multiple threads by using priority queue which takes n log n time for insertion. Also the output is obtained when all the elements wake up. This time is proportional to the max(input). So its time complexity is approximately O(n log n + max(input)).

7. Sleep sort can be preferred over which of the following sorting algorithms for large number of input elements?
a) Quick sort
b) Bubble sort
c) Selection sort
d) No sorting algorithm is preferred
Answer: d
Clarification: Sleep sort is not preferred over any of the given sorting algorithms as sleep sort does not guarantee a correct output every time. So sleep sort is not a reliable sorting technique.

8. Auxiliary space requirement of sleep sort is ___________
a) O(n)
b) O(1)
c) O(max(input))
d) O(log n)
Answer: b
Clarification: All the major processes involved in sleep sort takes place internally in the OS. So it does not require any auxiliary space to sort the elements.

9. Sleep sort does gives a correct output when ___________
a) any input element is negative
b) input array is reverse sorted
c) any input element is positive
d) when there is a very small number to the left of very large number

Answer: c
Clarification: Sleep sort gives a sorted output when the array elements are positive. But when any other case than this occur out of the above given cases then we may not see a correct output. This makes sleep sort very unreliable sorting technique.

10. Which of the following sorting algorithm is most closely related to the OS?
a) gnome sort
b) sleep sort
c) radix sort
d) bogo sort

Answer: b
Clarification: Sleep sort is most closely related to the operating system. It is because most of the major steps of this algorithm takes place at the core of OS.

11. Sleep sort is an in-place sorting technique.
a) True
b) False

Answer: a
Clarification: Sleep sort is an in-place sorting technique as most of its major steps takes place in the background. So it does not require auxiliary space to sort the input.

& Algorithms.

and Answers.

contest

Data Structures & Algorithms Matching Multiple Choice Questions on “Quick Search Algorithm”.

1. Which of the following is the fastest algorithm in string matching field?
a) Boyer-Moore’s algorithm
b) String matching algorithm
c) Quick search algorithm
d) Linear search algorithm
Answer: c
Clarification: Quick search algorithm is the fastest algorithm in string matching field whereas Linear search algorithm searches for an element in an array of elements.

2. Which of the following algorithms formed the basis for the Quick search algorithm?
a) Boyer-Moore’s algorithm
b) Parallel string matching algorithm
c) Binary Search algorithm
d) Linear Search algorithm

Answer: a
Clarification: Quick search algorithm was originally formed to overcome the drawbacks of Boyer-Moore’s algorithm and also for increased speed and efficiency.

3. What is the time complexity of the Quick search algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)

Answer: c
Clarification: The time complexity of the Quick search algorithm was found to be O(m+n) and is proved to be faster than Boyer-Moore’s algorithm.

4. What character shift tables does quick search algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables

Answer: b
Clarification: Quick search algorithm uses only bad character shift tables and it is one of the reasons for its increased speed than Boyer-Moore’s algorithm.

5. What is the space complexity of quick search algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)

Answer: a
Clarification: The space complexity of quick search algorithm is mathematically found to be O(n) where n represents the input size.

6. Quick search algorithm starts searching from the right most character to the left.
a) true
b) false
View Answer

Answer: b
Clarification: Quick search algorithm starts searching from the left most character to the right and it uses only bad character shift tables.

7. What character shift tables does Boyer-Moore’s search algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables

Answer: d
Clarification: Boyer-Moore’s search algorithm uses both good and bad character shift tables whereas quick search algorithm uses only bad character shift tables.

8. What is the worst case running time in searching phase of Boyer-Moore’s algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)

Answer: d
Clarification: If the pattern occurs in the text, the worst case running time of Boyer-Moore’s algorithm is found to be O(mn).

9. The searching phase in quick search algorithm has good practical behaviour.
a) true
b) false
Answer: a
Clarification: During the searching phase, the comparison between pattern and text characters can be done in any order. It has a quadratic worst case behaviour and good practical behaviour.

10. Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using quick search algorithm.
a) 2
b) 6
c) 11
d) 14

Answer: b
Clarification: By using quick search algorithm, the given input text string is preprocessed and starts its search from the left most character and finds the first occurrence of the pattern at index=2.

and Answers.

Data Structure Multiple Choice Questions on “Breadth First Search”.

1. Breadth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal

Answer: c
Clarification: The Breadth First Search Algorithm searches the nodes on the basis of level. It takes a node (level 0), explores it’s neighbors (level 1) and so on.

2. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)

Answer: a
Clarification: The Breadth First Search explores every node once and every edge once (in worst case), so it’s time complexity is O(V + E).

3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
c) Linked List
d) Tree

Answer: b
Clarification: The Breadth First Search explores every node once and put that node in queue and then it takes out nodes from the queue and explores it’s neighbors.

4. The Breadth First Search traversal of a graph will result into?
a) Linked List
b) Tree
c) Graph with back edges
d) Arrays

Answer: b
Clarification: The Breadth First Search will make a graph which don’t have back edges (a tree) which is known as Breadth First Tree.

5. A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s algorithm

Answer: b
Clarification: This is the definition of the Breadth First Search. Exploring a node, then it’s neighbors and so on.

6. Which of the following is not an application of Breadth First Search?
a) Finding shortest path between two nodes
b) Finding bipartiteness of a graph
c) GPS navigation system
d) Path Finding

Answer: d
Clarification: Breadth First Search can be applied to Bipartite a graph, to find the shortest path between two nodes, in GPS Navigation. In Path finding, Depth First Search is used.

7. When the Breadth First Search of a graph is unique?
a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d) When the graph is a Ternary Tree

Answer: b
Clarification: When Every node will have one successor then the Breadth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

8. Regarding implementation of Breadth First Search using queues, what is the maximum distance between two nodes present in the queue? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information

Answer: c
Clarification: In the queue, at a time, only those nodes will be there whose difference among levels is 1. Same as level order traversal of the tree.

9. In BFS, how many times a node is visited?
a) Once
b) Twice
c) Equivalent to number of indegree of the node
d) Thrice

Answer: c
Clarification: In Breadth First Search, we have to see whether the node is visited or not by it’s ancestor. If it is visited, we won’t let it enter it in the queue.

& Algorithms.

and Answers.

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

1. Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?
a) Number of vertices in U = Number of vertices in V
b) Sum of degrees of vertices in U = Sum of degrees of vertices in V
c) Number of vertices in U > Number of vertices in V
d) Nothing can be said

Answer: b
Clarification: We can prove this by induction. By adding one edge, the degree of vertices in U is equal to 1 as well as in V. Let us assume that this is true for n-1 edges and add one more edge. Since the given edge adds exactly once to both U and V we can tell that this statement is true for all n vertices.

2. A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
a) Number of vertices in U=Number of vertices in V
b) Number of vertices in U not equal to number of vertices in V
c) Number of vertices in U always greater than the number of vertices in V
d) Nothing can be said

Answer: a
Clarification: We know that in a bipartite graph sum of degrees of vertices in U=sum of degrees of vertices in V. Given that the graph is a k-regular bipartite graph, we have k*(number of vertices in U)=k*(number of vertices in V).

3. There are four students in a class namely A, B, C and D. A tells that a triangle is a bipartite graph. B tells pentagon is a bipartite graph. C tells square is a bipartite graph. D tells heptagon is a bipartite graph. Who among the following is correct?
a) A
b) B
c) C
d) D

Answer: c
Clarification: We can prove it in this following way. Let ‘1’ be a vertex in bipartite set X and let ‘2’ be a vertex in the bipartite set Y. Therefore the bipartite set X contains all odd numbers and the bipartite set Y contains all even numbers. Now let us consider a graph of odd cycle (a triangle). There exists an edge from ‘1’ to ‘2’, ‘2’ to ‘3’ and ‘3’ to ‘1’. The latter case (‘3’ to ‘1’) makes an edge to exist in a bipartite set X itself. Therefore telling us that graphs with odd cycles are not bipartite.

4. A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
a) n
b) n/2
c) n/4
d) data insufficient

Answer: b
Clarification: We can prove this by calculus. Let x be the total number of vertices on set X. Therefore set Y will have n-x. We have to maximize x*(n-x). This is true when x=n/2.

5. When is a graph said to be bipartite?
a) If it can be divided into two independent sets A and B such that each edge connects a vertex from to A to B
b) If the graph is connected and it has odd number of vertices
c) If the graph is disconnected
d) If the graph has at least n/2 vertices whose degree is greater than n/2

Answer: a
Clarification: A graph is said to be bipartite if it can be divided into two independent sets A and B such that each edge connects a vertex from A to B.

6. Are trees bipartite?
a) Yes
b) No
c) Yes if it has even number of vertices
d) No if it has odd number of vertices

Answer: a
Clarification: Condition needed is that there should not be an odd cycle. But in a tree there are no cycles at all. Hence it is bipartite.

7. A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)
a) 100
b) 140
c) 80
d) 20

Answer: a
Clarification: Let the given bipartition X have x vertices, then Y will have 20-x vertices. We need to maximize x*(20-x). This will be maxed when x=10.

8. Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite?
a) Yes
b) No

Answer: a
Clarification: It is required that the graph is connected also. If it is not then it cannot be called a bipartite graph.

9. Can there exist a graph which is both eulerian and is bipartite?
a) Yes
b) No
c) Yes if it has even number of edges
d) Nothing can be said

Answer: a
Clarification: If a graph is such that there exists a path which visits every edge atleast once, then it is said to be Eulerian. Taking an example of a square, the given question evaluates to yes.

10. A graph is found to be 2 colorable. What can be said about that graph?
a) The given graph is eulerian
b) The given graph is bipartite
c) The given graph is hamiltonian
d) The given graph is planar

Answer: b
Clarification: A graph is said to be colorable if two vertices connected by an edge are never of the same color. 2 colorable mean that this can be achieved with just 2 colors.

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

1. Which of the following sorting algorithm has best case time complexity of O(n²)?
a) bubble sort
b) selection sort
c) insertion sort
d) stupid sort

Answer: b
Clarification: Selection sort is not an adaptive sorting algorithm. It finds the index of minimum element in each iteration even if the given array is already sorted. Thus its best case time complexity becomes O(n²).

2. Which of the following is the biggest advantage of selection sort?
a) its has low time complexity
b) it has low space complexity
c) it is easy to implement
d) it requires only n swaps under any condition

Answer: d
Clarification: Selection sort works by obtaining least value element in each iteration and then swapping it with the current index. So it will take n swaps under any condition which will be useful when memory write operation is expensive.

3. What will be the recurrence relation of the code of recursive selection 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: Function to find the minimum element index takes n time.The recursive call is made to one less element than in the previous call so the overall recurrence relation becomes T(n) = T(n-1) + n.

4. Which of the following sorting algorithm is NOT stable?
a) Selection sort
b) Brick sort
c) Bubble sort
d) Merge sort

Answer: a
Clarification: Out of the given options selection sort is the only algorithm which is not stable. It is because the order of identical elements in sorted output may be different from input array.

5. What will be the best case time complexity of recursive selection sort?
a) O(n)
b) O(n²)
c) O(log n)
d) O(n log n)

Answer: b
Clarification: Selection sort’s algorithm is such that it finds the index of minimum element in each iteration even if the given array is already sorted. Thus its best case time complexity becomes O(n²).

6. Recursive selection sort is a comparison based sort.
a) true
b) false

Answer: a
Clarification: In selection 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 selection 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 selection sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n²). It is unvaried throughout the three cases.

8. What is the bidirectional variant of selection sort?
a) cocktail sort
b) bogo sort
c) gnome sort
d) bubble sort

Answer: a
Clarification: A bidirectional variant of selection sort is called cocktail sort. It’s an algorithm which finds both the minimum and maximum values in the array in every pass. This reduces the number of scans of the array by a factor of 2.

9. Choose correct C++ code for recursive selection sort from the following.
a)

#include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == 0) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] < a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 
 
	if (index == n) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x == index) 
	{	    
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	recursiveSelectionSort(arr, n); 	
	return 0; 
}

b)

#include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] < a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 
 
	if (index == n) 
        return; 	 
	int x = minIndex(a, index, n-1);	 
	if (x != index) 
	{
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	recursiveSelectionSort(arr, n); 	
	return 0; 
}

c)

#include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 
	return (a[i] > a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 	
	if (index == n) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x != index) 
	{	    
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
        recursiveSelectionSort(arr, n); 
	return 0; 
}

d)

 #include  
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] > a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 	
	if (index == 0) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x == index) 
	{	    
	    	swap(a[x], a[index]);
	}
 	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	recursiveSelectionSort(arr, n); 
        return 0; 
}

View Answer

Answer: b
Clarification: Using the function recursiveSelectionSort() we find the element that needs to be placed at the current index. For finding the minimum element index we use another function minIndex(). After finding the minimum element index the current element is swapped with this element in the function recursiveSelectionSort().

10. What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: The first swap takes place between 1 and 5. The second swap takes place between 3 and 2 which sorts our array.

Data Structure Multiple Choice Questions on “Fibonacci using Dynamic Programming”.

1. The following sequence is a fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21,…..
Which technique can be used to get the nth fibonacci term?
a) Recursion
b) Dynamic programming
c) A single for loop
d) Recursion, Dynamic Programming, For loops

Answer: d
Clarification: Each of the above mentioned methods can be used to find the nth fibonacci term.

2. Consider the recursive implementation to find the nth fibonacci number:

int fibo(int n)
    if n <= 1
	return n
    return __________

Which line would make the implementation complete?
a) fibo(n) + fibo(n)
b) fibo(n) + fibo(n – 1)
c) fibo(n – 1) + fibo(n + 1)
d) fibo(n – 1) + fibo(n – 2)

Answer: d
Clarification: Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a fibonacci sequence would be given by:
fibo(n) = fibo(n-1) + fibo(n-2).

3. What is the time complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n²)
c) O(n!)
d) Exponential
Answer: d
Clarification: The recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). So, the time complexity is given by:
T(n) = T(n – 1) + T(n – 2)
Approximately,
T(n) = 2 * T(n – 1)
= 4 * T(n – 2)
= 8 * T(n – 3)
:
:
:
= 2^k * T(n – k)
This recurrence will stop when n – k = 0
i.e. n = k
Therefore, T(n) = 2ⁿ * O(0) = 2ⁿ
Hence, it takes exponential time.
It can also be proved by drawing the recursion tree and counting the number of leaves.

4. Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:

fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) 
+ fibonacci(3)	+ fibonacci(3) + fibonacci(2)
:
:
:

Which property is shown by the above function calls?
a) Memoization
b) Optimal substructure
c) Overlapping subproblems
d) Greedy

Answer: c
Clarification: From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.

5. What is the output of the following program?

#include
int fibo(int n)
{
      if(n<=1)
	 return n;
      return fibo(n-1) + fibo(n-2);
}
int main()
{   
      int r = fibo(50000);
      printf("%d",r); 
      return 0;
}

a) 1253556389
b) 5635632456
c) Garbage value
d) Runtime error

Answer: d
Clarification: The value of n is 50000. The function is recursive and it’s time complexity is exponential. So, the function will be called almost 2⁵⁰⁰⁰⁰ times. Now, even though NO variables are stored by the function, the space required to store the addresses of these function calls will be enormous. Stack memory is utilized to store these addresses and only a particular amount of stack memory can be used by any program. So, after a certain function call, no more stack space will be available and it will lead to stack overflow causing runtime error.

6. What is the space complexity of the recursive implementation used to find the nth fibonacci term?
a) O(1)
b) O(n)
c) O(n²)
d) O(n³)

Answer: a
Clarification: The recursive implementation doesn’t store any values and calculates every value from scratch. So, the space complexity is O(1).

7. Consider the following code to find the nth fibonacci term:

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   __________
  	   __________
       return curFib

Complete the above code.
a)

prevFib = curFib
curFib = curFib

b)

prevFib = nextFib
curFib = prevFib

c)

prevFib = curFib
curFib = nextFib

d)

prevFib = nextFib
nextFib = curFib

Answer: c
Clarification: The lines, prevFib = curFib and curFib = nextFib, make the code complete.

8. What is the time complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

a) O(1)
b) O(n)
c) O(n²)
d) Exponential
Answer: b
Clarification: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

9. What is the space complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

a) O(1)
b) O(n)
c) O(n²)
d) Exponential
Answer: a
Clarification: To calculate the nth term, we just store the previous term and the current term and then calculate the next term using these two terms. It takes a constant space to store these two terms and hence O(1) is the answer.

10. What will be the output when the following code is executed?

#include
int fibo(int n)
{
      if(n==0)
         return 0;
      int i;
      int prevFib=0,curFib=1;
      for(i=1;i<=n-1;i++)
      {
           int nextFib = prevFib + curFib;
	   prevFib = curFib;
           curFib = nextFib;
      }
      return curFib;
}
int main()
{
      int r = fibo(10);  
      printf("%d",r);
      return 0;
}

a) 34
b) 55
c) Compile error
d) Runtime error
View Answer

Answer: b
Clarification: The output is the 10th fibonacci number, which is 55.

11. Consider the following code to find the nth fibonacci term using dynamic programming:

1. int fibo(int n)
2.   int fibo_terms[100000]  //arr to store the fibonacci numbers
3.   fibo_terms[0] = 0
4.   fibo_terms[1] = 1
5.		
6.   for i: 2 to n
7.	 fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.   return fibo_terms[n]

Which property is shown by line 7 of the above code?
a) Optimal substructure
b) Overlapping subproblems
c) Both overlapping subproblems and optimal substructure
d) Greedy substructure
View Answer

Answer: a
Clarification: We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.

12. Consider the following code to find the nth fibonacci term using dynamic programming:

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

Which technique is used by line 7 of the above code?
a) Greedy
b) Recursion
c) Memoization
d) Overlapping subproblems

Answer: c
Clarification: Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.

13. What is the time complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

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

Answer: b
Clarification: To calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

14. What is the space complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

int fibo(int n)
        int fibo_terms[100000]  //arr to store the fibonacci numbers
        fibo_terms[0] = 0
	fibo_terms[1] = 1
 
	for i: 2 to n
		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
 
	return fibo_terms[n]

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

Answer: b
Clarification: To calculate the nth term, we store all the terms from 0 to n – 1. So, it takes O(n) space.

15. What will be the output when the following code is executed?

#include
int fibo(int n)
{
      int i;
      int fibo_terms[100];
      fibo_terms[0]=0;
      fibo_terms[1]=1;
      for(i=2;i<=n;i++)
          fibo_terms[i] = fibo_terms[i-2] + fibo_terms[i-1];
      return fibo_terms[n];
}
int main()
{
      int r = fibo(8);
      printf("%d",r);
      return 0;
}

a) 34
b) 55
c) Compile error
d) 21

Answer: d
Clarification: The program prints the 8th fibonacci term, which is 21.

and Answers.