CS GATE 2011 (Test 2)



Tag: cs gate 2011
Q.1
Which of the following options is the closest in the meaning to the word below: Inexplicable
A. Incomprehensible
B. Indelible
C. Inextricable
D. Infallible
Answer : Option A
Explaination / Solution:

Inexplicable means not explicable; that cannot be explained, understood, or accounted for. So the best synonym here is incomprehensible.

Workspace
Report
Topic: Arithmetic Tag: CS GATE 2011
Q.2
A transporter receives the same number of orders each day. Currently, he has some pending orders (backlog) to be shipped. If he uses 7 trucks, then at the end of the 4th day he can clear all the orders. Alternatively, if he uses only 3 trucks, then all the orders are cleared at the end of the 10th day. What is the minimum number of trucks required so that there will be no pending order at the end of the 5th day?
A. 4
B. 5
C. 6
D. 7
Answer : Option C
Explaination / Solution:

 Let each truck carry 100 units.
2800 = 4n + e         n = normal
3000 = 10n + e       e = excess/pending 

Minimum possible = 6 


Workspace
Report
Topic: Databases Tag: CS GATE 2011
Q.3
Consider a relational table r with sufficient number of records, having attributes A1, A2,…, An and let 1 ≤ p ≤ n. Two queries Q1 and Q2 are given below.

The database can be configured to do ordered indexing on Ap or hashing on Ap
Which of the following statements is TRUE? 
A. Ordered indexing will always outperform hashing for both queries
B. Hashing will always outperform ordered indexing for both queries
C. Hashing will outperform ordered indexing on Q1, but not on Q2
D. Hashing will outperform ordered indexing on Q2, but not on Q1.
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Q.4
Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the following is TRUE?
A. tt2
B. tt2
C. tt2
D.  Nothing can be said about the relation between tand t2
Answer : Option C
Explaination / Solution:

Process switching also involves mode changing.

Workspace
Report
Q.5
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
A. Finite state automata
B. Deterministic pushdown automata
C. Non-Deterministic pushdown automata
D. Turing machine
Answer : Option A
Explaination / Solution:

Lexical Analysis is implemented by finite automata

Workspace
Report
Q.6
A deterministic finite automation (DFA)D with alphabet ∑ = {a,b} is given below

Which of the following finite state machines is a valid minimal DFA which accepts the same language as D? 
A.
B.
C.
D.
Answer : Option A
Explaination / Solution:

Options B and C will accept the string b Option – D will accept the string “bba” Both are invalid strings. So the minimized DFA is option A

Workspace
Report
Topic: Algorithms Tag: CS GATE 2011
Q.7
Consider the following recursive C function that takes two arguments 
unsigned int foo unsigned int n, unsigned int r {
if (n > 0) return (n%r) + foo (n / r, r ));
else return 0;
}
What is the return value of the function foo when it is called as foo (345, 10) ?
A. 345
B. 12
C. 5
D. 3
Answer : Option B
Explaination / Solution:



Workspace
Report
Q.8
Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of the operator ↑ . Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?
A.
B.
C.
D.
Answer : Option B
Explaination / Solution:

7 ↓ 3 ↑ 4 ↑ 3 ↓ 2 7 ↓ 3 ↑ (4 ↑ 3) ↓ 2 as ↑ is right associative 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2 (7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative

Workspace
Report
Q.9
Consider a network with five nodes, N1 to N5, as shown below

The net work uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as following
N1 : (0, 1, 7, 8, 4) 
N2 : (1, 0, 6, 7, 3) 
N3 : (7, 6, 0, 2, 6) 
N4 : (8, 7, 2, 0, 4) 
N5 : (4, 3, 6, 4, 0)
Each distance vector is the distance of the best known path at that instance to nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors
The cost of link N2-N3 reduces to 2 in (both directions). After the next round of updates, what will be the new distance vector at node, N3? 
A. (3. 2, 0, 2, 5)
B. (3, 2, 0, 2, 6)
C. (7, 2, 0, 2, 5)
D. (7, 2, 0, 2, 6)
Answer : Option A
Explaination / Solution:



Workspace
Report
Q.10
Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline registers are as given in the figure.

What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation? 
A. 4.0
B. 2.5
C. 1.1
D. 3.0
Answer : Option B
Explaination / Solution:

(5 + 6 + 11 + 8) / (11 + 1) = 30 / 12 = 2.5

Workspace
Report