Select all the statements below which are TRUE. Let L be a doubly-linked list wi

Question

Select all the statements below which are TRUE.

Let L be a doubly-linked list with n elements. Then finding the successor of an element x takes (n) in the worst-case.

The Heap sort algorithm uses divide-and-conquer approach.

Let A be a max-heap of height h. In the worst-case h = (n).

The Heap sort algorithm is more efficient than the Insertion sort algorithm.

Counting sort is a comparison sort algorithm.

In a min-heap A, for every node i (n-1)/2 the value A[i] A[2i] and A[i] A[2i+1].

Let L be a doubly-linked list with n elements. Then finding the successor of an element x takes (n) in the worst-case.

The Heap sort algorithm uses divide-and-conquer approach.

Let A be a max-heap of height h. In the worst-case h = (n).

The Heap sort algorithm is more efficient than the Insertion sort algorithm.

Counting sort is a comparison sort algorithm.

In a min-heap A, for every node i (n-1)/2 the value A[i] A[2i] and A[i] A[2i+1].

Explanation / Answer

Answer:

Let L be a doubly-linked list with n elements. Then finding the successor of an element x takes (n) in the worst-case. : TRUE

Reason:

Sucessor means next element. In worst case, we have to traverse all the n elements to match with x and finding its suceessor. So it will take (n) time.

-----------------------------------------------------------------

The Heap sort algorithm uses divide-and-conquer approach. : FALSE

Reason: It is using heap property and constructs heap.After constrcution element one element will be removed at a time without violating heap property. Here no divide and conquer method is used.

------------------------------------------------------------------

Let A be a max-heap of height h. In the worst-case h = (n).: FALSE

------------------------------------------------------------------
The Heap sort algorithm is more efficient than the Insertion sort algorithm. :TRUE

Reason: heap sort finds the next largest element using heap easily and takes O(log n) time, instead of O(n) for Insertion sort. Also insertion sort needs shifting all flollowing elements over by one. So heap sort is efficient

-------------------------------------------------------------------

Counting sort is a comparison sort algorithm.: FALSE

Reason: It is not a comparision sort. It uses actual values of elements to index into an array. It counts number of elements less than the element and place it instead of actual elements.

--------------------------------------------------------------------

In a min-heap A, for every node i (n-1)/2 the value A[i] A[2i] and A[i] A[2i+1].:TRUE
--------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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