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
1/36 | |
1/6 | |
1/4 | |
1/3 |

Question 2 |
is always > (1/3) | |
is always < (1/3) | |
is always = (1/3) | |
may be greater or lesser than (1/3) |
Question 3 |
-1 | |
0 | |
1 | |
2 |

determinant = product of diagonal element [upper triangular matrix]
= -1 * 1 * 1 * 1
= -1
Question 4 |
It is necessarily regular but not necessarily context-free. | |
It is necessarily context-free. | |
It is necessarily non-regular. | |
None of the above. |
Question 5 |
It represents a finite set of finite strings. | |
It represents an infinite set of finite strings. | |
It represents a finite set of infinite strings. | |
It represents an infinite set of infinite strings.
|
So, given regular expression represents an infinite set of finite strings.
Question 6 |
regular | |
context-free but not regular | |
context-free but its complement is not context-free | |
not context-free |
So, given language is regular.
Question 7 |
![]() | |
![]() | |
![]() | |
None of these |

Question 8 |
0 -1 0 0 1 0 0 -1 | |
1 1 0 0 0 1 1 1 | |
0 -1 0 0 1 0 0 0 | |
0 1 0 0 -1 0 0 1 |

Question 9 |
10 | |
6.4 | |
1 | |
.64 |
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 |
![]() | |
![]() | |
![]() | |
![]() |

From this we can clearly know that given is EX-NOR operation i.e.,
(S1⊙S2) = (S1⊕S2)'
Question 11 |
134 | |
133 | |
124 | |
123 |
→ 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 |
p | |
p + 1 | |
n - p | |
n - p + 1 |
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element

Root contains the value is n - p.
Question 13 |
6 | |
4 | |
3 | |
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 |
k | |
k + 1 | |
n - k - 1 | |
n - k |
In this question, we are going to applying the depth first search traversal on each component of graph where G is conected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
Question 15 |
1→ C, 2 → A, 3 → B, 4 → D | |
1→ B, 2 → D, 3 → C, 4 → A | |
1→ C, 2 → D, 3 → A, 4 → B | |
1→ B, 2 → A, 3 → C, 4 → D |
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?
2 | |
3 | |
4 | |
6 |
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 |
(I) and (II) only | |
(II) and (III) only | |
(II) only | |
(I) and (III) only |
Question 18 |
ls passwd | |
cat passwd | |
grep name passwd | |
grep print passwd
|
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?
kernel mode | |
superuser mode | |
privileged mode | |
user mode |
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.
The relationship between FP and LOC depends on the programming language used to implement the software. | |
LOC requirement for an assembly language implementation will be more for a given FP value, than LOC for implementation in COBOL | |
On an average, one LOC of C++ provides approximately 1.6 times the functionality of a single LOC of FORTRAN | |
FP and LOC are not related to each other
|
Question 21 |
Person | |
Hotel Room | |
Lodging | |
None of these |
Question 22 |
1 NF | |
2 NF | |
3 NF | |
None |
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 |
5 | |
4 | |
3 | |
2 |
Here, the tree has 4 levels, then 4+1=5 nodes to be present in the newly created process.
Question 24 |
Except in case of an Operating System crash | |
Except in case of a Disk crash | |
Except in case of a power failure | |
Always, even if there is a failure of any kind |
Question 25 |
HTTP, SMTP, FTP | |
FTP, HTTP, SMTP | |
HTTP, FTP, SMTP | |
SMTP, HTTP, FTP |
Question 26 |
By progressively querying routers about the next router on the path to B using ICMP packets, starting with the first router | |
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 | |
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 | |
By locally computing the shortest path from A to B |
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 |
IEEE 802.11 wireless LAN runs CSMA/CD protocol | |
Ethernet is not based on CSMA/CD protocol | |
CSMA/CD is not suitable for a high propagation delay network like satellite network | |
There is no contention in a CSMA/CD network |
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 |
Bridge is a layer 2 device | |
Bridge reduces collision domain | |
Bridge is used to connect two or more LAN segments | |
Bridge reduces broadcast domain |
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 |
link state routing protocol. | |
distance vector routing protocol. | |
DNS while resolving host name. | |
TCP for congestion control. |
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.
Only GET | |
Only POST | |
Either of GET or POST | |
Neither GET nor POST |
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?
g is onto ⇒ h is onto | |
h is onto ⇒ f is onto | |
h is onto ⇒ g is onto | |
h is onto ⇒ f and g are onto |
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 |
n | |
n + 1 | |
2(n-1) + 1 | |
n! |
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 |
3 | |
4 | |
5 | |
6 |
Question 34 |
p(p - 1) | |
pq | |
(p2 - 1)(q - 1) | |
p(p - 1)(q - 1) |
→ 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 |
-1 | |
1 | |
0 | |
π |

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 |
((∀x(P(x)∨Q(x))))⟹((∀xP(x))∨(∀xQ(x))) | |
(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x))) | |
(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x))) | |
(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))
|
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 |
L1 = L2 | |
L1 ⊂ L2 | |
L2 ⊂ L1 | |
None of the above |
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?
L(P) is necessarily Σ* but N(P) is not necessarily Σ* | |
N(P) is necessarily Σ* but L(P) is not necessarily Σ* | |
Both L(P) and N(P) are necessarily Σ* | |
Neither L(P) nor N(P) are necessarily Σ*
|
Question 39 |
2 | |
3 | |
4 | |
5 |
The minimum string length is 2 [aa], so we require 3 states to construct DFA.
Question 40 |
L is necessarily a regular language | |
L is necessarily a context-free language, but not necessarily a regular language | |
L is necessarily a non-regular language | |
None of the above |
Question 41 |
Both 1 and 2 are true | |
1 is true but 2 is false | |
2 is true but 1 is false | |
Both 1 and 2 are false |
P2 can be starves on P, then P1 loops forever.
Both statements (i) and (ii) are True.
Question 42 |
1 | |
2 | |
3 | |
4 |

