GATE CSE 2007
View Questions

## GATE CSE

Consider the following segment of C-code: int j, n; j=1; while(j &lt;= 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 &lt;= 2) return 1;
View Question
Consider the following C code segment: int IsPrime(n){ int i, n; for(i=2; i&lt;=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 &amp; 1 \cr 1 &amp; 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 &lt;= 0) return 1; if(n&gt;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
EXAM MAP
Medical
NEET