Campus and Interview preparation with Data Structure

Important topic of  Data Structure    :-

• Stack

• Queue

• Linked List

• Sorting

• Heap

• Tree

• AVL Tree

• Hashing

• C language questions

• C ++ Language questions

campus/interview preparation

Objective type questions or multiple choice questions (MCQ) are often asked in various exams, including job recruitment tests. It also helps in understanding language constructs, syntax and fundamental rules.click the link given in above list to go to that topic.

Sorting in Data Structure

1. 

Select the sorting that always has a time complexity O(n2 ),irrespective of the condition of array.

(a) Bubble sort
(b) Selection sort
(c) Quick sort
(d) Merge sort

Answer

(b) Selection sort

Bubble sort can have O(n) time complexity if elements are already sorted.
Quick sort and merge sort have time complexity of O(nlogn ) (though worst case complexity of Quicksort is O(n2).
While selection sort always have O(n2 ) complexity. It is pretty obvious because if we look at the logic of selection sort then we select the minimum element at every iteration and replace it with the current position’s element. Whatever be the case, we need to make a complete iteration to find minimum. Thus its complexity cannot be reduced.

2. You have to sort a list L consisting of a sorted list followed by a few “random” elements.
Which of the following sorting methods would be especially suitable for such a task?

(a) Bubble sort
(b) Selection sort
(c) Quick sort
(d) Insertion sort

Answer

(d) insertion sort

Bubble sort can be modified -if all the elements are sorted then no swaps will occur and thus count of swaps=0, which signifies that array is sorted. But in this question there are some elements at the end which are not sorted .So eventually we need to have whole iteration again and again.
Selection sort-It always makes full iteration irrespective of the condition of array.
Quicksort –It will not help as quicksort will choose a random pivot which may disturb sorted part of list L.
Insertion sort-Insertion sort is suitable in this case. If the list is already almost sorted, every time we compare list’s next element it is greater than previous element resulting in no swaps or iteration. Thus no work will be done for sorted part. Only movement for unsorted part would be done.

3. Which of the following sorting algorithms does not have a worst case running time of O(n2 )?

(a) Insertion sort (b) Merge sort
(c) Quick sort (d) Bubble sort

Answer

(b) merge sort

Insertion, Quick and bubble all have worst case time complexity of O(n2).Only merge sort has the worst case running time of O(nlogn).

4. Which of the following sorting methods would be most suitable for sorting a list which is almost sorted

(a) Bubble Sort (b) Insertion Sort
(c) Selection Sort (d) Quick Sort

Answer

(a)Bubble sort

In bubble sort once the array becomes sorted say after 2 or 3 iterations, we do not need to make further iterations if we use modified bubble sort.Thus it is best for almost sorted list.
While other algorithms will give O(n2).Quick sort also doesn’t perform well for sorted lists.

5. Quick sort is also known as

(a) Merge sort (b) Heap sort
(c) Bubble sort (d) Partition exchange sort

Answer

(d) Partition exchange sort

Since quicksort requires partitioning using a pivot element thus it is also known as partition exchange sort.

6. Which of the following sorting algorithm is stable

(a) insertion sort. (b) bubble sort.
(c) quick sort. (d) heap sort.

Answer

(d)

An algorithm is said to be stable if two equal elements appear in the same order in output(sorted objects list) as they appear in input list(unsorted list)
For ex- If we have 5 elements -4, 7, 2, 8, 2
For our understanding, let’s rename sequence as 4, 7, 2(first occurrence), 8, 2(second occurrence)
Then after sorting we will get 2, 2, 4, 7, 8 .But which 2 came first? Which 2 is this? 2(first occurrence) or 2(second occurrence) .If they are in the same order as input ,then such algorithms are called stable algorithm else unstable algorithm.

7. The worst case of quick sort has order

(a) O(n2) (b) O(n)
(c) O (n log2 n) (d) O (log2 n)

Answer

(a)

Quick sort has worst case time complexity as O (n2)

8. Which of the following is not an in-place sorting algorithm?

(a) Selection sort
(b) Heap sort
(c) Quick sort
(d) Merge sort

Answer

(d)

If in any step , no auxiliary space is required to sort the elements then such an algorithm is called in-place sorting algorithm.

9. Which of the following is a comparison sort?

(a) Counting sort
(b) Bucket sort
(c) Radix sort
(d) Shell sort

Answer

(d) Shell sort

All other options name the sorting algorithms which do not require the comparison of elements for sorting.

10. The time complexity of heap sort in worst case is

(a) O(logn)
(b) O(n)
(c) O(nlogn)
(d) O(n2)

Answer

( c)

Heap sort is O(nlogn) even in worst case.

If this article is helpful to you so please like share and comments.. Thank you..