CS GATE 2011 (Test 4)



Tag: cs gate 2011
Q.1
Choose the most appropriate word from the options given below to complete the following sentence. If you are trying to make a strong impression on your audience, you cannot do so by being understated, tentative or_____________.
A. Hyperbolic
B. Restrained
C. Argumentative
D. Indifferent
Answer : Option B
Explaination / Solution:

The tone of the sentence clearly indicates a word that is similar to understated is needed for the blank. Alternatively, the word should be antonym of strong (fail to make strong impression). Therefore, the best choice is restrained which means controlled/reserved/timid.

Workspace
Report
Q.2
Consider different activities related to email. m1: Send an email from a mail client to a mail server m2: Download an email from mailbox server to a mail client m3: Checking email in a web browser Which is the application level protocol used in each activity?
A. m1:HTTP m2:SMTP m3:POP
B. m1:SMTP m2:FTP m3:HTTP
C. m1: SMTP m2: POP m3: HTTP
D. m1: POP m2: SMTP m3:IMAP
Answer : Option C
Explaination / Solution:

Sending an email will be done through user agent and message transfer agent by SMTP, downloading an email from mail box is done through POP, checking email in a web browser is done through HTTP

Workspace
Report
Topic: Databases Tag: CS GATE 2011
Q.3
Consider a database table T containing two columns X and Y each of type integer. After the creation of the table, one record (X= 1, Y=l) is inserted in the table. Let MX and MY denote the respective maximum values of X and Y among all records in the table at any point in time. Using MX and MY, new records are inserted in the table 128 times with X and Y values being MX+1, 2*MY+1 respectively. It may be noted that each time after the insertion, values of MX and MY change. What will be the output of the following SQL query after the steps mentioned above are carried out? SELECT Y FROM T WHERE X=7;
A. 127
B. 255
C. 129
D. 257
Answer : Option A
Explaination / Solution:



Workspace
Report
Q.4
Consider the following table of arrival time and burst time for three processes P0, P1 and P2. 
Process   Arrival time       Burst Time 
  P0             0 ms                 9 ms 
  P1             1 ms                 4ms 
  P2             2 ms                 9ms 
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
A. 5.0 ms
B. 4.33 ms
C. 6.33 ms
D. 7.33 ms
Answer : Option A
Explaination / Solution:


Average waiting time = (4+11)/3 = 5 ms

Workspace
Report
Q.5
Let P be a regular language and Q be a context free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pn qn | n ∈ N}). Then which of the following is ALWAYS regular?
A. P ∩ Q
B. P − Q
C. ∑ * − P
D. ∑ * − Q
Answer : Option C
Explaination / Solution:

Σ* − P is the complement of P so it is always regular, since regular languages are closed under complementation

Workspace
Report
Q.6
Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate P (x) = ¬ (x = 1) ∧ ∀y (∃z (x = y * z) ⇒ (y = x) ∨ (y = 1))
A. P(x) being true means that x is a prime number
B. P(x) being true means that x is a number other than 1
C. P(x) is always true irrespective of the value of x
D. P(x) being true means that x has exactly two factors other than 1 and x
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Q.7
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
A.
B.
C.
D.
Answer : Option B
Explaination / Solution:

Heap is a complete binary tree

Workspace
Report
Q.8
Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression? 

A. 2
B. 9
C. 5
D. 3
Answer : Option D
Explaination / Solution:


Total 3 Registers are required minimum 

Workspace
Report
Q.9
Consider a hypothetical processor with an instruction of type LW R1, 20(R2), which during execution reads a 32-bit word from memory and stores it in a 32-bit register R1. The effective address of the memory location is obtained by the addition of constant 20 and the contents of register R2. Which of the following best reflects the addressing mode implemented by this instruction for the operand in memory?
A. Immediate Addressing
B. Register Addressing
C. Register Indirect Scaled Addressing
D. Base Indexed Addressing
Answer : Option D
Explaination / Solution:

Here 20 will act as base and content of R2 will be index

Workspace
Report
Q.10
On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine, is given to transfer 500 bytes from an I/O device to memory.
Initialize the address register
Initialize the count to 500
LOOP: Load a byte from device
Store in memory at address given by address register
Increment the address register
Decrement the count
If count != 0 go to LOOP
Assume that each statement in this program is equivalent to a machine instruction which takes one clock cycle to execute if it is a non-load/store instruction. The load-store instructions take two clock cycles to execute.
The designer of the system also has an alternate approach of using the DMA controller to implement the same transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer cycle takes two clock cycles to transfer one byte of data from the device to the memory.
What is the approximate speedup when the DMA controller based design is used in place of the interrupt driven program based input-output? 
A. 3.4
B. 4.4
C. 5.1
D. 6.7
Answer : Option A
Explaination / Solution:

No. of clock cycles required by using load-store approach = 2 + 500 × 7 = 3502 and that of by using DMA = 20 + 500 × 2 = 1020 Required speed up = 3502/1020 = 3.4

Workspace
Report