GATE CSE 2006 PYQ

Which one the following in place sorting algorithms needs the minimum number of swaps?

Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?

Consider the following C-program fragment in which i, j,and n are integer variables. for (i = n, j = 0; i > 0; i/=2, j += i); Let Val(j) denote the value stored in the variable j after termination of

Consider a weighted complete graph G on the vertex set { } such that the weight of the edge ( ) is 2|i-j|. The weight of a minimum spanning tree

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, then data structure to be used is

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represen

The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21 A Huffman code is used to represent the characters. What is

Let T be a depth first search tree in a undirected graph G Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

Consider the following recurrence: T(n)=2T( )+ 1, T(1) = 1 Which one of the following is true?

Consider the following grammar. S S * E S E E F + E E F F F id Consider the following LR(0) items corresponding to the grammar above. (i) S S * .E (ii) E F. + E (iii) E F + .E Given the items above, w

The grammar S AC|CB C aCb| A aA|a B Bb|b generates the language , what is the length of the derivation (number of steps starting from S) to generate the string with ?

Consider the following translation scheme. S ER R * E{print('*');}R| E F+E{print('+');}|F F (S)|id{print(id.value);} Here id is a taken that represents an integer and id.value represents the correspon

Which one of the following grammars generates the language

Consider the following C code segment. for (i = 0, < i n; i++) { for (j=0; j< n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } } Which one to the following false?

Consider the following grammar S FR R * S | F id In the predictive parser table, M, of the grammar the entries M[S, id] and M[R,$] respectively

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a sp

For which one of the following reason does Internet Protocol (IP) use the timeto-live (TTL) field in the IP datagram header?

Which of the following statements is TRUE?

Two computers C1 and C2 are configured as follows. C1 has IP address 203. 197.2.53 and netmask 255.255. 128.0. C2 has IP address 203.197.75.201 and netmask 255.255.192.0. Which one of the following st

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a sp

On a wireless link, the probability of packet error is 0.2. A stop-and-wait protocol is used to transfer data across the link. The channel condition is assumed to be independent of transmission to tra

A router has two full-duplex Ethernet interfaces each operating at 100 Mb/s. Ethernet frames are at least 84 bytes long (including the Preamble and the Inter-Packet-Gap). The maximum packet processing

Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay between A and B is 80 milliseconds and the bottleneck bankwidth on the path betwe

A router uses the following routing table: 0 1 2 3 Packet bearing a destination address 144.16.68.117 arrives at the router. On which interface will it be forwarded?

Which of the following statement(s) is TRUE? I. A hash function takes a message of arbitrary length and generates a fixed length code. II. A hash function takes a message of fixed length and generates

A subnetted Class B network has the following broadcast address: 144.16.95.255 Its subnet mask

A program on machine X attempts to open a UDP connection to port 5376 on a machine Y, and a TCP connection to port 8632 on machine Z. However, there are no applications listening at the corresponding

Suppose that it takes 1 unit of time to transmit a packet (of fixed size) on a communication link. The link layer uses a window flow control protocol with a window size of N packets. Each packet cause

HELO and PORT, respectively, are commands from the protocols:

Station A needs to send a message consisting of 9 packets to Station B using a siding window (window size 3) and go-back-n error control strategy. All packets are ready and immediately available for t

A link of capacity 100 Mbps is carrying traffic from a number of sources. Each source generates an on-off traffic stream; when the source is on, the rate of traffic is 10 Mbps, and when the source is

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a twodimensional array of size 512x512 with elements that occupy 8-bytes each. Consider the following two C code segments,

Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction "bbs reg, pos, labbel" jumps to label if bit in position pos of register operand reg is one. a register is 32 bits wi

A computer system has a level-1 instruction cache (1-cache), a level-1 data cache (D-cache) and a level-2 cache (L2-cache) with the following specifications: I 4K 4 D 4K 2 4 L2 64K 4 16 The length of

A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well

Which of the following statements about relative addressing mode is FALSE?

A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative.

