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. |
Thanks for this beneficial article...
ReplyDelete