GATE CSE 2005 PYQ

Let T(n) be a function defined by the recurrence and Which of the following statements is TRUE?

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time comple

We are given 9 tasks T1, T2... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the ta

An undirected graph G has n nodes. Its adjacency matrix is given by an nxn square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are 1's. which one of the following is TRUE?

The Asymptotic Notation of computing the transitive closure of a binary relation on a set of n elements is known to be:

Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

We are given 9 tasks T1, T2... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the ta

Consider the following C-function: double foo (int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } } The Asymptotic Notation of

Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s X and t Y. Consider the edge e having the minimum weight am

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

Let be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex to a vertex iff either or . The minimum number of edges in a path in G from vertex 1 to ver

Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always

Consider the following C-function: double foo (int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } } Suppose we modify the abov

Suppose T(0)=T(1)=1 Which one of the following is FALSE?

Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s X and t Y. Consider the edge e having the minimum weight am

Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s X and t Y. Consider the edge e having the minimum weight am

Consider the grammar: S (S) | a Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good:

Consider the context-free grammar where E is the starting symbol, the set of terminals is , and the set of nonterminals is {E}. Which of the following terminal strings has more than one parse tree whe

Consider the context-free grammar where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}. For the terminal string id + id + id + id, how many parse

Consider the grammar: E E + n | E * n | n For a sentence n + n * n, the handles in the right-sentential form of the reduction are:

