PREVIOUS YEAR SOLVED PAPERS - GATE 2020
- Option : A
- Explanation : 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 n2 elements ⇒ n2 log n ⇒ O(n2 log n)
- Option : A
- Explanation : 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.
- Option : B
- Explanation : ∀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
∴ Minterms will be
= ∑m(1, 4, 5, 6, 7)- Option : C
- Explanation : 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 = 216/28 = 28
Number of sets (S) = N/P-way = 28/4 = 26
