GATE 2008 CSE & IT
97 questions across 1 session
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
Let X be a random variable following normal distribution with mean + 1 and variance 4. Let Y be another normal variable with mean - 1 and variance unknown. If $$P\,(X\, \le \, - 1)...
A sample space has two events A and B such that probabilities $$P\,(A\, \cap \,B)\, = \,1/2,\,\,P(\overline A )\, = \,1/3,\,\,P(\overline B )\, = \,1/3$$. What is P $$P\,(A\, \cup...
Which of the following is TRUE?
Which of the following are true? I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can...
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers...
Consider The Following Relational Scheme Student ( school-id, sch-roll-no , sname, saddress) School ( school-id , sch-name, sch-address, sch-phone) Enrolment ( school-id, sch-roll-...
Consider The Following Relational Scheme Student ( school-id, sch-roll-no , sname, saddress) School ( school-id , sch-name, sch-address, sch-phone) Enrolment ( school-id, sch-roll-...
Which of the following is/are true of the auto-increment addressing mode? $${\rm I}.\,\,\,$$ It is useful in creating self-relocating code $${\rm II}.\,\,\,$$ If it is included in...
A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is u...
The data blocks of a very large file in the Unix file system are allocated using
What is printed by the following C program? #include < stdio.h > int f(int x, int *py, int **ppz) { int y, z; **ppz += 1; z = **ppz; *py += 2; y = *py; x += 3; return x + y + z; }...
If $$P$$, $$Q$$, $$R$$ are Boolean variables, then $$(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$$ simplifies to
Let $$R\left( {A,\,B,\,C,\,D,E,P,G} \right)$$ be a relational schema in which the following functional dependencies are known to hold: $$AB \to CD,\,\,DE \to P,\,\,C \to E.\,\,P \t...
Consider the following relational schemes for a library database. Book ( Title, Author, Catalog_ no, Publisher, Year, Pr ice ) Collection ( Title, Author, Catalog no ) With in the...
$$\mathop {\lim }\limits_{x \to \infty } {{x - \sin x} \over {x + \cos \,x}}\,\,Equals$$
For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to
Let $$R\left( {A,B,C,D} \right)$$ be a relational schema with the following functional dependencies: $$A \to B,\,\,B \to C,\,\,C \to D$$ and $$D \to B.$$ The decomposition of $$R$$...
Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys 43 36 92 87 11 4 71 1...
The following system of equations $${x_1}\, + \,{x_2}\, + 2{x_3}\, = 1$$ $${x_1}\, + \,2 {x_2}\, + 3{x_3}\, = 2$$ $${x_1}\, + \,4{x_2}\, + a{x_3}\, = 4$$ has a unique solution. The...
$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be partitioned into two edge-disjoint spanning trees. Which of the following in NOT true for $$G$$?
Which of the following are true? I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can...
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contains no consecutive $$0s$$. Which of the following recurrences does $${x_n}$$ satisfy?
Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned....
The following code is to run on a pipelined processor with one branch delay slot $$\eqalign{ & {{\rm I}_1}:\,\,ADD\,\,{R_2}\,\, \leftarrow \,\,{R_7} + {R_8} \cr & {{\rm I}_2}:\,\,S...
Some code optimizations are carried out on the intermediate code because
Which of the following is/are true of the auto increment addressing mode? $$1.$$ It is useful in creating self relocating code $$2.$$ If it is included in an Instruction Set Archit...
A set of Boolean connectives is functionally complete if all Boolean function can be synthesized using those, Which of the following sets of connectives is NOT functionally complet...
If $$P, Q, R$$ are subsets of the universal set $$U$$, then $$\left( {P \cap Q \cap R} \right) \cup \left( {{P^c} \cap Q \cap R} \right) \cup {Q^c} \cup {R^c}$$ is
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighb...
Choose the correct option to fill ? 1 and ? 2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character....
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 II...
For inclusion to hold between two cache levels $$L1$$ and $$L2$$ in a multilevel cache hierarchy, which of the following are necessary? $$1.$$ $$L1$$ must be a write-through cache...
Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that the studies mathematics the next day is 0.6....
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
The total number of keys required for a set of n individuals to be able to communicate with each other using secret key and public key crypto-systems, respectively are:
Which of the following are NOT true in a pipelined processor? $$1.$$ Bypassing can handle all RAW hazards $$2.$$ Register renaming can eliminate all register carried WAR hazards $$...
$$P$$ and $$Q$$ are two propositions. Which of the following logical expressions are equivalent? $${\rm I}.$$ $${\rm P}\, \vee \sim Q$$ $${\rm I}{\rm I}.$$ $$ \sim \left( { \sim {\...
In an instruction execution pipeline, the earliest that the data $$TLB$$ (Translation Look aside Buffer) can be accessed is
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve $$3{x^4} - 16{x^3} + 24{x^2} + 37$$ is
If $$M$$ is a square matrix with a zero determinant, which of the following assertion(s) is (are) correct? $$S1$$ : Each row of $$M$$ can be represented as a linear combination of...
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 II...
Which of the following tuple relational calculus expression(s) is/are equivalent to $$\forall t \in r \left(P\left(t\right)\right)$$? I. $$\neg \exists t \in r \left(P\left(t\right...
For all delayed conditional branch instructions, irrespective of whether the condition evaluate true or false,
Which of the following must be true for the $$RFE$$ (Return From Exception) instruction on a general purpose processor? $$1.$$ It must be a trap instruction $$2.$$ It must be a pri...
Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 * f1(n - 2)); } int f2(int n){ int i; int X[N], Y[N], Z[N]; X[0] = Y[...
How many distinct BSTs can be constructed with 3 distinct keys?
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a 1 ,a 2 ,a 3 ,…,a n } and positive integer W, is there a subset of S whose elements sum to W...
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the...
In the $$IEEE$$ floating point representation the hexadecimal value $$0\, \times \,00000000$$ corresponds to
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i =...
Consider the following C functions: int f1(int n){ if(n == 0 || n == 1){ return n; } return (2 * f1(n - 1) + 3 * f1(n - 2)); } int f2(int n){ int i; int X[N], Y[N], Z[N]; X[0] = Y[...
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a 1 ,a 2 ,a 3 ,…,a n } and positive integer W, is there a subset of S whose elements sum to W...
The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An al...
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i =...
You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine the unique binary search tree that has P as its post order tr...
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Add a node $$v$$ to $$G$$ and make it adjacent to each odd degree vertex of $$G$$. The resultant graph...
Which of the following is the negation of $$$\left[ {\forall x,\alpha \to \left( {\exists y,\beta \to \left( {\forall u,\exists v,\gamma } \right)} \right)} \right]?$$$
A computer on a 10 Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2 Mbps. It is initially filled to capacity with 16 Megabits. What is the max...
Which of the following statements is true for every planar graph on $$n$$ vertices?
Let fsa and $$pda$$ be two predicates such that fsa$$(x)$$ means $$x$$ is a finite state automation, and pda$$(y)$$ means that $$y$$ is a pushdown automation. Let $$equivalent$$ be...
The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows: P(s): s = s-1; if s < 0 then wait; V(s) : s = s-1; ifs <= 0 then wakeup a pr...
If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is
The exponent of $$11$$ in the prime factorization of $$300!$$ is
When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation $$$T\left( n \right) = \sqrt 2 T\left( {n/2} \right) + \sqrt n ,\,\,T\left( 1 \right) = 1$$$ evaluates to
If $$\,\,\,\,f\,\,\,\,\left( x \right)$$ is defined as follows, what is the minimum value of $$f\,\left( x \right)$$ for $$x \in \left( {0,2} \right)$$ ? $$$f\left( x \right) = \le...
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighb...
The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. MBCAFHPYK KAMCBYPFH MABCKYFPH Pick the true...
A clustering index is defined on the fields which are of type
Let R and S be two relations with the following schema R ( P , Q , R1, R2, R3) S ( P , Q , S1, S2) Where {P, Q} is the key for both schemas. Which of the following queries are equi...
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to determine the unique binary search tree that has P as its posto...
The value of $$\int\limits_0^3 {\int\limits_0^x {\left( {6 - x - y} \right)dxdy\,\,\,} } $$ is _____.
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contain no consecutive $$0s$$. The value of $${x_5}$$ is
Which of the following describes a handle (as applicable to LR-parsing) appropriately?
What is the probability that in a randomly choosen group of r people at least three people have the same birthday?
Which of the following system calls results in the sending of SYN packets?
In the slow start phase of the TCP congestion control algorithm, the size of the congestion window
How many of the following matrices have an eigen value $$1$$? $$\left[ {\matrix{ 1 & 0 \cr 0 & 0 \cr } } \right],\,\,\left[ {\matrix{ 0 & 1 \cr 0 & 0 \cr } } \right],\,\,\left[ {\m...
What is the maximum size of data that the application layer can pass on to the TCP layer below?
Consider the following three schedules of transactions T 1 , T 2 and T 3 . [ Notation: In the following NYO represents the action Y (R for read, W for write) performed by transact...
A process executes the following code for (i = 0; i < n; i + +) fork ( ); The total number of child processes created is
A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket( ), a bind( ) and a listen( ) syst...
If $$P, Q, R$$ are Boolean variables, then $$\left( {P + \overline Q } \right)$$ $$\left( {P.\overline Q + P.R} \right)\left( {\overline P .\overline R + \overline Q } \right)$$ Si...
Which of the following first order formulae is logically valid? Here $$\alpha \left( x \right)$$ is a first order formulae with $$x$$ as a free variable, and $$\beta $$ is a first...
In how many ways can $$b$$ blue balls and $$r$$ red balls be distributed in $$n$$ distinct boxes?
The use of multiple register windows with overlap causes a reduction in the number of memory accesses for $$1.\,\,\,\,$$ Function locals and parameters $$2.\,\,\,\,$$ Register save...
If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?
Which of the following are decidable? $$1.$$ Whether the intersection of two regular languages is infinite $$2.$$ Whether a given context-free language is regular $$3.$$ Whether tw...
Which of the following statements are true? $$1.$$ Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa $$2.$$ All ε-productions can be removed...
Match the following List-$${\rm I}$$ with List - $${\rm II}$$ List-$${\rm I}$$ $$E)$$ Checking that identifiers are declared before their $$F)$$ Number of formal parameters in the...
Which of the following statement is false?
Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?
Consider the following functions: F(n) = 2 n G(n) = n! H(n) = n logn Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?