GATE CSE 2010 PYQ

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a spanning tree T in this gra

Two alternative packages A and B are available for processing a database having records. Package A requires 0.0001 time units and package B requires time units to process n records. What is the smalle

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a path P from vertex 1 to ver

Which data structure in a compiler is used for managing information about variables and their attributes?

The program below uses six temporary variables a, b, c, d, e, f. a =1 b= 10 c =20 d= a +b e= c +d f =c +e b= c+ e e =b +f d =5 +e return d +f Assuming that all operations take their operands from regi

The grammar S aSa|bS|c is

Which languages necessarily need heap allocation in the runtime environment?

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram All the routers use the distance vector based routing algorithm to update their routing

Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram Suppose the weights of all unused links in the previous question are changed to 2 and t

One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?

Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same net mask N. Which of the values of N given below should not be used if A and B should b

Which one of the following is not a client server application?

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times

A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times

A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take 1 clock c

A main memory unit with a capacity of 4 megabytes is built using 1Mx1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 10

Consider the following schedule for transactions T1, T2 and T3: Which one of the schedules below is the correct serialization of the above?

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock? I. 2-phase locking II. Time-stamp ordering

The following functional dependencies hold for relations R(A, B, C) and S(B, D, E) B A, A C The relation R contains 200tuples and the relation S contains 100tuples. What is the maximum number of tuple

A relational schema for a train reservation database is given below What pids are returned by the following SQL query for the above instance of the tables? SELECT pid FROM Re servation WHERE class = '

The minterm expansion of f(P,Q,R)=PQ+QR'+PR' is

In the sequential circuit shown below, if the initial value of the output is 00, what are the next four values of ?

What is the Boolean Algebra for the output f of the combinational logic circuit of NOR gates given below?

The Boolean expression for the output f of the multiplexer shown below is

P is a 16-bit signed integer. The 2's complement representation of P is . The 2's complement representation of 8*P is

Newton-Raphson method is used to compute a root of the equation with 3.5 as the initial value. The approximation after one iteration is

The weight of a sequence of real numbers is defined as A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X

What is the probability that divisor of is a multiple of ?

Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company therefore subjects each computer to a testing process. This testing process gives th

What is the possible number of reflexive relations on a set of 5 elements?

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? I. 7,

Suppose the predicate F(x,y,t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula ?

Consider the set S = {1, }, where and are cube roots of unity. If * denotes the multiplication operation, the structure (S, *) forms

Let G=(V, E) be a graph. Define , where is the number of vertices of degree d in G. If S and T are two different trees with , then

What is the value of ?

Consider the following matrix If the eigenvalues of A are 4 and 8, then

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0. How many times will process P0 print '0'? How many times will proc

A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages

Which of the following statements are true? I. Shortest remaining time first scheduling may cause starvation II. Preemptive scheduling may cause starvation III. Round robin is better than FCFS in term

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.

A system has n resources , and k processes . The implementation of the resource request logic of each process is as follows: if (i%2= = 0) { if (i[latex] [/latex]n) request [latex]R_{i}[/latex] ; if (

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below Which one of the fol

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below How many different i

Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is

What does the following program print? #include void f (int *p, int * q) { p=q; *p=2; } int i= 0, j= 1; int main ( ){ f(&i, & j); printf( "%d%d \ n", i,j); return 0; }

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

What is the value printed by the following C program? #include int f(int * a, int n) { if(n<=0)return 0; else if(*a% 2 ==0) return *a+f(a+1,n-1); else return *a-f(a+1,n-1); } int main ( ) { int a[ ] {

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

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Let L = {w (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?

Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?