1. How many child nodes does each node of K-ary Tree contain?
a) 2
b) 3
c) more than k
d) at most k
Answer: d
Explanation:
Each node of K-ary tree contains at most k nodes. While tree with 2 nodes is called Binary tree and tree with 3 nodes is called Ternary tree.
2. Which of the following is the name of the node having child nodes?
a) Brother
b) Sister
c) Mother
d) Parent
Answer: d
Explanation:
Parent node is the node having child nodes and child nodes may contain references to their parents. Parent node is a node connected by a directed edge to its child.
3. What is the depth of the root node of K-ary tree?
a) 2
b) 1
c) 0
d) 3
Answer: c
Explanation:
Depth is defined as the length of the path from root to the node. So the depth of root node in K-ary tree is 0.
4. What is the Height of the root node of K-ary tree?
a) 1
b) 2
c) 3
d) 0
Answer: d
Explanation:
Height of K-ary tree is defined as the length of path from root to deepest node in tree. Therefore, height of root node in K-ary tree is 0.
5. Can leaf node be called child node in a K-ary tree?
a) True
b) false
Answer: a
Explanation:
Leaf node is a node that has no child. Since Leaf node will always be the node on the last level of k-ary tree, so it can be called child node of given parent node in K-ary tree.
6. Can child node be always called Leaf node in the K-ary tree?
a) True
b) False
Answer: b
Explanation:
Leaf node is any node that does not contain any children. Child node may or may not contain more nodes. Child node will only be called leaf Node if the node has no child node.
7. What is the upper bound for maximum leaves in K-ary tree with height h?
a) K*h
b) K^h
c) K+h
d) K-h
Answer: b
Explanation:
In the K-ary tree having height h, the upper bound for having maximum number of leaves is k^h.
8. What is the height of a K-ary tree having only root node?
a) 1
b) 0
c) 2
d) 3
Answer: b
Explanation:
Height of a K-ary tree does not include the root node. So the height of the K-ary tree is without root node is 0.
9. Which one of the following is the correct formulae to find the parent node at index I?
a) (I-1)/K
b) (I+1)/K
c) (I*1)/K
d) (I-2)/K
Answer: a
Explanation:
The parent node for the node of index I in a K-ary tree is given by (I-1)/K.
10. How many extra nodes are there in Full K-ary tree than complete K-ary tree?
a) 1
b) 2
c) 3
d) Both have same number of nodes
Answer: a
Explanation:
In order to perform the splitting on the rope data structure, one can split the given string into two new string S1 and S2 in O (log n) time. So, the time complexity for worst case is O (log n). The split operation can be performed if the split point is either at the end of the string or in the middle of the string.
11. Which operation is used to break a preferred path into two sets of parts at a particular node?
a) Differentiate
b) Cut
c) Integrate
d) Join
Answer: b
Explanation:
A preferred path is broken into two parts. One of them is known as top part while other is known as bottom part. To break a preferred path into two sets, cut operation is used at a particular node.
12. What is the upper bound for a tango tree if k is a number of interleaves?
a) k+2 O (log (log n))
b) k O (log n)
c) K2 O (log n)
d) k+1 O (log (log n))
Answer: d
Explanation:
Upper bound is found to analyze the work done by a tango tree on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).
13. What is the time complexity for searching k+1 auxiliary trees?
a) k+2 O (log (log n))
b) k+1 O (log n)
c) K+2 O (log n)
d) k+1 O (log (log n))
Answer: d
Explanation:
Since each search operation in the auxiliary tree takes O (log (log n)) time as auxiliary tree size is bounded by the height of the reference tree that is log n. So for k+1 auxiliary trees, total search time is k+1 O (log (log n)).
14. What is the time complexity for the update cost on auxiliary trees?
a) O (log (log n))
b) k-1 O (log n)
c) K2 O (log n)
d) k+1 O (log (log n))
Answer: d
Explanation:
The update cost also is bounded by the upper bound. We perform one cut as well as one join operation for the auxiliary tree, so the total update cost for the auxiliary tree is found to be k+1 O (log (log n)).
15. Which of the following is the self-adjusting binary search tree?
a) AVL Tree
b) Splay Tree
c) Top Tree
d) Ternary Tree
Answer: b
Explanation:
Splay tree is a self – adjusting binary search tree. It performs basic operations on the tree like insertion, deletion, loop up performing all these operations in O (log n) time.
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
