GATE CSE 2007

## GATE CSE

Consider the following segment of C-code:
int j, n;
j=1;
while(j <= n)
j = j * 2;
The number of comparisons made in

View Question
Consider the DAG with $$V = \{1,2,3,4,5,6\}$$, shown below.
Which of the following is NOT a topological ordering?

View Question
Which of the following sorting algorithms has the lowest worst-case complexity?

View Question
What is the time complexity of the following recursive function?
int DoSomething(int n){
if(n <= 2)
return 1;

View Question
Consider the following C code segment:
int IsPrime(n){
int i, n;
for(i=2; i<=sqrt(n);i++){
if(n % i == 0){
pr

View Question
Consider the process of inserting an element into a Max Heap, where the Max
Heap is represented by an array. Suppose we

View Question
In the following C function, let n $$ \ge $$ m.
int gcd(n,m)
{
if (n % m == 0) return m;
n = n % m;
return gcd(m,n);
}
H

View Question
An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs t

View Question
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the follo

View Question
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight

View Question
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the averag

View Question
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most effic

View Question
Which one of the following is a top-down parser?

View Question
Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar
Whic

View Question
Consider the grammar with non-terminals N = { S, C, S1 }, terminals T = { a, b, i, t, e }, with S as the start symbol, a

View Question
Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol

View Question
Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol

View Question
In Ethernet when Manchester encoding is used, the bit rate is:

View Question
There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is

View Question
The message 11001001 is to be transmitted using the CRC polynomial x3 + 1 to protect it from errors. The message that sh

View Question
The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilomet

View Question
The address of a class B host is to be split into subnets with a 6-bit subnet number. What is the maximum number of subn

View Question
Which one of the following uses UDP as the transport protocol?

View Question
Match the following:
List - I
(P) SMTP
(Q) BGP
(R) TCP
(S) PPP
List - II
(1) Application layer
(2) Transport l

View Question
Consider the following two statements:
i. A hash function (these are often used for computing digital signatures) is an

View Question
The minimum positive integer p such that (3p modulo 17) = 1 is

View Question
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest up

View Question
In a look $$-$$ ahead carry generator, the carry generate function $${G_i}$$ and the carry propagate function $${P_i}$$

View Question
Consider a $$4$$-way set associative cache consisting of $$128$$ lines with a line size of $$64$$ words. The $$CPU$$ gen

View Question
Consider a machine with a byte addressable main memory of $${2^{16}}$$ bytes. Assume that a direct mapped data cache con

View Question
Consider a machine with a byte addressable main memory of $${2^{16}}$$ bytes. Assume that a direct mapped data cache con

View Question
Consider a pipelined processor with the following four stages
$$\,\,\,\,\,$$$$IF:$$ Instruction Fetch
$$\,\,\,\,\,$$$$ID

View Question
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:

View Question
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
Note

View Question
Consider the following C program:
#include
#define EOF -1
void push (int); /* push the argument on the stack */

View Question
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a bi

View Question
The maximum number of binary trees that can be formed with three unlabeled nodes is:

View Question
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder tra

View Question
Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
{
st

View Question
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 a

View Question
A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes

View Question
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m dif

View Question
Consider the following two statements:
i. A hash function (these are often used for computing digital signatures) is an

View Question
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table

View Question
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will

View Question
Which one of the following statements if FALSE?

View Question
Consider the table employee(empId, name, department, salary) and the two queries Q1, Q2 below. Assuming that department

View Question
Information about a collection of students is given by the relation studInfo(studId, name, sex). The relation enroll(stu

View Question
Consider a selection of the form σA ≤ 100(r), where r is a relation with 1000 tuples. Assume that the attribute values f

View Question
Consider the relation employee(name, sex, supervisorName) with name as the key, supervisorName gives the name of the sup

View Question
Consider the following relation schemas :
b-Schema = (b-name, b-city, assets)
a-Schema = (a-num, b-name, bal)
d-Schema =

View Question
Consider the following schedules involving two transactions. Which one of the following statements is TRUE?
S1: r1(X);

View Question
Consider the following two transactions: T1 and T2.
T1: read (A); T2: read (B);
read (B);

View Question
Consider the B+ tree in the adjoining figure, where each node has at most two keys and three links.
Now the key K 50 is

View Question
Consider the B+ tree in the adjoining figure, where each node has at most two keys and three links.
Keys K 15 and then

View Question
The order of a leaf node in a B+- tree is the maximum number of (value, data record pointer) pairs it can hold. Given th

View Question
Consider the following Boolean function with four variables
$$F\left( {w,\,x,\,y,\,z} \right) = \sum {\left( {1,\,3,\,4

View Question
Let $$f\left( {w,x,y,z} \right) = \sum {\left( {0,4,5,7,8,9,13,15} \right).} $$ Which of the following expressions are N

View Question
How many $$3$$ to $$8$$ decodes with an enable input are needed to construct to constant $$6$$ to $$64$$ line decoder wi

View Question
Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of $$n$$ variable

View Question
The control signal functions of a $$4$$-bit binary counter are given below $$($$where $$X$$ “don’t care”$$):$$
The coun

View Question
Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives he

View Question
Suppose we uniformly and randomly select a permutation from the 20! permutations of 1, 2, 3,..., 20. What is the promuta

View Question
Which one of these first-order logic formulae is valid?

View Question
How many different non-isomorphic Abelian groups of order 4 are there?

View Question
What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?

View Question
Let $$S$$ be a set6 of $$n$$ elements. The number of ordered pairs in the largest and the smallest equivalence relations

View Question
Consider the following Hasse diagrams.
Which all of the above represent a lattice?

View Question
A partial order P is defined on the set of natural numbers as following. Herw x/y denotes integer division.
i) (0, 0) $

View Question
Consider the set of (column) vectors defined by $$X = \,\{ \,x\, \in \,{R^3}\,\left| {{x_1}\, + \,{x_2}\, + \,{x_3} = 0}

View Question
The maximum number of binary trees that can be formed with three unlabeled nodes is:

View Question
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a bi

View Question
Consider a weighted undirected graph with positive edge weights and let $$uv$$ be an edge in the graph. It is known that

View Question
Let $$G$$ be the non-planar graph with minimum possible number of edges. Then $$G$$ has

View Question
Consider the following two statements about the function
$$$f\left( x \right) = \left| x \right|:$$$
$$P.\,\,f\left( x

View Question
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit

View Question
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit

View Question
Let Graph$$(x)$$ be a predicate which denotes that $$x$$ is a graph. Let Connected$$(x)$$ be a predicate which denotes t

View Question
Which of the following graphs has an Eulerian circuit?

View Question
Let $$A$$ be $$a$$ $$4$$ $$x$$ $$4$$ matrix with eigen values $$-5$$, $$-2, 1, 4$$.
Which of the following is an eigen

View Question
Let $$A$$ be the matrix $$\left[ {\matrix{
3 & 1 \cr
1 & 2 \cr
} } \right]$$. What is the maximum v

View Question
Group-1 contains some $$CPU$$ scheduling algorithms and Group-2 contains some applications. Match entries in Group-1 to

View Question
Consider the following statements about user level threads and kernel level threads.
Which one of the following stateme

View Question
An operating system uses Shortest Remaining Time first $$(SRT)$$ process scheduling algorithm. Consider the arrival time

View Question
Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct us

View Question
A process has been allocated $$3$$ page frames. Assume that none of the pages of the process are available in the memory

View Question
A process has been allocated $$3$$ page frames. Assume that none of the pages of the process are available in the memory

View Question
A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to

View Question
Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in

View Question
A single processor system has three resource types X, Y and Z, which are shared
by three processes. There are 5 units of

View Question
Consider the following C function:
int f(int n)
{
static int r = 0;
if(n <= 0) return 1;
if(n>3)
{

View Question
A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\lef

View Question
Which of the following languages is regular?

View Question
Consider the following finite state automation
The language accepted by this automation is given by the regular expres

View Question
Consider the following finite state automation
The minimum state automation equivalent to the above $$FSA$$ has the fo

View Question
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the t

View Question
The language $$L = \left\{ {{0^i}{{21}^i}\,|\,i \ge 0} \right\}$$ over the alphabet $$\left\{ {0,1,2} \right\}$$ is

View Question
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the t

View Question