GATE Computer Science Solved Session I 2016 - Part 5

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) {ambn|m > 0 or n > 0} and {ambn|m > 0 and n > 0}
(B) { ambn|m > 0 and n > 0} and { ambn|m > 0 or n ≥ 0}
(C) { ambn|m ≥ 0 or n > 0} and { ambn|m > 0 and n > 0}
(D) { ambn|m ≥ 0 and n > 0} and { ambn|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 = {anbn|n ≥ 0} and is not accepted by any finite automata
(B) L = {an|n ≥ 0} U {anbn|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 = {an|n ≥ 0} U {anbn|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 a1, a2, ..., a20, a1, a2, ..., a20), 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: P0 ...Pn−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 {O1,...,Ok}. This is done in the following manner:
Step 1. T acquires exclusive locks to O1, ... , Ok 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 Kx- and Kx+ for x=A,B, respectively. Let Kx(m) represent the operation of encrypting m with a key Kx 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

Pages   2   3   4   5 

Post a Comment