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 11
1. Consider
a situation where the data to be sorted is too big to fit in memory, so most of
it is on disk. Which of the following
is the best algorithm to sort such data?
a) Insertion sort
b) Heap sort
c) Merge sort
d) All of the above
Click here to view answer and explanation
Ans : (c)
Answer: (c) Merge
sort
External
sorting is required when the data being sorted do not fit into the main
memory. Merge sort is a “not inplace” sorting algorithm which is wellsuited
for sorting data in secondary storage.

2. Consider
a large data set, where all the data has only one of about 10 values for
sorting purposes (e.g., the data is records of employees of an organization where
the legal age range is 25 to 60 and the sort is by age in years). Which of the following is the best algorithm
to sort such data?
a) Insertion sort
b) Bucket sort
c) Merge sort
d) Heap sort
Click here to view answer and explanation
Ans : (b)
Answer: (b) Bucket
sort
Bucket
Sort is a type of sorting algorithm in which the individual elements of the
input array are distributed into several groups which are known as buckets. The
advantage of bucket sort is that once the elements are distributed into
buckets, each bucket can be processed independently of the others. This means
that you often need to sort much smaller arrays as a followup step than the
original array. It also means that you can sort all of the buckets in
parallel with one another.

3. Given
a dataset, we would like to sort the first k smallest (k is much smaller than
the size of the dataset) in ascending order. Which of the following is the best algorithm to sort such data?
a) Insertion sort
b) Selection sort
c) Merge sort
d) Bucket sort
Click here to view answer and explanation
Ans : (b)
Answer: (b) Selection
sort
Selection
sorting is a simple solution to sort such a dataset. Selection sort divides the
given dataset into two subarrays (left subarray as sorted (initially all
elements are considered as unsorted) and right subarray as unsorted). It
then finds the smallest element from the unsorted array, swap that with the
leftmost element in the unsorted array and mark the index up to the leftmost
element as sorted. This process can be continued until the first k elements
are sorted.

4. If
h is any hashing function chosen from universal collection of hash functions and
is used to hash n keys in to a table of size m, where n<=m, the expected
number of collisions involving a particular key x is
a) <m
b) <n
c) < half of n
d) <1
Click here to view answer and explanation
Ans : (d)
Answer: (d) <1
The
method of choosing the hash function randomly in a way that is independent of
the keys that are actually going to be stored is referred as universal
hashing.
Refer
here for the proof of answer. Universal hashing

5. Which
among the following is a technique of direct search?
a) Binary search
b) Linear search
c) Hash search
d) All of the above
Click here to view answer and explanation
Ans : (c)
Answer: (c) Hash
search
Hashing
directly points to the index or location where the desired value(s) stored.
If you input the key to be searched in the hash function, the output will be
the index or location of the data.

*************************
Interview questions and answers in data structure and algorithms
DSA quiz questions with answers explained
Why merge sort is well suited for out of main memory data
Practice questions in data structures
Data structures and algorithms GATE exam questions
Merge sort is good for sorting the data in secondary storage
Which sorting algorithm is good at sorting first k smallest elements ?
What is universal collection of hash functions?