Q1. What is the worst case efficiency for a path compression algorithm?.
A. O(N).
B. O(log N).
C. O(N log N).
D. O(M log N).
Answer= O(M log N)
Q2. Does path compression algorithm work during?.
A. Create operation.
B. Insert operation.
C. Find operation.
D. Delete operation.
Answer= Find operation
Q3. What is the definition for Ackermann's function?.
A. A(1,i) = i+1 for i>=1.
B. A(i,j) = i+j for i>=j.
C. A(i,j) = i+j for i = j.
D. A(1,i) = i+1 for i<1.
Answer= A(1,i) = i+1 for i>=1
Q4. ___________ is one of the earliest forms of a self-adjustment strategy used in splay trees, skew heaps..
A. Union by rank.
B. Equivalence function.
C. Dynamic function.
D. Path compression.
Answer= Path compression
Q5. What is the depth of any tree if the union operation is performed by height?.
A. O(N).
B. O(log N).
C. O(N log N).
D. O(M log N).
Answer= O(log N)
Q6. When executing a sequence of Unions, a node of rank r must have at least 2r descendants..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q7. What is the value for the number of nodes of rank r?.
A. N.
B. N/2.
C. N/2r.
D. Nr.
Answer= N/2r
Q8. What is the worst-case running time of unions done by size and path compression?.
A. O(N).
B. O(log * N).
C. O(N log N).
D. O(M log* N).
Answer= O(M log* N)
Q9. In the Union/Find algorithm, the ranks of the nodes on a path will increase monotonically from?.
A. leaf to root.
B. root to node.
C. root to leaf.
D. left subtree to right subtree.
Answer= leaf to root
Q10. How many strategies are followed to solve a dynamic equivalence problem?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 2
Q11. What is the total time spent for N-1 merges in a dynamic equivalence problem?.
A. O(N).
B. O(log N).
C. O(N log N).
D. O(M log N).
Answer= O(N log N)
Q12. What is the condition for an equivalence relation if two cities are related within a country?.
A. the two cities should have a one-way connection.
B. the two cities should have a two-way connection.
C. the two cities should be in different countries.
D. no equivalence relation will exist between two cities.
Answer= the two cities should have a two-way connection
Q13. What is the use of the bin data structure?.
A. to have efficient insertion.
B. to have efficient deletion.
C. to have efficient region query.
D. to have efficient traversal.
Answer= to have efficient region query
Q14. Bin is an example of a range query data structure..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q15. What is the worst case time complexity of query operation(n is the no. of candidates)?.
A. O(1).
B. O(n).
C. O(log n).
D. O(n log n).
Answer= O(n)
Q16. What is the worst case time complexity of delete operation(n is the no. of candidates)?.
A. O(1).
B. O(n).
C. O(log n).
D. O(n log n).
Answer= O(n)
Q17. What is the worst case time complexity of insertion operation(n =no. of candidates)?.
A. O(1).
B. O(n).
C. O(log n).
D. O(n log n).
Answer= O(1)
Q18. What is computational geometry?.
A. study of geometry using a computer.
B. study of geometry.
C. study of algorithms.
D. study of algorithms related to geometry.
Answer= study of algorithms related to geometry
Q19. What will be the time complexity of query operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (k = number of bins query rectangle intersects).
A. O(1).
B. O(k).
C. O(k2).
D. O(log k).
Answer= O(k)
Q20. What will be the time complexity of delete operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects).
A. O(1).
B. O(m).
C. O(m2).
D. O(log m).
Answer= O(m)
Q21. What will be the time complexity of insertion operation if all the candidates are evenly spaced so that each bin has constant no. of candidates? (m = number of bins intersecting candidate intersects).
A. O(1).
B. O(m).
C. O(m2).
D. O(log m).
Answer= O(m)
Q22. Efficiency of bin depends upon ___________.
A. size of query and candidates.
B. location of query and candidates.
C. location and size of query and candidates.
D. depends on the input.
Answer= location and size of query and candidates
Q23. Bigger the query rectangle the better is the query efficiency..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= FALSE
Q24. In what time can a 2-d tree be constructed?.
A. O(N).
B. O(N log N).
C. O(N2).
D. O(M log N).
Answer= O(N log N)
Q25. Insertion into a 2-d tree is a trivial extension of insertion into a binary search tree..
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q26. In a two-dimensional search tree, the root is arbitrarily chosen to be?.
A. even.
B. odd.
C. depends on subtrees.
D. 1.
Answer= odd