Question 43 |

000 101 111 | |
101 110 111 | |
011 101 111 | |
001 110 111 | |
None of these |

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?
214 nsec | |
202 nsec | |
86 nsec | |
-200 nsec |
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 |
S5=T1+I2⋅T3 and S10=(I1+I3)⋅T4+(I2+I4)⋅T5 | |
S5=T1+(I2+I4)⋅T3 and S10=(I1+I3)⋅T4+(I2+I4)⋅T5 | |
S5=T1+(I2+I4)⋅T3 and S10=(I2+I3+I4)⋅T2+(I1+I3)⋅T4+(I2+I4)⋅T5 | |
S5=T1+(I2+I4)⋅T3 and S10=(I2+I3)⋅T2+I4⋅T3+(I1+I3)⋅T4+(I2+I4)⋅T5 |
→ 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
3N | |
3N - 1 | |
2N - 1 | |
2 |
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 |
(1053.6)8 | |
(1053.2)8 | |
(1024.2)8 | |
None of these |
(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 |
1, 0, B | |
1, 0, A | |
0, 1, B | |
0, 1, A |
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 |
0 | |
103 | |
22 | |
55 |
= 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:
2h-1 | |
2h-1 + 1 | |
2h - 1 | |
2h |

Above tree satisfies the property given in the question. Hence, only option (B) satisfies it.
Question 51 |
T(n) = θ(log n) | |
T(n) = θ(√n) | |
T(n) = θ(n) | |
T(n) = θ(n log n) |
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?
There exists a cutset in G having all edges of maximum weight | |
There exists a cycle in G having all edges of maximum weight | |
Edge e cannot be contained in a cycle | |
All edges in G have the same weight
|

(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 |
A : count [a[j]]++ and B : count[b[j]]– | |
A : count [a[j]]++ and B : count[b[j]]++ | |
A : count [a[j++]]++ and B : count[b[j]]– | |
A : count [a[j]]++and B : count[b[j++]]– |
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 |
1, 2, 3, 4, 5, 6, 7 | |
2, 1, 4, 3, 6, 5, 7 | |
1, 3, 2, 5, 4, 7, 6 | |
2, 3, 4, 5, 6, 7, 1 |
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
8, 7, 6, 5, 4, 3, 2, 1 | |
1, 2, 3, 4, 8, 7, 6, 5 | |
2, 1, 4, 3, 6, 7, 8, 5 | |
2, 1, 4, 3, 7, 8, 6, 5 |
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 |
4 | |
7 | |
23 | |
99 |
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 58 |
a[j] – a[i] > S | |
a[j] – a[i] < S | |
a[i] – a[j] < S | |
a[i] – a[j] > 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 |
only I and II | |
only I and IV | |
only II and III | |
only III and IV |
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 |
30 sec, 30 sec | |
30 sec, 10 sec | |
42 sec, 42 sec | |
30 sec, 42 sec
|

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 |
0 3 5 7 16 55 | |
0 3 5 7 9 16 55 | |
0 5 7 9 16 55 | |
3 5 7 9 16 55 |
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
Hence, answer is (C).
Question 62 |
(I) and (IV) | |
(II) and (III) | |
(I) and (II) | |
None of the above |
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?
35400 and 35800 bytes | |
35800 and 35400 bytes | |
35600 and 35400 bytes | |
35400 and 35600 bytes |
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?205 days | |
300 days | |
500 days | |
700 days |
Question 66 |
p1 invokes p2, p2 invokes either p3, or p4, or p5 | |
p2 invokes p1, and then invokes p3, or p4, or p5 | |
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 | |
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 |
Question 67 |
Execute T1 followed by T2 followed by T3 | |
Execute T2, followed by T3; T1 running concurrently throughout | |
Execute T3 followed by T2; T1 running concurrently throughout | |
Execute T3 followed by T2 followed by T1
|
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 |
6 | |
4 | |
2 | |
0 |

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 |
do not supply any item | |
supply exactly one item | |
supply one or more items | |
supply two or more items |
Question 70 |
CD → AC | |
BD → CD | |
BC → CD | |
AC → BC |
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
10000 bits | |
10000 bytes | |
5000 bits | |
5000 bytes |
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
80 bytes | |
80 bits | |
160 bytes | |
160 bits |
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
2048 bytes | |
4096 bytes | |
6144 bytes | |
8192 bytes |
= 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 b2 respectively. The probability that the packet will be received without error via either L1 or L2 is
(1 – b1)L p1 + (1 – b2)Lp2 | |
[1 – (b1 + b2)L]p1p2 | |
(1 – b1)L (1 – b2)Lp1p2 | |
1 – (b1 Lp1 + b2 Lp2) |
Probability for no bit error for any single bit = (1 - b1)
Similarly, for link L2,
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
Hence, answer is option A.
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
3 | |
5 | |
10 | |
20 |

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?
204.204.204.128/255.255.255.192 204.204.204.0/255.255.255.128 204.204.204.64/255.255.255.128 | |
204.204.204.0/255.255.255.192 204.204.204.192/255.255.255.128 204.204.204.64/255.255.255.128 | |
204.204.204.128/255.255.255.128 204.204.204.192/255.255.255.192 204.204.204.224/255.255.255.192 | |
204.204.204.128/255.255.255.128 204.204.204.64/255.255.255.192 204.204.204.0/255.255.255.192 |
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”.
Query a NS for the root domain and then NS for the “dom” domains | |
Directly query a NS for “dom” and then a NS for “mydomain.dom” domains | |
Query a NS for in-addr.arpa and then a NS for 128.145.in-addr.arpa domains | |
Directly query a NS for 145.in-addr.arpa and then a NS for 128.145.in-addr.arpa domains |
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 |
01110 | |
01011 | |
10101 | |
10110 |
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
3 | |
4 | |
5 | |
6 |
where p is the primitive root and n is the modulus and 'a' and 'b' are the secret values selected by parity A & B.
So answer is,
32×5 mod 7 = 310 mod 7 = 4
Question 81 |
(i) 80 MB (ii) 2040 MB | |
(i) 2040 MB (ii) 80 MB | |
(i) 80 MB (ii) 360 MB | |
(i) 80 MB (ii) 360 MB |
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 |
13.5 ms | |
10 ms | |
9.5 ms | |
20 ms |
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, angulur 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 |
800000 | |
40080 | |
32020 | |
100 |
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 |
0 | |
30400 | |
38400 | |
798400 |
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 |
id + id + id + id | |
id + (id* (id * id)) | |
(id* (id * id)) + id | |
((id * id + id) * id) |

Question 86 |
5 | |
4 | |
3 | |
2 |
Question 87 |
E1 : A[i][j] and E2 : i = j; | |
E1 : !A[i][j] and E2 : i = j + 1; | |
E1: !A[i][j] and E2 : i = j; | |
E1 : A[i][j] and E2 : i = j + 1;
|
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.
So, answer is (C).
Question 88 |
(A[i][j] && !A[j][i]) | |
(!A[i][j] && A[j][i]) | |
(!A[i][j] | | A[j][i]) | |
(A[i][j] | | !A[j][i]) |
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 90 |
>100 but finite | |
∞ | |
3 | |
>3 and ≤100 |
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.