GATE 2010 CSE & IT
40 questions across 1 session
A system uses FIFO policy for page replacement. It has $$4$$ pages frames with no pages loaded to begin with. The system first accesses $$100$$ distinct pages in some order and the...
Consider the set $$S = \left\{ {1,\,\omega ,\,{\omega ^2}} \right\},$$ where $$\omega $$ and $${{\omega ^2}}$$, are cube roots of unity. If $$ * $$ denotes the multiplication opera...
Which data structure in a compiler is used for managing information about variables and their attributes?
The minters expansion of $$f\left( {P,Q,R} \right) = PQ + Q\overline R + P\overline R $$ is
Which languages necessarily need heap allocation in the runtime environment?
What is the value of $$\mathop {\lim }\limits_{n \to \infty } {\left[ {1 - {1 \over n}} \right]^{2n}}?$$
A main memory unit with a capacity of $$4$$ megabytes is built using $$1M \times 1$$-bit $$DRAM$$ chips. Each $$DRAM$$ chip has $$1K$$ rows of cells with $$1K$$ cells in each row....
$$P$$ is a $$16$$-bit signed integer. The $$2's$$ complement representtation of $$P$$ is $${\left( {F87B} \right)_{16}}$$ . The $$2's$$ complement representation of $$8{}^ * \,P$$...
Let $$G$$ $$\,\,\,\,\, = \,\,\,\left( {V,\,\,\,\,\,E} \right)$$ be a graph. Define $$\xi \left( G \right) = \sum\limits_d {{i_d} \times } {\mkern 1mu} d,$$ where $${{i_d}}$$ is the...
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence...
Consider the following matrix $$A = \left[ {\matrix{ 2 & 3 \cr x & y \cr } } \right]\,\,$$ If the eigen values of $$A$$ are $$4$$ and $$8$$, then
Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1...
The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some...
Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same net mask N. Which of the values of N given below should not be used...
What is the possible number of reflexive relations on a set $$5$$ elements?
Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1...
The following program is to be tested for statement coverage: begin if $$\left( {a = \,\, = b} \right)\,\,\left\{ {S1;\,\,exit;} \right\}$$ else if $$\left( {c = \,\, = d} \right)\...
What does the following program print? #include < stdio.h > void f (int *p, int *q) { p = q; *p = 2; } int i = 0, j = 1; int main ( ){ f(&i, &j); printf ("%d %d \ n", i, j); return...
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4...
Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock? I. 2-phase locking II. Time-stamp ordering
Two alternate packages A and B are available for processing a database having 10 k records. Package A requires 0.0001n 2 time units and package B requires $$10n.\log _{10}^n$$ time...
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4...
The grammar $$S \to aSa\,|\,\,bS\,|\,\,c$$ is
Consider the following matrix $$A = \left[ {\matrix{ 2 & 3 \cr x & y \cr } } \right].$$ If the eigen values of $$A$$ are $$4$$ and $$8$$ then
Which languages necessarily need heap allocation in the runtime environment?
The following functional dependencies hold for relations R(A, B, C) and S(B, D, E): $$$\eqalign{ & B \to A \cr & A \to C \cr} $$$ The relation R contains 200 tuples and the relatio...
Which one of the following is not a client-server application?
A relational schema for a train reservation database is given below: Passenger ( pid, pname, age) Reservation (pid, cass, tid) Table: Passenger pid pname age 0 'Sachin' 65 1 'Rahul...
Suppose the predicate $$F(x,y,t)$$ is used to represent the statements that person $$x$$ can fool person $$y$$ at time $$t$$. Which one of the statements below expresses best the m...
Consider a company that assembles computers. The probability of a faulty assembly of any computer is P. The company therefore subjects each computer to a testing process. This give...
A system has n resources R 0 ,.....,R n-1 , and k processes P 0 ,.....,P k-1 . The implementation of the resource request logic of each process P i , is as follows: if (i%2==0) { i...
What is the probability that divisor of $${10^{99}}$$ is a multiple of $${10^{96}}$$ ?
One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?
Which of the following statements are true? $${\rm I}.$$ Shortest remaining time first scheduling may cause starvation $${\rm II}.$$ Preemptive scheduling may cause starvation $${\...
Consider a B + - tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
The program below uses six temporary variables a, b, c, d, e, f. a = 1 b = 10 c = 20 d = a + b e = c + d f = c + e b = c + e e = b + f d = 5 + e return d + f Assuming that all oper...
Consider the languages $$$\eqalign{ & {L_1} = \left\{ {{0^i}{1^j}\,\left| {i \ne j} \right.} \right\},\,{L_2} = \left\{ {{0^i}{1^j}\,\left| {i = j} \right.} \right\}, \cr & {L_3} =...
Let $${L_1}$$ recursive language. Let $${L_2}$$ and $${L_3}$$ be languages that are recursively enumerable but not recursive. Which of the following statement is not necessarily tr...
Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1's} \right\},$$ i.e $$L$$ is the set of all bit strings with...
Let $$w$$ be any string of length $$n$$ in $${\left\{ {0,1} \right\}^ * }$$. Let $$L$$ be the set of all substrings of $$w.$$ What is the minimum number of states in a non-determin...