GATE 2020
Question 1 
Two straight lines are drawn perpendicular to each other in XY plane. If α and β are the acute angles the straight lines make with the Xaxis, then α+β is ______.
60°  
120°  
180°
 
90° 
Question 1 Explanation:
We know a + α + β = 180
α + β = 180  90
α + β = 90
Question 2 
The total revenue of a company during 20142018 is shown in the bar graph. If the total expenditure of the company in each year is 500 million rupees, then the aggregate profit or loss (in percentage) on the total expenditure of the company during 20142018 is ______.
20% profit
 
20% loss  
16.67% loss
 
16.67% profit

Question 2 Explanation:
Bargraph:
20142018
Total expenditure = 500 million/year = 500 × 5 = 2500 million
Revenue total (from the graph)
= 400 + 500 + 600 + 700 + 800
= 3000 million
Profit = 3000  2500 = 500
⟹ 500/2500 = 20% profit
20142018
Total expenditure = 500 million/year = 500 × 5 = 2500 million
Revenue total (from the graph)
= 400 + 500 + 600 + 700 + 800
= 3000 million
Profit = 3000  2500 = 500
⟹ 500/2500 = 20% profit
Question 3 
The figure below shows an annular ring with outer and inner radii as b and a, respectively. The annular space has been painted in the form of blue colour circles touching the outer and inner periphery of annular space. If maximum n number of circles can be painted, then the unpainted area available in annular space is ______.
Question 3 Explanation:
Area of nonpainted between 2 circles area of part 1 = πb^{2}  πa^{2} = π(b^{2}  a^{2})
Radius of painted circles = ba/2
Area of painted circle = π(ba/2)^{2}
For n circles = nπ(ba/2)^{2}
Nonpainted area = π[b^{2}  a^{2} n/4(b  a)^{2}]
Question 4 
Goods and Services Tax (GST) is an indirect tax introduced in India in 2017 that is imposed on the supply of goods and services, and it subsumes all indirect taxes except few. It is a destinationbased tax imposed on goods and services used, and it is not imposed at the point of origin from where goods come. GST also has a few components specific to state governments, central government and Union Territories (UTs).
Which one of the following statements can be inferred from the given passage?
GST includes all indirect taxes.  
GST is imposed at the point of usage of goods and services.  
GST does not have a component specific to UT.
 
GST is imposed on the production of goods and services.

Question 4 Explanation:
GST is imposed at the point of usage of goods and services.
Question 5 
Select the word that fits the analogy:
Cook : Cook :: Fly : _____
Flyer
 
Flying
 
Flew
 
Flighter

Question 5 Explanation:
Cookcook  Nounverb relation
FlyFlyer
FlyFlyer
Question 6 
The drawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for fresh water. The UN climate report estimates that without deep cuts to manmade emissions, at least 30% of the northern hemisphere’s surface permafrost could melt by the end of the century. Given this situation of imminent global exodus of billions of people displaced by rising seas, nationstates need to rethink their carbon footprint for political concerns, if not for environmental ones.
Which one of the following statements can be inferred from the given passage>
Nationstates are responsible for providing fresh water to billions of people.
 
Billions of people are affected by melting glaciers.
 
Nationstates do not have environmental concerns.  
Billions of people are responsible for manmade emissions.

Question 6 Explanation:
Billions of people are affected by melting glaciers.
Question 7 
There are multiple routes to reach from node 1 to node 2, as shown in the network.
The cost of travel on an edge between two nodes is given in rupees. Nodes ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, and ‘f’ are toll booths. The toll price at toll booths marked ‘a’ and ‘e’ is Rs.200, and is Rs.100 for the other toll booths. Which is the cheapest route from node 1 to node 2?
1fe2
 
1fb2
 
1b2
 
1ac2

Question 7 Explanation:
1  f  e  2 ─ 100 + 100 + 200 = 400
1  f  b  2 ─ 100 + 0 + 200 = 300 ⇾ shortest [Answer]
1  b  2 ─ 300 + 200 = 500
1  a  c ─ 2  200 + 100 + 100 = 400
1  f  b  2 ─ 100 + 0 + 200 = 300 ⇾ shortest [Answer]
1  b  2 ─ 300 + 200 = 500
1  a  c ─ 2  200 + 100 + 100 = 400
Question 8 
Raman is confident of speaking English _____ six months as he has been practising regularly_____the last three weeks.
for, in
 
during, for  
for, since
 
within, for

Question 9 
If P = 3, R = 27, T = 243, then Q+S = ______.
80  
110  
40  
90 
Question 9 Explanation:
P=3, R=27, T=243, Q+5=?
P=3^{1}, Q=3^{2}, R=3^{3}, S=3^{4}, T=3^{5}
Q+S = 3^{2}+3^{4} = 9+81 = 90
P=3^{1}, Q=3^{2}, R=3^{3}, S=3^{4}, T=3^{5}
Q+S = 3^{2}+3^{4} = 9+81 = 90
Question 10 
His knowledge of the subject was excellent but his classroom performance was ______.
good
 
praiseworthy
 
extremely poor
 
desirable

Question 10 Explanation:
A Contrast is indicated in the above sentence
Question 11 
Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.
7 
Question 11 Explanation:
Lagrange’s Theorem:
If ‘H” is a subgroup of finite group (G,*) then O(H) is the divisor of O(G).
Given that the order of group is 35. Its divisors are 1,5,7,35.
It is asked that the size of largest possible subgroup other than G itself will be 7.
If ‘H” is a subgroup of finite group (G,*) then O(H) is the divisor of O(G).
Given that the order of group is 35. Its divisors are 1,5,7,35.
It is asked that the size of largest possible subgroup other than G itself will be 7.
Question 12 
Consider a relational database containing the following schemas.
The primary key of each table is indicated by underlying the constituent fields.
SELECT s.sno, s.sname
FROM Suppliers s, Catalogue c
WHERE s.sno = c.sno AND
Cost > (SELECT AVG (cost)
FROM Catalogue
WHERE pno = ‘P4’
GROUP BY pno);
The number of rows returned by the above SQL query is
0  
5  
4  
2 
Question 12 Explanation:
The inner query “select avg(cost) from catalogue where pno='P4' group by pno;” returns:
AVG(COST)

225
The outer query “select s.sno,s.sname from suppliers s, catalogue c where s.sno=c.sno” returns:
SNO SNAME

S1 M/s Royal furniture
S1 M/s Royal furniture
S1 M/s Royal furniture
S2 M/s Balaji furniture
S2 M/s Balaji furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
So, the final result of the query is:
SN SNAME

S2 M/s Balaji furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
Therefore, 4 rows will be returned by the query.
AVG(COST)

