41.
Let Q denote a queue containing sixteen
numbers and S be an empty stack. Head(Q) returns the element at the head of the
queue Q without removing it from Q. Similarly Top(S) returns the element at the
top of S without removing it from S. Consider the algorithm given below.

The maximum possible number of iterations of
the while loop in the algorithm is.............

Answer: 256

42.
Consider the following context-free grammars:

G1: S→aS|B,
B→b|bB

G2: S→aA|bB,
A→aA|B|Îµ, B→bB|Îµ

Which one of
the following pairs of languages is generated by G1 and G2, respectively?

(A) {a^{m}b^{n}|m
> 0 or n > 0} and {a^{m}b^{n}|m > 0 and n > 0}

(B) { a^{m}b^{n}|m
> 0 and n > 0} and { a^{m}b^{n}|m > 0 or n ≥ 0}

(C) { a^{m}b^{n}|m
≥ 0 or n > 0} and { a^{m}b^{n}|m > 0 and n > 0}

(D) { a^{m}b^{n}|m
≥ 0 and n > 0} and { a^{m}b^{n}|m > 0 or n > 0}

Answer: D

43. Consider
the transition diagram of a PDA given below with input alphabet Î£ = {a, b} and
stack alphabet Î“ = {X, Z}. Z is the initial stack symbol. Let L denote the
language accepted by the PDA.

Which one of
the following is TRUE?

(A) L = {a^{n}b^{n}|n
≥ 0} and is not accepted by any finite automata

(B) L = {a^{n}|n
≥ 0} U {a^{n}b^{n}|n ≥ 0} and is not accepted by any deterministic
PDA

(C) L is not
accepted by any Turing machine that halts on every input

(D) L = {a^{n}|n
≥ 0} U {a^{n}b^{n}|n ≥ 0} and is deterministic context-free

Answer: D

44.
Let X be a recursive language and Y be a
recursively enumerable but not recursive language. Let W and Z be two languages
such that Y’ reduces to W, and Z reduces to X’ (reduction means the standard
many-one reduction). Which one of the following statements is TRUE?

(A) W can be recursively enumerable and Z is
recursive.

(B) W can be recursive and Z is recursively
enumerable.

(C) W is not recursively enumerable and Z is
recursive.

(D) W is not recursively enumerable and Z is
not recursive

Answer: C

45.
The attributes of three arithmetic operators
in some programming language are given below.

The value of the expression 2 - 5 + 1 - 7 * 3
in this language is ..............

Answer: 9

46.
Consider the following Syntax Directed
Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a, b}

S→aA {print 1}

S→a {print 2}

S→Sb {print 3}

Using the
above SDTS, the output printed by a bottom-up parser, for the input **aab**
is:

(A) 1 3 2

(B) 2 2 3

(C) 2 3 1

(D) Syntax Error

Answer: C

47.
Consider a computer system with 40-bit
virtual addressing and page size of sixteen kilobytes. If the computer system
has a one-level page table per process and each page table entry requires 48
bits, then the size of the per-process page table is ................ megabytes.

Answer: 384

48. Consider
a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87,
11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at
cylinder number 63, moving towards larger cylinder numbers on its servicing
pass. The cylinders are numbered from 0 to 199. The total head movement (in
number of cylinders) incurred while servicing these requests is ..............

Answer: 346

49. Consider
a computer system with ten physical page frames. The system is provided with an
access sequence a_{1}, a_{2}, ..., a_{20}, a_{1},
a_{2}, ..., a_{20}), where each ai is a distinct virtual page number.
The difference in the number of page faults between the last-in-first-out page
replacement policy and the optimal page replacement policy is ..............

Answer: 1

50. Consider
the following proposed solution for the critical section problem. There are n
processes: P_{0} ...P_{n−1}. In the code, function pmax returns
an integer not smaller than any of its arguments. For all i, t[i] is
initialized to zero.

Code for Pi:

do {

c[i]=1;
t[ i ]=pmax(t[0],: ::,t[n-1])+1; c[ i ]=0;

for
every j ≠ i in{0,: ::,n-1} {

while
(c[ j ]);

while
(t[ j ] !=0 && t[ j ]<= t[ i ]);

}

Critical
Section;

t[
i ]=0;

Remainder
Section;

} while (true);

Which one of
the following is TRUE about the above solution?

(A) At most one process can be in the
critical section at any time

(B) The bounded wait condition is satisfied

(C) The progress condition is satisfied

(D) It cannot cause a deadlock

Answer: A

51.
Consider the following two phase locking
protocol. Suppose a transaction T accesses (for read or write operations), a
certain set of objects {O_{1},...,O_{k}}. This is done in the
following manner:

Step 1. T
acquires exclusive locks to O_{1}, ... , O_{k} in increasing
order of their addresses. Step 2. The required operations are performed.

Step 3. All
locks are released.

This
protocol will

(A) guarantee serializability and
deadlock-freedom

(B) guarantee neither serializability nor
deadlock-freedom

(C) guarantee serializability but not
deadlock-freedom

(D) guarantee deadlock-freedom but not
serializability

Answer: A

52.
Consider that B wants to send a message m
that is digitally signed to A. Let the pair of private and public keys for A
and B be denoted by K_{x}^{-} and K_{x}^{+ }for
x=A,B, respectively. Let K_{x}(m) represent the operation of encrypting
m with a key K_{x} and H(m) represent the message digest. Which one of
the following indicates the CORRECT way of sending the message m along with the
digital signature to A?

Answer: B

53. An
IP datagram of size 1000 bytes arrives at a router. The router has to forward
this packet on a link whose MTU (maximum transmission unit) is 100 bytes.
Assume that the size of the IP header is 20 bytes.

The number
of fragments that the IP datagram will be divided into for transmission is
.....................

Answer: 13

54. For
a host machine that uses the token bucket algorithm for congestion control, the
token bucket has a capacity of 1 megabyte and the maximum output rate is 20
megabytes per second. Tokens arrive at a rate to sustain output at a rate of 10
megabytes per second. The token bucket is currently full and the machine needs
to send 12 megabytes of data. The minimum time required to transmit the data is
................. seconds.

Answer: 1.1

55. A
sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames.
Frames are of size 1000 bytes and the transmission rate at the sender is 80
Kbps (1Kbps = 1000 bits/second). Size of an acknowledgement is 100 bytes and
the transmission rate at the receiver is 8 Kbps. The one-way propagation delay
is 100 milliseconds.

Assuming no
frame is lost, the sender throughput is ................ bytes/second.

Answer: 2500