Please visit, subscribe and share 10 Minutes Lectures in Computer Science

# Data structures and algorithms multiple choice questions with answers, important interview questions in data structures, data structures questions for entrance exams, frequently asked questions in data structures and algorithms, GATE questions in data structures with explained answers

## SET 09

1. Which among the following comparison sorts are in-place sorts?

a) Bucket sort

b) Insertion sort

c) Selection sort

d) Parallel merge sort

Answer: (b) Insertion sort and (c) Selection sort

What is in-place sort?

### An in-place sort is one that sorts the input without requiring additional space.

A sort algorithm in which the sorted items occupy the same storage as the original ones. A sorting algorithm that uses a small constant amount of extra space in addition to the original input, usually overwrite the input space, is referred as in-place sorting. [Refer here for more, what is in-place sort].

Insertion Sort is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position. [Refer here for more, Wikipedia. ]

The selection sort algorithm finds the smallest (or largest, depending on sorting order) element in the unsorted sub-list, exchanges it with the leftmost unsorted element (putting it in sorted order), and moves the sub-list boundaries one element to the right without any additional space. [Refer here more more - Wikipedia, Selection sort]

### 2. A max heap can be converted into a min heap in ________.

a) Exponential time

c) Linear time

d) Logarithmic time

### Building a min heap on any array will take linear time. Hence, converting a max heap array into min heal will take the same time.

Min heap is a special binary tree where the value stored in the parent node is less than or equal to the children and max heap is a tree where the parent is larger than or equal to the children.

3. To delete a dynamically allocated tree, the most suitable traversal technique is ________.

a) Pre-order

b) Post-order

c) In-order

d) Level-order

### To delete a dynamically allocated tree, we can delete children first and then the parent.

We will traverse the tree by using post Order traversal because we have to delete all child nodes first before deleting root node. If we delete root node first then we cannot traverse child nodes of root without maintaining a separate data store.

*************************

### Why do we say that the post-order traversal as suitable traversal technique to delete a dynamically allocated binary tree?

#### 1 comment:

1. Thanks for this beneficial article...

## Featured Content

### Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

data recovery