| 1 |
Let G be a simple graph with 20 vertices and
100 edges. The size of the minimum vertex cover of G is 8. Then, the
size of the maximum independent set of G is |
| Options |
| A) 12 |
B) 8 |
| C) Less than 8 |
D) More than 12 |
|
|
|
| Correct Answer |
A |
|
| 2 |
A and B are the only two stations on an
Ethernet. Each has a steady queue of frames to send. Both A and B
attempt to transmit a frame, collide, and A wins the first backoff
race. At the end of this successful transmission by A, both A and B
attempt to transmit and collide. The probability that A wins the
second backoff race is |
| Options |
| A) 0.5 |
B) 0.625
|
| C) 0.75 |
D) 1.0
|
|
|
|
| Correct Answer |
A |
|
| 3 |
Consider the grammar
E ® E + n | E x n | n
For a sentence n + n x n, the handles in the right-sentential
form of the reduction are |
| Options |
| A) n, E + n and E + n x n |
B) n, E + n and E + E x n |
| C) n, n + n and n + n x n |
D) n, E + n and E x n |
|
|
|
| Correct Answer |
D |
|
| 4 |
Consider the grammar with the following
translation rules and E as the start symbol.
E ® E1 # T
{E.value = E1.value * T.value }
| T
{E.value = T.value }
T ® T1 & F {
T.value = T1.value + F.value }
|
F {T.value = F.value}
F ® num
{F.value = num.value }
Compute E. value for the root of the parse tree for the expression:
2 # 3 & 5 # 6 & 4. |
| Options |
| A) 200 |
B) 180 |
| C) 160 |
D) 40 |
|
|
|
| Correct Answer |
C |
|
| 5 |
Let
A be a sequence of 8 distinct integers sorted in ascending order.
How many distinct pairs of sequences, B and C are there such that (i)
each is sorted in ascending order, (ii) B has 5 and C has 3
elements, and (iii) the result of merging B and C gives A?
|
| Options |
|
|
|
| Correct Answer |
D |
|
| 6 |
Which one of the following is true for a CPU
having a single interrupt request line and a single interrrupt grant
line? |
| Options |
| A) Neither vectored interrupt nor multiple
interrupting devices are possible. |
B) Vectored interrupts are not possible but
multiple interrupting devices are possible. |
| C) Vectored interrupts and multiple interrupting
devices are both possible. |
D) Vectored interrupt is possible but multiple
interrupting devices are not possible. |
|
|
|
| Correct Answer |
B |
|
| 7 |
Consider a relation scheme R = (A, B, C, D, E,
H) on which the following functional dependencies hold : (A ®
B, BC ® D, E ®
C, D ® A). What are the
candidate keys of R? |
| Options |
| A) AE, BE |
B) AE, BE, DE |
| C) AEH, BEH, BCH |
D) AEH, BEH, DEH |
|
|
|
| Correct Answer |
D |
|
| 8 |
In a network of LANs connected by bridges, packets are sent from
one LAN to another through intermediate bridges. Since more than one
path may exist between two LANs, packets may have to be routed
through multiple bridges.
Why is the spanning tree algorithm used for bridge-routing?
|
| Options |
| A) For shortest path routing between LANs |
B) For avoiding loops in the routing paths |
| C) For fault tolerance |
D) For minimizing collisions |
|
|
|
| Correct Answer |
B |
|
| 9 |
Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE? |
| Options |
| A) T(n) = O(n2 ) |
B) T(n) = q (n log
n) |
| C) T(n) = W (n2) |
D) T(n) = O(n log n) |
|
|
|
| Correct Answer |
B |
|
| 10 |
Consider the following C program segment
struct CellNode {
struct CellNode *leftChild ;
int element;
struct CellNode *rightChild ;
};
int DoSomething (struct CellNode *ptr)
{
int value = 0 ; if (ptr ! = NULL)
{ if (ptr->leftChild ! = NULL)
value = 1 + DoSomething (ptr - > leftChild) ;
if (ptr - > rightChild ! = NULL)
value = max (value, 1 + DoSomething (ptr - >
rightChild)) ;
}
return (value);
}
The value returned by the function DoSomething when a pointer to
the root of a
non-empty tree is passed as argument is
|
| Options |
A) The number of leaf nodes in the tree
|
B) The number of nodes in the tree |
| C) The number of internal nodes in the tree |
D) The height of the tree
|
|
|
|
| Correct Answer |
D |
Active Topics 
Memberlist 
Calendar 
Search 
Help
Register 
Login
One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers
Topic: CSE GATE sample papers
Topic: CSE GATE sample papers
IP Logged
