GATE CSE 2001 PYQ

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort ?

Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectivel

Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectivel

Let and be two positive functions of n. Which of the following statements is correct ?

Which of the following statements is false ?

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

Suppose a processor does not have any stack pointer register. Which of the following statements is true ?

A processor needs software interrupt to

More than one word are put in one cache block to

A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged

Consider the following data path of a simple non-pilelined CPU. The registers A, B, A1, A2, MDR, the bus and the ALU are 8-bit wide. SP and MAR are 16- bit registers. The MUX is of size 8x(2:1) and th

A low memory can be connected to 8085 by using

Which is the most appropriate match for the items in the first column with the items in the second column

Consider a relation geq which represents "greater than or equal to", that is, (x,y) geq only if y x: create table geq ( ib integer not null ub integer not null primary key ib foreign key (ub) referenc

Consider a schema R(A,B,C,D) and functional dependencies A B and C D. Then the decomposition of R into R1(AB) and R2(CD) is :

R,(A,B,C,D) is a relation. Which of the following does not have a lossless join, dependency preserving BCNF decomposition ?

Which of the following relational calculus expressions is not safe ?

Suppose the adjacency relation of vertices in a graph is represented in a table Adj(X,Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length ?

Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. Then the relational algebra expression is always equal to :

Given the following Karnaugh map, which one of the following represents the minimal sum-of-Products of the map ?

Consider the circuit given below the initial state . The state of the circuit is given by the value Which one of the following is the correct state sequence of the circuit ?

Consider the following circuit with initial state Q0 = Q1 = 0. The D flip-flops are positive edged triggered and have set up times 20 nanosecond and hold times 0.

Consider the circuit shown below. The output of a 2:1 Mux is given by the function (ac' + bc). Which of the following is true?

The 2's complement representation of is hexadecimal is

Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectivel

Consider the following relations: R1(a,b) iff (a+b) is even over the set of integers R2(a,b) iff (a+b) is odd over the set of integers R3(a,b) iff a.b > 0 over the set of non-zero rational numbers R4(

How many 4-digit even numbers have all 4 digits distinct?

Consider two well-formed formulas in prepositional logic. Which of the following statements is correct?

How many undirected graphs (not necessarily connected) can be constructed out of a given set V={ } of n vertices ?

Consider the following statements: S1: There exists infinite sets A, B, C such that [latex]A (B C)[/latex] is finite. S2: There exists two irrational numbers x and y such that (x+y) is rational. Which

Let be a function, and let E and F be subsets of A. Consider the following statements about images. Which of the following is true about S1 and S2?

Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?

Consider the following statements: S1: The sum of two singular nxn matrices may be non-singular S2: The sum of two nxn non-singular matrices may be singular. Which of the following statements is corre

Which of the following statements is false ?

Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4 KB, what is the approximate size of the page table ?

Which of the following requires a device driver ?

Consider Peterson's algorithm for mutual exclusion between two concurrent processes i and j . The program executed by process is shown below. repeat flag [i] = true; turn = j; while ( P ) do no-op; En

Consider a set of n tasks with known runtimes to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput ?

Which of the following does not interrupt a running process ?

Where does the swap space reside ?

Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will.

What is the minimum number of stacks of size n required to implement a queue to size n ?

What is printed by the print statements in the program P1 assuming call by reference parameter passing ? Program P1() { x = 10; y = 3; func1(y,x,x); print x; print y; } func1(x,y,z) { y = y+4; z = x+y

Consider the following program Program P2 var n: int: procedure W(var x: int) begin x=x+1; print x; end procedure D begin var n: int; n=3; W(n); end begin //beginP2 n=10; D; end If the language has dy

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array ( ) , the index of the

Consider the following three functions : [P1] int * g (void) { int x= 10; return (&x); } [P2] int * g (void) { int * px; *px= 10; return px; } [P3] int *g (void) { int *px; px = (int *) malloc (sizeof

Consider the following two statements : S1: { } is a regular language S2 : { } is a regular language Which of the following statements is correct?

Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.

Consider a DFA over = {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have ?

Consider the following languages : L1 = {ww| w {a,b}*} L2 = {w w {a,b} *, is the reverse of w} L3 = { | i is an integer} L4 ={ | i is an integer} Which of the languages are regular ?

Which of the following statements true ?

Consider the following problem x . Given a Turing machine M over the input alphabet , any state q of M. And a word w ) does the computation of M on w visit the state q ? Which of the following stateme