GATE 2005-IT

 Question 1

A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded and it is put back in the bag. This process is repeated 3 times. The probability that no two of the marbles drawn have the same colour is

 A 1/36 B 1/6 C 1/4 D 1/3
Engineering-Mathematics       Probability
Question 1 Explanation:
No. of colours = 3(b,g,r)
Total possible combinations = 3! = 6
Probability of blue marble = 10/60[10 + 20 + 30 = 60]
Probability of green marble = 20/60
Probability of red marble = 30/60
The probability that no two of the marbles has same colour = [10/60 * 20/60 * 30/60] = 1/6
 Question 2

If the trapezoidal method is used to evaluate the integral obtained 01x2dx ,then the value obtained

 A is always > (1/3) B is always < (1/3) C is always = (1/3) D may be greater or lesser than (1/3)
Engineering-Mathematics       Calculus
Question 2 Explanation:
Note: Out of syllabus.
 Question 3

The determinant of the matrix given below is

 A -1 B 0 C 1 D 2
Engineering-Mathematics       Linear-Algebra
Question 3 Explanation:

determinant = product of diagonal element [upper triangular matrix]
= -1 * 1 * 1 * 1
= -1
 Question 4

Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language if Lc ∪ Mc is TRUE?

 A It is necessarily regular but not necessarily context-free. B It is necessarily context-free. C It is necessarily non-regular. D None of the above.
Theory-of-Computation       Regular Languages and finite automata
Question 4 Explanation:
Context-free languages not closed under complementation. So, Lc ∪ Mc is neither regular nor context-free. It might be context sensitive language.
 Question 5

Which of the following statements is TRUE about the regular expression 01*0?

 A It represents a finite set of finite strings. B It represents an infinite set of finite strings. C It represents a finite set of infinite strings. D It represents an infinite set of infinite strings.
Theory-of-Computation       Regular languages and finite automata
Question 5 Explanation:
The given expression 01*0 is regular. So this is a finite string. So options C and D are false and * is placed. So this is infinite set.
So, given regular expression represents an infinite set of finite strings.
 Question 6

The language {0n 1n 2n | 1 ≤ n ≤ 106} is

 A regular B context-free but not regular C context-free but its complement is not context-free D not context-free
Theory-of-Computation       Regular languages and finite automata
Question 6 Explanation:
In this the value of n is finite then we can be able to construct a finite state automata for this language.
So, given language is regular.
 Question 7

Which of the following expressions is equivalent to (A⊕B)⊕C

 A B C D None of these
Theory-of-Computation       Logical-Functions-and-Minimization
Question 7 Explanation:
(A⊕B)⊕C
⇒ We know that
A⊕B = A'B + AB'
A⊙B = AB + A'B' ⇒ (A⊕B)'C + (A⊕B)C'
⇒ (A⊙B)C + (A'B + AB')C'
⇒ (AB + A'B')C + (A'B + AB')C'
⇒ ABC + A'B'C + A'BC' + AB'C'
⇒ ABC + (A'B'C + A'B'C) + A'BC' + AB'C'
[We know that A + A = A]
⇒ ABC + A'B'C + A'B'C + A'BC' + AB'C'
⇒ ABC + A'(B'C + BC') + B'(A'C + AC')
⇒ ABC + A'(B⊕C) + B'(A⊕C)
 Question 8

Using Booth’s Algorithm for multiplication, the multiplier -57 will be recoded as

 A 0 -1 0 0 1 0 0 -1 B 1 1 0 0 0 1 1 1 C 0 -1 0 0 1 0 0 0 D 0 1 0 0 -1 0 0 1
Computer-Organization       Booth\'s-Algorithm
Question 8 Explanation:
Consider option A:
 Question 9

A dynamic RAM has a memory cycle time of 64 nsec. It has to be refreshed 100 times per msec and each refresh takes 100 nsec. What percentage of the memory cycle time is used for refreshing?

 A 10 B 6.4 C 1 D 0.64
Computer-Organization       Cache
Question 9 Explanation:
We know that 1ms = 106ns
In 106ns refresh 100 times.
Each refresh takes 100ns.
Memory cycle time = 64ns
Refresh time per 1ms i.e., per 106ns = 100 * 100 = 104ns
Refresh time per 1ns = (104)/(106) ns
Refresh time per cycle = (104*64)/(106) = 64ns
Percentage of the memory cycle time is used for refreshing = (64*100)/64 = 1%
 Question 10

A two-way switch has three terminals a, b and c. In ON position (logic value 1), a is connected to b, and in OFF position, a is connected to c. Two of these two-way switches S1 and S2 are connected to a bulb as shown below.

Which of the following expressions, if true, will always result in the lighting of the bulb ?

 A B C D
Digital-Logic-Design       Circuits-Output
Question 10 Explanation:
The bulb will be on when both the switch S1 and S2 are in same state, either OFF (or) ON:

From this we can clearly know that given is EX-NOR operation i.e.,
(S1⊙S2) = (S1⊕S2)'
 Question 11

How many pulses are needed to change the contents of a 8-bit up counter from 10101100 to 00100111 (rightmost bit is the LSB)?

 A 134 B 133 C 124 D 123
Digital-Logic-Design       Sequential-Circuits
Question 11 Explanation:
The 8 bit counter will be 0-255 to move from 10101100 (172) to 1000111 (39).
→ First counter is move from 172 to 255 = 83 pulses
→ 255 to 0 = 1 pulse
→ 0 to 39 = 39 pulses
Total = 83 + 1 + 39 = 123 pulses
 Question 12

The numbers 1, 2, .... n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be

 A p B p + 1 C n - p D n - p + 1
Algorithms       Tree Traversals
Question 12 Explanation:
Total element = n
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element

Root contains the value is n - p.
 Question 13

A function f defined on stacks of integers satisfies the following properties.

` f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. `

If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

 A 6 B 4 C 3 D 2
Question 13 Explanation:
2, -3, 2, -1, 2
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,-3)) = max(2,0) + (-3) = 2 - 3 = -1
f(push(-1,2)) = max(-1,0) + 2 = 0 + 2 = 2
f(push(2,-1)) = max(2,0)+ (-1) = 2 - 1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
 Question 14

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

 A k B k + 1 C n - k - 1 D n - k
Algorithms       Graph-Traversal
Question 14 Explanation:
In a graph G with n vertices and p component then G has n - p edges(k).
In this question, we are going to applying the depth first search traversal on each component of graph where G is connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
 Question 15

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

```1. Bellman-Ford algorithm       A: O ( m log n)
2. Kruskal’s algorithm          B: O (n3)
3. Floyd-Warshall algorithm     C: O (nm)
4. Topological sorting	        D: O (n + m) ```
 A 1→ C, 2 → A, 3 → B, 4 → D B 1→ B, 2 → D, 3 → C, 4 → A C 1→ C, 2 → D, 3 → A, 4 → B D 1→ B, 2 → A, 3 → C, 4 → D
Algorithms       General
Question 15 Explanation:
Bellman-ford algorithm → O(nm)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
 Question 16

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?

 A 2 B 3 C 4 D 6
Algorithms       Sorting-and-Searching
Question 16 Explanation:
43%10 = 3 [occupy 3]
165%10 = 5 [occupy 5]
62%10 = 2 [occupy 2]
123%10 = 3 [3 already occupied, so occupies 4]
142%10 = 2 [2, 3, 4, 5 are occupied, so it occupies 6]
 Question 17

