GATE CSE 2001
View Questions

GATE CSE

1
Let f(n) = n2 log n and g(n) = n(log n)10 be two positive functions of n. Which of the following statements is correct?
2
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 $$\left( {i \le n} \right)$$, the index of the parent is
3
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?
4
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
5
Which of the following statements is false?
6
More than one word are put in one cache block to
7
A $$CPU$$ has $$32$$-bit memory address and a $$256$$ $$KB$$ cache memory. The cache is organized as a $$4$$-way set associative cache with cache block size of $$16$$ bytes.

(a)$$\,\,\,\,$$ What is the number of sets in the cache?
(b)$$\,\,\,\,$$ What is the size (in bits) of the tag field per cache block?
(c)$$\,\,\,\,$$ What is the number and size of comparators required for tag matching?
(d)$$\,\,\,\,$$ How many address bits are required to find the byte offset within a cache block?
(e)$$\,\,\,\,$$ What is the total amount of extra memory (in bytes) required for the tag bits?

8
Which is the most appropriate match for the items in the first column with the items in the second column?
$$X.$$ Indirect Addressing
$$Y.$$ Indexed Addressing
$$Z.$$ Base Register Addressing
$${\rm I}.\,\,$$Array implementation
$${\rm II}.\,\,$$Writing relocatable code
$${\rm III}.\,\,$$Passing array as parameter
9
Arrange the following configuration for CPU in decreasing order of operating speeds: Hardwired control, vertical micro- programming, horizontal micro-programming
10
Consider the following datapath of a simple non-pipelined $$CPU.$$ The registers $$A,B,$$ $${A_1},{A_2},$$ $$MDR,$$ the bus and the $$ALU$$ are $$8$$-bit wide. $$SP$$ and $$MAR$$ are $$16$$-bit registers. The $$MUX$$ is of size $$8 \times \left( {2:1} \right)$$ and the $$DEMUX$$ is of size $$8 \times \left( {1:2} \right)$$. Each memory operation takes $$2$$ $$CPU$$ clock cycles and uses $$MAR$$ (Memory Address Register) and $$MDR$$ (Memory Data register). $$SP$$ can be decremented locally. GATE CSE 2001 Computer Organization - Alu Data Path and Control Unit Question 9 English

The $$CPU$$ instruction $$''push$$ $$r'',$$ where $$r=A$$ or $$B,$$ has the specification
$$\eqalign{ & \,\,\,\,\,\,\,\,\,\,\,\,\,M\left[ {SP} \right] \leftarrow r \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,SP \leftarrow SP - 1 \cr} $$
How many $$CPU$$ clock cycles are needed to execute the $$''push$$ $$r''$$ instruction?

11
A processor needs software interrupt to
12
Consider an 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 from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?
13
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = { v1,v2,........,vn } of n vertices?
14
Which of the following relational calculus expressions is not safe?
15
Consider a schema $$R(A,B,C,D)$$ and functional dependencies $$A \to B\,\,$$ and $$C \to D\,\,$$. Then the decomposition of $$R$$ into $${R_1}\left( {AB} \right)$$ and $${R_2}\left( {CD} \right)$$ is
16
$$R(A,B,C,D)$$ is a relation. Which of the following does not have a lossless-join, dependency preserving $$BCNF$$ decomposition?
17
Consider the circuit given below with initial state $${Q_0} = 1,\,\,{Q_1} = {Q_2} = 0.$$ The state of the circuit is given by the value of $$4{Q_2} + 2{Q_1} + {Q_{0.}}$$ GATE CSE 2001 Digital Logic - Sequential Circuits Question 23 English

Which one of the following is correct state sequence of the circuit?

18
Consider the following circuit with initial state $${Q_0} = {Q_1} = 0.$$ The $$D$$ Flip-Flops are positive edge triggered and have set up times $$20$$ nanosecond and hold times $$0.$$ GATE CSE 2001 Digital Logic - Sequential Circuits Question 16 English 1

