GATE 2022
Question 1 
The _________ is too high for it to be considered _________.
fair / fare
 
faer / fair
 
fare / fare
 
fare / fair

Question 1 Explanation:
Fare: The money paid for a journey.
Fair: treating people equally without favouritism or discrimination (or) without cheating (or) trying to achieve unjust advantage
The fare is too high for it to be considered fair.
Question 2 
A function y(x) is defined in the interval [0, 1] on the xaxis as
Which one of the following is the area under the curve for the interval [0, 1] on the xaxis?
5/6  
6/5  
13/6  
6/13 
Question 2 Explanation:
We know that area of a rectangle = length * breadth = L * B
Area of rectangle (1) = L*B = (1/3) * 2 = (2/3)
Area of rectangle (2) = L*B = (3/4  1/3 ) * 3 = (5/4 )
Area of rectangle (3) = L*B = (1  3/4) * 1 = 1/4
Therefore Total area = Area(1+2+3) = (2/3) + (5/4) + (1/4) = 26/12 = 13/6
Question 3 
Let r be a root of the equation x^{2} + 2x + 6 = 0.
Then the value of the expression (r + 2)(r + 3)(r + 4)(r + 5) is
51  
51  
126  
126 
Question 3 Explanation:
Question 4 
Given below are four statements.
Statement 1: All students are inquisitive.
Statement 2: Some students are inquisitive.
Statement 3: No student is inquisitive.
Statement 4: Some students are not inquisitive.
From the given four statements, find the two statements that CANNOT BE
TRUE simultaneously, assuming that there is at least one student in the class.
Statement 1 and Statement 3  
Statement 1 and Statement 2  
Statement 2 and Statement 4  
Statement 3 and Statement 4 
Question 4 Explanation:
Explanation: Statement 1 & Statement 3 cannot be true simultaneously.
Statement 1: All students are inquisitive. Statement 3: No student is inquisitive
Statement 1: All students are inquisitive. Statement 3: No student is inquisitive
Question 5 
A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters.
From the additional plates given in the options, which one of the combinations of additional plates would allow the player to construct a fiveletter palindrome.The player should use all the five plates exactly once. The plates can be rotated in their plane.
Question 5 Explanation:
From the question we know that letters can rotate in the plane, now we will verify the options one by one.
Option 1: A,D,D,D,J from these letters we can't form a palindrome.
Option 2: A,D,R,A,R from these we can form RADAR which is a palindrome.
Option 3: A,D,Z,E,D from these letters we can't form a palindrome.
Option 4: A,D,I,L,Y from these letters we can't form a palindrome.
Option 2: A,D,R,A,R from these we can form RADAR which is a palindrome.
Option 3: A,D,Z,E,D from these letters we can't form a palindrome.
Option 4: A,D,I,L,Y from these letters we can't form a palindrome.
Question 6 
Some people believe that “what gets measured, improves”. Some others believe that “what gets measured, gets gamed”. One possible reason for the difference in the beliefs is the work culture in organizations. In organizations with good work culture, metrics help improve outcomes. However, the same metrics are counterproductive in organizations with poor work culture.
Which one of the following is the CORRECT logical inference based on the information in the above passage?
Metrics are useful in organizations with poor work culture  
Metrics are useful in organizations with good work culture  
Metrics are always counterproductive in organizations with good work culture  
Metrics are never useful in organizations with good work culture 
Question 6 Explanation:
From the given passage consider the sentence “In organizations with good work culture, metrics help improve outcomes”
Option A: Metrics are useful in organizations with poor work culture. Which is incorrect based on the sentence.
Option B: Metrics are useful in organizations with good work culture. Which is correct and relevant to the considered sentence.
Option C: Metrics are always counterproductive in organizations with good work culture. Which is incorrect because we can't always guarantee good work culture.
Option D: Metrics are never useful in organizations with a good work culture. Incorrect metrics will help to make a good work culture.
Option B: Metrics are useful in organizations with good work culture. Which is correct and relevant to the considered sentence.
Option C: Metrics are always counterproductive in organizations with good work culture. Which is incorrect because we can't always guarantee good work culture.
Option D: Metrics are never useful in organizations with a good work culture. Incorrect metrics will help to make a good work culture.
Question 7 
In a recently conducted national entrance test, boys constituted 65% of those who appeared for the test. Girls constituted the remaining candidates and they accounted for 60% of the qualified candidates.
Which one of the following is the correct logical inference based on the information provided in the above passage?
Equal number of boys and girls qualified  
Equal number of boys and girls appeared for the test  
The number of boys who appeared for the test is less than the number of girls
who appeared
 
The number of boys who qualified the test is less than the number of girls who
Qualified

