Category: Data Structure Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Evaluation of a Prefix Expression”.

1. How many stacks are required for evaluation of prefix expression?
a) one
b) two
c) three
d) four

Answer: b
Clarification: 2 stacks are required for evaluation of prefix expression, one for integers and one for characters.

2. While evaluating a prefix expression, the string is read from?
a) left to right
b) right to left
c) center to right
d) center to left to right

Answer: b
Clarification: The string is read from right to left because a prefix string has operands to its right side.

3. The associativity of an exponentiation operator ^ is right side.
a) True
b) False

Answer: a
Clarification: The associativity of ^ is right side while the rest of the operators like +,-,*,/ has its associativity to its left.

4. How many types of input characters are accepted by this algorithm?
a) one
b) two
c) three
d) four

Answer: c
Clarification: Three kinds of input are accepted by this algorithm- numbers, operators and new line characters.

5. What determines the order of evaluation of a prefix expression?
a) precedence and associativity
b) precedence only
c) associativity only
d) depends on the parser

Answer: a
Clarification: Precedence is a very important factor in determining the order of evaluation. If two operators have the same precedence, associativity comes into action.

6. Find the output of the following prefix expression.

*+2-2 1/-4 2+-5 3 1

a) 2
b) 12
c) 10
d) 4

Answer: a
Clarification: The given prefix expression is evaluated using two stacks and the value is given by (2+2-1)*(4-2)/(5-3+1)= 2.

7. An error is thrown if the character ‘n’ is pushed in to the character stack.
a) true
b) false

Answer: b
Clarification: The input character ‘n’ is accepted as a character by the evaluation of prefix expression algorithm.

8. Using the evaluation of prefix algorithm, evaluate +-9 2 7.
a) 10
b) 4
c) 17
d) 14

Answer: d
Clarification: Using the evaluation of prefix algorithm, +-9 2 7 is evaluated as 9-2+7=14.

9. If -*+abcd = 11, find a, b, c, d using evaluation of prefix algorithm.
a) a=2, b=3, c=5, d=4
b) a=1, b=2, c=5, d=4
c) a=5, b=4, c=7,d=5
d) a=1, b=2, c=3, d=4

Answer: b
Clarification: The given prefix expression is evaluated as ((1+2)*5)-4 = 11 while a=1, b=2, c=5, d=4.

10. In the given C snippet, find the statement number that has error.

//C code to push an element into a stack
1. void push( struct stack *s, int x) 
2. {
3.     if(s->top==MAX-1)
4.     {
5.         printf(“stack overflow”);
6.     }
7.     else
8.     {
9.         s->items[++s->top]=x;
10.        s++;
11.    }   
12. }

a) 1
b) 9
c) 10
d) 11

Answer: c
Clarification: If the stack is not full then we are correctly incrementing the top of the stack by doing “++s->top” and storing the value of x in it. However, in the next statement “s++”, we are un-necessarily incrementing the stack base pointer which will lead to memory corruption during the next push() operation.

Data Structures & Algorithms Multiple Choice Questions on “Count Inversion”.

1. What does the number of inversions in an array indicate?
a) mean value of the elements of array
b) measure of how close or far the array is from being sorted
c) the distribution of values in the array
d) median value of the elements of array

Answer: b
Clarification: The number of inversions in an array indicates how close or far the array is from being completely sorted. The array is sorted if the number of inversions are 0.

2. How many inversions does a sorted array have?
a) 0
b) 1
c) 2
d) cannot be determined

Answer: a
Clarification: When an array is sorted then there cannot be any inversion in the array. As the necessary condition for an inversion is arr[i]>arr[j] and i<j.

3. What is the condition for two elements arr[i] and arr[j] to form an inversion?
a) arr[i]<arr[j]
b) i < j
c) arr[i] < arr[j] and i < j
d) arr[i] > arr[j] and i < j

Answer: d
Clarification: For two elements to form an inversion the necessary condition is arr[i] > arr[j] and i < j. The number of inversions in an array indicate how close or far the array is from being completely sorted.

4. Under what condition the number of inversions in an array are maximum?
a) when the array is sorted
b) when the array is reverse sorted
c) when the array is half sorted
d) depends on the given array

Answer: b
Clarification: Number of inversions in an array are maximum when the given array is reverse sorted. As the necessary condition for an inversion is arr[i]>arr[j] and i<j.

5. Under what condition the number of inversions in an array are minimum?
a) when the array is sorted
b) when the array is reverse sorted
c) when the array is half sorted
d) depends on the given array

Answer: a
Clarification: Number of inversions in an array are minimum when the given array is sorted. As the necessary condition for an inversion is arr[i]>arr[j] and i<j.

6. How many inversions are there in the array arr = {1,5,4,2,3}?
a) 0
b) 3
c) 4
d) 5

Answer: d
Clarification: The necessary condition for an inversion is arr[i]>arr[j] and i

7. Which of the following form inversion in the array arr = {1,5,4,2}?
a) (5,4), (5,2)
b) (5,4), (5,2), (4,2)
c) (1,5), (1,4), (1,2)
d) (1,5)

Answer: b
Clarification: The necessary condition for an inversion is arr[i]>arr[j] and i