225
The outer query “select s.sno,s.sname from suppliers s, catalogue c where s.sno=c.sno” returns:
SNO SNAME

S1 M/s Royal furniture
S1 M/s Royal furniture
S1 M/s Royal furniture
S2 M/s Balaji furniture
S2 M/s Balaji furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
So, the final result of the query is:
SN SNAME

S2 M/s Balaji furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
S3 M/s Premium furniture
Therefore, 4 rows will be returned by the query.
Question 13 
Consider the language
and the following statements.
 L is deterministic contextfree.
 L is contextfree but not deterministic contextfree.
 L is not LL(k) for any k.
2 only
 
3 only
 
1 only
 
1 and 3 only

Question 13 Explanation:
L is DCFL.
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
Question 15 
Consider the following statements.
I.If L1L2is regular, then both L1and L2 must be regular.
II.The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
I.If L1L2is regular, then both L1and L2 must be regular.
II.The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
Both I and II  
II only  
Neither I nor II
 
I only 
Question 15 Explanation:
Statement I is wrong. Assume L1= {an bn  n>0} and L2= complement of L1
L1 and L2 both are DCFL but not regular, but L1 U L2 = (a+b)* which is regular.
Hence even though L1 U L2 is regular , L1 and L2 need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L1= {ab}
L2={aabb}
L3={aaabbb}
.
.
.
.
L100={a^100 b^100}
.
If we take infinite union of all above languages i.e,
{L1 U L2 U ……….L100 U ……} then we will get a new language L={a^n b^n  n>0}, which is not regular. Hence regular languages are not closed under infinite UNION.
L1 and L2 both are DCFL but not regular, but L1 U L2 = (a+b)* which is regular.
Hence even though L1 U L2 is regular , L1 and L2 need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L1= {ab}
L2={aabb}
L3={aaabbb}
.
.
.
.
L100={a^100 b^100}
.
If we take infinite union of all above languages i.e,
{L1 U L2 U ……….L100 U ……} then we will get a new language L={a^n b^n  n>0}, which is not regular. Hence regular languages are not closed under infinite UNION.
Question 16 
Consider the following statements.
 Daisy chaining is used to assign priorities in attending interrupts.
 When a device raises a vectored interrupt, the CPU does polling to identify the source of the interrupt.
 In polling, the CPU periodically checks the status bits to know if any device needs its attention.
 During DMA, both the CPU and DMA controller can be bus masters at the same time.
I and IV only
 
I and II only
 
III only  
I and III only

