# Recent activity by gatecse

1
Cohesion is an extension of: Abstraction concept Refinment concept Information hiding concept Modularity
2
Raman is confident of speaking English _______six months as he has been practising regularly_______the last three weeks during, for for, since for, in within, for
3
Express the complement of the following functions in sum of minterms form: a) F(a,b,c,d) = Σ (3,5,9,11,15) b)F(x,y,z) = Π (2,4,5,7)
4
Consider a fully associative cache with $8$ cache blocks (numbered $0-7$) and the following sequence of memory block requests: $4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7$ If LRU replacement policy is used, which cache block will have memory block $7$? $4$ $5$ $6$ $7$
5
6
Consider a system with a two-level paging scheme in which a regular memory access takes $150$ $nanoseconds$, and servicing a page fault takes $8$ $milliseconds$. An average instruction takes $100$ nanoseconds of CPU time, and two memory accesses. The TLB ... average instruction execution time? $\text{645 nanoseconds}$ $\text{1050 nanoseconds}$ $\text{1215 nanoseconds}$ $\text{1230 nanoseconds}$
7
If $A\oplus B=C$, then which one of the following is true? $A\oplus C=B$ $B\oplus C=B$ $A\oplus B\oplus C=0$ Both (A) and (B)
8
When searching for the key value $60$ in a binary search tree, nodes containing the key values $10, 20, 40, 50, 70, 80, 90$ are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value $60$? $35$ $64$ $128$ $5040$
9
The Fibonacci sequence is the sequence of integers 1, 3, 5, 7, 9, 11, 13 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 0, 1, 3, 4, 7, 11, 18, 29, 47 0, 1, 3, 7, 15
10
In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$
11
A 4-stage pipeline has the stage delays as $150$, $120$, $160$ and $140$ $nanoseconds$, respectively. Registers that are used between the stages have a delay of $5$ $nanoseconds$ each. Assuming constant clocking rate, the total time taken to process $1000$ data items ... will be: $\text{120.4 microseconds}$ $\text{160.5 microseconds}$ $\text{165.5 microseconds}$ $\text{590.0 microseconds}$
12
Suppose we are implementing quadratic probing with a Hash function, $Hash(y) = X$ $mode$ $100$. If an element with key $4594$ is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is : $2$ $3$ $9$ $97$
13
What is the output of the following $C$-program main() { printf("%d %d %d",size of (3.14f), size of (3.14), size of (3.141)); } 4 4 4 4 8 10 8 4 8 8 8 8
14
Context-free grammar can be recognized by finite state automation $2$- way linear bounded automata push down automata both (B) and (C)
15
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? Quicksort runs in $\Theta (n^2)$ time Bubblesort runs in $\Theta (n^2)$ time Mergesort runs in $\Theta (n)$ time Insertion sort runs in $\Theta (n)$ time I and II only I and III only II and IV only I and IV only
16
Consider a paging system that uses $1$-level page table residing in main memory and a TLB for address translation. Each main memory access takes $100$ ns and TLB lookup takes $20$ ns. Each page transfer to/from the disk takes $5000$ ns. Assume that the TLB hit ... is read from disk. TLB update time is negligible. The average memory access time in ns (round off to $1$ decimal places) is ___________
17
If $T_1 = O(1)$, give the correct matching for the following pairs: $\begin{array}{l|l}\hline \text{(M)$T_n = T_{n-1} + n$} & \text{(U)$T_n = O(n)$} \\\hline \text{(N)$T_n = T_{n/2} + n$} & \text{(V)$T_n = O(n \log n)$} \\\hline \text{(O)$T_n = T_{n/2} + n \log n$} & \text{(W)$T_n ... $\text{M-W, N-U, O-X, P-V}$ $\text{M-V, N-W, O-X, P-U}$ $\text{M-W, N-U, O-V, P-X}$
18
The following program main() { inc(); inc(); inc(); } inc() { static int x; printf("%d", ++x); } prints 012 prints 123 prints 3 consecutive, but unpredictable numbers prints 111
19
We consider the addition of two $2's$ complement numbers $b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by $c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out by $c_{out}$ ... $c_{out}\oplus c_{n-1}$ $a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$
20
The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon$ is: Unambiguous CFG Ambiguous CFG Not a CFG Deterministic CFG
21
What is the meaning of regular expression $\Sigma^*001\Sigma^*$? Any string containing ‘$1$’ as substring Any string containing ‘$01$’ as substring Any string containing ‘$011$’ as substring All string containing ‘$001$’ as substring
22
Which of the following is not a monotonically increasing grammar? (A) Context-sensitive grammar (B) Unrestricted grammar (C) Regular grammar (D) Context-free grammar
23
Consider a complete binary tree where the left and the right sub trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is: $\Omega(\log n)$ $\Omega(n\log n)$ $\Omega(n)$ $\Omega(n^2)$
24
The instruction format of a CPU is: \begin{array}{|c|c|c|} \hline \text {OP CODE} & \text{MODE}& \text{RegR} \\\hline \end{array}\begin{array}{|c||} \text {___one memory word___} \end{array} $\text{Mode}$ and $\text{RegR}$ together specify the ... (PC). What is the address of the operand? Assuming that is a non-jump instruction, what are the contents of PC after the execution of this instruction?
25
In a cache memory if total number of sets are ‘$s$’, then the set offset is: $2^8$ $\log_2s$ $s^2$ $s$
26
The logic expression for the output of the circuit shown in figure below is: $\overline{AC} + \overline{BC} +CD$ $\overline{A}C + \overline{B}C + CD$ $ABC +\overline {C}\; \overline{D}$ $\overline{A}\; \overline{B} + \overline{B}\; \overline{C} +CD$
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree ... described by which of the following? $\log_2 n$ $\log_{\frac{4}{3}} n$ $\log_3 n$ $\log_{\frac{3}{2}} n$
Let $I=\int(\sin\:x-\cos\:x)(\sin\:x+\cos\:x)^{3}dx$ and $K$ be a constant of integration. Then the value of $I$ is $(\sin\:x+\cos\:x)^{4}+K$ $(\sin\:x+\cos\:x)^{2}+K$ $-\frac{1}{4}(\sin\:x+\cos\:x)^{4}+K$ None of these
Consider the following relations $A, B$ and $C:$ ... of $A\cup B$ is the same as that of $A$. $(A\cup B)\bowtie _{A.Id > 40 \vee C.Id < 15} C$ $7$ $4$ $5$ $9$
prove that $x’ \oplus y = x \oplus y’ = (x \oplus y)’ = xy+x’y’$