## GATE CSE 2001

Exam Held on Thu Jan 01 1970 00:00:00 GMT+0000 (Coordinated Universal Time)
Click View All Questions to see questions one by one or you can choose a single question from below.

## Algorithms

Let f(n) = n<sup>2</sup> log n and g(n) = n(log n)<sup>10</sup> be two positive...
Consider any array representation of an n element binary heap where the elements...
Randomized quicksort is an extension of quicksort where the pivot is chosen rand...

## Compiler Design

The process of assigning load addresses to the various parts of the program and ...
Which of the following statements is false?

## Computer Organization

More than one word are put in one cache block to
A $$CPU$$ has $$32$$-bit memory address and a $$256$$ $$KB$$ cache memory. The c...
Which is the most appropriate match for the items in the first column with the i...
Arrange the following configuration for CPU in decreasing order of operating spe...
Consider the following datapath of a simple non-pipelined $$CPU.$$ The registers...
A processor needs software interrupt to

## Data Structures

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be...
How many undirected graphs (not necessarily connected) can be constructed out of...

## Database Management System

Consider a schema $$R(A,B,C,D)$$ and functional dependencies $$A \to B\,\,$$ and...
$$R(A,B,C,D)$$ is a relation. Which of the following does not have a lossless-jo...
Which of the following relational calculus expressions is not safe?

## Digital Logic

The $$2's$$ complement representation of $${\left( { - 539} \right)_{10}}$$ in h...
Given the following Karnaugh map, which one of the following represents the mini...
Consider the circuit shown below. The output of a $$2:1$$ Mux is given by the fu...
Consider the circuit given below with initial state $${Q_0} = 1,\,\,{Q_1} = {Q_2... Consider the following circuit with initial state$${Q_0} = {Q_1} = 0.$$The$$D...

## Discrete Mathematics

Consider two well-formed formulas in propositional logic <br>$$F1:P \Rightarrow... Seven (distinct) car accidents occurred in a week. What is the probability that ... Let$$f:\,A\, \to B$$be a function, and let E and F be subsets of A. Consider t... Consider the following statements: <p> S1: There exist infinite sets A, B, C su... Consider the following relations: <br>$${R_1}\,\,\left( {a,\,\,b} \right)\,\,\,i...
Consider the following statements: <br> S1: The sum of two singular n x n matric...
How many 4 digit even numbers have all 4 digits distinct?
how many undirected graphs (not necessarily connected) can be constructed out of...
The value of the integral is $${\rm I} = \int\limits_0^{{\raise0.5ex\hbox{\scri... ## Operating Systems A processor needs software interrupt to Consider a set of$$n$$tasks with known runtimes$${r_1},{r_2},.....\,{r_n}\,\,...
A CPU has two modes-privileged and non-privileged. In order to change the mode f...
Which of the following does not interrupt a running process?
Where does the swap space reside?
Suppose a processor does not have any stack pointer register. Which of the follo...
Consider Peterson’s algorithm for mutual exclusion between two concurrent proces...
Which of the following statements is false?
The process of assigning load addresses to the various parts of the program and ...
Consider a virtual memory system with $$FIFO$$ page replacement policy. For an a...
Consider a machine with 64 MB physical memory and a 32-bit virtual address space...
Which of the following requires a device driver?
Consider a disk with following specifications: $$20$$ surface, $$1000$$ tracks/s...
Consider a disk with the $$100$$ tracks numbered from $$0$$ to $$99$$ rotating a...

## Programming Languages

What is printed by the print statements in the program P1 assuming call by refer...
Consider the following program <pre><code class="pascal">Program P2 var n:...
Consider the following three C functions: <pre><code>[P1] int*g(void) { ...
Consider the following C program: <pre><code>void abc(char *s) { if(s[0]=='\0...

## Theory of Computation

Consider the following two statements; <br>$${S_1}\,\,:\,\,\left\{ {{0^{2n}}\lef... Given an arbitrary non-deterministic finite automaton$$(NFA)$$with$$N$$state... Consider a$$DFA$$over$$\sum { = \left\{ {a,\,\,b} \right\}} $$accepting all ... Consider the following languages: <br>$${L_1} = \left\{ {w\,w\left| {w \in {{\le...
Which of the following statement is true?
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the inpu...