Question 16 Explanation:
StatementI is true as daisy chaining is used to assign priorities in attending interrupts.
StatementII is false as vectored interrupt doesn’t involve polling but nonvectored interrupt involves polling.
StatementIII is true as polling means that CPU periodically checks the status bits to know if any device needs attention.
StatementIV is false as during DMA only one of the CPU or DMA can be bus master at a time.
StatementII is false as vectored interrupt doesn’t involve polling but nonvectored interrupt involves polling.
StatementIII is true as polling means that CPU periodically checks the status bits to know if any device needs attention.
StatementIV is false as during DMA only one of the CPU or DMA can be bus master at a time.
Question 17 
A direct mapped cache memory of 1 MB has a block ize of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss, it takes 20 ns to bring the first word of a block from the main memory, while each subsequent word takes 5 ns. The word size is 64 bits. The average memory access time in ns (round off to 1 decimal place) is _____.
13.5 
Question 17 Explanation:
Cache access time = 3 ns
Hit ratio of cache=0.94
Word size is 64 bits = 8 bytes.
Cache line size = 256 bytes = 32 words
Main memory access time=20ns(time for first word)+155ns(time for remaining 31 words, 31*5=155ns) = 175 ns
Average access time = h1*t1+(1h1)(t1+t2) = t1+(1h1)t2
⇒ 3+(0.06)(175) = 13.5 ns
Hit ratio of cache=0.94
Word size is 64 bits = 8 bytes.
Cache line size = 256 bytes = 32 words
Main memory access time=20ns(time for first word)+155ns(time for remaining 31 words, 31*5=155ns) = 175 ns
Average access time = h1*t1+(1h1)(t1+t2) = t1+(1h1)t2
⇒ 3+(0.06)(175) = 13.5 ns
Question 18 
Let R be the set of all binary relations on the set {1,2,3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is _____.
0.125 
Question 18 Explanation:
For a set with n elements,
The number of reflexive relations is 2^(n^2n).
The total number of relations on a set with n elements is 2^ (n^2).
The probability of choosing the reflexive relation out of set of relations i s = 2^(n^2n) /2^ (n^2) = 2^( n^2n n^2) = 2^(n)
Given n=3, the probability will be 2^(n) = ⅛ = 0.125
The number of reflexive relations is 2^(n^2n).
The total number of relations on a set with n elements is 2^ (n^2).
The probability of choosing the reflexive relation out of set of relations i s = 2^(n^2n) /2^ (n^2) = 2^( n^2n n^2) = 2^(n)
Given n=3, the probability will be 2^(n) = ⅛ = 0.125
Question 19 
Which one of the following is used to represent the supporting manyone relationships of a weak entity set in an entityrelationship diagram?
Ovals that contain underlined identifiers
 
Rectangles with double/bold border
 
Diamonds with double/bold border
 
Ovals with double/bold border

Question 19 Explanation:
An entity set that does not have sufficient attributes to form a primary key is termed as a weak entity and an entity set that has a primary key is termed as strong entity set. For a weak entity set to be meaningful, it must be associated with another entity set, called identifying or owner entity set. The relationship associating the weak entity set with the identifying entity set is called the identifying relationship and it is represented by double diamond. The identifying relationship is manytoone from the weak entity set to the identifying entity set and the participation of weak entity set in the relationship is total.
Question 20 
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?
The hole created by worst fit is always larger than the hole created by first fit.
 
The hole created by best fit is never larger than the hole created by first fit.
 
The hole created by first fit is always larger than the hole created by next fit.  
The hole created by next fit is never larger than the hole created by best fit.

Question 20 Explanation:
The size of hole created using best fit is never greater than size created by first fit. The best fit chooses the smallest available partition to fit the size of the process. Whereas, first fit and next fit doesn’t consider the size of the holes available.
Question 21 
Consider the following grammar.
S>aSB d
B>b
The number of reduction steps taken by a bottomup parser while accepting the string aaadbbb is _______.
S>aSB d
B>b
The number of reduction steps taken by a bottomup parser while accepting the string aaadbbb is _______.
7 
Question 21 Explanation:
7 reductions total.
Question 22 
Consider the following statements about process state transitions for a system using preemptive scheduling.
I. A running process can move to ready state.
II. A ready process can move to ready state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.
Which of the above statements are TRUE?
I. A running process can move to ready state.
II. A ready process can move to ready state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.
Which of the above statements are TRUE?
II and III only
 
I, II and III only
 
I, II, III and IV
 
I, II and IV only

Question 22 Explanation:
Question 23 
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder traversal of the tree?
Which one of the following is the postorder traversal of the tree?
20, 19, 18, 16, 15, 12, 11, 10
 
11, 12, 10, 16, 19, 18, 20, 15
 
10, 11, 12, 15, 16, 18, 19, 20  
19, 16, 18, 20, 11, 12, 10, 15 
Question 23 Explanation:
Question 24 
A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The minimum number of select lines needed for the multiplexer is _____.
5 
Question 24 Explanation:
Number of registers is 32. Only one register has to be selected at any instant of time.
A 2^{5}x1 Multiplexer with 5 select lines selects one of the 32(= 2^{5} )registers at a time depending on the selection input.
The content from the selected register will be transferred through the output line to the Accumulator.
A 2^{5}x1 Multiplexer with 5 select lines selects one of the 32(= 2^{5} )registers at a time depending on the selection input.
The content from the selected register will be transferred through the output line to the Accumulator.
Question 25 
Consider a double hashing scheme in which the primary hash function is h_{1}(k)=k mod 23, and the secondary hash function is h_{2}(k)=1+(k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is _______.
13 
Question 25 Explanation:
• Probe sequence is the list of locations which a method for open addressing produces as alternatives in case of a collision.
• K=90
• h_{1}(k)= k mod 23 = 90 mod 23 =21
• In case of collision , we need to use secondary hash function
• h_{2}(k)=1+(k mod19)=1+90mod19=1+14 =15
• Now (21+15) mod 23 =36 mod 23 =13
• So the address is 13
• K=90
• h_{1}(k)= k mod 23 = 90 mod 23 =21
• In case of collision , we need to use secondary hash function
• h_{2}(k)=1+(k mod19)=1+90mod19=1+14 =15
• Now (21+15) mod 23 =36 mod 23 =13
• So the address is 13
Question 26 
Consider the functions
Which of the above functions is/are increasing everywhere in [0,1]?
Which of the above functions is/are increasing everywhere in [0,1]?
II and III only
 
III only
 
II only
 
I and III only

Question 26 Explanation:
Question 27 
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
option A and option B 
Question 27 Explanation:
Method1:
When we are inserting an element in to empty linked list and to perform sorted order list of every element will take O(n^2)
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case.
After inserting elements into an empty linked list we have to perform sorting operation.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only.
Let head be the first node of the linked list to be sorted and head Reference be the pointer to head. The head in MergeSort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^2) and heap sort will not be suitable to apply.
Method2:
When we are inserting an element into an empty linked list and to perform a sorted list after inserting all elements will take O(nlogn) time.
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case. After inserting elements into an empty linked list we have to perform sorting operations.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only. Let head be the first node of the linked list to be sorted and head Reference be the pointer to head. The head in Merge Sort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^2) and heap sort will not be suitable to apply.
Note: They are given “needs to be maintained in sorted order” but not given clear conditions to sort an elements.
When we are inserting an element in to empty linked list and to perform sorted order list of every element will take O(n^2)
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case.
After inserting elements into an empty linked list we have to perform sorting operation.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only.
Let head be the first node of the linked list to be sorted and head Reference be the pointer to head. The head in MergeSort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^2) and heap sort will not be suitable to apply.
Method2:
When we are inserting an element into an empty linked list and to perform a sorted list after inserting all elements will take O(nlogn) time.
Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case. After inserting elements into an empty linked list we have to perform sorting operations.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only. Let head be the first node of the linked list to be sorted and head Reference be the pointer to head. The head in Merge Sort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n^2) and heap sort will not be suitable to apply.
Note: They are given “needs to be maintained in sorted order” but not given clear conditions to sort an elements.
Question 28 
Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in nonpersistent mode. The web page contains text and five very small images. The minimum number of TCP connections required to display the web page completely in your browser is ______.
6 
Question 28 Explanation:
In nonpersistent HTTP connection for every object, there is a TCP connection established. Therefore, 1 TCP connection for text and 5 TCP connections for images required.
Hence, 1 Text + 5 Image = 6 Objects
Hence, 1 Text + 5 Image = 6 Objects
Question 29 
Consider the following C program.
#include
int main () {
int a [4] [5] = {{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}};
printf (“%d\n”, *(* (a+**a+2) +3));
return (0);
}
The output of the program is _______.
#include
int main () {
int a [4] [5] = {{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20}};
printf (“%d\n”, *(* (a+**a+2) +3));
return (0);
}
The output of the program is _______.
19 
Question 29 Explanation:
Check out the step by step program and its output in the comment:
#include
int main()
{
int a[4][5] = { {1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20}
};
printf("%d\n",a); //880 (consider base address = 880)
printf("%d\n",*a); //880
printf("%d\n",**a); //1
printf("%d\n",**a+2); //3
printf("%d\n",a+**a+2); //940
printf("%d\n",*(a+**a+2));//940
printf("%d\n",*(a+**a+2)+3);//952
printf("%d\n",*(*(a+**a+2)+3));//19
return 0;
}
#include
int main()
{
int a[4][5] = { {1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20}
};
printf("%d\n",a); //880 (consider base address = 880)
printf("%d\n",*a); //880
printf("%d\n",**a); //1
printf("%d\n",**a+2); //3
printf("%d\n",a+**a+2); //940
printf("%d\n",*(a+**a+2));//940
printf("%d\n",*(a+**a+2)+3);//952
printf("%d\n",*(*(a+**a+2)+3));//19
return 0;
}
Question 30 
Consider the following data path diagram.
Consider an instruction: R0 ← R1 + R2. The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The subscripts r and w indicate read and write operations, respectively.
Which one of the following is the correct order of execution of the above steps?
Consider an instruction: R0 ← R1 + R2. The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The subscripts r and w indicate read and write operations, respectively.
Which one of the following is the correct order of execution of the above steps?
3, 5, 1, 2, 4  
3, 5, 2, 1, 4
 
1, 2, 4, 3, 5
 
2, 1, 4, 5, 3

