17) Which of the following is a valid bimary search tree 6 of 7 23 43 50 23 40 5

Question

17) Which of the following is a valid bimary search tree 6 of 7 23 43 50 23 40 50 40 50 18) What is the wost-case nuatime of searching for a value in a binary search tree (a) constant o(l) b) logarithmie Ollogn) ) linear O Page 6/72 COMP 1006/1406- Summer 2017 Sample Final 19) Suppose we are sorting the list t3, 10, , 12, 6. 9. 11, 5). weuse quicksort and the ist partition value is 10, which of the following could NOT be the ondering of the list after this fist partitionin (a) [3. 4, 5, , , 10, 11, 12 (b) 19. 6,5, 4. 3. 10, 12 11 (c) (3, 4,5, 6, 9. 11, 10. 12 20) Cosider insertion soet, qaicksort and mergnsoet. Which has the most efficient wurst-ca time? (a) insertion set (b) quicksoet (s) mergesort

Explanation / Answer

Question : 17

Option b is a valid binary search tree.

Explanation : Binary Search Tree is a tree in which all the tree nodes followos the below rules

Question : 19

option c is could not be the ordering.

Reason : Quick sort simply divide the list with partition element into two parts .

i.e) elements list lessthan partition element ,partition element, elements list greaterthan partition element.

In the given options ,option c violates that rule.(11,10,12)

The left sub-tree of a node has a value less than or equal to its parent node's value.

The right sub-tree of a node has a value greater than to its parent node's value.

i.e) Left(k) <= Root(k) < Right(k) ,This applicable to each and every node in tree.

This above rule is violated in option a(41 node is placed in left tree of node 40 ,It is violates above rule), option c(27 node is placed in left tree of root node 23 ,It is violates above rule).

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.