Saturday, December 26, 2020

Multiple choice questions in Data structures and algorithms with answers set 09

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


Data Structures and Algorithms Multiple Choice Questions

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

b) Quadratic time

c) Linear time

d) Logarithmic time

Answer: (c) Linear 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

Answer: (b) Pos-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.

 

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

Interview questions and answers in data structure and algorithms

DSA quiz questions with answers explained

Solved true or false questions in DSA

Practice questions in data structures

Data structures and algorithms GATE exam questions 

Why insertion sort is a in-place sorting algorithm?

Why do we refer selection sort as in-place sorting algorithm?

What is the time complexity of converting min heap into a max heap?

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


1 comment:

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...

All time most popular contents

data recovery