Question 30 Explanation:
To execute the given instruction R0 < R1 + R2,
First the PC value has to be moved into MAR (step3 from the given sequence),
then the instruction has to be fetched(step5 from the given sequence).
then Temp1 is loaded with the value of R1 (step2 from the given sequence),
then the addition operation is performed by accessing the R2 value directly and adding it to Temp1 value and storing the result in Temp2 (step1 from the given sequence).
Finally the result from Temp2 is stored in R0 (step4 from the given sequence).
Hence the correct sequence is (3, 5, 2, 1, 4).
First the PC value has to be moved into MAR (step3 from the given sequence),
then the instruction has to be fetched(step5 from the given sequence).
then Temp1 is loaded with the value of R1 (step2 from the given sequence),
then the addition operation is performed by accessing the R2 value directly and adding it to Temp1 value and storing the result in Temp2 (step1 from the given sequence).
Finally the result from Temp2 is stored in R0 (step4 from the given sequence).
Hence the correct sequence is (3, 5, 2, 1, 4).
Question 31 
Consider the following statements.
I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the runtime environment.
III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.
Which of the above statements is/are TRUE?
I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the runtime environment.
III. Errors violating the condition ‘any variable must be declared before its use’ are detected during syntax analysis.
Which of the above statements is/are TRUE?
II only  
I only
 
I and III only
 
None of I, II and III

Question 31 Explanation:
I is wrong as Symbol table is also accessed during semantic analysis phase.
II is wrong as compilers which supports recursion require stack memory in run time environment.
III is wrong “any variable must be declared before its use” is a semantic error and nit syntax error.
II is wrong as compilers which supports recursion require stack memory in run time environment.
III is wrong “any variable must be declared before its use” is a semantic error and nit syntax error.
Question 32 
If there are m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m + n is ____.
1034 
Question 32 Explanation:
The size of the decoder required is 10x 210i.e 10x 1024.
Each output line of the decoder is connected to one of the 1K(= 1024) rows of RAM.
Each row stores 1 Byte.
m=10 and n=1024
Each output line of the decoder is connected to one of the 1K(= 1024) rows of RAM.
Each row stores 1 Byte.
m=10 and n=1024
Question 33 
What is the worst case time complexity of inserting n^{2} elements into an AVLtree with n elements initially?
Question 33 Explanation:
AVL Tree all operations(insert, delete and search) will take O(logn) time.
In question they asked about n^{2} elements.
So, In worst case it will take o(n^{2} logn) time.
In question they asked about n^{2} elements.
So, In worst case it will take o(n^{2} logn) time.
Question 34 
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
10*(0*10*10*)*
 
((0 + 1)*1(0 + 1)*1)*10*  
(0*10*10*)*10*  
(0*10*10*)*0*1

Question 34 Explanation:
The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generate the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generate the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
Question 35 
Consider the following statements about the functionality of an IP based router.
I. A router does not modify the IP packets during forwarding.
II. It is not necessary for a router to implement any routing protocol.
III. A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming IP packet.
Which of the above statements is/are TRUE?
I. A router does not modify the IP packets during forwarding.
II. It is not necessary for a router to implement any routing protocol.
III. A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming IP packet.
Which of the above statements is/are TRUE?
I and II only
 
II only
 
I only
 
II and III only

Question 35 Explanation:
I: The packet contains Header and data. The router modifies the header details like TTL
II: is True
III: Ressemble is not necessary at the router.
II: is True
III: Ressemble is not necessary at the router.
Question 36 
Consider a nonpipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instructions. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the nonpipelined processor (round off to 2 decimal places) is _____.
2.16 
Question 36 Explanation:
In the nonpipelined architecture the clock cycle time = 1/(2.5)G = 0.4 ns
It is given that each instruction takes 5 clock cycles to execute in the nonpipelined architecture, so time taken to execute each instruction = 5 * 0.4 = 2ns
In the pipelined architecture the clock cycle time = 1/2G = 0.5 ns
In the pipelined architecture there are stalls due to memory instructions and branch instructions.
In the pipeline, the updated clocks per instruction CPI = (1+stall frequency due to memory operations * stalls of memory instructions + stall frequency due to branch operations * stalls due to branch instructions)
Out of the total instructions , 30% are memory instructions. Out of those 30%, only 5% cause stalls of 50 cycles each.
Stalls per instruction due to memory operations = 0.3*0.05*50 = 0.75
Out of the total instructions 10% are branch instructions. Out of those 10% of instructions 50% of them cause stalls of 2 cycles each.
Stalls per instruction due to branch operations = 0.1*0.5*2 = 0.1
The updated CPI in pipeline = 1 + 0.75 + 0.1 = 1.85
The execution time in the pipeline = 1.85 * 0.5 = 0.925 ns
The speed up = Time in nonpipelined architecture / Time in pipelined architecture = 2 / 0.925 = 2.16
It is given that each instruction takes 5 clock cycles to execute in the nonpipelined architecture, so time taken to execute each instruction = 5 * 0.4 = 2ns
In the pipelined architecture the clock cycle time = 1/2G = 0.5 ns
In the pipelined architecture there are stalls due to memory instructions and branch instructions.
In the pipeline, the updated clocks per instruction CPI = (1+stall frequency due to memory operations * stalls of memory instructions + stall frequency due to branch operations * stalls due to branch instructions)
Out of the total instructions , 30% are memory instructions. Out of those 30%, only 5% cause stalls of 50 cycles each.
Stalls per instruction due to memory operations = 0.3*0.05*50 = 0.75
Out of the total instructions 10% are branch instructions. Out of those 10% of instructions 50% of them cause stalls of 2 cycles each.
Stalls per instruction due to branch operations = 0.1*0.5*2 = 0.1
The updated CPI in pipeline = 1 + 0.75 + 0.1 = 1.85
The execution time in the pipeline = 1.85 * 0.5 = 0.925 ns
The speed up = Time in nonpipelined architecture / Time in pipelined architecture = 2 / 0.925 = 2.16
Question 37 
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P_{1},P_{2},P_{3},P_{4}.
If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is _____.
If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is _____.
5.25 
Question 37 Explanation:
Question 38 
Let G = (V,E) be a directed, weighted graph with weight function w:E> R. For some function f:V> R, for each edge (u,v)E, define w'(u,v) as w(u,v)+f(u)f(v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _______”.
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w’ too, _______”.
if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G  
for every f:V> R

