1. Which of the following is not the self balancing binary search tree?
a) AVL Tree
b) 2-3-4 Tree
c) Red – Black Tree
d) Splay Tree
Answer: b
Explanation:
2-3-4 Tree is balanced search trees. But it is not a binary tree. So, it is not a self balancing binary tree. AVL tree, Red-Black Tree and Splay tree are self balancing binary search tree.
2. The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.
a) O(n log n)
b) O(n)
c) O(n2)
d) O(log n)
Answer: a
Explanation:
The worst case running time of the binary tree sort is O(n2). But, the worst case running time can be improved to the O(n log n) using a self – balancing binary search tree.
3. An AVL tree is a self – balancing binary search tree, in which the heights of the two child sub trees of any node differ by _________
a) At least one
b) At most one
c) Two
d) At most two
Answer: b
Explanation:
In an AVL tree, the difference between heights of the two child sub trees of any node is at most one. If the height differs by more than one, AVL tree performs rotations to balance the tree.
4. Associative arrays can be implemented using __________
a) B-tree
b) A doubly linked list
c) A single linked list
d) A self balancing binary search tree
Answer: d
Explanation:
Associative arrays can be implemented using a self balancing binary search tree as the worst-case time performance of self – balancing binary search trees is O(log n).
5. Self – balancing binary search trees have a much better average-case time complexity than hash tables.
a) True
b) False
Answer: b
Explanation:
For lookup, insertion and deletion hash table take O(1) time in average-case while self – balancing binary search trees takes O(log n). Therefore, hash tables perform better in average-case.
6. Which of the following is a self – balancing binary search tree?
a) 2-3 tree
b) Threaded binary tree
c) AA tree
d) Treap
Answer: c
Explanation:
An AA tree, which is a variation of red-black tree, is a self – balancing binary search tree. 2-3 is B-tree of order 3 and Treat is a randomized binary search tree. A threaded binary tree is not a balanced tree.
7. A self – balancing binary search tree can be used to implement ________
a) Priority queue
b) Hash table
c) Heap sort
d) Priority queue and Heap sort
Answer: a
Explanation:
Self-balancing binary search trees can be used to construct and maintain ordered lists, to achieve the optimal worst case performance. So, self – balancing binary search tree can be used to implement a priority queue, which is ordered list.
8. In which of the following self – balancing binary search tree the recently accessed element can be accessed quickly?
a) AVL tree
b) AA tree
c) Splay tree
d) Red – Black tree
Answer: c
Explanation:
In a Splay tree, the recently accessed element can be accessed quickly. In Splay tree, the frequently accessed nodes are moved towards the root so they are quick to access again.
9. The minimum height of self balancing binary search tree with n nodes is _____
a) log2(n)
b) n
c) 2n + 1
d) 2n – 1
Answer: a
Explanation:
Self – balancing binary trees adjust the height by performing transformations on the tree at key insertion times, in order to keep the height proportional to log2(n).
10. Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.
a) True
b) False
Answer: a
Explanation:
The worst case performance of binary tree sort is O(n log n) when it is implemented using a self balancing binary search tree. Self balancing binary search trees perform transformations to balance the tree, which caused balancing overhead. Due to this overhead, binary tree sort is slower than merger sort.
11. Using what formula can a parent node be located in an array?
a) (i+1)/2
b) (i-1)/2
c) i/2
d) 2i/2
Answer: b
Explanation:
If a binary tree is represented in an array, parent nodes are found at indices (i-1)/2.
12. Which of the following properties are obeyed by all three tree – traversals?
a) Left subtrees are visited before right subtrees
b) Right subtrees are visited before left subtrees
c) Root node is visited before left subtree
d) Root node is visited before right subtree
Answer: a
Explanation:
In preorder, inorder and postorder traversal the left subtrees are visited before the right subtrees. In Inorder traversal, the Left subtree is visited first then the Root node then the Right subtree. In postorder traversal, the Left subtree is visited first, then Right subtree and then the Root node is visited.
13. Which of the following is the predefined function for array reversal in javascript?
a) reverse()
b) arr_reverse()
c) array_reverse()
d) rev()
Answer: a
Explanation:
The predefined function for reversing an array is reverse() in javascript. It does not requires any argument.
14. Predefined function reverse() in C++ is available under which header file?
a) math
b) stdio
c) stdlib
d) algorithm
Answer: d
Explanation:
The predefined function for reversing an array is reverse() in C++ which comes under the library called an algorithm. It requires 2 arguments the first being the pointer to the starting index of the array and the second being the pointer to the last index of the array.
15. What is the time complexity of the juggling algorithm to rotate an array?
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
Answer: b
Explanation:
Time complexity of juggling algorithm is O(n). Its auxiliary space complexity is O(1).
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
Answer: a
Explanation:
Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity
