# CS GATE 2012 (Test 1)

Tag: cs gate 2012
Q.1
Which one of the following options is the closest in meaning to the word given below? Mitigate
A. Diminish
B. Divulge
C. Dedicate
D. Denote
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
Wanted Temporary, Part-time persons for the post of Field Interviewer to conduct personal interviews to collect and collate economic data. Requirements: High School-pass, must be available for Day, Evening and Saturday work. Transportation paid, expenses reimbursed. Which one of the following is the best inference from the above advertisement?
A. Gender-discriminatory
B. Xenophobic
C. Not designed to make the post attractive
D. Not gender-discriminatory
Explaination / Solution:

Workspace
Report
Q.3
The protocol data unit (PDU) for the application layer in the Internet stack is
A. Segment
B. Datagram
C. Message
D. Frame
Explaination / Solution:

The PDU for Datalink layer, Network layer , Transport layer and Application layer are frame, datagram, segment and message respectively.

Workspace
Report
Topic: Databases Tag: CS GATE 2012
Q.4
Which of the following is TRUE?
A. Every relation is 3NF is also in BCNF
B. A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on every key of R
C. Every relation in BCNF is also in 3NF
D. No relation can be in both BCNF and 3NF
Explaination / Solution:

Option A is false since BCNF is stricter than 3NF (it needs LHS of all FDs should be candidate key for 3NF condition) Option B is false since the definition given here is of 2NF Option C is true, since for a relation to be in BCNF it needs to be in 3NF, every relation in BCNF satisfies all the properties of 3NF. Option D is false, since if a relation is in BCNF it will always be in 3NF.

Workspace
Report
Q.5
The amount of ROM needed to implement a 4 bit multiplier is
A. 64 bits
B. 128 bits
C. 1 kbits
D. 2 kbits
Explaination / Solution:

For a 4 bit multiplier there are 24 × 24 = 28 = 256 combinations.
Output will contain 8 bits.
So the amount of ROM needed is 28 ×8 bits = 2Kbits

Workspace
Report
Q.6
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is context-free language, then, is also context-free?
3) If L is regular language, then, is also regular?
4) If L is recursive language, then, is also recursive?
A. 1,2,3,4
B. 1,2
C. 2,3,4
D. 3,4
Explaination / Solution:

CFL’s are not closed under complementation. Regular and recursive languages are closed under complementation.

Workspace
Report
Q.7
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, \$ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S The appropriate entries for E1, E2, and E3 are
A. E1: S →aAbB, A →S
E2: S →bAaB, B → S
E3: B →S
B. E1: S →aAbB, S → ε
E2: S →bAaB, S → ε
E3: S → ε
C. E1: S →aAbB, S → ε
E2: S →bAaB, S → ε
E3: B →S
D. E1: A →S, S→ ε
E2: B →S, S → ε
E3: B →S
Explaination / Solution: Workspace
Report
Topic: Algorithms Tag: CS GATE 2012
Q.8
Consider the following C code segment:
int a, b, c = 0;
void prtFun(void);
main( )
{ static int a = 1;            /* Line 1 */
prtFun( );
a + = 1;
prtFun( )
printf(“\n %d %d “, a, b);
}
void prtFun(void)
{ static int a=2;               /* Line 2 */
int b=1;
a+=++b;
printf(“\n %d %d “, a, b);
What output will be generated by the given code segment?
A. 3 1
4 1
4 2
B. 4 2
6 1
6 1
C. 4 2
6 2
2 0
D. 3 1
5 2
5 2
Explaination / Solution: Workspace
Report
Q.9
Consider an instance of TCP’s Additive Increase Multiplicative decrease (AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first transmission is 8 MSS. Assume that a timeout occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.
A. 8MSS
B. 14MSS
C. 7MSS
D. 12MSS
Explaination / Solution: Given, initial threshold = 8
Time = 1, during 1st transmission,Congestion window size = 2 (slow start phase)
Time = 2, congestion window size = 4 (double the no. of acknowledgments)
Time = 3, congestion window size = 8 (Threshold meet)
Time = 4, congestion window size = 9, after threshold (increase by one Additive increase)
Time = 5, transmits 10 MSS, but time out occurs congestion window size = 10
Hence threshold = (Congestion window size)/2 = 10/2 = 5
Time = 6, transmits 2
Time = 7, transmits 4
Time = 8, transmits 5 (threshold is 5)
Time = 9, transmits 6, after threshold (increase by one Additive increase)
Time = 10, transmits 7
∴ During 10th transmission, it transmits 7 segments hence at the end of the tenth transmission the size of congestion window is 7 MSS.

Workspace
Report
Q.10
Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are
A. full: (REAR+1) mod n==FRONT empty: REAR ==FRONT
B. full:(REAR+1)mod n==FRONT empty: (FRONT+1)mod n==REAR
C. full: REAR==FRONT empty: (REAR+1) mod n ==FRONT
D. full:(FRONT+1)mod n==REAR empty: REAR ==FRONT