# Recent posts tagged gate2017

2
Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$? $\{q_0,q_1,q_2\}$ $\{q_0,q_1\}$ $\{q_0,q_1,q_2,q_3\}$ $\{q_3\}$
3
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly $4$ nodes is $O(n^a\log^bn)$. Then the value of $a+10b$ is __________.
4
Consider a relation scheme $R = (A, B, C, D, E, H)$ on which the following functional dependencies hold: {$A \rightarrow B$, $BC \rightarrow D$, $E \rightarrow C$, $D \rightarrow A$}. What are the candidate keys R? $AE, BE$ $AE, BE, DE$ $AEH, BEH, BCH$ $AEH, BEH, DEH$
5
A $5$ stage pipelined CPU has the following sequence of stages: IF - instruction fetch from instruction memory RD - Instruction decode and register read EX - Execute: ALU operation for data and address computation MA - Data memory access - for write access, the register read ... clock cycles taken to complete the above sequence of instructions starting from the fetch of $I_1$? $8$ $10$ $12$ $15$
6
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})$
7
Which of the following problems is undecidable? Membership problem for CFGs Ambiguity problem for CFGs Finiteness problem for FSAs Equivalence problem for FSAs
8
Which of the following addressing modes are suitable for program relocation at run time? Absolute addressing Based addressing Relative addressing Indirect addressing I and IV I and II II and III I, II and IV
9
Consider the following $2-3-4$ tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree. What is the result of inserting $G$ in the above tree? None of the above
10
The following is a scheme for floating point number representation using 16 bits. Bit Position 15 14 .... 9 8 ...... 0 s e m Sign Exponent Mantissa Let s, e, and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the ... maximum difference between two successive real numbers representable in this system? $2^{-40}$ $2^{-9}$ $2^{22}$ $2^{31}$
11
A computer uses $32-bit$ virtual address, and $32-bit$ physical address. The physical memory is byte addressable, and the page size is $4$ $\text{kbytes}$ . It is decided to use two level page tables to translate from virtual address to physical ... entries that can be contained in each page? How many bits are available for storing protection and other information in each page table entry?
12
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates? $n$ $n-1$ $2n$ $\frac{n}{2}$
13
Which of the following is not a form of memory instruction cache instruction register instruction opcode translation look-a-side buffer
14
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______
15
A computer uses $46-bit$ virtual address, $32-bit$ physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table $(T1)$, which occupies exactly one page. Each entry of $T1$ stores the base address of a page of ... cache block size is $64$ bytes. What is the size of a page in $KB$ in this computer? $2$ $4$ $8$ $16$
16
Yess ~L is also not empty :). But would you like to shed some light on the the way you transform the RE's complement into L or ~L. The way I think both of them are NonRE is combination of some RE language and some NonRE language will always be NonRE unless their union is Universal!..isn't it correct?. this question seems to be way too much tricky!
17
I am still of the opinion that we cannot take only one inverter, since inverter is an input to the two different the AND gates A'C' and A'B'. Though, it is the same inverter that is used, but it is used twice with different combination of another input to ... . You are just calculating the number of inverters and number of gates(AND/OR) but not checking from where the input is coming/going to.
18
(a) is true. Ada supports in-out parameter passing, which is nothing other than call by value result (but Ada in GATE syllabus?) (b) Not true. (c) Most robust? I don't know what is meant by robust here. (d) Not true. (e) Not ... every occurrence of the formal paramater and hence efficiency will only be less. Reference: http://courses.cs.washington.edu/courses/cse341/03wi/imperative/parameters.html
19
Register renaming is done in pipelined processors: as an alternative to register allocation at compile time for efficient access to function parameters and local variables to handle certain kinds of hazards as part of address translation
20
The amount of ROM needed to implement a $4-bit$ multiplier is $64$ bits $128$ bits $1$ Kbits $2$ Kbits
To see more, click for the full list of questions or popular tags.