GATE CSE 2008 PYQ

Consider the following sequence of nodes for the undirected graph given below: 1.a b e f d g c 2.a b e f c g d 3.a d g e b c f 4.a d b c g e f A Depth First Search (DFS) is started at node a. The node

If we use Radix Sort to sort n integers in the range , for some k>0 which is independent of n, the time taken would be?

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

Let denote the number of binary strings of length n that contain no consecutive 0s. The value of is

The subset-sum problem is defined as follows. Given a set of n positive integers, S={ } and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this probl

Arrange the following functions in increasing asymptotic order: a. b. c. d. e.

G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

Let denote the number of binary strings of length n that contain no consecutive 0s. Which of the following recurrences does satisfy?

Consider the following C functions: int f1(int n) { if(n == 0 || n == 1) return n; else return (2*f1(n-1) + 3*f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N] ; X[0] = Y[0] = Z[0] = 0; X[1] = 1

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span?ning Tree?

Consider the following functions: Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

When for some , the recurrence relation evaluates to :

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

How many comparisons are needed to sort an array of length 5 if a straight selection sort is used and array is already in the opposite order?

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n)

Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to

The subset-sum problem is defined as follows. Given a set of n positive integers, S={ } and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this probl

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

Which of the following are true? I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with

Consider the grammar Which of the following sentences can be derived by this grammar?

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

In a resident - OS computer, which of the following systems must reside in the main memory under all situations?

Match the following:

Some code optimizations are carried out on the intermediate code because

Which of the following class of statement usually produces no executable code when compiled?

Relative to the program translated by a compiler, the same program when interpreted runs

Which of the following transmission media is not readily suitable to CSMA operation?

A 1 Mbps satellite link connects two ground stations. The altitude of the satellite is 36,504 km and speed of the signal is m/s. What should be the packet size for a channel utilization of 25% for a s

Two popular routing algorithms are Distance Vector(DV) and Link State (LS) routing. Which of the following are true? (S1): Count to infinity is a problem only with DV and not LS routing (S2): In LS, t

The subnet mask 255.255.255.192

Host X has IP address 192.168.1.97 and is connected through two routers R1 and R2 to another host Y with IP address 192.168.1.80. Router R1 has IP addresses 192.168.1.135 and 192.168.1.110. R2 has IP

A public key encryption system

A computer on a 10Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2Mbps. It is initially filled to capacity with 16Megabits. What is the maximum duration for which

The minimum frame size required for a CSMA/CD based computer network running at 1Gbps on a 200m cable with a link speed of is:

The TCP sliding window

The network 198.78.41.0 is a

Which of the following statements are TRUE? S1: TCP handles both congestion and flow control S2: UDP handles congestion but not flow control S3: Fast retransmit deals with congestion but not flow cont

Which Project 802 standard provides for a collision-free protocol?

If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?

The total number of keys required for a set of n individuals to be able to communicate with each other using secret key and public key cryptosystems, respectively are:

In the slow start phase of the TCP congestion control algorithm, the size of the congestion window

The three way handshake for TCP connection establishment is shown below. Which of the following statements are TRUE? S1: Loss of SYN + ACK from the server will not establish a connection S2: Loss of A

On a LAN ,where are IP datagrams transported?

How many bytes of data can be sent in 15 seconds over a serial link with baud rate of 9600 in asynchronous mode with odd parity and two stop bits in the frame?

Data transmitted on a link uses the following 2D parity scheme for error detection: Each sequence of 28 bits is arranged in a matrix (rows through , and columns through ) and is padded with a column a

Host X has IP address 192.168.1.97 and is connected through two routers R1 and R2 to another host Y with IP address 192.168.1.80. Router R1 has IP addresses 192.168.1.135 and 192.168.1.110. R2 has IP

What is the bandwidth of the signal that ranges from 40 kHz to 4 MHz?

Assume that each character code consists of 8 bits. The number of characters that can be transmitted per second through an asynchronous serial line at 2400 baud rate, and with two stop bits is

In Ethernet, the source address field in the MAC frame is the _______ address.

The device which is used to connect a peripheral to bus is known as

The TRAP is one of the interrupts available in INTEL 8085. Which one of the following statements is true of TRAP ?

A processor that has the carry, overflow and sign flag bits as part of its program status word (PSW) performs addition of the following two 2's complement numbers 01001101 and 11101001. After the exec

Which of the following is/are true of the auto-increment Addressing Modes? I. It is useful in creating self-relocating code II. If it is included in an Instruction Set Architecture, then an additional

In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is

The use of multiple register windows with overlap causes a reduction in the number of memory accesses for I. Function locals and parameters II. Register saves and restores III. Instruction fetches

An interrupt in which the external device supplies its address as well as the interrupt requests is known as

The Memory Address Register

The ability to temporarily halt the CPU and use this time to send information on buses is called