Consider the arithmetic expression: a = (b + c) * (b + c) - d How many nodes and edges does the DAG (Directed Acyclic Graph) for this expression have, assuming common subexpression elimination is appl

Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production. The above grammar and the semantic rules are fed to a yacc tool (wh

The grammar is not suitable for predictive-parsing because the grammar is:

Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production. Assume the conflicts of this question are resolved usinf yacc tool

Traceroute reports a possible route that is taken by packets moving from some host A to some other host B. Which of the following options represents the technique used by traceroute to identify these

Consider the following message M = 1010001101. The cyclic redundancy check (CRC) for this message using the divisor polynomial is :

Which of the following statements is TRUE about CSMA/CD:

Which of the following statements is FALSE regarding a bridge?

The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:

An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be:

A network with CSMA/CD protocol in the MAC layer is running at 1Gbps over a 1km cable with no repeaters. The signal speed in the cable is . The minimum frame size for this network should be:

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destina

Count to infinity is a problem associated with:

Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 . The minimum frame size is

On a TCP connection, current congestion window size is Congestion Window = 4 KB. The window size advertised by the receiver is Advertise Window = 6 KB. The last byte sent by the sender is LastByteSent

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destina

Consider the three commands : PROMPT, HEAD and RCPT. Which of the following options indicate a correct association of these commands with protocols where these are used?

A company has a class C network address of 204.204.204.0. It wishes to have three subnets, one with 100 hosts and two with 50 hosts each. Which one of the following options represents a feasible set o

Suppose that two parties A and B wish to setup a common secret key (D-H key) between themselves using the Diffie-Hellman key exchange technique. They agree on 7 as the modulus and 3 as the primitive r

Assume that "host1.mydomain.dom" has an IP address of 145.128.16.8. Which of the following options would be most appropriate as a subsequence of steps in performing the reverse lookup of 145.128.16.8

In a TDM medium access control bus LAN, each station is assigned one time slot per cycle for transmission. Assume that the length of each time slot is the time to transmit plus the end-to-end propagat

Packets of the same session may be routed through different paths in:

A channel has a bit rate of 4 kbps and one-way propagation delay of 20 ms. The channel uses stop and wait protocol. The transmission time of the acknowledgment frame is negligible. To get a channel ef

In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 b

The address resolution protocol (ARP) is used for:

In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed thr

Consider a 2-way set associative cache memory with 4 sets and total 8 cache blocks (0-7) and a main memory with 128 blocks (0-127). What memory blocks will be present in the cache after the following

A dynamic RAM has a memory cycle time of 64 nsec. It has to be refreshed 100 times per msec and each refresh takes 100 nsec. What percentage of the memory cycle time is used for refreshing?

We have two designs D1 and D2 for a synchronous pipeline processor. D1 has 5 pipeline stages with execution times of 3 nsec, 2 nsec, 4 nsec, 2 nsec and 3 nsec while the design D2 has 8 pipeline stages

Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?

A disk has 8 equidistant tracks. The diameters of the innermost and outermost tracks are 1 cm and 8 cm respectively. The innermost track has a storage capacity of 10 MB. If the disk has 20 sectors per

Consider the following data path of a CPU. ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried o

An instruction set of a processor has 125 signals which can be divided into 5 groups of mutually exclusive signals as follows: Group 1 : 20 signals, Group 2 : 70 signals, Group 3 : 2 signals, Group 4

A hardwired CPU uses 10 control signals to , in various time steps to , to implement 4 instructions to as shown below: Which of the following pairs of expressions represent the circuit for generating

Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions pr

A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred byte-wise. Let the interrupt overhead be 4 sec. The byte transfer time between the device interfaces register and

Consider a disk drive with the following specifications: 16 surfaces, 512 tracks/surface, 512 sectors/track, 1 KB/sector, rotation speed 3000 rpm. The disk is operated in cycle stealing mode whereby w

Consider the following data path of a CPU. ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried o

Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generates 32 bit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively.

Consider a three word machine instruction ADD A[R0], @B The first operand (destination) "A[R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@B" uses indire

A disk has 8 equidistant tracks. The diameters of the innermost and outermost tracks are 1 cm and 8 cm respectively. The innermost track has a storage capacity of 10 MB. What is the total amount of da

A 5 stage pipelined CPU has the following sequence of stages: IF - Instruction fetch from instruction memory, RD - Instruction decode and register read, EX - Execute: ALU operation for data and addres

Match each of the high level language statements given on the left hand side with the most natural Addressing Modes from those listed on the right hand side. 1 A[1] = B[J]; a Indirect addressing 2 whi

Which one of the following statements about normal forms is FALSE?

In an inventory management system implemented at a trading corporation, there are several tables designed to hold all the information. Amongst these, the following two tables hold information on which

In a schema with attributes A, B, C, D and E following set of functional dependencies are given Which of the following functional dependencies is NOT implied by the above set?

A database table has 2000 records and occupies 80 disk blocks. Another table has 400 records and occupies 20 disk blocks. These two tables have to be joined as per a specified join condition that need

In a computer system, four files of size 11050 bytes, 4990 bytes, 5170 bytes and 12640 bytes need to be stored. For storing these files on disk, we can use either 100 byte disk blocks or 200 byte disk

The following table has two attributes A and C where A is the primary key and C is the foreign key referencing A with on-delete cascade. The set of all tuples that must be additionally deleted to pres

Let E1 and E2 be two entities in an E/R diagram with simple single-valued attributes. R1 and R2 are two relationships between E1 and E2, where R1 is one-to-many and R2 is many-to-many. R1 and R2 do no

Let r be a relation instance with schema R = (A, B, C, D). We define and . Let where * denotes natural join. Given that the decomposition of r into and is lossy, which one of the following is TRUE?

A database table has 2000 records and occupies 80 disk blocks. Another table has 400 records and occupies 20 disk blocks. These two tables have to be joined as per a specified join condition that need

Consider a relation scheme R=(A,B,C,D,E,H) on which the following functional dependencies hold: {A B, BC D, E C, D A}. What are the candidate keys of R?

Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database by a successful transaction persist

A table has fields with the following functional dependencies In terms of Normalization, this table is in

A company maintains records of sales made by its salespersons and pays them commission based on each individual's total sales made in a year. This data is maintained in a table with following schema:

Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below: If we wish to store information about the rent payment to be made by person (s) occupying di

A table 'student' with schema (roll, name, hostel, marks), and another table 'hobby' with schema (roll, hobbyname) contains records as shown below: The following SQL query is executed on the above tab

The relation book (title, price) contains the titles and prices of different books. Assuming that no two books have the same price, what does the following SQL query list? select title from book as B

Which one of the following is a key factor for preferring - trees to binary search trees for indexing database relations?

Consider the following circuit. Which one of the following is TRUE?

Consider the following floating point format Mantissa is a pure fraction in sign-magnitude form. The normalized representation for the above format is specified as follows. The mantissa has an implici

Consider the following circuit involving a positive edge triggered D FF. Consider the following timing diagram. Let Ai represent the logic level on the line A in the i-th clock period. Let A' represen

Using Booth's Algorithm for multiplication, the multiplier -57 will be recoded as

Which of the following input sequences will always generate a 1 at the output z at the end of the third cycle?

A two-way switch has three terminals a, b and c. In ON position (logic value 1), a is connected to b, and in OFF position, a is connected to c. Two of these two-way switches S1 and S2 are connected to

The switching expression corresponding to f(A,B,C,D)= (1,4,5,9,11,12) is:

evaluates to

The hexadecimal representation of is:

How many pulses are needed to change the contents of a 8-bit up counter from 10101100 to 00100111 (rightmost bit is the LSB)?

Consider the following floating point format Mantissa is a pure fraction in sign-magnitude form. The decimal number has the following hexadecimal representation (without normalization and rounding off

Which of the following expressions is equivalent to

The circuit shown below implements a 2-input NOR gate using two 2-4 MUX (control signal 1 selects the upper input). What are the values of signals x, y and z?

Consider the following circuit. The flip-flops are positive edge triggered D FFs. Each state is designated as a two-bit string Q0Q1 . Let the initial state be 00. the state transition sequence is

What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some student

A sink in a directed graph is a vertex i such that there is an edge from every vertex to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adj

A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded and it is put back in the bag. This process is repeated 3 times. The probabilit

Which one of the following graphs is NOT planar?

Let P, Q and R be tree atomic prepositional assertions. Let X denote (P Q) R and Y denote (P R) (Q R). Which one of the following is a tautology?

What are the eigen values of the following 2 x 2 matrix?

Let , where . What is g(i)?

What is the value of

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE?

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen set such that a c mod 3 and b d mod 5

In a communication network, a packet of length L bits takes link with a probability of or link with a probability of . Link and have bit error probability of and respectively. The probability that the

Let be a function from a set A to a set B, a function from B to C, and a function from A to C, such that for all . Which of the following statements is always true for all such functions and ?

If the trapezoidal method is used to evaluate the integral obtained , then the value obtained

Consider the following system of equations in three real variables : The system of equations has

An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is

Let f: B C and g: A B be two functions and let h = f g. Given that h is an onto function which one of the following is TRUE?

Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:

A sink in a directed graph is a vertex i such that there is an edge from every vertex to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adj

Box P has 2 red balls and 3 blue balls and box Q has 3 balls and 1 blue ball. A ball is selected as follows: (i) select a box (ii) choose a ball from the selected box such that each ball in the box is

Let R and S be any two equivalence relations on a non-empty set A. Which one of the following statements is TRUE?

Consider the set H of all 3 x 3 matrices of the type where a,b,c,d,e and f are real numbers and abc 0. Under the matrix multiplication operation, the set H is:

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. then, the size of the maximum independent set of G is:

The following is the Hasse diagram of the poset [{a,b,c,d,e}, ] The poset is:

The determinant of the matrix given below is

The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively:

Let , where p and q are distinct prime numbers. How many numbers m satisfy and gcd(m,n)=1? Note that gcd(m,n) is the greatest common divisor of m and n.

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly gene

Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets and in C, either or . What is the maximum cardinality of C?

A line L in a circuit is said to have a stuck-at-0 fault if the line permanently has a logic value 0. Similarly a line L in a circuit is said to have a stuck-at-1 fault if the line permanently has a l

Let A, B and C be non-empty sets and let X = (A - B) - C and Y = (A - C) - (B - C) Which one of the following is TRUE?

Let f(x) be the continuous probability density function of a random variable X. The probability that , is:

Consider the following code fragment: if (fork() == 0) { a = a + 5; printf("%d,%dn", a, &a); } else { a = a - 5; printf("%d, %dn", a, &a); } Let u, v be the values printed by the parent process, and x

What is the swap space in the disk used for?

The shell command find -name passwd -print is executed in /etc directory of a computer system running Unix. Which of the following shell commands will give the same information as the above command wh

Two shared resources and are used by processes and . Each process has a certain priority for accessing each resource. Let denote the priority of for accessing . A process can snatch a resource from pr

Given below is a program which when executed spawns two concurrent processes : semaphore X : = 0 ; /* Process now forks into concurrent processes P1 & P2 */ P1 P2 V (X) ; P(X) ; P(X) ; V(X) ; Consider

A student wishes to create symbolic links in a computer system running Unix. Three text files named "file 1", "file 2" and "file 3" exist in her current working directory, and the student has read and

Suppose n processes, share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process is , where . Which one of the following is a suffic

Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and R4, as shown below. R1; R1; R2; R2; R3; R3; R4; R4; Both processes are started at the same time, and each resource can be ac

A user level process in Unix traps the signal sent on a Ctrl-C input, and has a signal handling routine that saves appropriate files before terminating the process. When a Ctrl-C input is given to thi

We wish to schedule three processes P1, P2 and P3 on a uniprocessor system. The priorities, CPU time requirements and arrival times of the processes are as shown below. We have a choice of preemptive

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tre

A program P reads in 500 integers in the range [0,100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequ

The numbers are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be

Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let c be a sorted array containing 2n integers obtained by merging the two arrays a and b. Assuming the arrays are

Consider the following C-program: void foo(int n, int sum) { int k = 0, j = 0; if (n == 0) return; k = n % 10; j = n / 10; sum = sum + k; foo (j, sum); printf ("%d,", k); } int main () { int a = 2048,

What is the output printed by the following program? #include int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/2, 2*k) - k; } int main () { printf("%

Consider line number 3 of the following C-program. int main ( ) { /* Line 1 */ int I, N; /* Line 2 */ fro (I =0, I < N, I++); /* Line 3 */ } Identify the compiler's response about this line while crea

The following C function takes two ASCII strings and determines whether one is an anagram of the other. An anagram of a string s is a string obtained by permuting the letters in s. int anagram (char *

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with t

Let a be an array containing n integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference is a specified number S > 0. i = 0;

Consider the following C-program: double foo (double); /* Line 1 */ int main() { double da, db; // input da db = foo(da); } double foo(double a) { return a; } The above code compiled without any error

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements '1' and '7' are inserted in the heap

A function defined on stacks of integers satisfies the following properties. and for all stacks and integers .If a stack contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is ?

Suppose there are sorted lists of elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)

A binary search tree contains the numbers 1,2,3,4,5,6,7,8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5,3,1,2,4,6,8,7. If the t

What does the following C-statement declare? int ( * f) (int * ) ;

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in

Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the resul

How many distinct binary search trees can be created out of 4 distinct keys?

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is true?

Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the

A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?

Consider the languages: and Which one of the following statements is FALSE?

Which of the following statements is TRUE about the regular expression 01*0?

Consider the regular grammar: where S is the starting symbol, the set of terminals is {a} and the set of non-terminals is {S, W, X, Y, Z}. We wish to construct a deterministic finite automaton (DFA) t

Consider the non-deterministic finite automaton (NFA) shown in the figure. State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE?

Let and denote the classes of languages accepted by non-deterministic finite automata and non- deterministic push-down automata, respectively. Let and denote the classes of languages accepted by deter

Let L be a regular language and M be a context-free language, both over the alphabet . Let and denote the complements of L and M respectively. Which of the following statements about the language is T

Consider the machine M: The language recognized by M is :

Consider the languages: ,where # is a special symbol Which one of the following is TRUE?

The language is

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?