Searching &Sorting

Q1. Consider the array A [] = {10, 5, -3, 15, 2, 0, -9}.

If we perform bubble sort on A then what is the status of array A after three
passes?
(a) 0, 2, -3, -9, 5, 10, 15
(b) -3, 5, 10, 15, 2, 0, -9
(c) -3, 2, 0, -9, 5, 10, 15
(d) -3, 0, 2, -9, 5, 10, 15
Answer: C
Solution:
A = {10, 5, -3, 15, 2, 0, -9}
10 5 -3 15 2 0 -9
pass 1 5 -3 10 2 0 -9 15
pass 2 -3 5 2 0 -9 10 15
pass -3 2 0 -9 5 10 15
C is correct.
Q2. [MSQ]
If one uses the bubble sort algorithm to sort the given array in ascending order,
then in which of the following pairs the data values will not interchange during
the first pass?
Input array: {2,6,5, 3, 7, 8, 1, 9, 4}.
(a) 2,6 (b) 6, 3
(c) 7, 8 (d) 7, 1
Answer: A, C, D
Solution:
Input array: {2, 6, 5, 3, 7, 8, 1, 9, 4}.
After pass 1: 2 5 3 6 7 18 4 9
In this pass, pair (3, 6) interchanged.
so out of the given option pair (2, 6), (7, 1)& (7, 8) have no possibility to get
changed during pass 1.
So, answer is A C &D.

BASIC DATA STRUCTURE AND ALGORITHMPage 1

