GATE 2013 CSE & IT
45 questions across 1 session
An index is clustered, if
A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, s...
Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction $$(FI),$$ Decode Instruction $$(DI),$$ Fetch Operand $$(FO),$$ Execute Instructio...
Which one of the following functions is continuous at $$x = 3$$?
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
Using public key cryptography, X adds a digital signature σ to message M, encrypts, and sends it to Y, where it is decrypted. Which one of the following sequences of keys is used f...
A $$RAM$$ chip has a capacity of $$1024$$ words of $$8$$ bits each $$\left( {1K \times 8} \right).$$ The number of $$2 \times 4$$ decoders with enable line needed to construct a $$...
A Binary operation $$ \oplus $$ on a set of integers is defined as $$x$$ $$ \oplus $$ $$y$$ $$ = {x^2} + {y^2}$$. Which one of the following statements is TRUE about $$ \oplus $$ ?
The procedure given below is required to find and replace certain characters inside an input character string supplied in array $$A.$$ The characters to be replaced are supplied in...
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on sem...
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
A certain computation generates two arrays a and b such that a[i]=f(i)for 0 ≤ i < n and b[i] = g (a[i] )for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent pr...
Which one of the following expressions does NOT represent exclusive NOR of $$x$$ and $$y?$$
Consider the following relational schema. Students( rollno: integer, sname: string) Courses( courseno: integer, cname: string) Registration( rollno: integer, courseno: integer, per...
The line graph $$L(G)$$ of a simple graph $$G$$ is defined as follows: $$\,\,\,\,$$There is exactly one vertex $$v(e)$$ in $$L$$(G)$$ for each edge $$e$$ in $$G$$ $$\,\,\,\,$$ For...
Consider a hypothetical processor with an instruction of type $$LW$$ $$R1, 20(R2),$$ which during execution reads a $$32$$-bit word from memory and stores it in a $$32$$-bit regist...
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production ( i.e., of type $$A \to \varepsilon $$ and $$A...
Relation $$R$$ has eight attribution $$ABCDEFGH.$$ Fields of $$R$$ contain only atomic values. $$F = \left\{ {CH \to G,\,\,A \to BC,\,B \to CFH,\,\,E \to A,\,\,F \to EG} \right\}$$...
Determine the maximum length of cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable t...
Which of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether there e...
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object in to a binary search tree of n nodes?
Consider the following sequence of micro-operations $$\eqalign{ & \,\,\,\,\,\,\,\,\,\,\,\,\,MBR\,\,\,\,\,\,\, \leftarrow PC \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,MAR\,\,\,\,\,\,\, \lefta...
Consider the following function: int unknown(int n) { int i, j, k = 0; for (i = n/2; i <= n; i++) for (j = 2; j <= n; j = j * 2) k = k + n/2; return k; } The return value of the fu...
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty and m > 0) { Deque...
Consider the following two sets of LR(1) items of an LR(1) grammar. $$\eqalign{ & X \to c.X,\,c/d\,\,\,\,\,\,\,\,X \to c.X,\$ \cr & X \to .cX,c/d\,\,\,\,\,\,\,\,X \to .cX,\$ \cr &...
Which of the following does not equal $$\left| {\matrix{ 1 & x & {{x^2}} \cr 1 & y & {{y^2}} \cr 1 & z & {{z^2}} \cr } } \right|?$$
Relation $$R$$ has eight attribution $$ABCDEFGH.$$ Fields of $$R$$ contain only atomic values. $$F = \left\{ {CH \to G,\,\,A \to BC,\,B \to CFH,\,\,E \to A,\,\,F \to EG} \right\}$$...
In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total length is 400 and the fragment offset value is 300. The position of the datagram, the sequence numb...
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the...
The procedure given below is required to find and replace certain characters inside an input character string supplied in array $$A.$$ The characters to be replaced are supplied in...
The transport layer protocols used for real time multimedia, file transfer, DNS and email, respectively are
What is the logical translation of the following statement? "None of my friends are perfect."
What is the return value of f (p, p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is p...
Which one of the following is NOT logically equivalent to $$\neg \exists x\left( {\forall y\left( \alpha \right) \wedge \left( {\forall z\left( \beta \right)} \right)} \right)?$$
The smallest integer that can be represented by an $$8$$-bit number in $$2's$$ complement form is
Suppose p is the number of cars per minute passing through a certain road junction between 5PM and 6PM and p has a poisson distribution with mean 3. What is the probability of obse...
Which one of the following functions is continuous at $$x=3?$$
Consider an undirected random$$^ \circ $$ graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered...
In a $$k$$-way set associative cache, the cache is divided into $$v$$ sets, each of which consists of $$k$$ lines. The lines of a set are placed in sequence one after another. The...
Which of the following statements is/are FALSE ? $$1.$$ For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine $$2.$$ Turing recognizab...
Consider the languages $${L_1} = \phi $$ and $${L_2} = \left\{ a \right\}.$$ Which one of the following represents $${L_1}\,L_2^ * UL_1^ * ?$$
Consider the following languages $${L_1} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0} \right.} \right\}$$ $${L_2} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0,p \ne r} \right.}...
Which of the following is/are undecidable? $$1.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \Phi ?$$ $$2.$$ $$G$$ is a $$CFG.$$ Is $$L\left( G \right) = \sum {{}^ * } ?$$ $$3.$$...