Question 7 Explanation:
The girls accounted for 60% of the qualified candidates.
60% can be written as ⅗. Which means among 5 qualified persons three of them are girls.
So, The number of boys qualified is less than the number of girls qualified.
60% can be written as ⅗. Which means among 5 qualified persons three of them are girls.
So, The number of boys qualified is less than the number of girls qualified.
Question 8 
A box contains five balls of same size and shape. Three of them are green coloured balls and two of them are orange coloured balls. Balls are drawn from the box one at a time. If a green ball is drawn, it is not replaced. If an orange ball is drawn, it is replaced with another orange ball.
First ball is drawn. What is the probability of getting an orange ball in the next draw?
1/2  
8/25  
19/50  
23/50 
Question 8 Explanation:
Case 1: The first ball is Green
Probability of first ball is green = 3/5
If the first ball is green then we are not replacing so the probability of the second ball being orange is = 2/4.
Probability of first ball green and second ball orange is =3/5 * 2/4 = 6/20
Case 2: The first ball is orange
Probability of first ball is orange =2/5
If the first ball is orange then we are replacing it with another orange ball/ so the number balls will remain the same.
Probability of second ball is orange = 2/5
Probability of first ball is orange and second ball is also orange = 2/5*2/5 = 4/25
Therefore, Total probability = (6/20 + 4/25) = 23/50.
Probability of first ball is green = 3/5
If the first ball is green then we are not replacing so the probability of the second ball being orange is = 2/4.
Probability of first ball green and second ball orange is =3/5 * 2/4 = 6/20
Case 2: The first ball is orange
Probability of first ball is orange =2/5
If the first ball is orange then we are replacing it with another orange ball/ so the number balls will remain the same.
Probability of second ball is orange = 2/5
Probability of first ball is orange and second ball is also orange = 2/5*2/5 = 4/25
Therefore, Total probability = (6/20 + 4/25) = 23/50.
Question 9 
The corners and midpoints of the sides of a triangle are named using the distinct letters P, Q, R, S, T and U, but not necessarily in the same order. Consider the following statements:
The line joining P and R is parallel to the line joining Q and S.
P is placed on the side opposite to the corner T.
S and U cannot be placed on the same side.
Which one of the following statements is correct based on the above information?
P cannot be placed at a corner  
S cannot be placed at a corner  
U cannot be placed at a midpoint  
R cannot be placed at a corner 
Question 9 Explanation:
From the given information draw the image, such that
The Image is satisfying all given conditions. From this we can say that S cannot be placed at the corner. By satisfying all given conditions we can draw in different ways but in all cases S cannot be placed at the corner.
The Image is satisfying all given conditions. From this we can say that S cannot be placed at the corner. By satisfying all given conditions we can draw in different ways but in all cases S cannot be placed at the corner.
Question 10 
A plot of land must be divided between four families. They want their individual plots to be similar in shape, not necessarily equal in area. The land has equally spaced poles, marked as dots in the below figure. Two ropes, R1 and R2, are already present and cannot be moved.
What is the least number of additional straight ropes needed to create the desired plots? A single rope can pass through three poles that are aligned in a straight line.
2  
4  
5  
3 
Question 10 Explanation:
Given Conditions are Shape is to be similar, area need not to be same, A rope can pass through three poles.
Therefore least number of additional ropes required = 3.
Therefore least number of additional ropes required = 3.
Question 11 
Which one of the following statements is TRUE for all positive functions f (n) ?
f ( n ^2 ) ( f ( n ) ^2 ), when f ( n ) is a polynomial  
f ( n ^2 ) o ( f ( n ) ^2 )  
f ( n ^2 ) O ( f ( n ) ^2 ), when f ( n ) is an exponential function  
Question 11 Explanation:
constant < logarithmic < linear < polynomial < exponential < factorial
f(n)=n^c where c is a constant
f(n^2) = (n^2)^c = n^2c
(f(n))^2 = (n^c)^2 = n^2c
f(n^2) = (f(n))^2 is TRUE asymptotically.
OptionB: FALSE: The small omega function indicates the tightest upper bound.
f(n)^2 < o(f(n)^2) is FALSE asymptotically.
OptionC: FALSE: Consider f(n)=logn
f(n^2)=logn^2 = 2*logn
(f(n))^2 = (logn)^2 = logn * logn
f(n^2) <=Ω(f(n))^2 is FALSE asymptotically.
OptionD: FALSE:
Exponential values(Eg: 2^n, 3^n,..,k^n where k is a constant ”
f(n)=3^n
f(n^2)=f(3^(n^2)
(f(n))^2 = (3^n)^2 = 3^2n
f(n^2) >= O(f(n))^2 is FALSE asymptotically.
f(n)=n^c where c is a constant
f(n^2) = (n^2)^c = n^2c
(f(n))^2 = (n^c)^2 = n^2c
f(n^2) = (f(n))^2 is TRUE asymptotically.
OptionB: FALSE: The small omega function indicates the tightest upper bound.
f(n)^2 < o(f(n)^2) is FALSE asymptotically.
OptionC: FALSE: Consider f(n)=logn
f(n^2)=logn^2 = 2*logn
(f(n))^2 = (logn)^2 = logn * logn
f(n^2) <=Ω(f(n))^2 is FALSE asymptotically.
OptionD: FALSE:
Exponential values(Eg: 2^n, 3^n,..,k^n where k is a constant ”
f(n)=3^n
f(n^2)=f(3^(n^2)
(f(n))^2 = (3^n)^2 = 3^2n
f(n^2) >= O(f(n))^2 is FALSE asymptotically.
Question 12 
Which one of the following regular expressions correctly represents the language of the finite automaton given below?
ab * bab * ba * aba *  
( ab * b ) * ab * ( ba * a ) * ba *  
( ab * b ba * a ) * ( a * b * )  
( ba * a ab * b ) * ( ab * ba * ) 
Question 12 Explanation:
Regular expression ab*bab* +ba*aba* does not generate the string “abb” which is accepted by FA hence this is not true.
(ab*b)*ab*+(ba*a)*ba* does not generate the string “abbaa” hence this is also wrong.
(ab*b+ba*a)*(a*+b*) generates epsilon hence this is also wrong.
(ab*b+ba*a)*(ab*+ba*) is the correct regular expression.
GATE 2022 Computer Science and Information Technology (CS)
(ab*b)*ab*+(ba*a)*ba* does not generate the string “abbaa” hence this is also wrong.
(ab*b+ba*a)*(a*+b*) generates epsilon hence this is also wrong.
(ab*b+ba*a)*(ab*+ba*) is the correct regular expression.
GATE 2022 Computer Science and Information Technology (CS)
Question 13 
Which one of the following statements is TRUE?
The LALR (1) parser for a grammar G cannot have reducereduce conflict if the LR (1) parser for G does not have reducereduce conflict.  
Symbol table is accessed only during the lexical analysis phase.  
Data flow analysis is necessary for runtime memory management.  
LR (1) parsing is sufficient for deterministic contextfree languages. 
Question 13 Explanation:
Even though there is no reducereduce conflict in CLR(1) but in LALR(1) while merging the states differ in only lookahead may get reducereduce conflict. So the given statement is not true.
Symbol table is accessed in all the phases of compiler and not only in lexical analysis phase.
Data flow analysis is done in the control flow graph, in the code optimization phase. If LR(1) parses a grammar then definitely it is DCFL, so LR(1) parsing is sufficient for deterministic contextfree languages.
Symbol table is accessed in all the phases of compiler and not only in lexical analysis phase.
Data flow analysis is done in the control flow graph, in the code optimization phase. If LR(1) parses a grammar then definitely it is DCFL, so LR(1) parsing is sufficient for deterministic contextfree languages.
Question 14 
In a relational data model, which one of the following statements is TRUE?
A relation with only two attributes is always in BCNF.  
If all attributes of a relation are prime attributes, then the relation is in BCNF.  
Every relation has at least one nonprime attribute.  
BCNF decompositions preserve functional dependencies. 
Question 14 Explanation:
A relation with only two attributes will always be in BCNF.
Example:
R(A, B).
Two functional dependencies possible for the relation: (1) A>B and (2) B>A
If there is no functional dependency, we can assume trivial functional dependencies like AB>A and AB>B.
In all cases, functional dependencies like A>B, A must be a key.
So they all will be in BCNF irrespective of the functional depencies set.
Example:
R(A, B).
Two functional dependencies possible for the relation: (1) A>B and (2) B>A
If there is no functional dependency, we can assume trivial functional dependencies like AB>A and AB>B.
In all cases, functional dependencies like A>B, A must be a key.
So they all will be in BCNF irrespective of the functional depencies set.
Question 15 
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,
Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O (1) space?
It is not possible to reverse a singly linked list in O (1) space. 
Question 15 Explanation:
/* Link list node */
struct Node {
int data;
struct Node* next;
{
this>data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
/* Function to reverse the linked list */
void reverse()
{
// Initialize current, previous and
// next pointers
Node* current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL) {
// Store next
next = current>next;
// Reverse current node's pointer
current>next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
head = prev;
}
For the above algorithm :
Time Complexity: O(n)
Space Complexity: O(1)
struct Node {
int data;
struct Node* next;
{
this>data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
/* Function to reverse the linked list */
void reverse()
{
// Initialize current, previous and
// next pointers
Node* current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL) {
// Store next
next = current>next;
// Reverse current node's pointer
current>next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
head = prev;
}
For the above algorithm :
Time Complexity: O(n)
Space Complexity: O(1)
Question 16 
Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h 1 and h 2 . Further suppose our hashing scheme uses h 1 for the odd keys and h 2 for the even keys. What is the expected number of keys in a slot?
m/n  
n/m  
2n/m  
n/2m 
Question 16 Explanation:
For n keys and m elements without any condition the expected number of elements in a slot are n/m.
How?
For 1st element the probability of key1 ends up in slot 1 is 1/m.
For 2nd element the probability of key2 ends up in slot 2 is 1/m
..
..
For nth element the probability of keyn ends up in slot n is 1/m
Hence expected number of elements in a slot is:
1/m+1/m+... (n times)= n/m
In the given question h1 is for elements at even sequence position and h2 is for odd number of sequence positions. This will not affect the overall probability.
Hence here also it is n/m
How?
For 1st element the probability of key1 ends up in slot 1 is 1/m.
For 2nd element the probability of key2 ends up in slot 2 is 1/m
..
..
For nth element the probability of keyn ends up in slot n is 1/m
Hence expected number of elements in a slot is:
1/m+1/m+... (n times)= n/m
In the given question h1 is for elements at even sequence position and h2 is for odd number of sequence positions. This will not affect the overall probability.
Hence here also it is n/m
Question 17 
Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?
DMA based I/O transfer  
Interrupt driven I/O transfer  
Polling based I/O transfer  
Programmed I/O transfer 
Question 17 Explanation:
Explanation: Both the methods of programmed I/O and Interruptdriven I/O require the active intervention of the processor to transfer data between memory and the I/O module, and any data transfer must transverse a path through the processor.
DMA or direct memory access allows the peripherals to directly communicate with each other using the memory buses, removing the intervention of the CPU. Hence it is the fast mode of IO transfer compared to all other methods. In polling, the processor wastes countless processor cycles by repeatedly checking each IO device if it needs attention.
DMA or direct memory access allows the peripherals to directly communicate with each other using the memory buses, removing the intervention of the CPU. Hence it is the fast mode of IO transfer compared to all other methods. In polling, the processor wastes countless processor cycles by repeatedly checking each IO device if it needs attention.
Question 18 
Let R1 and R2 be two 4bit registers that store numbers in 2’s complement form. For the operation R1+R2, which one of the following values of R1 and R2 gives an arithmetic overflow?
R1 = 1011 and R2 = 1110  
R1 = 1100 and R2 = 1010  
R1 = 0011 and R2 = 0100  
R1 = 1001 and R2 = 1111 
Question 18 Explanation:
Question 19 
Consider the following threads, T 1 , T 2 , and T 3 executing on a single processor, synchronized using three binary semaphore variables, S 1 , S 2 , and S 3 , operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.
Which initialization of the semaphores would print the sequence BCABCABCA….?
S 1 = 1; S 2 = 1; S 3 = 1  
S 1 = 1; S 2 = 1; S 3 = 0  
S 1 = 1; S 2 = 0; S 3 = 0  
S 1 = 0; S 2 = 1; S 3 = 1 
Question 19 Explanation:
Explanation: Since B is to be printed first semaphore S1 has to be set to 1, so that the thread enters its critical section and prints B. Then C needs to be printed, this happens when Thread 1 is blocked on semaphore s3 (blocked, s3=0). Then Thread1 invokes Thread 3 to print A.
Question 20 
where tr() represents the trace of a matrix. Which one of the following holds?
Statement 1 is correct and Statement 2 is wrong.  
Statement 1 is wrong and Statement 2 is correct.  
Both Statement 1 and Statement 2 are correct.  
Both Statement 1 and Statement 2 are wrong. 
Question 20 Explanation:
the matrices AB and BA have the same characteristic polynomial, so in particular the same trace, and the same determinant.
(In exam point of view, you can just consider small example and conclude).
So trace of AB = trace of BA
As well
Trace of CD = trace of DC
(In exam point of view, you can just consider small example and conclude).
So trace of AB = trace of BA
As well
Trace of CD = trace of DC
Question 21 
What is printed by the following ANSI C program?
#include
int main(int argc, char *argv[])
{
int x = 1, z[2] = {10, 11};
int *p = NULL;
p = &x;
*p = 10;
p = &z[1];
*(&z[0] + 1) += 3;
printf("%d, %d, %d\n", x, z[0], z[1]);
return 0;
}
#include
int main(int argc, char *argv[])
{
int x = 1, z[2] = {10, 11};
int *p = NULL;
p = &x;
*p = 10;
p = &z[1];
*(&z[0] + 1) += 3;
printf("%d, %d, %d\n", x, z[0], z[1]);
return 0;
}
1, 10, 11  
1, 10, 14  
10, 14, 11  
10, 10, 14 
Question 21 Explanation:
Question 22 
Consider an enterprise network with two Ethernet segments, a web server and a firewall, connected via three routers as shown below.
What is the number of subnets inside the enterprise network?
3  
12  
6  
8 
Question 22 Explanation:
It can be seen as Non equal subneting.
Where router 2 (via Firewall) has the half of the addresses.
Router 1 (via web server) has other half which is further divided into two subnets which is web server and router 3. So total of 3 subnets possible.
Where router 2 (via Firewall) has the half of the addresses.
Router 1 (via web server) has other half which is further divided into two subnets which is web server and router 3. So total of 3 subnets possible.
Question 23 
Which of the following statements is/are TRUE?
Every subset of a recursively enumerable language is recursive.
 
Complement of a contextfree language must be recursive.  
Question 23 Explanation:
Every subset of recursively enumerable need not be recursive. For example (a+b)* is a universal language and regular. Every language over alphabet {a,b} is subset of (a+b)*. This language is regular so it is recursively enumerable also and so many languages are known to be nonrecursive which are definitely subset of (a+b)*. Thus every subset of recursively enumerable need not be recursive.
If L and L(complement) both are recursively enumerable then L must be recursive. It is a theorem.
Every CFL is CSL and CSL is closed under complement so complement of CFL must be CSL and every CSL is recursive. Thus the complement of CFL must be CSL, hence it must be recursive also.
If L1 and L2 are regular then their intersection must be regular, as regular languages are closed under intersection, so L1 intersection L2 must be regular, hence it must be DCFL, since every regular is also a DCFL.
If L and L(complement) both are recursively enumerable then L must be recursive. It is a theorem.
Every CFL is CSL and CSL is closed under complement so complement of CFL must be CSL and every CSL is recursive. Thus the complement of CFL must be CSL, hence it must be recursive also.
If L1 and L2 are regular then their intersection must be regular, as regular languages are closed under intersection, so L1 intersection L2 must be regular, hence it must be DCFL, since every regular is also a DCFL.
Question 24 
Let WB and WT be two set associative cache organizations that use LRU algorithm for cache block replacement. WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?
Each cache block in WB and WT has a dirty bit.  
Every write hit in WB leads to a data transfer from cache to main memory.  
Eviction of a block from WT will not lead to data transfer from cache to main memory  
A read miss in WB will never lead to eviction of a dirty block from WB. 
Question 24 Explanation:
Option A: The given statement is false as cache blocks in WT will not have a dirty bit. Only the cache blocks in WB will have dirty bits associated with them.
Option B: Every write hit in WB need not lead to data transfer from cache to main memory, rather only when that particular block is being evicted there will be transfer from cache to main memory. There can be several write hits in WB before the block is evicted and all those writes will be propagated to the main memory at once. Hence the given statement is false.
Option C: The given statement is true because in WT the writes happen in parallel both in cache and main memory so at the eviction of a block in WT it will not lead to data transfer from cache to main memory.
Option D: A read miss in WB will fetch a new block from main memory and can lead to eviction of a dirty block. Hence the given statement is false.
Option B: Every write hit in WB need not lead to data transfer from cache to main memory, rather only when that particular block is being evicted there will be transfer from cache to main memory. There can be several write hits in WB before the block is evicted and all those writes will be propagated to the main memory at once. Hence the given statement is false.
Option C: The given statement is true because in WT the writes happen in parallel both in cache and main memory so at the eviction of a block in WT it will not lead to data transfer from cache to main memory.
Option D: A read miss in WB will fetch a new block from main memory and can lead to eviction of a dirty block. Hence the given statement is false.
Question 25 
Consider the following three relations in a relational database.
Employee ( eId , Name ), Brand ( bId , bName ), Own ( eId , bId )
Which of the following relational algebra expressions return the set of elds who own all the brands?
Employee ( eId , Name ), Brand ( bId , bName ), Own ( eId , bId )
Which of the following relational algebra expressions return the set of elds who own all the brands?
Question 25 Explanation:
Option (A) returns eid’s which owns every brand of the relation Brand.
In relational algebra, divide (/) is not a basic operator and it can be derived from the basic operators. In option (B), the divide operator is derived using basic operators and which is equivalent to option (A)
In relational algebra, divide (/) is not a basic operator and it can be derived from the basic operators. In option (B), the divide operator is derived using basic operators and which is equivalent to option (A)
Question 26 
Which of the following statements is/are TRUE with respect to deadlocks?
Circular wait is a necessary condition for the formation of deadlock.  
In a system where each resource has more than one instance, a cycle in its waitfor graph indicates the presence of a deadlock.  
If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.  
In the resourceallocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state. 
Question 27 
Which of the following statements is/are TRUE for a group G ?
If the order of G is 2 , then G is commutative.  
If G is commutative, then a subgroup of G need not be commutative. 
Question 27 Explanation:
(A) : True. Circular wait is a necessary condition for the formation of a deadlock.
(B) : False. In a multiple instance graph, a cycle always does not indicate deadlock.
(C) : False. Unsafe state may or may not lead to deadlock.
(D) : True. Since every edge is allocated, that means there are no requests. Hence, cycle is not possible.
(B) : False. In a multiple instance graph, a cycle always does not indicate deadlock.
(C) : False. Unsafe state may or may not lead to deadlock.
(D) : True. Since every edge is allocated, that means there are no requests. Hence, cycle is not possible.
Question 28 
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_____________.
509 
Question 28 Explanation:
Array indices shown beside node
Now, the 3^rd largest number will be at location of max3. We can find what can be the probable index values of max1 at different levels. They will be 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 . . .
∴ 511 is index value of our max1
510 is index value of our max2
509 is index value of our max3
& Hence, Answer is 509
Now, the 3^rd largest number will be at location of max3. We can find what can be the probable index values of max1 at different levels. They will be 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023 . . .
∴ 511 is index value of our max1
510 is index value of our max2
509 is index value of our max3
& Hence, Answer is 509
Question 29 
Consider the augmented grammar with { + , *, (, ), id } as the set of terminals.
5 
Question 29 Explanation:
Question 30 
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
36 
Question 30 Explanation:
We obtain maximum number of edges in a disconnected graph, with one isolated vertex and remaining completely connected.
Given 10 vertices,
Then we can have a complete graph with 9 vertices and one isolated verted.
Number of edges in complete graph with 9 edges is n(n1)/2 = 9*8/2 = 36
Given 10 vertices,
Then we can have a complete graph with 9 vertices and one isolated verted.
Number of edges in complete graph with 9 edges is n(n1)/2 = 9*8/2 = 36
Question 31 
Consider a relation R ( A , B , C , D , E ) with the following three functional dependencies.
AB → C; BC → D; C → E;
The number of superkeys in the relation R is _____________.
8 
Question 31 Explanation:
R(A, B, C, D, E)
AB → C
BC → D
C → E
¯ The attributes A, B are not there in the right hand side of any of the given FDs.
¯ So, AB can be a candidate key.
(AB)^+ = ABCDE
¯ (AB)^+ is deriving all the attributes of R Hence, AB is a candidate key.
¯ The number of super keys possible for R with “AB” candidate kay is:
2^5 – 2 = 2^3
= 8
AB → C
BC → D
C → E
¯ The attributes A, B are not there in the right hand side of any of the given FDs.
¯ So, AB can be a candidate key.
(AB)^+ = ABCDE
¯ (AB)^+ is deriving all the attributes of R Hence, AB is a candidate key.
¯ The number of super keys possible for R with “AB” candidate kay is:
2^5 – 2 = 2^3
= 8
Question 32 
The number of arrangements of six identical balls in three identical bins is______.
7 
Question 32 Explanation:
Given distribution of n identical items into r identical boxes.
As no other condition is given,
We need to consider that distinct distribution will be based on the count of balls.
6 identical balls into 3 identical bins.
That can be done in the combination of
[6,0,0], [5,1,0], [ 4,2,0], [3,3,0], [4,1,1],[3,2,1],[2,2,2]
I.e. in 7 ways
As no other condition is given,
We need to consider that distinct distribution will be based on the count of balls.
6 identical balls into 3 identical bins.
That can be done in the combination of
[6,0,0], [5,1,0], [ 4,2,0], [3,3,0], [4,1,1],[3,2,1],[2,2,2]
I.e. in 7 ways
Question 33 
A cache memory that has a hit rate of 0.8 has an access latency 10 ns and miss penalty 100 ns. An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _____________.
0.85 
Question 33 Explanation:
The initial values are:
h1 = 0.8
t1 = 10 ns
t2 = 100ns
After the optimization the average memory access time remains the same,
Let the new hit rate be h2. The new cache access time is 15ns.
Applying the average access time formula h1t1+(1h1)(t1+t2)
0.8*10+0.2*(10+100) = h2*15+(1h2)(15+100)
30 = 15 + (1h2)*100
1h2 = 0.15
h2 = 0.85
h1 = 0.8
t1 = 10 ns
t2 = 100ns
After the optimization the average memory access time remains the same,
Let the new hit rate be h2. The new cache access time is 15ns.
Applying the average access time formula h1t1+(1h1)(t1+t2)
0.8*10+0.2*(10+100) = h2*15+(1h2)(15+100)
30 = 15 + (1h2)*100
1h2 = 0.15
h2 = 0.85
Question 34 
The value of the following limit is _____________.
1/2 
Question 34 Explanation:
When 0 is substituted, we get 0/0
Apply L Hospital rule
1/2
Question 35 
Consider the resolution of the domain name www.gate.org.in by a DNS resolver. Assume that no resource records are cached anywhere across the DNS servers and that iterative query mechanism is used in the resolution. The number
of DNS queryresponse pairs involved in completely resolving the domain name Is_____________.
3 
Question 35 Explanation:
In the iterative query the DNS resolver go to the following three servers
1.root server, 2. TLD DNS server, 3. authoritative server.
So there will be three pairs of request and response here.
1.root server, 2. TLD DNS server, 3. authoritative server.
So there will be three pairs of request and response here.
Question 36 
Question 36 Explanation:
Question 37 
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3cycles in the graph is given by the trace of
A ^3  
A^ 3 divided by 2  
A ^3 divided by 3  
A ^3 divided by 6 
Question 38 
Which one of the following statements is FALSE?
The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.  
If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.  
The memory access time using a given inverted page table is always same for all incoming virtual addresses.  
In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same. 
Question 38 Explanation:
(A) True: The tlb performs the address search in parallel to memory.
(B) True: TLB hit implies no page fault. Hence, the pageframe will always be in main memory.
(C) False: Inverted page table depends on the size of the process. Hence, the memory access time also varies.
(D) True: Collision resolution techniques are applied. Hence, the each address may take different time.
(B) True: TLB hit implies no page fault. Hence, the pageframe will always be in main memory.
(C) False: Inverted page table depends on the size of the process. Hence, the memory access time also varies.
(D) True: Collision resolution techniques are applied. Hence, the each address may take different time.
Question 39 
Question 39 Explanation:
The given schedule ‘s’ is:
Precedence Graph
T1 → T3 → T4 → T2
Precedence Graph
T1 → T3 → T4 → T2
Question 40 
Consider a digital display system (DDS) shown in the figure that displays the contents of register X. A 16bit code word is used to load a word in X, either from S or from R. S is a 1024word memory segment and R is a 32word register file. Based on the value of mode bit M, T selects an input word to load in X. P and Q interface with the corresponding bits in the code word to choose the addressed word. Which one of the following represents the functionality of P, Q, and T?
P is 10:1 multiplexer; Q is 5:1 multiplexer; T is 2:1 multiplexer  
P is 10:2 ^10 decoder; Q is 5:2^ 5 decoder; T is 2:1 encoder  
P is 10:2^ 10 decoder; Q is 5:2^ 5 decoder; T is 2:1 multiplexer  
P is 1:10 demultiplexer; Q is 1:5 demultiplexer; T is 2:1 multiplexer 
Question 40 Explanation:
P is a 10:2^10 decoder that takes a 10bit address from Saddress as input and enable one of the 1024 words of the S memory.
Q is a 5:2^5 decoder that takes a 5bit address from Raddress as input and enable one of the 32 words of the R memory.
T is a 2x1 Multiplexer that select one of the 2 inputs and transmit it as output.
Q is a 5:2^5 decoder that takes a 5bit address from Raddress as input and enable one of the 32 words of the R memory.
T is a 2x1 Multiplexer that select one of the 2 inputs and transmit it as output.
Question 41 
Consider three floating point numbers A , B and C stored in registers R A , R B and R C , respectively as per IEEE754 single precision floating point format. The 32bit content stored in these registers (in hexadecimal form) are as follows.
Which one of the following is FALSE?
A + C = 0  
C = A + B  
B = 3 C  
( B  C ) > 0 
Question 41 Explanation:
A= 12, B= +36 and C= +12
A+C= 0
B=3C
(BC)>0
C≠A+B
Question 42 
Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?
P = 4, Q = 10, R = 6, S = 2  
P = 2, Q = 9, R = 5, S = 1  
P = 4, Q = 12, R = 5, S = 4  
P = 3, Q = 7, R = 7, S = 3 
Question 42 Explanation:
The Gantt chart can be assumed as :
The combinations of given context switches are possible for options A,B and C. However, we can observe that option D does not follow the context switch. Hence, D is the answer.
The combinations of given context switches are possible for options A,B and C. However, we can observe that option D does not follow the context switch. Hence, D is the answer.
Question 43 
What is printed by the following ANSI C program?
#include
{
int a[3][3][3] =
{{1, 2, 3, 4, 5, 6, 7, 8, 9},
{10, 11, 12, 13, 14, 15, 16, 17, 18},
{19, 20, 21, 22, 23, 24, 25, 26, 27}};
int i = 0, j = 0, k = 0;
for( i = 0; i < 3; i++ ){
for(k = 0; k < 3; k++ )
printf("%d ", a[i][j][k]);
printf("\n");
}
return 0;
}
#include
{
int a[3][3][3] =
{{1, 2, 3, 4, 5, 6, 7, 8, 9},
{10, 11, 12, 13, 14, 15, 16, 17, 18},
{19, 20, 21, 22, 23, 24, 25, 26, 27}};
int i = 0, j = 0, k = 0;
for( i = 0; i < 3; i++ ){
for(k = 0; k < 3; k++ )
printf("%d ", a[i][j][k]);
printf("\n");
}
return 0;
}
1 2 3 10 11 12 19 20 21  
1 4 7 10 13 16 19 22 25  
1 2 3 4 5 6 7 8 9  
1 2 3 13 14 15 25 26 27 
Question 43 Explanation:
Array dimension sizes are 3,3,3 for all 3 dimensions hence, the value assigned to a[3] [3] [3] will be assigned from only first 3 indices i.e. 0^th, 1^st, & 2^nd and 3 dimensions shown by { }
Hence, 1, 2, 3 will be 1^st row
10 , 11, 12 will be 2^nd row
19, 20, 21 will be 3^rd row
Hence, 1, 2, 3 will be 1^st row
10 , 11, 12 will be 2^nd row
19, 20, 21 will be 3^rd row
Question 44 
What is printed by the following ANSI C program?
#include
int main(int argc, char *argv[]){
char a = 'P';
char b = 'x';
char c = (a & b) + '*';
char d = (a  b)  '';
char e = (a ^ b) + '+';
printf("%c %c %c\n", c, d, e);
return 0;
}
#include
int main(int argc, char *argv[]){
char a = 'P';
char b = 'x';
char c = (a & b) + '*';
char d = (a  b)  '';
char e = (a ^ b) + '+';
printf("%c %c %c\n", c, d, e);
return 0;
}
z K S  
122 75 83  
*  +  
P x + 
Question 44 Explanation:
Question 45 
Consider solving the following system of simultaneous equations using LU decomposition.
Question 45 Explanation:
The LU decomposition of the given matrix is
Given,
(Assume x1,x2,x3 as a,b,c)
Given,
(Assume x1,x2,x3 as a,b,c)
Question 46 
Which of the following is/are undecidable?
Given two Turing machines M1and M 2 , decide if L ( M 1 ) L ( M 2 ).  
Given a Turing machine M , decide if L ( M ) is regular.  
Given a Turing machine M , decide if M accepts all strings.  
Given a Turing machine M , decide if M takes more than 1073 steps on every string. 
Question 46 Explanation:
Equality problem of recursively enumerable languages is undecidable, so whether two Turing machines accept the same language is undecidable.
Checking whether a Turing machine accepts a regular language is also undecidable.
Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.
Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.
Checking whether a Turing machine accepts a regular language is also undecidable.
Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.
Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.
Question 47 
L 1 and L 2 are regular.  
L 1 and L 2 are contextfree.  
L 1 is regular and L 2 is contextfree.  
L 1 and L 2 are contextfree but not regular. 
Question 47 Explanation:
Both L1 and L2 are regular.
Since no condition on the value of “n” is mentioned so for a particular case we can assume n=0, now when n=0 the language L1= w =(a+b)*
So if one case is (a+b)* then now even we assume any value of “n” the generated string will already present in (a+b)* thus L1=(a+b)*.
L2: In L2 the middle X can expand and consume all symbols of w except the first symbol and symbols of wr except the last symbol so L2 will be equivalent to language all strings start and end with the same symbol, hence L2 is regular.
Since no condition on the value of “n” is mentioned so for a particular case we can assume n=0, now when n=0 the language L1= w =(a+b)*
So if one case is (a+b)* then now even we assume any value of “n” the generated string will already present in (a+b)* thus L1=(a+b)*.
L2: In L2 the middle X can expand and consume all symbols of w except the first symbol and symbols of wr except the last symbol so L2 will be equivalent to language all strings start and end with the same symbol, hence L2 is regular.
Question 48 
Consider the following languages:
L 1 is not contextfree but L 2 and L 3 are deterministic contextfree.  
Neither L 1 nor L 2 is contextfree.  
Neither L 1 nor its complement is contextfree. 
Question 48 Explanation:
L1=ww is a wellknown CSL (nonCFL) and its complement is CFL.
L2={an bn cm  m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn  m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn  n >=0} so this is CSL (nonCFL).
So A is a true statement and rest all are false statements.
L2={an bn cm  m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn  m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn  n >=0} so this is CSL (nonCFL).
So A is a true statement and rest all are false statements.
Question 49 
Consider a simple undirected weighted graph G , all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?
The edge with the second smallest weight is always part of any minimum spanning tree of G .  
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G .  
G can have multiple minimum spanning trees. 
Question 49 Explanation:
Let assume the graph and minimum spanning tree of the corresponding graph.
OptionA: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.
The second smallest weight is always in MST because it will not form a cycle.
OptionB: FALSE: As per the above graph, the third minimum edge weight is not part of the MST.
The third or fourth edge weight may be part of the cycle. So, it may or may not be in MST.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
OptionA: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.
The second smallest weight is always in MST because it will not form a cycle.
OptionB: FALSE: As per the above graph, the third minimum edge weight is not part of the MST.
The third or fourth edge weight may be part of the cycle. So, it may or may not be in MST.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
Question 50 
The following simple undirected graph is referred to as the Peterson graph.
Which of the following statements is/are TRUE?
Which of the following statements is/are TRUE?
The chromatic number of the graph is 3.  
The graph has a Hamiltonian path  
The following graph is isomorphic to the Peterson graph.  
The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.) 
Question 50 Explanation:
Chromatic number is 3.
Peterson graph ihas hamiltonian path but not hamiltonian cycle
Given graph in option C is isomorphic as the given has same number of vertice, edges, degree sequence and cycles.
LArgest independent set can be more than 3
Peterson graph ihas hamiltonian path but not hamiltonian cycle
Given graph in option C is isomorphic as the given has same number of vertice, edges, degree sequence and cycles.
LArgest independent set can be more than 3
Question 51 
Consider the following recurrence:
Then, which of the following statements is/are TRUE?
Then, which of the following statements is/are TRUE?
f (2^ n 1) 2^ n 1  
f (2 ^n ) 1  
f (5 . 2 ^n ) 2^ n + 1 1  
f (2^ n + 1) 2 ^n + 1 
Question 51 Explanation:
We can solve this problem by eliminating options. Substitute n=1024
Based on the “n” value we can get OptionA, B and C are correct.
Based on the “n” value we can get OptionA, B and C are correct.
Question 52 
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
The diagonal entries of A 2 are the degrees of the vertices of the graph.  
If the graph is connected, then none of the entries of A^ n + 1 + I n can be zero.  
If the sum of all the elements of A is at most 2( n 1), then the graph must be acyclic.  
If there is at least a 1 in each of A ’s rows and columns, then the graph must be Connected. 
Question 52 Explanation:
IF A is adjacency matrix, then in the matrix A*A = A^2 we have
The entries aii show the number of 2length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3length paths between the nodes i and j.
In A^n1 + I n, we will have at least n1 length paths, so there is no possibility of zero entires
The entries aii show the number of 2length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3length paths between the nodes i and j.
In A^n1 + I n, we will have at least n1 length paths, so there is no possibility of zero entires
Question 53 
Which of the following is/are the eigenvector(s) for the matrix given below?
Question 53 Explanation:
Question 54 
Consider a system with 2 KB direct mapped data cache with a block size of 64 bytes. The system has a physical address space of 64 KB and a word length of 16 bits. During the execution of a program, four data words P, Q, R, and S are accessed in that order 10 times (i.e., PQRSPQRS…). Hence, there are 40 accesses to data cache altogether. Assume that the data cache is initially empty and no other data words are accessed by the program. The addresses of the first bytes of P, Q, R, and S are 0xA248, 0xC28A, 0xCA8A, and 0xA262, respectively. For the execution of the above program, which of the following statements is/are TRUE with respect to the data cache?
Every access to S is a hit.  
Once P is brought to the cache it is never evicted.  
At the end of the execution only R and S reside in the cache.  
Every access to R evicts Q from the cache. 
Question 54 Explanation:
Cache size = 2KB = 2^11 bytes
Block size = 64 bytes = 2^6 bytes, we need 6 bits OFFSET to identify each byte in the block.
No. of blocks in the cache = 2^11 / 2^6 = 2^5, since it is a direct mapped cache we need 5 bits in the physical address to identify the LINE number.
Each word is 16 bits long = 2 bytes.
Number of words in each block = 64/2 = 32 words.
The physical memory is 64KB = 2^16 bytes, so the physical address is 16 bits.
In direct mapped cache the physical address is divided into (TAG, LINE, OFFSET)
In the 16 bits physical address OFFSET is 6 bits and LINE number is 5 bits, so there are 5 TAG bits.
The given physical addresses of P, Q, R, S can be written in binary as below (each hexadecimal digit represents 4 binary digits):
P: 0xA248 (10100 01001 001000 )
Q: 0xC28A (11000 01010 001010)
R: 0xCA8A (11001 01010 001010)
S: 0xA262 (10100 01001 100010)
Here P is mapped to line number 9 in the cache. S also is mapped to line number 9 and not only that they both are from the same block as even the TAG bits are matching. So, even the first access of S will be a hit as it gets prefetched along with P. Once P is fetched it is never evicted.
Both Q and R are mapped to line number 10 in the cache. But they are from different blocks as the TAG bits are different. Since it is a direct mapped cache, every access of R evicts Q from the cache.
Hence options A, B, D are true. Option C is false as at the end of execution P, R, S are in the cache not just R, S.
Block size = 64 bytes = 2^6 bytes, we need 6 bits OFFSET to identify each byte in the block.
No. of blocks in the cache = 2^11 / 2^6 = 2^5, since it is a direct mapped cache we need 5 bits in the physical address to identify the LINE number.
Each word is 16 bits long = 2 bytes.
Number of words in each block = 64/2 = 32 words.
The physical memory is 64KB = 2^16 bytes, so the physical address is 16 bits.
In direct mapped cache the physical address is divided into (TAG, LINE, OFFSET)
In the 16 bits physical address OFFSET is 6 bits and LINE number is 5 bits, so there are 5 TAG bits.
The given physical addresses of P, Q, R, S can be written in binary as below (each hexadecimal digit represents 4 binary digits):
P: 0xA248 (10100 01001 001000 )
Q: 0xC28A (11000 01010 001010)
R: 0xCA8A (11001 01010 001010)
S: 0xA262 (10100 01001 100010)
Here P is mapped to line number 9 in the cache. S also is mapped to line number 9 and not only that they both are from the same block as even the TAG bits are matching. So, even the first access of S will be a hit as it gets prefetched along with P. Once P is fetched it is never evicted.
Both Q and R are mapped to line number 10 in the cache. But they are from different blocks as the TAG bits are different. Since it is a direct mapped cache, every access of R evicts Q from the cache.
Hence options A, B, D are true. Option C is false as at the end of execution P, R, S are in the cache not just R, S.
Question 55 
Consider routing table of an organization’s router shown below:
Which of the following prefixes in CIDR notation can be collectively used to correctly aggregate all of the subnets in the routing table?
Which of the following prefixes in CIDR notation can be collectively used to correctly aggregate all of the subnets in the routing table?
12.20.164.0/20  
12.20.164.0/22  
12.20.164.0/21  
12.20.168.0/22 
Question 55 Explanation:
Do bit wise and with the given subnet and subnets mask then compare to given choices IP address range.
Question 56 
Consider the relational database with the following four schemas and their respective instances.
Student(sNo, sName, dNo) Dept(dNo, dName)
Course(cNo, cName, dNo)
Register(sNo, cNo)
The number of rows returned by the above SQL query is___________.
Student(sNo, sName, dNo) Dept(dNo, dName)
Course(cNo, cName, dNo)
Register(sNo, cNo)
The number of rows returned by the above SQL query is___________.
2 
Question 56 Explanation:
Final result of the given SQL query is:
+++
 sNo  sName  dNo 
++++
 S01  James  D01 
 S04  Jane  D01 
++++
+++
 sNo  sName  dNo 
++++
 S01  James  D01 
 S04  Jane  D01 
++++
Question 57 
Consider a network with three routers P, Q, R shown in the figure below. All the links have cost of unity.
The routers exchange distance vector routing information and have converged on the routing tables, after which the link Q−R fails. Assume that P and Q send out routing updates at random times, each at the same average rate. The probability of a routing loop formation (rounded off to one decimal place) between P and Q, leading to counttoinfinity problem, is___________.
The routers exchange distance vector routing information and have converged on the routing tables, after which the link Q−R fails. Assume that P and Q send out routing updates at random times, each at the same average rate. The probability of a routing loop formation (rounded off to one decimal place) between P and Q, leading to counttoinfinity problem, is___________.
1 
Question 57 Explanation:
If asked for R, Probablity = 1
If asked for R, from among P, Q, R
Probability = 1 /3
If asked for R, from among P, Q, R
Probability = 1 /3
Question 58 
Let G ( V , E ) be a directed graph, where V = {1, 2,3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A .
24 
Question 58 Explanation:
Graph have 2 elements > We get 1 MST
Graph have 3 elements > We get 2 MSTs
Graph have 4 elements > We get 6 MSTs (3*2*1)
Graph have 5 elements > We get 24 MSTs(4*3*2*1)
Graph have 3 elements > We get 2 MSTs
Graph have 4 elements > We get 6 MSTs (3*2*1)
Graph have 5 elements > We get 24 MSTs(4*3*2*1)
Question 59 
Consider a 100 Mbps link between an earth station (sender) and a satellite (receiver) at an altitude of 2100 km. The signal propagates at a speed of 3x10 8 m/s. The time taken (in milliseconds, rounded off to two decimal places) for the receiver to completely receive a packet of 1000 bytes transmitted by the sender is_________
7.08 ms 
Question 59 Explanation:
The time required for the receiver to receive the packet is transmission time + propagation time i.e. Tt +Tp
Tt = L / B => 1000 x 8 bits / 10^8 bps = 0.08 ms
Tp = D / V => 2100 x 1000 m / 3 x10^8 ms = 7 ms
Therefore, Total time = 7.08 ms
Tt = L / B => 1000 x 8 bits / 10^8 bps = 0.08 ms
Tp = D / V => 2100 x 1000 m / 3 x10^8 ms = 7 ms
Therefore, Total time = 7.08 ms
Question 60 
Consider the data transfer using TCP over a 1 Gbps link. Assuming that the maximum segment lifetime (MSL) is set to 60 seconds, the minimum number of bits required for the sequence number field of the TCP header, to prevent the sequence number space from wrapping around during the MSL is____________.
33 
Question 60 Explanation:
Bandwidth = 1Gbps =2^30 / 8 bps
1 sec = 20^30 / 8 bytes
=> 1 sec = 20^30 / 8 sequence number
=> 60 sec =20^30 x 60 / 8 bytes
Number of sequence bits required = log (20^30 x 60 / 8) => 33
1 sec = 20^30 / 8 bytes
=> 1 sec = 20^30 / 8 sequence number
=> 60 sec =20^30 x 60 / 8 bytes
Number of sequence bits required = log (20^30 x 60 / 8) => 33
Question 61 
A processor X 1 operating at 2 GHz has a standard 5stage RISC instruction pipeline having a base CPI (cycles per instruction) of one without any pipeline hazards. For a given program P that has 30% branch instructions, control hazards incur 2 cycles stall for every branch. A new version of the processor X 2 operating at same clock frequency has an additional branch predictor unit (BPU) that completely eliminates stalls for correctly predicted branches. There is neither any savings nor any additional stalls for wrong predictions. There are no structural hazards and data hazards for X 1 and X 2 . If the BPU has a prediction accuracy of 80%, the speed up (rounded off to two decimal places) obtained by X 2 over X 1 in executing P is____________.
1.43 
Question 61 Explanation:
The effective CPI in X1 : (1+Stall frequency * No. of stall cycles)
It is given that there are 30% branch instructions and each branch instruction causes 2 stall cycles.
= 1+0.3*2 = 1.6
In X2 there is a branch predictor which predicts correctly 80% of the time. Only in 20% cases the prediction is wrong. So, out of the 30% of branch instructions only 20% of them now lead to stalls.
The effective CPI in X2 : (1+Stall frequency * No. of stall cycles) = (1+0.3*0.2*2) = 1.12
Since the processor speed remains the same, the clock cycle time also doesn’t change. Hence speedup of X2 over X1 : 1.6/1.12 = 1.43
It is given that there are 30% branch instructions and each branch instruction causes 2 stall cycles.
= 1+0.3*2 = 1.6
In X2 there is a branch predictor which predicts correctly 80% of the time. Only in 20% cases the prediction is wrong. So, out of the 30% of branch instructions only 20% of them now lead to stalls.
The effective CPI in X2 : (1+Stall frequency * No. of stall cycles) = (1+0.3*0.2*2) = 1.12
Since the processor speed remains the same, the clock cycle time also doesn’t change. Hence speedup of X2 over X1 : 1.6/1.12 = 1.43
Question 62 
Consider the queues Q 1 containing four elements and Q 2 containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q,element) and Dequeue(Q). The minimum number of Enqueue operations on Q 1 required to place the elements of Q 1 in Q 2 in reverse order (shown as the Final State in the figure) without using any additional storage is___________.
6 
Question 62 Explanation:
Count Q1 enqueue
Question 63 
Consider two files systems A and B , that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in A and also in B. Now, consider inserting a new block in the middle of the file (between 50 th and 51 st block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in A and B are n A and n B , respectively, then the value of n A + n B is_________.
102 
Question 63 Explanation:
Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory.
For linked allocation we have to trace the first 51 blocks, which requires 51 disk accesses. Similarly for contiguous allocation we have to move the block number 50100 after insertion of a new block, which takes 51 accesses. Hence, the answer is 51+51 = 102.
For linked allocation we have to trace the first 51 blocks, which requires 51 disk accesses. Similarly for contiguous allocation we have to move the block number 50100 after insertion of a new block, which takes 51 accesses. Hence, the answer is 51+51 = 102.
Question 64 
Consider a demand paging system with four page frames (initially empty) and LRU page replacement policy. For the following page reference string
7, 2, 7, 3, 2, 5,3, 4, 6, 7, 7,1, 5, 6,1
the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is_________.
7, 2, 7, 3, 2, 5,3, 4, 6, 7, 7,1, 5, 6,1
the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is_________.
0.60 
Question 64 Explanation:
We have a total of 9 page faults using LRU page replacement algorithm with on demand paging. Out of 15 references, 9 page faults implies the page fault rate is 9/16 = 0.60.
Question 65 
Consider the following grammar along with translation rules.
80 
Question 65 Explanation:
There are 65 questions to complete.