Sorting Interview Questions Part 1

1.Which of the following algorithms can be used for sorting large data sets based on time complexity?
a. Bubble sort b. Merge sort c. Heap sort d. Quick sort
Ans:c
Heap sort does not require massive recursion or multiple arrays.


2. Which of the following algorithms is the slowest
a. Bubble sort b. Merge sort c. Quick sort d. Heap sort
Ans:a
The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items


3.The sorting algorithms belonging to quadratic complexity includes
a. bubble sort b. insertion sort c .selection sort d. All the above
Ans:d
4. The sorting algorithms not having complexity O(n log n)includes
a. heap sort b. quick sort c. bubble sort d.merge sort
Ans: a

5.An algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted,directed graph..
a.Dijkstra’s b.Prim’s c. Kruskal d.none of the above
Ans:a

6.Time complexity of Dijkstra’s algorithm
a.O(VlogV) b.O(E+VlogV) c.O(ElogV) d.none of the above
Ans:b

7.In the time complexity O(E+VlogV) V is the number of _____
Ans:vertices

8.In the time complexity O(E+VlogV) E is the number of _____
Ans:edges

9.In Dijkstra’s algorithm,all weights must be nonnegative(T/F)
Ans:True

10.A step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps is called
a.Structure b.Queue c.Algorithm d.Data structure
Ans:c


11.Big O notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:a


12. θ notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:c

13.Ω notation is used for
a.Asymptotic upper bound
b. Asymptotic lower bound
c. Tight bound
d.none of these
Ans:b



14.For inplace sorting no extra memory is required.(T/F)
Ans:True

15.Which of the following do not use inplace sorting
a.Selection b.Bubble c.Insertion d.Merge
Ans: d

16.The operations which directly affect the output of an algorithm are ______
Ans:Key operations

17.Number of times a key operation executes is
a.Complexity b.Frequency count c.Time d.None
Ans:b

18.What are the advantages of sorting
a.Used in algorithms as a key subroutine.
b.Used for engineering issues.
c.Both
d.None
Ans:c


19.A sorting technique where some of the records are in auxiliary storage is
a.Internal sorting
b.External sorting
c.inplace sorting
d.Non inplace sorting
Ans:b

20.A sorting technique where the records are in main memory is
a.Internal sorting
b.External sorting
c.inplace sorting
d.Non inplace sorting
Ans:a

21.Each item in a file is called a record.(T/F)
Ans:True

22.A sort takes place either on the records themselves or on an auxiliary table of pointers.(T/F)
Ans:True

23.Suppose the amount of data stored in the records is so large that the overhead involved in moving the actual data is prohibitive,then the auxiliary table of pointers may be used so that these pointers are moved instead of the actual data,this is called _______
Ans:sorting by address

24.Which of the following is applicable for any constant ‘c’
a.c=O(1)
b.c=O(logn)
c.c=O(nlogn)
d.c=O(n)
Ans:a