## GATE CSE 2015 Set 1

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

Match the following: <p><b>List 1</b></p> (P) Prim’s algorithm for minimum spann...
Which one of the following is the recurrence equation for the worst case time co...
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4....
An algorithm performs $${\left( {\log N} \right)^{1/2}}$$ find operations, N ins...
Consider the following C function. <pre><code class='c'>int fun1 (int n) { ...
The graph shown below has 8 edges with distinct integer edge weights. The minimu...

## Compiler Design

Which one of the following is TRUE at any valid state in shift-reduce parsing?
A variable x is said to be live at a statement $${S_i}$$ in a programif the foll...
The least number of temporary variables required to create a three-address code ...

## Computer Networks

Consider a LAN with four nodes S<sub>1</sub>, S<sub>2</sub>, S<sub>3</sub> and S...
Suppose that the stop-and-wait protocol is used on a link with a bit rate of 64 ...
Which one of the following fields of an IP header is NOT modified by a typical I...
Suppose two hosts use a TCP connection to transfer a large file. Which of the fo...
In one of the pairs of protocols given below, both the protocols can use multipl...
Suppose that everyone in a group of N people wants to communicate secretly with ...

## Computer Organization

Consider a disk pack with a seek time of 4 milliseconds and rotational speed of ...
Consider a non-pipelined processor with a clock rate of 2.5 gigahertz and averag...

## Data Structures

The height of a tree is the length of the longest root-to-leaf path in it. The m...
Which of the following is/are correct inorder traversal sequence(s) of binary se...
What are the worst-case complexities of insertion and deletion of a key in a bin...
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it ...

## Database Management System

A file is organized so that the ordering of data records is the same as or close...
SELECT operation in SQL is equivalent to
<p>Consider an Entity-Relationship (ER) model in which entity sets E<sub>1</sub>...
<p>Consider the following relation: </p> <p><b>Student</b></p> <style type="text...

## Digital Logic

Consider a 4-bit Johnson counter with an initial value of 0000. The counting seq...
<p>The binary operator $$\ne$$ is defined by the following truth table.</p> <s...
A positive edge-triggered D flip-flop is connected to a positive edge-triggered ...
<p>Consider the operations</p> $$f\left( {x,y,z} \right) = X'YZ + XY' + Y'Z'$$ ...

## Discrete Mathematics

Consider the following $$2 \times 2$$ matrix $$A$$ where two elements are unknow...
$$\,\,\mathop {\lim }\limits_{x \to \infty } \,{x^{1/x}}\,\,$$ is
$$\,\int\limits_{1/\pi }^{2/\pi } {{{\cos \left( {1/x} \right)} \over {{x^2}}}dx... If$$g(x)=1-x$$&$$h\left( x \right) = {x \over {x - 1}}\,\,$$then$$\,\,{{g\...
Given Set $$\,\,\,A = \left\{ {2,3,4,5} \right\}\,\,\,$$ and Set $$\,\,\,B = \le... The probabilities that a student passes in Mathematics, Physics and Chemistry ar... For a set A, the power set of A is denoted by 2<sup>A</sup>. If A = {5, {6}, {7}... In the LU decomposition of the matrix$$\left[ {\matrix{ 2 & 2 \cr 4 & 9...
Suppose L = { p, q, r, s, t } is a lattice represented by the following Hasse di...
$$\sum\limits_{x = 1}^{99} {{1 \over {x\left( {x + 1} \right)}}}$$ = __________...
Let G be a connected planar graph with 10 vertices. If the number of edges on ea...
Let $${a_n}$$ represent the number of bit strings of length n containing two con...

## General Aptitude

Didn't you buy _________ when you went shopping?
Which of the following combinations is incorrect?
The pie chart below has the breakup of the number of students from different dep...
Given set A = {2, 3, 4, 5} and Set B = {11, 12, 13, 14, 15}, two numbers are ran...
Which of the following options is the closest in meaning to the sentence below? ...
Based on the given statements, select the most appropriate option to solve the g...
The probabilities that a student passes in Mathematics, Physics and Chemistry ar...
Select the alternative meaning of the underlined part of the sentence. <p>The ch...
The given statement is followed by some courses of action. Assuming the statemen...
<p>The number of students in a class who have answered correctly, wrongly, or no...

## Operating Systems

A file is organized so that the ordering of data records is the same as or close...
The following two functions P1 and P2 that share a variable B with an initial va...
Consider a uniprocessor system executing three tasks T<sub>1</sub>, T<sub>2</sub...
Consider a main memory with five page frames and the following sequence of page ...
Suppose the following disk request sequence (track numbers) for a disk with 100 ...

## Programming Languages

The output of the following C program is__________. <pre><code class='c'> void f...
What is the output of the following C code? Assume that the address of x is 2000...
Consider the following pseudo code, where x and y are positive integers. <pre><c...

## Software Engineering

<p>Match the following:</p> <style type="text/css"> .tg {border-collapse:collap...
Consider the following C program segment. <pre><code class='c'>while(first <= la...

## Theory of Computation

<p>For any two languages L<sub>1</sub> and L<sub>2</sub> such that L<sub>1</sub>...
<img class="question-image" src="https://imagex.cdn.examgoal.com/NFARklqwJkxQqBC...
Consider the NPDA \left\langle {Q = \left\{ {{q_0},{q_1},{q_2}} \right\}} \rig...

## Web Technologies

Which of the following statements is/are FALSE? <p>I. XML overcomes the limitati...