25-08-2017, 09:32 PM
1455271267-www.entranceexam.netGATEComputerScienceSamplePaper1.pdf (Size: 300.04 KB / Downloads: 5)
Q. No. 1 – 25 Carry One Mark Each
1. Let G=(V, E) be a graph. Define ( ) d
d
ξ G id = ∑ × , where id is the number of
vertices of degree d in G. If S and T are two different trees with ξ =ξ ( ) S T( ) ,
then
(A) S 2T = (B) S T1 = − © S T = (D) S T1 = +
2. Newton-Raphson method is used to compute a root of the equation 2 x 13 0 − =
with 3.5 as the initial value. The approximation after one iteration is
(A) 3.575 (B) 3.676 © 3.667 (D) 3.607
3. What is the possible number of reflexive relations on a set of 5 elements?
(A) 210 (B) 215 © 220 (D) 225
4. Consider the set S = {1, ω, ω2
}, where ω and ω2
are cube roots of unity. If *
denotes the multiplication operation, the structure (S, *) forms
(A) A group (B) A ring
© An integral domain (D) A field
5. What is the value of
2n
n
1 lim 1 ?
→∞ n
⎛ ⎞ − ⎜ ⎟ ⎝ ⎠
(A) 0 (B) e-2 © e-1/2 (D) 1
6. The minterm expansion of f (P, Q, R) =++ PQ QR PR is
(A) mm 2467 +++ (B) mm 0135 + + +
© mm 0167 +++ (D) mm 2345 + + +
7. A main memory unit with a capacity of 4 megabytes is built using 1M×1-bit
DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The
time taken for a single refresh operation is 100 nanoseconds. The time required
to perform one refresh operation on all the cells in the memory unit is
(A) 100 nanoseconds (B) 100*210 nanoseconds
© 100*220 nanoseconds (D) 3200*220 nanoseconds
8. P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)16.
The 2’s complement representation of 8*P is
(A) ( )16 C3D8 (B) ( )16 187B © ( )16 F878 (D) ( )16 987B
⏐CS⏐ GATE 2010 www.gateforum.com
© All rights reserved by Gateforum Educational Services Pvt. Ltd. No part of this document may be reproduced or utilized in any form without the
written permission. Discuss GATE 2010 question paper at www.gatementor.com. 2
9. The Boolean expression for the output f of the multiplexer shown below is
(A) PQR ⊕ ⊕
(B) PQR ⊕ ⊕
© PQR + +
(D) PQR + +
10. In a binary tree with n nodes, every node has an odd number of descendants.
Every node is considered to be its own descendant. What is the number of nodes
in the tree that have exactly one child?
(A) 0 (B) 1 © (n 1 /2 − ) (D) n-1
11. What does the following program print?
( )
( )
#include stdio.h
void f int * p, int * g {
p q;
* p 2;
}
int i 0, j 1;
int main ( ){
f(&i, & j);
pr int f "%d %d \ n", i, j ;
return 0;
}
< >
=
=
= =
(A) 2 2 (B) 2 1 © 0 1 (D) 0 2
12. Two alternative packages A and B are available for processing a database having
10k
records. Package A requires 0.0001n2
time units and package B requires
10nlog10n time units to process n records. What is the smallest value of k for
which package B will be preferred over A?
(A) 12 (B) 10 © 6 (D) 5
13. Which data structure in a compiler is used for managing information about
variables and their attributes?
(A) Abstract syntax tree (B) Symbol table
© Semantic stack (D) Parse table