Computer Science and Information Technology - GATE 2007 Paper Solution

Consider the following two statements the function f(x) = |x|:

P. f(x) is continuous for all real values of x
Q. f(x) is differentiable for all real values of x

Which of the following is TRUE?

Let S be a set of n elements. The number of ordered  pairs in the largest and the smallest equivalence relations on S are:

What is the maximum number of different Boolean functions involving n Boolean variables?

Let G be the non-planar graph with the minimum possible number of edges. Then G has

Consider the DAG with = V = {1, 2, 3, 4, 5, 6}, shown below.

Which of the following is NOT a topological ordering?

Which of the following problems is undecidable?

Which of the following is TRUE?

How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?

Consider the following Boolean function of four variables:

$f\left(w,x,y,z\right)=\sum \left(1,3,4,6,9,11,12,14\right)$

The function is

Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:

Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Which of the following sorting algorithms has the lowest worst-case complexity?

Consider the following segment of C-code:

int j, n;
j = 1;
while (j <= n)
j = j*2;

The number of comparisons made in the execution of the loop for any n > 0 is:

Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.

 Group 1 Group 2 P. Gang Scheduling 1. Guaranteed Scheduling Q. Rate Monotonic Scheduling 2. Real-time Scheduling R. Fair Share Scheduling 3. Thread Scheduling

Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?

Which one of the following is a top-down parser?

In Ethernet when Manchester encoding is used, the bit rate is:

Which one of the following uses UDP as the transport protocol?