Q3. Consider the following two implementation of bubble sort?
Implementation I Implementation II
VoidSort1 (int arr [], int n) VoidSort2(intarr [], int n)
{ {
for (i = 0; i < n-1; i++) if (n > 1) {
for (j = 0; j < n-i-1; j++) for (int i=0; i<n-1; i++)
if (arr[j] >= arr[j+1]) if (arr[i] >arr[i+1]) swap(arr[i],
swap(arr[j], arr[j+1]); arr[i+1]);
} Sort2(arr, n-1);
}
}
Which of the above implementation is/are stable?
(a) Only I (b) Only II
(c) Both I and II (d) neither I nor II
Solution:
I: if(a[i] > = a[j+1]
the line, swap the equal data. (When a[j] = a[j+1])
It is not stable.
II is stable.
Answer B
Q4. The total numbers of swaps performed by Bubble sort on array
A[] = {7, 20, 16, 9, 18, 17, 22, 4} till the 3rd pass, is ________
Answer: 9
Solution: 7, 20, 16, 9, 18, 17, 22, 4

BASIC DATA STRUCTURE AND ALGORITHMPage 2

 Number of swaps after 1st pass = 5.

number of swaps=3

Number of swaps=1
Total number of swaps performed after the 3rd pass = 5+3+1 = 9Answer is 9.
Q5. The number of swapping needed to sort the numbers 8,23,7,9,32, 20,5,13 in
ascending order using bubble sort is
Answer:14
Solution:
Pass I II III IV V VI VII
Number of swaps 5 4 2 1 1 1 0
So, total number of swaps = 5 + 4 + 2 + 1 + 1 + 1 + 0 = 14
Q6. If we have given a sorted array A[] = {1, 2, 3 … n} and we want to sort this array
using Bubble sort (not modified bubble sort), then how many swapping are
performed?
(a)0 (b) (𝑛 − 1)
(c) 𝑛(𝑛 − 1)/2 (d) 𝑛
Answer: A
Solution:
If array is already in a sorted sequence, then there will be zero swapping.
Q7. If we have given a sorted array A [] = {1, 2, 3 … n} and we want to sort this array
using Bubble sort (not modified bubble sort), then how many key comparisons
are performed?
(a)0 (b) (𝑛 − 1)

BASIC DATA STRUCTURE AND ALGORITHMPage 3

 (c) 𝑛(𝑛 − 1)/2 (d) 𝑛
Answer: C
Solution:Since bubble sort is not modified,
 In pass 1 there will be (n – 1) comparison, in pass 2 (n – 2) comparison and
so till last pass there will be 1 comparison.
Pass 1 2 ………… n–2 n–1
Comparison n–1 n–2 ………… 2 1
Total comparison: 1 + 2 + . . .. + (n – 1) + (n – 2)
𝑛 (𝑛−1)
The sum of above series is=
2

 (C) is correct.
Q8. If we have given a sorted array A [] = {1, 2, 3 … n} and we want to sort this array
using Modified bubble sort then how many key comparisons are performed?
(a)0 (b) (𝑛 − 1)
(c) 𝑛(𝑛 − 1)/2 (d) 𝑛
Answer: B
Solution: Since this time our bubble sort is modified and the array is already
sorted. Therefore, there will be just one pass & we know in first pass there are
(n – 1) key comparison.
Data for next four questions: Consider an algorithm to sort the array of size n:
void sort (int A [], int n)
{
int i, j, temp1, temp2;
for (i = 0; i < n – 1; i++) /*-------1stloop-------*/
{
temp1 = i;
for (j= i +1; j< n; j++) /*------- 2ndloop-------*/
{
if (A[j] <A[temp1])
temp1 =j;
}
/*--swap elements--*/
temp2 = A[temp1];
A[temp1] = A[i];
A[i] = temp2;
}
}
Q9. The above algorithm performs
(a)Insertion Sort
(b) Selection sort
(c) Bubble sort

BASIC DATA STRUCTURE AND ALGORITHMPage 4

 (d) Algorithm unable to sort the array
Solution:
This code is for selection sort „temp 1‟ variable is used as a min variable and
„temp2‟
is used for swapping.
Answer is B
Q10. If array contains 6, 12, 7, 4,13,8 elements then how many array elements are
compared by above code? _________
Answer: 15
Solution:

for i =0, temp1=0

PassI:- 5 comparisons of array elements

Pass II:- 4 comparisons

Pass III:- 3 comparison
Pass II:- 2 comparisons
PassI:- 1 comparisons
Total number of comparisons = 5+4+3+2+1 = 15
Q11. If array contains 6,12,7,4,13,8 elements then after 4thiteration of 1stloop in
above code the status of array will be
(a) 4, 12, 7, 6, 13, 8 (b)4, 6, 7, 8, 12, 13
(c)4, 6, 7, 12,13, 8 (d) 4, 6, 7, 8, 13, 12

BASIC DATA STRUCTURE AND ALGORITHMPage 5

 Answer: D
Solution: -
6 12 7 4 13 8
Pass I:- min = 6

Pass II :-

Pass III:-

After 3rditeration, status of array will be –

4, 6, 7, 12, 13 8
Pass IV:

Answer is D.
Q12. If array contains 6,12,7,4,13, 8 elements, then after sorting how many times
variable „temp1‟ will be changed in 1st loop? __________________

BASIC DATA STRUCTURE AND ALGORITHMPage 6

 Solution: 8

6,12,7,4,13,8
When a[j]< min then „temp I‟ will be changed in loop 2.

Pass I: -

II:-

Result: 4 6 7 8 8 12 13
temp1 will change for each i =0 to 4 and, in 2ndloop 3 times changed.
Required number of ways= 5+3=8.
Answer is 8

For next three questions: consider the follow array:

[38, -5, 47, 55, 1, 68, 16, 96, -80, 7]
Each of the following is sequence a view of a sort in progress of the above array.
Q13. [-80, -5, 1, 55, 47, 68, 16, 96, 38, 7]
Select suitable /appropriate sorting technique.
(A) Bubble Sort (B) Selection Sort
(C) Insertion Sort (D) Quick Sort
Answer: B
Solution:
As in selection sort, after each pass smallest element starts taking their actual

BASIC DATA STRUCTURE AND ALGORITHMPage 7

 position. Obvious and appropriate choice would be option (B).
Q14. [-5, 38, 1, 47, 16, 55, -80, 7, 68, 96]
Select suitable /appropriate sorting technique.
(a)Bubble Sort (b) Selection Sort
(c) Insertion Sort (d) Quick Sort
Answer: A
Solution:
We know in bubble sort, with each pass, largest element take their actual
position in sorted sequence.
 Appropriate choice is (a).
Q15. [-5, 38, 47, 55, 1, 68, 16, 96, -80, 7]
Select suitable /appropriate sorting technique.
(a) Selection Sort (b) Bubble Sort
(c) Insertion Sort (d) Quick Sort
Answer: C
Solution:
Given array:
38, -5, 47, 55, 1, 68, 16, 96, -80, 7
Array after some passes of some sorting technique:
-5, 38, 47, 55, 1, 68, 16, 96, -80, 7
First two element swapped position & rest of the array remains unchanged.
This usually happens in insertion sort.
Q16. Assume that we‟re using selection sort on the array {5, 3, -1, 7, 4, 2, 0}. What
would be the state of the array after secondpass of selection sort?
(a){-1, 3, 5, 7, 4, 2, 0} (b){3, -1, 5, 4, 2, 0, 7}
(c){-1, 0, 5, 7, 4, 2, 3} (d){-1, 0, 3, 5, 7, 4, 2}
Answer: C
Solution: Array: {5, 3, -1, 7, 4, 2, 0}
I pass of selection sort:
5, 3, -1, 7, 4, 2, 0
mm = 5, 3, -1
-1, 3, 5, 7, 4, 2, 0
II pass:min = 3, 2, 0
-1, 0, 5, 7, 4, 2, 3
Answer is (C)

BASIC DATA STRUCTURE AND ALGORITHMPage 8

Q17. Consider the following code:
void doDomething (int vals [], int length)// length is
size of array
{
int k;
for (j = 0; j <(length – 1); j++)
{
k = vals [j];
i = j-1;
while(i> 0 && vals[i] > k)
{
vals [i + 1] = vals [i];
i = i – 1;
}
vals [i + 1] = k;
}
}
When called with the array [6, 4, 3, 1], what are the contents of „vals‟ at the end
of each outer for loop?
(a) [1, 6, 4, 3] [1, 3, 6, 4] [1, 3, 4, 6]
(b) [4, 6, 3, 1] [3, 4, 6, 1] [1, 3, 4, 6]
(c) [6, 4, 3, 1] [6, 4, 3, 1] [6, 3, 4, 1]
(d) [6, 4, 3, 1] [6, 3, 4, 1] [6, 1, 3, 4]
Answer: C
For J = 0;
K = val[j] = val[0]=> k = 6
we won’t go inside while loop as i is not greater than 0.
After first iteration of outer loop, array is [6, 4, 3, 1]
For J = 1;
K = val[j] = val[1]=> k = 4
i=0
we won’t go inside while loop as i is not greater than 0.
After first iteration of outer loop, array is [6, 4, 3, 1]

BASIC DATA STRUCTURE AND ALGORITHMPage 9

 Hence option (a), (b) and (d) are eliminated Therefore ans is (C)
Q18. Selection sort is sort is used to sort the following array (with A[0] shown as the
left-most value)in ascending order: 5, 15, 14, -3, 10, 11, 7, and 2. After 4
passes what will be status of array (min always from L.H.S.)?
(a) -3, 5, 10, 11, 14, 15, 7, 2
(b) -3, 5, 14, 15, 10, 11, 7, 2
(c) -3, 2, 5, 14, 10, 11, 7, 15
(d) -3, 2, 5, 7, 10, 11, 14, 15
Solution: D

5, 15, 14, -3, 10, 11, 7, 2

After 4th path status of array will be

-3 2 5 7 10 11 14 15
Answer is D

Q19. What is the maximum number of exchanges required to order an array of 5

elements using the selection sort? ___________

BASIC DATA STRUCTURE AND ALGORITHMPage 10

 Answer: 4
Solution:
In selection sort, with each pass there happens atmost one swap.
So, with array of 5 elements, there will be 4 passes & with each pass there will
be 1 swap atmost.
Maximum there will be 4 swaps (exchange).
Q20. What is the minimum number of exchanges required to order an array of 5
elements using the selection sort? _________
Answer: 0
Solution:Refer the solution of Q.19
If array is already sorted, there will be 0 swap.
Q21. Which of the following algorithm pays the least attention to the ordering of the
elements in the input list?
(a) Insertion sort (b)Selection sort
(c)Quick sort (d)Bubble sort
Solution: Selection sort is not stable.
Answer is B
Q22. In a selection sort of n elements, how many times is the swap function called in
the complete execution of the algorithm?
(a)n (b) n – 1
(c) n log n (d) n²
Solution: In selection sort each i =1 to n-1 swap function is called.
 Required number of calls= n-1
Answer is B

BASIC DATA STRUCTURE AND ALGORITHMPage 11

Q23. Consider the following code for sorting the array „arr‟ of size „n‟:
void NewSort (int arr [], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
The above code is equivalent to which of the following sorting techniques?
(a) Insertion sort
(b)Selection sort
(c)Quick sort
(d)Bubble sort
Answer: A
Solution:
Take small example array like {3, 2, 1}
and run above code
3 2 1
key = array [1] = 2
j=0
pass 1: 2 3 1
key = array [2] = 1
j=1
pass 2: 1 2 3
You might observe this works like insertion sort.

BASIC DATA STRUCTURE AND ALGORITHMPage 12

Q24. What would be the worst-case time complexity of the insertion sort algorithm, if
the inputs are restricted to permutation of 1, 2…n with at most n inversion?
(a) θ (n2) (b) θ (nlogn)
(c) θ (n1.5) (d) θ (n)
Solution: Worst time complexity of the insertion sort algorithm
= number of elements + number of inversions = n+n=2n=(n)
Answer is D

Q25. What is the number of element comparisons performed by insertion sort when
applied to arrays of size N that are already correctly sorted?
(a) N – 1 (b)N – 2
(c) N (d) N2 – 1
Answer: A
Solution:Take example
1 2 3 4 5 6 7 8

pass 2: 1 2 3 4 5 6 7 8
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - --
There will be 7 passes & 7 comparisons.
 There will be (N – 1) passes for n elements.
Hence N – 1 comparison.

Q26. You have given an array A [] = {12, 11, 10, 9 … 3, 2, 1}. An inversion in an array
a is a pair of array indices (i, j) such that i < j but a[i] > a[j]. Assume the index of
array is starting from 0. What is the maximal number of inversions that can be
eliminated by the following program fragment? __________
if (i < j && a[i] > a[j])
{
temp = a [5];
a [5] = a [10];
a [10] = temp;
}
Answer: 9
Solution:
There are 66 inversions

BASIC DATA STRUCTURE AND ALGORITHMPage 13

 temp = a [ 5]  temp = 7
a [5] = a [10]  a [5] = 2
a [10] = temp  a [10] = 7

After running given code snippet, we have 57inversions.

Hence 9 inversions eliminated.
Q27. How many inversions will be there to sort the following array in increasing
order?
Given Array A[] ={10, 9, 7, 8, 12, 6, 1}
Solution:

Total number ofinversions=5+4+2+2+2+1=16

Answer is 16.

BASIC DATA STRUCTURE AND ALGORITHMPage 14

Q28. Consider the following array and we are performing acomparison-based sorting
technique. The status of the array in different passes are shown below:

Then which of the following sorting techniques is used above?

(a)Bubble Sort (b) Selection sort
(c) Insertion Sort (d) Heap Sort
Answer: C
Solution:
In each pass we can see comparison & shifting is taking place.
we can tell that the technique used is insertion sort.

Q29. [MSQ]
Which of the following is not the status of array after some iteration(of outer
loop)of a sorting algorithm, which sorting algorithm it might be?
-5 2 19 53 44 91 87 35
(a) Heap sort (b) Bubble sort
(c) Selection sort (d)Insertion sort
Answer: A
Solution: Bubble sort can be possible because if we move right to left in outer
loop then minimum element will be at 1st position.
Insertion and selection sort both can be possible because 1st two elements are
sorted.
If we create heap using the given elements then it is neither max-heap nor min-
heap. So, Heap sort is not possible.

BASIC DATA STRUCTURE AND ALGORITHMPage 15

Q30. [MSQ]
Which of the following is/are the status of array after some iteration (of outer
loop) of a sorting algorithm, which sorting algorithm it might be?
12 40 17 70 13 10 7-1
(a) Heap sort
(b) Bubble sort
(c) Selection sort
(d) Insertion sort
Answer:B, C, D
Solution:
12 40 17 70 13 10 7 -1
If we create heap using the given elements then it is neither max-heap nor min-
heap. So, Heap sort is not possible.
Bubble sort and Selection can be possible because if we sort the given array
into descending order then the smallest element will be at last index of the
array.
Insertion sort can be possible because 1st two elements are sorted.

Q31. [MSQ]
Which of the following is/are the status of array after some iteration (of outer
loop)of a sorting algorithm, which sorting algorithm it might be?
29 35 44 114 37 30 28 46
(a) Heap sort
(b)Bubble sort
(c) Selection sort
(d) Insertion sort
Answer:D
It can‟t be bubble sort as neither smallest nor largest element is at its position.

It can‟t be selection sort as smallest element is not its place.

As insertion sort solves element from left to right and we can observe from
array that elements are sorted from left to right therefore this might be
insertion sort.

Ans D

BASIC DATA STRUCTURE AND ALGORITHMPage 16

Q32. Following is the status of array after some iteration (of outer loop) of a sorting
algorithm, which sorting algorithm it might be?
6 10 13 50 15 60 -1
(a) Heap sort
(b)Bubble sort
(c) Selection sort
(d) Insertion sort
Answer:B, C, D
Solution:
It can be bubble sort for decreasing order sorting, similarly it can be selection
sort, (reason same as bubble) and since array is sorted left to right till some
index, definitely it can be insertion sort.
Data for next two questions:
Examine the following sequence of some sorting algorithm to sort the array.
After Status of array
Pass
1st 5 7 15 1 20 25
2nd 5 7 1 15 20 25
3rd 5 1 7 15 20 25
4th 1 5 7 15 20 25
Q33. [MSQ]
Which sorting algorithm it might be?
(a)Bubble sort (b) Selection sort (c) Insertion sort (d) None of these
Answer: A
Solution:As after 1st pass, largest element is at its position. Similarly in second
pass second largest element is at its position & so on. This is property of bubble
sort.
Q34. [MSQ]
Which of the following status of array may be the initial status of array [before
pass 1]?
(a) 5, 7, 15, 20, 1, 25
(b) 7, 5, 15, 20, 1, 25
(c) 5, 15, 7, 20, 1, 25
(d) 5, 7, 15, 1, 20, 25

BASIC DATA STRUCTURE AND ALGORITHMPage 17

 Answer: a, b, c
Solution:
(a) 5, 7, 15, 20, 1, 25
pass 1: 5 7 15 1 20 25
True;
(b) 7, 5, 15, 20, 1, 25
pass 1: 5 7 15 1 20 25
True;
(c) 5, 15, 7, 20, 1, 25
pass 1: 5 7 15 1 20 25
True;
(d) 5, 7, 15, 1, 20, 25
pass 1: 5 7 15 1 20 25
False.

Q35. Consider the following code to perform insertion sort

void insertionSort (int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] >= key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
Which of the following is true about above code?
(a) It is both in-place and stable
(b) It is in place but not stable.
(c) It is not in-place but stable
(d) It is neither in-place nor stable
Answer: A
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 18

 Insertion sort is in-place and condition is′ ≥ ′ so it will make it non- stable.
Answer:B
Solution:

For our understanding let first „2‟ & 2b to second „2‟.

2a 2b 1 3
2a 2b 1 3
pass 1 2b 2a 1 3
pass 2 1 2b 2a 3
pass 3 1 2b 2a 3
Hence, we can see it is not stable but in place.
Q36. [MSQ]

Which of the following array representation is/are a min-heap?

(a) 11, 14, 12, 23, 5

(b) 2, 10, 3, 15, 11, 4, 5

(c) 10, 12, 3, 13, 16, 4, 5

(d) 3, 1, 2, 4, 5, 6, 0

Answer: B
Solution:
(a)

Not min heap.

(b)

BASIC DATA STRUCTURE AND ALGORITHMPage 19

 Min heap
(c)

It is not a min heap because 3 is child of 10.

(d)

Not a min heap.

Q37. Which of the following array representation is not a max-heap?

(a) 31, 14, 12, 2, 3, 25

(b) 12, 10, 3, 4, 5
(c) 10, 2, 3, 4, 5
(d) 6, 5, 2, 4, 3, 1
Answer:A, C
Solution:

(a)

BASIC DATA STRUCTURE AND ALGORITHMPage 20

 Not a max heap.

(b)

It‟s a max heap.

(c)

 Not max Heap.

(d)

BASIC DATA STRUCTURE AND ALGORITHMPage 21

 It„s a max heap.

Q38. Insert the following nodes in an empty Binary Max-heap (one by one) in the
order and apply heapifications if required.
30, 20, 10, 40, 50, 80, 70, 60.
The level order traversal of the binary max heap obtained above is
(a) 80, 40, 70, 20, 30, 10, 50, 60
(b) 80, 60, 70, 20, 30, 10, 50, 40
(c) 80, 60, 50, 70, 40, 20, 10, 30
(d) 80, 60, 70, 40, 30, 10, 50, 20
Answer: D
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 22

 Level: 80 60 70 40 30 10 50 20
Q39. Consider a max heap 9, 5, 8, 2, 3, 4, 1. If we delete root, then what is the
resulting array representation of the max-heap?
(a) [2, 3, 4, 5, 8, 1]
(b) [5, 8, 1, 2, 3, 4]
(c) [8, 4, 5, 3, 2, 1]
(d) [8, 5, 4, 2, 3, 1]

BASIC DATA STRUCTURE AND ALGORITHMPage 23

 Answer: D
Solution:
Max heap:

Swap root with node (1)

BASIC DATA STRUCTURE AND ALGORITHMPage 24

Q40. An array with no duplicate values is to be sorted into increasing order using
heap sort. Step one is to insert the elements of the array sequentially into a
max-heap. If the given array is 6 7 1 9 2 0 8, what will the contents of the max-
heap be after all the elements are inserted?

Answer: D
Solution:

Q41. [MSQ]
The elements 18, 32,15,20,30,12,25,16 are inserted one by one in the given
order into a MAX heap that is initially empty. Which of the following node(s)
does not lie in theright subtree of the root?
(a) 12 (b) 25
(c) 16 (d) 20
Answer: C, D
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 25

Q42. Minimum how many comparisons are required to convert the following array in
to max-heap? ________
Array: 4 2 1 3 5
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 26

 Therefore, no of comparison is 6.
Answer is 6
Q43. [MSQ]
Consider the following binary heap:

Suppose that the last operation performed in the binary heap above was
inserting the Keyx. Which of the following is/are possible value of x?
(a) 19 (b) 26 (c) 32 (d) 35
Answer: a, b, c, d

BASIC DATA STRUCTURE AND ALGORITHMPage 27

Q44. [MSQ]
Which of the following is/are true about the heap sort?
(a)heap sort is in-place.
(b)heap sort is stable.
(c)heap sort is more efficient than the merge sort in the average case.
(d)heap sort is better time complexity than the quick sort in the average case.
Answer: A
Solution: Heap sort is in-place but not stable.
Average case complexity of both Heap sort and Quick sort are same (O(n log n)).
So, only option A is true.
Q45. [MSQ]
Which of the following comparison sorts are in-place sorts? Select all that
apply.
(a) Selection Sort
(b) Heap Sort
(c) Merge sort
(d) Quick Sort
Answer: a, b, d
Solution:Merge sort is not in-place.
Q46. Suppose that we implemented a min heap. If we started with the min heap
pictured below, what key would be in the left child of the root after calling the
following two operations on it: Insert (7), delete_Min (). ___________

Answer: 7
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 28

 Insert 7
delete min ()
Delete min ()

Left child of root is (7).

Q47. What is the minimum and maximum number of nodes in the left-most sub tree
of the root of a 4-ary heap of height h when height of tree is start with 0?
4ℎ 4 ℎ −1
(a) 𝑀𝑖𝑛𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 + 1 𝑎𝑛𝑑 𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 =
3 3
4 ℎ −1 −1 4 ℎ −1
(b)𝑀𝑖𝑛𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 + 1 𝑎𝑛𝑑 𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 =
3 3
4 ℎ −1 4 ℎ −1
(c)𝑀𝑖𝑛𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 + 1 𝑎𝑛𝑑 𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 = +1
3 3
4 ℎ −1 4 ℎ −1
(d) 𝑀𝑖𝑛𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 + 1 𝑎𝑛𝑑 𝑀𝑎𝑥𝑖𝑚𝑢𝑚 𝑛𝑜𝑑𝑒 = −1
3 3

Answer: B
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 29

 Maximum node:- 5 (of left most subtree of root).
42 −1 15
so = =5
3 3

From the option.

and minimum.

42−1 −1 4−1 3
Minimum node of left most subtree of root is 2= +1= +1= + 1= 1+1= 2
3 3 3

Q48. What are the minimum and maximum number of nodes in the right-most sub
tree of the root of a 4-ary heap of height h, when height of tree is start with 0?
4ℎ 4 ℎ −1
(a)𝑀𝑖𝑛𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 + 1 𝑎𝑛𝑑𝑀𝑎𝑥𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 =
3 3
4 ℎ −1 4 ℎ −1
(b)𝑀𝑖𝑛𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 + 1 𝑎𝑛𝑑𝑀𝑎𝑥𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 =
3 3
4 ℎ −1 −1 4 ℎ −1
(c)𝑀𝑖𝑛𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 𝑎𝑛𝑑𝑀𝑎𝑥𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 =
3 3
4 ℎ −1 4 ℎ −1
(d) 𝑀𝑖𝑛𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 + 1 𝑎𝑛𝑑𝑀𝑎𝑥𝑖𝑚𝑢𝑚𝑛𝑜𝑑𝑒 = −1
3 3

Answer: C
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 30

 This is right most. Maximum node: In right most subtree of root 5.
4 ℎ −1 −1 16−1 15
= = = 5. From option answer is 5.
3 3 3

For minimum node: -

42−1 −1
minimum node in right most subtree of root is 1. So, from the operation =
3
4−1 2
= = =1 Answer:C
3 3

Q49. Consider a binary min heap of height 6. What is the sumof minimum and
maximum number of comparisons performed while deleting smallest element?
_________________ [Assume height is start from 1 and all elements are distinct]
Answer:14
Solution: In case of minimum: four comparisons are required.

BASIC DATA STRUCTURE AND ALGORITHMPage 31

 In the above min-heap, if we delete smallest element (from root) 1, then 12 will
reach at root. Then total four comparisons are required to heapify.
Compared pairs: (2, 6), (12, 2), (13, 14), (12, 13).

For maximum comparisons consider following min-Heap:

In the above heap, In the above min-heap, if we delete smallest element (from
root) 1, then 91 will reach at root. So, total compared pairs to heapify: (6, 2),
(91, 2), (9, 15), (9, 91), (10, 16), (10, 91), (11, 23), (11, 91), (12, 42), (12, 91).
So, total 10 comparisons are required.
So, required sum = 14.

BASIC DATA STRUCTURE AND ALGORITHMPage 32

Q50. What is the minimum and maximum number of nodes in a Binary min heap of
height 7? [Assume height is starting from 1]
(a) 63 and 127 (b) 63 and 128
(c) 64 and 127 (d) 64 and 128
Answer:C
Solution:

1+2+4+23+24+24+25+1=64
For maximum all element is present.
1+2+4+8+16+32+64=127
So, maximum element is 127.
Answer:C
Q51. If 5 is inserted into the heap below, and the heap condition is restored, into
which position will the 5 go?
i 0 1 2 3 4 5 6 7 8 9 10
A[i] 3 9 15 10 17 16 23 19 22 30 33

(a) A [0]
(b) A [1]
(c)A [2]
(d)A [5]
Answer:C

BASIC DATA STRUCTURE AND ALGORITHMPage 33

 5 will be at a[2]
(c) is correct.
Q52. The following sequence represents a max heap
60 40 50 35 32 30 20 34 10 25
What would be the content of the array after the 3rditeration of the heap-sort
algorithm (given below)?
Heapsort(A){
1. Build-Heap(A)
2. for i = length[A] down to 2 do
3. exchange A[1] , A[i]
4. heap-size[A] = heap-size[A] - 1
5. Heapify (A, 1)
}
(a)35 34 30 10 32 25 20 40 50 60
(b)50 40 30 35 32 25 20 34 10 60
(c)10 40 30 35 32 25 20 34 50 60
(d)10 20 30 32 25 34 40 50 35 60
Answer: A
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 34

 1st iteration: Swap A(1)and A(i)

Now reheapilfy from 1 to heapsize.

BASIC DATA STRUCTURE AND ALGORITHMPage 35

 Now, 2nd iteration:

BASIC DATA STRUCTURE AND ALGORITHMPage 36

 3rd iteration:

BASIC DATA STRUCTURE AND ALGORITHMPage 37

 So, sequence of array after 3rd iteration.
35, 34, 30, 10, 32, 25, 20, 40, 50, 60.
Answer:A
Q53. Suppose we are sorting an array of eight integers using heap (max heap) sort,
and we have just finished one of the re-heapifications downward. The array
now looks like this:6 4 5 1 2 7 8. How many maximum re-heapifications
downward have been performed so far?
(a)1 (b)2
(c) 3 or 4 (d)5 or 6
Solution: 6 4 5 1 2 7 8
In this array, last two element is sorted. Since we are using max-heap then
after two reheapification downward, we get above array.
Number of maximum re-heapifications=2
Answer is B

Q54. Given that an array of ten integers:4 3 8 9 1 7 0 2 6 5.

What will be status of array before the final merge step have occurred?
(a)3 4 8 9 1 0 2 6 5 7 (b) 0 1 2 3 4 9 8 7 6 5
(c) 1 3 4 8 9 0 2 5 6 7 (d) 0 1 2 3 4 5 6 7 8 9
Solution: Merge sort
4 3 8 9 1| 7 0 2 6 5
4 3|8 9 1| 7 0| 2 6 5
4 | 3 | 8| 9 | 1 | 7 | 0 | 2 | 6 |5
After merging before the final merge step,

BASIC DATA STRUCTURE AND ALGORITHMPage 38

 3 4 | 8 | 1 9| 0 7 | 2 | 5 6
3 4| 1 8 9| 0 7 |2 5 6
1 3 4 8 9| 0 2 5 6 7
This is, before the final merge step:
After this we will get sorted list using merge sort.
Answer is C
Q55. [MSQ]
If the number of records to be sorted is small, then ...... sorting can be efficient.
(a)Merge (b)Quick
(c)Selection (d)Bubble
Solution: Merge sort is not preferable as it is not “in place”. Quick sort is
complex as compare to bubble/selection sort.
Answer is C, D
Q56. In Merge Sort, there are two recursive calls to Merge Sort. They occur
(a) Before the merge step.
(b) After the merge step.
(c) One before and one after the merge step.
(d) During the merge step.
Answer: A
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = l+ (r-l)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
Q57. Consider the merge step used in Merge Sort. When two sorted sequences of
length n/2 are being merged, the worst-case time complexity of the merge
operation
(a)(lg(n)) (b) (n)
(c) (nlg(n)). (d) None of the above
(2017- 37)
Answer: B
(a) Create an array arr3 [] of size n1 + n2.
(b) Simultaneously traverse arr1 [] and arr2 [].

BASIC DATA STRUCTURE AND ALGORITHMPage 39

 Pick smaller of current elements in arr1 [] and arr2 [], copy this smaller
element to next position in arr3 [] and move ahead in arr3 [] and the
array whose element is picked.
(c) If there are remaining elements in arr1 [] or arr2 [], copy them also in arr3
[].
Let n = n1+n2.
Asymptotically time complexity will be O(n)
Q58. In the Merge Sort algorithm, what is the asymptotic running time of the step of
merging sorted subarrays?
(A)(log n) (B) (n)
(C) (nlog n) (D) (n2)
Answer: B
Refer Q57.

Q59. What is the efficient asymptotic running time to find the median of a sorted
array of size N?
(a)(n) (b) (log n)
(c) (1) (d) (n logn)
Answer: C
Median of a sorted array of size n is defined as the middle element when n is
odd and average of middle two elements when n is even. Which can be done
in O(1) time

Q60. To sort the array [5, 4, 3, 2, 1, 0] increasing, the first merge in Mergsort will
result in:
(A) [0, 4, 3, 2, 1, 5] (B) [2, 4, 3, 5, 1, 0]
(C) [5, 4, 3, 2, 0, 1] (D) [4, 5, 3, 2, 1, 0]
(2017-42)
Answer: D

BASIC DATA STRUCTURE AND ALGORITHMPage 40

 Therefore, answer will be D.
Q61. Suppose we are sorting an array of eight integers using quick sort, and we have
just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10. Which statement is correct?
(a) The pivot could be either the 7 or the 9.
(b)The pivot could be the 7 or 11, but it is not the 9.
(c) The pivot is not the 7, but it could be the 9.
(d) Neither the 7 nor the 9 is the pivot
Solution: Since, we have just finished the 1st partitioning and we get array 2 5 1
6 7 9 12 11 10 In this, pivot is their position(actual position).

The elements 7 or 9 or 11 are at own their position but 12 is before (left) the 11.
So, 11 cannot be pivot element.
Answer is A

Q62. Which of the following is not a limitation of binary search algorithm?

(a) must use a sorted array
(b) requirement of sorted array is expensive when a lot of insertion and
deletions are needed
© there must be a mechanism to access middle element directly
(d) binary search algorithm is not efficient when the data elements more than
1500.
Solution: Binary search doesn‟t depend on size of data.
Answer is D
Q63. Which of the following is not the required condition for binary search
algorithm?
(a)The list must be sorted

BASIC DATA STRUCTURE AND ALGORITHMPage 41

 (b)There should be the direct access to the middle element in any sub list
©There must be mechanism to delete and/or insert elements in list.
(d)Number values should only be present
Solution: “c” is not requirement for binary search algorithm.
Answer is C
Q64. The list 13 8 1 6 33 15 3 5 is to be sorted into ascending order using heap sort.
What is the maximum level of the binary tree that will be formed, given that the
root is at level 1?
(a) 1 (b) 2
©3 (d) 4
Solution:

Height is 4.

Q65. MSQ]
Which of the following statement is/are true?
(a) Given two heaps with n elements each, it is possible to construct a single
heap comprising all 2n elements in O(n) time.
(b) Building a heap with n elements can always be done in O(nlogn) time.

BASIC DATA STRUCTURE AND ALGORITHMPage 42

 (c) In a heap of depth d, there must be at least 2d elements. (Assume the depth
of the first element (or root) is zero).
(d) We can always find the maximum in a min-heap in O(log n) time
Answer: a, b, c
Solution:
(a) We can build a heap of 2n elements in O(n) time. Following are the
steps. Create an array of size 2n and copy elements of both heaps to
this array. Call build heap for the array of size 2n. Build heap operation
takes O (n) time.

(b) True, (refer ma‟am‟s notes)

(c) True

(d) FALSE. The maximum element in a min-heap can be anywhere in the

bottom level of the heap. There are up to n/2 elements in the bottom
level, so finding the maximum can take up to O (n) time.

Q66. Consider the partition step used in quick Sort. When a sequence of length n is
partitioned, the worst-case time complexity of the partitioning operation is
(a) (lg(n)). (b) (n).
(c) (nlog (n)). (d) None of the above.
Answer: B
Solution:Partition function will always take O (n).

Q67. Suppose you are sorting the following 6-digit decimal numbers using straight
radix sort, i.e., starting from the least significant position: 578037, 270332,
370548, 187578, 404288 and 913210. What is the order of the numbers after
the second iteration of radix sort?
(a) 913210, 270332,578037, 370548, 187578, 404288

BASIC DATA STRUCTURE AND ALGORITHMPage 43

 (b) 913210, 578037,270332,370548, 187578, 404288
(c) 913210, 578037,270332, 187578, 370548, 404288
913210,270332,578037,187578, 404288, 370548
Solution:
Bucket Pass 1 Pass 2
0 913210
1 913210
2 270332
3 270332,
578037
4 370548
5
6
7 578037 187578
8 370548, 404288
187578,
404288
9
Ans is (A)

Q68. Suppose you are given a function which tells you in O (1) time the index of the
median element in A. What is the best and worst-case running time of Quick
sort if you have that function to determine which pivot element to use?
(a) (n) and (n)
(b) (n) and (nlog2 n)
(c) (nlog2n) and (nlog2n)
(d) (nlog2n) and (n2)
Answer: C
Solution: If we find median in O (1) then we can always divide the list into two
parts. Therefore, in each case the complexity of quick sort is O(n log n).
Q69. Consider a min heap with more than 1000 unique integer keys. Which of the
following statements is false if the level start from zero?
(a) The second smallest key must be at level 1.
(b) The third smallest key must be at level 2.

BASIC DATA STRUCTURE AND ALGORITHMPage 44

 (c) The fourth smallest key could be at level 2.
(d) The fifth smallest key could be at level 3.
Answer is B
Solution:
(a) is true; because second smallest-key must be at level 1 in min-heap if
integers are unique.
(b) is false, 3rd smallest key may be at level 1
e.g.

(c) is true, 4th smallest key could be at level 2.

(d) is true,

Answer is B

Q70. How many element comparisons would heap sort use (min-heap) to sort the
integers 1 to 8 if they were initially in sorted(ascending) order? _______________
Answer is 24
Solution: When elements are initially in ascending order
1 2 3 4 5 6 7 8

BASIC DATA STRUCTURE AND ALGORITHMPage 45

 7 comparisons to insert each element one by one (building Heap).
Now, deletion &reheapification
Comparison2 & 3, 8 & 2
4&8, 4& 5

delete 2,
compare 4&3 ,7&3 ,8&7

Deletion 1 2 3 4 5 6 7 8
Comparison 4 3 4 3 2 1 0 0
Total number of comparisons = 7+17 =24

BASIC DATA STRUCTURE AND ALGORITHMPage 46

 Answer is 24
For next three questions consider the following piece of code of merge sort
void Mergsort(int[]arr,int left int right)
{
//arrays of size 1 are already sorted
If (start >= end)
Return;
int mid =(left +right)/2; DIVIDE
partition (arr, left,mid);
partition (arr,mid+1,right);
Mergsort (arr,left,mid+1, right); CONQUER
}
Q71. What is the complexity of the divide step?
(a) log N (b) N
(c) N log N (d) N2
Answer:
Solution: B
For DIVIDE: Recurrencerelation will be T (n) = 2T (n/2) + 1.
Solving T (n) we will get O (n) as complexity.
Q72. What is the complexity of the Conquer step?
(a) log N (b) N
(c) N log N (d) N2
Answer:
Solution: B
For Conquer: T (n) we will get O (n) as complexity.

Q73. You are told that you need to search on a set of data that is not sorted, the
maximum array size will Remain constant, and you need the fastest search
possible. It does not matter if the storage method maintains the order of the
data or not. Which lookup would you use:
(a)linear search (b)sequential search
(c)binary search (d)hash lookup
Answer: (D)
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 47

 From the given technique, hashing is the most suitable technique as we are
allowed to use space.

Q74. Consider the following code:

int may_be_linear_search(int v[],int size, int target)
{
int even = 0;
while (even < size) {
if ((v[even] == target) || (v[even+1] == target))
return 1;
even += 2;
}
return 0;
}
This code is:
(a) a correct implementation of linear search in all cases
(b) a correct implementation of linear search just when target is not in v
(c) a correct implementation of linear search just when target is in v
(d) an incorrectimplementation of linear search in some cases
Answer: D

Q75. Consider an array of size 2N elements consisting of N 2‟s followed by N 1‟s.

Below is the array when N = 4, 2 2 2 2 1 1 1 1 What is the complexity of
insertion sort in this case?
(a) θ(n) (b) θ(nlogn)
(c)θ(n2) (d) none
Solution: C
Since 2222….111111…….
there data are sorted in decreasing order, but we have to sort in increasing
order using insertion sort. This is worst case of insertion sort.
It will take (n2) time.
Let’s take a look at efficient approach:
1) Count the number of 2s. Let count be C.
2) Once we have count, we can put C 1s at the beginning and 2s at the

