# GATE Computer Science Sample Question Paper - I

1 The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?
A) 24
B) 25
C) 26
D) 27

2 The Boolean function x, y, + xy + x, y
A) x, + y,
B) x + y
C) x + y,
D) x, + y

3 In an MxN matrix such that all non-zero entries are covered in a rows and b columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is
A) £ a + b
B) £ max {a, b}
C) £ min {M-a, N-b}
D) £ min {a, b}

4. The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies:
C) name -> rollNo
D) rollNo -> name
The highest normal form of this relation scheme is

5. The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by
A) the instruction set architecture
B) page size
C) physical memory size
D) number of processes in memory

6. 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
A) 12
B) 8
C) Less than 8
D) More than 12

7. What does the following algorithm approximate? (Assume m > 1, Î > 0).
x = m;
y-i;
while (x - y > Î)
{ x = (x + y) / 2 ;
y = m/x ;
}
print (x) ;
A) log m
B) m2
C) m1/2
D) m1/3

8. Consider the following C program
main ()
{ int x, y, m, n ;
scanf ("%d %d", &x, &y);
/ * Assume x > 0 and y > 0 * /
m = x; n = y ;
while ( m ! = n)
{ if (m > n)
m = m — n;
else
n = n - m ; }
printf("%d",n); }
The program computes
A) x + y, using repeated subtraction
B) x mod y using repeated subtraction
C) the greatest common divisor of x and y
D) the least common multiple of x and y

9. The best data structure to check whether an arithmetic expression has balanced parentheses is a
A) queue
B) stack
C) tree
D) list

10. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8,5,3,2 Two new elements 1 and 7 are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is
A) 10,8,7,5,3,2,1
B) 10,8,7,2,3,1,5
C) 10,8,7,1,2,3,5
D) 10,8,7,3,2,1,5

11. An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be
A) 255.255.0.0
B) 255.255.64.0
C) 255.255.128.0
D) 255.255.252.0

12. Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 ms. The minimum frame size is:
A) 94
B) 416
C) 464
D) 512

13. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
A) 2
B) 3
C) 4
D) 6

14. Consider the following C function:
int f (int n)
{ static int i = 1;
if (n >= 5) return n;
n = n + i;
i ++;
return f (n);
}
The value returned by f(1) is

A) 5
B) 6
C) 7
D) 8

15. The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by
A) the instruction set architecture
B) page size
C) physical memory size
D) number of processes in memory

## Replies

You are reading an archived discussion.

## GATE Computer Science Sample Question Paper - II

1 The address resolution protocol (ARP) is used for A) Finding the IP address from the DNS B) Finding the IP address of the default gateway C) Finding the IP...

## GATE Computer Science Sample Question Paper - III

1 The problems 3-SAT and 2-SAT are A) both in P B) both NP-complete C) NP-complete and in P respectively D) undecidable and NP-complete respectively Answer : (C) 2 Consider...

## GATE Computer Science Sample Question Paper - IV

Q-1 Select the one true statement. A) Every binary tree is either complete or full. B) Every complete binary tree is also a full binary tree. C) Every full binary...

## GATE Mechanical Engineering Sample Questions - I

1 In PERT analysis a critical activity has A) maximum Float B) zero Float C) maximum Cost D) minimum Cost Answer : (B) 2 Environment friendly refrigerant R134a is used...

## GATE Mechanical Engineering Sample Questions - II

1 Stokes theorem connects A) a line integral and a surface integral B) a surface integral and a volume integral C) a line integral and a volume integral D) gradient...