GATE CSE 2021 SET-1
Q1.
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?Q2.
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?Q3.
Consider the following three functions. f_1=10^n\; f_2=n^{\log n}\;f_3=n^{\sqrt {n}} Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?Q4.
Consider a computer system with a byte-addressable primary memory of size 2^{32} \text{ bytes}. Assume the computer system has a direct-mapped cache of size 32 KB (1 KB = 2^{10} \text{ bytes}), and each cache block is of size 64 bytes. The size of the tag field is __________ bits.Q5.
Consider the following expression.\lim_{x\rightarrow-3}\frac{\sqrt{2x+22}-4}{x+3} The value of the above expression (rounded to 2 decimal places) is ___________.Q6.
There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: The fastest computer gets the toughest job and the slowest computer gets the easiest job. Every computer gets at least one job. The number of ways in which this can be done is ___________.Q7.
Suppose that L_1 is a regular language and L_2 is a context-free language. Which one of the following languages is NOT necessarily context-free?Q8.
Consider the following context-free grammar where the set of terminals is \{a,b,c,d,f\}.\begin{array}{lll} S & \rightarrow & d \: a \: T \mid R \: f \\ T & \rightarrow & a \: S \: \mid \: b \: a \: T \: \mid \epsilon \\ R & \rightarrow & c \: a \: T \: R \: \mid \epsilon \end{array} The following is a partially-filled LL(1) parsing table. Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?Q9.
Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _____________ milliseconds.Q10.
Consider the following ANSI C program. #include < stdio.h > int main() { int i, j, count; count=0; i=0; for (j=-3; j < =3; j++) { if (( j > = 0) && (i++)) count = count + j; } count = count +i; printf("%d", count); return 0; }Which one of the following options is correct?