1. For a binary tree if in-order traversal is = DGBAHEICF and pre-order = ABDGCEHIF. Its post-order traversal would be:
A: ABCDEFGHI
B: GCIEHABFD
C: GIHECFDBA
D: GDBHIEFCA
Select one:
A
B
C
D
Ans: D
2. Which of the following statement is correct:
A: A max tree is always a complete binary tree.
B: A min heap can never be a complete binary tree.
C: A min heap can or cannot be a complete binary tree.
D: A max heap is always a complete binary tree.
Select one:
A
B
C
D
Ans: D
3. A one thousand character long data file comprises of only 3 characters A, B and C in the occurrence frequency of 600, 300 and 100 respectively. If these characters are stored in 2, 3, and 4 bit long codes respectively what will be the saving as compared to ASCII storage?
A: 31.25%
B: 53.55%
C: 68.75%
D: 46.45%
Select one:
A
B
C
D
Ans: C
4 . A Binary Search Tree is constructed using integers (in the given sequence): 98, 34, 100, 35, 97, 33, 0 and -12. The post-order traversal of this binary tree will be:
A: 0, -12, 33, 35, 97, 34, 100, 98
B: -12, 0, 33, 97, 35, 100, 34, 98
C: -12, 0, 33, 97, 35, 34, 100, 98
D: 98, 0, 35, 97, 33, 34, 100, -12
Select one:
A
B
C
D
Ans: C
5. In a Binary Search Tree, if a node is deleted which has two sub-trees. After deletion, the following can replace the deleted node:
(1) Largest node on the left sub-tree of the deleted node.
(2) Smallest node on the left sub-tree of the deleted node.
(3) Smallest node on the right sub-tree of the deleted node.
(4) Largest node on the right sub-tree of the deleted node.
Select one:
A. 1 and 2 only.
B. 1 and 3 only
C. 1 and 4 only.
D. All of the above
Ans: B
Reference: “Deletion starategy is the following: replace the node being deleted with the largest node in the left subtree and then delete that largest node. By symmetry, the node being deleted can be swapped with the smallest node is the right subtree.”
6. Which one of the following statement is correct about Weight Biased Leftist Trees (WBLT)?
A: If x is an internal node, its weight is 1 more than the sum of the weights of its children.
B: If x is an internal node, its weight is 1 more than the max of the weights of its left and right children.
C: If x is an internal node, its weight is 1 more than the min of the weights of its left and right children.
D: None of these.
Select one:
A
B
C
D
Ans: A (Based on Rishab & Venkata SBP)
7. Given the infix expression as ( (A / (B-C+D)) * (E-A) *C). The postfix expression would be:
A: ABC-/D+EA-*C*
B: ABC-D+/EA-*C*
C: ABCD+/-EA*C*-
D: ABCD+/-EA-*C*
Select one:
A
B
C
D
Ans: B
8. Which of the following statement is correct?
A: A full binary tree is always perfect binary tree also.
B: A complete binary tree is always full.
C: A perfect binary tree is always full and complete.
D: A left skewed binary tree is complete because all the children are on the left side.
Select one:
A
B
C
D
Ans: C
9. Level-1 up Splay step is possible for a Splay node only when this node is at level-2 of the binary tree.
Select one:
True
False
Ans: True
10. If there are 4 nodes in a binary tree. Total number of branches/links = x and out them y would be NULL branches. What are values of x and y respectively?
A: 3, 5
B: 8, 5
C: None of these
D: 4, 5
Select one:
A
B
C
D
Ans: B
11. A student tries to solve the problem of optimum packing of big boxes with small boxes using binary search trees so that the big boxes' space is best utilized. He uses the best fit approach. The big boxes are equal in size and shape but their holding capacities are: A (9 Kg), B (15 Kg), C (12 Kg) and D (8 Kg). Small boxes are equal in size and shape but their weights are 10, 3, 2, 9, and 15 Kg respectively. After packing all the small boxes into big boxes, which is (are) the box(es) left out with what unused capacity?
A: C (2 Kg), D (3 Kg)
B: D, 5 Kg
C: No box will be left out with unused capacity
D: None of the above
Select one:
A
B
C
D
Ans: A (Based on Anju Abhi & Venkata SBP )
12. The in-order traversal of a Splay Tree is 1, 2, 3, 4, 5 and the pre-order traversal is 4, 2, 1, 3, 5. The last binary tree operation that was performed on this Splay tree was search(3). What will be the level order traversal of the Splay tree after this search?
A: 3, 2, 1, 4, 5
B: 3, 2, 4, 1, 5
C: 3, 1, 4, 2, 5
D: None of the above
Select one:
A
B
C
D
Ans: B
13. A min heap is constructed using integers (in the given sequence): 98, 34, 100, 35, 97, 33, 0 and -12.The level order traversal of this binary tree will be:
A: -12, 0, 33, 35, 97, 100, 98, 34
B: -12, 33, 0, 35, 97, 100, 34, 98
C: -12, 0, 33, 35, 97, 100, 34, 98
D: -12, 0, 35, 98, 97, 33, 100, 34
Select one:
A
B
C
D
Ans: C
14. Individual operations are inexpensive in a Splay Tree but a sequence of operations is more expensive than a corresponding AVL tree.
Select one:
True
False
Ans: False
15. If a min heap is stored in an array. The array will be be automatically sorted in non-decreasing order.
Select one:
True
False
Ans: False
16. Which of the following statement is correct about Height Biased Leftist Trees (HBLT):
A: For any internal node x in HBLT, shortest (x) = 1 + min { shortest(leftChild (x)), shortest(rightChild (x)) }
B: For any internal node x in HBLT, shortest (x) = 1 + max { shortest(leftChild (x)), shortest(rightChild (x)) }
C: For any internal node x in HBLT, shortest (x) = min { shortest(leftChild (x)), shortest(rightChild (x)) }
D: They will always be complete.
Select one:
A
B
C
D
Ans: A
17. Which one of the following statement is correct?
A: HBLT are normally referred to as Leftist Trees.
B: There is no advantage of using leftist trees over heaps.
C: HBLT operations are analogous with the operations of Binary Search Tree.
D: None of these.
Select one:
A
B
C
D
Ans: A
18. It is not possible to come up with an algorithm to assign n jobs to m machines to finish the assignment as soon as possible because:
A: The algorithm will have a time complexity of non-deterministic polynomial.
B: There is no available data structure to attempt the assignment.
C: There is no way to verify the solution.
D: None of the above.
Select one:
A
B
C
D
Ans: A (based on Anju Abhi & rishab)
19. Which of the following statement is incorrect for a binary tree? i and h >=1 and ^ is the exponent operator.
A: The maximum number of nodes on level i = 2^i-1
B: The maximum number of nodes on level i = 2^(i-1)
C: The maximum number of nodes in a binary tree of height h is = 2^h-1
D: The number of nodes in a binary tree of height h is can be less than 2^h-1
Select one:
A
B
C
D
Ans: A
20. MAR, MAY, NOV and AUG are added into an empty AVL search tree in the given sequence. After all the nodes are inserted, the post-order traversal of the balanced AVL tree will be:
A: MAR, MAY, NOV, AUG
B: NOV, MAY, MAR, AUG
C: AUG, MAR, NOV, MAY
D: AUG, MAR, MAY, NOV
Select one:
A
B
C
D
Ans: C
No comments:
Post a Comment