1. Let T be a Binary Search Tree (BST) with n keys. Select all the statements be
ID: 3891511 • Letter: 1
Question
1. Let T be a Binary Search Tree (BST) with n keys. Select all the statements below which are TRUE.
If the BST T has height 3, then the maximum number of nodes in T is 16.
The first element printed by the POSTORDER-TREE-WALK(T.root) is the smallest key of T.
For any node x, if y is a node in the right subtree of x,and z is a node in the left subtree of x, then y.key ? z.key.
2. Consider the matrix chain A1A2A3, where A1 has dimension 20 × 10, A3 has dimension 10 × 5 and A2 has dimension 5 × 3. Which of the following parenthesizations require the minimum number of scalar multiplications?
This chain of matrices cannot be parenthesized because the sequence of matrices is incompatible.
A tree is balanced if all the leaves have the same depth. The height of a balanced BST T is .
O (1gn)Explanation / Answer
Q1
The first option is correct
The second option is incorrect as the max nodes can be 1+2+4+8=15
The third option is incorrect as inorder traversal prints it in sorted order
The fourth option is correct as all the elements are inserted in sorted manner
This option is wrong in accordance with above option
This sixth option is correct
The seventh option is also correct
Q2
A2A3 will result in 10x3 matrix and then there will be 5*5*10*3+20*10*10*3 multiplications.
A1A2 will result in 20x5 matrix and total multiplications will be 20*10*10*5+20*5*5*3
Hence (A1(A2A3)) has lesser number of multiplications.
Do give a thumbs up
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.