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