NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
DATA STRUCTURES AND ALGORITHMS USING JAVA
Assignment 7
TYPE OF QUESTION: MCQ
Number of questions: 10 Total marks: 10×1 = 10
______________________________________________________________________________
QUESTION 1:
Which of the following terminologie(s) is(are) not related to tree?
a. Node
b. Top
c. Level
d. Link
Correct Answer: b
Detailed Solution:
Basic Tree terminologies are node, link, level, parent, child, root, leaf, height, degree, sibling. Top is a basic
terminology of Stack data structure which is a linear data structure.
______________________________________________________________________________
QUESTION 2:
Which of the following is a common issue with an unbalanced Binary Search Tree (BST)?
a. It can have duplicate keys
b. It may not maintain the binary property
c. It can degrade to a linked list, increasing time complexity
d. It requires extra space for parent pointers
Correct Answer: c
Detailed Solution:
If a BST becomes unbalanced (e.g., inserting sorted data), it can degenerate into a structure resembling a
linked list. This causes operations like insertion, deletion, and search to degrade from O(log n) to O(n)
time, defeating the purpose of using a BST for efficient lookup.
______________________________________________________________________________
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
QUESTION 3:
What is the balance factor of a node in an AVL Tree?
a. The number of children the node has
b. The height of the left subtree minus the height of the right subtree
c. The depth of the node from the root
d. The maximum number of nodes in both subtrees
Correct Answer: b
Detailed Solution:
In an AVL tree, the balance factor of a node is calculated as:
Balance Factor = Height(left subtree) – Height(right subtree)
For the tree to remain balanced, this value must be -1, 0, or 1 at every node. A value outside this range
triggers rebalancing through rotations.
______________________________________________________________________________
QUESTION 4:
Which rotation is performed in an AVL tree when a node is inserted into the right subtree of the
left child of an unbalanced node?
a. Left Rotation
b. Right Rotation
c. Left-Right Rotation
d. Right-Left Rotation
Correct Answer: c
Detailed Solution:
This situation creates a Left-Right (LR) imbalance. To rebalance, a double rotation is needed: first a left
rotation on the left child, followed by a right rotation on the unbalanced node. This restores the AVL
property while preserving the binary search tree ordering.
______________________________________________________________________________
QUESTION 5:
What is the worst-case time complexity of searching an element in a Binary Search Tree (BST)?
a. O(1) in both balanced and unbalanced BSTs
b. O(log n) in balanced BST, O(n) in unbalanced BST
c. O(n) in both balanced and unbalanced BSTs
d. O(log n) in both balanced and unbalanced BSTs
Correct Answer: b
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
Detailed Solution:
In a balanced BST (like an AVL or Red-Black Tree), the height of the tree is logarithmic relative to the
number of nodes, so search takes O(log n) time. In an unbalanced BST, the tree may degrade into a linear
chain (like a linked list), making search take O(n) time in the worst case.
______________________________________________________________________________
QUESTION 6:
What is the maximum height of an AVL tree with 1000 nodes (rounded to the nearest integer)?
a. 10
b. 14
c. 20
d. 30
Correct Answer: b
Detailed Solution:
The maximum height of an AVL tree with 1000 nodes is approximately 14, using the formula in slide 34.
So the correct answer is B.
______________________________________________________________________________
QUESTION 7:
Which of the following is true about a binary max-heap?
a. The smallest element is always at the root
b. It is always a balanced binary search tree
c. The largest element is always at the root
d. Insertion requires O(log n²) time
Correct Answer: c
Detailed Solution:
In a binary max-heap, the largest element is always stored at the root. The heap is a complete binary tree,
but not necessarily balanced or a binary search tree. Insertions and deletions (heapify operations) take
O(log n) time due to the height of the tree.
______________________________________________________________________________
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
QUESTION 8:
Consider the following code.
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(20);
System.out.print(pq.poll() + " ");
System.out.print(pq.peek());
}
}
What will be the output of the above program?
a. 30 20
b. 10 20
c. 10 30
d. 20 10
Correct Answer: b
Detailed Solution:
Java's PriorityQueue is a min-heap by default. The add() method inserts elements, and poll() removes and
returns the smallest element (10). The next smallest (20) remains at the top, so peek() returns 20. Output:
10 20.
______________________________________________________________________________
QUESTION 9:
What is the worst-case time complexity of deleting the maximum element from a min-heap
with n elements?
a. O(1)
b. O(log n)
c. O(n)
d. O(n log n)
Correct Answer: c
NPTEL Online Certification Courses
Indian Institute of Technology Kharagpur
Detailed Solution:
In a min-heap, the minimum element is at the root and can be deleted in O(log n). However, the
maximum element is not in a fixed location — it could be in any leaf node. In the worst case, you
must scan all leaf nodes (approximately n/2 of them) to find the maximum, resulting in O(n) time
for deletion.
______________________________________________________________________________
QUESTION 10:
Which of the following is a typical application of a heap data structure?
a. Balancing a binary search tree
b. Implementing recursion
c. Finding shortest paths in unweighted graphs
d. Scheduling tasks by priority
Correct Answer: d
Detailed Solution:
Heap trees, especially priority queues, are widely used in task scheduling where each task has a priority.
______________________________________________________________________________
************END************