Question 38 Explanation:
Question 39 
Consider a schedule of transactions T_{1} and T_{2}:
Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one of the following schedules is conflict equivalent to the above schedule?
Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one of the following schedules is conflict equivalent to the above schedule?
Question 39 Explanation:
• Two schedules are said to be conflict equivalent, if conflict operations in both the schedules are executed in the same order.
• First, let’s list the conflict operations of each of the schedule given in the options and compare with the conflict operations of schedule which is given in the question.
Given schedule:
The conflict operations in the option (2) and given schedule are appearing in the same sequence order, so option (2) is the answer.
• First, let’s list the conflict operations of each of the schedule given in the options and compare with the conflict operations of schedule which is given in the question.
Given schedule:
The conflict operations in the option (2) and given schedule are appearing in the same sequence order, so option (2) is the answer.
Question 40 
A computer system with a word length of 32 bits has a 16 MB byteaddressable main memory and a 64 KB, 4way set associative cache memory with a block size of 256 bytes. Consider the following four physical addresses represented in hexadecimal notation.
A1 = 0x42C8A4, A2 = 0x546888, A3 = 0x6A289C, A4 = 0x5E4880
Which one of the following is TRUE?
A1 = 0x42C8A4, A2 = 0x546888, A3 = 0x6A289C, A4 = 0x5E4880
Which one of the following is TRUE?
A1 and A4 are mapped to different cache sets.  
A1 and A3 are mapped to the same cache set.
 
A3 and A4 are mapped to the same cache set.
 
A2 and A3 are mapped to the same cache set.

