GATE CSE 2020: Revision Quiz 1 (App update required to attempt this test)
Attempt now to get your rank among 418 students!
Question 1
Consider the following function: int function(int n, int m){ if(n%m == 0) return m; return function(m,n%m); } What is the number of recursive calls made by the above function considering the assumption that n>=m?
Question 2
This will print --------.
Question 3
The postfix expression to be evaluated as 30 is
Question 4
Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
Question 5
Given below three graphs G1, G2 and G3 The number of bridges in G1, G2 and G3 are x, y and z respectively. Find the value of |x-y+z| ____________.
Question 6
There are two segments supported by the hardware. Address spaces are small (1KB), and the amount of physical memory on the system is 16KB. Assume that the segment-0 base register has the value 1KB, and its bounds (size) is set to 300 bytes; this segment grows upward. Assume the segment 1-base register has the value 5KB in it, and its bound is also 300; this segment grows downward (the negative direction). Assume we have the following program :
int main()
{
void *ptr = 20;
while (ptr<= 1024)
{
int x = (int *) *ptr; // LINE 1: read what is at address ’ptr’
ptr = ptr + 20; // LINE 2: increment ’ptr’ to a new address
}
}
This program will run for __________ iterations before crashing due to a segmentation fault ?
Question 7
Suppose c=⟨c[0],…,c[k−1]⟩is an array of lengthk, where all the entries are from the set{0,1}. For any positive integers αand n,consider the following pseudo code. DOSOMETHING(c,a,n) If k=4, c=⟨1,0,1,1⟩, a =2and n=8, then the output of DOSOMETHING(c,a,n)is___________.
Question 8
The height of a tree is the length of the longest root to leaf path in it. The maximum and minimum number of nodes in a binary tree of height 4 is.
Question 9
Given that the preorder traversal of binary tree is (1,2,3). Find the number of different binary trees are possible whose postorder traversal is (3,2,1) for the given preorder traversal?
Question 10
Which of the options are correct with respect to Tower of Hanoi problem ?
Question 11
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to the same value ii) 1471, 6171 has to the same value iii) All elements hash to the same value iv) Each element hashes to a different value
Question 12
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
Question 13
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
Question 14
Consider the following graph G.
Modified BFS traversal on G applied as follows Assume starting vertex is ‘a’. At any level (breadth), vertices are visited in alphabetic order. In above graph G, after visiting vertex ‘a’, the order of vertices visited in G are c, d and e. It works same as BFS except the restriction on order of vertices visited. Which of the following is not a cross edge during given BFS traversal on G?
Question 15
Consider the divide and conquer algorithm to find the minimum and maximum number in an array of n integers. Find the number of comparisons required to find these two numbers of the total number of integers in the array is 100 _______.
