[7:18 AM, 12/14/2020] +92 343 7690131: 1.

Process of
inserting an element in stack is called ____

a) Create

b) Push

c) Evaluation

d) Pop

View Answer

Answer: b

Explanation: Push operation allows users to insert

elements in the stack. If the stack is filled completely and
trying to perform push operation stack – overflow can
happen.

advertisement

2. Process of removing an element from stack is called

____

a) Create

b) Push

c) Evaluation

d) Pop

View Answer

Answer: d

Explanation: Elements in the stack are removed using pop

operation. Pop operation removes the top most element in
the stack i.e. last entered element.
3. In a stack, if a user tries to remove an element from an
empty stack it is called ___

a) Underflow

b) Empty collection

c) Overflow

d) Garbage Collection

View Answer

Answer: a

Explanation: Underflow occurs when the user performs a

pop operation on an empty stack. Overflow occurs when
the stack is full and the user performs a push operation.
Garbage Collection is used to recover the memory
occupied by objects that are no longer used.

4. Pushing an element into stack already having five

elements and stack size of 5, then stack becomes _____

a) Overflow

b) Crash

c) Underflow

d) User flow

View Answer

Answer: a

Explanation: The stack is filled with 5 elements and

pushing one more element causes a stack overflow. This
results in overwriting memory, code and loss of unsaved
work on the computer.
5. Entries in a stack are “ordered”. What is the meaning of
this statement?

a) A collection of stacks is sortable

b) Stack entries may be compared with the ‘<‘ operation

c) The entries are stored in a linked list

d) There is a Sequential entry that is one by one

View Answer

Answer: d

Explanation: In stack data structure, elements are added

one by one using push operation. Stack follows LIFO
Principle i.e. Last In First Out(LIFO).

advertisement

6. Which of the following is not the application of stack?

a) A parentheses balancing program

b) Tracking of local variables at run time

c) Compiler Syntax Analyzer

d) Data Transfer between two asynchronous process

View Answer

Answer: d

Explanation: Data transfer between the two asynchronous

process uses the queue data structure for synchronisation.
The rest are all stack applications.
7. Consider the usual algorithm for determining whether a
sequence of parentheses is balanced. The maximum
number of parentheses that appear on the stack AT ANY
ONE TIME when the algorithm analyzes: (()(())(()))?

a) 1

b) 2

c) 3

d) 4 or more

View Answer

Answer: c

Explanation: In the entire parenthesis balancing method

when the incoming token is a left parenthesis it is pushed
into stack. A right parenthesis makes pop operation to
delete the elements in stack till we get left parenthesis as
top most element. 3 elements are there in stack before
right parentheses comes. Therefore, maximum number of
elements in stack at run time is 3.

8. Consider the usual algorithm for determining whether a

sequence of parentheses is balanced. Suppose that you
run the algorithm on a sequence that contains 2 left
parentheses and 3 right parentheses (in some order). The
maximum number of parentheses that appear on the
stack AT ANY ONE TIME during the computation?

a) 1

b) 2

c) 3

d) 4 or more

View Answer
Answer: b

Explanation: In the entire parenthesis balancing method

when the incoming token is a left parenthesis it is pushed
into stack. A right parenthesis makes pop operation to
delete the elements in stack till we get left parenthesis as
top most element. 2 left parenthesis are pushed whereas
one right parenthesis removes one of left parenthesis. 2
elements are there before right parenthesis which is the
maximum number of elements in stack at run time.

9. What is the value of the postfix expression 6 3 2 4 + –

*?

a) 1

b) 40

c) 74

d) -18

View Answer

Answer: d

Explanation: Postfix Expression is (6*(3-(2+4))) which

results -18 as output.

advertisement

10. Here is an infix expression: 4 + 3*(6*3-12). Suppose

that we are using the usual stack algorithm to convert the
expression from infix to postfix notation. The maximum
number of symbols that will appear on the stack AT ONE
TIME during the conversion of this expression?

a) 1
b) 2

c) 3

d) 4

View Answer

Answer: d

Explanation: When we perform the conversion from infix

