GATE 2013 questions cs and IT

30. The number of elements that can be sorted in Q(logn) time using heap sort is

a) Θ(1)

b) Θ(√ logn)

c) Θ((logn)/(log log n)

d) Θ(log n)

Answer: a

31. Consider the following function

int unknown int n {

int i, j, k 0;

for( i= n / 2; i<= n; i++)

            for ( j=2; j<=n; j= j * 2)

                        k=k +n / 2;

return k ;

}

The return value of the function is

a) Θ(n2)

b) Θ(n2 log n)

c) Θ(n3)

d) Θ(n3log n)

Answer: b

32. Consider the following languages

            L1= { 0p1q0r | p,q,r ≥ 0}

           L2= { 0p1q0r | p,q,r ≥ 0,p≠ r}

Which one of the following statements is FALSE?

a)  L2 is context–free

b) L2∩L2 is context–free

c) Complement of L2 is recursive

d) Complement of L1 is context–free but not regular

Answer: d

33. Consider the DFA given below.

Which of the following are FALSE?

1. Complement of L(A) is context–free

2. L (A) = L ((11* 0 + 0) (0 + 1) * 0 *1*)

3. For the language accepted by A, A is the minimal DFA

4. A accepts all strings over {0, 1} of length at least 2

a) 1 and 3 only

b) 2 and 4 only  

c) 2 and 3 only

d) 3 and 4 only

Answer: d

34. A shared variable x, initialized to zero, is operated on by four concurrent processes

W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e. wait) on a counting semaphore S and invokes the V operation (i.e. signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?

a) –2

b) –1

c) 1

d) 2

Answer: d

35. Consider the following relational schema.

Students(rollno: integer, sname: string)

Courses(courseno: integer, cname: string)

Registration(rollno: integer, courseno; integer, percent: real)

Which of the following queries are equivalent to this query in English?

“Find the distinct names of all students who score more than 90% in the course

numbered 107”

(I) SELECT DISTINCT S.sname

FROM Students as S, Registration as R

WHERE R.rollno=S.rollno AND R.Courseno=107 AND R.percent>90

(II)  Пsname(σcourseno=107Ùpercent> 90 (Registration*Students)

(III) {T | $S Є Students,$R Є Registration (S.rol lno = R.rollno Ù

R.courseno = 107 Ù R.percent > 90 Ù T.sname = S.name)}

(IV) { <SN>}$SR $RP(<SR, SN > Є Students Ù <SR,107, RP > Є Registration Ù RP>90) }

a) I, II, III and IV

b) I, II and III only

c) I, II and IV only

d) II, III and IV only

Answer: a

36. Determine the maximum length of cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km/s

a) 1

b) 2

c) 2.5
d) 5

Answer: b

Next : GATE Exam 2013 Computer science answer key  questions 37-45 
Previous: GATE CS and IT answer Key 2013 questions 23-29