BASIC DATA STRUCTURE AND ALGORITHMPage 48

 remaining n – C positions in array. So, Answer should be A. But
Since it is mention that in question “using insertion sort”.
So, the time complexity = θ(n2). Answer will be C.
Q76. If a 5 is inserted into the heap below, into which position will the 5 go?
i: 0 1 2 3 4 5 6 7 8 9 10
A[i]: 3 9 15 10 17 16 23 19 22 30 33
(a)A[0] (b)A[1]
(c) A[2] (d) A[5]
Solution:

Therefore a[2] = 5
Answer is C.

Q77. Consider a min heap with 16 elements. Which of the following statements is
true?
(a) The length of shortest path in the heap is 2 and the length of longest path in
the heap is 4.
(b) The length of shortest path in the heap is 2 and the length of longest path in
the heap is 3.
(c) The length of shortest path in the heap is 3 and the length of longest path in

BASIC DATA STRUCTURE AND ALGORITHMPage 49

 the heap is 5.
(d) The length of shortest path in the heap is 3 and the length of longest path in
the heap is 4.
Solution:

Length of longest path = 4

Length of shortest path =3
Answer is D
Data for next four questions: The time complexity of Quick sort not only depends on
the data being sorted but also depend the element selected as the pivot. Although
Quick sort is O (n log n) on average, but in some cases Quick sort takes θ(n2) time.
For next four questions find the complexity of Quick sort.
Q78. On a sorted array suppose we select the pivot element from the last position of
the sub-array. Quick sort now takes (in worst case)
(a) θ(n) (b) θ(nlogn) (c) θ(n2) (d) none of these
Solution: On a sorted array, suppose we select the pivot element from the last
position, then it may possible list is not divided into two equal parts, or list is
divided into two parts with 1 and n-1 elements. Then, in this complexity will be
(n2).
Answer is C
Q79. On a sorted array suppose we select the pivot element from the middle position
of the sub-array. Quicksort now takes(in worst case)
(a) θ(n) (b) θ(nlogn)
(c) θ(n2) (d) none of these
Solution: ∵ middle position need not be median of array. But here we have
given sorted array. Therefore, middle element of this array is median.

