# GATE CSE 2009

 Question 1
Which one of the following in NOT necessarily a property of a Group?
 A Commutativity B Associativity C Existence of inverse for every element D Existence of identity
Discrete Mathematics   Group Theory
Question 1 Explanation:
 Question 2
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n$\geq$2.
 A 2 B 3 C n-1 D n
Discrete Mathematics   Graph Theory
Question 2 Explanation:
 Question 3
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
 A No two vertices have the same degree. B At least two vertices have the same degree. C At least three vertices have the same degree. D All vertices have the same degree.
Discrete Mathematics   Graph Theory
Question 3 Explanation:
 Question 4
Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}. Which one of the following is TRUE?
 A R is symmetric but NOT antisymmetric B R is NOT symmetric but antisymmetric C R is both symmetric and antisymmetric D R is neither symmetric nor antisymmetric
Discrete Mathematics   Relation
Question 4 Explanation:
 Question 5
$(1217)_{8}$ is equivalent to
 A $(1217)_{16}$ B $(028F)_{16}$ C $(2297)_{10}$ D $(0B17)_{16}$
Digital Logic   Number System
Question 5 Explanation:
 Question 6
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?
 A 2 B 3 C 4 D 5
Digital Logic   Boolean Algebra
Question 6 Explanation:
 Question 7
How many 32K x 1 RAM chips are needed to provide a memory capacity of 256Kbytes?
 A 8 B 32 C 64 D 128
Computer Organization   Memory Chip Design
Question 7 Explanation:
 Question 8
A CPU generally handles an interrupt by executing an interrupt service routine
 A As soon as an interrupt is raised B By checking the interrupt register at the end of fetch cycle. C By checking the interrupt register after finishing the execution of the current instruction. D By checking the interrupt register at fixed time intervals.
Computer Organization   Interrupt
Question 8 Explanation:
 Question 9
In which one of the following page replacement policies, Belady's anomaly may occur?
 A FIFO B Optimal C LRU D MRU
Operating System   Memory Management
Question 9 Explanation:
 Question 10
The essential content(s) in each entry of a page table is / are
 A Virtual page number B Page frame number C Both virtual page number and page frame number D Access right information
Operating System   Memory Management
Question 10 Explanation:
There are 10 questions to complete.