GATE 2009
Question 1 
Which one of the following in NOT necessarily a property of a Group?
Commutativity
 
Associativity  
Existence of inverse for every element
 
Existence of identity 
So, commutativity is not required.
Question 2 
What is the chromatic number of an nvertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
2  
3  
n1  
n 
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Question 3 
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
No two vertices have the same degree.  
At least two vertices have the same degree.  
At least three vertices have the same degree.  
All vertices have the same degree.

If all vertices have different degrees, then the degree sequence will be {1,2,3,....n1}, it will not have ‘n’( A simple graph will not have edge to itself, so it can have edges with all other (n1) vertices). Degree sequence has only (n1) numbers, but we have ‘n’ vertices. So, by Pigeonhole principle there are two vertices which has same degree.
Method 2:
A) Consider a triangle, all vertices has same degree, so it is false
C) Consider a square with one diagonal, there are less than three vertices with same degree, so it is false
D) Consider a square with one diagonal, vertices have different degrees. So, it is false.
We can conclude that option B is correct.
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?
R is symmetric but NOT antisymmetric
 
R is NOT symmetric but antisymmetric  
R is both symmetric and antisymmetric  
R is neither symmetric nor antisymmetric 
Antisymmetric Relation: A relation R on a set A is called antisymmetric if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.
In the given relation R, for (x,y) there is no (y,x). So, this is not Symmetric. (x,z) is in R also (z,x) is in R, but as per antisymmetric relation, x should be equal to z, where this fails.
So, R is neither Symmetric nor Antisymmetric.
Question 5 
(1217)_{8} is equivalent to
(1217)_{16}
 
(028F)_{16}  
(2297)_{10}  
(0B17)_{16} 
Divide the bits into groups, each containing 4 bits.
= (0010 1000 1111)_{2}
= (28F)_{16}
Question 6 
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2input NOR gates?
2  
3  
4  
5 
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1^{st} NOR (A+C)’. Let X = (A+C)’
2^{nd} NOR (B+C)’. Let Y = (B+C)’
3^{rd} NOR (X+Y)’
Question 7 
How many 32K × 1 RAM chips are needed to provide a memory capacity of 256Kbytes?
8  
32  
64  
128 
Needed memory capacity = 256K  bytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1 = 64
Question 8 
A CPU generally handles an interrupt by executing an interrupt service routine
As soon as an interrupt is raised.  
By checking the interrupt register at the end of fetch cycle.  
By checking the interrupt register after finishing the execution of the current instruction.  
By checking the interrupt register at fixed time intervals. 
Question 9 
In which one of the following page replacement policies, Belady’s anomaly may occur?
FIFO  
Optimal  
LRU  
MRU 
Question 10 
The essential content(s) in each entry of a page table is/are
Virtual page number  
Page frame number  
Both virtual page number and page frame number  
Access right information 
Virtual page number can represents index in the page table to get the page frame number.
Question 11 
What is the number of swaps required to sort n elements using selection sort, in the worst case?
θ(n)  
θ(n log n)  
θ(n^{2})  
θ(n^{2} logn) 
Question 12 
The language generated by the above grammar over the alphabet {a,b} is the set of
all palindromes.  
all odd length palindromes.  
strings that begin and end with the same symbol.  
all even length palindromes. 
Question 13 
Which of the following statement(s) is/are correct regarding BellmanFord shortest path algorithm?

P. Always finds a negative weighted cycle, if one
Q. Finds whether any negative weighted cycle is reachable from the source.
P Only  
Q Only  
Both P and Q  
Neither P nor Q 
More Info: The Dijkstra'a algorithm:
A greedy algorithm
Works when weights are all nonnegative
The bellman ford algorithm: If there is a negative cycle, there is no solution, but negative weight edges are allowed.
– Add this cycle again can always produces a less weight path
If there is no negative cycle, a shortest path has at most V1 edges
A dynamic programming algorithm
Note: Dijkastra is faster than BellmanFord
Question 14 
Let π_{A} be a problem that belongs to the class NP. Then which one of the following is TRUE?
There is no polynomial time algorithm for π_{A}.  
If π_{A} can be solved deterministically in polynomial time,then P = NP.  
If π_{A} is NPhard, then it is NPcomplete.  
π_{A} may be undecidable. 
Question 15 
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
The set of all strings containing the substring 00.
 
The set of all strings containing at most two 0’s.  
The set of all strings containing at least two 0’s.  
The set of all strings that begin and end with either 0 or 1. 