Which of the following are NOT true in a pipelined processor? I. Bypassing can handle all RAW hazards II. Register renaming can eliminate all register carried WAR hazards III. Control hazard penalties

Consider a CPU where all the instructions require 7 clock cycles to complete execution. There are 140 instructions in the instruction set. It is found that 125 control signals are needed to be generat

Consider a machine with a 2-way set associative data cache of size 64Kbytes and block size 16bytes. The cache is managed using 32 bit virtual addresses and the page size is 4Kbyts. A program to be run

More than one word are put in one cache block to:

Assume that EA = (X)+ is the effective address equal to the contents of location X, with X incremented by one word length after the effective address is calculated; EA = -(X) is the effective address

Which of the following statements about synchronous and asynchronous I/O is NOT true?

Delayed branching can help in the handling of control hazards For all delayed conditional branch instructions, irrespective of whether the condition evaluates to true or false

Consider the following Assembly language program MVIA 30 H ACI 30 H XRA A POP H After the execution of the above program, the contents of the accumulator will be

Which of the following architecture is/are not suitable for realising SIMD?

For inclusion to hold between two cache levels L1 and L2 in a multi-level cache hierarchy, which of the following are necessary? I. L1 must be a write-through cache II. L2 must be a write-through cach

The performance of a pipelined processor suffers if:

Delayed branching can help in the handling of control hazards The following code is to run on a pipelined processor with one branch delay slot: I1: ADD R2 R7 +R8 I2 : SUB R4 R5 - R6 I3: ADD R1 R2 + R3

For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to

A non pipelined single cycle processor operating at 100 MHz is converted into a synchronous pipelined processor with five stages requiring 2.5 nsec, 1.5 nsec, 2 nsec, 1.5 nsec and 2.5 nsec, respective

Consider a computer with a 4-ways set-associative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8

Consider a computer with a 4-ways set-associative mapped cache of the following characteristics: a total of 1 MB of main memory, a word size of 1 byte, a block size of 128 words and a cache size of 8

Which of the following is an example of spooled device?

The total time to prepare a disk drive mechanism for a block of data to be read from it is

Which of the following must be true for the RFE (Return From Exception) instruction on a general purpose processor? I. It must be a trap instruction II. It must be a privileged instruction III. An exc

Consider a machine with a 2-way set associative data cache of size 64Kbytes and block size 16bytes. The cache is managed using 32 bit virtual addresses and the page size is 4Kbyts. A program to be run

Consider a machine with a 2-way set associative data cache of size 64Kbytes and block size 16bytes. The cache is managed using 32 bit virtual addresses and the page size is 4Kbyts. A program to be run

