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) Î˜(n

^{2}) (B) Î˜(n^{2}logn)
(C) Î˜(n

^{3}) (D) Î˜(n^{3}logn)
Answer: B

32. Consider the following
languages.

L

_{1}={0^{p}1^{q}0^{r}|*p,q,r*≥0}
L

_{2}={0^{p}1^{q}0^{r}|*p,q,r*≥0,*p*≠*r*}
Which one of the following statements is

**FALSE**?
(A) L

_{2}is context–free
(B) L

_{1}∩L_{2}is context–free
(C) Complement of L

_{2}is recursive
(D) Complement of L

_{1}is context–free but not regular
Answer: D

33. Consider the DFA

*A*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.rollno=R.rollno∧

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

(IV) {<S

_{N}>|∃S_{R}∃R_{P}(<S_{R},S_{N}>ÏµStudents∧<S_{R},107,R_{P}>ÏµRegistration∧R_{P}>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

37. In an IPv4 datagram, the M
bit is 0, the value of HLEN is 10, the value of total length is 400 and the
fragment offset value is 300. The position of the datagram, the sequence numbers
of the first and the last bytes of the payload, respectively are

(A) Last fragment, 2400 and 2789

(B) First fragment, 2400 and 2759

(C) Last fragment, 2400 and 2759

(D) Middle fragment, 300 and 689

Answer: C

38. The following figure
represents access graphs of two modules M1 and M2. The filled circles represent
methods and the unfilled circles represent attributes. If method m is moved to
module M2 keeping the attributes where they are, what can we say about the
average cohesion and coupling between modules in the system of two modules?

(A) There is no change.

(B) Average cohesion goes up but coupling is reduced

(C) Average cohesion goes down and coupling also reduces

(D) Average cohesion and coupling increase

Answer: A

39. A certain computation
generates two arrays a and b such that a[i]=f(i) for 0≤i<n and b[i]=g(a[i])
for 0≤i<n. Suppose this computation is decomposed into two concurrent
processes X and Y such that X computes the array a and Y computes the array b.
The processes employ two binary semaphores R and S, both initialized to zero.
The array a is shared by the two processes. The structures of the processes are
shown below.

Process X; Process
Y;

private i; private
i;

for (i=0; i<n; i++) { for
(i=0; i<n; i++) {

a[i]=f(i); EntryY(R,
S);

ExitX(R, S); b[i]=g(a[i]);

} }

Which one of the following represents the

**CORRECT**implementations of ExitX and EntryY ?
(A) ExitX R, S {

P(R);

V(S);

}

EntryY R, S {

P(S);

V(R);

}

(B) ExitX R, S {

V(R);

V(S);

}

EntryY R, S {

P(R);

P(S);

}

(C) ExitX R, S {

P(S);

V(R);

}

EntryY R, S {

V(S);

P(R);

}

(D) ExitX R, S {

V(R);

P(S);

}

EntryY R, S {

V(S);

P(R);

}

Answer: C

40. Consider the following two
sets of LR(1) items of an LR(1) grammar

X→c.X, c/d X→c.X,
$

X→.cX, c/d X→.cX,
$

X→.d, c/d X→.d,
$

Which of the following statements related to merging of
the two sets in the corresponding

**LALR**parser is/are**FALSE**?
1. Cannot be merged since look aheads are different

2. Can be merged but will result in S–R conflict

3. Can be merged but will result in R–R conflict

4. Cannot be merged since

*goto*on*c*will lead to two different sets
(A) 1 only (B)
2 only

(C) 1 and 4 only (D)
1, 2, 3 and 4

Answer: D

## 0 Comments