BASIC DATA STRUCTURE AND ALGORITHMPage 50

 And its recurrence relation will T(n) = 2T(n/2) + n
Its complexity = (n log n) in worst case.
Answer is B
Q80. On a sorted array suppose we select the pivot element from the median element
of the first, middle and last keys of the sub-array. Quick sort now takes(in
worst case)
(a) θ(n) (b) θ(nlogn)
(c) θ(n2) (d) none of these
Solution: We select the pivot element from the median element of the 1st middle
and last keys of the sub- array. but this median need not be actual median of
whole sorted array. Complexity in worst case = ( n2)
Answer is C
Q81. Consider the following array :21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34,
46, 40
Which are the first two lists to be merged?
(a) [21, 1] and [26, 45]
(b) [1, 2, 9, 21, 26, 28, 29, 45] and [16, 27, 34, 39, 40, 43, 46, 49]
(c) [21] and [1]
(d) [9] and [16]
Solution: After breaking the list by merge sort into 16 parts, each list have one
element.

Answer will be [21] and [1]

Answer is C

Q82. The following array is to be sorted using merge sort:

19 3 9 22 1 17 33 15 8 5 12 13 10 7 6 11
How many recursive calls will be made by merge sort?_____
Solution: 30
19 3 9 22 1 17 33 15 8 5 12 13 10 7 6 11

