Courses

# Test : CSE Past Year Paper 2019

## 65 Questions MCQ Test Mock Test Series - Computer Science Engg. (CSE) GATE | Test : CSE Past Year Paper 2019

Description
This mock test of Test : CSE Past Year Paper 2019 for GATE helps you for every GATE entrance exam. This contains 65 Multiple Choice Questions for GATE Test : CSE Past Year Paper 2019 (mcq) to study with solutions a complete question bank. The solved questions answers in this Test : CSE Past Year Paper 2019 quiz give you a good mix of easy questions and tough questions. GATE students definitely take this Test : CSE Past Year Paper 2019 exercise for a better result in the exam. You can find other Test : CSE Past Year Paper 2019 extra questions, long questions & short questions for GATE on EduRev as well by searching above.
QUESTION: 1

### Two cars start at the same time from the same location and go in the same direction. The speed of the first car is 50 km/h and the speed of the second car is 60 km/h. The number of hours it takes for the distance between the two cars to be 20 km is _________.

Solution:

Let us take two cars A and B
VA = 50 km/hr
V= V 60 km/hr

QUESTION: 2

Solution:
QUESTION: 3

### Ten friends planned to share equally the cost of buying a gift for their teacher. When two of them decided not to contribute, each of the other friends had to pay Rs 150 more. The cost of the gift was Rs __________.

Solution:

Let us consider cost of gift = X
If 10 friends contributes then share = X/10
Two friends denied to contribute then remaining are 8 each of remaining to be given 150 more

QUESTION: 4

A court is to a judge as ________ is to a teacher.

Solution:
QUESTION: 5

The search engine‟s business model ________ around the fulcrum of trust.

Solution:
QUESTION: 6

Three of the five students allocated to a hostel put in special requests to the warden. Given the floor plan of the vacant rooms, select the allocation plan that will accommodate all their requests.
Request X: Due to pollen allergy, I want to avoid a wing next to the garden.
Request by Y: I want to live as far from the washrooms as possible, since I am very sensitive to
smell.
Request by Z: I believe in Vaastu and so want to stay in the South-west wing.

Solution:
QUESTION: 7

The police arrested four criminals –P, Q, R and S. The criminals knew each other. They made the following statements:
P says “Q committed the crime.”
Q says “S committed the crime.”
R says “I did not do it.”
S says “What Q said about me is false.”
Assume only one of the arrested four committed the crime and only one of the statement made above is true. Who committed the crime?

Solution:

Explanation: Given that only one person committed the crime and only one given statement is correct.

When P is correct and Q, R, S are false: it implies,Q committed crime, S did not commit crime, R committed crime, S committed crime.

This situation is impossible.

When Q is correct and P, R, S are false: it implies,Q did not commit crime, S committed crime, R committed crime, S committed crime.

This situation is impossible.

When R is correct and P, Q, S are false: it implies,Q did not commit crime, S did not commit crime, R did not commit crime, S committed crime.

This situation is impossible.

When S is correct and P, Q, R are false: it implies,Q did not commit crime, S did not commit crime, R committed crime, S did not commit crime.

This situation is possible means R has committed crime.

So, option (B) is correct.

QUESTION: 8

“A recent High Court Judgment has sought to dispel the ideal of begging as a disease which leads to its stigmatization and criminalization – and to regard it as a symptom. The underlying disease is the failure of the state to protect citizens who fall through the social security net.”
Which one of the following statements can be inferred from the given passage?

Solution:
QUESTION: 9

In a college, there are three student clubs, Sixty students are only in the Drama club, 80 students are only in the Dance club, 30 students are only in the Maths club, 40 students are in both Drama and Dance clubs, 12 students are in both Dance and Maths clubs, 7 students are in both Drama and Maths clubs, and 2 students are in all the clubs. If 75% of the students in the college are not in any of these clubs, then the total number of students in the college is ________.

Solution:

Total number of students in the all three clubs
= 60 + 38 + 80 + 5 + 2 + 10 + 30 = 225
Total number of students in the college = X

Given that 75% of students are not of any of these clubs.
Remaining 25% of X = 225
0.25X = 225 ⇒ X = 225/0.25 = 900

