Consider the following recursive function.
Int function (int x, int y) {
If (y <= 0) return x;
return function (y, x%y);
}
The above recursive function computes ______.
Consider x = 10 and y = 25
CASE1:
If (y <= 0) return x; // 25<=0 (false)
return function (y, x%y); return function(25, 10)
CASE 2:
x = 25, y= 10
If (y <= 0) return x; // 10<=0 (False)
return function (y, x%y); // return function (10, 5)
CASE 3:
x =10, y =5
If (y <= 0) return x; // 5<=0 (false)
return function (y, x%y); //return function(5, 0)
CASE 4:
x = 5, y =0
If (y <= 0) return x; // condition true, return 5
return function (y, x%y);
Output = 5
Which is greatest common divisor of 10 and 25.
So, given program computes GCD of x and y
A stack can be implemented using two queues. Let stack to be implemented be ‘x’ and queues used to implement be ‘a’ and ‘b’.
Method 1 (By push operation)
This method makes sure that the newly entered element is always at the front of ‘a’, so that pop operation just dequeues from ‘a’. ‘b’ is used to put every new element at front of ‘b’.
Method 2 (By making pop operation costly)
In a push operation, the new element is always enqueued to a. In pop() operation, if b is empty then all the elements except the last, are moved to b. Finally, the last element is dequeued from a and returned.
Therefore Option 2 is correct
Concept:
Explanation:
A recursive problem like the Tower of Hanoi can be rewritten using system stack or user-defined stack
Recurrence relation of tower of Hanoi: T(n) = 2T(n - 1) + 1
Additional Information
Number of moves required for n disc in a Tower of Hanoi is 2n – 1 = 27 – 1 = 127.
Stack underflow happens when one tries to pop (remove) an item from the stack when nothing is actually there to remove.
Answer: Option 2
Explanation:
- For implementing recursive calls, Stack (LIFO) is required. Because for each call to the function, the caller function's temporary variables need to be pushed into the stack so that at the time of backtracking variables are easily accessible.
for example:
Consider the following Fibonacci example Where fib5 make a call to fib4 then fib5 will be pushed into the stack and then fib4 make a call to fib3, fib4 will be pushed into the stack and so on. and when fib1 and fib0 complete then backtracks to fib3 reusing the variable of fib3 which are stored in the stack.
Additional Information
Hash Table:
A hash table is a data structure that is used to store keys/value pairs. It uses a hash function to compute an index into an array in which an element will be inserted or searched. By using a good hash function, hashing can work well. Under reasonable assumptions, the average time required to search for an element in a hash table is O(1).
Queue:
The queue is FIFO (First in First out) data structure i.e. the first element that is added to the queue is the first one to be removed. Elements are always added to the back (Rear) and removed from the front.
Binary Tree:
A Binary tree consists of nodes which are having data part and a pointer pointing to the left subtree and a right pointer pointing to the right subtree.
If a tree is empty, it is represented by a null pointer.
Total MCQS : 128
gradeTotal MCQS : 37
gradeTotal MCQS : 133
gradeTotal MCQS : 166
gradeTotal MCQS : 165
gradeTotal MCQS : 61
gradeTotal MCQS : 133
gradeTotal MCQS : 120
gradeTotal MCQS : 7
gradeTotal MCQS : 36
gradeTotal MCQS : 7
gradeTotal MCQS : 175
gradeTotal MCQS : 2533
gradeTotal MCQS : 9
gradeTotal MCQS : 11
grade191 Points
54 Points
53 Points
52 Points
49 Points