GATE CSE 2011 PYQ

Which of the following algorithm design technique is used in merge sort?

An undirected graph G(V, E) contains n (n 2) nodes named v1 , v2 ,...,vn. Two nodes vi , vj are connected if and only if 0 |i-j| 2. Each edge (vi,vj ) is assigned a weight i+j. A sample graph with n=4

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

Which of the given options provides the increasing order of asymptotic complexityoffunctions f1, f2, f3 and f4?

Let be defined by and for all integers . Which of the following represents the order of growth of as a function of n?

An undirected graph G(V, E) contains n (n 2) nodes named v1 , v2 ,...,vn. Two nodes vi , vj are connected if and only if 0 |i-j| 2. Each edge (vi,vj ) is assigned a weight i+j. A sample graph with n=4

Four matrices M1, M2, M3 and M4 are dimensions p x q, q x r, r x s and s x t respectively can be multiplied in several ways with different number of total scalar multiplications. For example When mult

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below. Let Li denote the length of the longest monotonically increasing seque

Which of the following statements about peephole optimization is False?

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e are

Number of comparisons required for an unsuccessful search of an element in a sequential search organized, fixed length, symbol table of length L is

Consider two binary operators ' 'and ' ' with the precedence of operator being lower than that of the operator . Operator is right associative while operator is left associative. Which one of the foll

Which of the following sentences can be generated by

In a compiler, keywords of a language are recognized during

The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

In compiler terminology reduction in strength means

A symbol table of length 152 is processing 25 entries at any instant. What is occupation density?

Which variable does not drive a terminal string in grammar? S -> AB A -> a B -> b B -> C

In which layer of network architecture, the secured socket layer (SSL) is used?

Consider different activities related to email. m1: Send an email from a mail client to a mail server m2: Download an email from mailbox server to a mail client m3: Checking email in a web browser Whi

Lightweight Directory Access protocol is used for

The hamming distance between the octets of 0xAA and 0x55 is

Consider a network with five nodes, N1 to N5, as shown below The network uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as follow

The broadcast address for IP network 172.16.0.0 with subnet mask 255.255.0.0 is

What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and horizontal sweep time of (including of retrace time)?

The network protocol which is used to get MAC address of a node by providing IP address is

HTML (Hyper Text Markup Language) has language elements which permit certain actions other than describing the structure of the web document. Which one of the following actions is NOT supported by pur

One SAN switch has 24 ports. All 24 supports 8 Gbps Fiber Channel technology. What is the aggregate bandwidth of that SAN switch?

An example of poly-alphabetic substitution is

Consider a network with five nodes, N1 to N5, as shown below The network uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as follow

The encoding technique used to transmit the signal in giga ethernet technology over fiber optic medium is

Data is transmitted continuously at 2.048 Mbps rate for 10 hours and received 512 bits errors. What is the bit error rate?

A layer-4 firewall (a device that can look at all protocol headers up to the transport layer) CANNOT

Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Del

Which RAID level gives block level striping with double distributed parity?

If a microcomputer operates at 5 MHz with an 8-bit bus and a newer version operates at 20 MHz with a 32-bit bus, the maximum speed-up possible approximately will be

On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine, is given to transfer 500 bytes from an I/O device to memory. Initialize the address regist

A processor takes 12 cycles to complete an instruction I. The corresponding pipelined processor uses 6 stages with the execution times of 3,2,5,4,6 and 2 cycles respectively. What is the asymptotic sp

Two control signals in microprocessor which are related to Direct Memory Access (DMA) are

Find the memory address of the next instruction executed by the microprocessor (8086), when operated in real mode for CS=1000 and IP=E000

An application loads 100 libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as 10ms. Rotational speed of disk is 6000r

Number of chips ( RAM) needed to provide a memory capacity of 2048 bytes

The search concept used in associative memory is

Consider a direct mapped cache with 64 blocks and a block size of 16 bytes. To what block number does the byte address 1206 map to

Consider a hypothetical processor with an instruction of type LW R1, 20(R2), which during execution reads a 32-bit word from memory and stores it in a 32-bit register R1. The effective address of the

A computer handles several interrupt sources of which the following are relevant for this question. Interrupt from CPU temperature sensor (raises interrupt if CPU temperature is too high) Interrupt fr

A fast wide SCSI-II disk drive spins at 7200 RPM, has a sector size of 512 bytes, and holds 160 sectors per track. Estimate the sustained transfer rate of this drive

MOV [BX], AL type of data addressing is called ?

In DMA transfer scheme, the transfer scheme other than burst mode is

An 8KB direct mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor generates 32-bit addresses. The cache controller maintains the tag information for each cach

In functional dependency Armstrong inference rules refers to

Consider a relational table with a single record for each registered student with the following attributes. 1. Registration_Number: Unique registration number for each registered student 2. UID: Uniqu

Consider a relational table r with sufficient number of records, having attributes and let . Two queries Q1 and Q2 are given below. where c is a constant where and are constants The database can be co

What is the equivalent serial schedule for the following transactions?

Which normal form is based on the concept of 'full functional dependency' is

