# Recent questions tagged gate2014-cse-set2

1
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________
2
SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below: select * from R where a in (select S.a from S) select R.* from R, S where R.a ... R,(select distinct a from S) as S1 where R.a=S1.a select R.* from R,S where R.a=S.a and is unique R
3
Which one of the following Boolean expressions is NOT a tautology? $((\,a\,\to\,b\,)\,\wedge\,(\,b\,\to\,c))\,\to\,(\,a\,\to\,c)$ $(\,a\,\to\,c\,)\,\to\,(\,\sim b\,\to\,(a\,\wedge\,c))$ $(\,a\,\wedge\,b\,\wedge\,c)\,\to\,(\,c\vee\,a)$ $a\,\to\,(b\,\to\,a)$
4
The number of distinct minimum spanning trees for the weighted graph below is _____
5
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
6
Consider the following relation on subsets of the set $S$ of integers between $1$ and $2014$. For two distinct subsets $U$ and $V$ of $S$ we say $U\:<\:V$ if the minimum element in the symmetric difference of the two sets is in $U$. Consider the following two statements: $S1$: There ... $S2$ are true $S1$ is true and $S2$ is false $S2$ is true and $S1$ is false Neither $S1$ nor $S2$ is true
7
The number of distinct positive integral factors of $2014$ is _____________
8
The probability that a given positive integer lying between $1$ and $100$ (both inclusive) is NOT divisible by $2$, $3$ or $5$ is ______ .
9
The product of the non-zero eigenvalues of the matrix is ____ $\begin{pmatrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix}$
10
In the Newton-Raphson method, an initial guess of $x_0= 2$ is made and the sequence $x_0,x_1,x_2\:\dots$ is obtained for the function $0.75x^3-2x^2-2x+4=0$ Consider the statements $x_3\:=\:0$ The method converges to a solution in a finite number of iterations. Which of the following is TRUE? Only I Only II Both I and II Neither I nor II
11
The value of a $\text{float}$ type variable is represented using the single-precision $\text{32-bit}$ floating point format of $IEEE-754$ standard that uses $1$ $\text{bit}$ for sign, $\text{8 bits}$ for biased exponent and $\text{23 bits}$ for the ... $−14.25$. The representation of $X$ in hexadecimal notation is $C1640000H$ $416C0000H$ $41640000H$ $C16C0000H$
12
If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected? Width of tag comparator Width of set index decoder Width of way selection multiplexer Width of processor to main memory data bus
13
In designing a computer's cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context? A smaller block size implies better spatial locality A smaller block size implies a smaller ... smaller block size implies a larger cache tag and hence lower cache hit time A smaller block size incurs a lower cache miss penalty
14
Consider the C function given below. int f(int j) { static int i = 50; int k; if (i == j) { printf("something"); k = f(i); return 0; } else return 0; } Which one of the following is TRUE? The function returns $0$ for all values of $j$. The function prints ... of $j$. The function returns $0$ when $j = 50$. The function will exhaust the runtime stack or run into an infinite loop when $j = 50$.
15
Suppose a stack implementation supports an instruction $REVERSE$, which reverses the order of elements on the stack, in addition to the $PUSH$ and $POP$ instructions. Which one of the following statements is TRUE (with respect to this modified stack)? A queue ... $DEQUEUE$ takes a single instruction. A queue can be implemented where both $ENQUEUE$ and $DEQUEUE$ take a single instruction each.
16
Consider the following function. double f(double x){ if( abs(x*x - 3) < 0.01) return x; else return f(x/2 + 1.5/x); } Give a value $q$ (to $2$ decimals) such that $f(q)$ will return $q$:_____.
17
Consider the expression tree shown. Each leaf represents a numerical value, which can either be $0$ or $1$. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.
18
Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
19
Consider two strings $A$="qpqrr" and $B$="pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$. Then $x +10y=$ ___.
20
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $\text{ has at least as many occurrences of }$ $(000)'$ $\text{s as}$ ... one of the following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
21
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$ ... $L$ is: decidable and recursively enumerable undecidable but recursively enumerable undecidable and not recursively enumerable decidable but not recursively enumerable
22
For a C program accessing $\mathbf{X[i] [j] [k]}$, the following intermediate code is generated by a compiler. Assume that the size of an integer is $32$ bits and the size of a character is $8$ bits. t0 = i ∗ 1024 t1 = j ∗ 32 t2 = k ∗ 4 t3 = t1 + t0 t4 = t3 + t2 t5 = X[t4] ... $\mathbf{X}$ is declared as "char $\mathbf{X[4] [32] [8]}$ . $\mathbf{X}$ is declared as "char $\mathbf{X[32] [16] [2]}$ .
23
A computer has twenty physical page frames which contain pages numbered $101$ through $120$. Now a program accesses the pages numbered $\text{1, 2, ..., 100}$ in that order, and repeats the access sequence THRICE. Which one of the following page ... faults as the optimal page replacement policy for this program? Least-recently-used First-in-first-out Last-in-first-out Most-recently-used
24
Three processes $A$, $B$ and $C$ each execute a loop of $100$ iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU milliseconds and then initiates a single I/O operation that lasts for $t_{io}$ ... uses a time slice of $50$ milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.
25
Consider the procedure below for the Producer-Consumer problem which uses semaphores: semaphore n = 0; semaphore s = 1; void producer() { while(true) { produce(); semWait(s); addToBuffer(); semSignal(s); semSignal(n); } } void consumer() { while(true) { semWait(s) ... semaphore s when the buffer is empty. The starting value for the semaphore $n$ must be $1$ and not $0$ for deadlock-free operation.
26
Consider a join (relation algebra) between relations $r(R)$ and $s(S)$ using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R))<size(s(S)) , the join will have fewer number of ... $r(R)$ and $s(S)$ is more than 0.5. join selection factor between $r(R)$ and $s(S)$ is less than 0.5.
27
Consider the following schedule S of transactions $T1, T2, T3, T4:$ ... serializable but not recoverable S is not conflict-serializable but is recoverable S is both conflict-serializable and recoverable S is neither conflict-serializable not is it recoverable
A graphical HTML browser resident at a network client machine $Q$ accesses a static HTML webpage from a HTTP server $S$. The static HTML page has exactly one static embedded image which is also at $S$. Assuming no caching, which one of the following is correct about the ... A single HTTP request from $Q$ to $S$ is sufficient, and this is possible without any TCP connection between $Q$ and $S$
An IP machine $Q$ has a path to another $IP\ machine\ H$ via three $IP\ routers \ R1, R2,$ and $R3$. $Q-R1-R2-R3-H$ $H$ acts as an $HTTP\ server$, and $Q$ connects to $H$ via $HTTP$ and downloads a file. Session layer encryption is used, with $DES$ as the shared ... and $I4$ can an intruder learn through sniffing at $R2$ alone? Only $I1$ and $I2$ Only $I1$ Only $I2$ and $I3$ Only $I3$ and $I4$
Consider the store and forward packet switched network given below. Assume that the bandwidth of each link is $10^6$ bytes / sec. A user on host $A$ sends a file of size $10^3$ bytes to host $B$ through routers $R1$ and $R2$ in three different ways. In the first case a single ... third case respectively. Which one of the following is CORRECT? $T1<T2<T3$ $T1>T2>T3$ $T2=T3, T3<T1$ $T1=T3, T3> T2$