Consider the following relational schema: Student(school-id,sch-roll-no,sname,saddress) School(school-id,sch-name,sch-address,sch-phone) Enrolment(school-id,sch-roll-no,erollno,examname) ExamResult(er

Let R and S be two relations with the following schema R ( ,R1,R2,R3) S ( ,S1,S2) Where {P, Q} is the key for both schemas. Which of the following queries are equivalent? I. II. III. IV.

Consider the following three schedules of transactions T1, T2 and T3. [Notation: In the following NYO represents the action Y (R for read, W for write) performed by transaction N on object O.] Which o

Consider the following relational schemes for a library database: Book (Title, Author, Catalog_ no, Publisher, Year, Price) Collection (Title,Author, Catalog_ no) with in the following functional depe

Which of the following tuple relational calculus expression(s) is/are equivalent to ? I. II. III. IV.

Consider the following ER diagram The minimum number of tables needed to represent M, N, P, R1, R2 is

Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored

Let R (A, B, C, D, E, P, G) be a relational schema in which the following functional dependencies are known to hold: and . The relational schema R is

The join operation can be defined as

Let be a relational schema in which the following functional dependencies are known to hold: and . The decomposition of into

Consider the following relational schema: Student(school-id,sch-roll-no,sname,saddress) School(school-id,sch-name,sch-address,sch-phone) Enrolment(school-id,sch-roll-no,erollno,examname) ExamResult(er

Consider the following ER diagram Which of the following is a correct attribute set for one of the tables for the minimum number of tables needed to represent M, N, P, R1, R2?

Repeated execution of simple computation may cause compounding of

In the expression by writing the first term A as A+0, the expression is best simplified as

What Boolean function does the circuit below realize?

Let r denote number system radix. The only value(s) of r that satisfy the equation is / are

How many 2-input multiplexers are required to construct a -input multiplexer?

The following bit pattern represents a floating point number in IEEE 754 single precision format 1 10000011 101000000000000000000000 The value of the number in decimal form is

In the given network of AND and OR gates f can be written as

If where N is a positive integer, then the value of N is

Which of the following is not a valid rule of XOR?

Given f1, f3 and f in canonical sum of products form (in decimal) for the circuit then is

A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?

If , then the value of x is

The Boolean expression simplifies to

The output Y of the given circuit

The Boolean theorem corresponds to

Which of the following is termed as minimum error code ?

Consider the following Boolean function of four variables The function is

A computer uses 8 digit mantissa and 2 digit exponent. If a=0.052 and b=28E+11 then b+a-b will :

Consider the following state diagram and its realization by a JK flip flop The combinational circuit generates J and K in terms of x, y and Q. The Boolean expressions for J and K are :

The two numbers given below are multiplied using the Booth's algorithm. Multiplicand : 0101 1010 1110 1110 Multiplier: 0111 0111 1011 1101 How many additions/Subtractions are required for the multipli

The logic operations of two combinational circuits in Figure-I and Figure -II are

In the Karnaugh map shown below, x denotes a don't care term. What is the minimal form of the function represented by the Karnaugh map?

If P, Q, R are Boolean variables, then simplifies to

In the IEEE floating point representation the hexadecimal value 0x00000000 corresponds to

If P, Q, R are subsets of the universal set U, then is

If a square matrix satisfies , then the matrix is

P and Q are two propositions. Which of the following logical expressions are equivalent? I. II. III. IV.

equals

Let x be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown. If P (x -1) = P (Y 2) , the standard deviation

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

Consider the graph shown in the figure below: Which of the following is a valid strong component?

If M is a square matrix with a zero determinant, which of the following assertion (s) is (are) correct? S1: Each row of M can be represented as a linear combination of the other rows S2: Each column o

If is defined as follows, what is the minimum value of for ?

Consider the function . Suppose an execution of the Newton-Raphson method to find a zero of starts with an approximation of . What is the value of , the approximation of that algorithm produces after

Which of the following statements is true for every planar graph on n vertices?

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

Which of the following first order formulae is logically valid? Here is a first order formula with x as a free variable, and is a first order formula with no free variable.

Consider the following Hasse diagrams. i. ii. iii. iv. Which all of the above represent a lattice?

The number of distinct simple graphs with up to three nodes is

A sample space has two events A and B such that probabilities . What is ?

Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that the studies mathematics the next day is 0.6. If she studies mathe

A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve is

The following system of equations has a unique solution. The only possible value(s) for is/are

If the two matrices have the same determinant, then the value of is

What is the chromatic number of the following graph?

Which of the following is the negation of

How many of the following matrices have an eigenvalue 1? and

What is the probability that in a randomly chosen group of people at least three people have the same birthday?

Consider the field C of complex numbers with addition and multiplication. Which of the following form(s) a subfield of C with addition and multiplication? S1: the set of real numbers S2: and b are rat

In how many ways can blue balls and red balls be distributed in distinct boxes?

Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b)

The Newton-Raphson iteration can be used to compute the

G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be

The minimum number of equal length subintervals needed to approximate to an accuracy of at least using the trapezoidal rule is

What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes

Consider the following sequence of nodes for the undirected graph given below: 1.a b e f d g c 2.a b e f c g d 3.a d g e b c f 4.a d b c g e f A Depth First Search (DFS) is started at node a. The node

Four jobs to be executed on a single processor system arrive at time 0 in the order A,B,C,D. Their burst CPU time requirements are 4,1,8,1 time units respectively. The completion time of A under round

The page replacement algorithm which gives the lowest page fault rate is

Which of the following need not necessarily be saved on a Context Switch between processes?

Which of the following system calls results in the sending of SYN packets?

Feedback queues

A process executes the following code for (i = 0; i < n; i + +) fork( ); The total number of child processes created is

Match the following flag bits used in the context of virtual memory management on the left side with the different purposes on the right side of the table below.

The data blocks of a very large file in the Unix file system are allocated using

Overlaying

Consider a logical address space of 8 pages of 1024 words mapped into memory of 32 frames. How many bits are there in the logical address?

A critical section is a program segment

Which of the following need not necessarily be saved on a context switch between processes?

Checkpointing a job

Dynamic address translation

With Round-Robin CPU scheduling in a time shared system

The following is a code with two threads, producer and consumer, that can run in parallel. Further, S and Q are binary semaphores quipped with the standard P and V operations. semaphore S = 1, Q = 0;

In which of the following four necessary conditions for deadlock processes claim exclusive control of the resources they require?

Thrashing

A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket(), a bind() and a listen() system call in that order,

If the time-slice used in the round-robin scheduling policy is more than the maximum time required to execute any process, then the policy will

Assume that a main memory with only 4 pages, each of 16 bytes, is initially empty. The CPU generates the following sequence of virtual addresses and uses the Least Recently Used (LRU) page replacement

A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to p

Fork is

Consider the execution of the following commands in a shell on a Linux operating system. bash In alpha beta bash cat >> beta << SAME Information Technology SAME bash$ cat beta The output of the last c

An operating system implements a policy that requires a process to release all resources before making a request for another resource. Select the TRUE statement from the following:

The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows: P(s) : s = s - 1; if (s < 0) then wait; V(s) : s = s + 1; if (s <= 0) then wakeup a process wait

A paging scheme uses a Translation Look-aside Buffer (TLB). A TLB-access takes 10 ns and the main memory access takes 50 ns. What is the effective access time(in ns) if the TLB hit ratio is 90% and th

Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?

A binary tree with n>1 nodes has , and nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remain

The time required to search an element in a linked list of length n is

Which of the following is an illegal array definition?

Which of the following is TRUE?

Consider the following C functions: int f1(int n) { if(n == 0 || n == 1) return n; else return (2*f1(n-1) + 3*f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N] ; X[0] = Y[0] = Z[0] = 0; X[1] = 1

Consider the code fragment written in C below : void f (int n) { if (n <=1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } } What does f(173) print?

What is the output printed by the following C code? #include int main () { char a [6] = "world"; int i, j; for (i = 0, j = 5; i < j; a [i++] = a [j--]); printf ("%s ", a); }

A binary tree with n>1 nodes has , and nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. can be expressed as

What is printed by the following C program? int f(int x, int *py, int **ppz) { int y, z; **ppz += 1; z = **ppz; *py += 2; y = *py; x += 3; return x+y+z; } void main() { int c, *b, **a; c = 4; b = &c;

Consider the code fragment written in C below : void f (int n) { if (n <= 1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } } Which of the following implementations will produce the same

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 I

Choose the correct option to fill ? 1 and ? 2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character. void recerse void {

Which combination of the integer variables x, y and z makes the variable a get the value 4 in the following expression? a = (x > y) ? ((x > z) ? x : z) : ((y > z) ? y : z)

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k)=kmod 11 be the hash function used. A sequence of records with keys 43 36 92 87 11 4 71 13 14 is inserted into a

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in th

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. I.MBCAFHPYK II.KAMCBYPFH III.MABCKYFPH Pick the true statement f

C program is given below: #include int main () { int i, j; char a [2] [3] = {{'a', 'b', 'c'}, {'d', 'e', 'f'}}; char b [3] [2]; char *p = *b; for (i = 0; i < 2; i++) { for (j = 0; j < 3; j++) { *(p +

Consider the following code segment: for (int k=0; k<20; k=k+2) { if (k % 3 == 1) system.out.print(k+ " "); } What is printed as a result of executing the code segment?

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5

Which of the following operations is performed more efficiently by doubly linked list than by linear linked list?

The minimum number of fields with each node of doubly linked list is

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 I

How many distinct BSTs can be constructed with 3 distinct keys?

Consider the following C function: int f(int n) { static int i = 1; if(n >= 5) return n; n = n+i; i++; return f(n); } The value returned by f(1) is:

Consider the C program given below. What does it print? #include int main () { int i, j; int a [8] = {1, 2, 3, 4, 5, 6, 7, 8}; for(i = 0; i 4; j--) { int i = j/2; a[i] = a[i] - 1; } printf ("%d, %d",

A complete binary tree with the property that the value at each node is at least as large as the values at its children is known as

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?

Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of the stack B can be only be pri

Consider the C program below. What does it print? #include # define swapl (a, b) tmp = a; a = b; b = tmp void swap2 ( int a, int b) { int tmp; tmp = a; a = b; b = tmp; } void swap3 (int*a, int*b) { in

What is the value of F(4) using the following procedure: function F(K : integer) integer; begin if (k<3) then F:=k else F:=F(k-1)*F(k-2)+F(k-3) end;

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i = 0; j = 9; 4. do { 5

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,...,n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the t

Which of the following are regular sets? II. III. IV.

Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?

Given below are two finite state automata ( indicates the start state and F indicates a final state) Which of the following represents the product automaton ZxY?

Which of the following is true for the language{ |p is a prime} ?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. For the string "aabbaab" how many steps are required to derive the string an

Which of the following statements is false?

Consider the following languages. Which of the following is true?

Consider the following two finite automata. accepts and accepts . Which one of the following is TRUE?

Match the following NFAs with the regular expressions they correspond to 1. + 0(01*1 + 00) * 01* 2. + 0(10 *1 + 00) * 0 3. + 0(10 *1 + 10) *1 4. + 0(10 *1 + 10) *10 *

Which of the following languages is (are) non-regular? reads the same forward and backward contains an even number of 0's and an even number of 1's

Consider a CFG with the following productions. S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is:

If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA?

Which of the following statements are true? I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa II. All -productions can be removed from any context-free gramm

Which of the following regular expressions describes the language over consisting of strings that contain exactly two 1's?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. Which of the following strings is generated by the grammar above?

Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept t

If L and are recursively enumerable then L is