 Sample Questions, Previous Year Solved Papers, Study Materials For Competitive Examinations Like UGC NET, SET And GATE Computer Science.

Wednesday, 23 November 2016

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.............
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}
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
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
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 ..............

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
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.
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 ..............
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 ..............
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,: ::,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
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
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?
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 .....................