QUESTION: 10

In the given diagram, teachers are represented in the triangle, researchers in the circle and administrators in the rectangle. Out of the total number of the people, the percentage of administrators shall be in the rage of ___________.

Solution:

Total number of people = 70 + 10 + 20 + 20 + 40 = 160
Total number of administrators = 10 + 20 + 20 = 50

QUESTION: 11

Which one of the following kinds of derivation is used by LR parsers?

Solution:

LR parser uses rightmost derivation in reverse order.

*Answer can only contain numeric values
QUESTION: 12

Consider the following C program:
#include <stdio.h>
int main(){
int arr[ ]={1,2,3,4,5,6,7,8,9,0,1,2,5},  *ip=arr+4;
printf("%d \n", ip[1]);
return 0;
}
The number that will be displayed on execution of the program is _________.

Solution:

*ip=arr+4 will point element 5 in the array, since it will increment the base address of the array by 4.
ip[1] is equal to *(ip+1)
it will further increment the pointer to next element and hence it will print 6.

QUESTION: 13

For ∑ = {a,b} , let us consider the regular language L = {x | x a2+3k or  x = b10+12k, k ≥ 0}.
Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

Solution:

The set x is consists of {a2 , a5 , a8 , a11........} here the pumping length is 3 i.e. to get the another string we can repeat the length 3.
The regular expression is aa(aaa)*
Or { b10 , b22 , b34 , b46 ...........}, here the pumping length is 12
The regular expression is b10 (bbbbbbbbbbbb)*
Pumping length can‟t be 5
Pumping length can‟t be 9, because it will generate 18 which is not multiple of 12
Pumping length can‟t be 3, since it will generate 15, which is not multiple of 12
Possible pumping length can be 24 since every repetition will be multiple of 3 and 12.

QUESTION: 14

Let U = {1, 2, …, n}. Let A = {( x, X ) | x ∈ X, X ⊂ U}. Consider the following two statements on |A|.

Which of the above statements is/are TRUE?

Solution:

U {1, 2, ....n}
X U
i.e., X is subset of U
and number of subsets are = 2[ since n elements are there]
In case of nC0 n i.e., subset is φ
We cannot select any element
In case of mC1 we have only one choice
In case of nC2 we have selected two elements subset
So there exists two value of x & . t x ∈ x
And this goes on.

QUESTION: 15

A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?

Solution:

The division of fully associative cache is
Cache size is 16 kB
Block size is 16 Bytes , byte offset is log2 = 4bits
Number of blocks 16kb/16 = 1k = 210
Number of bits required to index is 10 bits.
Since fully associative is not having index field hence TAG field is 32 – 4 = 28 bits (D) is the Key.

*Answer can only contain numeric values
QUESTION: 16

Consider the grammar given below:
S → Aa
A → BD
B → b | ∈
D → d | ∈
Let a, b, d, and \$ be indexed as follows:

Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b. d, \$}, then the Key should be 3210)

Solution:

follow(B)  = first(D)
first(D) is { d , ∈ }
follow (B)  is {d} and since first(D) contains e
first(A) is {a}
Index of a is 3 and d is 1
Hence 31.

QUESTION: 17

Let X be a square matrix. Consider the following two statements on X.
I. X is invertible
II. Determine of X is non-zero.
Which one of the following is TRUE?

Solution:

If | A | ≠ 0 then A is invertible matrix
If A -1 exists then | A | ≠ 0
∴ I and II are equivalent statements.

QUESTION: 18

