Trees and Graphs - trees, forests, binary trees, threaded binary trees, binary search trees, AVL trees, B-tree variants, graphs - One Line Questions
1.
What is the allowed range for the balance factor of any node in an AVL tree? —
-1 to 1
2.
In a general tree, what is the maximum number of children a node can have? —
Varies depending on the tree structure
3.
In a B-tree of order 'm', what is the minimum number of keys a non-root node can have? —
ceil(m/2) - 1
4.
What is the maximum number of nodes in a binary tree of height 'h' (where height of root is 0)? —
2^(h+1) - 1
5.
What is a 'vertex' in a graph? —
A node or point in the graph.
6.
What is a 'weighted graph'? —
A graph where edges have associated costs or weights.
7.
What is a graph in data structures? —
A non-linear data structure consisting of vertices (nodes) and edges (connections between vertices).
8.
What is the main characteristic of a B-tree node regarding the number of keys and children? —
A node can have multiple keys and a variable number of children, within a defined range.
9.
What does an 'edge' represent in a graph? —
A relationship or connection between two vertices.
10.
What is a 'cycle' in a graph? —
A path that starts and ends at the same vertex, traversing at least one edge.
11.
What is a B-tree? —
A tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
12.
What is a 'spanning tree' of a connected, undirected graph? —
A tree that includes all vertices and a subset of edges, forming a connected acyclic subgraph.
13.
What is an AVL tree? —
A binary search tree that maintains a balanced structure.
14.
What is a 'forest' in the context of trees? —
A collection of disjoint trees.
15.
Which of the following is NOT a type of tree discussed in the context of data structures? —
Decision Tree
16.
A graph with no cycles is called a: —
Acyclic graph
17.
Which graph traversal algorithm uses a queue data structure? —
Breadth-First Search (BFS)
18.
Which graph traversal algorithm typically uses a stack (either explicitly or implicitly via recursion)? —
Depth-First Search (DFS)
19.
What distinguishes a directed graph from an undirected graph? —
Edges in a directed graph have a specific direction.
20.
What is the defining characteristic of a binary tree? —
Each node has at most two children.
21.
Which operation is typically most efficient in a Binary Search Tree? —
All of the above
22.
What is the primary application of BFS? —
Finding the shortest path in an unweighted graph.
23.
What is the primary application of DFS? —
Finding connected components and detecting cycles.
24.
In a B+ tree, where are all the data records typically stored? —
Only in the leaf nodes.
25.
Which traversal method visits nodes in the order: Root, Left, Right? —
Pre-order traversal
26.
Which traversal method visits nodes in the order: Left, Right, Root? —
Post-order traversal
27.
What are the primary operations used to restore balance in an AVL tree after an insertion or deletion? —
Rotation operations (single and double)
28.
What is a 'threaded binary tree' designed to improve? —
Traversal efficiency without using a stack
29.
Dijkstra's algorithm is used to find the shortest path from a single source vertex to all other vertices in a graph. What condition must the graph satisfy? —
It must contain only non-negative edge weights.
30.
In a B-tree of order 'm', what is the maximum number of children a node can have? —
m
31.
What is the worst-case time complexity for search, insertion, and deletion in a standard Binary Search Tree? —
O(n)
32.
What is the time complexity of BFS and DFS on a graph represented by an adjacency list, where V is the number of vertices and E is the number of edges? —
O(V + E)
33.
What is the time complexity of BFS and DFS on a graph represented by an adjacency matrix, where V is the number of vertices? —
O(V^2)
34.
In an undirected graph, if there is an edge from vertex A to vertex B, is there also an edge from B to A? —
Yes, the relationship is symmetric.
35.
B-trees are particularly optimized for which type of storage? —
Disk storage (secondary storage)
36.
What is a key advantage of B+ trees over B-trees for range queries? —
All data is present in leaf nodes linked sequentially, making range scans efficient.
37.
In a binary tree, what is the term for a node with no children? —
Leaf node
38.
An in-order traversal of a binary tree visits nodes in what order? —
Left, Root, Right
39.
What is the primary advantage of using a Binary Search Tree over a simple list for searching? —
40.
In a threaded binary tree, what does a 'right thread' from a node point to? —
The node's in-order successor
41.
What is the 'degree' of a vertex in an undirected graph? —
The number of edges connected to the vertex.
42.
In a directed graph, what is the 'in-degree' of a vertex? —
The number of edges pointing towards the vertex.
43.
What is the 'balance factor' in an AVL tree? —
The height of the left subtree minus the height of the right subtree.
44.
In the context of graph theory, what does 'connectedness' refer to? —
The existence of a path between any two vertices in the graph.
45.
What property must a Binary Search Tree (BST) satisfy? —
The value of the left child is smaller than the parent, and the right child is greater.
46.
What is the primary purpose of a 'topological sort'? —
To find a linear ordering of vertices such that for every directed edge from vertex U to vertex V, U comes before V in the ordering.
47.
What is the primary goal of B-tree variants like B+ trees? —
To reduce the height of the tree further for faster disk I/O.
48.
Which data structure is a collection of disjoint sets? —
Forest
49.
Topological sorting is only possible on which type of graph? —
Directed Acyclic Graphs (DAGs)
50.
When does an imbalance occur in an AVL tree? —
When the balance factor of any node becomes greater than 1 or less than -1.