Question 40 Explanation:
Main memory is 16MB in size.
The word length is given as 32 bits and the physical addresses mentioned are all contain 6 hexadecimal digits, so the the physical address is 32 bits long.
Block size is 256 bytes, block offset = 8 bits as it is a byte addressable memory.
Cache size = 64KB
Number of blocks in the cache = 64KB/256B = 256
It is a 4way set associative cache, so no. of sets in the cache = 256/4 = 64 = 2^6
In the physical address we need 6 bits for the SET number.
TAG bits = 32  6  8 = 18
So the 32 bits physical address is divided as (18 TAG bits + 6 SET number bits + 8 OFFSET bits)
Since in all the options we are asked about SET numbers of the given addresses, we need to find the SET number of each of the addresses.
A1 = 0x42C8A4, here SET number is (00 1000) which includes the last 2 bits of C(1100) and binary representation of 8 (1000).
A2 = 0x546888, here SET number is (10 1000) which includes the last 2 bits of 6(0110) and binary representation of 8 (1000).
A3 = 0x6A289C here SET number is (10 1000) which includes the last 2 bits of 2(0010) and binary representation of 8 (1000).
A4 = 0x5E4880 here SET number is (00 1000) which includes the last 2 bits of 4 (0100) and binary representation of 8 (1000).
From the given options option4 is TRUE as A2, A3 are mapped to the same cache SET.
The word length is given as 32 bits and the physical addresses mentioned are all contain 6 hexadecimal digits, so the the physical address is 32 bits long.
Block size is 256 bytes, block offset = 8 bits as it is a byte addressable memory.
Cache size = 64KB
Number of blocks in the cache = 64KB/256B = 256
It is a 4way set associative cache, so no. of sets in the cache = 256/4 = 64 = 2^6
In the physical address we need 6 bits for the SET number.
TAG bits = 32  6  8 = 18
So the 32 bits physical address is divided as (18 TAG bits + 6 SET number bits + 8 OFFSET bits)
Since in all the options we are asked about SET numbers of the given addresses, we need to find the SET number of each of the addresses.
A1 = 0x42C8A4, here SET number is (00 1000) which includes the last 2 bits of C(1100) and binary representation of 8 (1000).
A2 = 0x546888, here SET number is (10 1000) which includes the last 2 bits of 6(0110) and binary representation of 8 (1000).
A3 = 0x6A289C here SET number is (10 1000) which includes the last 2 bits of 2(0010) and binary representation of 8 (1000).
A4 = 0x5E4880 here SET number is (00 1000) which includes the last 2 bits of 4 (0100) and binary representation of 8 (1000).
From the given options option4 is TRUE as A2, A3 are mapped to the same cache SET.
Question 41 
For n > 2, let a {0,1}^{n} be a nonzero vector. Suppose that x is chosen uniformly at random from {0,1}^{n}.
0.5 
Question 41 Explanation:
Question 42 
Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edgecolour G is _____.
7 
Question 42 Explanation:
In k3x4 there are two sets with sizes 3,4. (its a complete bipartite graph).
The vertex in the set of size 3 has 4 edges connected to 4 vertices on other set. So, edge color of G is max(3,4) i.e. 4.
When a vertex is added to the graph with 7 vertices ( K 3x4 has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
The vertex in the set of size 3 has 4 edges connected to 4 vertices on other set. So, edge color of G is max(3,4) i.e. 4.
When a vertex is added to the graph with 7 vertices ( K 3x4 has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
Question 43 
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space 202.61.0.0/17. The ISP wants to assign an address space to the organization which will minimize the number of routing entries in the ISP’s router using route aggregation. Which of the following address spaces are potential candidates from which the ISP can allot any one to the organization?
I. 202.61.84.0/21
II. 202.61.104.0/21
III. 202.61.64.0/21
IV. 202.61.144.0/21
I. 202.61.84.0/21
II. 202.61.104.0/21
III. 202.61.64.0/21
IV. 202.61.144.0/21
I and II only  
III and IV only
 
II and III only
 
I and IV only

Question 43 Explanation:
Given CIDR IP is 202.61.0.0/17 and for HID 32  17 = 15 bits can be used.
And to Assign an IP address for 1500 computer, we require 11 bit from HID part.
So NID + SID = 17 + 4 = 21 bits and HID = 11 bits
NID HID
202.61.0 0000 000.00000000
So, from the given option, possible IP Address is
I. 84  >0 1010 100 (BCZ in HID bit 1 is not possible)
II. 104 >0 1101 000
III. 64 > 0 1000 000
IV. 144>1 0010 000 (BCZ in NID bit 1 is not possible )
And to Assign an IP address for 1500 computer, we require 11 bit from HID part.
So NID + SID = 17 + 4 = 21 bits and HID = 11 bits
NID HID
202.61.0 0000 000.00000000
So, from the given option, possible IP Address is
I. 84  >0 1010 100 (BCZ in HID bit 1 is not possible)
II. 104 >0 1101 000
III. 64 > 0 1000 000
IV. 144>1 0010 000 (BCZ in NID bit 1 is not possible )
Question 44 
Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?
A cell in R holds a set instead of an atomic value.
 
R has a nontrivial functional dependency X>A, where X is not a superkey and A is a nonprime attribute and X is not a proper subset of any key.
 
R has a nontrivial functional dependency X>A, where X is not a superkey and A is a nonprime attribute and X is a proper subset of some key.
 
R has a nontrivial functional dependency X>A, where X is not a superkey and A is a prime attribute.

Question 44 Explanation:
R(ABCD)
FDs:
AB → C
BC → A
(BD)^{+} = BD ✖
(ABD)^{+} = ABDC ✔
(CBD)^{+} = CBDA ✔
Candidate keys = {ABD, CBD}
• The relation R is in 3NF, as there are no transitive dependencies.
• The relation R is not in BCNF, because the left side of both the FD’s are not Super keys.
• In R, BC → A is a nontrivial FD and in which BC is not a Super key and A is a prime attribute.
FDs:
AB → C
BC → A
(BD)^{+} = BD ✖
(ABD)^{+} = ABDC ✔
(CBD)^{+} = CBDA ✔
Candidate keys = {ABD, CBD}
• The relation R is in 3NF, as there are no transitive dependencies.
• The relation R is not in BCNF, because the left side of both the FD’s are not Super keys.
• In R, BC → A is a nontrivial FD and in which BC is not a Super key and A is a prime attribute.
Question 45 
Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is ______.
4 
Question 45 Explanation:
Question 46 
A processor has 64 registers and uses 16bit instruction format. It has two types of instructions: Itype and Rtype. Each Itype instruction contains an opcode, a register name, and a 4bit immediate value. Each Rtype instruction contains an opcode and two register names. If there are 8 distinct Itype opcodes, then the maximum number of distinct Rtype opcodes is _____.
14 
Question 46 Explanation:
Instruction is of size 16bits.
All possible binary combinations = 2^16
There are 64 registers, so no. of bits needed to identify a register = 6
Itype instruction has (Opcode+Register+4bit immediate value).
There are 8 distinct Itype instructions.
All the binary combinations possible with the Itype instructions are = 8*2^6*2^4 = 2^13
Rtype instructions have 2 register operands.
Let x be the number of Rtype instructions.
All the possible binary combinations of Rtype instructions = x*2^6*2^6 = x*2^12
The sum of Itype and Rtype binary combinations should be equal to 2^16.
x*2^12 + 2^13 = 2^16
2^12 (x+2) = 2^16
x+2 = 2^4
x = 16 2 = 14
All possible binary combinations = 2^16
There are 64 registers, so no. of bits needed to identify a register = 6
Itype instruction has (Opcode+Register+4bit immediate value).
There are 8 distinct Itype instructions.
All the binary combinations possible with the Itype instructions are = 8*2^6*2^4 = 2^13
Rtype instructions have 2 register operands.
Let x be the number of Rtype instructions.
All the possible binary combinations of Rtype instructions = x*2^6*2^6 = x*2^12
The sum of Itype and Rtype binary combinations should be equal to 2^16.
x*2^12 + 2^13 = 2^16
2^12 (x+2) = 2^16
x+2 = 2^4
x = 16 2 = 14
Question 47 
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
Note that W is a predicate formula without any free occurrence of x.
Question 47 Explanation:
Question 48 
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.
Question 48 Explanation:
The idea is to traverse the given binary search tree starting from root. For every node being visited, check if this node lies in range, if yes, then add 1 to result and recur for both of its children. If the current node is smaller than the low value of range, then recur for right child, else recur for left child.
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is logn, hence O(logn+k)
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is logn, hence O(logn+k)
Question 49 
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is _______.
12 
Question 49 Explanation:
There are 5 places
― ― ― ― ―
Given: L I L A C
The derangements formula ⎣n!/e⎦ cannot be directly performed as there are repeated characters.
Let’s proceed in regular manner:
The L, L can be placed in other ‘3’ places as
(1) Can be arranged such that A, I, C be placed in three positions excluding ‘C’ being placed at its own position, which we get only 2×2×1=4 ways.
Similarly (2) can be filled as A, I, C being placed such that 4th position is not filled by A, so we have 2×2×1= 4 ways. Similarly with (3).
Totally, we get 4+4+4 = 12 ways.
― ― ― ― ―
Given: L I L A C
The derangements formula ⎣n!/e⎦ cannot be directly performed as there are repeated characters.
Let’s proceed in regular manner:
The L, L can be placed in other ‘3’ places as
(1) Can be arranged such that A, I, C be placed in three positions excluding ‘C’ being placed at its own position, which we get only 2×2×1=4 ways.
Similarly (2) can be filled as A, I, C being placed such that 4th position is not filled by A, so we have 2×2×1= 4 ways. Similarly with (3).
Totally, we get 4+4+4 = 12 ways.
Question 50 
Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ε V x V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
Question 50 Explanation:
Method1:
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge .
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V)
Method2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method1 is the most appropriate answer for giving a question.
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge .
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V)
Method2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method1 is the most appropriate answer for giving a question.
Question 51 
Consider the following C functions.
The return value of fun2 (5) is _______.
The return value of fun2 (5) is _______.
55 
Question 51 Explanation:
#include
int fun1(int n) {
printf("fun1 call\n");
static int i = 0;
if(n>0){
++i;
printf("fun1(%d1)\n",n);
fun1(n1);
}
printf("fun1(%d)= %d\n",n, i);
return(i);
}
int fun2(int n) {
printf("\n******* fun2 call ********\n");
static int i = 0;
if(n>0){
printf("%d + fun1(%d)\n", i,n);
i=i+fun1(n);
fun2(n1);
}
printf("fun2(%d)= %d\n",n, i);
return(i);
}
void main()
{
printf("final = %d\n", fun2(5));
}
Check step by step handrun of the code to understand the recursion:
******* fun2 call ********
0 + fun1(5)
fun1 call
fun1(51)
fun1 call
fun1(41)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 5
fun1(1)= 5
fun1(2)= 5
fun1(3)= 5
fun1(4)= 5
fun1(5)= 5
******* fun2 call ********
5 + fun1(4)
fun1 call
fun1(41)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 9
fun1(1)= 9
fun1(2)= 9
fun1(3)= 9
fun1(4)= 9
******* fun2 call ********
14 + fun1(3)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 12
fun1(1)= 12
fun1(2)= 12
fun1(3)= 12
******* fun2 call ********
26 + fun1(2)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 14
fun1(1)= 14
fun1(2)= 14
******* fun2 call ********
40 + fun1(1)
fun1 call
fun1(11)
fun1 call
fun1(0)= 15
fun1(1)= 15
******* fun2 call ********
fun2(0)= 55
fun2(1)= 55
fun2(2)= 55
fun2(3)= 55
fun2(4)= 55
fun2(5)= 55
final = 55
int fun1(int n) {
printf("fun1 call\n");
static int i = 0;
if(n>0){
++i;
printf("fun1(%d1)\n",n);
fun1(n1);
}
printf("fun1(%d)= %d\n",n, i);
return(i);
}
int fun2(int n) {
printf("\n******* fun2 call ********\n");
static int i = 0;
if(n>0){
printf("%d + fun1(%d)\n", i,n);
i=i+fun1(n);
fun2(n1);
}
printf("fun2(%d)= %d\n",n, i);
return(i);
}
void main()
{
printf("final = %d\n", fun2(5));
}
Check step by step handrun of the code to understand the recursion:
******* fun2 call ********
0 + fun1(5)
fun1 call
fun1(51)
fun1 call
fun1(41)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 5
fun1(1)= 5
fun1(2)= 5
fun1(3)= 5
fun1(4)= 5
fun1(5)= 5
******* fun2 call ********
5 + fun1(4)
fun1 call
fun1(41)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 9
fun1(1)= 9
fun1(2)= 9
fun1(3)= 9
fun1(4)= 9
******* fun2 call ********
14 + fun1(3)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 12
fun1(1)= 12
fun1(2)= 12
fun1(3)= 12
******* fun2 call ********
26 + fun1(2)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 14
fun1(1)= 14
fun1(2)= 14
******* fun2 call ********
40 + fun1(1)
fun1 call
fun1(11)
fun1 call
fun1(0)= 15
fun1(1)= 15
******* fun2 call ********
fun2(0)= 55
fun2(1)= 55
fun2(2)= 55
fun2(3)= 55
fun2(4)= 55
fun2(5)= 55
final = 55
Question 52 
Consider the array representation of a binary minheap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
511 
Question 52 Explanation:
The binary heap contains 1023 elements.
When it performs minimum comparisons it will take Ceil(n/2)
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2. So, we have to subtract from the total elements
=5121
=511
When it performs minimum comparisons it will take Ceil(n/2)
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2. So, we have to subtract from the total elements
=5121
=511
Question 53 
Let A and B be two n×n matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements,
I. rank(AB) = rank(A) rank(B)
II. det(AB) = det(A) det(B)
III. rank(A + B) ≤ rank(A) + rank(B)
IV. det(A + B) ≤ det(A) + det(B)
Which of the above statements are TRUE?
I. rank(AB) = rank(A) rank(B)
II. det(AB) = det(A) det(B)
III. rank(A + B) ≤ rank(A) + rank(B)
IV. det(A + B) ≤ det(A) + det(B)
Which of the above statements are TRUE?
I and II only
 
