1. Select the code snippet which performs in-order traversal.
a)
public void inorder(Tree root)
{
System.out.println(root.data);
inorder(root.left);
inorder(root.right);
}b)
public void inorder(Tree root)
{
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}c)
public void inorder(Tree root)
{
System.out.println(root.data);
inorder(root.right);
inorder(root.left);
}d)
public void inorder(Tree root)
{
inorder(root.right);
inorder(root.left);
System.out.println(root.data);
} Answer: b
Explanation:
In-order traversal follows LNR(Left-Node-Right).
2. Select the code snippet which performs level-order traversal.
a)
public static void levelOrder(Tree root)
{
Queue queue=new LinkedList();
queue.add(root);
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.left!=null)
queue.add(tempNode.left);
if(tempNode.right!=null)
queue.add(tempNode.right);
}
}b)
public static void levelOrder(Tree root)
{
Queue queue=new LinkedList();
queue.add(root);
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.left!=null)
queue.add(tempNode.right);
if(tempNode.right!=null)
queue.add(tempNode.left);
}
}c)
public static void levelOrder(Tree root)
{
Queue queue=new LinkedList();
queue.add(root);
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.right!=null)
queue.add(tempNode.left);
if(tempNode.left!=null)
queue.add(tempNode.right);
}
}d)
public static void levelOrder(Tree root)
{
Queue queue=new LinkedList();
queue.add(root);
while(!queue.isEmpty())
{
Node tempNode=queue.poll();
System.out.println("%d ",tempNode.data);
if(tempNode.right!=null)
queue.add(tempNode.left.left);
if(tempNode.left!=null)
queue.add(tempNode.right.right);
}
} Answer: a
Explanation:
Firstly add the root node to the queue. Then for all the remaining nodes, pop the front end of the queue and print it, add the left and right children of the popped node to the queue.
3. What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)
Answer: d
Explanation:
In the worst case we have d stack frames in the recursive call, hence the complexity is O(d).
4. What is the time complexity of level order traversal?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer: a
Explanation:
Since you have to go through all the nodes, the complexity becomes O(n).
5. Which of the following graph traversals closely imitates level order traversal of a binary tree?
a) Depth First Search
b) Breadth First Search
c) Depth & Breadth First Search
d) Binary Search
Answer: b
Explanation:
Both level order tree traversal and breadth first graph traversal follow the principle that visit your neighbors first and then move on to further nodes.
6. In a binary search tree, which of the following traversals would print the numbers in the ascending order?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal
Answer: d
Explanation:
Left subtree is traversed first in post-order traversal, then the right subtree is traversed and then the output current node.
7. To obtain a prefix expression, which of the tree traversals is used?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal
Answer: b
Explanation:
As the name itself suggests, pre-order traversal can be used.
8. Consider the following data and specify which one is Preorder Traversal Sequence, Inorder and Postorder sequences.
S1: N, M, P, O, Q
S2: N, P, Q, O, M
S3: M, N, O, P, Q
a) S1 is preorder, S2 is inorder and S3 is postorder
b) S1 is inorder, S2 is preorder and S3 is postorder
c) S1 is inorder, S2 is postorder and S3 is preorder
d) S1 is postorder, S2 is inorder and S3 is preorder
Answer: c
Explanation:
Preorder traversal starts from the root node and postorder and inorder starts from the left child node of the left subtree. The first node of S3 is different and for S1 and S2 it’s the same. Thus, S3 is preorder traversal and the root node is M. Postorder traversal visits the root node at last. S2 has the root node(M) at last that implies S2 is postorder traversal. S1 is inorder traversal as S2 is postorder traversal and S3 is preorder traversal. Therefore, S1 is inorder traversal, S2 is postorder traversal and S3 is preorder traversal.
9. How many orders of traversal are applicable to a binary tree (In General)?
a) 1
b) 4
c) 2
d) 3
Answer: d
Explanation:
The three orders of traversal that can be applied to a binary tree are in-order, pre-order and post order traversal.
10. If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?
a) 2i+1
b) 2i+2
c) 2i
d) 4i
Answer: a
Explanation:
If binary trees are represented in arrays, left children are located at indices 2i+1 and right children at 2i+2.
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