A CPU has a cache with block size 64 bytes. The main memory has k banks, each bank being c bytes wide. Consecutive c-byte chunks are mapped on consecutive banks with warp-around. All the k banks can b

Consider these two functions and two statements S1 and S2 about them. S1 : The transformation from work 1 to work 2 is valid, i.e., for any program state and input arguments, work 2 will compute the s

Which of the following DMA transfer modes and interrupt handling mechanisms will enable the highest I/O band-width?

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a twodimensional array of size 512x512 with elements that occupy 8-bytes each. Consider the following two C code segments,

A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)?

The memory locations 1000,1001 and 1020 have data values 18,1 and 16 respectively before the following program is executed. R_s, 1 R_d, 1000(R_s) R_d, 1000 0(R_d), 20 Which of the statements below is

A cache line is 64 bytes. The main memory has latency 32 ns and bandwidth 1 GBytes/s. The time required to fetch the entire cache line from the main memory is:

The data path shown in the figure computes the number of 1s in the 32-bit input word corresponding to an unsigned even integer stored in the shift register. The unsigned counter, initially zero, is in

A pipelined processor uses a 4-stage instruction pipeline with the following stages: Instruction fetch (IF), Instruction decode (ID), Execute (EX) and Writeback (WB). The arithmetic operations as well

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32-byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32-byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both

A CPU has five-stages pipeline and runs at 1GHz frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the target address and evaluates the

Consider the following log sequence of two transactions on a bank account, with initial balance 12000,that transfer 2000 to a mortgage payment and, then apply a 5% interest. 1. T1 start 2. T1 B old =

Consider the relations r1(P, Q, R) and r2(R, S, T) with primary keys P and R respectively. The relation contains 2000 tuples and contains 2500 tuples. The maximum size of the join is :

Consider a relation R with five attributes V, W, X, Y, and Z. The following functional dependencies hold: . Which of the following is a candidate key for R?

Consider the relation enrolled (student, course) in which student, course) is the primary key, and the relation paid (student, amount) where student is the primary key . Assume no null values and no f

The following functional dependencies are given: Which one of the following options is false?

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these pr

Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no f

Consider the relation account (customer, balance) where customer is a primary key and there are no mall values. We would like to rank customers according to decreasing balance. The customer with the l

Which of the following relational query languages have the same expressive power? I. Relational algebra II. Tuple relational calculus restricted to safe expressions III. Domain relational calculus res

In a database file structure, the search key field is 9 bytes long, the block size is 512 bytes, a record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a non-leaf no

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these pr

Given two three bit numbers and and c, the carry in, the function that represents the carry generate function when these two numbers are added is

A logical binary relation , is defined as follows Let be the unary negation (NOT) operator, with higher precedence, than . Which one of the following is equivalent to A B?

When multiplicand Y is multiplied by multiplier using bit-pair recoding in Booth's algorithm, partial products are generated according to the following table. The partial products for rows 5 and 8 are

Consider the circuit in the diagram. The operator represents Ex-OR. The D flip-flops are initialized to zeroes (cleared). The following data : 100110000 is supplied to the "data" terminal in nine cloc