I and IV only
 
III and IV only
 
II and III only

Question 53 Explanation:
Rank(AB)≥Rank(A)+Rank(B)−n. So option I is wrong.
Rank is the number of independent rows(vectors) of a matrix. On product of two matrices, the combined rank is more than the sum of individual matrices (subrtraced with the order n)
det(AB) = det(A).det(b) as the magnitude remains same for the matrices after multiplication.
Note: We can just take a 2x2 matrix and check the options.
Rank is the number of independent rows(vectors) of a matrix. On product of two matrices, the combined rank is more than the sum of individual matrices (subrtraced with the order n)
det(AB) = det(A).det(b) as the magnitude remains same for the matrices after multiplication.
Note: We can just take a 2x2 matrix and check the options.
Question 54 
Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a shared variable initialized to 0 and not used in CODE SECTION P.
wait (a); count = count+1;
if (count==n) signal (b);
signal (a); wait (b); signal (b);
What does the code achieve?
wait (a); count = count+1;
if (count==n) signal (b);
signal (a); wait (b); signal (b);
What does the code achieve?
It ensures that all processes execute CODE SECTION P mutually exclusively.
 
It ensures that at most two processes are in CODE SECTION Q at any time.  
It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
 
It ensures that at most n1 processes are in CODE SECTION P at any time.

Question 54 Explanation:
The wait(a) ensures that count value is correctly incremented (no race condition) if(count==n) signal (b); // This signal(b) statement is executed by the last (nth) process only. Rest of the n1 processes are blocked on wait(b). Once the nth process makes signal(b) then rest of the processes can proceed
an enter Code section Q.
Question 55 
Consider the productions A⟶PQ and A⟶XY. Each of the five nonterminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.
Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i
Which one of the following is TRUE?
Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s
Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i
Which one of the following is TRUE?
Only Rule 2 is Lattributed.  
Neither Rule 1 nor Rule 2 is Lattributed.
 
Both Rule 1 and Rule 2 are Lattributed.
 
Only Rule 1 is Lattributed.

Question 55 Explanation:
In rule 2 for production A> XY the attribute “i” is calculated from the right sibling Y in
X.i= A.i + Y.s which is violating the L attribute definition, as in L attribute calculating attribute vale from RHS sibling is not allowed.
X.i= A.i + Y.s which is violating the L attribute definition, as in L attribute calculating attribute vale from RHS sibling is not allowed.
Question 56 
Consider a TCP connection between a client and a server with the following specifications: the round trip time is 6 ms, the size of the receiver advertised window is 50 KB, slow start threshold at the client is 32 KB, and the maximum segment size is 2 KB. The connection is established at time t=0. Assume that there are no timeouts and errors during transmission. Then the size of the congestion window (in KB) at time t+60 ms after all acknowledgements are processed is ______.
44 
Question 56 Explanation:
Threshold = 32 Kb, MSS = 2KB, RTT = 6ms
Here, t + 60 is nothing but at the 10 RTT (60/6 = 10), but here it’s asking after all acknowledgement are processed it means after the 10th RTT, .i.e at the 11RTT
1st transmission: 2 KB
2nd transmission: 4 KB
3rd transmission: 8 KB
4th transmission: 16 KB
5th transmission: 32 KB (Threshold reached)
6th transmission: 34 KB
7th transmission: 36 KB
8th transmission: 38 KB
9th transmission: 40 KB
10th transmission: 42 KB
At the completion of 10th transmission RTT = 10*6 = 60 ms
For the 11th transmission, The congestion window size is 44 KB
Here, t + 60 is nothing but at the 10 RTT (60/6 = 10), but here it’s asking after all acknowledgement are processed it means after the 10th RTT, .i.e at the 11RTT
1st transmission: 2 KB
2nd transmission: 4 KB
3rd transmission: 8 KB
4th transmission: 16 KB
5th transmission: 32 KB (Threshold reached)
6th transmission: 34 KB
7th transmission: 36 KB
8th transmission: 38 KB
9th transmission: 40 KB
10th transmission: 42 KB
At the completion of 10th transmission RTT = 10*6 = 60 ms
For the 11th transmission, The congestion window size is 44 KB
Question 57 
Consider the Boolean function z(a,b,c).
Which one of the following minterm lists represents the circuit given above?
Which one of the following minterm lists represents the circuit given above?
Z=Σ(0,1,3,7)
 
Z=Σ(2,4,5,6,7)
 
Z=Σ(1,4,5,6,7)  
Z=Σ(2,3,5)

