## GATE CSE 2004

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

The tightest lower bound on the number of comparisons, in the worst case, for co...
What does the following algorithm approximate? <br/>(Assume m > 1, $$\in > 0$$...
Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is ...
The time complexity of the following C function is (assume n > 0) <pre><code cla...
The recurrence equation<br/> T(1) = 1<br/> T(n) = 2T(n - 1)+n, $$n \ge 2$$<br/> ...
The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given or...
Suppose we run Dijkstra’s single source shortest-path algorithm on the following...
The tightest lower bound on the number of comparisons, in the worst case, for co...
The problems 3-SAT and 2-SAT are

## Compiler Design

<p>Which of the following grammar rules violate the requirements of an operator ...
<p>Consider the grammar with the following translation rules and E as the start ...
Consider the grammar rule $$E \to {E_1} - {E_2}$$ for arithmetic expressions. Th...

## Computer Networks

Choose the best matching between <b>Group 1</b> and <b>Group 2 </b>: <p><b>Gro...
A and B are the only two stations on an Ethernet. Each has a steady queue of fra...
Which of the following is NOT true with respect to a transparent bridge and a ro...
The routing table of a router is shown below: <img class="question-image" src="h...
<p>Consider three IP networks A, B and C. Host H<sub>A</sub> in networks A sends...
<p>Consider three IP networks A, B and C. Host H<sub>A</sub> in networks A sends...
A TCP message consisting of 2100 bytes is passed to IP for delivery across two n...
Suppose that the maximum transmit window size for a TCP connection is 12000 byte...
A sender is employing public key Cryptography to send a secret message to a rece...

## Computer Organization

What is the result of evaluating the following two expressions using three $$-$$...
$$A$$ $$4$$-bit carry look ahead adder, which adds two $$4$$-bit numbers, is des...
Consider a small two-way set-associative cache memory, consisting of four blocks...
A $$4$$-stage pipeline has the stage delays as $$150, 120,160$$ and $$140$$ nano...
Which of the following addressing modes are suitable for program relocation at r...
Consider the following program segment for a hypothetical $$CPU$$ having three ...
Consider the following program segment for a hypothetical $$CPU$$ having three ...
Which one of the following is true for a $$CPU$$ having a single interrupt reque...
How many $$8$$-bit characters can be transmitted per second over $$9600$$ baud s...
A Hard disk with a transfer rate of $$10Mbytes/second$$ is constantly transferri...
The microinstructions stored in the control memory of a processor have a width o...

## Data Structures

A single array A[1..MAXSIZE] is used to implement two stacks, The two stacks gro...
Two matrices M<sub>1</sub> and M<sub>2</sub> are to be stored in arrays A and B ...
The best data structure to check whether an arithmetic expression has balanced p...
Assume that the operators +, -, ×, are left associative and ^ is right associati...
A program attempts to generate as many permutation as possible of the string “ab...
A circularly linked list is used to represent a Queue. A single variable p is us...
Let P be a singly linked list, Let Q be the pointer to an intermediate node x in...
Level order traversal of a rooted tree can be done by starting from the root and...
The following numbers are inserted into an empty binary search tree in the given...
Consider the following C program segment <pre><code class="c">struct CellNode{ ...
Consider the label sequences obtained by the following pairs of traversals on a ...
In a depth-first traversal of a graph G with n vertices,k edges are marked as tr...
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and t...
A program takes as input a balanced binary search tree with n leaf nodes and com...

## Database Management System

Consider the following entity relationship diagram $$(ERD),$$ where two entities...
The relation scheme student Performance (Name, CourseNo, RollNo, Grade) has the ...
A relation Empdt $$1$$ is defined with attributes empcode (unique), name, street...
Consider the following relation schema pertaining to a students database: <pre><...
<p>The employee information in a company is stored in the relation</p> Employee ...
A relational database contains two table <b>student</b> and <b>department</b> in...
Consider two tables in a relational database with columns and rows as follows: <...
Let R<sub>1</sub> (<u>A,</u> B, C) and R<sub>2</sub> (<u>D,</u> E) be two relati...
Consider the relation <b>Student (<u>name,</u> sex, marks)</b>, where the primar...
Which level of locking provides the highest degree of concurrency in a relationa...
Consider the following schedule S of transactions T1 and T2: <img class="questio...
The order of an internal node in a B<sup>+</sup> tree index is the maximum numbe...
Consider a table T in a relational database with a key field K. A B-tree of orde...

$${73_x}$$ (in base $$-$$ $$x$$ number system) is equal to $${54_y}$$ (in base $... Let $$A=1111$$ $$1010$$ and $$B=0000$$ $$1010$$ be two $$8$$-bit $$2's$$ complem... The Boolean function $$x'y' +xy +x'y$$ is equivalent to Which are the essential prime implicants of the following Boolean function? $$F\... A circuit outputs a digit in the form of$$4$$bits.$$0$$is represented by$$0... Consider a multiplexer with $$X$$ and $$Y$$ as data inputs and $$Z$$ as control ... $$SR.$$ latch made by cross coupling two $$NAND$$ gates if $$S=R=0,$$ Then it wi... Consider the partial implementation of a $$2$$-bit counter using $$T$$ flip-flop... ## Discrete Mathematics Identify the correct translation into logical notation of the following assertio... Let $$a(x,y)$$, $$b(x,y)$$ and $$c(x,y)$$ be three statements with variables $$x... Let$$p, q, r$$and$$s$$be four primitive statements. Consider the following a... The following propositional statement is$$$\left( {P \to \left( {Q \vee R} \rig...
In a population of N families, 50% of the families have three children, 30% of t...
If a fair coin is tossed four times, what is the probability that two heads and ...
A point is randomly selected with uniform probability in the X-Y plane within th...
An examination paper has 150 multiple-choice questions of one mark each, with ea...
Two n bit binary stings, S1 and, are chosen randomly with uniform probability. T...
The following is the incomplete operation table of a 4-element group. <img class...
The inclusion of which of the following sets into <p> S = { {1, 2}, 1, 2, 3}, {...
Consider the binary relation: $$S = \left\{ {\left( {x,y} \right)|y = x + 1\,\,a... The number of different$$nxn$$symmetric matrices with each ele... Let$${R_1}$$be a relation from$$A = \left\{ {1,3,5,7} \right\}$$to$$B = \le...
In a class of 200 students, 125 students have taken Programming Language course,...
Let A, B, C, D be $$n\,\, \times \,\,n$$ matrices, each with non-zero determinat...
What values of x, y and z satisfy the following system of linear equations? $$\... What is the maximum number of edges in an acyclic undirected graph with$$n$$ve... Mala has a colouring book in which each English letter is drawn two times. She w... In how many ways can we distribute 5 distinct balls,$${B_1},{B_2},......,{B_5}... The recurrence equation <br>$$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$ <br>$$\,\,\... How many solutions does the following system of linear equations have? <br><br... The minimum number of colours required to colour the following graph, such that ... In an M$$ \times $$N matrix such that all non-zero entries are covered in$$a$$... If matrix$$X = \left[ {\matrix{ a & 1 \cr { - {a^2} + a - 1} & {1 - a} ... Let $$A$$ be and n$$\times$$n matrix of the folowing form. <img class="questio... How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n... Let$${G_1} = \left( {V,\,{E_1}} \right)$$and$${G_2} = \left( {V,\,{E_2}} \rig... What is the number of vertices in an undirected connected graph with $$27$$ edge... The number of different $$n \times n$$ symmetric matrices with each elements bei... ## Operating Systems Consider the following statements with respect to user-level threads and kernel-... Consider the following set of processes, with the arrival times and the $$CPU$$-... Consider a program $$P$$ that consists of two source modules $${M_1}$$ and $${M_... Which of the following addressing modes are suitable for program relocation at r... The minimum number of page frames that must be allocated to a running process in... Consider a System with a two-level paging scheme in which a regular memory acces... Consider an operating system capable of loading and executing a single sequentia... ## Programming Languages The goal of structured programming is to Choose the best matching between the programming style in <b>Group 1</b> and the... Consider the following C function: <pre><code>int f(int n) { static int i = 1; i... Consider the following C program <pre><code class="c">main ( ) { int x, y, m,... Consider the following C function: <pre><code class="c">void swap (int a, int b)... Consider the following C program segment: <pre><code>char p[20]; char *s = "stri... ## Theory of Computation The following finite state machine accepts all those binary strings in which the... Which of the following grammar rules violate the requirements of an operator gra... Consider the following grammar$$G:$$<br>$$\eqalign{ & S \to bS\,\left| {\,a... The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}... Let$$M = \left( {K,\,\sum {,\,F,\,\Delta ,\,s,\,F} } \right)\$ be a pushdown au...

### 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