8. Choose the correct function from the following which determines the number of inversions in an array?
a)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i ; j < n; j++) 
			if (arr[i] >= arr[j]) 
				count++; 
 
	return count; 
}

b)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count; 
}

c)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count + 1; 
}

d)

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] < arr[j]) 
				count++; 
 
	return count + 1; 
}

View Answer

Answer: b
Clarification: To determine the number of inversions we apply a nested loop and compare the value of each element with all the elements present after it. Then the count of number of inversions is counted and returned to the main function.

9. What is the time complexity of the following code that determines the number of inversions in an array?

int InvCount(int arr[], int n) 
{ 
	int count = 0; 
	for (int i = 0; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (arr[i] > arr[j]) 
				count++; 
 
	return count; 
}

a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: The time complexity of the given code is O(n2). It is due to the presence of nested loop.

10. The time complexity of the code that determines the number of inversions in an array using merge sort is lesser than that of the code that uses loops for the same purpose.
a) true
b) false

Answer: a
Clarification: The time complexity of the code that determines the number of inversions in an array using merge sort is O(n log n) which is lesser than the time complexity taken by the code that uses loops.

11. What is the time complexity of the code that uses merge sort for determining the number of inversions in an array?
a) O(n²)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: d
Clarification: The code of merge sort is slightly modified in order to calculate the number of inversions in an array. So the time complexity of merge sort remains unaffected and hence the time complexity is O(n log n).

12. What is the time complexity of the code that uses self balancing BST for determining the number of inversions in an array?
a) O(n²)
b) O(n)
c) O(log n)
d) O(n log n)

Answer: d
Clarification: When a self balancing BST like an AVL tree is used to calculate the number of inversions in an array then the time complexity is O(n log n) as AVL insert takes O(log n) time.

13. The time complexity of the code that determines the number of inversions in an array using self balancing BST is lesser than that of the code that uses loops for the same purpose.
a) true
b) false

Answer: a
Clarification: The time complexity of the code that determines the number of inversions in an array using self balancing BST is O(n log n) which is lesser than the time complexity taken by the code that uses loops.

14. What is the space complexity of the code that uses merge sort for determining the number of inversions in an array?
a) O(n)
b) O(log n)
c) O(1)
d) O(n log n)

Answer: a
Clarification: The space complexity required by the code will be O(n). It is the same as the space complexity of the code of standard merge sort.

Data Structures & Algorithms Multiple Choice Questions on “2-3 Tree”.

1. 2-3 tree is a specific form of _________
a) B – tree
b) B+ – tree
c) AVL tree
d) Heap

Answer: a
Clarification: The 2-3 trees is a balanced tree. It is a specific form the B – tree. It is B – tree of order 3, where every node can have two child subtrees and one key or 3 child subtrees and two keys.

2. AVL trees provide better insertion the 2-3 trees.
a) True
b) False

Answer: b
Clarification: Insertion in AVL tree and 2-3 tree requires searching for proper position for insertion and transformations for balancing the tree. In both, the trees searching takes O(log n) time, but rebalancing in AVL tree takes O(log n), while the 2-3 tree takes O(1). So, 2-3 tree provides better insertions.

3. Which of the following is false?
a) 2-3 tree requires less storage than the BST
b) lookup in 2-3 tree is more efficient than in BST
c) 2-3 tree is shallower than BST
d) 2-3 tree is a balanced tree

Answer: a
Clarification: Search is more efficient in the 2-3 tree than in BST. 2-3 tree is a balanced tree and performs efficient insertion and deletion and it is shallower than BST. But, 2-3 tree requires more storage than the BST.

4. The height of 2-3 tree with n elements is ______
a) between (n/2) and (n/3)
b) (n/6)
c) between (n) and log2(n + 1)
d) between log3(n + 1) and log2(n + 1)

Answer: d
Clarification: The number of elements in a 2-3 tree with height h is between 2h – 1 and 3h – 1. Therefore, the 2-3 tree with n elements will have the height between log3(n + 1) and log2(n + 1).

5. Which of the following the BST is isometric with the 2-3 tree?
a) Splay tree
b) AA tree
c) Heap
d) Red – Black tree

Answer: b
Clarification: AA tree is isometric of the 2-3 trees. In an AA tree, we store each node a level, which is the height of the corresponding 2-3 tree node. So, we can convert a 2-3 tree to an AA tree.

6. Which of the following data structure can provide efficient searching of the elements?
a) unordered lists
b) binary search tree
c) treap
d) 2-3 tree

Answer: d
Clarification: The average case time for lookup in a binary search tree, treap and 2-3 tree is O(log n) and in unordered lists it is O(n). But in the worst case, only the 2-3 trees perform lookup efficiently as it takes O(log n), while others take O(n).

7. LLRB maintains 1-1 correspondence with 2–3 trees.
a) True
b) False

8. Which of the following is not true about the 2-3 tree?
a) all leaves are at the same level
b) it is perfectly balanced
c) postorder traversal yields elements in sorted order
d) it is B-tree of order 3

Answer: c
Clarification: In a 2-3 tree, leaves are at the same level. And 2-3 trees are perfectly balanced as every path from root node to the null link is of equal length. In 2-3 tree in-order traversal yields elements in sorted order.5