Consider the following timing diagram of $$X$$ and $$C;$$ the clock period of $$C>40$$ nanosecond which one is the correct plot of $$Y?$$

GATE CSE 2001 Digital Logic - Sequential Circuits Question 16 English 2
19
Consider the circuit shown below. The output of a $$2:1$$ Mux is given by the function $$(ac+bc)$$ GATE CSE 2001 Digital Logic - Combinational Circuits Question 16 English

Which of the following is true?

20
The $$2's$$ complement representation of $${\left( { - 539} \right)_{10}}$$ in hexadecimal is
21
Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map? GATE CSE 2001 Digital Logic - K Maps Question 12 English
22
Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day ?
23
Let $$f:\,A\, \to B$$ be a function, and let E and F be subsets of A. Consider the following statements about images.

$$S1:\,f\,\left( {E\, \cup \,F} \right)\, = \,f\left( E \right)\, \cup \,f\,\left( F \right)$$
$$S2:\,f\,\left( {E\, \cap \,F} \right)\, = \,f\left( E \right)\, \cap \,f\,\left( F \right)$$
Which of the following is true about S1 and S2?

24
Consider the following statements:

S1: There exist infinite sets A, B, C such that
$$A\, \cap \left( {B\, \cup \,C} \right)$$ is finite.
S2: There exist two irrational numbers x and y such that (x + y) is rational.
Which of the following is true about S1 and S2?

25
Consider the following relations:
$${R_1}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,\left( {a + b} \right)$$ is even over the set of integers
$${R_2}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,\left( {a + b} \right)$$ is odd over the set of integers
$${R_3}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,a.b > 0$$ over the set of non-zero rational numbers
$${R_4}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,\left| {a - b} \right| \le 2$$ over the set of natural numbers

Which of the following statements is correct?

26
Consider the following statements:
S1: The sum of two singular n x n matrices may be non-singular
S2: The sum of two n x n non-singular matrices may be singular

Which of the following statements is correct?

27
How many 4 digit even numbers have all 4 digits distinct?
28
how many undirected graphs (not necessarily connected) can be constructed out of a given $$\,\,\,\,V = \left\{ {{v_1},\,\,{v_2},\,....,\,\,{v_n}} \right\}$$ of $$n$$ vertices?
29
The value of the integral is $${\rm I} = \int\limits_0^{{\raise0.5ex\hbox{$\scriptstyle \pi $} \kern-0.1em/\kern-0.15em \lower0.25ex\hbox{$\scriptstyle 4$}}} {{{\cos }^2}x\,dx} $$
30
Consider two well-formed formulas in propositional logic
$$F1:P \Rightarrow \neg P$$
$$F2:\left( {P \Rightarrow \neg P} \right) \vee \left( {\neg P \Rightarrow } \right)$$

Which of the following statements is correct?

31
Which of the following statements is false?
32
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
33
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
34
Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the approximate size of the page table?
35
Which of the following requires a device driver?
36
Consider a disk with following specifications: $$20$$ surface, $$1000$$ tracks/surface, $$16$$ sectors/track, data density $$1$$ $$KB/sector,$$ rotation speed $$3000$$ $$rpm.$$ The operating system initiates the transfer between the disk and the memory sector-wise. Once the head has been placed on the right track, the disk reads a sector in a single scan. It reads bits from the sector while the head is passing over the sector. The read bits are formed into bytes in a serial $$=$$in-parallel-out buffer and each byte is then transferred to memory. The disk writing is exactly a complementary process. For parts $$(c)$$ and $$(d)$$ below, assume memory read-write time $$= 0.1$$ micro-second/ byte, interrupt driven transfer has an interrupt overhead $$= 0.4$$ microseconds, the $$DMA$$ initialization and termination overhead is negligible compared to the total sector transfer time. $$DMA$$ requests are always granted.

(a) What is the total capacity of the disk?
(b) What is the data transfer rate?
(c) What is the percentage of time the $$CPU$$ is required for this disk $${\rm I}/O$$ for byte-wise interrupts driven transfer?
(d) What is the maximum percentage of time the $$CPU$$ is held up for this disk $${\rm I}/O$$ for cycle-stealing $$DMA$$ transfer ?