BASIC DATA STRUCTURE AND ALGORITHMPage 51

 Array contains 16 elements. Its recursive tree will be-

Total number of recursive calls (excluding original call)

=21 + 22 + 23 + 24 = 2 + 4 + 8 + 16 = 30
Answer is 30.
Q83. Merging 4 sorted lists of n elements each, takes time:
(a) θ(n) (b) θ(nlogn) (c) θ(n2) (d) (2n)
Solution: During merging, we have to copy all elements, store into temporary
array.
Complexity for merging = (n)
Now, we have 4 sorted lists with n element each & we have to merge.
Complexity of merging of two list = (n)
& Merging of two other list = (n)
then, we merge finally, these two merged lists =(n) + (n)= (n)
Overall complexity = (n)
Answer is A
Q84. Merging n sorted lists, of 4 elements each, takes time:
(a) θ(n) (b) θ(n log n)
(c) θ(n2) (d) (2n)
Solution: (B)
We have n sorted lists of 4 element each,
Total elements = 4n

BASIC DATA STRUCTURE AND ALGORITHMPage 52

 So, we have k-level i.e., log n and, each level, we have 4n comparison or cost
Overall complexity = 4n log n = 4n log n = (n log n)
Answer is B.
Q85. On a sorted array suppose we select the pivot element from the median element
of the first three keys of the sub-array. Quick sort now takes (in worst case)
(a) θ(n) (b) θ(nlogn)
(c) θ(n2) (d) none of these
Solution: We select pivot median of 1st 3 elements and it may not be median.
Complexity in worst case = (n2)
Answer is C
Q86. [MSQ]
Consider the array 7, 1,4,2,5,6,2,6. Which of the following is/are intermediate
state of array possible during merge sort?
(a) 1, 7,4,2,5,6,2,6
(b)1, 2,4,7,5,6,2,6
(c) 1, 2,4,5,6,7,2,6
(d) 1, 2,4,7,2,5,6,6
Answer: a, b, d
Solution:

BASIC DATA STRUCTURE AND ALGORITHMPage 53

 Now, we will merge….

we can see that, only (a), (b) & (d) are intermediate stage.

Q87. [MSQ]
Which of the following statement is/are true about counting sort?

BASIC DATA STRUCTURE AND ALGORITHMPage 54

 (a) Counting sort is efficient if the range of input data is not significantly
greater than the number of objects to be sorted. Consider the situation
where the input sequence is between range 1 to 10K and the data is 10, 5,
10K, 5K.
(b) It is not a comparison-based sorting. It running time complexity is O(n)
with space proportional to the range of data.
(c) Counting sort uses a partial hashing to count the occurrence of the data
object in O(1).
(d) Counting sort can be extended to work for negative inputs also.
Answer: a, b, c, d
Q88. Following array is sorted using radix sort using a radix of 10, into ascending
order:
I 0 1 2 3 4 5 6 7 8 9 10 11 12 13
A[i] 329 595 408 15 291 466 7 290 141 53 210 883 107 395
Which element will be at index 7 after second pass of radix sort?___________
Solution:
329 595 408 15 291 466 7 290 141 53 210 883 107 395

Queue Pass I Pass II

0 290,210 007,107,408
1 291,141 210,15
2 329
3 53,883
4 141
5 595,15,395 53
6 466 466
7 7,107
8 408 883
9 329 290,291,595,395
After first pass, Array will contain
290,210,291,141,53,883,595,15,395,466,7,107,408,329. After second pass,
status of array will be-007, 107, 408, 210,15,329,141,53,466,883,290,291
,595,395.
a[7] =53