Database table by name Loan_Records is given below. What is the output of the following SQL query? SELECT count(*) FROM( (SELECT Borrower, Bank_Manager FROM Loan_Records) AS S NATURAL JOIN (SELECT Ban

Consider a database table T containing two columns X and Y each of type integer. After the creation of the table, one record (X=1,Y=1) is inserted in the table. Let MX and MY denote the respective max

In an RS flip-flop, if the S line (Set line) is set high (1) and the R line (Reset line) is set low (0), then the state of the flip-flop is :

The output expression of the following gate network is

The minimum number of D flip-flops needed to design a mod-258 counter is

Consider the following circuit involving three D-type flip-flops used in a certain type of counter configuration. If all the flip-flops were reset to 0 at power on, what is the total number of distinc

The simplified SOP (Sum of Product) form of the Boolean Algebra is

In Boolean algebra, rule

How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?

Which one of the following circuits is NOT equivalent to a 2-input XNOR (exclusive NOR) gate?

Consider the following circuit involving three D-type flip-flops used in a certain type of counter configuration. If at some instance prior to the occurrence of the clock edge, P. Q and R have a value

Evaluate (X xor Y) xor Y?

What is the decimal value of the floating-point number C1D00000 (hexadecimal notation)? (Assume 32-bit, single precision floating point IEEE representation)

Given , what will be the evaluation of the definite integral ?

Consider the matrix as given below. Which one of the following provides the CORRECT values of eigenvalues of the matrix?

K4 and Q3 are graphs with the following structures Which one of the following statements is TRUE in relation to these graphs?

Which one of the following is true?

What is the matrix that represents rotation of an object by about the origin in 2D?

Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate

A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected

If and are square matrices with same order and is symmetric, then is

If two fair coins are flipped and at least one of the outcomes is known to be a head, what is the probability that both outcomes are heads?

If the difference between the expectation of the square of random variable and the square of the expectation of the random variable is denoted by R then

n-th derivative of is

How many edges are there in a forest with v vertices and k components?

If node A has three siblings and B is parent of A, what is the degree of A?

The arithmetic mean of attendance of 49 students of class A is 40% and that of 53 students of class B is 35%. Then the percentage of arithmetic mean of attendance of class A and B is

Three coins are tossed simultaneously. The probability that they will fall two heads and one tail is

Given X: 0 10 16 Y: 6 16 28 The interpolated value X=4 using piecewise linear interpolation is

Consider a finite sequence of random values . Let be the mean and be the standard deviation of X .Let another finite sequence Y of equal length be derived from this as , where a and b are positive con

Consider the following table of arrival time and burst time for three processes P0, P1 and P2. The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arriva

Which of the following UNIX command allows scheduling a program to be executed at the specifies time?

Belady's anomaly means

Below is the precedence graph for a set of tasks to be executed on a parallel processing system S. What is the efficiency of this precedence graph on S if each of the tasks takes the same time and the

Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the following is TRUE?

A total of 9 units of a resource type available, and given the safe state shown below, which of the following sequence will be a safe state?

If the page size in a 32-bit machine is 4K bytes then the size of page table is

A thread is usually defined as a 'light weight process' because an operating system (OS) maintains smaller data structures for a thread than for a process. In relation to this, which of the followings

In a system using single processor, a new process arrives at the rate of six processes per minute and each such process requires seven seconds of service time. What is the CPU utilization?

Consider a 32-bit machine where four-level paging scheme is used. If the hit ratio to TLB is 98%, and it takes 20 nanosecond to search the TLB and 100 nanoseconds to access the main memory what is eff

Let the page fault service time be 10ms in a computer with average memory access time being 20ns. If one page fault is generated for every memory accesses, what is the effective access time for the me

The following table shows the processes in the ready queue and time required for each process for completing its job. If round-robin scheduling with 5 ms is used what is the average waiting time of th

There are three processes in the ready queue. When the currently running process requests for I/O how many process switches take place?

In Java, after executing the following code what are the values of x, y and z? int x, y=10; z=12; x=y++ + z++;

What does the following fragment of C-program print? char c []="GATE2011"; char *p =c; printf ("%s", p + p[3]- p[ 1 ]);

What is the output of the following C code? #include int main() { int index; for(index=1; index<=5; index++) { printf("%d", index); if (index==3) continue; } }

Consider the following pseudocode x:=1; i:=1; while (x 500) begin x:=2^x; i:=i+1; end What is the value of i at the end of the pseudocode?

Consider the following recursive C function that takes two arguments unsigned int foo(unsigned int n, unsigned int r) { if (n > 0) return (n%r + foo (n/r, r )); else return 0; } What is the return val

The in-order traversal of a tree resulted in FBGADCE. Then the pre-order traversal of that tree would result in

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

Find the output of the following Java code line System.out.printIn(math.floor(-7.4))

Consider the following recursive C function that takes two arguments unsigned int foo(unsigned int n, unsigned int r) { if (n > 0) return (n%r + foo (n/r, r )); else return 0; } What is the return val

The average depth of a binary search tree is

Which of the following pairs have DIFFERENT expressive power?

Definition of a language L with alphabet {a} is given as following L={ |k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?

Consider the languages L1, L2 and L3 as given below and Which of the following statements is NOT TRUE?

A problem whose language is recursion is called?

A deterministic finite automation (DFA)D with alphabet = {a,b} is given below Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?

Let P be a regular language and Q be a context free language such that Q P. (For example, let P be the language represented by the regular expression p*q* and Q be Then which of the following is ALWAY