PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2020

26 What is the worst case time complexity of inserting n² elements into an AVL Tree with n elements initially?

Insertion of an element into AVL requires O(log n) time.
To insert an element
1. Find the position, where to insert
2. After insertion, to satisfy AVL properly, we may need to perform rotation.
So, (1) take ‘log n time’ and (2) take ‘log n’ time.
Total time for inserting one element into AVL tree is
log n + log n = 2 log n ⇒ O (log n).
Now, To insert n² elements ⇒ n² log n
⇒ O(n² log n)

27 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, _________”.

w(u, v)=(u, v ) edge weight
w′(u, v) = w(u, v) + [f(u) - f(v)]/0 = w (u, v)
So, option (A) correct.

28 Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.

∀x (p(x) → W) ⇒ (∀x p(x)) → W is wrong
∀ x [(px) → W] ≡ ∀x [∼P(x) ∨ W]
≡ ∀x [∼P(x) ∨ W]
≡ ∼ [∃x p(x)] ∨ W)
≡ ∃x p(x)] → W

29 Consider the Boolean function z(a, b, c).

Which one of the following minterm lists represents the circuit given above?

z = a + bc
solving it with K-map

∴ Minterms will be
= ∑m(1, 4, 5, 6, 7)

30 A computer system with a word length of 32 bits has a 16 MB byte-addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider the following four physical addresses represent hexadecimal notation.
A1 = 0×42C8A4, A2 = 0×546888,
A3 = 0×6A289C, A4 = 0×5E4880
Which one of the following is TRUE?

Word length = 32 bit, MM size = 16 MB
Physical address = 24 bit, CM size = 64 KB
4-way set associative
Block size = 256 B
Number of lines (N) = 64K/256 = 2¹⁶/2⁸ = 2⁸
Number of sets (S) = N/P-way = 2⁸/4 = 2⁶

i = 0	i = 1	i = 2
ex = 3 x 3	ex = 9 x 3	tot = t * t *ex
= 9	= 81	= 1 * 81 = 81

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2020

Follow Us :