A student wishes to create symbolic links in a computer system running Unix. Three text files named "file 1", "file 2" and "file 3" exist in her current working directory, and the student has read and write permissions for all three files. Assume that file 1 contains information about her hobbies, file 2 contains information about her friends and file 3 contains information about her courses. The student executes the following sequence of commands from her current working directory

```ln -s file 1 file 2
ln -s file 2 file 3 ```

Which of the following types of information would be lost from her file system?

`(I) Hobbies (II) Friends (III) Courses`
 A (I) and (II) only B (II) and (III) only C (II) only D (I) and (III) only
Operating-Systems       Unix
Question 17 Explanation:
Note: Out of syllabus.
 Question 18

The shell command

` find -name passwd -print `

is executed in /etc directory of a computer system running Unix. Which of the following shell commands will give the same information as the above command when executed in the same directory?

 A ls passwd B cat passwd C grep name passwd D grep print passwd
Operating-Systems       Shell-Command
Question 18 Explanation:
Note: Out of syllabus.
 Question 19

A user level process in Unix traps the signal sent on a Ctrl-C input, and has a signal handling routine that saves appropriate files before terminating the process. When a Ctrl-C input is given to this process, what is the mode in which the signal handling routine executes?

 A kernel mode B superuser mode C privileged mode D user mode
Operating-Systems       Unix
Question 19 Explanation:
Note: Out of syllabus.
 Question 20

The Function Point (FP) calculated for a software project are often used to obtain an estimate of Lines of Code (LOC) required for that project. Which of the following statements is FALSE in this context.

 A The relationship between FP and LOC depends on the programming language used to implement the software. B LOC requirement for an assembly language implementation will be more for a given FP value, than LOC for implementation in COBOL C On an average, one LOC of C++ provides approximately 1.6 times the functionality of a single LOC of FORTRAN D FP and LOC are not related to each other
Software-Engineering       LOC
Question 20 Explanation:
Note: Out of syllabus.
 Question 21

Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below:

If we wish to store information about the rent payment to be made by person (s) occupying different hotel rooms, then this information should appear as an attribute of

 A Person B Hotel Room C Lodging D None of theseThe information should appear as an attribute of lodging, because this is the only common attribute that relating to the hotel room and person. The information should appear as an attribute of lodging, because this is the only common attribute that relating to the hotel room and person.
Database-Management-System       ER-Model
Question 21 Explanation:
The information should appear as an attribute of lodging, because this is the only common attribute that relating to the hotel room and person.
 Question 22

A table has fields Fl, F2, F3, F4, F5 with the following functional dependencies

` F1 → F3,  F2→ F4,  (F1.F2) → F5 `

In terms of Normalization, this table is in

 A 1 NF B 2 NF C 3 NF D None
Database-Management-System       Normalization
Question 22 Explanation:
F1 → F3 ......(i)
F2 → F4 ......(ii)
(F1⋅F2) → F5 .....(iii)
F1F2 is the candidate key.
F1 and F2 are the prime key.
In (i) and (ii) we can observe that the relation from P → NP which is partial dependency. So this is in 1NF.
 Question 23

A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are:

 A 5 B 4 C 3 D 2
Database-Management-System       B+-Trees
Question 23 Explanation:
No. of nodes in a children of a node = no. of keys in parent node + 1
Here, the tree has 4 levels, then 4+1=5 nodes to be present in the newly created process.
 Question 24

Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database by a successful transaction persist

 A Except in case of an Operating System crash B Except in case of a Disk crash C Except in case of a power failure D Always, even if there is a failure of any kind
Question 24 Explanation:
Durability guarantees that once a transition has been committed, it will remain committed even in the case of a system failure.
 Question 25

Consider the three commands : PROMPT, HEAD and RCPT.
Which of the following options indicate a correct association of these commands with protocols where these are used?

 A HTTP, SMTP, FTP B FTP, HTTP, SMTP C HTTP, FTP, SMTP D SMTP, HTTP, FTP
HTML       HTML
Question 25 Explanation:
Note: Out of syllabus.
 Question 26

Traceroute reports a possible route that is taken by packets moving from some host A to some other host B. Which of the following options represents the technique used by traceroute to identify these hosts

 A By progressively querying routers about the next router on the path to B using ICMP packets, starting with the first router B By requiring each router to append the address to the ICMP packet as it is forwarded to B. The list of all routers en-route to B is returned by B in an ICMP reply packet C By ensuring that an ICMP reply packet is returned to A by each router en-route to B, in the ascending order of their hop distance from A D By locally computing the shortest path from A to B
Computer-Networks       Network-Layer
Question 26 Explanation:
Traceroute works by sending packets with gradually increasing TTL value, starting with TTL value of 1. The first router receives the packet, decrements the TTL value and drops the packet because it then has TTL value zero. The router sends an ICMP time exceeded message back to the source. The next set of packets are given a TTL value of 2.
So the first router forwards the packets, but the second router drops them and replies with ICMP time exceeded. Proceeding in this way, traceroute uses the returned ICMP time exceeded messages to build a list of routers that packets traverse, until the destination is reached and returns an ICMP echo reply message.
 Question 27

Which of the following statements is TRUE about CSMA/CD

 A IEEE 802.11 wireless LAN runs CSMA/CD protocol B Ethernet is not based on CSMA/CD protocol C CSMA/CD is not suitable for a high propagation delay network like satellite network D There is no contention in a CSMA/CD network
Computer-Networks       CSMA/CD
Question 27 Explanation:
For CSMA/CD requires that sender is to be transmitting atleast till the first bit reaches the receiver. So the collision will be eliminated in case if it is present.
For networks with high propagation delay this time becomes too long hence the minimum packet size required becomes too big to be feasible.
 Question 28

Which of the following statements is FALSE regarding a bridge?

 A Bridge is a layer 2 device B Bridge reduces collision domain C Bridge is used to connect two or more LAN segments D Bridge reduces broadcast domain
Computer-Networks       Network-Layer
Question 28 Explanation:
Bridge devices works at the data link layer of the open system interconnected (OSI) model, connecting two different networks together and providing communication between them. So, option A, C are true.
The bridge acts as a interface between two networks and speed the traffic between them and there by reduces the collision domain.
So, option B also True.
 Question 29

Count to infinity is a problem associated with

 A link state routing protocol. B distance vector routing protocol. C DNS while resolving host name. D TCP for congestion control.
Computer-Networks       Network-Layer
Question 29 Explanation:
Distance vector routing protocol uses the Bellman-Ford algorithm and Ford-Fulkerson algorithm.
The Bellman-Ford algorithm does not prevent routing loops from happening and suffers from the count-to-infinity problem.
 Question 30

A HTML form is to be designed to enable purchase of office stationery. Required items are to be selected (checked). Credit card details are to be entered and then the submit button is to be pressed. Which one of the following options would be appropriate for sending the data to the server. Assume that security is handled in a way that is transparent to the form design.

 A Only GET B Only POST C Either of GET or POST D Neither GET nor POST
HTML       XML
Question 30 Explanation:
Note: Out of syllabus.
 Question 31

Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f(a)) for all a ∈ A. Which of the following statements is always true for all such functions f and g?

 A g is onto ⇒ h is onto B h is onto ⇒ f is onto C h is onto ⇒ g is onto D h is onto ⇒ f and g are onto