Question 57 Explanation:
The output of the given circuit is a+b’c.
Convert a+b’c into canonical form which is sum of minterms.
a+b’c = a(b+b’)(c+c’)+ (a+a’)b’c
= abc + abc’ + ab’c + ab’c’ + ab’c + a’b’c
=Σ(7,6,5,4,1)
Convert a+b’c into canonical form which is sum of minterms.
a+b’c = a(b+b’)(c+c’)+ (a+a’)b’c
= abc + abc’ + ab’c + ab’c’ + ab’c + a’b’c
=Σ(7,6,5,4,1)
Question 58 
Consider three registers R1, R2 and R3 that store numbers in IEEE754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0x42200000 and 0xC1200000, respectively.
If R3 = R1/R2, what is the value stored in R3?
If R3 = R1/R2, what is the value stored in R3?
0x40800000
 
0x83400000
 
0xC8500000
 
0xC0800000

Question 58 Explanation:
Given numbers are 0x42200000 and 0xC1200000 which are stored in the registers R1 and R2, respectively.
Question 59 
Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.
(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)
Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.
Which one of the following statements is FALSE?
(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)
Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.
Which one of the following statements is FALSE?
The head reverses its direction of movement between servicing of Q and P.  
T is serviced before P.  
R is serviced before P.
 
Q is serviced after S, but before T.

Question 59 Explanation:
(P,155)(Q,85)(R,110)(S,30)(T,115)
Question 60 
Consider a graph G = (V, E), where V = {v_{1}, v_{2}, …, v_{100}}, E = {(v_{i}, v_{j})  1 ≤ i < j ≤ 100}, and weight of the edge (v_{i}, v_{j}) is i  j. The weight of the minimum spanning tree of G is ______.
99 
Question 60 Explanation:
• If there are n vertices in the graph, then each spanning tree has n − 1 edges.
• N =100
• Edge weight is ij for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So 99 edges of weight is 99
• N =100
• Edge weight is ij for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So 99 edges of weight is 99
Question 61 
Consider the following C functions.
The value returned by pp (3, 4) is ________.
The value returned by pp (3, 4) is ________.
81 
Question 61 Explanation:
pp(3,4) ⇒
a=3,b=4
tot=1
ex=a=3
len=tob(b,arr) which is 3
[
tob(4,arr)==>
b=4
b%2 =4%2=0 Condition is false then arr[0]=0
=> b=b/2 =4/2 =2
b=2
b%2 =2%2=0 condition is false then arr[1]=0
=>b=b/2=2/2=1
b=1
then b%2=1%2 condition is true then arr[2]=1
=>b=b/2=1/2=0
The i value is 3 [length is 3]
]
i=0,
arr[0] ==1 condition is false
ex=3*3=9
i=1
arr[1]==1 condition is false
then
ex=9*9=81
i=2
then arr[2]==1 condition is true
tot=tot*ex=1*81=81
ex=81*81
Finally it returns tot value which 81
a=3,b=4
tot=1
ex=a=3
len=tob(b,arr) which is 3
[
tob(4,arr)==>
b=4
b%2 =4%2=0 Condition is false then arr[0]=0
=> b=b/2 =4/2 =2
b=2
b%2 =2%2=0 condition is false then arr[1]=0
=>b=b/2=2/2=1
b=1
then b%2=1%2 condition is true then arr[2]=1
=>b=b/2=1/2=0
The i value is 3 [length is 3]
]
i=0,
arr[0] ==1 condition is false
ex=3*3=9
i=1
arr[1]==1 condition is false
then
ex=9*9=81
i=2
then arr[2]==1 condition is true
tot=tot*ex=1*81=81
ex=81*81
Finally it returns tot value which 81
Question 62 
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.
L_{2} and L_{3} only
 
L_{1} and L_{3} only  
L_{2}, L_{3} and L_{4} only  
L_{1}, L_{3} and L_{4} only 
Question 62 Explanation:
L1 is undecidable as emptiness problem of Turing machine is undecidable. L3 is undecidable since there is no algorithm to check whether a given TM accept recursive language. L4 is undecidable as it is similar to membership problem.
Only L3 is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Only L3 is decidable. We can check whether a given TM reach state q in exactly 100 steps or not. Here we have to check only upto 100 steps, so here is not any case of going to infinite loop.
Question 63 
Consider a paging system that uses a 1level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ______.
154.5ns 
Question 63 Explanation:
M=100ns
T=20ns
D=5000ns
h=0.95
p=0.1, 1p=0.9
d=0.2, 1d=0.8
EMAT = h×(T+M)+(1h)[(1p)×2M+p[(1d)[D+M]+d(2D+M)]+T]
= 0.95×(20+100)+(10.95)[(10.1)×200+(0.1)[(10.2)[5000+100]+(0.2)(10000+100)]+20] = 154.5ns
T=20ns
D=5000ns
h=0.95
p=0.1, 1p=0.9
d=0.2, 1d=0.8
EMAT = h×(T+M)+(1h)[(1p)×2M+p[(1d)[D+M]+d(2D+M)]+T]
= 0.95×(20+100)+(10.95)[(10.1)×200+(0.1)[(10.2)[5000+100]+(0.2)(10000+100)]+20] = 154.5ns
Question 64 
Consider the following language.
L = {x ∈ {a,b}*  number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.
L = {x ∈ {a,b}*  number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.
6 
Question 64 Explanation:
Question 65 
Consider the following languages.
L_{1} = {wxyx  w,x,y ∈ (0 + 1)+}
L_{2} = {xy  x,y ∈ (a + b)*, x = y, x ≠ y}
Which one of the following is TRUE?
L_{1} = {wxyx  w,x,y ∈ (0 + 1)+}
L_{2} = {xy  x,y ∈ (a + b)*, x = y, x ≠ y}
Which one of the following is TRUE?
L_{1} is contextfree but not regular and L_{2} is contextfree.
 
Neither L_{1} nor L_{2} is contextfree.
 
L_{1} is regular and L_{2} is contextfree.  
L_{1} is contextfree but L_{2} is not contextfree.

Question 65 Explanation:
L_{1} is regular. y can be expanded and w can also expanded. So x can be either "a" or "b"
So it is equivalent to
(a+b)+ a (a+b)+ a + (a+b)+ b (a+b)+ b
L_{2} is CFL since it is equivalent to complement of L=ww. Complement of
L=ww is CFL.
So it is equivalent to
(a+b)+ a (a+b)+ a + (a+b)+ b (a+b)+ b
L_{2} is CFL since it is equivalent to complement of L=ww. Complement of
L=ww is CFL.
There are 65 questions to complete.