GATE 2007 CSE & IT

Consider the following segment of C-code: int j, n; j=1; while(j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any n > 0 is:

What is the time complexity of the following recursive function? int DoSomething(int n){ if(n <= 2) return 1; else return (floor(sqrt(n)) + n); }

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 NOT equivalent to $$f?$$ $$(P)\,\,\,$$ $$x'y'z' + w'xy' + wy'...

The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation operator. The top two elements o...

There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given...

Consider the following C function: int f(int n) { static int r = 0; if(n <= 0) return 1; if(n>3) { r = n; return f(n-2)+2; } return f(n-1)+r; } What is the value of f(5)?

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

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

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 right, i.e., if it is at $$(i, j)$$ then it can move to eit...

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compu...

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

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

Information about a collection of students is given by the relation studInfo(studId, name, sex) . The relation enroll(studId, courseId) gives which student has enrolled for (or tak...

Suppose we uniformly and randomly select a permutation from the 20! permutations of 1, 2, 3,..., 20. What is the promutations that 2 appears at an earlier position than any other e...

Which of the following graphs has an Eulerian circuit?

Consider the following Boolean function with four variables $$F\left( {w,\,x,\,y,\,z} \right) = \sum {\left( {1,\,3,\,4,\,6,\,9,\,11,\,12,\,14} \right)} $$ the function is

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 binary tree of height h is:

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules: $$\eqalign{ & S...

The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity....

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 traversal of the binary tree is:

Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an ex...

Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk p...

Let Graph$$(x)$$ be a predicate which denotes that $$x$$ is a graph. Let Connected$$(x)$$ be a predicate which denotes that $$x$$ is connected. Which of the following first order l...

In a look $$-$$ ahead carry generator, the carry generate function $${G_i}$$ and the carry propagate function $${P_i}$$ for inputs, $${A_i}$$ and $${B_i}$$ are given by: $${P_i} =...

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents...

Consider the following C program segment where CellNode represents a node in a binary tree: struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild;...

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 and L be the number of leaves in a complete n-ary tree. If L...

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

Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes: /* P1 */ while(true){ want s1=true; whi...

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

Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of $$n$$ variables. What is the minimum size of the multiplexer needed?

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

Which one of the following statements if FALSE?

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many d...

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

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

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); } How many recursive calls are made by this function?

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

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

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 average length of Huffman codes?

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 right, i.e., if it is at $$(i, j)$$ then it can move to eit...

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the...

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 to be determined. Which of the following is TRUE about the nu...

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

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 following is the Huffman code for the letter a, b, c, d, e, f?

Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?

Consider the table employee(empId, name, department, salary) and the two queries Q 1 , Q 2 below. Assuming that department 5 has more than one employee, and we want to find the emp...

Let $$A$$ be the matrix $$\left[ {\matrix{ 3 & 1 \cr 1 & 2 \cr } } \right]$$. What is the maximum value of $${x^T}Ax$$ where the maximum is taken over all $$x$$ that are the unit e...

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

Consider the following relation schemas : b-Schema = (b-name, b-city, assets) a-Schema = (a-num, b-name, bal) d-Schema = (c-name, a-number) Let branch, account and depositor be res...

A process has been allocated $$3$$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page...

Consider the following two transactions: T 1 and T 2 . T 1 : read (A); T 2 : read (B); read (B); read (A); if A = 0 then B ← B + 1; if B ≠ 0 then A ← A - 1; write (B); write (A); W...

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules: $$\eqalign{ & S...

A process has been allocated $$3$$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page...

The order of a leaf node in a B + - tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 by...

Match the following: List - I (P) SMTP (Q) BGP (R) TCP (S) PPP List - II (1) Application layer (2) Transport layer (3) Data link layer (4) Network layer (5) Physical layer

Consider a $$4$$-way set associative cache consisting of $$128$$ lines with a line size of $$64$$ words. The $$CPU$$ generates a $$20$$-bit address of a word in main memory. The nu...

Consider the grammar with non-terminals N = { S, C, S 1 }, terminals T = { a, b, i, t, e }, with S as the start symbol, and the following set of rules: $$\eqalign{ & S \to iCtS{S_1...

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

How many $$3$$ to $$8$$ decodes with an enable input are needed to construct to constant $$6$$ to $$64$$ line decoder without using any other logic gates

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

Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE?

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 subnets and the maximum number of hosts in each subnet?

Consider the following two statements about the function $$$f\left( x \right) = \left| x \right|:$$$ $$P.\,\,f\left( x \right)$$ is continuous for all real values of $$x$$ $$Q.\,\,...

Consider the following C program: #include #define EOF -1 void push (int); /* push the argument on the stack */ int pop (void); /* pop the top of the stack */ void flagError (); in...

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 binary tree of height $$h$$ is:

Consider a weighted undirected graph with positive edge weights and let $$uv$$ be an edge in the graph. It is known that the shortest path from the source vertex $$s$$ to $$u$$ has...

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: i. isEmpty (Q) — returns true if the queue is empty, false ot...

A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements: $$P:$$ Increa...

Consider the relation employee(name, sex, supervisorName) with name as the key, supervisorName gives the name of the supervisor of the employee under consideration. What does the f...

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

Consider a selection of the form σ A ≤ 100(r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the inte...

Let $$A$$ be $$a$$ $$4$$ $$x$$ $$4$$ matrix with eigen values $$-5$$, $$-2, 1, 4$$. Which of the following is an eigen value of $$\left[ {\matrix{ {\rm A} & {\rm I} \cr {\rm I} & {...

Consider a machine with a byte addressable main memory of $${2^{16}}$$ bytes. Assume that a direct mapped data cache consisting of $$32$$ lines of $$64$$ bytes each is used in the...

Consider a machine with a byte addressable main memory of $${2^{16}}$$ bytes. Assume that a direct mapped data cache consisting of $$32$$ lines of $$64$$ bytes each is used in the...

Group-1 contains some $$CPU$$ scheduling algorithms and Group-2 contains some applications. Match entries in Group-1 to entries in Group-2. Group-1 (P) Gang Scheduling (Q) Rate Mon...

A partial order P is defined on the set of natural numbers as following. Herw x/y denotes integer division. i) (0, 0) $$ \in \,P$$. ii) (a, b) $$ \in \,P$$ if and only a % $$10\, \...

Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. On e of the two coins is picked up...

Consider the following two statements: i. A hash function (these are often used for computing digital signatures) is an injective function. ii. encryption technique such as DES per...

The message 11001001 is to be transmitted using the CRC polynomial x 3 + 1 to protect it from errors. The message that should be transmitted is:

Consider the following schedules involving two transactions. Which one of the following statements is TRUE? S 1 : r 1 (X); r 1 (Y); r 2 (Y); r 2 (X); w 2 (Y); w 1 (X); S 2 : r 1 (X...

Consider the following two statements: i. A hash function (these are often used for computing digital signatures) is an injective function. ii. encryption technique such as DES per...

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

A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\left\{ {0,1} \right\}}^ * },\,\,} \right.$$ number of $$0'$$s a...

Which of the following languages is regular?