to postfix expression +, *, (, * symbols are placed inside
the stack. A maximum of 4 symbols are identified during
the entire conversion

[7:22 AM, 12/14/2020] +92 343 7690131: Menu

Data Structure Questions and Answers – Stack Operations

–2

« PrevNext »

This set of Data Structure Interview Questions and

Answers focuses on “Stack Operations – 2”.

1. The postfix form of the expression (A+ B)*(C*D- E)*F / G

is?

a) AB+ CD*E – FG /**

b) AB + CD* E – F **G /

c) AB + CD* E – *F *G /

d) AB + CDE * – * F *G /

View Answer
Answer: c

Explanation: (((A+ B)*(C*D- E)*F) / G) is converted to

postfix expression as

(AB+(*(C*D- E)*F )/ G)

(AB+CD*E-*F) / G

(AB+CD*E-*F * G/). Thus Postfix expression is

AB+CD*E-*F*G/

advertisement

2. The data structure required to check whether an

expression contains balanced parenthesis is?

a) Stack

b) Queue

c) Array

d) Tree

View Answer

Answer: a

Explanation: The stack is a simple data structure in which

elements are added and removed based on the LIFO
principle. Open parenthesis is pushed into the stack and a
closed parenthesis pops out elements till the top element
of the stack is its corresponding open parenthesis. If the
stack is empty, parenthesis is balanced otherwise it is
unbalanced.

3. What data structure would you mostly likely see in a

non recursive implementation of a recursive algorithm?

a) Linked List
b) Stack

c) Queue

d) Tree

View Answer

Answer: b

Explanation: In recursive algorithms, the order in which

the recursive process comes back is the reverse of the
order in which it goes forward during execution. The
compiler uses the stack data structure to implement
recursion. In the forwarding phase, the values of local
variables, parameters and the return address are pushed
into the stack at each recursion level. In the backing-out
phase, the stacked address is popped and used to execute
the rest of the code.

4. The process of accessing data stored in a serial access

memory is similar to manipulating data on a ____

a) Heap

b) Binary Tree

c) Array

d) Stack

View Answer

Answer: d

Explanation: In serial access memory data records are

stored one after the other in which they are created and
are accessed sequentially. In stack data structure,
elements are accessed sequentially. Stack data structure
resembles the serial access memory.
5. The postfix form of A*B+C/D is?

a) *AB/CD+

b) AB*CD/+

c) A*BC+/D

d) ABCD+/*

View Answer

Answer: b

Explanation: Infix expression is (A*B)+(C/D)

AB*+(C/D)

AB*CD/+. Thus postfix expression is AB*CD/+.

advertisement

6. Which data structure is needed to convert infix notation

to postfix notation?

a) Branch

b) Tree

c) Queue

d) Stack

View Answer

Answer: d

Explanation: The Stack data structure is used to convert

infix expression to postfix expression. The purpose of
stack is to reverse the order of the operators in the
expression. It also serves as a storage structure, as no
operator can be printed until both of its operands have
appeared.

7. The prefix form of A-B/ (C * D ^ E) is?

a) -/*^ACBDE

b) -ABCD*^DE

c) -A/B*C^DE

d) -A/BC*^DE

View Answer

Answer: c

Explanation: Infix Expression is (A-B)/(C*D^E)

(-A/B)(C*D^E)

-A/B*C^DE. Thus prefix expression is -A/B*C^DE

8. What is the result of the following operation?

Top (Push (S, X))

a) X

b) X+S

c) S

d) XS

View Answer

Answer: a

Explanation: The function Push(S,X) pushes the value X in

the stack S. Top() function gives the value which entered
last. X entered into stack S at last.
9. The prefix form of an infix expression (p + q) – (r * t) is?

a) + pq – *rt

b) – +pqr * t

c) – +pq * rt

d) – + * pqrt

View Answer

Answer: c

Explanation: Given Infix Expression is ((p+q)-(r*t))

(+pq)-(r*t)

(-+pq)(r*t)

-+pq*rt. Thus prefix expression is -+pq*rt.

advertisement

10. Which data structure is used for implementing

recursion?

a) Queue

b) Stack

c) Array

d) List

View Answer

Answer: b

Explanation: Stacks are used for the implementation of

Recursion.
Sanfoundry Global Education & Learning Series – Data
Structure.

[7:25 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Insertion Sort – 2”.

1. Which of the following is correct with regard to insertion

sort?

a) insertion sort is stable and it sorts In-place

b) insertion sort is unstable and it sorts In-place

c) insertion sort is stable and it does not sort In-place

d) insertion sort is unstable and it does not sort In-place

View Answer

Answer: a

Explanation: During insertion sort, the relative order of

elements is not changed. Therefore, it is a stable sorting
algorithm. And insertion sort requires only O(1) of
additional memory space. Therefore, it sorts In-place.

2. Which of the following sorting algorithm is best suited if

the elements are already sorted?

a) Heap Sort

b) Quick Sort

c) Insertion Sort

d) Merge Sort

View Answer
Answer: c

Explanation: The best case running time of the insertion

sort is O(n). The best case occurs when the input array is
already sorted. As the elements are already sorted, only
one comparison is made on each pass, so that the time
required is O(n).

3. The worst case time complexity of insertion sort is

O(n2). What will be the worst case time complexity of
insertion sort if the correct position for inserting element is
calculated using binary search?

a) O(nlogn)

b) O(n2)

c) O(n)

d) O(logn)

View Answer

Answer: b

Explanation: The use of binary search reduces the time of

finding the correct position from O(n) to O(logn). But the
worst case of insertion sort remains O(n2) because of the
series of swapping operations required for each insertion.

4. Insertion sort is an example of an incremental

algorithm.

a) True

b) False

View Answer

Answer: a
Explanation: In the incremental algorithms, the
complicated structure on n items is built by first building it
on n − 1 items. And then we make the necessary changes
to fix things in adding the last item. Insertion sort builds
the sorted sequence one element at a time. Therefore, it
is an example of an incremental algorithm.

5. Consider the code given below, which runs insertion

sort:

void insertionSort(int arr[], int array_size)

int i, j, value;

for (i = 1; i < array_size; i++)

value = arr[i];

j = i;

while (____ )

arr[j] = arr[j − 1];

j = j − 1;

arr[j] = value;

Which condition will correctly implement the while loop?

a) (j > 0) || (arr[j − 1] > value)

b) (j > 0) && (arr[j − 1] > value)

c) (j > 0) && (arr[j + 1] > value)

d) (j > 0) && (arr[j + 1] < value)

View Answer

Answer: b

Explanation: In insertion sort, the element is A[j] is

inserted into the correct position in the sorted sequence
A[1… j – 1]. So, condition given in (j > 0) && (arr[j − 1] >
value) will implement while loop correctly.

6. Which of the following is good for sorting arrays having

less than 100 elements?

a) Quick Sort

b) Selection Sort

c) Merge Sort

d) Insertion Sort

View Answer

Answer: d

Explanation: The insertion sort is good for sorting small

arrays. It sorts smaller arrays faster than any other sorting
algorithm.

7. Consider an array of length 5, arr[5] = {9,7,4,2,1}.

What are the steps of insertions done while running
insertion sort on the array?

a) 7 9 4 2 1 47921 24791 12479

b) 9 7 4 1 2 97124 91247 12479

c) 7 4 2 1 9 42197 21974 19742

d) 7 9 4 2 1 24791 47921 12479

View Answer

Answer: a

Explanation: The steps performed while running insertion

sort on given array are:

Initial : 9 7 4 2 1 key = 7

7 9 4 2 1 key = 4

4 7 9 2 1 key = 2

2 4 7 9 1 key = 1

12479

In each step, the key is the element that is compared with

the elements present at the left side to it.

8. Statement 1: In insertion sort, after m passes through

the array, the first m elements are in sorted order.

Statement 2: And these elements are the m smallest

elements in the array.

a) Both the statements are true

b) Statement 1 is true but statement 2 is false

c) Statement 1 is false but statement 2 is true

d) Both the statements are false

View Answer

Answer: b
Explanation: In insertion sort, after m passes through the
array, the first m elements are in sorted order but they are
whatever the first m elements were in the unsorted array.

9. In insertion sort, the average number of comparisons

required to place the 7th element into its correct position
is __

a) 9

b) 4

c) 7

d) 14

View Answer

Answer: b

Explanation: On average (k + 1) / 2 comparisons are

required to place the kth element into its correct position.
Therefore, average number of comparisons required for
7th element = (7 + 1)/2 = 4.

10. Which of the following is not an exchange sort?

a) Bubble Sort

b) Quick Sort

c) Partition-exchange Sort

d) Insertion Sort

View Answer

Answer: d

Explanation: In Exchange sorts, we compare each element

of an array and swap those elements that are not in their
proper position. Bubble Sort and Quick Sort are exchange
sorts. Quick Sort is also called as Partition-exchange Sort.
Insertion sort is not an exchange sort.

Sanfoundry Global Education & Learning Series – Dat

[7:27 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Multiple Choice Questions & Answers (MCQs)
focuses on “Bubble Sort”.

1. What is an external sorting algorithm?

a) Algorithm that uses tape or disk during the sort

b) Algorithm that uses main memory during the sort

c) Algorithm that involves swapping

d) Algorithm that are considered ‘in place’

View Answer

Answer: a

Explanation: As the name suggests, external sorting

algorithm uses external memory like tape or disk.

2. What is an internal sorting algorithm?

a) Algorithm that uses tape or disk during the sort

b) Algorithm that uses main memory during the sort

c) Algorithm that involves swapping

d) Algorithm that are considered ‘in place’

View Answer

Answer: b
Explanation: As the name suggests, internal sorting
algorithm uses internal main memory.

3. What is the worst case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: Bubble sort works by starting from the first

element and swapping the elements if required in each
iteration.

4. Select the appropriate code that performs bubble sort.

a)

for(int j=arr.length-1; j>=0; j--)

for(int k=0; k<j; k++)

if(arr[k] > arr[k+1])

int temp = arr[k];

arr[k] = arr[k+1];

arr[k+1] = temp;
}

b)

for(int j=arr.length-1; j>=0; j--)

for(int k=0; k<j; k++)

if(arr[k] < arr[k+1])

int temp = arr[k];

arr[k] = arr[k+1];

arr[k+1] = temp;

c)

for(int j=arr.length; j>=0; j--)

for(int k=0; k<j; k++)

if(arr[k] > arr[k+1])

{

int temp = arr[k];

arr[k] = arr[k+1];

arr[k+1] = temp;

d)

for(int j=arr.length; j>=0; j--)

for(int k=0; k<j; k++)

if(arr[k] > arr[k+2])

int temp = arr[k];

arr[k] = arr[k+1];

arr[k+1] = temp;

View Answer

Answer: a
Explanation: The outer loop keeps count of number of
iterations, and the inner loop checks to see if swapping is
necessary.

5. What is the average case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: Bubble sort works by starting from the first

element and swapping the elements if required in each
iteration even in the average case.

6. Which of the following is not an advantage of optimised

bubble sort over other sorting techniques in case of sorted
elements?

a) It is faster

b) Consumes less memory

c) Detects whether the input is already sorted

d) Consumes less time

View Answer

Answer: c
Explanation: Optimised Bubble sort is one of the simplest
sorting techniques and perhaps the only advantage it has
over other techniques is that it can detect whether the
input is already sorted. It is faster than other in case of
sorted array and consumes less time to describe whether
the input array is sorted or not. It consumes same memory
than other sorting techniques. Hence it is not an
advantage.

7. The given array is arr = {1, 2, 4, 3}. Bubble sort is used

to sort the array elements. How many iterations will be
done to sort the array?

a) 4

b) 2

c) 1

d) 0

View Answer

Answer: a

Explanation: Even though the first two elements are

already sorted, bubble sort needs 4 iterations to sort the
given array.

8. How can you improve the best case efficiency in bubble

sort? (The input is already sorted)

a)

boolean swapped = false;

for(int j=arr.length-1; j>=0 && swapped; j--)

{
swapped = true;

for(int k=0; k<j; k++)

if(arr[k] > arr[k+1])

int temp = arr[k];

arr[k] = arr[k+1];

arr[k+1] = temp;

swapped = false;

b)

boolean swapped = true;

for(int j=arr.length-1; j>=0 && swapped; j--)

swapped = false;

for(int k=0; k<j; k++)

if(arr[k] > arr[k+1])

int temp = arr[k];

arr[k] = arr[k+1];
arr[k+1] = temp;

c)

boolean swapped = true;

for(int j=arr.length-1; j>=0 && swapped; j--)

swapped = false;

for(int k=0; k<j; k++)

if(arr[k] > arr[k+1])

int temp = arr[k];

arr[k] = arr[k+1];

arr[k+1] = temp;

swapped = true;

d)

boolean swapped = true;

for(int j=arr.length-1; j>=0 && swapped; j--)

for(int k=0; k<j; k++)

if(arr[k] > arr[k+1])

int temp = arr[k];

arr[k] = arr[k+1];

[7:28 AM, 12/14/2020] ZaHeeR ShahZaiB: What is the best

case efficiency of bubble sort in the improvised version?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: c

Explanation: Some iterations can be skipped if the list is

sorted, hence efficiency improves to O(n).

10. The given array is arr = {1,2,4,3}. Bubble sort is used

to sort the array elements. How many iterations will be
done to sort the array with improvised version?

a) 4

b) 2

c) 1

d) 0
View Answer

Answer: b

Explanation: Only 2 elements in the given array are not

sorted, hence only 2 iterations are required to sort them.

Sanfoundry Global Education & Learning Series – Data

Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here

is complete set of 1000+ Multiple Choice Questions and
Answers.

[7:33 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Multiple Choice Questions & Answers (MCQs)
focuses on “Selection Sort”.

1. What is an in-place sorting algorithm?

a) It needs O(1) or O(logn) memory to create auxiliary

locations

b) The input is already sorted and in-place

c) It requires additional storage

d) It requires additional space

View Answer

Answer: a

Explanation: Auxiliary memory is required for storing the

data temporarily.
2. In the following scenarios, when will you use selection
sort?

a) The input is already sorted

b) A large file has to be sorted

c) Large values need to be sorted with small keys

d) Small values need to be sorted with large keys

View Answer

3. What is the worst case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: Selection sort creates a sub-list, LHS of the

‘min’ element is already sorted and RHS is yet to be
sorted. Starting with the first element the ‘min’ element
moves towards the final element.

4. Select the appropriate code that performs selection

sort.

a)

int min;

for(int j=0; j<arr.length-1; j++)

{

min = j;

for(int k=j+1; k<=arr.length-1; k++)

if(arr[k] < arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];

arr[j] = temp;

b)

int min;

for(int j=0; j<arr.length-1; j++)

min = j;

for(int k=j+1; k<=arr.length; k++)

if(arr[k] < arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];
arr[j] = temp;

c)

int min;

for(int j=0; j<arr.length-1; j++)

min = j;

for(int k=j+1; k<=arr.length-1; k++)

if(arr[k] > arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];

arr[j] = temp;

d)

int min;

for(int j=0; j<arr.length-1; j++)

min = j;

for(int k=j+1; k<=arr.length; k++)

{

if(arr[k] > arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];

arr[j] = temp;

View Answer

Answer: a

Explanation: Starting with the first element as ‘min’

element, selection sort loops through the list to select the
least element which is then swapped with the ‘min’
element.

5. What is the advantage of selection sort over other

sorting techniques?

a) It requires no additional storage space

b) It is scalable

c) It works best for inputs which are already sorted

d) It is faster than any other sorting technique

View Answer

Answer: a
Explanation: Since selection sort is an in-place sorting
algorithm, it does not require additional storage.

6. What is the average case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: In the average case, even if the input is

partially sorted, selection sort behaves as if the entire
array is not sorted. Selection sort is insensitive to input.

7. What is the disadvantage of selection sort?

a) It requires auxiliary memory

b) It is not scalable

c) It can be used for small keys

d) It takes linear time to sort the elements

View Answer

Answer: b

Explanation: As the input size increases, the performance

of selection sort decreases.

8. The given array is arr = {3,4,5,2,1}. The number of

iterations in bubble sort and selection sort respectively
are,
a) 5 and 4

b) 4 and 5

c) 2 and 4

d) 2 and 5

View Answer

Answer: a

Explanation: Since the input array is not sorted, bubble

sort takes 5 iterations and selection sort takes 4(n-1)
iterations.

9. The given array is arr = {1,2,3,4,5}. (bubble sort is

implemented with a flag variable)The number of iterations
in selection sort and bubble sort respectively are,

a) 5 and 4

b) 1 and 4

c) 0 and 4

d) 4 and 1

View Answer

Answer: d

Explanation: Selection sort is insensitive to input, hence

4(n-1) iterations. Whereas bubble sort iterates only once
to set the flag to 0 as the input is already sorted.

10. What is the best case complexity of selection sort?

a) O(nlogn)

b) O(logn)
c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: The best, average and worst case

complexities of selection sort is O(n2).

(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2

[7:35 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Merge Sort”.

1. Merge sort uses which of the following technique to

implement sorting?

a) backtracking

b) greedy algorithm

c) divide and conquer

d) dynamic programming

View Answer

Answer: c

Explanation: Merge sort uses divide and conquer in order

to sort a given array. This is because it divides the array
into two halves and applies merge sort algorithm to each
half individually after which the two sorted halves are
merged together.
2. What is the average case time complexity of merge
sort?

a) O(n log n)

b) O(n2)

c) O(n2 log n)

d) O(n log n2)

View Answer

Answer: a

Explanation: The recurrence relation for merge sort is

given by T(n) = 2T(n/2) + n. It is found to be equal to O(n
log n) using the master theorem.

3. What is the auxiliary space complexity of merge sort?

a) O(1)

b) O(log n)

c) O(n)

d) O(n log n)

View Answer

Answer: c

Explanation: An additional space of O(n) is required in

order to merge two sorted arrays. Thus merge sort is not
an in place sorting algorithm.

4. Merge sort can be implemented using O(1) auxiliary

space.

a) true
b) false

View Answer

Answer: a

Explanation: Standard merge sort requires O(n) space to

merge two sorted arrays. We can optimize this merging
process so that it takes only constant space. This version
is known as in place merge sort.

5. What is the worst case time complexity of merge sort?

a) O(n log n)

b) O(n2)

c) O(n2 log n)

d) O(n log n2)

View Answer

Answer: a

Explanation: The time complexity of merge sort is not

affected by worst case as its algorithm has to implement
the same number of steps in any case. So its time
complexity remains to be O(n log n).

6. Which of the following method is used for sorting in

merge sort?

a) merging

b) partitioning

c) selection

d) exchanging

View Answer
Answer: a

Explanation: Merge sort algorithm divides the array into

two halves and applies merge sort algorithm to each half
individually after which the two sorted halves are merged
together. Thus its method of sorting is called merging.

7. What will be the best case time complexity of merge

sort?

a) O(n log n)

b) O(n2)

c) O(n2 log n)

d) O(n log n2)

View Answer

Answer: a

Explanation: The time complexity of merge sort is not

affected in any case as its algorithm has to implement the
same number of steps. So its time complexity remains to
be O(n log n) even in the best case.

8. Which of the following is not a variant of merge sort?

a) in-place merge sort

b) bottom up merge sort

c) top down merge sort

d) linear merge sort

View Answer

Answer: d
Explanation: In-place, top down and bottom up merge sort
are different variants of merge sort. Whereas linear merge
sort is not a possible variant as it is a comparison based
sort and the minimum time complexity of any comparison
based sort is O(n log n).

9. Choose the incorrect statement about merge sort from

the following?

a) it is a comparison based sort

b) it is an adaptive algorithm

c) it is not an in place algorithm

d) it is stable algorithm

View Answer

Answer: b

Explanation: Merge sort is not an adaptive sorting

algorithm. This is because it takes O(n log n) time
complexity irrespective of any case.

10. Which of the following is not in place sorting

algorithm?

a) merge sort

b) quick sort

c) heap sort

d) insertion sort

View Answer

Answer: a
Explanation: An additional space of O(n) is required in
order to merge two sorted arrays. Thus merge sort is not
an in place sorting algorithm.

11. Which of the following is not a stable sorting

algorithm?

a) Quick sort

b) Cocktail sort

c) Bubble sort

d) Merge sort

View Answer

Answer: a

Explanation: Out of the given options quick sort is the only

algorithm which is not stable. Merge sort is a stable
sorting algorithm.

12. Which of the following stable sorting algorithm takes

the least time when applied to an almost sorted array?

a) Quick sort

b) Insertion sort

c) Selection sort

d) Merge sort

View Answer

Answer: d

Explanation: Insertion sort takes linear time to sort a

partially sorted array. Though merge and quick sort takes
O(n*logn) complexity to sort, merge sort is stable. Hence,
Merge sort takes less time to sort partially sorted array.

13. Merge sort is preferred for arrays over linked lists.

a) true

b) false

View Answer

Answer: b

Explanation: Merge sort is preferred for linked list over

arrays. It is because in a linked list the insert operation
takes only O(1) time and space which implies that we can
implement merge operation in constant time.

14. Which of the following sorting algorithm makes use of

merge sort?

a) tim sort

b) intro sort

c) bogo sort

d) quick sort

View Answer

Answer: a

Explanation: Tim sort is a hybrid sorting algorithm as it

uses more than one sorting algorithm internally. It makes
use of merge sort and insertion sort.

15. Choose the correct code for merge sort.

a)
void merge_sort(int arr[], int left, int right)

if (left > right)

int mid = (right-left)/2;

merge_sort(arr, left, mid);

merge_sort(arr, mid+1, right);

merge(arr, left, mid, right); //function to merge

sorted arrays

b)

void merge_sort(int arr[], int left, int right)

if (left < right)

int mid = left+(right-left)/2;

merge_sort(arr, left, mid);

merge_sort(arr, mid+1, right);

merge(arr, left, mid, right); //function to merge
sorted arrays

c)

void merge_sort(int arr[], int left, int right)

if (left < right)

int mid = left+(right-left)/2;

merge(arr, left, mid, right); //function to merge sorted

arrays

merge_sort(arr, left, mid);

merge_sort(arr, mid+1, right);

d)

void merge_sort(int arr[], int left, int right)

if (left < right)

{

int mid = (right-left)/2;

merge(arr, left, mid, right); //function to merge sorted

arrays

merge_sort(arr, left, mid);

merge_sort(arr, mid+1, right);

View Answer

Answer: b

Explanation: Merge sort first sorts the two halves of the

array individually. Then it merges the two sorted halves in
order to obtain sorted array.

16. Which of the following sorting algorithm does not use

recursion?

a) quick sort

b) merge sort

c) heap sort

d) bottom up merge sort

View Answer
Answer: d

Explanation: Bottom up merge sort uses the iterative

method in order to implement sorting. It begins by
merging a pair of adjacent array of size 1 each and then
merge arrays of size 2 each in the next step and so on.

[7:37 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Quicksort – 1”.

1. Which of the following sorting algorithms is the fastest?

a) Merge sort

b) Quick sort

c) Insertion sort

d) Shell sort

View Answer

Answer: b

Explanation: Quick sort is the fastest known sorting

algorithm because of its highly optimized inner loop.

2. Quick sort follows Divide-and-Conquer strategy.

a) True

b) False

View Answer

Answer: a
Explanation: In quick sort, the array is divided into
sub-arrays and then it is sorted (divide-and-conquer
strategy).

3. What is the worst case time complexity of a quick sort

algorithm?

a) O(N)

b) O(N log N)

c) O(N2)

d) O(log N)

View Answer

Answer: c

Explanation: The worst case performance of a quick sort

algorithm is mathematically found to be O(N2).

4. Which of the following methods is the most effective for

picking the pivot element?

a) first element

b) last element

c) median-of-three partitioning

d) random element

View Answer

Answer: c

Explanation: Median-of-three partitioning is the best

method for choosing an appropriate pivot element. Picking
a first, last or random element as a pivot is not much
effective.
5. Find the pivot element from the given input using
median-of-three partitioning method.

8, 1, 4, 9, 6, 3, 5, 2, 7, 0.

a) 8

b) 7

c) 9

d) 6

View Answer

Answer: d

Explanation: Left element=8, right element=0,

Centre=[position(left+right)/2]=6.

6. Which is the safest method to choose a pivot element?

a) choosing a random element as pivot

b) choosing the first element as pivot

c) choosing the last element as pivot

d) median-of-three partitioning method

View Answer

Answer: a

Explanation: This is the safest method to choose the pivot

element since it is very unlikely that a random pivot would
consistently provide a poor partition.

7. What is the average running time of a quick sort

algorithm?

a) O(N2)
b) O(N)

c) O(N log N)

d) O(log N)

View Answer

Answer: c

Explanation: The best case and average case analysis of a

quick sort algorithm are mathematically found to be O(N
log N).

8. Which of the following sorting algorithms is used along

with quick sort to sort the sub arrays?

a) Merge sort

b) Shell sort

c) Insertion sort

d) Bubble sort

View Answer

Answer: c

Explanation: Insertion sort is used along with quick sort to

sort the sub arrays.

It is used only at the end.

9. Quick sort uses join operation rather than merge

operation.

a) true

b) false

View Answer
Answer: a

Explanation: Quick sort uses join operation since join is a

faster operation than merge.

10. How many sub arrays does the quick sort algorithm
divide the entire array into?

a) one

b) two

c) three

d) four

View Answer

Answer: b

Explanation: The entire array is divided into two partitions,

1st sub array containing elements less than the pivot
element and 2nd sub array containing elements greater
than the pivot element.

11. Which is the worst method of choosing a pivot

element?

a) first element as pivot

b) last element as pivot

c) median-of-three partitioning

d) random element as pivot

View Answer

Answer: a
Explanation: Choosing the first element as pivot is the
worst method because if the input is pre-sorted or in
reverse order, then the pivot provides a poor partition.

12. Which among the following is the best cut-off range to

perform insertion sort within a quick sort?

a) N=0-5

b) N=5-20

c) N=20-30

d) N>30

View Answer

Answer: b

Explanation: A good cut-off range is anywhere between

N=5 and N=20 to avoid nasty degenerate cases

[7:38 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Quicksort – 2”.

1. Quick sort is a ____

a) greedy algorithm

b) divide and conquer algorithm

c) dynamic programming algorithm

d) backtracking algorithm

View Answer

Answer: b
Explanation: Quick sort is a divide and conquer algorithm.
Quick sort first partitions a large array into two smaller
sub-arrays. And then recursively sorts the sub-arrays.

2. What is the worst case time complexity of the Quick

sort?

a) O(nlogn)

b) O(n)

c) O(n3)

d) O(n2)

View Answer

Answer: d

Explanation: The worst case running time for Quick sort is

O(n2). In Quick sort, the worst case behaviour occurs
when the partitioning routine produces two sub-arrays one
with n – 1 element and other with 0 elements.

3. Apply Quick sort on a given sequence 7 11 14 6 9 4 3

12. What is the sequence after first phase, pivot is first
element?

a) 6 4 3 7 11 9 14 12

b) 6 3 4 7 9 14 11 12

c) 7 6 14 11 9 4 3 12

d) 7 6 4 3 9 14 11 12

View Answer

Answer: b

Explanation: Let’s apply Quick sort on the given sequence,

For first phase, pivot = 7

7 11 14 6 9 4 3 12

i j

7 11 14 6 9 4 3 12

i j

7 3 14 6 9 4 11 12

i j

7 3 4 6 9 14 11 12

i j

7 3 4 6 9 14 11 12

j i

6 3 4 7 9 14 11 12

4. The best case behaviour occurs for quick sort is, if

partition splits the array of size n into ____

a) n/2 : (n/2) – 1

b) n/2 : n/3

c) n/4 : 3n/2

d) n/4 : 3n/4

View Answer

Answer: a

Explanation: The best case analysis of quick sort occurs

when the partition splits the array into two subarrays,
each of size no more than n/2 since one is of size n/2 and
one of size (n/2) – 1.

5. Quick sort is a stable sorting algorithm.

a) True

b) False

View Answer

Answer: b

Explanation: In stable sorting algorithm the records with

equal keys appear in the same order in the sorted
sequence as they appear in the input unsorted sequence.
Quick sort does not preserve the relative order of equal
sort items. Therefore, Quick sort is not a stable sort.

6. Consider the Quick sort algorithm in which the

partitioning procedure splits elements into two sub-arrays
and each sub-array contains at least one-fourth of the
elements. Let T(n) be the number of comparisons required
to sort array of n elements. Then

a) T(n) <= 2 T(n/4) + cn

b) T(n) <= T(n/4) + T(3n/4) + cn

c) T(n) <= 2 T(3n/4) + cn

d) T(n) <= T(n/3) + T(3n/4) + cn

View Answer

Answer: b

Explanation: If there are n/4 elements in one sub-array

then T(n/4) comparisons are needed for this sub-array.
And T(3n/4) comparison are required for the rest 4n/5
elements, and cn is time required for finding the pivot. If
there are more than n/4 elements in one sub-array then
other sub-array will have less than 3n/4 elements and time
complexity will be less than T(n/4) + T(3n/4) + cn.
7. Consider the Quick sort algorithm which sorts elements
in ascending order using the first element as pivot. Then
which of the following input sequence will require a
maximum number of comparisons when this algorithm is
applied on it?

a) 22 25 56 67 89

b) 52 25 76 67 89

c) 22 25 76 67 50

d) 52 25 89 67 76

View Answer

Answer: a

Explanation: If the input sequence is already sorted then

worst case behaviour occurs for the Quick sort algorithm
which use the first element as pivot. Therefore, the input
sequence given in 22 25 56 67 89 will require a maximum
number of comparisons.

8. A machine needs a minimum of 200 sec to sort 1000

elements by Quick sort. The minimum time needed to sort
200 elements will be approximately

a) 60.2 sec

b) 45.54 sec

c) 31.11 sec

d) 20 sec

View Answer

Answer: c
Explanation: The Quick sort requires nlog2n comparisons
in best case, where n is size of input array. So, 1000 *
log21000 ≈ 9000 comparisons are required to sort 1000
elements, which takes 200 sec. To sort 200 elements
minimum of 200 * log2200 ≈ 1400 comparisons are
required. This will take 200 * 1400 / 9000 ≈ 31.11 sec.

9. Which one of the following sorting algorithm is best

suited to sort an array of 1 million elements?

a) Bubble sort

b) Insertion sort

c) Merge sort

d) Quick sort

View Answer

Answer: d

Explanation: The Quick sort is best suited to sort the array

of 1 million elements. The practical implementations of
Quick sort use randomised version. In practice randomised
Quick sort algorithms rarely shows worst case behaviour
and is almost always O(nlogn). And Quick sort requires
little additional space and exhibits good cache locality.

10. Quick sort is a space-optimised version of __

a) Bubble sort

b) Selection sort

c) Insertion sort

d) Binary tree sort

View Answer
Answer: d

Explanation: Quick sort is a space-optimised version of the

binary tree sort. In binary sort tree, the elements are
inserted sequentially into the binary search tree and Quick
sort organises elements into a tree that is implied by the
recursive calls.

[7:39 AM, 12/14/2020] ZaHeeR ShahZaiB: 1. QuickSort can

be categorized into which of the following?

a) Brute Force technique

b) Divide and conquer

c) Greedy algorithm

d) Dynamic programming

View Answer

Answer: b

Explanation: First you divide(partition) the array based on

the pivot element and sort accordingly.

2. Select the appropriate recursive call for QuickSort.(arr is

the array, low is the starting index and high is the ending
index of the array, partition returns the pivot element, we
will see the code for partition very soon)

a)

public static void quickSort(int[] arr, int low, int high)

int pivot;

if(high>low)
{

pivot = partition(arr, low, high);

quickSort(arr, low, pivot-1);

quickSort(arr, pivot+1, high);

b)

public static void quickSort(int[] arr, int low, int high)

int pivot;

if(high<low)

pivot = partition(arr, low, high);

quickSort(arr, low, pivot-1);

quickSort(arr, pivot+1, high);

c)

public static void quickSort(int[] arr, int low, int high)

int pivot;

if(high>low)
{

pivot = partition(arr, low, high);

quickSort(arr, low, pivot);

quickSort(arr, pivot, high);

d)

public static void quickSort(int[] arr, int low, int high)

int pivot;

if(high>low)

pivot = partition(arr, low, high);

quickSort(arr, low, pivot);

quickSort(arr, pivot+2, high);

View Answer

Answer: a

Explanation: Based on the pivot returned by the call to

partition, recursive calls to quickSort sort the given array.

3. What is the worst case complexity of QuickSort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: When the input array is already sorted.

4. What is a randomized QuickSort?

a) The leftmost element is chosen as the pivot

b) The rightmost element is chosen as the pivot

c) Any element in the array is chosen as the pivot

d) A random number is generated which is used as the

pivot

View Answer

Answer: c

Explanation: QuickSort is randomized by placing the input

data in the randomized fashion in the array or by choosing
a random element in the array as a pivot.

5. Which of the following code performs the partition

operation in QuickSort?

a)

private static int partition(int[] arr, int low, int high)

{
int left, right, pivot_item = arr[low];

left = low;

right = high;

while(left > right)

while(arr[left] <= pivot_item)

left++;

while(arr[right] > pivot_item)

right--;

if(left < right)

swap(arr, left, right);

arr[low] = arr[right];

arr[right] = pivot_item;

return right;

b)
private static int partition(int[] arr, int low, int high)

int left, right, pivot_item = arr[low];

left = low;

right = high;

while(left <= right)

while(arr[left] <= pivot_item)

left++;

while(arr[right] > pivot_item)

right--;

if(left < right)

swap(arr, left, right);

arr[low] = arr[right];

arr[right] = pivot_item;

return right;

}
c)

private static int partition(int[] arr, int low, int high)

int left, right, pivot_item = arr[low];

left = low;

right = high;

while(left <= right)

while(arr[left] > pivot_item)

left++;

while(arr[right] <= pivot_item)

right--;

if(left < right)

swap(arr, left, right);

arr[low] = arr[right];

arr[right] = pivot_item;
return right;

d)

private static int partition(int[] arr, int low, int high)

int left, right, pivot_item = arr[low];

left = low;

right = high;

while(left > right)

while(arr[left] > pivot_item)

left++;

while(arr[right] <= pivot_item)

right--;

if(left < right)

swap(arr, left, right);

}
arr[low] = arr[right];

arr[right] = pivot_item;

return right;

View Answer

Answer: b

Explanation: The array is partitioned such that the

elements left to the pivot are lesser than the pivot while
the elements right of the pivot are greater than the pivot.

6. What is the best case complexity of QuickSort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: a

Explanation: The array is partitioned into equal halves,

using the Divide and Conquer master theorem, the
complexity is found to be O(nlogn).

7. The given array is arr = {2,3,4,1,6}. What are the

pivots that are returned as a result of subsequent
partitioning?

a) 1 and 3

b) 3 and 1

c) 2 and 6
d) 6 and 2

View Answer

Answer: a

Explanation: The call to partition returns 1 and 3 as the

pivot elements.

8. What is the average case complexity of QuickSort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: a

Explanation: The position of partition(split) is unknown,

hence all(n) possibilities are considered, the average is
found by adding all and dividing by n.

9. The given array is arr = {2,6,1}. What are the pivots

that are returned as a result of subsequent partitioning?

a) 1 and 6

b) 6 and 1

c) 2 and 6

d) 1

View Answer

Answer: d
Explanation: There is only one pivot with which the array
will be sorted, the pivot is 1.

10. Which of the following is not true about QuickSort?

a) in-place algorithm

b) pivot position can be changed

c) adaptive sorting algorithm

d) can be implemented as a stable sort

View Answer

Answer: b

Explanation: Once a pivot is chosen, its position is finalized

in the sorted array, it cannot be modified.

[7:41 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Recursive Insertion Sort”.

1. Which of the following is an advantage of recursive

insertion sort over its iterative version?

a) it has better time complexity

b) it has better space complexity

c) it is easy to implement

d) it has no significant advantage

View Answer

Answer: d
Explanation: Recursive insertion sort has no significant
advantage over iterative insertion sort. It is just a different
way to implement the same.

2. Insertion sort is an online sorting algorithm.

a) true

b) false

View Answer

Answer: a

Explanation: Insertion sort does not require the entire

input data in the beginning itself in order to sort the array.
It rather creates a partial solution in every step, so future
elements are not required to be considered. Hence it is an
online sorting algorithm.

3. What will be the recurrence relation of the code of

recursive insertion sort?

a) T(n) = 2T(n/2) + n

b) T(n) = 2T(n/2) + c

c) T(n) = T(n-1) + n

d) T(n) = T(n-1) + c

View Answer

Answer: c

Explanation: The recurrence relation of the code of

recursive insertion sort is T(n) = T(n-1) + n. It can be
solved by the method of substitution and is found to be
equal to n2.

4. Which of the following sorting algorithm is stable?

a) Selection sort

b) Quick sort

c) Insertion sort

d) Heap sort

View Answer

Answer: c

Explanation: Out of the given options insertion sort is the

only algorithm which is stable. It is because the elements
with identical values appear in the same order in the
output array as they were in the input array.

5. Which of the following is a variant of insertion sort?

a) selection sort

b) shell sort

c) odd-even sort

d) stupid sort

View Answer

Answer: b

Explanation: Shell sort is a variation of insertion sort. It

has a better running time in practical applications.

6. Recursive insertion sort is a comparison based sort.

a) True

b) False

View Answer
Answer: a

Explanation: In insertion sort, we need to compare

elements in order to find the minimum element in each
iteration. So we can say that it uses comparisons in order
to sort the array. Thus it qualifies as a comparison based
sort.

7. What is the average case time complexity of recursive

insertion sort?

a) O(n)

b) O(n log n)

c) O(n2)

d) O(log n)

View Answer

Answer: c

Explanation: The overall recurrence relation of recursive

insertion sort is given by T(n) = T(n-1) + n. It is found to
be equal to O(n2).

8. What is the best case time complexity of recursive

insertion sort?

a) O(n)

b) O(n log n)

c) O(n2)

d) O(log n)

View Answer

Answer: a
Explanation: The best case time complexity of recursive
insertion sort is O(n). It occurs in the case when the input
is already/almost sorted.

9. What is the worst case time complexity of recursive

insertion sort?

a) O(n)

b) O(n log n)

c) O(n2)

d) O(log n)

View Answer

Answer: c

Explanation: The overall recurrence relation of recursive

insertion sort is given by T(n) = T(n-1) + n. It is found to
be equal to O(n2).

10. How many swaps will be required in the worst case to

sort an array having n elements using binary insertion
sort?

a) n

b) 1

c) n * log n

d) log n

View Answer

Answer: d

Explanation: In a normal insertion sort at most n

comparisons are required to sort the array. But if we also
implement the concept of a binary sort in insertion sort
then we can sort by having log n comparisons only.

11. What will be the base case for the code of recursive
insertion sort ?

a)

if(n < 1)

return;

b)

if(n == 0)

return;

c)

if(n <= 1)

return;

d)

If(n == 2)

return;

View Answer

Answer: c

Explanation: The most appropriate condition for the base

case of recursive insertion sort is when n is less than or
equal 1 then return. It is because we know that an array
with only 1 element is always sorted.
12. What is the auxiliary space complexity of recursive
insertion sort?

a) O(n)

b) O(1)

c) O(n log n)

d) O(n2)

View Answer

Answer: b

Explanation: The auxiliary space required by recursive

insertion sort is O(1). So it qualifies as an in place sorting
algorithm.

13. Which of the following is an adaptive sorting

algorithm?

a) recursive insertion sort

b) merge sort

c) heap sort

d) selection sort

View Answer

Answer: a

Explanation: Insertion sort is an adaptive algorithm. It is

because the time complexity of the algorithm improves
when the input array is almost sorted.
14. Which of the following sorting algorithm is in place?

a) recursive insertion sort

b) merge sort

c) radix sort

d) counting sort

View Answer

Answer: a

Explanation: Out of the given options recursive insertion

sort is the only algorithm which is in place. It is because
the auxiliary space required by recursive bubble sort is
O(1).

15.Choose the correct function for recursive insertion sort?

a)

void RecInsertionSort(int arr[], int n)

if (n <= 1)

return;

RecInsertionSort( arr, n-1 );

int key = arr[n-1];

int j = n-2;

while (j >= 0 && arr[j] > key)

arr[j+1] = arr[j];
j--;

arr[j+1] = key;

b)

void RecInsertionSort(int arr[], int n)

if (n < 1)

return;

RecInsertionSort( arr, n-1 );

int key = arr[n-1];

int j = n-2;

while (j >= 0 || arr[j] > key)

arr[j+1] = arr[j];

j--;

arr[j] = key;

}
c)

void RecInsertionSort(int arr[], int n)

if (n <1)

return;

RecInsertionSort( arr, n-1 );

int key = arr[n-1];

int j = n-2;

while (j >= 0 && arr[j] > key)

arr[j+1] = arr[j];

j--;

arr[j] = key;

d)

void RecInsertionSort(int arr[], int n)

{
if (n <= 1)

return;

RecInsertionSort( arr, n-1 );

int key = arr[n-1];

int j = n-1;

while (j >= 0 || arr[j] > key)

arr[j+1] = arr[j];

j--;

arr[j+1] = key;

View Answer

Answer: a

Explanation: The base case of recursive bubble sort should

be when n equal or less than 1 then return. Also we need
to insert the element being chosen as key at its correct
position in the sorted array to its left. All this needs to be
done in a recursive code.

[7:43 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Recursive Bubble Sort”.
1. Which of the following is an advantage of recursive
bubble sort over its iterative version?

a) it has better time complexity

b) it has better space complexity

c) it is easy to implement

d) it has no significant advantage

View Answer

Answer: d

Explanation: Recursive bubble sort has no significant

advantage over iterative bubble sort. It is just a different
way to implement the same.

2. Bubble sort is also known as _____

a) stupid sort

b) ship sort

c) sinking sort

d) shell sort

View Answer

Answer: c

Explanation: Bubble sort is also referred to as sinking sort.

It continuously compares the value of adjacent elements
as it traverses through an array and swaps the elements
which are out of order.

3. What will be the recurrence relation of the code of

recursive bubble sort?

a) T(n) = 2T(n/2) + n
b) T(n) = 2T(n/2) + c

c) T(n) = T(n-1) + n

d) T(n) = T(n-1) + c

View Answer

Answer: c

Explanation: The recurrence relation of the code of

recursive bubble sort is T(n) = T(n-1) + n. It can be solved
by the method of substitution and is found to be equal to
n2.

4. Which of the following sorting algorithm is stable?

a) Selection sort

b) Quick sort

c) Bubble sort

d) Heap sort

View Answer

Answer: c

Explanation: Out of the given options bubble sort is the

only algorithm which is stable. It is because the elements
with identical values appear in the same order in the
output array as they were in the input array.

5. Which of the following is a variation of bubble sort?

a) selection sort

b) odd even sort

c) cocktail sort
d) stupid sort

View Answer

Answer: b

Explanation: Odd even sort is a variation of bubble sort.

But unlike bubble sort, odd even sort traverses the array
in two phases- odd phase and even phase.

6. Recursive bubble sort is a comparison based sort.

a) true

b) false

View Answer

Answer: a

Explanation: In bubble sort, we need to compare elements

in order to find the minimum element in each iteration. So
we can say that it uses comparisons in order to sort the
array. Thus it qualifies as a comparison based sort.

7. What is the average case time complexity of recursive

bubble sort?

a) O(n)

b) O(n log n)

c) O(n2)

d) O(log n)

View Answer

Answer: c
Explanation: The overall recurrence relation of recursive
bubble sort is given by T(n) = T(n-1) + n. It is found to be
equal to O(n2).

8. What is the best case time complexity of recursive

bubble sort?

a) O(n)

b) O(n log n)

c) O(n2)

d) O(log n)

View Answer

Answer: a

Explanation: The best case time complexity of recursive

bubble sort is O(n). It occurs in the case when the input is
already/almost sorted.

9. What is the worst case time complexity of recursive

bubble sort?

a) O(n)

b) O(n log n)

c) O(n2)

d) O(log n)

View Answer

Answer: c

Explanation: The overall recurrence relation of recursive

bubble sort is given by T(n) = T(n-1) + n. It is found to be
equal to O(n2).
10. What are the number of swaps required to sort the
array arr={1, 2, 4, 3, 7, 5, 6} using recursive bubble sort?

a) 0

b) 1

c) 2

d) 3

View Answer

Answer: d

Explanation: The first swap takes place between 4 and 3

then the second swap takes place between 7 and 5 and
then finally 6 and 7 are swapped which sorts our array.

11. What will be the base case for the code of recursive
bubble sort?

a)

if(n < 1)

return;

b)

if(n == 0)

return;

c)

if(n == 1)

return;
d)

If(n == 2)

return;

View Answer

Answer: c

Explanation: The most appropriate condition for the base

case of recursive bubble sort is when n equal 1 then
return. It is because we know that an array with only 1
element is always sorted.

12. What is the auxiliary space complexity of recursive

bubble sort?

a) O(n)

b) O(1)

c) O(n log n)

d) O(n2)

View Answer

Answer: b

Explanation: The auxiliary space required by recursive

bubble sort is O(1). So it qualifies as an in-place sorting
algorithm.

13. Bubble sort is an adaptive sorting algorithm.

a) true
b) false

View Answer

Answer: a

Explanation: Bubble sort is an adaptive algorithm. It is

because the time complexity of the algorithm improves
when the input array is almost sorted.

14. Which of the following sorting algorithm is in place?

a) recursive bubble sort

b) merge sort

c) radix sort

d) counting sort

View Answer

Answer: a

Explanation: Out of the given options recursive bubble sort

is the only algorithm which is in place. It is because the
auxiliary space required by recursive bubble sort is O(1).

15. Choose the correct function for recursive bubble sort?

a)

void rec_bubbleSort(int arr[], int n)

if (n == 1)

return;

for (int i=0; i<n-1; i++)

if (arr[i] > arr[i+1])

swap(arr[i], arr[i+1]);

rec_bubbleSort(arr, n-1);

b)

void rec_bubbleSort(int arr[], int n)

if (n == 2)

return;

for (int i=0; i<n-1; i++)

if (arr[i] > arr[i+1])

swap(arr[i], arr[i+1]);

rec_bubbleSort(arr, n-1);

c)

void rec_bubbleSort(int arr[], int n)

if (n == 1)
return;

for (int i=0; i<n-1; i++)

if (arr[i] < arr[i+1])

swap(arr[i], arr[i+1]);

rec_bubbleSort(arr, n-1);

d)

void rec_bubbleSort(int arr[], int n)

if (n == 2)

return;

for (int i=0; i<n-1; i++)

if (arr[i] < arr[i+1])

swap(arr[i], arr[i+1]);

rec_bubbleSort(arr, n-1);

View Answer
Answer: a

Explanation: The base case of the recursive bubble sort

should be 1 when equal 1 then return. It is because we
know that an array with only 1 element is always sorted.
Also, we need to swap the adjacent elements which are
out of order.

[7:46 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Multiple Choice Questions & Answers (MCQs)
focuses on “Recursion”.

1. Recursion is a method in which the solution of a

problem depends on ____

a) Larger instances of different problems

b) Larger instances of the same problem

c) Smaller instances of the same problem

d) Smaller instances of different problems

View Answer

Answer: c

Explanation: In recursion, the solution of a problem

depends on the solution of smaller instances of the same
problem.

2. Which of the following problems can’t be solved using

recursion?

a) Factorial of a number

b) Nth fibonacci number

c) Length of a string

d) Problems without base case

View Answer

Answer: d

Explanation: Problems without base case leads to infinite

recursion call. In general, we will assume a base case to
avoid infinite recursion call. Problems like finding Factorial
of a number, Nth Fibonacci number and Length of a string
can be solved using recursion.

3. Recursion is similar to which of the following?

a) Switch Case

b) Loop

c) If-else

d) if elif else

View Answer

Answer: b

Explanation: Recursion is similar to a loop.

4. In recursion, the condition for which the function will

stop calling itself is ____

a) Best case

b) Worst case

c) Base case

d) There is no such condition

View Answer

Answer: c
Explanation: For recursion to end at some point, there
always has to be a condition for which the function will not
call itself. This condition is known as base case.

5. Consider the following code snippet:

void my_recursive_function()

my_recursive_function();

int main()

my_recursive_function();

return 0;

What will happen when the above snippet is executed?

a) The code will be executed successfully and no output

will be generated

b) The code will be executed successfully and random

output will be generated

c) The code will show a compile time error

d) The code will run for some time and stop when the
stack overflows

View Answer

Answer: d
Explanation: Every function call is stored in the stack
memory. In this case, there is no terminating
condition(base case). So, my_recursive_function() will be
called continuously till the stack overflows and there is no
more space to store the function calls. At this point of time,
the program will stop abruptly.

6. What is the output of the following code?

void my_recursive_function(int n)

if(n == 0)

return;

printf("%d ",n);

my_recursive_function(n-1);

int main()

my_recursive_function(10);

return 0;

a) 10

b) 1

c) 10 9 8 … 1 0

d) 10 9 8 … 1

View Answer
Answer: d

Explanation: The program prints the numbers from 10 to

1.

7. What is the base case for the following code?

void my_recursive_function(int n)

if(n == 0)

return;

printf("%d ",n);

my_recursive_function(n-1);

int main()

my_recursive_function(10);

return 0;

a) return

b) printf(“%d “, n)

c) if(n == 0)

d) my_recursive_function(n-1)

View Answer

Answer: c
Explanation: For the base case, the recursive function is
not called. So, “if(n == 0)” is the base case.

8. How many times is the recursive function called, when

the following code is executed?

void my_recursive_function(int n)

if(n == 0)

return;

printf("%d ",n);

my_recursive_function(n-1);

int main()

my_recursive_function(10);

return 0;

a) 9

b) 10

c) 11

d) 12

View Answer

Answer: c

Explanation: The recursive function is called 11 times.

9. What does the following recursive code do?

void my_recursive_function(int n)

if(n == 0)

return;

my_recursive_function(n-1);

printf("%d ",n);

int main()

my_recursive_function(10);

return 0;

a) Prints the numbers from 10 to 1

b) Prints the numbers from 10 to 0

c) Prints the numbers from 1 to 10

d) Prints the numbers from 0 to 10

View Answer

Answer: c

Explanation: The above code prints the numbers from 1 to

10.

10. Which of the following statements is true?

a) Recursion is always better than iteration

b) Recursion uses more memory compared to iteration

c) Recursion uses less memory compared to iteration

d) Iteration is always better and simpler than recursion

View Answer

Answer: b

Explanation: Recursion uses more memory compared to

iteration because every time the recursive function is
called, the function call is stored in stack.

11. What will be the output of the following code?

int cnt=0;

void my_recursive_function(int n)

if(n == 0)

return;

cnt++;

my_recursive_function(n/10);

int main()

my_recursive_function(123456789);

printf("%d",cnt);

return 0;

}
a) 123456789

b) 10

c) 0

d) 9

View Answer

Answer: d

Explanation: The program prints the number of digits in

the number 123456789, which is 9.

12. What will be the output of the following code?

void my_recursive_function(int n)

if(n == 0)

printf("False");

return;

if(n == 1)

printf("True");

return;

if(n%2==0)

my_recursive_function(n/2);
else

printf("False");

return;

int main()

my_recursive_function(100);

return 0;

a) True

b) False

View Answer

Answer: b

Explanation: The function checks if a number is a power of

2. Since 100 is not a power of 2, it prints false.

13. What is the output of the following code?

int cnt = 0;

void my_recursive_function(char *s, int i)

if(s[i] == '\0')
return;

if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' ||

s[i] == 'u')

cnt++;

my_recursive_function(s,i+1);

int main()

my_recursive_function("thisisrecursion",0);

printf("%d",cnt);

return 0;

a) 6

b) 9

c) 5

d) 10

View Answer

Answer: a

Explanation: The function counts the number of vowels in

a string. In this case the number is vowels is 6.

14. What is the output of the following code?

void my_recursive_function(int *arr, int val, int idx, int len)

{
if(idx == len)

printf("-1");

return ;

if(arr[idx] == val)

printf("%d",idx);

return;

my_recursive_function(arr,val,idx+1,len);

int main()

int array[10] = {7, 6, 4, 3, 2, 1, 9, 5, 0, 8};

int value = 2;

int len = 10;

my_recursive_function(array, value, 0, len);

return 0;

a) 3

b) 4

c) 5

d) 6
View Answer

Answer: b

Explanation: The program searches for a value in the

given array and prints the index at which the value is
found. In this case, the program searches for value = 2.
Since, the index of 2 is 4(0 based indexing), the program
prints 4.

[7:48 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Multiple Choice Questions & Answers (MCQs)
focuses on “Queue Operations”.

1. A linear list of elements in which deletion can be done

from one end (front) and insertion can take place only at
the other end (rear) is known as _____

a) Queue

b) Stack

c) Tree

d) Linked list

View Answer

Answer: a

Explanation: Linear list of elements in which deletion is

done at front side and insertion at rear side is called
Queue. In stack we will delete the last entered element
first.

2. The data structure required for Breadth First Traversal

on a graph is?
a) Stack

b) Array

c) Queue

d) Tree

View Answer

Answer: c

Explanation: In Breadth First Search Traversal, BFS,

starting vertex is first taken and adjacent vertices which
are unvisited are also taken. Again, the first vertex which
was added as an unvisited adjacent vertex list will be
considered to add further unvisited vertices of the graph.
To get the first unvisited vertex we need to follows First In
First Out principle. Queue uses FIFO principle.

3. A queue follows ____

a) FIFO (First In First Out) principle

b) LIFO (Last In First Out) principle

c) Ordered array

d) Linear tree

View Answer

Answer: a

Explanation: Element first added in queue will be deleted

first which is FIFO principle.

4. Circular Queue is also known as ____

a) Ring Buffer

b) Square Buffer
c) Rectangle Buffer

d) Curve Buffer

View Answer

Answer: a

Explanation: Circular Queue is also called as Ring Buffer.

Circular Queue is a linear data structure in which last
position is connected back to the first position to make a
circle. It forms a ring structure.

5. If the elements “A”, “B”, “C” and “D” are placed in a

queue and are deleted one at a time, in what order will
they be removed?

a) ABCD

b) DCBA

c) DCAB

d) ABDC

View Answer

Answer: a

Explanation: Queue follows FIFO approach. i.e. First in First

Out Approach. So, the order of removal elements are
ABCD.

6. A data structure in which elements can be inserted or

deleted at/from both ends but not in the middle is?

a) Queue

b) Circular queue

c) Dequeue
d) Priority queue

View Answer

Answer: c

Explanation: In dequeuer, we can insert or delete

elements from both the ends. In queue, we will follow first
in first out principle for insertion and deletion of elements.
Element with least priority will be deleted in a priority
queue.

7. A normal queue, if implemented using an array of size

MAX_SIZE, gets full when?

a) Rear = MAX_SIZE – 1

b) Front = (rear + 1)mod MAX_SIZE

c) Front = rear + 1

d) Rear = front

View Answer

Answer: a

Explanation: When Rear = MAX_SIZE – 1, there will be no

space left for the elements to be added in queue. Thus
queue becomes full.

8. Queues serve major role in ______

a) Simulation of recursion

b) Simulation of arbitrary linked list

c) Simulation of limited resource allocation

d) Simulation of heap sort

View Answer
Answer: c

Explanation: Simulation of recursion uses stack data

structure. Simulation of arbitrary linked lists uses linked
lists. Simulation of resource allocation uses queue as first
entered data needs to be given first priority during
resource allocation. Simulation of heap sort uses heap
data structure.

9. Which of the following is not the type of queue?

a) Ordinary queue

b) Single ended queue

c) Circular queue

d) Priority queue

View Answer

Answer: b

Explanation: Queue always has two ends. So, single ended

queue is not the type of queue.

[7:49 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Multiple Choice Questions & Answers (MCQs)
focuses on “Stack Operations – 1”.

1. Process of inserting an element in stack is called ____

a) Create

b) Push

c) Evaluation

d) Pop
View Answer

Answer: b

Explanation: Push operation allows users to insert

elements in the stack. If the stack is filled completely and
trying to perform push operation stack – overflow can
happen.

2. Process of removing an element from stack is called

____

a) Create

b) Push

c) Evaluation

d) Pop

View Answer

Answer: d

Explanation: Elements in the stack are removed using pop

operation. Pop operation removes the top most element in
the stack i.e. last entered element.

3. In a stack, if a user tries to remove an element from an

empty stack it is called ___

a) Underflow

b) Empty collection

c) Overflow

d) Garbage Collection

View Answer
Answer: a

Explanation: Underflow occurs when the user performs a

pop operation on an empty stack. Overflow occurs when
the stack is full and the user performs a push operation.
Garbage Collection is used to recover the memory
occupied by objects that are no longer used.

4. Pushing an element into stack already having five

elements and stack size of 5, then stack becomes _____

a) Overflow

b) Crash

c) Underflow

d) User flow

View Answer

Answer: a

Explanation: The stack is filled with 5 elements and

pushing one more element causes a stack overflow. This
results in overwriting memory, code and loss of unsaved
work on the computer.

5. Entries in a stack are “ordered”. What is the meaning of

this statement?

a) A collection of stacks is sortable

b) Stack entries may be compared with the ‘<‘ operation

c) The entries are stored in a linked list

d) There is a Sequential entry that is one by one

View Answer
Answer: d

Explanation: In stack data structure, elements are added

one by one using push operation. Stack follows LIFO
Principle i.e. Last In First Out(LIFO).

6. Which of the following is not the application of stack?

a) A parentheses balancing program

b) Tracking of local variables at run time

c) Compiler Syntax Analyzer

d) Data Transfer between two asynchronous process

View Answer

Answer: d

Explanation: Data transfer between the two asynchronous

process uses the queue data structure for synchronisation.
The rest are all stack applications.

7. Consider the usual algorithm for determining whether a

sequence of parentheses is balanced. The maximum
number of parentheses that appear on the stack AT ANY
ONE TIME when the algorithm analyzes: (()(())(()))?

a) 1

b) 2

c) 3

d) 4 or more

View Answer

Answer: c
Explanation: In the entire parenthesis balancing method
when the incoming token is a left parenthesis it is pushed
into stack. A right parenthesis makes pop operation to
delete the elements in stack till we get left parenthesis as
top most element. 3 elements are there in stack before
right parentheses comes. Therefore, maximum number of
elements in stack at run time is 3.

8. Consider the usual algorithm for determining whether a

sequence of parentheses is balanced. Suppose that you
run the algorithm on a sequence that contains 2 left
parentheses and 3 right parentheses (in some order). The
maximum number of parentheses that appear on the
stack AT ANY ONE TIME during the computation?

a) 1

b) 2

c) 3

d) 4 or more

View Answer

Answer: b

Explanation: In the entire parenthesis balancing method

when the incoming token is a left parenthesis it is pushed
into stack. A right parenthesis makes pop operation to
delete the elements in stack till we get left parenthesis as
top most element. 2 left parenthesis are pushed whereas
one right parenthesis removes one of left parenthesis. 2
elements are there before right parenthesis which is the
maximum number of elements in stack at run time.

9. What is the value of the postfix expression 6 3 2 4 + –

*?

a) 1
b) 40

c) 74

d) -18

View Answer

Answer: d

Explanation: Postfix Expression is (6*(3-(2+4))) which

results -18 as output.

10. Here is an infix expression: 4 + 3*(6*3-12). Suppose

that we are using the usual stack algorithm to convert the
expression from infix to postfix notation. The maximum
number of symbols that will appear on the stack AT ONE
TIME during the conversion of this expression?

a) 1

b) 2

c) 3

d) 4

View Answer

Answer: d

Explanation: When we perform the conversion from infix

to postfix expression +, *, (, * symbols are placed inside
the stack. A maximum of 4 symbols are identified during
the entire conversion.

[7:50 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Interview Questions and Answers focuses on
“Stack Operations – 2”.
1. The postfix form of the expression (A+ B)*(C*D- E)*F / G
is?

a) AB+ CD*E – FG /**

b) AB + CD* E – F **G /

c) AB + CD* E – *F *G /

d) AB + CDE * – * F *G /

View Answer

Answer: c

Explanation: (((A+ B)*(C*D- E)*F) / G) is converted to

postfix expression as

(AB+(*(C*D- E)*F )/ G)

(AB+CD*E-*F) / G

(AB+CD*E-*F * G/). Thus Postfix expression is

AB+CD*E-*F*G/

2. The data structure required to check whether an

expression contains balanced parenthesis is?

a) Stack

b) Queue

c) Array

d) Tree

View Answer

Answer: a

Explanation: The stack is a simple data structure in which

elements are added and removed based on the LIFO
principle. Open parenthesis is pushed into the stack and a
closed parenthesis pops out elements till the top element
of the stack is its corresponding open parenthesis. If the
stack is empty, parenthesis is balanced otherwise it is
unbalanced.

3. What data structure would you mostly likely see in a

non recursive implementation of a recursive algorithm?

a) Linked List

b) Stack

c) Queue

d) Tree

View Answer

Answer: b

Explanation: In recursive algorithms, the order in which

the recursive process comes back is the reverse of the
order in which it goes forward during execution. The
compiler uses the stack data structure to implement
recursion. In the forwarding phase, the values of local
variables, parameters and the return address are pushed
into the stack at each recursion level. In the backing-out
phase, the stacked address is popped and used to execute
the rest of the code.

4. The process of accessing data stored in a serial access

memory is similar to manipulating data on a ____

a) Heap

b) Binary Tree

c) Array

d) Stack
View Answer

Answer: d

Explanation: In serial access memory data records are

stored one after the other in which they are created and
are accessed sequentially. In stack data structure,
elements are accessed sequentially. Stack data structure
resembles the serial access memory.

5. The postfix form of A*B+C/D is?

a) *AB/CD+

b) AB*CD/+

c) A*BC+/D

d) ABCD+/*

View Answer

Answer: b

Explanation: Infix expression is (A*B)+(C/D)

AB*+(C/D)

AB*CD/+. Thus postfix expression is AB*CD/+.

6. Which data structure is needed to convert infix notation

to postfix notation?

a) Branch

b) Tree

c) Queue

d) Stack

View Answer
Answer: d

Explanation: The Stack data structure is used to convert

infix expression to postfix expression. The purpose of
stack is to reverse the order of the operators in the
expression. It also serves as a storage structure, as no
operator can be printed until both of its operands have
appeared.

7. The prefix form of A-B/ (C * D ^ E) is?

a) -/*^ACBDE

b) -ABCD*^DE

c) -A/B*C^DE

d) -A/BC*^DE

View Answer

Answer: c

Explanation: Infix Expression is (A-B)/(C*D^E)

(-A/B)(C*D^E)

-A/B*C^DE. Thus prefix expression is -A/B*C^DE

8. What is the result of the following operation?

Top (Push (S, X))

a) X

b) X+S

c) S

d) XS

View Answer
Answer: a

Explanation: The function Push(S,X) pushes the value X in

the stack S. Top() function gives the value which entered
last. X entered into stack S at last.

9. The prefix form of an infix expression (p + q) – (r * t) is?

a) + pq – *rt

b) – +pqr * t

c) – +pq * rt

d) – + * pqrt

View Answer

Answer: c

Explanation: Given Infix Expression is ((p+q)-(r*t))

(+pq)-(r*t)

(-+pq)(r*t)

-+pq*rt. Thus prefix expression is -+pq*rt.

10. Which data structure is used for implementing

recursion?

a) Queue

b) Stack

c) Array

d) List

View Answer
Answer: b

Explanation: Stacks are used for the implementation of

Recursion.

[7:51 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Questions and Answers for Freshers focuses on
“Stack Operations – 3”.

1. The result of evaluating the postfix expression 5, 4, 6, +,

*, 4, 9, 3, /, +, * is?

a) 600

b) 350

c) 650

d) 588

View Answer

Answer: b

Explanation: The postfix expression is evaluated using

stack. We will get the infix expression as

(5*(4+6))*(4+9/3). On solving the Infix Expression, we get

(5*(10))*(4+3)

= 50*7

= 350.

2. Convert the following infix expressions into its

equivalent postfix expressions.

(A + B ⋀D)/(E – F)+G

a) (A B D ⋀ + E F – / G +)
b) (A B D +⋀ E F – / G +)

c) (A B D ⋀ + E F/- G +)

d) (A B D E F + ⋀ / – G +)

View Answer

Answer: a

Explanation: The given infix expression is (A + B ⋀D)/(E –

F)+G.

(A B D ^ + ) / (E – F) +G

(A B D ^ + E F – ) + G. ‘/’ is present in stack.

A B D ^ + E F – / G +. Thus Postfix Expression is A B D ^ +

E F – / G +.

3. Convert the following Infix expression to Postfix form

using a stack.

x + y * z + (p * q + r) * s, Follow usual precedence rule

and assume that the expression is legal.

a) xyz*+pq*r+s*+

b) xyz*+pq*r+s+*

c) xyz+pq*r+s+

d) xyzp+*qr+s+

View Answer

Answer: a

Explanation: The Infix Expression is x + y * z + (p * q + r)

* s.

(x y z ) + (p * q + r) * s. ‘+’, ‘*’ are present in stack.

(x y z * + p q * r) * s. ‘+’ is present in stack.

x y z * + p q * r + s * +. Thus Postfix Expression is x y z *

+ p q * r + s * +.

4. Which of the following statement(s) about stack data

structure is/are NOT correct?

a) Linked List are used for implementing Stacks

b) Top of the Stack always contain the new node

c) Stack is the FIFO data structure

d) Null link is present in the last node at the bottom of the

stack

View Answer

Answer: c

Explanation: Stack follows LIFO.

5. Consider the following operation performed on a stack

of size 5.

Push(1);

Pop();

Push(2);

Push(3);

Pop();

Push(4);

Pop();

Pop();

Push(5);
After the completion of all operation, the number of
elements present in stack is?

a) 1

b) 2

c) 3

d) 4

View Answer

Answer: a

Explanation: Number of elements present in stack is equal

to the difference between number of push operations and
number of pop operations. Number of elements is 5-4=1.

6. Which of the following is not an inherent application of

stack?

a) Reversing a string

b) Evaluation of postfix expression

c) Implementation of recursion

d) Job scheduling

View Answer

Answer: d

Explanation: Job Scheduling is not performed using stacks.

7. The type of expression in which operator succeeds its

operands is?

a) Infix Expression

b) Prefix Expression
c) Postfix Expression

d) Both Prefix and Postfix Expressions

View Answer

Answer: c

Explanation: The expression in which operator succeeds

its operands is called postfix expression. The expression in
which operator precedes the operands is called prefix
expression. If an operator is present between two
operands, then it is called infix expressions.

8. Assume that the operators +,-, X are left associative

and ^ is right associative. The order of precedence (from
highest to lowest) is ^, X, +, -. The postfix expression for
the infix expression a + b X c – d ^ e ^ f is?

a) abc X+ def ^^ –

b) abc X+ de^f^ –

c) ab+c Xd – e ^f^

d) -+aXbc^ ^def

View Answer

Answer: b

Explanation: Given Infix Expression is a + b X c – d ^ e ^

f.

(a b c X +) (d ^ e ^ f). ‘–‘ is present in stack.

(a b c X + d e ^ f ^ -). Thus the final expression is (a b c X

+ d e ^ f ^ -).
9. If the elements “A”, “B”, “C” and “D” are placed in a
stack and are deleted one at a time, what is the order of
removal?

a) ABCD

b) DCBA

c) DCAB

d) ABDC

View Answer

Answer: b

Explanation: Stack follows LIFO(Last In First Out). So the

removal order of elements are DCBA.

[7:52 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Multiple Choice Questions & Answers (MCQs)
focuses on “Queue using Array”.

1. Which of the following properties is associated with a

queue?

a) First In Last Out

b) First In First Out

c) Last In First Out

d) Last In Last Out

View Answer

Answer: b

Explanation: Queue follows First In First Out structure.

2. In a circular queue, how do you increment the rear end
of the queue?

a) rear++

b) (rear+1) % CAPACITY

c) (rear % CAPACITY)+1

d) rear–

View Answer

Answer: b

Explanation: Ensures rear takes the values from 0 to

(CAPACITY-1).

3. What is the term for inserting into a full queue known

as?

a) overflow

b) underflow

c) null pointer exception

d) program won’t be compiled

View Answer

Answer: a

Explanation: Just as stack, inserting into a full queue is

termed overflow.

4. What is the time complexity of enqueue operation?

a) O(logn)

b) O(nlogn)

c) O(n)
d) O(1)

View Answer

Answer: d

Explanation: Enqueue operation is at the rear end, it takes

O(1) time to insert a new item into the queue.

5. What does the following Java code do?

public Object function()

if(isEmpty())

return -999;

else

Object high;

high = q[front];

return high;

a) Dequeue

b) Enqueue

c) Return the front element

d) Return the last element

View Answer
Answer: c

Explanation: q[front] gives the element at the front of the

queue, since we are not moving the ‘front’ to the next
element,

it is not a dequeue operation.

6. What is the need for a circular queue?

a) effective usage of memory

b) easier computations

c) to delete elements based on priority

d) implement LIFO principle in queues

View Answer

Answer: a

Explanation: In a linear queue, dequeue operation causes

the starting elements of the array to be empty, and there
is no way you can use that space, while in a circular queue,
you can effectively use that space. Priority queue is used
to delete the elements based on their priority. Higher
priority elements will be deleted first whereas lower
priority elements will be deleted next. Queue data
structure always follows FIFO principle.

7. Which of the following represents a dequeue operation?

(count is the number of elements in the queue)

a)

public Object dequeue()

if(count == 0)
{

System.out.println("Queue underflow");

return 0;

else

Object ele = q[front];

q[front] = null;

front = (front+1)%CAPACITY;

count--;

return ele;

b)

public Object dequeue()

if(count == 0)

System.out.println("Queue underflow");

return 0;

else

{
Object ele = q[front];

front = (front+1)%CAPACITY;

q[front] = null;

count--;

return ele;

c)

public Object dequeue()

if(count == 0)

System.out.println("Queue underflow");

return 0;

else

front = (front+1)%CAPACITY;

Object ele = q[front];

q[front] = null;

count--;

return ele;

}
}

d)

public Object dequeue()

if(count == 0)

System.out.println("Queue underflow");

return 0;

else

Object ele = q[front];

q[front] = null;

front = (front+1)%CAPACITY;

return ele;

count--;

View Answer

Answer: a

Explanation: Dequeue removes the first element from the

queue, ‘front’ points to the front end of the queue and
returns the first element.
8. Which of the following best describes the growth of a
linear queue at runtime? (Q is the original queue, size()
returns the number of elements in the queue)

a)

private void expand()

int length = size();

int[] newQ = new int[length<<1];

for(int i=front; i<=rear; i++)

newQ[i-front] = Q[i%CAPACITY];

Q = newQ;

front = 0;

rear = size()-1;

b)

private void expand()

int length = size();

int[] newQ = new int[length<<1];

for(int i=front; i<=rear; i++)

{

newQ[i-front] = Q[i%CAPACITY];

Q = newQ;

c)

private void expand()

int length = size();

int[] newQ = new int[length<<1];

for(int i=front; i<=rear; i++)

newQ[i-front] = Q[i];

Q = newQ;

front = 0;

rear = size()-1;

d)

private void expand()

int length = size();

int[] newQ = new int[length*2];

for(int i=front; i<=rear; i++)

newQ[i-front] = Q[i%CAPACITY];

Q = newQ;

View Answer

Answer: a

Explanation: A common technique to expand the size of

array at run time is simply to double the size. Create a
new array of double the previous size and copy all the
elements, after copying do not forget to assign front = 0
and rear = size()-1, as these are necessary to maintain
the decorum of the queue operations.

9. What is the space complexity of a linear queue having n

elements?

a) O(n)

b) O(nlogn)

c) O(logn)

d) O(1)

View Answer

Answer: a
Explanation: Because there are n elements.

10. What is the output of the following Java code?

public class CircularQueue

protected static final int CAPACITY = 100;

protected int size,front,rear;

protected Object q[];

int count = 0;

public CircularQueue()

this(CAPACITY);

public CircularQueue (int n)

size = n;

front = 0;

rear = 0;

q = new Object[size];

public void enqueue(Object item)

{

if(count == size)

System.out.println("Queue overflow");

return;

else

q[rear] = item;

rear = (rear+1)%size;

count++;

public Object dequeue()

if(count == 0)

System.out.println("Queue underflow");

return 0;

else

Object ele = q[front];

q[front] = null;
front = (front+1)%size;

count--;

return ele;

public Object frontElement()

if(count == 0)

return -999;

else

Object high;

high = q[front];

return high;

public Object rearElement()

if(count == 0)

return -999;

else

Object low;

rear = (rear-1)%size;
low = q[rear];

rear = (rear+1)%size;

return low;

public class CircularQueueDemo

public static void main(String args[])

Object var;

CircularQueue myQ = new CircularQueue();

myQ.enqueue(10);

myQ.enqueue(3);

var = myQ.rearElement();

myQ.dequeue();

myQ.enqueue(6);

var = mQ.frontElement();

System.out.println(var+" "+var);

a) 3 3

b) 3 6

c) 6 6
d) 10 6

View Answer

Answer: a

Explanation: First enqueue 10 and 3 into the queue,

followed by a dequeue(removes 10), followed by an
enqueue(6), At this point, 3 is at the front end of the
queue and 6 at the rear end, hence a call to frontElement()
will return 3 which is displayed twice.

[7:55 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “First-in, First-out Algorithm
(FIFO)”.

1. ____ is a typical online problem from the competitive

analysis to determine the optimal solution.

a) Page replacement algorithm

b) Segmentation

c) Paging

d) Segmentation with paging

View Answer

Answer: a

Explanation: Page replacement is a typical online problem

from the competitive analysis. They determine which
pages to page out or write to disk.

2. Which of the following is the simplest page replacement

algorithm?
a) FIFO

b) Optimal page replacement

c) LRU replacement

d) Counting based replacement

View Answer

Answer: a

Explanation: FIFO is the simplest page replacement

algorithm since LRU and optimal replacement algorithms
require past and future data patterns respectively.

3. ____ algorithm associates with each page the time when

the page was brought into memory.

a) Optimal page replacement

b) FIFO

c) LRU replacement algorithm

d) Counting based replacement

View Answer

Answer: b

Explanation: FIFO algorithm associates with each page the

time when the page was brought into memory. The new
page is inserted at the tail of the queue.

4. As the number of frames available increases, the

number of page faults decreases.

a) True

b) False
View Answer

Answer: a

Explanation: One of the rules of the page replacement

algorithm is that, as the number of frames available
increases, the number of page faults decreases.

5. Which of the following page replacement algorithms

return the minimum number of page faults?

a) LRU replacement algorithm

b) Optimal page replacement algorithm

c) FIFO

d) Counting based replacement

View Answer

Answer: b

Explanation: Though FIFO is the simplest of all algorithms,

optimal page replacement algorithm returns the minimum
number of page faults.

6. Which of the following is the main drawback of FIFO

page replacement algorithm?

a) Requirement of large memory

b) Frame allocation

c) Reduction in multiprogramming

d) Reduced optimality

View Answer
Answer: c

Explanation: The main drawback of FIFO page

replacement algorithm is that it reduces the level of
multiprogramming and also causes Belady’s anomaly.

7. Which of the following is required to determine the

number of page faults in FIFO?

a) Page number

b) Page frame number

c) Memory capacity

d) Segment number

View Answer

Answer: b

Explanation: To determine the number of page faults in a

page replacement algorithm using FIFO, we require page
frame number.

8. In a FIFO algorithm, when a page is to be replaced,

which of the following page is chosen?

a) Oldest page

b) Newest page

c) Frequently occurred page in past

d) Frequently occurred page in future

View Answer

Answer: a
Explanation: In FIFO page replacement algorithm, when a
page is to be replaced, the oldest page is chosen and
replaced at the tail of the queue.

9. The cost required to execute a FIFO algorithm is

expensive.

a) True

b) False

View Answer

Answer: b

Explanation: The cost of a FIFO algorithm is cheap and

intuitive and it is used in poor practical applications.

10. FIFO algorithm is used by ____ operating system.

a) Linux

b) Mac

c) Windows

d) VAX/VMS

View Answer

Answer: d

Explanation: Of the following given operating systems,

VAX/VMS uses a FIFO algorithm.

11. What is the competitive analysis of the FIFO

algorithm?

a) k/k+1

b) k+1
c) k(k+1)

d) k/(k-h+1)

View Answer

Answer: d

Explanation: The competitive analysis of a FIFO algorithm

is mathematically found to be k/(k-h+1) where k and h are
some constants used in page replacement and always,
h<=k.

12. Under which of the following scenarios is page

replacement algorithm required?

a) When total memory exceeds physical memory

b) To determine the number of frames for each process

c) When paging and segmentation are to be used

d) Execution of a process, not in memory

View Answer

Answer: a

Explanation: An appropriate page replacement algorithm

is required when the total memory requirements exceed
the physical memory.

13. Consider a reference string:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 3.

Using FIFO algorithm, determine the number of page
faults.

a) 12

b) 16
c) 14

d) 15

View Answer

Answer: d

Explanation: For the given reference string of frame size 3,

the number of page faults is calculated to be 15. It is
explained in the diagram.

first-in-first-out-algorithm-fifo-questions-answers-q13

14. Consider a reference string:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 of frame size 4.

Using FIFO algorithm, determine the number of page
faults.

a) 12

b) 16

c) 10

d) 14

View Answer

Answer: c

Explanation: For the given reference string of frame size 4,

the number of page faults is calculated to be 10. It is
explained in the diagram.

first-in-first-out-algorithm-fifo-questions-answers-q14

15. ___ states that, on a page fault, the frame that has
been in memory the longest is replaced.

a) Belady’s anomaly
b) Second chance algorithm

c) Partial second chance algorithm

d) LRU replacement algorithm

View Answer

Answer: a

Explanation: Belady’s anomaly states that, on a page fault,

the frame that has been in memory the longest is replaced.
It occurs in FIFO algorithm.

[8:02 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structure Multiple Choice Questions & Answers (MCQs)
focuses on “Dynamic Array”.

1. What is a dynamic array?

a) A variable size data structure

b) An array which is created at runtime

c) The memory to the array is allocated at runtime

d) An array which is reallocated everytime whenever new

elements have to be added

View Answer

Answer: a

Explanation: It is a varying-size list data structure that

allows items to be added or removed, it may use a fixed
sized array at the back end.

2. What is meant by physical size in a dynamic array?

a) The size allocated to elements

b) The size extended to add new elements

c) The size of the underlying array at the back-end

d) The size visible to users

View Answer

Answer: c

Explanation: Physical size, also called array capacity is the

size of the underlying array, which is the maximum size
without relocation of data.

3. The number of items used by the dynamic array

contents is its ____

a) Physical size

b) Capacity

c) Logical size

d) Random size

View Answer

Answer: c

Explanation: The number of items used by the dynamic

array contents is called logical size. Physical size is the
size of the underlying array, which is the maximum size
without reallocation of data.

4. How will you implement dynamic arrays in Java?

a) Set

b) Map

c) HashMap
d) List

View Answer

Answer: d

Explanation: ArrayList is used to implement dynamic

arrays in Java.

5. Which of the following is the correct syntax to declare

an ArrayList in Java?

a) ArrayList al = new ArrayList();

b) ArrayList al = new ArrayList[];

c) ArrayList al() = new ArrayList();

d) ArrayList al[] = new ArrayList[];

View Answer

Answer: a

Explanation: This is a non-generic way of creating an

ArrayList.

6. Array is divided into two parts in ____

a) Hashed Array Tree

b) Geometric Array

c) Bounded-size dynamic array

d) Sparse Array

View Answer

Answer: c
Explanation: The first part stores the items of the dynamic
array and the second part is reserved for new allocations.

7. Which of the following is a disadvantage of dynamic

arrays?

a) Locality of reference

b) Data cache utilization

c) Random access

d) Memory leak

View Answer

Answer: d

Explanation: Dynamic arrays share the advantage of

arrays, added to it is the dynamic addition of elements to
the array. Memory can be leaked if it is not handled
properly during allocation and deallocation. It is a
disadvantage.

8. What is the time complexity for inserting/deleting at the

beginning of the array?

a) O(1)

b) O(n)

c) O(logn)

d) O(nlogn)

View Answer

Answer: b

Explanation: All the other elements will have to be moved,

hence O(n).
9. Dynamic arrays overcome the limit of static arrays.

a) True

b) False

View Answer

Answer: a

Explanation: Static arrays have fixed capacity. The

capacity must be specified during memory allocation.
Dynamic arrays don’t require to specify their capacity
during memory allocation. Dynamic arrays have fixed
physical size at backend and its capacity increases if
required. Thus, Dynamic arrays overcome the limit of
static arrays.

10. The size of the dynamic array is deallocated if the

array size is less than ___% of the backend physical size.

a) 30

b) 40

c) 10

d) 20

View Answer

Answer: a

Explanation: The size of the dynamic array is

decreased/deallocated if the actual size of the array is less
than 30% of the backend physical size. This is used to
avoid memory wastage.

11. Both Dynamic array and Dynamically memory

allocated array are same.
a) True

b) False

View Answer

Answer: b

Explanation: Physical size of a Dynamic array is fixed with

a larger value. Dynamically memory allocated arrays are
arrays whose memory is allocated at run time rather than
at compile time. Dynamically memory allocated arrays
don’t have physical size at the backend. Thus, Dynamic
arrays and Dynamically memory allocated arrays are
different.

12. In which of the following cases dynamic arrays are not

preferred?

a) If the size of the array is unknown

b) If the size of the array changes after few iterations

c) If the memory reallocation takes more time i.e.

expensive

d) If the array holds less number of elements

View Answer

Answer: d

Explanation: Dynamic arrays are preferred when the size

of the array is unknown during memory allocation or the
size changes after few iterations or the memory
reallocation is expensive. If array holds less number of
elements, the physical size is reduced and reduction takes
more time. In that case, we can use normal arrays instead
of dynamic arrays.
13. The growth factor of ArrayList in Java is ___

a) 1

b) 1.5

c) 2

d) 0

View Answer

Answer: b

Explanation: The growth factor of dynamic arrays (Array

List) in Java is 3/2.

The new array capacity is calculated as new_array_size =

(old_array_size*3)/2+1.

14. In special case, the time complexity of

inserting/deleting elements at the end of dynamic array is
____

a) O (n)

b) O (n1/2)

c) O (log n)

d) O (1)

View Answer

Answer: a

Explanation: In general, the time complexity of inserting or

deleting elements at the end of dynamic array is O (1).
Elements are added at reserved space of dynamic array. If
this reserved space is exceeded, then the physical size of
the dynamic array is reallocated and every element is
copied from original array. This will take O(n) time to add
new element at the end of the array.

15. Which of the following arrays are used in the

implementation of list data type in python?

a) Bit array

b) Dynamic arrays

c) Sparse arrays

d) Parallel arrays

View Answer

Answer: b

Explanation: Dynamic arrays are used in the

implementation of list data type in python. Sparse arrays
are used in the implementation of sparse matrix in Numpy
module. All bit array operations are implemented in
bitarray module.

[8:04 AM, 12/14/2020] ZaHeeR ShahZaiB: 1. What is an

in-place sorting algorithm?

a) It needs O(1) or O(logn) memory to create auxiliary

locations

b) The input is already sorted and in-place

c) It requires additional storage

d) It requires additional space

View Answer

Answer: a
Explanation: Auxiliary memory is required for storing the
data temporarily.

2. In the following scenarios, when will you use selection

sort?

a) The input is already sorted

b) A large file has to be sorted

c) Large values need to be sorted with small keys

d) Small values need to be sorted with large keys

View Answer

Answer: c

Explanation: Selection is based on keys, hence a file with

large values and small keys can be efficiently sorted with
selection sort.

3. What is the worst case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: Selection sort creates a sub-list, LHS of the

‘min’ element is already sorted and RHS is yet to be
sorted. Starting with the first element the ‘min’ element
moves towards the final element.
4. Select the appropriate code that performs selection
sort.

a)

int min;

for(int j=0; j<arr.length-1; j++)

min = j;

for(int k=j+1; k<=arr.length-1; k++)

if(arr[k] < arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];

arr[j] = temp;

b)

int min;

for(int j=0; j<arr.length-1; j++)

min = j;

for(int k=j+1; k<=arr.length; k++)

{
if(arr[k] < arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];

arr[j] = temp;

c)

int min;

for(int j=0; j<arr.length-1; j++)

min = j;

for(int k=j+1; k<=arr.length-1; k++)

if(arr[k] > arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];

arr[j] = temp;

d)
int min;

for(int j=0; j<arr.length-1; j++)

min = j;

for(int k=j+1; k<=arr.length; k++)

if(arr[k] > arr[min])

min = k;

int temp = arr[min];

arr[min] = arr[j];

arr[j] = temp;

View Answer

Answer: a

Explanation: Starting with the first element as ‘min’

element, selection sort loops through the list to select the
least element which is then swapped with the ‘min’
element.

5. What is the advantage of selection sort over other

sorting techniques?

a) It requires no additional storage space

b) It is scalable

c) It works best for inputs which are already sorted

d) It is faster than any other sorting technique

View Answer

Answer: a

Explanation: Since selection sort is an in-place sorting

algorithm, it does not require additional storage.

6. What is the average case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: In the average case, even if the input is

partially sorted, selection sort behaves as if the entire
array is not sorted. Selection sort is insensitive to input.

7. What is the disadvantage of selection sort?

a) It requires auxiliary memory

b) It is not scalable

c) It can be used for small keys

d) It takes linear time to sort the elements

View Answer

Answer: b
Explanation: As the input size increases, the performance
of selection sort decreases.

8. The given array is arr = {3,4,5,2,1}. The number of

iterations in bubble sort and selection sort respectively
are,

a) 5 and 4

b) 4 and 5

c) 2 and 4

d) 2 and 5

View Answer

Answer: a

Explanation: Since the input array is not sorted, bubble

sort takes 5 iterations and selection sort takes 4(n-1)
iterations.

9. The given array is arr = {1,2,3,4,5}. (bubble sort is

implemented with a flag variable)The number of iterations
in selection sort and bubble sort respectively are,

a) 5 and 4

b) 1 and 4

c) 0 and 4

d) 4 and 1

View Answer

Answer: d
Explanation: Selection sort is insensitive to input, hence
4(n-1) iterations. Whereas bubble sort iterates only once
to set the flag to 0 as the input is already sorted.

10. What is the best case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n2)

View Answer

Answer: d

Explanation: The best, average and worst case

complexities of selection sort is O(n2).

(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.

[8:05 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Bucket Sort (Uniform Keys)”.

1. How many comparisons will be made to sort the array

arr={1, 5, 3, 8, 2} using bucket sort?

a) 5

b) 7

c) 9

d) 0

View Answer
Answer: d

Explanation: As bucket sort is an example of a

non-comparison sort so it is able to sort an array without
making any comparison. So the answer should be 0.

2. What is the alternate name of bucket sort?

a) group sort

b) radix sort

c) bin sort

d) uniform sort

View Answer

Answer: c

Explanation: Bucket sort is also known as bin sort. It is an

example of a non-comparison sort.

3. Which of the following non-comparison sort can also be

considered as a comparison based sort?

a) counting sort

b) MSD radix sot

c) bucket sort

d) pigeonhole sort

View Answer

Answer: c

Explanation: Bucket sort can also be considered as a

comparison based sort. It is because it can also be
implemented with comparisons.
4. Which of the following is not true about bucket sort?

a) It is a non comparison based integer sort

b) It is a distribution sort

c) It can also be considered as comparison based sort

d) It is in place sorting algorithm

View Answer

Answer: d

Explanation: Bucket sort is a non comparison based

integer sort. It sorts the given data by distributing the
array elements into a number of buckets. It is not an in
place sorting technique.

5. Which of the following don’t affect the time complexity

of bucket sort?

a) algorithm implemented for sorting individual buckets

b) number of buckets used

c) distribution of input

d) input values

View Answer

Answer: d

Explanation: Time complexity of bucket sort is affected by

various factors. These include algorithm implemented for
sorting individual buckets, number of buckets used and
distribution of input. It doesnot depend on the input value.
It can be either positive or negative or zero.

6. Bucket sort is most efficient in the case when ____

a) the input is non uniformly distributed

b) the input is uniformly distributed

c) the input is randomly distributed

d) the input range is large

View Answer

Answer: b

Explanation: Bucket sort works by distributing the array

elements into a number of buckets. So bucket sort is most
efficient in the case when the input is uniformly
distributed.

7. Bucket sort is a generalization of which of the following

sort?

a) LSD radix sort

b) Pigeonhole sort

c) Counting sort

d) MSD radix sort

View Answer

Answer: b

Explanation: Pigeonhole sort is a particular case of bucket

sort. Bucket sort is also closely related to MSD radix sort.

8. What is the worst case time complexity of bucket sort (k

= number of buckets)?

a) O(n + k)

b) O(n.k)
c) O(n2)

d) O(n log n)

View Answer

Answer: c

Explanation: Time complexity of bucket sort is O(n2) in the

worst case. So if bucket sort does not get the inputs in the
desired manner then it becomes very inefficient.

9. What is the best time complexity of bucket sort (k=

number of buckets)?

a) O(n + k)

b) O(n.k)

c) O(n2)

d) O(n log n)

View Answer

Answer: a

Explanation: Time complexity of bucket sort is O(n+k). It

performs better than any comparison based sort if there is
a uniform input distribution.

10. Which of the following is not necessarily a stable

sorting algorithm?

a) bucket sort

b) counting sort

c) merge sort

d) pigeonhole sort
View Answer

Answer: a

Explanation: Bucket sort is not necessarily a stable sorting

algorithm. This is because its stability depends on the
stability of the algorithm that we have used to sort the
individual buckets.

11. Bucket sort is an in place sorting algorithm.

a) True

b) False

View Answer

Answer: b

Explanation: Bucket sort is not an in place sorting

algorithm. It requires an auxiliary space of O(n k) in the
worst case.

12. What is the worst space complexity of bucket sort (k =

number of buckets)?

a) O(n + k)

b) O(n.k)

c) O(n2)

d) O(n log n)

View Answer

Answer: b

Explanation: Worst case space complexity of bucket sort is

O(n.k). So it is not an in place sorting algorithm
[8:07 AM, 12/14/2020] ZaHeeR ShahZaiB: 1. On which
algorithm is heap sort based on?

a) Fibonacci heap

b) Binary tree

c) Priority queue

d) FIFO

View Answer

Answer: c

Explanation: Heap sort is based on the algorithm of

priority queue and it gives the best sorting time.

2. In what time can a binary heap be built?

a) O(N)

b) O(N log N)

c) O(log N)

d) O(N2)

View Answer

Answer: a

Explanation: The basic strategy is to build a binary heap of

N elements which takes O(N) time.

3. Heap sort is faster than Shell sort.

a) true

b) false

View Answer
Answer: b

Explanation: Heap sort is slower than Shell sort because

Shell sort uses Sedgewick’s increment sequence.

4. Consider the following heap after buildheap phase.

What will be its corresponding array?

heapsort-questions-answers-q4

a) 26,53,41,97,58,59,31

b) 26,31,41,53,58,59,97

c) 26,41,53,97,31,58,59

d) 97,53,59,26,41,58,31

View Answer

Answer: d

Explanation: Constructing a max heap using the elements

97,53,59,26,41,58,31 will cause the heap to look like that.

5. In what position does the array for heap sort contains

data?

a) 0

b) 1

c) -1

d) anywhere in the array

View Answer

Answer: a
Explanation: The array for heap sort contains data at
position 0 whereas for a binary heap, array begins at 1.
This is the reason for its complexity.

6. In heap sort, after deleting the last minimum element,

the array will contain elements in?

a) increasing sorting order

b) decreasing sorting order

c) tree inorder

d) tree preorder

View Answer

Answer: b

Explanation: By logic, after deleting minimum element,

the heap will contain elements in decreasing sorting order.
We can change this by altering the ordering property.

7. What is the typical running time of a heap sort

algorithm?

a) O(N)

b) O(N log N)

c) O(log N)

d) O(N2)

View Answer

Answer: b

Explanation: The total running time of a heap sort

algorithm is mathematically found to be O(N log N).
8. How many arrays are required to perform deletion
operation in a heap?

a) 1

b) 2

c) 3

d) 4

View Answer

Answer: b

Explanation: To perform deletion operation in a heap, we

require 2 arrays and that occupies extra memory space
and hence increase in running time.

9. What is the time taken to perform a delete min

operation?

a) O(N)

b) O(N log N)

c) O(log N)

d) O(N2)

View Answer

Answer: c

Explanation: The time taken to perform a deletion of a

minimum element is mathematically found to be O( log N).

10. Heap sort is an extremely stable algorithm.

a) true

b) false
View Answer

Answer: a

Explanation: Heap sort uses fewer comparisons than other

sorting algorithms and hence it is an extremely stable
algorithm.

11. What is the average number of comparisons used in a

heap sort algorithm?

a) N log N-O(N)

b) O(N log N)-O(N)

c) O(N log N)-1

d) 2N log N + O(N)

View Answer

Answer: d

Explanation: The average number of comparisons in a

heapsort algorithm is mathematically found to be 2N log N
+ O(N).

12. What is the time taken to copy elements to and from

two arrays created for deletion?

a) O(N)

b) O(N log N)

c) O(log N)

d) O(N2)

View Answer
Answer: a

Explanation: The time taken to copy elements to and from

the main array and extra array is found to be O(N).

13. What is the average number of comparisons used to

heap sort a random permutation of N distinct items?

a) 2N log N-O(N)

b) 2N log N-O(N log N)

c) 2N log N-O(N log log N)

d) 2N log N-O(log N)

View Answer

Answer: c

Explanation: According to a theorem, the average number

of comparisons used to heap sort a random permutation
of N distinct items is found to be 2N log N-O(N log log N)

[8:08 AM, 12/14/2020] ZaHeeR ShahZaiB: This set of Data

Structures & Algorithms Multiple Choice Questions &
Answers (MCQs) focuses on “Heapsort – 2”.

1. Heap sort is an implementation of ____ using a

descending priority queue.

a) insertion sort

b) selection sort

c) bubble sort

d) merge sort

View Answer
Answer: b

Explanation: Heap sort is an implementation of selection

sort using the input array as a heap representing a
descending priority queue. Heap sort algorithm is divided
into two phase. In first phase the max-heap is created and
the second phase (selection phase) deletes the elements
from the priority queue using siftdown operation.

2. Which one of the following is false?

a) Heap sort is an in-place algorithm

b) Heap sort has O(nlogn) average case time complexity

c) Heap sort is stable sort

d) Heap sort is a comparison-based sorting algorithm

View Answer

Answer: c

Explanation: Heap sort is a comparison based sorting

algorithm and has time complexity O(nlogn) in the
average case. Heap sort is an in-place algorithm as it
needs O(1) of auxiliary space. Heap sort uses heap and
operations on heap can change the relative order of items
with the same key values. Therefore, Heap sort is not a
stable sort.

3. The essential part of Heap sort is construction of

max-heap. Consider the tree shown below, the node 24
violates the max-heap property. Once heapify procedure is
applied to it, which position will it be in?

data-structures-questions-answers-heapsort-q3

a) 4

b) 5
c) 8

d) 9

View Answer

Answer: d

Explanation: In max-heap element at each node is smaller

than or equal to the element at its parent node. On
applying the heapify procedure on item at position 2, it
will be in position 9 as shown below.

data-structures-questions-answers-heapsort-q3-exp

4. The descending heap property is _____

a) A[Parent(i)] = A[i]

b) A[Parent(i)] <= A[i]

c) A[Parent(i)] >= A[i]

d) A[Parent(i)] > 2 * A[i]

View Answer

Answer: c

Explanation: The max-heap is also known as descending

heap. Max-heap of size n is an almost complete binary
tree of n nodes such that the element at each node is less
than or equal to the element at its parent node.

5. What is its wort case time complexity of Heap sort?

a) O(nlogn)

b) O(n2logn)

c) O(n2)
d) O(n3)

View Answer

Answer: a

Explanation: In Heap sort, the call to procedure

build_Max-heap takes O(n) time and each of O(n) calls to
the function max_Heapify takes O(logn) time. So the worst
case complexity of Heap sort is O(nlogn).

6. In average case Heap sort is as efficient as the Quick

sort.

a) True

b) False

View Answer

Answer: b

Explanation: Quick sort is more efficient than Heap sort

because experiments indicate that Heap sort requires
twice as much time as Quick sort for randomly sorted
input.

7. Choose the correct option to fill? X so that the code

given below implements the Heap sort.

#include <stdio.h>

void heapify(int arr[], int n, int i)

int largest = i; // Initialize largest as root

int l = 2*i + 1; // left = 2*i + 1

int r = 2*i + 2; // right = 2*i + 2

if (l < n && arr[l] > arr[largest])

largest = l;

if (r < n && arr[r] > arr[largest])

largest = r;

if (largest != i)

swap(arr[i], arr[largest]);

heapify(arr, n, largest);

void heapSort(int arr[], int n)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i=n-1; i>=0; i--)

X;

heapify(arr, i, 0);

void printArray(int arr[], int n)

for (int i=0; i<n; ++i)

printf(“%d”,arr[i]);

printf(“\n”);

int main()

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof(arr)/sizeof(arr[0]);

heapSort(arr, n);

printf(“Sorted array is \n");

printArray(arr, n);

a) swap(arr[0], arr[n])

b) swap(arr[i], arr[n])

c) swap(arr[0], arr[i])

d) swap(arr[i], arr[2*i])

View Answer

Answer: c

Explanation: Steps in heap sort are : (i) Build the

max-heap, (ii) Swap the root element with the last
element of the heap, (iii) Reduce the size of heap by 1 and
heapify the root element, (iv) Repeat the steps form step
number (v) until all the elements are sorted. Therefore the
correct option is swap(arr[0], arr[i]).

8. Which one of the following is a variation of Heap sort?

a) Comb sort
b) Smooth sort

c) Binary tree sort

d) Shell sort

View Answer

Answer: b

Explanation: Smooth sort is a variation of Heap sort.

Smooth sort has O(nlogn) worst case time complexity like
Heap sort. But Smooth sort takes O(n) time to sort the
nearly sorted input array.

9. Introsort algorithm is combination of _____

a) Quick sort and Heap sort

b) Quick sort and Shell sort

c) Heap sort and Merge sort

d) Heap sort and insertion sort

View Answer

Answer: a

Explanation: Introsort is a hybrid sorting algorithm that

combines Quick sort and Heap sort to retain advantages of
both. It has worst case speed of Heap sort and average
case speed of Quick sort.

10. How many elements can be sorted in O(logn) time

using Heap sort?

a) O(1)

b) O(n/2)

c) O(logn/log(logn))
d) O(logn)

View Answer

Answer: c

Explanation: The time complexity of Heap sort is O(klogk)

for k input elements,

for k = logn/log(logn),

O(klogk) = O(logn/log(logn) * log(logn/log(logn)))

∴ O(klogk) = O(logn/log(logn) * (log(logn) – log(log(logn))))

= O(logn)

Hence the correct option is O(logn/log(logn))