1
How many children does a binary tree have?
Correct Answer
0 or 1 or 2
☑ MCQ PRACTICE
Data Structures Unit 3
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Data Structures - Unit-3
2
To represent hierarchical relationship between elements, Which data structure is suitable?
Correct Answer
Tree
3
What is/are the disadvantages of implementing tree using normal arrays?
Correct Answer
have to know the maximum number of nodes possible before creation of trees
4
Advantages of linked list representation of binary trees over arrays?
Correct Answer
both dynamic size and ease in insertion/deletion
5
Disadvantages of linked list representation of binary trees over arrays?
Correct Answer
Random access is not possible and extra memory with every element
6
If binary trees are represented in arrays, what formula can be used to locate a left child, if the parent node has an index i?
Correct Answer
2i+1
7
Using what formula can a parent node be located in an array?
Correct Answer
(i-1)/2
8
Which of the following properties are obeyed by all three tree – traversals?
Correct Answer
Left subtrees are visited before right subtrees
9
A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75?
Correct Answer
8, 7, 26, 13, 40, 75, 70, 35
10
In a binary search tree, which of the following traversals would print the numbers in the ascending order?
Correct Answer
In-order traversal
11
The number of edges from the root to the node is called __________ of the tree.
Correct Answer
Depth
12
The number of edges from the node to the deepest leaf is called _________ of the tree.
Correct Answer
Height
13
What is a full binary tree?
Correct Answer
Each node has exactly zero or two children
14
What is a complete binary tree?
Correct Answer
A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right
15
Which of the following is false about a binary search tree?
Correct Answer
In order sequence gives decreasing order of elements
16
What is the main characteristic of a B Tree?
Correct Answer
Each node has a variable number of children within a specified range.
17
In a B Tree, what property does the order 'm' define?
Correct Answer
Maximum number of children a node can have.
18
Which of the following operations can be performed efficiently using a B Tree?
Correct Answer
Insertion, deletion, and search of keys in a database
19
What is a significant advantage of using B Trees in database systems?
Correct Answer
They ensure minimal disk I/O operations.
20
How do B+ Trees differ from B Trees?
Correct Answer
In B+ Trees, all keys are stored in leaf nodes and internal nodes act as routing guides.
21
What is the advantage of B+ Trees over B Trees in terms of range queries?
Correct Answer
Leaf nodes of B+ Trees are linked, providing efficient full-range scans.
22
In a B+ Tree, where are the actual records pointed to by the keys stored?
Correct Answer
Only in leaf nodes
23
Why are B+ Trees preferred in database indexing over B Trees?
Correct Answer
The linked leaf nodes in B+ Trees make sequential access faster.
24
What is the key property of an AVL Tree?
Correct Answer
The difference in height between the left and right subtrees of any node is at most 1.
25
What is the time complexity of insertion in an AVL Tree?
Correct Answer
O(log n)
26
Which of the following operations can cause an AVL Tree to become unbalanced?
Correct Answer
Inserting a node
27
What mechanism is used to maintain the balance of an AVL Tree after insertion or deletion?
Correct Answer
Tree rotations
28
In the context of AVL Trees, what is a rotation?
Correct Answer
Changing the structure of the tree without altering the in-order sequence of elements
29
What is the maximum number of rotations needed to balance an AVL Tree after a single insertion?
Correct Answer
2
30
How does the height of an AVL Tree compare to the height of a perfectly balanced binary tree?
Correct Answer
It can be larger, but no more than log n.
31
Which of the following is true about the deletion operation in an AVL Tree?
Correct Answer
It may require rebalancing through rotations.
32
What is a distinctive feature of a Red-Black Tree?
Correct Answer
Each node is colored either red or black.
33
Which of these properties must a Red-Black Tree satisfy?
Correct Answer
All of the above.
34
What is the time complexity of insertion and deletion operations in a Red-Black Tree?
Correct Answer
O(log n)
35
What action is performed to maintain the Red-Black properties after an insertion or deletion?
Correct Answer
Recoloring nodes and performing rotations
36
In a Red-Black Tree, what does the property "the tree has the same number of black nodes on any path from a node to a descendant leaf" ensure?
Correct Answer
The tree is height-balanced, with the longest path no more than twice the length of the shortest path.
37
Which of the following operations may cause a violation of Red-Black Tree properties?
Correct Answer
Inserting a node
38
What is the maximum height of a Red-Black Tree with 'n' nodes?
Correct Answer
2 log₂(n+1)
39
Why are Red-Black Trees important in computer science?
Correct Answer
They provide a worst-case guarantee for insertion, deletion, and search operations.
40
What is a Splay Tree?
Correct Answer
A tree where recently accessed elements are quick to access again.
41
What is the key operation used in Splay Trees to maintain tree properties?
Correct Answer
Splaying
42
What does the splaying operation in a Splay Tree do?
Correct Answer
Moves a node to the root through a series of rotations.
43
What is the time complexity of search, insert, and delete operations in a Splay Tree in the amortized case?
Correct Answer
O(log n)
44
Which of the following scenarios best demonstrates the advantage of a Splay Tree?
Correct Answer
When certain nodes are accessed frequently and need to be accessed quickly.
45
What property does a Splay Tree use to ensure that recently accessed elements are quick to access again?
Correct Answer
Frequently accessed nodes are moved closer to the root.
46
In a Splay Tree, what happens after an element is accessed (searched, inserted, or delete?
Correct Answer
The accessed element is moved to the root of the tree.
47
Why might Splay Trees not be suitable in an environment with parallel or concurrent operations?
Correct Answer
Because they do not support concurrent modifications well due to the restructuring after operations.