GATE 2010
Question 1 |
Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then
|S| = 2|T| | |
|S| = |T| - 1 | |
|S| = |T| | |
|S| = |T| + 1 |

id= no. of vertices of degree ‘d’ in ‘G’
Eg:

No. of vertices with degree ‘2’ = 3
ξ(G') = 3 × 2 = '6' i.e., sum of degrees
By Handshaking Theorem,
The sum of degrees would be equal to twice the no. of edges
|V| = 2|E|
It is given that ξ(G) = ξ(S) then
Sum of degrees of vertices in G is equal to sum of degrees of vertices in S
i.e., 2*(no. of edges in G) = 2*no. of edges in S no. of edges in G = no. of edges in S
Eg:

ξ(G) = (2 × 2) + (2 × 3) = 4 + 6 = 10

ξ(S) = 2 × 5 = 10
You can observe that, though no. of vertices are different, but still no. of edges are same.
Question 2 |
Newton-Raphson method is used to compute a root of the equation x2 - 13 = 0 with 3.5 as the initial value. The approximation after one iteration is
3.575 | |
3.676 | |
3.667 | |
3.607 |
Question 3 |
What is the possible number of reflexive relations on a set of 5 elements?
210 | |
215 | |
220 | |
225 |
Definition of Reflexive relation:
A relation ‘R’ is reflexive if it contains xRx ∀ x∈A
A relation with all diagonal elements, it can contain any combination of non-diagonal elements.
Eg:
A={1, 2, 3}


So for a relation to be reflexive, it should contain all diagonal elements. In addition to them, we can have possible combination of (n2-n)non-diagonal elements (i.e., 2n2-n)
Ex:
{(1,1)(2,2)(3,3)} ----- ‘0’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)} ----- ‘1’ non-diagonal element
{(1,1)(2,2)(3,3)(1,2)(1,3)} “
___________ “
___________ “
{(1,1)(2,2)(3,3)(1,2)(1,3)(2,1)(2,3)(3,1)(3,2)} (n2-n) diagonal elements
____________________
Total: 2n2-n
For the given question n = 5.
The number of reflexive relations = 2(25-5) = 220
Question 4 |
Consider the set S = {1, ω, ω2}, where ω and ω2 are cube roots of unity. If * denotes the multiplication operation, the structure (S,*) forms
A group | |
A ring | |
An integral domain | |
A field |
1) Closure
2) Associativity
3) Have Identity element
4) Invertible
Over ‘*’ operation the S = {1, ω, ω2} satisfies the above properties.
The identity element is ‘1’ and inverse of 1 is 1, inverse of ‘w’ is 'w2' and inverse of 'w2' is 'w'.
Question 6 |
The minterm expansion of is
m2+m4+m6+m7 | |
m0+m1+m3+m5 | |
m0+m1+m6+m7 | |
m2+m3+m4+m5 |
= PQR + PQR' + PQR' + P'QR' + PQR' + PQ'R'
= PQR + PQR' + P'QR' + PQ'R'
= m7 + m6 + m2 + m4
Question 7 |
A main memory unit with a capacity of 4 megabytes is built using 1M 1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is
100 nanoseconds | |
100*210 nanoseconds | |
100*220 nanoseconds | |
3200*220 nanoseconds |
Required capacity = 4MB
Number of chips needed = 4M*8 bits / 1M x 1-bit = 32 (1M x 1-bit)/(1M x 1-bit) = 32
Irrespective of the number of chips, all chips can be refreshed in parallel.
And all the cells in a row are refreshed in parallel too. So, the total time for refresh will be number of rows times the refresh time of one row.
Here we have 1K rows in a chip and refresh time of single row is 100ns.
So total time required = 1K × 100
= 100 × 210 nanoseconds
Question 8 |
P is a 16-bit signed integer. The 2's complement representation of P is (F87B)16. The 2's complement representation of 8*P is
(C3D8)16 | |
(187B)16 | |
(F878)16 | |
(987B)16 |
(F87B)16=(1111 1000 0111 1011)2. (It is a negative number which is in 2's complement form)
P = 1111 1000 0111 1011 (2's complement form)
8 * P = 23* P = 1100 0011 1101 1000. ( NOTE: Left shift k times is equivalent to Multiplication by 2k)
Hence, 1100 0011 1101 1000 is 2's complement representation of 8P.
1100 0011 1101 1000 = (C3D8)16.
Question 9 |
The Boolean expression for the output 'f' of the multiplexer shown below is
![]() | |
P⊕Q⊕R | |
P+Q+R | |
![]() |
= (P’Q’ + PQ)R + (P’Q+PQ’)R’
= (P⊕Q)’R + (P⊕Q)R’
= (P⊕Q⊕R)
Question 10 |
In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
0 | |
1 | |
(n-1)/2 | |
n-1 |
Every node has an odd number of descendants.
Also given every node is considered to be its own descendant.

― This is even number of descendants (2), because A is also considered as a descendant.

― This is odd number of descendants (3), A, B, C are descendants here.
Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.
Question 11 |
What does the following program print?
#include void f(int *p, int *q) { p = q; *p = 2; } int i = 0, j = 1; int main() { f(&i, &j); printf("%d %d n", i, j); getchar(); return 0; }
2 2 | |
2 1 | |
0 1 | |
0 2 |

Both pointers points to j = 1
now *p = 2
where j is updated with value 2.
printf (i, j) i = 0, j = 2
Question 12 |
Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10nlog10n time units to process n records.What is the smallest value of k for which package B will be preferred over A?
12 | |
10 | |
6 | |
5 |
Let n = 10k records. Substitute into 10nlog10n ≤ 0.0001n2
10(10k)log1010k ≤ 0.0001(10k)2
10k+1k ≤ 0.0001 × 102k
k ≤ 102k−k−1−4
k ≤ 10k−5
According to the problem value 6 is suitable for K.
Question 13 |
Which data structure in a compiler is used for managing information about variables and their attributes?
Abstract syntax tree | |
Symbol table | |
Semantic stack | |
Parse Table |
Question 14 |
Which languages necessarily need heap allocation in the runtime environment?
Those that support recursion | |
Those that use dynamic scoping | |
Those that allow dynamic data structures | |
Those that use global variables |
Question 15 |
One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?
It can be used to prioritize packets
| |
It can be used to reduce delays
| |
It can be used to optimize throughput | |
It can be used to prevent packet looping |
Question 16 |
Which one of the following is not a client server application?
Internet chat | |
Web browsing | |
E-mail | |
ping |
Question 17 |
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
L2 – L1 is recursively enumerable
| |
L1 – L3 is recursively enumerable | |
L2 ∩ L1 is recursively enumerable | |
L2 ∪ L1 is recursively enumerable |
L1 − L3 means L1 ∩ L3c, since recursive enumerable is not closed under complement, so L3c may or may not be recursive enumerable, hence we cannot say that L1 − L3 will always be recursive enumerable. So B is not necessarily true always.
L2 ∩ L1 means (Recursive enum ∩ Recursive) , as every recursive is recursive enum also, so it is equivalent to (Recursive enum ∩ Recursive enum) and recursive enum is closed under intersection, so L2 ∩ L1 must be recursive enumerable. Hence C is always true.
L2 ∪ L1 means (Recursive enum ∪ Recursive) , as every recursive is recursive enum also, so it is equivalent to (Recursive enum ∪ Recursive enum) and recursive enum is closed under union, so L2 ∪ L1 must be recursive enumerable. Hence D is always true.
Question 18 |
Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
1 | |
2 | |
3 | |
4 |
― Here,
p = order
key = order – 1 = p – 1
― In the non-root node, the minimum no. of keys = ⌈p/2⌉-1
― So, key = 5
order = 6
― So, minimum no. of keys in root node =⌈6/2⌉ - 1 = 2
Question 19 |
A relational schema for a train reservation database is given below. Passenger (pid, pname, age) Reservation (pid, class, tid)
Table: Passenger pid pname age ----------------- 0 Sachin 65 1 Rahul 66 2 Sourav 67 3 Anil 69 Table : Reservation pid class tid --------------- 0 AC 8200 1 AC 8201 2 SC 8201 5 AC 8203 1 SC 8204 3 AC 8202
What pids are returned by the following SQL query for the above instance of the tables?
SELECT pid FROM Reservation , WHERE class ‘AC’ AND EXISTS (SELECT * FROM Passenger WHERE age > 65 AND Passenger. pid = Reservation.pid)
1, 0 | |
1, 2 | |
1, 3 | |
1, 5 |

― 1, 3 Pids are returned
Question 20 |
Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?
I. 2-phase locking II. TIme-stamp ordering
I only | |
II only | |
Both I and II | |
Neither I nor II |
― Timestamp ordering protocol ensures conflict serializability and free from deadlock.
Question 21 |
The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side?

19 | |
21 | |
20 | |
10 |
Question 22 |
What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle?
P. Requirements Capture 1. Module Development and Integration Q. Design 2. Domain Analysis R. Implementation 3. Structural and Behavioral Modeling S. Maintenance 4. Performance Tuning
P-3, Q-2, R-4, S-1 | |
P-2, Q-3, R-1, S-4 | |
P-3, Q-2, R-1, S-4 | |
P-2, Q-3, R-4, S-1 |
Question 23 |
Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.

Which one of the following statements describes the properties achieved?
Mutual exclusion but not progress
| |
Progress but not mutual exclusion | |
Neither mutual exclusion nor progress | |
Both mutual exclusion and progress |
Question 24 |
A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?
196 | |
192 | |
197 | |
195 |
Page 1 …….. Page 100 causes 100 faults.
Now, when they are accesses in reverse order page 100, 99, 98, 97 are already present. So we get 96 page faults. So, total of 196 page faults.
Question 25 |
Which of the following statements are true?
- I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time
I only | |
I and III only | |
II and III only | |
I, II and III |
- Pre-emptive scheduling causes starvation (for example lower priority jobs are waiting).
- Best Response time is given by RR.
Question 26 |
Consider a company that assembles computers. The probability of a faulty assembly of any computer is p. The company therefore subjects each computer to a testing process. This testing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty?
pq + (1 - p)(1 - q) | |
(1 - q)p | |
(1 - p)q | |
pq |
= Probability of testing process gives the correct result × Probability that computer is faulty + Probability of testing process giving incorrect result × Probability that computer is not faulty
= p × q + (1 - p) (1 - q)
Question 27 |
What is the probability that divisor of 1099 is a multiple of 1096?
1/625 | |
4/625 | |
12/625 | |
16/625 |
We can write 1099 as 1096×103
So, (1099)/(1096) to be a whole number, [1096×103/1096] ➝ (1)
We can observe that every divisor of 103 is a multiple of 1096
So number of divisor of 103 to be found first
⇒ 103 = (5×2)3 = 23×53
No. of divisors = (3 + 1) (3 + 1) = 16
Total number of divisor of 1099 are 1099 = 299×599 = 100×100 = 10000
Probability that divisor of 1099 is a multiple of 1096 is
⇒ 16/10,000
Question 28 |
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
- (I) 7, 6, 5, 4, 4, 3, 2, 1
(II) 6, 6, 6, 6, 3, 3, 2, 2
(III) 7, 6, 6, 4, 4, 3, 2, 2
(IV) 8, 7, 7, 6, 4, 2, 1, 1
I and II | |
III and IV | |
IV only | |
II and IV |
⇾ Arrange the degree of vertices in descending order
eg. d1, d2, d3... dn
⇾ Discard d1, subtrack ‘1’ from the next 'd1' degrees
eg:

⇒ 1 1 0 1
⇾ We should not get any negative value if its negative, this is not valid sequence
⇾ Repeat it till we get ‘0’ sequence
I. 7, 6, 5, 4, 4, 3, 2, 1
➡️5, 4, 3, 3, 2, 1, 0
➡️3, 2, 2, 1, 0, 0
➡️1, 1, 0, 0, 0
➡️0, 0, 0, 0
[valid]
II. 6, 6, 6, 6, 3, 3, 2, 2
➡️5, 5, 5, 2, 2, 1, 2
put them in descending order
➡️5, 5, 5, 2, 2, 2, 1
➡️4, 4, 1, 1, 1, 1
➡️3, 0, 0, 0, 1 (descending order)
➡️3, 1, 0, 0, 0
➡️0, -1, -1, 0
[This is not valid]
III. 7, 6, 6, 4, 4, 3, 2, 2
➡️5, 5, 3, 3, 2, 1, 1
➡️4, 2, 2, 1, 0, 1
➡️4, 2, 2, 1, 1, 0 (descending order)
➡️1, 1, 0, 0, 0
➡️0, 0, 0, 0
[valid]
IV. 8, 7, 7, 6, 4, 2, 1, 1
There is a degree ‘8’, but there are only ‘8’ vertices.
A vertex cannot have edge to itself in a simple graph. This is not valid sequence.
Question 29 |
Consider the following matrix . If the eigenvalues of A are 4 and 8, then
x=4, y=10 | |
x=5, y=8 | |
x=-3, y=9 | |
x=-4, y=10 |

Trace = {Sum of diagonal elements of matrix}

Here given that eigen values are 4, 8
Sum = 8 + 4 = 12
Trace = 2 + y
⇒ 2 + y = 12
y = 10

Determinant = |2y - 3x|
Product of eigen values = 8 × 4 = 32
2y - 3x = 32
(y = 10)
20 - 3x = 32
-12 = 3x
x = -4
∴ x = -4, y = 10
Question 30 |
Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. Which one of the statements below expresses best the meaning of the formula ∀x∃y∃t(¬F(x,y,t))?
Everyone can fool some person at some time | |
No one can fool everyone all the time | |
Everyone cannot fool some person all the time
| |
No one can fool some person at some time |
For better understanding propagate negation sign outward by applying Demorgan's law.
∀x∃y∃t(¬F(x, y, t)) ≡ ¬∃x∀y∀t(F(x,y,t))
Now converting ¬∃x∀y∀t(F(x,y,t)) to English is simple.
¬∃x∀y∀t(F(x,y,t)) ⇒ There does not exist a person who can fool everyone all the time.
Which means "No one can fool everyone all the time".
Hence, Option (B) is correct.
Question 31 |
What is the Boolean expression for the output f of the combinational logic circuit of NOR gates given below?

![]() | |
![]() | |
![]() | |
![]() |
= (P’Q’ + Q’R’)( P’R’ + Q’R’)
= (P’Q’P’R’ + P’Q’Q’R’ + Q’R’P’R’ + Q’R’Q’R’)
= (P’Q’R’ + P’Q’R’ + P’Q’R’ + Q’R’)
= (P’Q’R’ + Q’R’)
= (Q’R’)
= (Q+R)’
Question 32 |
In the sequential circuit shown below,if the initial value of the output Q1Q0 is 00,what are the next four values of Q1Q0?

11, 10, 01, 00 | |
10, 11, 01, 00 | |
10, 00, 01, 11 | |
11, 10, 00, 01 |

The next four values of Q1Q0 are 11, 10, 01, 00.
Question 33 |
A 5-stage pipelined processor has Instruction Fetch(IF),Instruction Decode(ID),Operand Fetch(OF),Perform Operation(PO)and Write Operand(WO)stages.The IF,ID,OF and WO stages take 1 clock cycle each for any instruction.The PO stage takes 1 clock cycle for ADD and SUB instructions,3 clock cycles for MUL instruction,and 6 clock cycles for DIV instruction respectively.Operand forwarding is used in the pipeline.What is the number of clock cycles needed to execute the following sequence of instructions?
Instruction Meaning of instruction I0 :MUL R2 ,R0 ,R1 R2 ¬ R0 *R1 I1 :DIV R5 ,R3 ,R4 R5 ¬ R3/R4 I2 :ADD R2 ,R5 ,R2 R2 ¬ R5+R2 I3 :SUB R5 ,R2 ,R6 R5 ¬ R2-R6
13 | |
15 | |
17 | |
19 |

Question 34 |
The weight of a sequence a0, a1, ..., an-1 of real numbers is defined as a0+a1/2+...+ an-1/2n-1. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0, a1, ...,an-1 and Y the maximum possible weight of a subsequence of a1, a2, ..., an-1. Then X is equal to
max(Y, a0+Y) | |
max(Y, a0+Y/2) | |
max(Y, a0+2Y) | |
a0+Y/2 |
1. Do not include a0 in the subsequence: then the maximum possible weight will be equal to maximum possible weight of a subsequence of {a1, a2,….an} which is represented by Y
2. Include a0: then maximum possible weight will be equal to : a0 + (each number picked in Y will get divided by 2) = a0 + Y/2.
Key point here is Y will itself pick optimal subsequence to maximize the weight. The value of a0 can be anything (negative or
Note: Y/2 meaning: Each number picked in Y will get divided by 2.
Question 35 |
What is the value printed by the following C program
#includeint f(int *a, int n) { if(n <= 0) return 0; else if(*a % 2 == 0) return *a + f(a+1, n-1); else return *a - f(a+1, n-1); } int main() { int a[] = {12, 7, 13, 4, 11, 6}; printf("%d", f(a, 6)); getchar(); return 0; }
-9 | |
5 | |
15 | |
19 |
if (n <= 0)
return 0;
else if (*a % 2 = = 0)
return *a + f(a+1, n-1);
else
return *a – f(a+1, n-1);


⇒ 12+(7-(13-(4+(11-(6)))))
⇒ 12+(7-(13-(4+5)))
⇒ 12+7-(4)
⇒ 12+3
⇒ 15
Question 36 |
The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
typedef struct node { int value; struct node *next; }Node; Node *move_to_front(Node *head) { Node *p, *q; if ((head == NULL: || (head->next == NULL)) return head; q = NULL; p = head; while (p-> next !=NULL) { q = p; p = p->next; } _______________________________ return head; }
Choose the correct alternative to replace the blank line.
q = NULL; p→next = head; head = p; | |
q→next = NULL; head = p; p→next = head; | |
head = p; p→next = q; q→next = NULL; | |
q→next = NULL; p→next = head; head = p; |
The function modifies the list by moving the last element to the front of the list.
Let the list be 1 → 2 → 3 → 4 & the modified list must be 4 → 1 → 2 → 3.
Algorithm:
Traverse the list till last node. Use two pointers. One to store the address of last node & other for the address of second last node.
After completion of loop. Do these.
(i) Make second last as last
(ii) Set next of last as head
(iii) Make last as head

while (p → !=NULL)
{
q = p;
p = p → next;
}
― p is travelling till the end of list and assigning q to whatever p had visited & p takes next new node, so travels through the entire list.
Now the list looks like

According to the Algorithm new lines must be
q → next = NULL; p → next = head; head = p

Question 37 |
The program below uses six temporary variables a, b, c, d, e, f.
a = 1 b = 10 c = 20 d = a+b e = c+d f = c+e b = c+e e = b+f d = 5+e return d+f
Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
2 | |
3 | |
4 | |
6 |
Assume 'a' is mapped to r1, 'b' to r2 and 'c' to r3.
d = a + b, after this line if u notice 'a' is never present on right hand side, so we can map 'd' to r1.
e = c + d, after this line 'd' is never present on rhs, so we can map 'e' to r1.
at this time mapping is
r1 --- e
r2 --- b
r3 --- c
We have 3 registers for e, b and c.
f = c + e
b = c + e
These two are essentially doing same thing, after these two line 'b' and 'f' are same so we can skip computing 'f' or need not give any new register for 'f'. And wherever 'f' is present we can replace it with 'b', because neither of 'f' and 'b' are changing after these two lines, so value of these will be 'c+e' till the end of the program.
At second last line "d = 5 + e"
here 'd' is introduced, we can map it to any of the register r1 or r3, because after this line neither of 'e' or 'c' is required. Value of 'b' is required because we need to return 'd+f', and 'f' is essentially equal to 'b'
finally code becomes
r1 = 1
r2 = 10
r3 = 20
r1 = r1 + r2
r1 = r3 + r1
r2 = r3 + r1
r2 = r3 + r1
r1 = r2 + r2
r3 = 5 + r1
return r3 + r2
Therefore minimum 3 registers needed.
Question 38 |
The grammar S → aSa|bS|c is
LL(1) but not LR(1) | |
LR(1) but not LR(1) | |
Both LL(1) and LR(1) | |
Neither LL(1) nor LR(1) |

As there is no conflict in LL(1) parsing table, hence the given grammar is LL(1) and since every LL(1) is LR(1) also, so the given grammar is LL(1) as well as LR(1).
Question 39 |
Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
(0*10*1)* | |
0*(10*10*)* | |
0*(10*1*)*0* | |
0*1(10*1)*10* |
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
Question 40 |
Consider the languages
- L1 = {0i1j | i != j}.
L2 = {0i1j | i = j}.
L3 = {0i1j | i = 2j+1}.
L4 = {0i1j | i != 2j}.
Which one of the following statements is true?
Only L2 is context free | |
Only L2 and L3 are context free | |
Only L1 and L2 are context free | |
All are context free |
Question 41 |
Let w be any string of length n is {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
n-1 | |
n | |
n+1 | |
2n-1 |

Since L is set of all substrings of “w” (Substring of a string is obtained by deleting any prefix or any suffix from string), so if we consider “w” as “101” , then the substrings of w are { ϵ, 0, 1, 10, 01, 101}.
Since the string “101” is also its substring, so we require 4 states (i.e. for n length string, n+1 states are required) and the NFA would be:

Question 42 |
Consider the following schedule for transactions T1, T2 and T3:
Which one of the schedules below is the correct serialization of the above?
T1 → T3 → T2 | |
T2 → T1 → T3 | |
T2 → T3 → T1 | |
T3 → T1 → T2 |

― Precedence graph for the above schedule is,

― From the precedence graph the correct serialization is,

Question 43 |
Which of the following functional dependencies hold for relations R(A, B, C) and S(B, D, E):
B -> A A -> C
The relation R contains 200 tuples and the rel ation S contains 100 tuples. What is the maximum number of tuples possible in the natural join of R and S (R natural join S)
100 | |
200 | |
300 | |
2000 |
R(A, B, C) – 200 tuples
S(B, D, E) – 100 tuples
FD’s:
B → A
A → C
― ‘B’ is primary key for R and foreign key of S from the given FDs.
― Maximum tuples in natural join of R and S is min(200, 100) = 100.
Question 44 |
The following program is to be tested for statement coverage:
begin if (a== b) {S1; exit;} else if (c== d) {S2;] else {S3; exit;} S4; end
The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given. T1 : a, b, c and d are all equal T2 : a, b, c and d are all distinct T3 : a = b and c != d T4 : a != b and c = d Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?
T1, T2, T3 | |
T2, T4 | |
T3, T4 | |
T1, T2, T4 |
T2 covers S3
T4 covers S2, S4.
Question 45 |
The following program consists of 3 concurrent processes and 3 binary semaphores.The semaphores are initialized as S0 = 1, S1 = 0, S2 = 0.

How many times will process P0 print '0'?
At least twice | |
Exactly twice | |
Exactly thrice | |
Exactly once |
S1=0
S2=0
P0 enters the critical section first,
prints (‘0’)
releases S1,S2(i.e., S1=1 & S2=1)
Now P1 & P2 both can enter critical section releases S0 & prints (‘0’)
This process continues, hence the number of zero’s printed ≥2.
Question 46 |
A system has n resources R0,...,Rn-1,and k processes P0,....Pk-1.The implementation of the resource request logic of each process Pi is as follows:
if (i % 2 == 0) { if (i < n) request Ri if (i+2 < n) request Ri+2 } else { if (i < n) request Rn-i if (i+2 < n) request Rn-i-2 }
In which one of the following situations is a deadlock possible?
n = 40, k = 26 | |
n = 21, k = 12 | |
n = 20, k = 10 | |
n = 41, k = 19 |
P10 requests R10 & R11
P11 requests R10 & R8
Hence P10 & P11 inorder in deadlock.
Question 47 |
Suppose computers A and B have IP addresses 10.105.1.113 and 10.105.1.91 respectively and they both use the same net mask N. Which of the values of N given below should not be used if A and B should belong to the same network?
255.255.255.0 | |
255.255.255.128 | |
255.255.255.192 | |
255.255.255.224 |
When we perform AND operation between IP address 10.105.1.113 and 255.255.255.224 result is 10.105.1.96 and when we perform AND operation between IP address 10.105.1.91 and 255.255.255.224 result is 10.105.1.64.
Therefore, 10.105.1.96 and 10.105.1.64 are different network, so D is correct answer.
Question 48 |
A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively.

When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache. What is the time taken for this transfer?
2 nanoseconds | |
20 nanoseconds | |
22 nanoseconds | |
88 nanoseconds |
And it requires one access of L1 cache and one access of L2 cache. So time taken = 20+2 = 22ns
Question 49 |
A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively.

When there is a miss in both L1 cache and L2 cache, first a block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache to L1 cache. What is the total time taken for these transfers?
222 nanoseconds | |
888 nanoseconds | |
902 nanoseconds | |
968 nanoseconds |
And it requires one access of L1 cache and one access of L2 cache. So time taken = 20+2 = 22ns
L2 cache block is of size 16 words and nothing is mentioned about the main memory block, so we assume the main memory block is also of size 16 words. But the bus between L2 and main memory is only 4 words..so when the data has to be transferred from main memory to L2 cache it has to send 4 times through the data bus.
When a data request comes to L1, if there is a cache miss in L1 then it will be searched in L2 if there is a hit in L2 then the required data is transferred from L2 to L1 in a single transfer through the bus. If there is a miss in L2 then it will be searched in main memory. Then the 16 words data from main memory will be transferred to L2 in 4 transfers through the data bus. Time taken for this = 4*(200+20) = 4*220 = 880 ns
Then from L2 to L1 only 4 words of data will be transferred through the data bus in a single transfer. We know time taken for this is 22ns.
So total time taken = 880 + 22 = 902 ns
Question 50 |
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
7 | |
8 | |
9 | |
10 |

So, the edges of the spanning tree given that vertex 0 is a leaf node in the tree,

So, the minimum possible weight of spanning tree will be
= 1 + 4 + 2 + 3
= 10
Question 51 |
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
7 | |
8 | |
9 | |
10 |

The minimum possible weight of a path p from vertex 1 to vertex 2 such that p contains atmost 3 edges,

= 1 + 4 + 3
= 8
Question 52 |
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
46, 42, 34, 52, 23, 33 | |
34, 42, 23, 52, 33, 46
| |
46, 34, 42, 23, 52, 33 | |
42, 46, 33, 23, 34, 52
|
After inserting 6 values, the table looks like

The possible order in which the keys are inserted are:
34, 42, 23, 46 are at their respective slots 4, 2, 3, 6.
52, 33 are at different positions.
― 52 has come after 42, 23, 34 because, it has the collision with 42, because of linear probing, it should have occupy the next empty slot. So 52 is after 42, 23, 34.
― 33 is after 46, because it has the clash with 23. So it got placed in next empty slot 7, which means 2, 3, 4, 5, 6 are filled.
42, 23, 34 may occur in any order but before 52 & 46 may come anywhere but before 33.

So option (C)

Question 53 |
A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
10 | |
20 | |
30 | |
40 |
― 33 must be inserted at last (only one possibility)
― 46 can be inserted in any of the 5 places remaining. So 5 ways.
― 52 must be inserted only after inserting 42, 23, 34. So only one choice for 52.
〈42,23,34〉 can be sequenced in 3! ways.
Hence, 5×3! = 30 ways
Question 54 |
Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram:

All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all the routing tables stabilize, how many links in the network will never be used for carrying any data?
4 | |
3 | |
2 | |
1 |
Similarly, link R4-R6 will not be used, instead this link we can use R4-R5-R6 link which costs only 5 unit.
Question 55 |
Consider a network with 6 routers R1 to R6 connected with links having weights as shown in the following diagram:

Suppose the weights of all unused links in the previous question are changed to 2 and the distance vector algorithm is used again until all routing tables stabilize. How many links will now remain unused?
0 | |
1 | |
2 | |
4 |

And only link that will be removed is R5-R6 link.
Question 56 |
Choose the most appropriate word from the options given below to the complete the following sentence:
His rather casual remarks on politics ___________ his lack of seriousness about the subject.
masked | |
belied | |
betrayed | |
suppressed |
Belied - Not appropriate to given
Betrayed - Most appropriate to given (Reveal intentionally)
Suppressed - Irrelevant to given
Answer is option C.
Question 57 |
Which of the following options is closest in meaning to the word below:
Circuitouscyclic | |
indirect
| |
confusing | |
crooked |
Question 58 |
Choose the most appropriate word from the options given below to complete the following sentence:
If we manage to ____________ our natural resources, we would leave a better planet for our children.
uphold | |
restrain | |
cherish | |
conserve |
Restrain - keep under control
Cherish - be fond of
Conserve - protect from harm i.e., keeping safety, loss of destruction
Answer is option d.
Question 59 |
25 persons are in a room. 15 of them play hockey, 17 of them play football and 10 of them play both hockey and football. Then the number of persons playing neither hockey nor football is:
2 | |
17 | |
13 | |
3 |

Total number of persons = a+b+c = 25 → (1)
Number of persons who play hockey = a+b = 15 → (2)
Number of persons who play football = b+c = 17 → (3)
Number of persons who play hockey and football = b = 10 → (4)
From (2) ⇒ a=5
From (3) ⇒ c=7
From (1) ⇒ d = 3
Number of persons who play neither hockey nor football = d = 3
Question 60 |
The question below consists of a pair of related words followed by four pairs of words. Select the pair that best expresses the relation in the original pair.
Unemployed: Workerfallow: land | |
unaware: sleeper | |
wit: jester | |
renovated: house |
→ Same as a land which is not used called fallow.
Question 61 |
If 137+276 = 435 how much is 731+672?
534 | |
1403 | |
1623 | |
1513 |
(137)x + (276)x = (435)x
x2 + 3x + 7 + 2x2 + 7x + 6 = 4x2 + 3x + 5
x2 - 7x - 8 = 0
x = 8 (or) -1
∴ x = 8 (-1 cannot be a base)
(731)x + (672)x = (731)8 + ( 672)8
= 7 × 82 + 3× 8 + 1×1 + 6 × 82 + 7 × 8 + 2 × 1
= 915
From the options, 915 can be written as 1623 in base 8.
Question 62 |
Hari(H), Gita(G), Irfan(I) and Saira(S) are siblings (i.e., brothers and sisters). All were born on 1st January. The age difference between any two successive siblings (that is born one after another) is less than 3 years. Given the following facts:
- i. Hari's age + Gita's age > Irfan's age + Saira's age.
ii. The age difference between Gita and Saira is 1 year. However Gita is not the oldest and Saira is not the youngest.
iii. There are no twins.
In what order were they born (oldest first)?
HSIG | |
SGHI | |
IGSH | |
IHSG |
Option A: HSIG
from (ii) , we can say that Gita and Saira are successive siblings.
Hence, option A is not true.
Option C: IGSH

In any of the above 4 cases, (i) is not true.
Hence, option C is not true.
Option D: IHSG

In any of the above 4 cases, (i) is not true.
Hence, option D is not true.
Option B: SGHI

In last two cases, all the facts are true.
∴ The order is SGHI.
Question 63 |
Modern warfare has changed from large scale clashes of armies to suppression of civilian populations. Chemical agents that do their work silently appear to be suited to such warfare; and regretfully, there exist people in military establishments who think that chemical agents are useful tools for their cause.
Which of the following statements best sums up the meaning of the above passage:
Modern warfare has resulted in civil strife. | |
Chemical agents are useful in modern warfare. | |
Use of chemical agents in warfare would be undesirable. | |
People in military establishments like to use chemical agents in war.
|
Question 64 |
5 skilled workers can build a wall in 20 days: 8 semi-skilled workers can build a wall in 25 days; 10 unskilled workers can build a wall in 30 days. If a team has 2 skilled, 6 semi-skilled and 5 unskilled workers, how long will it take to build the wall?
20 | |
10 | |
16 | |
15 |
Capacity = 1/100
8 semi-skilled workers can build the wall in 25 days
⇒ 1 semi-skilled worker can build the wall in 200 days
Capacity = 1/200
10 un-skilled workers can build the wall in 30 days
⇒ 1 un-skilled worker can build the wall in 300 days
Capacity = 1/300
1 day work (2 skilled + 6 semi-skilled + 5 unskilled) = 2(1/100) + 6(1/200) + 5(1/300) = 1/15
∴ They can complete the work in 15 days.
Question 65 |
Given digits 2, 2, 3, 3, 3, 4, 4, 4, 4 how many distinct 4 digit numbers greater than 3000 can be formed?
50 | |
51 | |
52 | |
54 |
⇒ First digit: 3 or 4
(i) First digit - 3:
We have to choose 3 digits from (2, 2, 3, 3, 4, 4, 4, 4).
Any place can have either 2 or 3 or 4, but (222, 333) is not possible as we have only two 2's and two 3's.
Total = 3 × 3 × 3 - 2 = 25
(ii) First digit - 4:
We have to choose 4 digits from (2, 2, 3, 3, 4, 4, 4, 4).
Any place can have either 2 or 3 or 4, but (222) is not possible we have only two 2's.
Total = 3 × 3 × 3 - 1 = 26
∴ Total number possible = 25 + 26 = 51