37
Consider a disk with the $$100$$ tracks numbered from $$0$$ to $$99$$ rotating at $$3000$$ $$rpm.$$ The number of sectors per track is $$100.$$ the time to move the head between two successive tracks is $$0.2$$ milliseconds.

(a) Consider a set of disk requests to read data from tracks $$32, 7, 45, 5$$ and $$10.$$ Assuming that the elevator algorithm is used to schedule disk requests, and the head is initially at track $$25$$ moving up (towards larger track numbers), what is the total seek time for servicing the requests?
(b) Consider an initial set of $$100$$ arbitrary disk requests and assume that no new disk requests arrive while servicing these requests. If the head is initially at track $$0$$ and the elevator algorithm is used to schedule disk requests, what is the worst case time to complete all the requests?

38
Consider a set of $$n$$ tasks with known runtimes $${r_1},{r_2},.....\,{r_n}\,\,$$ to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?.
39
A processor needs software interrupt to
40
A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged
41
Which of the following does not interrupt a running process?
42
Where does the swap space reside?
43
Suppose a processor does not have any stack pointer register. Which of the following statements is true?
44
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; 
     Enter critical section, perform actions, then 
     exit critical section 
     Flag[i]=false; 
     Perform other non-critical section actions. 
 Until false;
For the program to guarantee mutual exclusion, the predicate P in the while loop should be
45
Consider the following three C 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 (size of (int));
       *px = 10;
       return px;
     }
Which of the above three functions are likely to cause problems with pointers?
46
Consider the following C program:
void abc(char *s)
{
   if(s[0]=='\0') return;
   abc(s+1);
   abc(s+1);
   printf("%c",s[0]);
}
main()
{ 
   abc("123");
}
(a) What will be the output of the program?
(b) If abc(s) is called with a null-terminated string s of length n characters (not counting the null ('\0') character), how many characters will be printed by abc(s)?
47
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+z;
}
48
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     \\begin P2
      n = 10;
      D;
end
If the language has dynamic scooping and parameters are passed by reference, what will be printed by the program?
49
Consider the following problem $$X.$$ Given a Turing machine $$M$$ over the input alphabet $$\sum , $$ any state $$q$$ of $$M$$ And a word $$w\,\,\varepsilon \,\,\sum {^ * ,} $$ does the computation of $$M$$ on $$w$$ visit the state $$q''$$

Which of the following statements about $$X$$ is correct?

50
Consider the following two statements;
$${S_1}\,\,:\,\,\left\{ {{0^{2n}}\left| {n \ge 1} \right.} \right\}$$ is a regular language
$${S_2}\,\,:\,\,\left\{ {{0^m}{1^n}{0^{m + n}}\left| {m \ge 1} \right.\,\,and\,\,n \ge \left. 1 \right\}} \right.$$ is a regular language

Which of the following statements is correct?

51
Given an arbitrary non-deterministic finite automaton $$(NFA)$$ with $$N$$ states, the maximum number of states in an equivalent minimized $$DFA$$ is at least
52
Consider a $$DFA$$ over $$\sum { = \left\{ {a,\,\,b} \right\}} $$ 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?
53
Consider the following languages:
$${L_1} = \left\{ {w\,w\left| {w \in {{\left\{ {a,\,b} \right\}}^ * }} \right.} \right\}$$
$${L_2} = \left\{ {w\,{w^R}\left| {w \in {{\left\{ {a,\,b} \right\}}^ * },} \right.{w^R}\,\,} \right.$$ is the reverse of $$\left. w \right\}$$
$${L_3} = \left\{ {{0^{2i}}\left| {i\,\,} \right.} \right.$$ is an integer$$\left. \, \right\}$$
$${L_4} = \left\{ {{0^{{i^2}}}\left| {i\,\,} \right.} \right.$$ is an integer$$\left. \, \right\}$$

Which of the languages are regular?

54
Which of the following statement is true?
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12