BASIC DATA STRUCTURE AND ALGORITHMPage 55

 Answer is 53
Q89. What is the running time of RADIX-SORT on an array of n integers in the range
0, 1,... , n5 - 1 when using base-10 representation?
(a) θ(n2) (b) θ (log n)
(c) θ (n) (d)θ(n log n)
Solution: We know that complexity of Radix sort = (nk) ---------(1);
where k= numberof digits. Now, we have given that range of n integers = {0,1,2
……n5-1}
Number of digit (k) =log10 𝑛5 = 5 log10 𝑛
Complexity = (nk) = (n 5 log10 𝑛)=(n logn)
Answer is D
Q90. What is the running time of RADIX-SORT on an array of n integers in the range
0, 1,... , n5 - 1 using a base-n representation?
(a) θ(n2) (b) θ (log n) (c) θ (n) (d) θ (n log n)
Solution: Complexity of radix sort =(k n)
where k= number of digits
range of n integers = 0 to n5-1 with base n .
 k= log 𝑛 𝑛5 = 5 log 𝑛 𝑛 =5
Complexity = (5n) = (n)
Answer is C
Q91. An unsorted array of n elements is given to you and you have to print largest
10% of them. This can be done in time (using a comparison-based algorithm):
(a) θ(1) (b) θ (log n) (c) θ (n) (d) θ (n log n)
Solution: Using comparison-basedalgorithm. we can sort the array with size n
in
(nlogn).
let n = 0.1n =0.1n
Complexity = (0.1 n log(0.1n))= (nlog n)
Answer is D
Q92. A sorted array of n elements is given to you and you have to print largest 10%
of them. This can be done in time (using a comparison-based algorithm):
(a) θ(1) (b) θ (log n) (c) θ (n) (d) θ (n log n)
Solution: We have sorted array with size n. now, we have to print 10% largest
element. for this wehave to access 0.1n element for last.

