Following questions have been asked in GATE CS 2007 exam.
1.
Answer (B)
Please see for closed hashing and probing.
2..
Answer(D)
*|)
Answer (C)
For an n-ary tree where each node has n children or no children, following relation holds
L = (n-1)*I + 1
Where L is the number of leaf nodes and I is the number of internal nodes.
Let us find out the value of n for the given data.
L = 41 , I = 10 41 = 10*(n-1) + 1 (n-1) = 4 n = 5
4. In the following C function, let n >= m.
int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); }
How many recursive calls are made by this function?
(A) Θ(logn)?
(B) Ω(n)
(C) Θ(loglogn)
(D) Θ(sqrt(n))
Answer (A)
Above code is implementation of the Euclidean algorithm for finding Greatest Common Divisor (GCD).
Please see for time complexity.
5. What is the time complexity of the following recursive function:
int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); }
(A) Θ(n)
(B) Θ(nlogn)
(C) Θ(logn)
(D) Θ(loglogn)
Answer (D)
Recursive relation for the DoSomething() is
T(n) = T(√n) + C1 if n > 2
We have ignored the floor() part as it doesn’t matter here if it’s a floor or ceiling.)
Please see GATE Corner for all previous year paper/solutions/explanations, syllabus, important dates, notes, etc.
Please write comments if you find any of the answers/explanations incorrect, or you want to share more information about the topics discussed above.
Recommended Posts:
- Data Structures and Algorithms | Set 12
- Data Structures and Algorithms | Set 10
- Data Structures and Algorithms | Set 23
- Data Structures and Algorithms | Set 13
- Operating Systems |.