Q.1 � Q.30 Carry One Mark Each

1. In a population of N families, SOS/c of the families have three children, 3O/c of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children?

(A)23

(B)25

(C)24

(D)10

2. In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 students have taken Computer Organization course; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Data Structures and Computer Organization; 30 students have taken both Data Structures and Computer Organizational, 15 students have taken all the three course. How many students have not taken any of the three courses?

(A) 15

(B) 20

(C) 25

(D)35

3. Let a(x,y),b(x,y) and c(x,y) be three statements with variables x and y chosen from some universe. Consider the following statement: (x)(vy)[(a(x,y) A b(x,y)c,y) Which one of the following is its equivalent?

(A) (vx) (ny) [(a (x, y) v b (x, y)) - c (x, )1

(B) (x)(vy)[(a(x,y) vb(x,y))A-1c(x,y)

(C) (vx)(y)[(a(x,y) Ab(x,y)) c(x,y)

(D) (Vx) (ny) [(a (x, y) v b (x, y)) - c (x, )1

4. Let R1 be a relation from A ={1,3,5,7} to B = {2,4,6,8} and R2 be another relation from B to C ={1,2,3,4}as defined below:

(i) An element x in A is related to an element y in B (under R1) if x+y is divisible by 3.

(A) R1R2 ={(1,2),(1,4),(3,3),(5,4),(7,3)

(B) R1R2 ={(1,2),(1,3),(3,2),(5,2),(7,3))

(C) R1R2 = {(1,2),(3,2),(3,4),(s,4),(7,2))

(D) R1R2 ={(3,2),(3,4),(5,i),(5,3),(7,i))

5. What is the maximum number of edges in an acyclic undirected graph with n vertices?

(A) n-i

(B) n

(C) n + 1

(D)2n - 1

6. What values of x, y and z satisfy the following system of linear equations?

(A) x=6,y=3,z=2

(B) x=i2,y=3,z=�4

(C) x=6,y=6,z=�4

(D) x=12,y=�3,z=O

7. Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c) *?

(A) (a*+b*+c*)*

(B) (a*b*c*)*

(C) ((ab) * +c *) *

8. What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?

(A) 3

(B) 4

(C) 5

(D) 6

9. Which one of the following statements is FALSE?

(A) There exist context free languages such that all the context free grammars generating them age ambiguous.

(B) An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it.

(C) Both deterministic and non-deterministic pushdown automata always accept the same set of languages

(D) A finite set of string from one alphabet is always a regular language.

10. What is the minimum size of ROM required to store the complete truth table of an 8-bit x 8-bit multiplier?

(A) 32 K x i6 bits

(B) 64 K x i6 bits

(C) i6 K x 32 bits

(D)64 K x 32 bits

11. What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and horizontal sweep time of lOOps (including 20 ps of retrace time)?

(A) 8 Mbps

(B) 6.4 Mbps

(C) 0.8 Mbps

(D)0.64 Mbps

12. Consider a system with 2 level caches. Access times of Level 1 cache, Level 2 cache and main memory are 1 ns, iOns, and 500 ns, respectively. The hit rates of Level 1 and Level 2 caches are 0.8 and 0.9, respectively. What is the average access time of the system ignoring the search time within the cache?

(A) 13.0 ns

(B) 12.8 ns

(C) 12.6 ns

(D) 12.4 ns

13. Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

(A) 0(n)

(B) o(log2 n)

(C) O(logn)

(D)0(1)

14. Which one of the following is NOT shared by the threads of the same process?

(A) Stack

(B) Address Space

(C) File Descriptor Table

(D) Message Queue

15. Let x be an integer which can take a value of 0 or 1. The statement if(x = 0) x = 1; else x = 0; is equivalent to which one of the following?

(A) x=1+x;

(B) x=1�x;

(C) x=x�1;

(D)x=1%x;