The chip select logic for a certain DRAM chip in a memory- system design is shown below Assume that the memory system has 16 address lines denoted by A15 to A0. What is the range of addresses (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal?

Solution:

Chip select signal will be enable only of

And rest of the bits

Will be available from 00000000000 to 11111111111 Hence address

*Answer can only contain numeric values
QUESTION: 19

Consider a sequence of 14 elements: A = {-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum  Determine the maximum of S (i, j ) , where 0 ≤ i ≤ j < 14 . (Divide and conquer approach may be used.)

Solution:

The maximum sum of the array
{6, 3, -1, -2, 13, 4, -9, -1, 4, 12 }
Which sum to 29.

*Answer can only contain numeric values
QUESTION: 20

An array of 25 distinct elements is to be sorted using quick sort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is

Solution:

The worst possible location for the pivot is either first place or the last place
Hence the probability is 2/25 = 0.08

*Answer can only contain numeric values
QUESTION: 21

The value of 351 mod 5 is _______.

Solution:

351 mod 5 = ?

*Answer can only contain numeric values
QUESTION: 22

Consider the concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialization to 100.

The processes are executed on a uniprocessor system running a time-shared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y–X is _________.

Solution:

For maximum value:
First P2 & P1 read the D value as 100.
So, P2 update it first
⇒ D = D - 50 = 100 - 50 = 50
After P2, P1 overwrite the value 50 by 120
⇒ D = D + 20 =100 + 20 =120
Then P3 read the value of D as 120 and adds 10 to it
⇒ D = 120 + 10 = 130
∴ The max value of D after all 3 processes are executed is 130(Y).
For minimum Value:
All processes read the D value as 100.
But, ensure that last update is from P2.
So that, the min value of D after all 3 processes are executed is 50 (X).
∴ Difference between X and Y is ( Y - X) = 130 - 50 = 80

QUESTION: 23

Compute

Solution:

*Answer can only contain numeric values
QUESTION: 24

Consider the following C program:
#include <stdio.h>
int jumble(int x, int y){
x=2*x+y;
return x; }
int main(){
int x=2, y=5;
y= jumble(y,x);
x= jumble(y,x);
printf("%d \n", x);
return 0;
}
The value printed by the program is _________

Solution:

Initial value of x and y is given as 2 and 5
y= jumble(y,x);
In function
5 is stored in x and 1 stored in y
x = 2*x+y is equal to 2*5+2 = 12 x = 12
return value update y to 12
x= jumble(y,x);
now 12 is stored in x and 2 stored in y
x = 2*x+y is equal to 2*12+2 = 26
x = 26
return value of update x to 26 value printed is 26

QUESTION: 25

Let G be an arbitrary group. Consider the following relations on G:

Which of the above is/are equivalence relation/relations?

Solution:

Let us take an example of multiplication modulus 5

Let us take R2
For Reflexive

So Not reflexive, So R is not equivalence
Let us take R1
For Reflexive

So It is reflexive
If a = g-1bg

[Since multiplication is commutative]

For transitive

So transitive,  so R1 is equivalent relation

QUESTION: 26

Consider the following two statements about database transaction schedules:
I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas‟ Write Rule can generate view serializable schedules that are not conflict serializable.
Which of the above statements is/are TRUE?

Solution:

Strict 2 phase locking protocol ensures conflict serializability as well as strict recoverability.
So statement I is correct.
Thomas write rule sometimes discard the operation in case of multiple write and it is similar to view serializability, focus on last write.
So statement-II is also correct.

*Multiple options can be correct
QUESTION: 27

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

Solution:

Option (B):
For labeled nodes,

For an undirected complete graph G.
Number of Hamiltonian cycles are

3 cycles are;
ABCDA
ACBDA
ACDBA
Option (C):
For unlabelled nodes:
Every Hamilton cycle will be similar. So answer is 1.
Since in question it is not mentioned whether the graph is labeled or not. So both answers are accepted.

QUESTION: 28

Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?

Solution:

SMTP and POP3 are application layer protocols which are responsible for email services
SMTP → Sending or outgoing mail(P ush protocol)
specifically

*Answer can only contain numeric values
QUESTION: 29

The following C program is executed on a Unix/Linux system:
# include < unistd.h>
int main ( )
{int i; for (i = 0; i < 10; i++) if (i % 2 = = 0) fork ( ); return 0;}
The total number of child processes created is ________.

Solution:

According to given logic, child creation is successful only for 5 times between 0 to 9 (As for loop is executed for 10 times)
∴ Number of child processes = 2n -1 = 25 -1 = 31

QUESTION: 30

Consider Z = X – Y, where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:​

Solution:

Ist method:
Take X=31, Y=-31, see both need 6 bits. But Z=X-Y=62 needs 7 bits in sign magnitude form. So, n+1 bits should be answer.
(or)
IInd method:
It is given that x, y, z are in sign magnitude form and represented using „n‟ number of bit.

110 → represent (-2) which is between overflow
If we represent 3 using 4 bits

Same result can be verified by taking
7+7
15 + 15
31 + 31.......So on
So in general z needs n + 1 number of bits.

QUESTION: 31

Which one of the following is NOT a valid identity?

Solution:

1.
XOR-operator following commutative and associative, so this identity is valid.

2.
This is also valid identity

3.

So, this identity is NOT valid.

This identity is also valid.

QUESTION: 32

Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

Solution:

Only leaf nodes have pointer to data records.
So option D is correct.

QUESTION: 33

If L is a regular language over ∑ = {a,b} ; which one of the following languages is NOT regular?

Solution:

Is standard context free language
If ∑= {a,b} then grammar is
S → aSa | bSb|∈
Option (C), regular language are closed under reverse operation and concatenation hence (C) is a regular language.
Call the language of option (b) Prefix(L). the language of option  (D) Suffix(L) and the language for reverse is Reverse(L).
Option (B) Prefix(L) =Reverse(Suffix(Reverse(L)). so if we establish the (b) and (c) parts, the (D) part follows.
Option (D) Because L is regular, there is a DFA that recognizes L. We make an NFA that accepts Suffix(L). First we modify the DFA to remove states that can never be reached. To do this, start by labeling the start state as reachable. Now whenever a state q is reachable and there is a transition from state q to state r. label state r as reachable. Repeat until all states are marked reachable, or until all states that are not reachable have no incoming transition from a reachable state. Delete all unreachable states. Next we modify the DFA to form an NFA as follows. Add a new start state s. Then for every (reachable) state r, add an ∈ -transition from s to r. Leave all accept states as in the DFA. This NFA accepts precisely the suffixes of L. Because Suffix(L) is accepted by an NFA. it is a regular language.

QUESTION: 34

In 16-bit 2‟s complement representation, the decimal number –28 is:

Solution:

First represent +28 16-bit format
+28 = 0000 0000 0001 1100
-28 = 1111 1111 1110 0100 (2 ' s complement of +28)
Finding, 2 ' s complement of +28= 2 ' s complement representation of –28.

*Answer can only contain numeric values
QUESTION: 35

Two numbers are chosen independently and uniformly at random from the set {1, 2… 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is __________.

Solution:

1 - 0 0 0 0
2 - 0 0 11
3 - 0 0 1 0
4 - 0 1 0 1
5 - 0 1 0 0
6 - 0 111
7 - 0 11 0
8 - 1 0 0 1
9 - 1 0 0 0
10 - 1 0 11
11 - 1 0 1 0
12 - 11 0 1
13 - 11 0 0
1–7 (MSB0) 7 numbers
8–13 (MSB1) 6 numbers
Required probability = Either both of them of MSB0
Or both of them of MSB1

*Answer can only contain numeric values
QUESTION: 36

Consider the following relations P(X, Y, Z), Q(X, Y, T) and R(Y, V)

How many tuples will be returned by the following relational algebra query?

Solution:

So A–B = 1 [Since X2 is not in B].

QUESTION: 37

Which one of the following languages over S= {a,b} is NOT a context free?

Solution:

Option (A) is context free language
S → aSa | bSb|ε
Option (C) is context free language
S → aSb | aSbbb | aSbbbbb |ε
Option (D) is Context free language
S → aSa |bSb| S1
S1 → aS1b |ε
Option (B) is NOT context free

QUESTION: 38

Consider the following c-program ​
#include <stdio.h>
int r(){
static int num=7;
return num --; }
int main(){
for (r();r();r())
printf("%d",r());
return 0; }
Which one of the following values will be displayed on execution of the programs?

Solution:

for (r();r();r())
for initialization r() function will execute num will become 6
for conditional checking r() will execute and num will be 5
body of the loop executed and return value will be 5 and hence 5 will be printed
increment part of the loop will be executed as r() and value will be 3
again condition will be tested as r() num will be 2
body of the loop will print as r(), 2 will be printed value decremented to 1
loop will break
final value printed is 52

QUESTION: 39

There are n unsorted arrays: A1 , A2 ,....., An . Assume that n is odd. Each of A1 , A2 ,....., An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1 , A2 ,....., An is

Solution:

Median of an array can be determine in linear time.

*Answer can only contain numeric values
QUESTION: 40

A relational database contains two tables Student and Performance as shown below:

The primary key of the student table is Roll_no. For the performance table, the columns Roll_no and Subject_code together form the primary key. Consider the SQL query given below:
Select S. Student_name,  sum (P. Marks)
FROM  Student S, Performance P
WHERE P. Marks >84
GROUP BY  S.Student_name;
The number of rows returned by the above SQL query is________.

Solution:

We are doing Cartesian product. So without any condition or constraint there are 5 × 6 = 30 rows.
But on applying where P marks > 84 there will be 5× 5 = 25 Rows.
So there are 5 different student names.
So after group by 5 rows would be there.

*Answer can only contain numeric values
QUESTION: 41

Consider the following C program
#include <stdio.h>
int main(){
float sum = 0.0, j = 1.0, i = 2.0;
while (i/j > 0.0625){
j= j+j;
sum = sum + i/j;
printf("%f\n", sum);
}
return 0; }
The number of times the variable sum will be printed, when the above program is executed, is _______.

Solution:

Total sum value printed is 5

QUESTION: 42

Let the set of functional dependencies F = {QR → S, R → P, S → Q} hold on a relation schema X=(PQRS). X is not in BCNF. Suppose X is decomposed into two schemas Y and Z, where Y=(PR) and Z = (QRS).
Consider the two statements given below.
I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is dependency preserving and lossless
Which of the above statements is/are correct?

Solution:

' QR ' is key
'S → Q ' violates
BCNF since
S is not superkey
So Z is not in BCNF
Since no depending is lost when we combine Y and Z.
So it is dependency preserving
Also Y ∩ Z= R
R is key in Y(P, R) So Decomposition is lossless.
So only II statement is correct.

*Answer can only contain numeric values
QUESTION: 43

The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointers. The disk block size is 4 kB, and the disk block address is 32-bits long. The maximum possible file size is (rounded off to 1decimal place)______GB.

Solution:

Given that
DBS = 4kB
DBA = 32 bits or 4B
∴ Number of addresses per DB =
∴ Max file size

= 48kB + 4MB + 4GB ≈ 4GB

*Answer can only contain numeric values
QUESTION: 44

In a RSA cryptosystem, the value of the public modulus parameter n is 3007. If it is also known that φ( n )= 2880, where φ () denotes Euler's Totient function, then the prime factor of n which is greater than 50 is_______

Solution:

Given that n = 3007
φ( n )= 2880
As per RSA algorithm,
n = p * q = 3007 (97*31)
φ (n) = (p-1) (q-1) =2880 (96*30)
For P = 97 and q = 31 only satisfies the given n & φ ( n )
Since, the question is asking for a prime number which greater than 50, So 97 is correct answer.

QUESTION: 45

Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

Solution:

Given LA = 64 bits, PA = 48 bits, PS = 8 kB
Word size = 4 Bytes
As per question, the memory is word addressable
Page size (in words) =
11 bits are required to represent a page (in words)
∴ 128 pages can be addresses with each of size 2kW
∴ Number of virtual addresses can be translated without any TLB miss

QUESTION: 46

Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let X1 , X2, X3, X4, X5, and X6 be the placeholders for the non-terminals D, T, L or L1 in the following table:

Which one of the following are the appropriate choices for X1, X2, X3 and X4?

Solution:

*Answer can only contain numeric values
QUESTION: 47

Consider the following matrix

The absolute value of the product of Eigen values of R is_______

Solution:

Product of Eigen values of R = det ( R )

Applying R 2 → R 2 - R1; R3 → R3 - R1; R 4 → R 4 - R1;

Again, applying R 2 → R 2 - 2R1; R 3 → R 3 - 3R1

∴ The absolute value of the product of eigen values = |det (R)| = |12| = 12

QUESTION: 48

Consider the following C function.
void convert(int n){ if(n<0)
printf(%d",n);
else {
convert(n/2); printf ("%d",n%2);
}
}
Which one of the following will happen when the function convert is called with any positive integer n as argument?

Solution:

Suppose n is equal to 6
void convert(6){
if(n<0)

*Answer can only contain numeric values
QUESTION: 49

Suppose Y is distributed uniformly in the open interval (1,6). The probability that the polynomial
3x2 + 6xY + 3Y + 6 has only real roots is (rounded off to 1 decimal place)____.

Solution:

Since Y ~ U (1, 6)

Pr(Polynomial 3x2 + 6x.y + 3y + 6 has only real roots)

(Since, a quadratic equation ax2 + bx + c = 0 has real roots if b2 - 4ac≥0)

*Answer can only contain numeric values
QUESTION: 50

Let ∑ be the set of all bijections from {1,…,5}to {1,….,5}, where id denotes the identity function, i.e. denote composition on functions. For a string
Consider the language  The minimum number of states in any DFA accepting L is______.

Solution:

Lets have all bijection possible from set {1,2,3} → {1,2,3}

Here, identity function is {{1,1}{2,2},{3,3}}

Lets represents it using a, b,c,d,e,f
Hence ∑ = {a, b, c, d , e, f } where a = {{1,1}{2, 2} ,{3,3}} , b= {{1,1}{2,3} ,{3, 2}} and so on String belong to the language will be

Lets take a string “ab” and see where its maps

Which is {{1,1}{2,3} ,{3, 2}} = b
Suppose the string is “abc”

The “abc” will be mapped to {{1,2}{2,1},{3,3}}

For mapping {1,2,3} → {1,2,3}, 6 states required
For mapping {1,2,3,4,5} → {1,2,3,4,5} , 120 states required

*Answer can only contain numeric values
QUESTION: 51

Let T be a full binary tree with 8 leaves. (A full binary' tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _________

Solution:

A Full binary tree with 8 leaves, the number of ways in which 2 leaves independently can be chosen is 8 * 8= 64
64 pairs of leaves exists
In this, 8 pairs will at distance 0 from each other
8 pairs will be at distance 2 from each others (children of the same parent)
16 pairs will be at distance 4 from each other
32 pairs will be at distance 6 from each other
Hence total distance is 8 * 0 + 8 * 2 + 16 * 4 + 32 * 6 = 272
Expected distance is 272/64 = 4.25

QUESTION: 52

Consider the following statements:
I. The smallest element in a max-heap is always at a leaf node
II. The second largest element in a max-heap is always a child of the root node
III. A max-heap can be constructed from a binary search tree m q(n) time
IV. A binary search tree can be constructed from a max-heap in q(n) time
Which of the above statements are TRUE?

Solution:

I. is TRUE, Smallest element always found at the leaf node.
II. second largest element is always present as children of the root
III. given a BST we can construct a Max heap using hepify in θ(n) time
IV. worst case time required to build a BST is O(n2)

QUESTION: 53

Consider three machines M, N, and P with IP address 100.10.5.2, 100.10.5.5, and 100.10.5.6. respectively. The subnet mask is set to 255.255.255.252 for all the three machines. Which one of the following is true?

Solution:

IP addresses for the given 3 machines as follows:

Subnet address calculation for all 3 machines is…..
Machine (M)

Machine (N)

Machine (P)

Since, (2) and (3) are same, N and P are belongs to the same subnet.
∴ Option (D) is correct.

QUESTION: 54

Consider the following sets:
S1. Set of all recursively enumerable languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet {0,1}
S4. Set of all non-regular languages over the alphabet {0,1}
Which of the above sets are uncountable?

Solution:

S1. Recursive enumerable language is accepted by TM and there are Countable number of TM possible.
S2. Countable. Given a length l, and a finite number of characters, c, we know that each length has only finitely many possible valid c codes cL. We can easily make a bijection from the natural numbers to the lengths, and at each length we add only finite number of other valid code, thus countable.
S3. The Number of language over ∑ is uncountable
S4. Non-regular language is Uncountable

QUESTION: 55

Let G be any connected, weighted, undirected graph.
I. G has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimumweight edge crossing the cut.
Which of the above two statements is/are TRUE?

Solution:
QUESTION: 56

Consider three 4-variable functions f1 , f2 , and f3 , which are expressed in sum-of-minterms as

For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as:

Solution:

It means overall minterm of F should be either minterm of (f1. f2) or minterm of f3.

Minterm 2 and 14 is common in all three functions.
So, it shouldn‟t be in overall functions minterm.
These are not present only in option (A).
So, overall minterm =∑ ( 7, 8,11)

QUESTION: 57

Consider the following snapshot of a system running n concurrent processes. Process i is holding
i X instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Yi additional instances of R while holding the Xi instances it already has. Of the n processes, there are exactly two processes p and q such that Yp = Yq= 0. which one of  the following conditions guarantees that no other process apart from p and q can complete execution ?

Solution:

Both the Processes p and q have no additional requirements and can be finished releasing Yp +Yq
resources
So, option A just ensures that the system can proceed from the current state. It doesn‟t guarantee that there won‟t be a deadlock before all processes are finished.
Hence, option (A) is correct.

*Answer can only contain numeric values
QUESTION: 58

A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60-MHz clock. To service a cache miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch all the eight words of the block, and finally transmits the words of the requested block at the rate of 1 word per cycle. The maximum bandwidth for the memory system when the program running on the processor issues a series of read operations is _____  ×  106 bytes/sec.

Solution:

To accept the starting address = 1 cycle
To fetch all eight words – 3 cycles
To transmits the words of the requested block at the rate of 1 word per cycle- 8cycles
Total 12 cycles required

Bandwidth is =160 * 106 bytes/sec

*Answer can only contain numeric values
QUESTION: 59

Consider the augmented grammar given below:

Let I0 = CLOSURE ({[S' → •S]}). The number of items in the set GOTO (Io , <) is:________

Solution:

*Answer can only contain numeric values
QUESTION: 60

Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:

These processes are run on a single processor using preemptive shortest remaining time first scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is ________.

Solution:

Gantt Chart:

*Answer can only contain numeric values
QUESTION: 61

Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink port.The minimum number of switches needed is______________.

Solution:

∴ To connect 15 machines in a LAN using 8-port Ethernet switches, we require 3 switches.

QUESTION: 62

Consider the first order predicate formula φ :

Here ' a | b' denotes that „a divides b‟ where a and b are integers. Consider the following sets:
S1 {1, 2, 3, .....,100}
S2 Set of all positive integers
S3 Set of all integers
Which of the above sets satisfy φ ?

Solution:

It says that for all prim number x there exist a prime number greater than x
Where x and y are prime numbers
So for S1 = {1, 2,…..100}
For prime number 97 this is not TRUE
But S2 and S3 are infinite sets
For S2 and S3 it is always TRUE
So S2 and S3 satisfy φ.

*Answer can only contain numeric values
QUESTION: 63

Consider the following C program
#include <stdio.h>
int main() {
int a[] = {2, 4, 6, 8, 10};
int i, sum = 0, *b = a + 4;
for (i = 0; i < 5; i+d+ )
sum = sum + (*b - i) - *(b - i);
print f("%d\n",sum);
return 0;
}
The output of the above C-program is _______.

Solution:

Consider the array and assumed base address as 100 and size of the element is 2B

b is a pointer assigned to 108
for loop is running

Final Key is 10

QUESTION: 64

Suppose that in an IP-over Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?

Solution:

ARP is a network protocol used to find the Hardware (MAC) address of a host from an IP address.
It is a request reply protocol.
ARP request messages an used to request the MAC address, while
ARP request is sent to the broadcast address, the switch will flood the request out all interfaces. Every device on the LAN will receive the request, but only the device with the IP address will process it and sends an ARP reply message. Listing its MAC address.
Hence option (D) is correct.

*Answer can only contain numeric values
QUESTION: 65

What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of minterms form as f =∑( 0,1, 5, 7, 8,10,13,15) ? Assume that all the inputs and their complements are available.

Solution:

f =∑ ( 0, 2, 5, 7,8,10,13,15)

As per the questions their complemented and normal both type of inputs are available.
So,

Their equivalent circuit can be redrawn like.

Therefore, minimum number of NOR-gate = 3.