Trees and Graphs - trees, forests, binary trees, threaded binary trees, binary search trees, AVL trees, B-tree variants, graphs - Question Bank

1. In the context of graph theory, what does 'connectedness' refer to?
A) The presence of cycles.
B) The existence of a path between any two vertices in the graph.
C) The number of edges in the graph.
D) Whether the graph is directed or undirected.
2. Which of the following is NOT a type of tree discussed in the context of data structures?
A) Binary Tree
B) AVL Tree
C) B-Tree
D) Decision Tree
3. What is the time complexity of BFS and DFS on a graph represented by an adjacency matrix, where V is the number of vertices?
A) O(V + E)
B) O(V * E)
C) O(V^2)
D) O(E log V)
4. 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?
A) O(V + E)
B) O(V * E)
C) O(V^2)
D) O(E log V)
5. Topological sorting is only possible on which type of graph?
A) Undirected graphs
B) Directed Acyclic Graphs (DAGs)
C) Complete graphs
D) Weighted graphs
6. What is the primary purpose of a 'topological sort'?
A) To find the shortest path in a graph.
B) 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.
C) To find the minimum spanning tree.
D) To determine if a graph is connected.
7. 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?
A) It must be an undirected graph.
B) It must contain only non-negative edge weights.
C) It must be a complete graph.
D) It must be acyclic.
8. What is a 'weighted graph'?
A) A graph where every vertex has a weight.
B) A graph where edges have associated costs or weights.
C) A graph that is guaranteed to be connected.
D) A graph with no cycles.
9. What is the primary application of DFS?
A) Finding the shortest path in an unweighted graph.
B) Finding connected components and detecting cycles.
C) Minimizing network flow.
D) Calculating the diameter of a graph.
10. What is the primary application of BFS?
A) Finding the shortest path in a weighted graph.
B) Finding the shortest path in an unweighted graph.
C) Topological sorting.
D) Detecting cycles in a directed graph.
11. Which graph traversal algorithm typically uses a stack (either explicitly or implicitly via recursion)?
A) Depth-First Search (DFS)
B) Breadth-First Search (BFS)
C) Kruskal's Algorithm
D) Bellman-Ford Algorithm
12. Which graph traversal algorithm uses a queue data structure?
A) Depth-First Search (DFS)
B) Breadth-First Search (BFS)
C) Dijkstra's Algorithm
D) Prim's Algorithm
13. What is a 'spanning tree' of a connected, undirected graph?
A) A tree that includes all vertices and a subset of edges, forming a cycle.
B) A tree that includes all vertices and a subset of edges, forming a connected acyclic subgraph.
C) A tree that includes only the leaf nodes of the graph.
D) A tree containing the maximum number of edges possible.
14. A graph with no cycles is called a:
A) Complete graph
B) Connected graph
C) Acyclic graph
D) Dense graph
15. What is a 'cycle' in a graph?
A) A path that visits every vertex exactly once.
B) A path that starts and ends at the same vertex, traversing at least one edge.
C) A path between two specific vertices.
D) A sequence of vertices with no edges.
16. In a directed graph, what is the 'in-degree' of a vertex?
A) The number of edges originating from the vertex.
B) The number of edges pointing towards the vertex.
C) The total number of edges connected to the vertex.
D) The number of paths leading to the vertex.
17. What is the 'degree' of a vertex in an undirected graph?
A) The number of edges connected to the vertex.
B) The number of vertices in the graph.
C) The number of paths from the vertex to the root.
D) The weight of the vertex.
18. What distinguishes a directed graph from an undirected graph?
A) Directed graphs have weighted edges.
B) Edges in a directed graph have a specific direction.
C) Undirected graphs have cycles.
D) Directed graphs cannot have cycles.
19. In an undirected graph, if there is an edge from vertex A to vertex B, is there also an edge from B to A?
A) Only if the graph is complete.
B) Yes, the relationship is symmetric.
C) No, it depends on the graph's properties.
D) Only if the graph is connected.
20. What is a 'vertex' in a graph?
A) A connection between two nodes.
B) A node or point in the graph.
C) The weight of an edge.
D) The degree of a node.
21. What does an 'edge' represent in a graph?
A) A node in the graph.
B) A relationship or connection between two vertices.
C) The value stored in a vertex.
D) The path length between two vertices.
22. What is a graph in data structures?
A) A linear collection of nodes.
B) A non-linear data structure consisting of vertices (nodes) and edges (connections between vertices).
C) A tree where every node has exactly two children.
D) A collection of disjoint trees.
23. What is a key advantage of B+ trees over B-trees for range queries?
A) Range queries are not supported by B+ trees.
B) All data is present in leaf nodes linked sequentially, making range scans efficient.
C) Internal nodes store the actual data, speeding up retrieval.
D) B+ trees have a shallower depth.
24. In a B+ tree, where are all the data records typically stored?
A) In all nodes of the tree.
B) Only in the leaf nodes.
C) Only in the internal nodes.
D) In a separate hash table.
25. What is the primary goal of B-tree variants like B+ trees?
A) To reduce the height of the tree further for faster disk I/O.
B) To implement operations more efficiently in RAM.
C) To allow for more complex key structures.
D) To guarantee a perfectly balanced tree at all times.
26. In a B-tree of order 'm', what is the maximum number of children a node can have?
A) m - 1
B) m
C) 2m
D) ceil(m/2)
27. In a B-tree of order 'm', what is the minimum number of keys a non-root node can have?
A) 1
B) m/2 - 1
C) ceil(m/2) - 1
D) m - 1
28. What is the main characteristic of a B-tree node regarding the number of keys and children?
A) A node can have at most one key and two children.
B) A node can have multiple keys and a variable number of children, within a defined range.
C) A node must have exactly two keys and three children.
D) The number of keys is always equal to the number of children.
29. B-trees are particularly optimized for which type of storage?
A) RAM
B) Cache memory
C) Disk storage (secondary storage)
D) CPU registers
30. What is a B-tree?
A) A self-balancing binary search tree.
B) A tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
C) A tree where each node has at most two children.
D) A tree used primarily for in-memory operations.
31. What are the primary operations used to restore balance in an AVL tree after an insertion or deletion?
A) Insertion and Deletion
B) Rotation operations (single and double)
C) Tree restructuring
D) Heapify
32. When does an imbalance occur in an AVL tree?
A) When a node is inserted or deleted.
B) When the balance factor of any node becomes greater than 1 or less than -1.
C) When the tree becomes too deep.
D) When duplicate keys are added.
33. What is the allowed range for the balance factor of any node in an AVL tree?
A) -2 to 2
B) -1 to 1
C) 0 to 1
D) -1 to 0
34. What is the 'balance factor' in an AVL tree?
A) The number of nodes in the left subtree minus the number of nodes in the right subtree.
B) The height of the left subtree minus the height of the right subtree.
C) The number of children of a node.
D) The difference in keys between the root and its children.
35. What is an AVL tree?
A) A tree where every node has exactly two children.
B) A binary search tree that maintains a balanced structure.
C) A tree used for storing ordered data.
D) A tree with no duplicate keys.
36. What is the worst-case time complexity for search, insertion, and deletion in a standard Binary Search Tree?
A) O(log n)
B) O(n)
C) O(1)
D) O(n log n)
37. What is the primary advantage of using a Binary Search Tree over a simple list for searching?
A) Simpler implementation
B) Faster average search time (O(log n))
C) Guaranteed O(1) search time
D) Lower memory overhead
38. Which operation is typically most efficient in a Binary Search Tree?
A) Finding the minimum element
B) Finding the maximum element
C) Searching for a specific value
D) All of the above
39. What property must a Binary Search Tree (BST) satisfy?
A) The value of the left child is greater than the parent, and the right child is smaller.
B) The value of the left child is smaller than the parent, and the right child is greater.
C) All nodes have exactly two children.
D) It is a balanced tree.
40. In a threaded binary tree, what does a 'right thread' from a node point to?
A) The node's right child
B) The node's parent
C) The node's in-order successor
D) The node's in-order predecessor
41. What is a 'threaded binary tree' designed to improve?
A) Insertion speed
B) Deletion speed
C) Traversal efficiency without using a stack
D) Memory usage
42. What is the maximum number of nodes in a binary tree of height 'h' (where height of root is 0)?
A) 2^(h+1) - 1
B) 2^h - 1
C) h + 1
D) 2h
43. What is a 'forest' in the context of trees?
A) A tree with many nodes.
B) A collection of disjoint trees.
C) A tree where all nodes have two children.
D) A tree used to represent geographical data.
44. Which traversal method visits nodes in the order: Left, Right, Root?
A) In-order traversal
B) Pre-order traversal
C) Post-order traversal
D) Level-order traversal
45. An in-order traversal of a binary tree visits nodes in what order?
A) Root, Left, Right
B) Left, Root, Right
C) Left, Right, Root
D) Root, Right, Left
46. Which traversal method visits nodes in the order: Root, Left, Right?
A) In-order traversal
B) Pre-order traversal
C) Post-order traversal
D) Level-order traversal
47. In a binary tree, what is the term for a node with no children?
A) Root node
B) Internal node
C) Leaf node
D) Parent node
48. What is the defining characteristic of a binary tree?
A) Each node has at most two children.
B) Each node has exactly two children.
C) It has a root node and leaf nodes.
D) It is a linear data structure.
49. Which data structure is a collection of disjoint sets?
A) Tree
B) Graph
C) Forest
D) Heap
50. In a general tree, what is the maximum number of children a node can have?
A) 1
B) 2
C) Varies depending on the tree structure
D) Infinite
All Question Banks
E-Book Trees and Graphs - trees, forests, binary trees, threaded binary trees, binary search trees, AVL trees, B-tree variants, graphs One Line Questions Trees and Graphs - trees, forests, binary trees, threaded binary trees, binary search trees, AVL trees, B-tree variants, graphs Online Test Trees and Graphs - trees, forests, binary trees, threaded binary trees, binary search trees, AVL trees, B-tree variants, graphs