Choose True or false, and give justification. 1. The worst-case height of a bina

Question

Choose True or false, and give justification.

1. The worst-case height of a binary search tree is O(log n).

2. A preorder traversal of a binary heap yields the keys in non-decreasing order.

3. The quicksort algorithm described in code fragment 11.5 on page 506 is stable. (A sorting
algorithm is stable if it preserves the original order of equal keys in the sequence.)

4. Depth-first search can be run on a tree with n vertices in O(n) time.

5. If e is a minimum-weight edge of a connected undirected graph G, then Kruskal's algorithm
will always include e in the MST it constructs.

Explanation / Answer

1) False : Incase of Skew tree its O(n)

2) False : Because Heap does not follow search property

3) False : Quicksort is not stable because it swaps two non-adjacent elements

4) False : Worst Case Complexity of dfs is O(|E| + |V|)

5) True : Since Kruskal's algorithm is a greedy algorithm

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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