GATE 2017 Computer Science Set 1 Questions and Solutions

# Recent questions tagged gate2017-1

1
A cache memory unit with capacity of $N$ words and block size of $B$ words is to be designed. If it is designed as a direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ____________ bits.
2
Consider the expression $(a-1) * (((b+c)/3)+d)$. Let $X$ be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which only load and store instructions can have memory operands and arithmetic instructions can have only register or immediate operands. The value of $X$ is _____________ .
3
Consider a $2-$way set associative cache with $256$ blocks and uses $LRU$ replacement. Initially the cache is empty. Conflict misses are those misses which occur due to the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access ... $10$ times. The number of conflict misses experienced by the cache is _________ .
4
Instruction execution in a processor is divided into 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Operand fetch (OF), Execute (EX), and Write Back (WB). These stages take 5, 4, 20, 10 and 3 nanoseconds (ns) respectively. A pipelined ... . The speedup (correct to two decimal places) achieved by EP over NP in executing 20 independent instructions with no hazards is _________ .
5
Consider the C code fragment given below. typedef struct node { int data; node* next; } node; void join(node* m, node* n) { node* p = n; while(p->next != NULL) { p = p->next; } p->next = m; } Assuming that m and n point to valid NULL-terminated linked ... or append list m to the end of list n. cause a null pointer dereference for all inputs. append list n to the end of list m for all inputs.
6
Consider the following table: ... $(P) \leftrightarrow (i), (Q) \leftrightarrow (ii), (R) \leftrightarrow (iii)$
7
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 order of asymptotic complexity is: $\log_{2}n$, $\frac{100}{n}$, $10$, $\sqrt{n}$, $n$ $\frac{100}{n}$, $10$ ... $\frac{100}{n}$, $\sqrt{n}$, $\log_{2}n$, $n$ $\frac{100}{n}$, $\log_{2}n$, $10$, $\sqrt{n}$, $n$
8
Consider the first-order logic sentence $F:\forall x(\exists yR(x,y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$? $\exists y(\exists xR(x,y))$ $\exists y(\forall xR(x,y))$ $\forall y(\exists xR(x,y))$ $¬\exists x(\forall y¬R(x,y))$ IV only I and IV only II only II and III only
9
The statement $\left ( ¬p \right ) \Rightarrow \left ( ¬q \right )$ is logically equivalent to which of the statements below? $p \Rightarrow q$ $q \Rightarrow p$ $\left ( ¬q \right ) \vee p$ $\left ( ¬p \right ) \vee q$ I only I and IV only II only II and III only
10
Consider the following C program. #include<stdio.h> #include<string.h> void printlength(char *s, char *t) { unsigned int c=0; int len = ((strlen(s) - strlen(t)) > c) ? strlen(s) : strlen(t); printf("%d\n", len); } void main() { char *x = "abc"; ... that $strlen$ is defined in $string.h$ as returning a value of type $size\_t$, which is an unsigned int. The output of the program is __________ .
11
The output of executing the following C program is _______________ . #include<stdio.h> int total(int v) { static int count = 0; while(v) { count += v&1; v >>= 1; } return count; } void main() { static int x=0; int i=5; for(; i>0; i--) { x = x + total(i); } printf("%d\n", x); }
12
A contour line joins locations having the same height above the mean sea level. The following is a contour plot of a geographical region. Contour lines are shown at $25$ m intervals in this plot. If in a flood, the water level rises to $525$ m, which of the villages $P, Q, R, S, T$ get submerged? $P, Q$ $P, Q, T$ $R, S, T$ $Q, R, S$
13
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 the colour white. Gulab and Neel like all the colours. In how many different ways can they choose the shirts so that no one has a shirt with a colour he or she dislikes? $21$ $18$ $16$ $14$
14
The expression $\large \frac{(x+y) - |x-y|}{2}$ is equal to : The maximum of $x$ and $y$ The minimum of $x$ and $y$ $1$ None of the above
15
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 immediate right. None of the women are right-handed. The number of women at the table is $2$ $3$ $4$ Cannot be determined
16
"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 best reflects the author's opinion? Nationalists are highly imaginative. History is viewed through the filter of nationalism. Our colonial past never happened. Nationalism has to be both adequately and properly imagined.
17
The probability that a $k$-digit number does NOT contain the digits $0, 5,$ or $9$ is $0.3^{k}$ $0.6^{k}$ $0.7^{k}$ $0.9^{k}$
18
Find the smallest number $y$ such that $y \times 162$ is a perfect cube. $24$ $27$ $32$ $36$
19
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 are seated opposite each other? Rahul and Murali Srinivas and Arul Srinvas and Murali Srinivas and Rahul
20
Research in the workplace reveals that people work for many reasons _______________ . money beside beside money money besides besides money
21
After Rajendra Chola returned from his voyage to Indonesia, he ________ to visit the temple in Thanjavur. was wishing is wishing wished had wished
22
Consider a RISC machine where each instruction is exactly $4$ bytes long. Conditional and unconditional branch instructions use PC-relative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to ... $i,$ then the decimal value of the Offset is ____________ .
23
Let $A$ be an array of $31$ numbers consisting of a sequence of $0$'s followed by a sequence of $1$'s. The problem is to find the smallest index $i$ such that $A\left [i \right ]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ____________.
24
The number of integers between $1$ and $500$ (both inclusive) that are divisible by $3$ or $5$ or $7$ is ____________ .
25
Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below. ... $T2 \leftarrow CR\div T1$ The number of rows in $T2$ is ______________ .
26
The values of parameters for the Stop-and-Wait ARQ protocol are as given below: Bit rate of the transmission channel = $1$ Mbps. Propagation delay from sender to receiver = $0.75$ ms. Time to process a frame = $0.25$ ms. Number of bytes in ... efficiency (expressed in percentage) of the Stop-and-Wait ARQ protocol for the above parameters is _____________ (correct to $2$ decimal places).
27
In a RSA cryptosystem, a participant $A$ uses two prime numbers $p = 13$ and $q = 17$ to generate her public and private keys. If the public key of $A$ is $35$, then the private key of $A$ is __________ .
Consider the following grammar: stmt $\rightarrow$ if expr then expr else expr; stmt | $0$ expr $\rightarrow$ term relop term | term term $\rightarrow$ id | number id $\rightarrow$ a | b | c number $\rightarrow [0-9]$ where relop is a relational operator (e.g.. $<$ ... example. the program if $e_1$ then $e_2$ else $e_3$ has $2$ control flow paths. $e_1 \rightarrow e_2$ and $e_1 \rightarrow e_3$.
In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let $TS(T_{1})$ and $TS(T_{2})$ be the timestamps of transactions $T_{1}$ and $T_{2}$ respectively. Besides, $T_{1}$ holds a lock on the ... , but not starvation-free. The database system is starvation-free, but not deadlock-free. The database system is neither deadlock-free nor starvation-free.
Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus. {$t$ | $\exists$u $\in$ ... v[DeptId]))} Which of the above queries are safe? I and II only I and III only II and III only I, II and III