GATE 2017 CSE & IT

Consider the following functions from positive integers to real numbers : $10, \sqrt{n}, n, \log _2 n, \frac{100}{n}$. The CORRECT arrangement of the above functions in increasing...

Consider the following table : Algorithms Design Paradigms (P) Kruskal (ii) Greedy (Q) Quicksort (i) Divide and Conquer (R) Floyd–Warshall (iii) Dynamic Programming Match the algor...

The statement $(\neg p) \Rightarrow(\neg q)$ is logically equivalent to which of the statements below? I. $\quad p \Rightarrow q$ II. $q \Rightarrow p$ III. $(\neg q) \vee p$ IV. $...

After Rajendra Chola returned from his voyage to Indonesia, he ______ to visit the temple in Thanjavur.

Research in the workplace reveals that people work for many reasons ___________.

Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali. Srinivas is sitting to the right of Arul. Which of the following pairs ar...

Find the smallest number $y$ such that $y \times 162$ is a perfect cube.

"The hold of the nationalist imagination on our colonial past is such that anything inadequately or improperly nationalist is just not history." Which of the following statements b...

Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her...

The expression $\frac{(x+y)-|x-y|}{2}$ is equal to :

Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes...

Consider the first-order logic sentence $F: \forall x(\exists y R(x, y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$? I. $\quad \exists y(...

Let $T$ be a binary search tree with 15 nodes. The minimum and maximum possible heights of $T$ are : Note : The height of a tree with a single node is 0.

The $n$-bit fixed-point representation of an unsigned real number $X$ uses $f$ bits for the fraction part. Let $i=n-f$. The range of decimal values for $X$ in this representation i...

Let $${c_1},.....,\,\,{c_n}$$ be scalars, not all zero, such that $$\sum\limits_{i = 1}^n {{c_i}{a_i} = 0} $$ where $${{a_i}}$$ are column vectors in $${R^{11}}.$$ Consider the set...

A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place....

Let $$A$$ be $$n\,\, \times \,\,n$$ real valued square symmetric matrix of rank $$2$$ with $$\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {A_{ij}^2 = 50.} } $$ Consider the followi...

The probability that a $k$-digit number does NOT contain the digits 0, 5, or 9 is :

Let $$X$$ be a Gaussian random variable with mean $$0$$ and variance $${\sigma ^2}$$ . Let $$Y=max(X,0)$$ where $$max(a, b)$$ is the maximum of $$a$$ and $$b$$. The median of $$Y$$...

The value of $$\mathop {\lim }\limits_{x \to 1} {{{x^7} - 2{x^5} + 1} \over {{x^3} - 3{x^2} + 2}}.$$

If the characteristic polynomial of a $$3 \times 3$$ matrix $$M$$ over $$R$$(the set of real numbers) is $${\lambda ^3} - 4{\lambda ^2} + a\lambda + 30.\,a \in R,$$ and one eigenva...

Let $$P = \left[ {\matrix{ 1 & 1 & { - 1} \cr 2 & { - 3} & 4 \cr 3 & { - 2} & 3 \cr } } \right]$$ and $$Q = \left[ {\matrix{ { - 1} & { - 2} & { - 1} \cr 6 & {12} & 6 \cr 5 & {10}...

$$P$$ and $$Q$$ are considering to apply for a job. The probability that $$P$$ applies for the job is $${1 \over 4},$$ the probability that $$P$$ applies for the job given that $$Q...

For any discrete random variable $$X,$$ with probability mass function $$P\left( {X = j} \right) = {p_j},$$ $${p_j}\,\, \ge 0,\,j \in \left\{ {0,..........,\,\,\,N} \right\},$$ and...

If a random variable $$X$$ has a Poisson distribution with mean $$5,$$ then the expectation $$E\left[ {{{\left( {X + 2} \right)}^2}} \right]$$ equals _________.

Consider a quadratic equation $${x^2} - 13x + 36 = 0$$ with coefficients in a base $$b.$$ The solutions of this equation in the same base $$b$$ are $$x=5$$ and $$x=6$$. Then $$b=$$...

If $$f\left( x \right)\,\,\, = \,\,\,R\,\sin \left( {{{\pi x} \over 2}} \right) + S.f'\left( {{1 \over 2}} \right) = \sqrt 2 $$ and $$\int_0^1 {f\left( x \right)dx = {{2R} \over \p...

The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is

Match the following: (P) static char var; (Q) m = malloc(10); m = NULL; (R) char *ptr[10]; (S) register int var1; (i) Sequence of memory locations to store addresses (ii) A variabl...

Match the algorithms with their time complexities: Algorithm (P) Towers of Hanoi with n disks (Q) Binary search given n sorted numbers (R) Heap sort given n numbers at the worst ca...

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L₁ U L₂ is context-free. II. L₁ is context-free. III. L₁...

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: (P) Syntax tree (Q) Character stream (R) Intermediate r...

Which of the following statements about parser is/are CORRECT? I. Canonical LR is more powerful than SLR. II. SLR is more powerful than LALR. III. SLR is more powerful than Canonic...

Which of the following is/are shared by all the threads in a process? I. Program counter II. Stack III. Address space IV. Registers

In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed? I. Contiguous II. Linked III. Indexed

Consider the following statements about the routing protocols, Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) in an IPv4 network. I: RIP uses distance vecto...

If $f(x) = R \sin (\frac{\pi x}{2}) + S$, $f' (\frac{1}{2}) = \sqrt{2}$ and $\int_0^1 f(x)dx = \frac{2R}{\pi}$, then the constants R and S are, respectively

Let p, q, r denote the statements "It is raining", "It is cold", and "It is pleasant", respectively. Then the statement "It is not raining and it is pleasant, and it is not pleasan...

Given the following binary number in 32-bit (single precision) IEEE-754 format: 00111110011011010000000000000000. The decimal value closest to this floating-point number is

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two externa...

Consider the following function implemented in C: void printxy(int x, int y) { int *ptr; x = 0; ptr = &x; y = *ptr; *ptr = 1; printf("%d,%d",x,y); } The output of invoking printxy...

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph belo...

Identify the language generated by the following grammar, where S is the start variable. S → XY X → aX | a Y → aYb | ε

An ER model of a database consists of entity types A and B. These are connected by a relationship R which does not have its own attribute. Under which one of the following conditio...

Consider socket API on a Linux machine that supports connected UDP sockets. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the f...

Consider the following tables T1 and T2. In table T1, P is the primary key and Q is the foreign key referencing R in table T2 with on-delete cascade and on-update cascade. In table...

The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is _________.

Consider the set $X = \{a,b,c,d,e\}$ under the partial ordering $R = \{(a,a), (a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e), (c,c), (c,e),(d,d),(d,e),(e,e)\}$. The Hasse diagram of the...

Let $P = \begin{bmatrix} 1 & 1 & -1 \\ 2 & -3 & 4 \\ 3 & -2 & 3 \end{bmatrix}$ and $Q = \begin{bmatrix} -1 & -2 & -1 \\ 6 & 12 & 6 \\ 5 & 10 & 5 \end{bmatrix}$ be two matrices. The...

$G$ is an undirected graph with $n$ vertices and 25 edges such that each vertex of $G$ has degree at least 3. Then the maximum possible value of $n$ is _________.

Consider a quadratic equation x² - 13x + 36 = 0 with coefficients in a base b. The solutions of this equation in the same base b are x = 5 and x = 6. Then b =

The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = {w1aw2 | w1, w2 ∈ {a, b}*, |w1| = 2, |w2| ≥ 3} is

P and Q are considering to apply for a job. The probability that P applies for the job is $\frac{1}{4}$, the probability that P applies for the job given that Q applies for the job...

If w, x, y, z are Boolean variables, then which one of the following is INCORRECT?

Given f(w, x, y, z) = ∑m (0,1,2,3,7,8,10) + Σd (5,6,11,15), where d represents the don't-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS)...

In a two-level cache system, the access times of L1 and L2 caches are 1 and 8 clock cycles, respectively. The miss penalty from the L2 cache to main memory is 18 clock cycles. The...

Consider the recurrence function T(n) = { 2T(√n) + 1, n > 2; 2, 0 < n ≤ 2. Then T(n) in terms of Θ notation is

For any discrete random variable X, with probability mass function P(X = j) = pj, Pj ≥ 0, j∈ {0,...,N}, and $\sum_{j=0}^{N} p_j = 1$, define the polynomial function $g_x(z) = \sum_...

Consider the following expression grammar G: E -> E - T | T T -> T + F | F F -> (E) | id Which of the following grammars is not left recursive, but is equivalent to G?

A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below: Process | Current Allocation | Maximum Requirement...

Consider a binary code that consists of only four valid codewords as given below: 00000, 01011, 10101, 11110 Let the minimum Hamming distance of the code be p and the maximum numbe...

Consider two hosts X and Y, connected by a single direct link of rate 10^6 bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2 ×...

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variables x, y, q and r are all unsigned int. ```c while (r >= y) { r = r - y...

Consider the following C function. ```c int fun(int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j < n; j += i) { printf("%d %d",i,j); } } } ``` Time complexity of fun in...

Let δ denote the transition function and $\hat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: Then $\hat{\delta}(q_2,...

Consider the following languages. $L_1 = \{a^p \mid p \text{ is a prime number}\}$ $L_2 = \{a^n b^m c^{2m} \mid n \ge 0, m \ge 0\}$ $L_3 = \{a^n b^n c^{2n} \mid n \ge 0\}$ $L_4 = \...

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine...

The next state table of a 2-bit saturating up-counter is given below. Q1 Q0 | Q1+ Q0+ 0 0 | 0 1 0 1 | 1 0 1 0 | 1 1 1 1 | 1 1 The counter is built as a synchronous sequential circu...

Consider the following snippet of a C program. Assume that swap(&x, &y) exchanges the contents of x and y. int main() { int array[] = {3, 5, 1, 4, 6, 2}; int done = 0; int i; while...

Two transactions T₁ and T₂ are given as T1:r1(X)w1(X)r1(Y)w1(Y) T2:r2(Y)w2(Y)r2(Z)w2(Z) where ri (V) denotes a read operation by transaction Tᵢ on a variable V and wᵢ(V) denotes a...

The read access times and the hit ratios for different caches in a memory hierarchy are as given below. Cache | Read access time (in nanoseconds) | Hit ratio ---|---|--- I-cache |...

If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)^2] equals _________.

In a B+ tree, if the search-key value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B+ tree is _________.

A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below: Character | Probability P | 0.22...

Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes hav...

If the characteristic polynomial of a 3 × 3 matrix M over R (the set of real numbers) is λ³ – 4λ² + αλ + 30, a ∈ R, and one eigenvalue of M is 2, then the largest among the absolut...

Consider a machine with a byte addressable main memory of 2^32 bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with thi...

Consider the following C Program. #include int main() { int m = 10; int n, nl; n = ++m; n1 = m++; n--; --nl; n -= nl; printf("%d", n); return 0; } The output of the program is ____...

Consider the following C Program. #include #include int main() { char* c = "GATECSIT2017"; char* p = c; printf("%d", (int)strlen(c+2[p]-6[p]-1)); return 0; } The output of the prog...

Choose the option with words that are not synonyms.

Saturn is __________ to be seen on a clear night with the naked eye.

There are five buildings called V, W, X, Y and Z in a row (not necessarily in that order). V is to the West of W. Z is to the East of X and the West of V. W is to the West of Y. Wh...

A test has twenty questions worth 100 marks in total. There are two types of questions. Multiple choice questions are worth 3 marks each and essay questions are worth 11 marks each...

There are 3 red socks, 4 green socks and 3 blue socks. You choose 2 socks. The probability that they are of the same colour is

"We lived in a culture that denied any merit to literary works, considering them important only when they were handmaidens to something seemingly more urgent - namely ideology. Thi...

There are three boxes. One contains apples, another contains oranges and the last one contains both apples and oranges. All three are known to be incorrectly labelled. If you are p...

X is a 30 digit number starting with the digit 4 followed by the digit 7. Then the number X³ will have

The number of roots of $e^x + 0.5x^2 - 2 = 0$ in the range $[-5, 5]$ is

An air pressure contour line joins locations in a region having the same atmospheric pressure. The following is an air pressure contour plot of a geographical region. Contour lines...