BASIC DATA STRUCTURE AND ALGORITHMPage 56

 Complexity =  (0.1n) = (n)
Answer is C
Q93. Let A is an array of size n. Arevis an array contains the same elements as that of
A but in reverse order. Let the total number of inversions in A is a and Arev is b,
then a + b is:
(a) n(n-1)/2 (b) n(n-1)/4 (c) n2(n-1)/2 (d) none
Solution: Size of A=n
𝑛(𝑛−1)
number of inversions in A and sum of inversions in Arev =
2
𝑛(𝑛−1)
a+b=
2

Answer is A

Q94. You are writing algorithms for a small device with very limited main memory.
Youhave to sort the of 4,000,000 withdrawal records in the ascending order
amount of money with` drawn. Which sorting technique do you prefer?
(a)Insertion Sort (b)Mergesort
(c)Radix Sort (d)Heap Sort
Solution: We can‟t use merge sort Radix sort, because it is not in place.
Therefore, Heap sort is better than insertion in terms of complexity.
Answer is D
Q95. A social networking sites assign a 64-bit unique identification numbers to every
user in sorted order(i.e., who join earlier will have a smaller-id than one who
join
later).You have so many friends on that site and you need to sort them
according
to their identification numbers. Which sorting technique do you prefer?
(a)Insertion Sort (b)Merge Sort
(c)Radix Sort (d)Heap Sort
Solution: Range of identification number = 0 to 264 – 1
 Number of digits = 64 bit
(It we take binary number for identification number)
In this case, Radix sort will give very less complexity as compare to other
sorting technique.
It‟s complexity = (n) = (n log 2 264 − 1) =(64 n) = (n)

BASIC DATA STRUCTURE AND ALGORITHMPage 57

 but other technique give have more complexity (n).
Radix sort is preferable.
Answer is C
Q96. Suppose you are asking to write a program to sort the records of students.
Each student has a 4-digit Enroll-ID. You have to sort the list using Enroll-
[Link] sorting technique would you use?
(a) Quick sort (b)Mergersort
(c)Heapsort (d)Counting sort
Solution: Since each student has a 4 digit Enroll – Id . Hence, range of Enroll-Id
is 0 to [Link] sort can sort a list in O(n+k) time, where n is the number
of elements and k is the range of values.
Complexity = O(9999+n) =O(n)
But other sorting techniques have more complexity than O(n) .
Counting sort is preferable.
Answer is D
Q97. Suppose you are doing a sequential search of the ordered list 3, 5, 6, 8, 11, 12,
14, 15, 17, 18. How many comparisons would you need to do in order to find
the key 13?
(a) 10 (b) 5 (c) 7 (d) 6
Solution: 3, 5, 6, 8, 11, 12, 14, 15, 17, 18.
 13 is not present in list
Number of comparisons = number of elements =10
Answer is A
Q98. Consider an array of 100 elements where a[i]= i. Which of the following
Statementbelow is true?
(a) We can‟t apply Binary search in this problem.
(b) Sequential search is always faster than binary search for every value
searched.
(c) Sequential search is always slower than binary search for every value
searched.
(d) Sequential search is sometimes faster, sometimes slower than binary search
depending on which value is being searched.
Solution: a[i]=1
Our array contains

BASIC DATA STRUCTURE AND ALGORITHMPage 58

 0 1 2 3 …………………99
(i) is false, because we can apply binary search (list is sorted).
(ii) & (iii) are false, because in best case and worst case both are false
respectively.
(iv) Sequential search is faster when key =a[0] , It is slower sometimes, when
key=a[n-1] or key is not present in list.
Answer is D
Q99. Suppose you have the following sorted list [3, 5, 6, 8, 11, 12, 14, 15, 17, 18]
and are usingthe recursive binary search algorithm. Which group of numbers
correctly shows the sequence ofcomparisons used to find the key 8?
(Assume mid = floor (low + high)/2)
(a) 11, 5, 6, 8 (b) 12, 6, 11, 8
(c) 11, 5, 6, 8 (d) 11 6, 8
Solution:

0+9
mid = = floor [4.5]=4
2

a[4] =11
∵ 11>8
∴We search left side of mid.
Now,
0+3
mid= floor =1
2

a[1]=5
∵5<8
∴We search right side of a[2]
2+3
Now, mid= =2
2

a[2] =6
& key =6
3+3
Now, mid= =3
2

a[3] = 8
∴Order of search will be11,5,6,8
Answer is C.

BASIC DATA STRUCTURE AND ALGORITHMPage 59

[Link] you have the following sorted list [3, 5, 6, 8, 11, 12, 14, 15, 17, 18]
and are using the recursive binary search algorithm. Which group of numbers
correctly shows the sequence of comparisons used to search for the key
16?(Assume mid = Ceil(low + high)/2)
(a) 11, 14, 17 (b) 18, 17, 15
(c) 14, 17, 15 (d) 12, 15,17
Solution: array a[ { 3 5 6 8 11 12 14 15 17 18}
𝑙𝑜𝑤 +ℎ𝑖𝑔ℎ 0+9
mid = = = 4.5 =5
2 2

a[5] =12
∵12< 16
low =5, high = 9
5+9
Now, mid = =7
2

a[7] =15
∵ 15<16
∴low=7 high =9
7+9
Now, mid = =8
2

a[8] =17
a[8] >16
and a[7] <16
∴ key is not present
sequence of search is 12, 15, 17
Answer is D

BASIC DATA STRUCTURE AND ALGORITHMPage 60

BASIC DATA STRUCTURE AND ALGORITHMPage 61