Suppose you had to write a method to delete all of the nodes of a binary tree. I

Question

Suppose you had to write a method to delete all of the nodes of a binary tree. If your method was passed a reference to the root of the tree, which traversal method would your algorithm use. a) inorder traversal b) preorder traversal c) postorder traversal d) any of the above e) none of the above could possible be used A bubble sort of 1000 elements requires a maximum of _____ passes. a) 1001 b) 1000 c) 999 d) 998 A sorted array of a million elements can be searched by a binary search in _____ or fewer comparisons. a) 10 b) 20 c) 30 d) 999, 999 What are the time requirements for straight selection sort? a) O(n) b) O(n^2) c) O(n^2/2) d) O((n^2 - n)/2) How does the insertion sort work? a) Each iteration takes the next smallest element and inserts it at the beginning of the array. b) Each iteration takes the next element in the unsorted portion of the array and inserts it into the sorted portion. c) Sorted subarrays are inserted into the larger array. d) Each iteration determines the location of a pivot and inserts it into place.

Explanation / Answer

1.To delete all nodes of a binary tree first we have to delete left and right child of each nodes, then the corresponding node. Hence , we should use postorder traversal.

2.In bubble sort in every pass one element is pushed to its correct position( like in the first pass max element is copied to the last position, and so on). So after n-1 passes all elements will be in its correct position. Hence, 999 passes in the worst case.

3. in binary search every time the array is split in 2 parts and depending on the search element(its less than or greater than the middle element) we search only one part . So no of comparisons in the worst case= log base 2 1000000=19.93. Hence, 20 or fewer comparisons.

12. O(n2)

In selection sort, in every iteration we select the min/max element from the unsorted array and place it in the correct position.

So complexity=(n-1)+(n-2)+................+1 = O(n2)

13.b) In insertion sort ,in each itearion we take one element from the unsorted portion of the array(selecting index wise) and place it in the sorted portion of the array (after finding its correct position in the sorted array).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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