Consider a boolean function f (w,x,y,z). Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i1=(w1,x1,y1,z1) and i2=(w2,x2,

You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip flo

The boolean function for a combinational circuit with four inputs is represented by the following Karnaugh map. Which of the product terms given below is an essential prime implicant of the function?

The majority function is a Boolean function f(x,y,z) that takes the value 1 whenever a majority of the variables x,y,z are 1. In the circuit diagram for the majority function shown below, the logic ga

Consider number represented in 4-bit gray code. Let be the gray code representation of a number n and let be the gray code of (n+1) (modulo 16) value of the number. Which one of the following function

We consider addition of two 2's complement numbers and . A binary Combinational Circuit for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by and the carryout by . W

Given a boolean function f , which of the following equations is NOT true?

Consider the circuit below. Which one of the following options correctly represents f (x,y,z)?

The following definite integral evaluates to

A set X can be represented by an array x[n] as follows Consider the following algorithm in which x,y and z are boolean arrays of size n; algorithm zzz(x[] , y[], z []) { int i; for (i=O; i < n; ++i) z

The vertices of graph G correspond to all subsets of a set of size n, for . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertic

Let S={1,2,3....,m},m 3. Let be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets that contain the element i. That is . Then

We are given a set where . A sample is drawn by selecting each independently with probability . The expected value of the smallest number in sample S is:

When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appe

Consider the polynomial , where . The minimum number of multiplications needed to evaluate p on an input x is:

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G=(V,E) with |V| divisible by 3 and DHAM3 be the problem of determining if a Hamltonian cycle exists in such graphs. Which one of the

x+y/2=9 3x+y=10 The value of the Frobenius norm for the above system of equations is

Let P, Q and R be sets, let denote the symmetric difference operator defined as . Using Venn diagrams, determine which of the following is/are TRUE? I. II.

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

Given a set of elements N = {1,2,...,n} and two arbitrary subsets A N and B N , how many of the n! permutations p from N to N satisfy min[p(A)]=min[p(B)], where min(S) is the smallest integer in the s

For each element in set of size 2n, an unbiased coin is tossed. The 2n coin tossed are independent. An element is chosen if the corresponding coin toss were head. The probability that exactly n elemen

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

Let T be a depth first search tree in a undirected graph G Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data indicates that if the temperature at noon is less than or equal to , the probabi

Let E,F and G be finite sets. Let X=(E F) - (F G) and Y = (E - (E G)) - (E - F). Which one of the following is true?

The vertices of graph G correspond to all subsets of a set of size n, for . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connec

Consider the following first order logic formula in which R is a binary relation symbol. , The formula is

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lions attack if they are hungry or threatened.

For the set N of natural numbers and a binary operation , an element is called an identity for f, if f (a, z) = a = f(z, a), for all . Which of the following binary operations have an identity? i. ii.

A relation R is defined on ordered pairs of integers as follows: (x,y)R(u,v) if x u and y v. Then R is

Let X, Y, Z be sets of sizes x, y and z respectively. Let W=X Y and E be the set of all subsets of W. The number of functions from Z to E is

In the 4B/5B encoding scheme, every 4 bits of data are encoded in a 5-bit codeword. It is required that the codewords have at most 1 leading and at most 1 trailing zero. How many are such codewords po

The vertices of graph G correspond to all subsets of a set of size n, for . Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree o

What are the eigenvalues of the matrix P given below

x+y/2=9 3x+y=10 What can be said about the Gauss-Siedel iterative method for solving the above set of linear equations?

What is the cardinality of the set of integers X defined below? , n is not divisible by either 2, 3 or 5}

F is an nxn real matrix. b is an nx1 real vector. Suppose there are two nx1 vectors, u and v such that u v , and Fu=b, Fv=b. Which one of the following statements is false?

Consider the following propositional statements: Which one of the following is true?

The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false?

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represen

Match the following iterative methods for solving algebraic equations and their orders of convergence.

Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit positi

In the working-set strategy, which of the following is done by the operating system to prevent thrashing? I. It initiates another process if there are enough extra frames. II. It selects a process to

Consider the solution to the bounded buffer producer/consumer problem by using general semaphores S, F, and E. The semaphore S is the mutual exclusion semaphore initialized to 1. The semaphore F corre

The arrival time, priority, and duration of the CPU and I/O bursts for each of three processes and are given in the table below. Each process has a CPU burst followed by an I/O burst followed by anoth

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leav

Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time

A computer system supports 32-bit virtual addresses as well as 32-bit physical addresses, Since the virtual address space is of the same size as the physical address space, the operating system design

The wait and signal operations of a monitor are implemented using semaphores as follows. In the following, x is a condition variable, mutex is a semaphore initialized to 1, x_sem is a semaphore initia

Consider the following snapshot of a system running n processes. Process i is holding instances of a resource R, for . Currently, all instances of R are occupied. Further, for all i , process i has pl

Consider three processes (process id 0,1,2, respectively) with compute time bursts 2,4, and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling

The process state transition diagram of an operating system is as given below. Which of the following must be FALSE about the above operating system?

For each of the four processes and . The total size in kilobytes (KB) and the number of segments are given below. P_1 P_2 P_3 P_4 The page size is 1 KB. The size of an entry in the page table is 4 byt

The atomic feth-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x . Consider

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leav

Consider three CPU-intensive processes, which require 10,20 and 30 time units and arrive at times 0,2, and 6, respectively. How many context switches are needed if the operating system implements a sh

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The roots is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i

Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and c[n+m] be another integer array. void xyz (int a[],int b[],int c[]){ int i, j, k; i=j=k=0; while((i < n) && (

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], no

The following function computes the value of correctly for all legal values and int func(int m, int n) { if (E) return 1; else return(func(m -1, n) + func(m - 1, n - 1)); } In the above function, whic

An implementation of a queue Q, using two stacks S1 and S2, is given below: void insert(Q,x){ push (S1,x); } void delete(Q){ if (stack-empty (S2))then if (stack-empty (S1))then{ print("Q is empty"); r

Consider the C code to swap two integers and these five statements: the code void swap(int *px,int *py){ *px=*px-*py; *py=*px+*py; *px=*py-*px; } S1 : will generate a compilation error S2 : may genera

Which one of the choices given below would be printed when the following program is executed ? #include struct test { int i; char *c; }st[] = {5, "become", 4, "better", 6, "jungle", 8, "ancestor", 7,

Which of the following sequences of array elements forms a heap?

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], no

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to

Given two arrays of numbers and where each number is 0 or 1, the fastest algorithm to find the largest span(i,j) such that , or report that there is no such span,

Which one of the choices given below would be printed when the following program is executed? #include void swap (int *x, int *y) { static int *temp; temp = x; x = y; y = temp; } void printab () { sta

Consider the following code written in a pass-by reference language like FORTAN and these statements about the code. subroutine swap(ix,iy) it = ix L1 : ix = iy L2 : iy = it end ia = 3 ib = 8 call swa

In a binary max heap containing n numbers, the smallest element can be found in time

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?

Which one of the choices given below would be printed when the following program is executed? #include int a1[] = {6, 7, 8, 18, 34, 67}; int a2[] = {23, 56, 28, 29}; int a3[] = {-12, 27, -31}; int *x[

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element , is?

An element in an array X is called a leader if it is grater than all elements to the right of it in X. The best algorithm to find all leaders in an array.

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element , is

Let L1 be regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?

In the context-free grammar below, S is the start symbol, a and b are terminals, and denotes the empty string. The grammar generates the language

In the automaton below, s is the start state and t is the only final state. Consider the strings . Which of the following statements is true?

For , let d(s) denote the decimal value of s (e.g. d(101)=5). Let L={s (0+1)*| d(s) mod 5=2 and d(s) mod 7 4} Which one of the following statements is true?

Let L be a context-free language and M a regular language. Then the language is

Consider the following statements about the context-free grammer 1. G is ambiguous 2. G produces all strings with equal number of a's and b's 3. G can be accepted by a deterministic PDA. Which combina

Let Which of these languages are NOT context free?

Let L be a regular language. Consider the constructions on L below: I. II. III. IV. Which choice of L is best suited to support your answer above?

Consider the regular grammar below The Myhill-Nerode equivalence classes for the language generated by the grammar are

Which of the following statements about regular languages is NOT true ?

Which regular expression best describes the language accepted by the non-deterministic automaton below?

In the context-free grammar below, S is the start symbol, a and b are terminals, and denotes the empty string Which of the following strings is NOT generated by the grammar?

If s is a string over (0+1)*, then let denote the number of 0's in s and the number of 1's in s. Which one of the following languages is not regular?

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet where is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} wh

Let L be a regular language. Consider the constructions on L below: I. II. III. IV. Which of the constructions could lead to a non-regular language?

Consider the regular language L = (111 + 11111)* . The minimum number of states in any DFA accepting this languages is

For a state machine with the following state diagram the expression for the next state in terms of the current state S and the input variables x and y is

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?