GATE CSE 2008

Exam Held on Thu Jan 01 1970 00:00:00 GMT+0000 (Coordinated Universal Time)
Click View All Questions to see questions one by one or you can choose a single question from below.

Algorithms

You are given the post order traversal, P, of a binary search tree on the n elem...
Consider the following functions: F(n) = 2<sup>n</sup><br/> G(n) = n!<br/> H(n) ...
The minimum number of comparisons required to determine if an integer appears mo...
The most efficient algorithm for finding the number of connected components in a...
Consider the following C functions: <pre><code>int f1(int n){ if(n == 0 || n ==...
The Breadth First Search algorithm has been implemented using the queue data str...
Consider the following C functions: <pre><code>int f1(int n){ if(n == 0 || n ==...
We have a binary heap on n elements and wish to insert n more elements (not nece...
Consider the Quicksort algorithm. Suppose there is a procedure for finding a piv...
<img class="question-image" src="https://gateclass.static.cdn.examgoal.com/p0VID...
The subset-sum problem is defined as follows. Given a set of n positive integers...
The subset-sum problem is defined as follows. Given a set of n positive integers...
Consider the following C program that attempts to locate an element x in an arra...
Consider the following C program that attempts to locate an element x in an arra...
The subset-sum problem is defined as follows: <br/>Given a set S of n positive ...

Compiler Design

Which of the following are true? <p>I. A programming language which does not pe...
Which of the following describes a handle (as applicable to LR-parsing) appropri...
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and o...
Some code optimizations are carried out on the intermediate code because

Computer Networks

If a class B network on the Internet has a subnet mask of 255.255.248.0, what is...
What is the maximum size of data that the application layer can pass on to the T...
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...
A client process P needs to make a TCP connection to a server process S. Conside...
A computer on a 10 Mbps network is regulated by a token bucket. The token bucket...
The total number of keys required for a set of n individuals to be able to commu...

Computer Organization

In the $$IEEE$$ floating point representation the hexadecimal value $$0\, \times...
For inclusion to hold between two cache levels $$L1$$ and $$L2$$ in a multilevel...
The following code is to run on a pipelined processor with one branch delay slot...
In an instruction execution pipeline, the earliest that the data $$TLB$$ (Transl...
Which of the following are NOT true in a pipelined processor? <br>$$1.$$ Bypassi...
The use of multiple register windows with overlap causes a reduction in the numb...
Which of the following must be true for the $$RFE$$ (Return From Exception) inst...
Which of the following is/are true of the auto increment addressing mode? <br>$$...
For all delayed conditional branch instructions, irrespective of whether the con...

Data Structures

The following C function takes a single-linked list of integers as a parameter a...
Which of the following is TRUE?
The following three are known to be the preorder, inorder and postorder sequence...
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the fo...
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the fo...
How many distinct BSTs can be constructed with 3 distinct keys?
You are given the postorder traversal, P, of a binary search tree on the n eleme...
Consider the following sequence of nodes for the undirected graph given below. <...
Consider a hash table of size 11 that uses open addressing with linear probing. ...

Database Management System

Consider the following $$ER$$ diagram <img class="question-image" src="https://i...
Consider the following $$ER$$ diagram <img class="question-image" src="https://i...
Consider the following relational schemes for a library database. Book ( Title, ...
Let $$R\left( {A,B,C,D} \right)$$ be a relational schema with the following func...
Let $$R\left( {A,\,B,\,C,\,D,E,P,G} \right)$$ be a relational schema in which th...
<p>Consider The Following Relational Scheme</p> <p>Student (<u>school-id, sch-ro...
<p>Consider The Following Relational Scheme</p> <p>Student (<u>school-id, sch-ro...
<p>Which of the following tuple relational calculus expression(s) is/are equival...
Let R and S be two relations with the following schema <p>R (<u>P</u>, <u>Q</u>,...
Consider the following three schedules of transactions T<sub>1</sub>, T<sub>2</s...
A clustering index is defined on the fields which are of type
Consider a file of 16384 records. Each record is 32 bytes long and its key field...

Digital Logic

Given $${f_1},$$ $${f_3},$$ and $$f$$ in canonical sum of products form (in deci...
If $$P, Q, R$$ are Boolean variables, then $$\left( {P + \overline Q } \right)$$...
In the Karnaugh map shown below, $$X$$ denotes a don’t care term. What is the m...

Discrete Mathematics

A set of Boolean connectives is functionally complete if all Boolean function ca...
A sample space has two events A and B such that probabilities $$P\,(A\, \cap \,...
Aishwarya studies either computer science or mathematics everyday. If she studie...
Let X be a random variable following normal distribution with mean + 1 and varia...
If $$P$$, $$Q$$, $$R$$ are Boolean variables, then $$(P + \bar{Q}) (P.\ba...
Let fsa and $$pda$$ be two predicates such that fsa$$(x)$$ means $$x$$ is a fini...
Which of the following first order formulae is logically valid? Here $$\alpha \l...
$$P$$ and $$Q$$ are two propositions. Which of the following logical expressions...
Which of the following is the negation of $$$\left[ {\forall x,\alpha \to \lef...
What is the probability that in a randomly choosen group of r people at least th...
If $$P, Q, R$$ are subsets of the universal set $$U$$, then <br>$$\left( {P \ca...
The following system of equations <br> $${x_1}\, + \,{x_2}\, + 2{x_3}\, = 1$$ <b...
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nin...
$$\mathop {\lim }\limits_{x \to \infty } {{x - \sin x} \over {x + \cos \,x}}\,\,...
If $$\,\,\,\,f\,\,\,\,\left( x \right)$$ is defined as follows, what is the mini...
A point on a curve is said to be an extremum if it is a local minimum or a local...
What is the chromatic number of the following graph? <img class="question-image"...
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contain n...
Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contains ...
The exponent of $$11$$ in the prime factorization of $$300!$$ is
In how many ways can $$b$$ blue balls and $$r$$ red balls be distributed in $$n$...
When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation $$$T\left( ...
Which of the following statements is true for every planar graph on $$n$$ vertic...
$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Ad...
$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be...
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of...
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of...
How many of the following matrices have an eigen value $$1$$? <br>$$\left[ {\mat...
If $$M$$ is a square matrix with a zero determinant, which of the following asse...
The value of $$\int\limits_0^3 {\int\limits_0^x {\left( {6 - x - y} \right)dxdy\...

Operating Systems

A process executes the following code <pre><code class='c'>for (i = 0; i < n; i...
Which of the following is/are true of the auto-increment addressing mode? <br>$$...
The P and V operations on counting semaphores, where s is a counting semaphore, ...
A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a ...
The data blocks of a very large file in the Unix file system are allocated using...
For a magnetic disk with concentric circular tracks, the seek latency is not lin...
Which of the following is NOT true of deadlock prevention and deadlock avoidance...

Programming Languages

Which of the following are true? <p>I. A programming language which does not per...
Choose the correct option to fill ? 1 and ? 2 so that the program below prints a...
What is printed by the following C program? <pre><code>#include < stdio.h > int ...

Theory of Computation

Given below are two finite state automata ($$ \to $$ indicates the start state a...
Match the following $$NFAs$$ with the regular expressions they correspond to <i...
Which of the following are regular sets? <img class="question-image" src="https...
Which of the following statement is false?
Which of the following statements are true? <br>$$1.$$ Every left-recursive gra...
Match the following List-$${\rm I}$$ with List - $${\rm II}$$ <p><b>List-$${\rm ...
Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| ...
If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is
Which of the following are decidable? <br>$$1.$$ Whether the intersection of two...

EXAM MAP

Joint Entrance Examination

JEE Advanced JEE Main

Graduate Aptitude Test in Engineering

GATE CSE GATE EE GATE ECE GATE ME GATE CE GATE PI GATE IN