1.Suppose we insert the numbers 32, 57, 43, 20, 28, 67, 41, 62, 91, 54 in this o
ID: 3890567 • Letter: 1
Question
1.Suppose we insert the numbers 32, 57, 43, 20, 28, 67, 41, 62, 91, 54 in this order into an initially empty binary search tree, and we do not do any restructuring. How many leaves does the final binary search tree have?
A: 4.
B: 5
C: 6
D: 7
In the same setting as the previous question, how many nodes are in the subtree rooted at the node for element 57 (including that node itself)?
A: 4.
B: 5
C: 6
D: 7
Suppose that a binary search tree contains a subset of numbers between 1 and 100, and we search for 65. Then the element 65 is compared to a sequence of numbers along the search path. Which of the following sequences is impossible to occur, i.e. there is no binary search tree for which the search will encounter this sequence.
A: 32, 44, 63
B:40, 93, 53, 61
C :35, 72, 43, 57, 74
D:81, 21, 40, 72, 63
The height of a rooted tree is the maximum number of edges on a path from the root to a leaf. Recall that the time needed to perform a search on a binary search tree is O(height) (to be precise, the number of comparisons is equal to height+1 in the worst case), and the same holds for all the other operations we discussed in the lecture. What is the minimum possible height of a binary search tree with 1000 nodes?
A:8
B:9
C: 10
D: 11
Explanation / Answer
The following are the answers:
1) B: 5
2) D: 7
3) C: 35, 72, 43, 57, 74
4) C: 10
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.