Engineering-Mathematics       Set-Theory
Question 31 Explanation:
g(f(a)) is a composition function which is A→B→C.
If h: A→C is a onto function, the composition must be onto, but the first function in the composition need to be onto.
So, B→C is must be onto.
 Question 32

Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S1 and S2 in C, either S⊂ S2 or S⊂ S1. What is the maximum cardinality of C?

 A n B n + 1 C 2(n-1) + 1 D n!
Engineering-Mathematics       Set-Theory
Question 32 Explanation:
Consider an example:
Let A = {a, b, c}, here n = 3
Now, P(A) = {Ø, {a}, {b}, {c}, {a,b}, {b,c}, {{a}, {a,b,c}}
Now C will be contain Ø (empty set) and {a,b,c} (set itself) as Ø is the subset of every set. And every other subset is the subset of {a,b,c}.
Now taking the subset of cardinality, we an take any 1 of {a}, {b}, {c} as none of the set is subset of other.
Let's take {2}
→ Now taking the sets of cardinality 2 -{a,b}, {b,c}
→ {b} ⊂ {a,b} and {b,c} but we can't take both as none of the 2 is subset of the other.
→ So let's take {c,a}.
So, C = {Ø, {b}, {b,c}, {a,b,c}}
→ So, if we observe carefully, we can see that we can select only 1 set from the subsets of each cardinality 1 to n
i.e., total n subsets + Ø = n + 1 subsets of A can be there in C.
→ So, even though we can have different combinations of subsets in C but maximum cardinality of C will be n+1 only.
 Question 33

An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is

 A 3 B 4 C 5 D 6
Engineering-Mathematics       Probability
Question 33 Explanation:
Generally which uses a recursion strategy to solve this problem. Other than using recursion we can solve using a formula which we know
The expected number of coin flips for getting n consecutive heads is(2^(n+1) -2)
The expected number of coin flips for getting n consecutive heads is(2^(n+1) -2)
The expected number of coin flips for getting n consecutive same tosses is (2^(n+1) -2) / 2.
where n = 2,
which is (2^(3+1) - 2) / 2 = 3
 Question 34

Let n = p2q, where p and q are distinct prime numbers. How many numbers m satisfy 1 ≤ m ≤ n and gcd (m, n) = 1? Note that gcd (m, n) is the greatest common divisor of m and n.

 A p(p - 1) B pq C (p2 - 1)(q - 1) D p(p - 1)(q - 1)
Engineering-Mathematics       Set-Theory
Question 34 Explanation:
n = p2q, [p, q are prime numbers]
→ No. of multiples of p in n = pq [n = p⋅p⋅q]
→ No. of multiples of q in n = p2 [n = p2q]
→ Prime factorization of n contains only p & q.
→ gcd(m,n) is to be multiple of p and (or) 1.
→ So, no. of possible m such that gcd(m,n) is 1 will be
n - number of multiples of either p (or) q
= n - p2 - pq + p
= p2q - p2 - pq + p
= p(pq - p - q + 1)
= p(p - 1)(q - 1)
 Question 35

What is the value of

 A -1 B 1 C 0 D π
Engineering-Mathematics       Calculus
Question 35 Explanation:

In the limits are be -π to π, one is odd and another is even product of even and odd is odd function and integrating function from the same negative value to positive value gives 0.
 Question 36

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE?

 A ((∀x(P(x)∨Q(x)))) ⟹ ((∀xP(x))∨(∀xQ(x))) B (∀x(P(x) ⟹ Q(x))) ⟹ ((∀xP(x)) ⟹ (∀xQ(x))) C (∀x(P(x)) ⟹ ∀x(Q(x))) ⟹ (∀x(P(x) ⟹ Q(x))) D (∀x(P(x)) ⇔ (∀x(Q(x)))) ⟹ (∀x(P(x) ⇔ Q(x)))
Engineering-Mathematics       Prepositional-Logic
Question 36 Explanation:
LHS: (P(x) ⟹Q(x)) which is True for every value thus ∀x(P(x) ⟹ Q(x)) becomes True.
RHS: (∀xP(x)) and (∀xQ(x)) both becomes False for assumed values which implies F→F and result will be True.
∴ LHS = RHS
 Question 37

Consider the non-deterministic finite automaton (NFA) shown in the figure.

State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be L1. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about L1 and L2 is TRUE? Correction in Question: There is an edge from Z->Y labeled 0 and another edge from Y->Z labeled 1 - in place of double arrowed and no arrowed edges.

 A L1 = L2 B L1 ⊂ L2 C L2 ⊂ L1 D None of the above
Theory-of-Computation       Regular Languages and Finite Automata
Question 37 Explanation:
Based on Arden's theorem write the Y and Z in terms of incoming arrows,
Y = X0 + Y0 + Z1
Z = X0 + Y0 + Z;
⇒ X = Z;
⇒ L1 = L2
 Question 38

Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be Σ. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack.
Which of the following statements is TRUE?

 A L(P) is necessarily Σ* but N(P) is not necessarily Σ* B N(P) is necessarily Σ* but L(P) is not necessarily Σ* C Both L(P) and N(P) are necessarily Σ* D Neither L(P) nor N(P) are necessarily Σ*
Theory-of-Computation       Push-Down-Automata
Question 38 Explanation:
Since, it is NPDA, so we might not have any transitions over any alphabet. So option (D) is correct.
 Question 39

Consider the regular grammar:
S → Xa | Ya
X → Za Z → Sa | ϵ
Y → Wa W → Sa
where S is the starting symbol, the set of terminals is {a} and the set of non-terminals is {S, W, X, Y, Z}. We wish to construct a deterministic finite automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA?

 A 2 B 3 C 4 D 5
Theory-of-Computation       DFA
Question 39 Explanation:
L = {aa, aaa, aaaaa, ...}
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
 Question 40

A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?

 A L is necessarily a regular language B L is necessarily a context-free language, but not necessarily a regular language C L is necessarily a non-regular language D None of the above
Theory-of-Computation       Pumping-lemma
Question 40 Explanation:
As we know that pumping lemma is a negative test, which can be use to disprove the given language is not regular. But reverse is not True.
 Question 41

Given below is a program which when executed spawns two concurrent processes:

```semaphore X := 0 ;
/* Process now forks into concurrent processes P1 & P2 */
P1: repeat forever               P2: repeat forever
V(X);                            P(X);
Compute;                         Compute;
P(X);	                     V(X); ```

Consider the following statements about processes P1 and P2:
I. It is possible for process P1 to starve.
II. It is possible for process P2 to starve.
Which of the following holds?

 A Both 1 and 2 are true B 1 is true but 2 is false C 2 is true but 1 is false D Both 1 and 2 are false
Pumping-lemma       Semaphores
Question 41 Explanation:
P1 can be starves on P, then P2 loops forever.
P2 can be starves on P, then P1 loops forever.
Both statements (i) and (ii) are True.
 Question 42

Two concurrent processes P1 and P2 use four shared resources R1, R2, R3 and R4, as shown below.

```P1:	              P2:
Compute:              Compute;
Use R1;               Use R1;
Use R2;               Use R2;
Use R3;               Use R3;
Use R4;	              Use R4; ```

Both processes are started at the same time, and each resource can be accessed by only one process at a time The following scheduling constraints exist between the access of resources by the processes:
P2 must complete use of R1 before P1 gets access to R1.
P1 must complete use of R2 before P2 gets access to R2.
P2 must complete use of R3 before P1 gets access to R3.
P1 must complete use of R4 before P2 gets access to R4.
There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?

 A 1 B 2 C 3 D 4
Operating-Systems       Process-Management
Question 42 Explanation:
It needs two semaphores such as X=0; Y=0
 Question 43

Which of the following input sequences will always generate a 1 at the output Z at the end of the third cycle?

 A 000 101 111 B 101 110 111 C 011 101 111 D 001 110 111 E None of these
Operating-Systems       Sequential-Circuits
Question 43 Explanation:

While filling done in reverse order, all operations are not satisfied.
 Question 44

We have two designs D1 and D2 for a synchronous pipeline processor. D1 has 5 pipeline stages with execution times of 3 nsec, 2 nsec, 4 nsec, 2 nsec and 3 nsec while the design D2 has 8 pipeline stages each with 2 nsec execution time How much time can be saved using design D2 over design D1 for executing 100 instructions?

 A 214 nsec B 202 nsec C 86 nsec D -200 nsec
Question 44 Explanation:
k = total no. of stages
n = no. of instructions
Total execution time = (k+n-1) * maximum clock cycle
In case of D1:
k = 5
n = 100
Maximum clock cycle = 4 ns
Total execution time = (5+100-1) * 4 = 416
In case of D2:
k = 8
n = 100
Maximum clock cycle = 2 ns
Total execution time = (8+100-1) * 2 = 214
Starved time D2 over D1 = 416 - 214 = 202
 Question 45

A hardwired CPU uses 10 control signals S1 to S10, in various time steps T1 to T5, to implement 4 instructions I1 to I4 as shown below:

Which of the following pairs of expressions represent the circuit for generating control signals S5 and S10 respectively? ((Ij+Ik)Tn indicates that the control signal should be generated in time step Tn if the instruction being executed is Ij or lk)

 A S5=T1+I2⋅T3 and S10=(I1+I3)⋅T4+(I2+I4)⋅T5 B S5=T1+(I2+I4)⋅T3 and S10=(I1+I3)⋅T4+(I2+I4)⋅T5 C S5=T1+(I2+I4)⋅T3 and S10=(I2+I3+I4)⋅T2+(I1+I3)⋅T4+(I2+I4)⋅T5 D S5=T1+(I2+I4)⋅T3 and S10=(I2+I3)⋅T2+I4⋅T3+(I1+I3)⋅T4+(I2+I4)⋅T5
Computer-Organization       CPU-Control-Design-an-Interfaces
Question 45 Explanation:
It is an example of Hardwired CU programming used in RISC processors.
→ If we look at the table, we need to find those timestamps which are using these control signals.
→ For example consider S5 = T1 has been used for control signal for all the instructions, or we can say that irrespective of the instruction.
→ Also S5 is used by instructions I2 and I4 for the timestamp T3 so that
S5 = T1 + I2⋅T3 + I4⋅T3 = T1 + (I2+I4)⋅T3
→ Like that
S10 = (I2+I3)⋅T2 + I4⋅T3 +(I1+I3)⋅T4 + (I2⋅I4)⋅T5
 Question 46

A line L in a circuit is said to have a stuck-at-0 fault if the line permanently has a logic value 0. Similarly a line L in a circuit is said to have a stuck-at-1 fault if the line permanently has a logic value 1. A circuit is said to have a multiple stuck-at fault if one or more lines have stuck at faults. The total number of distinct multiple stuck-at faults possible in a circuit with N lines is

 A 3N B 3N - 1 C 2N - 1 D 2
Digital-Logic-Design       Sequential-Circuits
Question 46 Explanation:
This is because the total possible combinations (i.e., a line may either be at fault (in 2 ways i.e., stuck at 0 or 1) or it may not be, so there are only 3 possibilities for a line) is 3N. In only one combination the circuit will have all lines to be correct (i.e., not a fault). Hence, total combinations in which distinct multiple stuck-at-faults possible in a circuit with N lines is 3N - 1.
 Question 47

(34.4)8 × (23.4)8 evaluates to

 A (1053.6)8 B (1053.2)8 C (1024.2)8 D None of these
Digital-Logic-Design       Number-Systems
Question 47 Explanation:
First convert (34.4)8 and (23.4)8 to decimal.
(34.4)8 = 3×81 + 4×80 + 4×8-1
= 24 + 4 + 0.5
= (28.5)10
(23.4)8 = 2×81 + 3×80 + 4×8-1
= 16 + 3 + 0.5
= (19.5)10
Now,
(28.5)10 × (19.5)01 = (555.75)10
Now,
(555.75)10 = ( ? )8
To convert the integer part,

We get, 1053.
To convert the fractional part, keep multiplying by 8 till decimal part becomes 0,

∴ (555.75)10 = (1053.6)8
 Question 48

The circuit shown below implements a 2-input NOR gate using two 2-4 MUX (control signal 1 selects the upper input). What are the values of signals x, y and z?

 A 1, 0, B B 1, 0, A C 0, 1, B D 0, 1, A
Digital-Logic-Design       Sequential-Circuits
Question 48 Explanation:
In MUX1, the equation is
g = Ax + Bz'
In MUX2, the equation is
f = xg + yg'
= x(Az+Bz') + y(Az+Bz')'
Function f should be equal to (A+B)'.
Just try to put the values of option (D), i.e., x=0, y=1, z=A,
f = 0(AA+BA') +1(AA+BA')'
= (A+B)'
∴ Option (D) is correct.
 Question 49

n instruction set of a processor has 125 signals which can be divided into 5 groups of mutually exclusive signals as follows:

```Group 1 : 20 signals, Group 2 : 70 signals,
Group 3 : 2 signals,  Group 4 : 10 signals,
Group 5 : 23 signals. ```

How many bits of the control words can be saved by using vertical microprogramming over horizontal microprogramming?

 A 0 B 103 C 22 D 55
Digital-Logic-Design       CPU-Control-Design-and-Interfaces
Question 49 Explanation:
In horizontal microprogramming we need 1 bit for every control word, therefore total bits in horizontal microprogramming
= 20 + 70 + 2 + 10 + 23
= 125
Now lets consider vertical microprogramming. In vertical microprogramming no. of bits required to activate 1 signal in group of N signals, is ⌈log2 N⌉. And in the question 5 groups contains mutually exclusive signals,
group 1 = ⌈log2 20⌉ = 5
group 2 = ⌈log2 70⌉ = 7
group 3 = ⌈log2 2⌉ = 1
group 4 = ⌈log2 10⌉ = 4
group 5 = ⌈log2 23⌉ = 5
Total bits required in vertical microprogramming
= 5 + 7 + 1 + 4 + 5
= 22
So, number of bits saved is
= 125 - 22
= 103
 Question 50

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:

 A 2h-1 B 2h-1 + 1 C 2h - 1 D 2h
Algorithms       Tree Traversals
Question 50 Explanation:
Let's take an example,

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
 Question 51

Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2 and T(1) = 1 Which of the following statements is TRUE?

 A T(n) = θ(log n) B T(n) = θ(√n) C T(n) = θ(n) D T(n) = θ(n log n)
Algorithms       Recursion
Question 51 Explanation:
Apply Master's theorem.
 Question 52

Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?

 A There exists a cutset in G having all edges of maximum weight B There exists a cycle in G having all edges of maximum weight C Edge e cannot be contained in a cycle D All edges in G have the same weight
Algorithms       Graph-Theory
Question 52 Explanation:
(A) True, because if there is heaviest edge in MST, then there exist a cut with all edges with weight equal to heaviest edge.

(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.
 Question 53

The following C function takes two ASCII strings and determines whether one is an anagram of the other. An anagram of a string s is a string obtained by permuting the letters in s.

```int anagram (char *a, char *b) {
int count [128], j;
for (j = 0;  j < 128; j++) count[j] = 0;
j = 0;
while (a[j] && b[j]) {
A;
B;
}
for (j = 0; j < 128; j++) if (count [j]) return 0;
return 1;
} ```

Choose the correct alternative for statements A and B.

 A A : count [a[j]]++ and B : count[b[j]]– B A : count [a[j]]++ and B : count[b[j]]++ C A : count [a[j++]]++ and B : count[b[j]]– D A : count [a[j]]++and B : count[b[j++]]–
Programming       Programming
Question 53 Explanation:
A: Increments the count by 1 at each index that is equal to the ASCII value of the alphabet, it is pointing at.
B: Decrements the count by 1 at each index that is equal to the ASCII value of the alphabet it is pointing at. Also it increments the loop counter for next iteration.
If one string is permutation of other, there would have been equal increments and decrements at each index of array, and so count should contain zero at each index, that is what the loop checks at last and if any non-zero elements is found, it returns 0 indicating that strings are not anagram to each other.
 Question 54

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

```struct node {
int value;
struct node *next;
);
void rearrange (struct node *list)
{
struct node *p, *q;
int temp;
if (!list || !list -> next)
return;
p = list;
q = list -> next;
while (q)
{
temp = p -> value;
p -> value = q -> value;
q -> value = temp;
p = q -> next;
q = p ? p -> next : 0;
}
} ```
 A 1, 2, 3, 4, 5, 6, 7 B 2, 1, 4, 3, 6, 5, 7 C 1, 3, 2, 5, 4, 7, 6 D 2, 3, 4, 5, 6, 7, 1
Programming       Programming
Question 54 Explanation:
It is nothing but a pairwise swapping of the linked list.
 Question 55

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be

 A 8, 7, 6, 5, 4, 3, 2, 1 B 1, 2, 3, 4, 8, 7, 6, 5 C 2, 1, 4, 3, 6, 7, 8, 5 D 2, 1, 4, 3, 7, 8, 6, 5
Algorithms       Tree Traversals
Question 55 Explanation:
Pre-order is given as
5, 3, 1, 2, 4, 6, 8, 7
In-order is the sorted sequence, i.e.,
1, 2, 3, 4, 5, 6, 7, 8
And we know that with given inorder and preorder, we can draw a unique BST.
So, the BST will be,

Hence, postorder traversasl sequence is,
2, 1, 4, 3, 7, 8, 6, 5
 Question 56

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is

 A 4 B 7 C 23 D 99
Algorithms       Graph-Theory
Question 56 Explanation:
Edge set consists of edges from i to j, using either
j = i +1
(or)
j = 3i
Second option will help us reach from 1 to 100 rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.
So, the edge sequence with minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
 Question 57

What is the output printed by the following program?

```#include
int f(int n, int k)
{
if (n == 0)
return 0;
else if (n % 2)
return f(n/2, 2*k) + k;
else return f(n/2, 2*k) - k;
}
int main ()
{
printf("%d", f(20, 1));
return 0;
}```
 A 5 B 8 C 9 D 20
Programming       Programming
Question 57 Explanation:

 Question 58

Let a be an array containing n integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference is a specified number S > 0.

```i = 0;
j = 1;
while (j < n )
{
if (E) j++;
else if (a[j] - a[i] == S) break;
else i++;
}
if (j < n)
printf("yes")
else
printf ("no"); ```

Choose the correct expression for E.

 A a[j] – a[i] > S B a[j] – a[i] < S C a[i] – a[j] < S D a[i] – a[j] > S
Programming       Programming
Question 58 Explanation:
For some 'i' if we find that difference of (A[j] - A[i] < S) we increment 'j' to make this difference wider so that it becomes equal to S.
If at times difference becomes greater than S we know that it won't reduce further for same 'i' and so we increment the 'i'.
 Question 59

Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let c be a sorted array containing 2n integers obtained by merging the two arrays a and b. Assuming the arrays are indexed starting from 0, consider the following four statements

```1. a[i] ≥ b [i] => c[2i] ≥ a [i]
2. a[i] ≥ b [i] => c[2i] ≥ b [i]
3. a[i] ≥ b [i] => c[2i] ≤ a [i]
4. a[i] ≥ b [i] => c[2i] ≤ b [i] ```
Which of the following is TRUE?

 A only I and II B only I and IV C only II and III D only III and IV
Programming       Sorting
Question 59 Explanation:
a[i] ≥ b[i]
Since both 'a' and 'b' are sorted in the beginning, there are 'i' elements than or equal to a[i] and similarly 'i' elements smaller than or equal to b[i]. So, a[i] ≥ b[i] means there are 2i elements smaller than or equal to a[i] and hence in the merged array, a[i] will come after these 2i elements. So, c[2i] ≤ a[i].
Similarly, a[i] ≥ b[i] says for b that, there are not more than 2i elements smaller than b[i] in the sorted array. So, b[i] ≤ c[2i].
So, option (C) is correct.
 Question 60

We wish to schedule three processes P1, P2 and P3 on a uniprocessor system. The priorities, CPU time requirements and arrival times of the processes are as shown below.

``` Process	 Priority	 CPU time required	 Arrival time (hh:mm:ss)
P1	        10(highest)	      20 sec	              00:00:05
P2	        9	              10 sec	              00:00:03
P3	        8 (lowest)	      15 sec	              00:00:00 ```
We have a choice of preemptive or non-preemptive scheduling. In preemptive scheduling, a late-arriving higher priority process can preempt a currently running process with lower priority. In non-preemptive scheduling, a late-arriving higher priority process must wait for the currently executing process to complete before it can be scheduled on the processor. What are the turnaround times (time from arrival till completion) of P2 using preemptive and non-preemptive scheduling respectively.

 A 30 sec, 30 sec B 30 sec, 10 sec C 42 sec, 42 sec D 30 sec, 42 sec
Operating-Systems       PU-Scheduling
Question 60 Explanation:
For preemptive,

TAT of P2 = Completion time of P2 - Arrival time of P2
= 33 - 3
= 30 sec
For non-preemptive,

TAT of P2 = Completion time of P2 - Arrival time of P2
= 45 - 3
= 42 sec
 Question 61

Consider a 2-way set associative cache memory with 4 sets and total 8 cache blocks (0-7) and a main memory with 128 blocks (0-127). What memory blocks will be present in the cache after the following sequence of memory block references if LRU policy is used for cache block replacement. Assuming that initially the cache did not have any memory block from the current job?

` 0 5 3 9 7 0 16 55 `
 A 0 3 5 7 16 55 B 0 3 5 7 9 16 55 C 0 5 7 9 16 55 D 3 5 7 9 16 55
Operating-Systems       Memory-Management
Question 61 Explanation:
The cache is 2-way associative, so in a set, there can be 2 block present at a time.
So,

Since, each set has only 2 places, 3 will be thrown out as its the least recently used block. So final content of cache will be
0 5 7 9 16 55
 Question 62

Two shared resources R1 and R2 are used by processes P1 and P2. Each process has a certain priority for accessing each resource. Let Tij denote the priority of Pi for accessing Rj. A process Pi can snatch a resource Rh from process Pj if Tik is greater than Tjk. Given the following:

```(I) T11 > T21
(II) T12 > T22
(III) T11 < T21
(IV) T12 < T22 ```
Which of the following conditions ensures that P1 and P2 can never deadlock?

 A (I) and (IV) B (II) and (III) C (I) and (II) D None of the above
Question 62 Explanation:
If all resources are allocated to one process then deadlock will never occur. So, if we allocate both R1 and R2 to process P1 or both R1 and R2 to process P2 then deadlock will never occur. So when one process will complete its execution then both the resources are allocated to the other process. So, either condition (I) and (II) or (III) and (IV) ensures that deadlock will never occur.
 Question 63

In a computer system, four files of size 11050 bytes, 4990 bytes, 5170 bytes and 12640 bytes need to be stored. For storing these files on disk, we can use either 100 byte disk blocks or 200 byte disk blocks (but can’t mix block sizes). For each block used to store a file, 4 bytes of bookkeeping information also needs to be stored on the disk. Thus, the total space used to store a file is the sum of the space taken to store the file and the space taken to store the book keeping information for the blocks allocated for storing the file. A disk block can store either bookkeeping information for a file or data from a file, but not both.

What is the total space required for storing the files using 100 byte disk blocks and 200 byte disk blocks respectively?

 A 35400 and 35800 bytes B 35800 and 35400 bytes C 35600 and 35400 bytes D 35400 and 35600 bytes
Computer-Organization       Secondary-memory-and-DMA
Question 63 Explanation:
For 100 bytes block,
11050 = 111 blocks requiring 111×4 = 444B of bookkeeping into which requires another 5 disk blocks. So, totally 111+5 = 116 disk blocks. Similarly,
4990 = 50 + ⌈(50×4)/100⌉ = 52
5170 = 52 + ⌈(52×4)/100⌉ = 55
12640 = 127 + ⌈(127×4)/100⌉ = 133
∴ Total no. of blocks required
= 52 + 55 + 133 + 116
= 356
So, total space required
= 35600 Bytes
For 200 Bytes block:
56 + ⌈(56×4)/200⌉ = 58
25 + ⌈(25×4)/200⌉ = 26
26 + ⌈(26×4)/200⌉ = 27
64 + ⌈(64×4)/200⌉ = 66
∴ Total space required,
(58+26+27+66) × 200
= 177 × 200
= 35400 Bytes
 Question 64

The availability of a complex software is 90%. Its Mean Time Between Failure (MTBF) is 200 days. Because of the critical nature of the usage, the organization deploying the software further enhanced it to obtain an availability of 95%. In the process, the Mean Time To Repair (MTTR) increased by 5 days.
What is the MTBF of the enhanced software?

 A 205 days B 300 days C 500 days D 700 days
Software-Engineering       Software-Engineering
Question 64 Explanation:
Note: Out of syllabus.
 Question 65

To carry out white box testing of a program, its flow chart representation is obtained as shown in the figure below:

For basis path based testing of this program, its cyclomatic complexity is

 A 5 B 4 C 3 D 2
Algorithms       Cyclomatic-Complexity
Question 65 Explanation:
Note: Out of syllabus.
 Question 66

In a data flow diagram, the segment shown below is identified as having transaction flow characteristics, with p2 identified as the transaction center

A first level architectural design of this segment will result in a set of process modules with an associated invocation sequence. The most appropriate architecture is

 A p1 invokes p2, p2 invokes either p3, or p4, or p5 B p2 invokes p1, and then invokes p3, or p4, or p5 C A new module Tc is defined to control the transaction flow. This module Tc first invokes p1 and then invokes p2, p2 in turn invokes p3, or p4, or p5 D A new module Tc is defined to control the transaction flow. This module Tc invokes p2, p2 invokes p1, and then invokes p3, or p4, or p5
Software-Engineering       SE
Question 66 Explanation:
Note: Out of syllabus.
 Question 67

A company maintains records of sales made by its salespersons and pays them commission based on each individual's total sales made in a year. This data is maintained in a table with following schema:
salesinfo = (salespersonid, totalsales, commission)
In a certain year, due to better business results, the company decides to further reward its salespersons by enhancing the commission paid to them as per the following formula:
If commission < = 50000, enhance it by 2% If 50000 < commission < = 100000, enhance it by 4% If commission > 100000, enhance it by 6%
The IT staff has written three different SQL scripts to calculate enhancement for each slab, each of these scripts is to run as a separate transaction as follows:

``` T1:
Update salesinfo
Set commission = commission * 1.02
Where commission < = 50000;

T2:
Update salesinfo
Set commission = commission * 1.04
Where commission > 50000 and commission is < = 100000;

T3:
Update salesinfo
Set commission = commission * 1.06
Where commission > 100000;  ```
Which of the following options of running these transactions will update the commission of all salespersons correctly

 A Execute T1 followed by T2 followed by T3 B Execute T2, followed by T3; T1 running concurrently throughout C Execute T3 followed by T2; T1 running concurrently throughout D Execute T3 followed by T2 followed by T1
Database-Management-System       SQL
Question 67 Explanation:
T3 followed by T2 followed by T1 will be the correct execution sequence.
In other cases some people will get two times increment, for example,
if we have T1 followed by T2 and if initial commission is 49500, then he is belonging to <50000.
Hence, 49500 * 1.02 = 50490.
Now again he is eligible for second category. So, he will get again increment as,
50490 * 1.04 = 52509.6
So he will get increment two times, but he is eligible for only one slab of commission.
 Question 68

A table 'student' with schema (roll, name, hostel, marks), and another table 'hobby' with schema (roll, hobbyname) contains records as shown below:

```Table: Student
ROLL	    NAME	HOSTEL	MARKS
1798	Manoj Rathod	  7	 95
2154	Soumic Banerjee	  5	 68
2369	Gumma Reddy	  7	 86
2643	Suhas Kulkarni	  5	 78
2872	Kiran Vora	  5	 92
2926	Manoj Kunkalikar  5	 94
2959	Hemant Karkhanis  7	 88
3125	Rajesh Doshi	  5	 82

Table: hobby
ROLL	HOBBYNAME
1798	chess
1798	music
2154	music
2369	swimming
2581	cricket
2643	chess
2643	hockey
2711	volleyball
2872	football
2926	cricket
2959	photography
3125	music
3125	chess ```

The following SQL query is executed on the above tables:

```select hostel
from student natural join hobby
where marks >= 75 and roll between 2000 and 3000; ```

Relations S and H with the same schema as those of these two tables respectively contain the same information as tuples. A new relation S’ is obtained by the following relational algebra operation:

`S’ = ∏hostel ((σs.roll = H.roll(σmarks > 75 and roll > 2000 and roll < 3000 (S)) X (H))  `

The difference between the number of rows output by the SQL statement and the number of tuples in S’ is

 A 6 B 4 C 2 D 0
Database-Management-System       SQL
Question 68 Explanation:
SQL query will return:

Total 7 rows are selected.
Where in relational algebra only distinct values of hostels are selected,i.e., 5, 6, 7 (3 rows).
∴ Answer is 7 - 3 = 4
 Question 69

In an inventory management system implemented at a trading corporation, there are several tables designed to hold all the information. Amongst these, the following two tables hold information on which items are supplied by which suppliers, and which warehouse keeps which items along with the stock-level of these items.
Supply = (supplierid, itemcode)
Inventory = (itemcode, warehouse, stocklevel)
For a specific information required by the management, following SQL query has been written

```Select distinct STMP.supplierid
From Supply as STMP
Where not unique (Select ITMP.supplierid
From Inventory, Supply as ITMP
Where STMP.supplierid = ITMP.supplierid
And ITMP.itemcode = Inventory.itemcode
And Inventory.warehouse = 'Nagpur'); ```
For the warehouse at Nagpur, this query will find all suppliers who

 A do not supply any item B supply exactly one item C supply one or more items D supply two or more items
Database-Management-System       SQL
Question 69 Explanation:
Here (not unique) in nested query ensures that only for those suppliers it return True which supplies more than 1 item in which case supplier id in inner query will be repeated for that supplier. Hence, the answer is (D) which supply two or more items.
 Question 70

In a schema with attributes A, B, C, D and E following set of functional dependencies are given

```A → B
A → C
CD → E
B → D
E → A ```
Which of the following functional dependencies is NOT implied by the above set?

 A CD → AC B BD → CD C BC → CD D AC → BC
Database-Management-System       ER-Model
Question 70 Explanation:
Apply membership test for all the functional dependencies.
Option (B):
BD → CD
BD+ = BD
i.e., BD cannot derive CD and hence is not implied.
 Question 71

A network with CSMA/CD protocol in the MAC layer is running at 1 Gbps over a 1 km cable with no repeaters. The signal speed in the cable is 2 × 108 m/sec. The minimum frame size for this network should be

 A 10000 bits B 10000 bytes C 5000 bits D 5000 bytes
Computer-Networks       CSMA/CD
Question 71 Explanation:
For CSMA/CD protocol we know that minimum frame size required is,
L ≤ 2×Tp×B
L ≤ 2×(d/v)×B
d = 1Km = 1000m
v = 2×103 m/s
B = 109 bps
By solving the above equation we will set the value of L as,
10000 bits.
 Question 72

A channel has a bit rate of 4 kbps and one-way propagation delay of 20 ms. The channel uses stop and wait protocol. The transmission time of the acknowledgement frame is negligible. To get a channel efficiency of at least 50%, the minimum frame size should be

 A 80 bytes B 80 bits C 160 bytes D 160 bits
Question 72 Explanation:
 Question 73

On a TCP connection, current congestion window size is Congestion Window=4 KB. The window size advertised by the receiver is Advertise Window=6 KB. The last byte sent by the sender is LastByteSent=10240 and the last byte acknowledged by the receiver is LastByteAcked=8192. The current window size at the sender is

 A 2048 bytes B 4096 bytes C 6144 bytes D 8192 bytes
Computer-Networks       Transport Layer
Question 73 Explanation:
Corrent sender window
= min (4KB, 6KB)
= 4KB
 Question 74

In a communication network, a packet of length L bits takes link L1 with a probability of p1 or link L2 with a probability of p2. Link L1 and L2 have bit error probability of b1and brespectively. The probability that the packet will be received without error via either L1 or L2 is

 A (1 – b1)L p1 + (1 – b2)Lp2 B [1 – (b1 + b2)L]p1p2 C (1 – b1)L (1 – b2)Lp1p2 D 1 – (b1 Lp1 + b2 Lp2)
Computer-Networks       Network-Layer
Question 74 Explanation:
Probability of choosing link L1 = p1
Probability for no bit error for any single bit = (1 - b1)
Probability of no bit error = (1 - b2)
Packet can go either through link L1 or L2, they are mutually exclusive events.
Probability packet will be received without any error = Probability of L1 being chosen and no errors in any of L bits + Probability of L2 being chosen and no error in any of the L bits
= (1 - b1)L p1 + (1 - b2)L p2
 Question 75

In a TDM medium access control bus LAN, each station is assigned one time slot per cycle for transmission. Assume that the length of each time slot is the time to transmit 100 bits plus the end-to-end propagation delay. Assume a propagation speed of 2 × 108 m/sec. The length of the LAN is 1 km with a bandwidth of 10 Mbps. The maximum number of stations that can be allowed in the LAN so that the throughput of each station can be 2/3 Mbps is

 A 3 B 5 C 10 D 20
Question 75 Explanation:
 Question 76

A company has a class C network address of 204.204.204.0. It wishes to have three subnets, one with 100 hosts and two with 50 hosts each. Which one of the following options represents a feasible set of subnet address/subnet mask pairs?

 A 204.204.204.128/255.255.255.192 204.204.204.0/255.255.255.128 204.204.204.64/255.255.255.128 B 204.204.204.0/255.255.255.192 204.204.204.192/255.255.255.128 204.204.204.64/255.255.255.128 C 204.204.204.128/255.255.255.128 204.204.204.192/255.255.255.192 204.204.204.224/255.255.255.192 D 204.204.204.128/255.255.255.128 204.204.204.64/255.255.255.192 204.204.204.0/255.255.255.192
Computer-Networks       Network-Layer
Question 76 Explanation:
MSB in last 8 bits is in use to get subnet since it is class C IP.
10000000/128 (mask) - subnet id bit (1) (subnet 1)
01000000/192 (mask) - subnet id bit (01) (subnet 2)
0000000/192 (mask) - subnet id bit (00) (subnet 3)
 Question 77

Assume that “host1.mydomain.dom” has an IP address of 145.128.16.8. Which of the following options would be most appropriate as a subsequence of steps in performing the reverse lookup of 145.128.16.8? In the following options “NS” is an abbreviation of “nameserver”.

 A Query a NS for the root domain and then NS for the “dom” domains B Directly query a NS for “dom” and then a NS for “mydomain.dom” domains C Query a NS for in-addr.arpa and then a NS for 128.145.in-addr.arpa domains D Directly query a NS for 145.in-addr.arpa and then a NS for 128.145.in-addr.arpa domains
Computer-Networks       Network-Layer
Question 77 Explanation:
We are performing reverse lookup of IP address to its hostname.
First we need to locate in-addr.apra, then perform reverse lookup of 8.16.128.145.in-addr.arpa which will point to host1.mydomain.com.
 Question 78

Consider the following message M = 1010001101. The cyclic redundancy check (CRC) for this message using the divisor polynomial x5 + x4 + x2 + 1 is:

 A 01110 B 01011 C 10101 D 10110
Question 78 Explanation:
Degree of generator polynomial is 5. Hence, 5 zeroes is appended before division.
M = 1010001101

append 5 zeroes = M = 101000110100000

∴ CRC = 01110
 Question 79

Suppose that two parties A and B wish to setup a common secret key (D-H key) between themselves using the Diffie-Hellman key exchange technique. They agree on 7 as the modulus and 3 as the primitive root. Party A chooses 2 and party B chooses 5 as their respective secrets. Their D-H key is

 A 3 B 4 C 5 D 6
Question 79 Explanation:
For Diffe-Hellaman the secret key is (pab)modn,
where p is the primitive root and n is the modulus and 'a' and 'b' are the secret values selected by parity A & B.
32×5 mod 7 = 310 mod 7 = 4
 Question 80

Given below is an excerpt of an xml specification.

Given below are several possible excerpts from "library.dtd". For which excerpt would the above specification be valid?

 A B C D
HTML       XML
Question 80 Explanation:
Note: Out of syllabus.
 Question 81

A disk has 8 equidistant tracks. The diameters of the innermost and outermost tracks are 1 cm and 8 cm respectively. The innermost track has a storage capacity of 10 MB.
What is the total amount of data that can be stored on the disk if it is used with a drive that rotates it with (i) Constant Linear Velocity (ii) Constant Angular Velocity?

 A (i) 80 MB (ii) 2040 MB B (i) 2040 MB (ii) 80 MB C (i) 80 MB (ii) 360 MB D (i) 80 MB (ii) 360 MB
Operating-Systems       Memory-Management
Question 81 Explanation:
Constant linear velocity:
Diameter of inner track = d = 1 cm
Circumference of inner track
= 2 * 3.14 * d/2
= 3.14 cm
Storage capacity = 10 MB (given)
Circumference of all equidistant tracks
= 2 * 3.14 * (0.5+1+1.5+2+2.5+3+3.5+4)
= 113.14 cm
Here, 3.14 cm holds 10 MB
Therefore, 1 cm holds 3.18 MB.
So, 113.14 cm holds
113.14 * 3.18 = 360 MB
So, total amount of data that can be hold on the disk = 360 MB.
For constant angular velocity:
In case of CAV, the disk rotates at a constant angular speed. Same rotation time is taken by all the tracks.
Total amount of data that can be stored on the disk
= 8 * 10 = 80 MB
 Question 82

A disk has 8 equidistant tracks. The diameters of the innermost and outermost tracks are 1 cm and 8 cm respectively. The innermost track has a storage capacity of 10 MB.
If the disk has 20 sectors per track and is currently at the end of the 5th sector of the inner-most track and the head can move at a speed of 10 meters/sec and it is rotating at constant angular velocity of 6000 RPM, how much time will it take to read 1 MB contiguous data starting from the sector 4 of the outer-most track?

 A 13.5 ms B 10 ms C 9.5 ms D 20 ms
Operating-Systems       Memory-Management
Question 82 Explanation:
Radius of inner track is 0.5cm (where the head is standing) and the radius of outermost track is 4cm.
So, the header has to seek (4 - 0.5) = 3.5cm.
For 10m ------- 1s
1m ------- 1/10 s
100cm ------- 1/(10×100) s
3.5cm ------- 3.5/1000 s = 3.5ms
So, the header will take 3.5ms.
Now, angular velocity is constant and header is now at end of 5th sector. To start from front of 4th sector it must rotate upto 18 sector.
6000 rotation in 60000ms.
1 rotation in 10ms (time to traverse 20 sectors).
So, to traverse 18 sectors, it takes 9ms.
In 10ms, 10MB data is read.
So, 1MB data can be read in 1ms.
∴ Total time = 1+9+3.5 = 13.5ms
 Question 83

A database table T1 has 2000 records and occupies 80 disk blocks. Another table T2 has 400 records and occupies 20 disk blocks. These two tables have to be joined as per a specified join condition that needs to be evaluated for every pair of records from these two tables. The memory buffer space available can hold exactly one block of records for T1 and one block of records for T2 simultaneously at any point in time. No index is available on either table.
If Nested-loop join algorithm is employed to perform the join, with the most appropriate choice of table to be used in outer loop, the number of block accesses required for reading the data are

 A 800000 B 40080 C 32020 D 100
Database-Management-System       File-Structures
Question 83 Explanation:
To minimize block accesses, we have to put that table outside having less records because for each outer record one block accesses inside will be required.
Therefore,
putting 2nd table outside,
for every 400 records {
80 block accesses in first table
}
= 32000 blocks
and also 20 blocks accesses of outer table.
So, answer comes out to be,
32000 + 20 = 32020
 Question 84

A database table T1 has 2000 records and occupies 80 disk blocks. Another table T2 has 400 records and occupies 20 disk blocks. These two tables have to be joined as per a specified join condition that needs to be evaluated for every pair of records from these two tables. The memory buffer space available can hold exactly one block of records for T1 and one block of records for T2 simultaneously at any point in time. No index is available on either table.
If, instead of Nested-loop join, Block nested-loop join is used, again with the most appropriate choice of table in the outer loop, the reduction in number of block accesses required for reading the data will be

 A 0 B 30400 C 38400 D 798400
Database-Management-System       File-Structures
Question 84 Explanation:
In Nested loop join the no. of block access will be,
400×80+20
= 32020 (calculated in previous question)
In block Nested loop join, the no. of block access will be
20×80+20 = 1620
∴ The difference is = 32020 - 1620 = 30400
 Question 85

Consider the context-free grammar

```E → E + E
E → (E * E)
E → id ```
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?

 A id + id + id + id B id + (id* (id * id)) C (id* (id * id)) + id D ((id * id + id) * id)
Theory-of-Computation       Regular languages and finite automata
Question 85 Explanation:
Let's draw more than one possible tree for id + id + id + id.
 Question 86

Consider the context-free grammar
E → E + E
E → (E * E)
E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?

 A 5 B 4 C 3 D 2
Theory-of-Computation       CFG
Question 86 Explanation:
Total 5 parse trees possible (solved in previous question).
 Question 87

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.

```i = 0
do {
j = i + 1;
while ((j < n) && E1)
j++;
if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;

if (flag)
printf("Sink exists");
else
printf ("Sink does not exist"); Choose the correct expressions for E1 and E2 ```
 A E1 : A[i][j] and E2 : i = j; B E1 : !A[i][j] and E2 : i = j + 1; C E1: !A[i][j] and E2 : i = j; D E1 : A[i][j] and E2 : i = j + 1;
Theory-of-Computation       Graphs
Question 87 Explanation:
If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one column and all 0's (except diagonal) in the corresponding row of that vertex. The given algorithm is a smart way of doing this as it finds the sink in O(n) time complexity.
The first part of the code, is finding if there is any vertex which doesn't have any outgoing edge to any vertex coming after it in adjacency matrix. The smart part of the code is E2, which makes rows slip when there is no edge from i to it, making it impossible for them to form a sink. This is done through
E1: A[i][j]
and
E2: i = j
E1 makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If A[i][j] becomes 1, i can no longer be a sink. Similarly, all previous j can also not be a sink. Now, the next potential candidate for sink is j. So, in E2, we must make i = j.
 Question 88

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.

```i = 0
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;

if (flag)
printf("Sink exists");
else
printf("Sink does not exist"); ```
Choose the correct expressions for E3

 A (A[i][j] && !A[j][i]) B (!A[i][j] && A[j][i]) C (!A[i][j] | | A[j][i]) D (A[i][j] | | !A[j][i])
Theory-of-Computation       Graphs
Question 88 Explanation:
First go through the explanation of previous question.
Now, the loop breaks when we found a potential sink-that is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix.
So, if the column in which this vertex comes is all 1's and the row is all 0's (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, E3 is checking this condition. But in the code flag is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present.
So, the condition is E3 must make flag = 0, if the found i is not a sink. So, the condition should be
A[i][j] | | !A[j][i]
So, option (D) is the answer.
 Question 89

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.

 A B C D
Theory-of-Computation       Graphs
Question 89 Explanation:

 Question 90

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

Continuing from the earlier problem, suppose at some time t, when the costs have stabilized, node A goes down. The cost from node F to node A at time (t + 100) is

 A >100 but finite B ∞ C 3 D >3 and ≤100
Theory-of-Computation       Graphs
Question 90 Explanation:
We consider ABDF at t, they are:
The distance between A and the nodes B, D, F respectively are:
t: 1 2 3
t + 1: 3 2 3
t + 2: 3 4 3
t + 3: 5 4 5
t + 4: 5 6 5
t + 5: 7 6 7
t + 6: 7 8 7
t + 7: 9 8 9
t + 8: 9 to 10
and this continues.
So, in every two steps they get incremented by 2.
So,
at t + 99, F is 101
at t + 100, F is 101.
There are 90 questions to complete.