NEW
Font size
WorksheetsExploring Trees and Graphs
Total questions: 45
Worksheet time: 15mins
What is a binary tree?
A binary tree is a data structure that only contains leaf nodes.
A binary tree is a tree data structure where each node has at most two children.
A binary tree is a type of graph where nodes are connected in a circular manner.
A binary tree is a structure with nodes that can have any number of children.
How do you perform an in-order traversal on a binary tree?
In-order traversal visits nodes in the order: left, root, right.
In-order traversal visits nodes in the order: left, right, root.
In-order traversal visits nodes in the order: root, left, right.
In-order traversal visits nodes in the order: right, root, left.
What is the difference between a binary tree and a binary search tree?
A binary tree is a type of graph, while a binary search tree is a linear structure.
A binary tree is always balanced, while a binary search tree can be unbalanced.
A binary tree has no specific ordering, while a binary search tree has a defined order based on node values.
A binary tree allows duplicate values, whereas a binary search tree does not.
What are the characteristics of a balanced binary tree?
A balanced binary tree has nodes with values in ascending order.
A balanced binary tree must have all leaves at the same level.
A balanced binary tree has a height difference of at most one between its left and right subtrees.
A balanced binary tree can have any height difference between subtrees.
Explain the concept of depth-first search (DFS) in graph traversal.
Depth-first search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Depth-first search (DFS) is a graph traversal strategy that randomly selects paths without backtracking.
Depth-first search (DFS) is a technique that only explores the shortest path in a graph.
Breadth-first search (BFS) is a graph traversal method that visits all neighbors before going deeper.
What is breadth-first search (BFS) and how does it differ from DFS?
BFS uses a stack to explore nodes, while DFS uses a queue for traversal.
BFS explores neighbors level by level, while DFS explores as deep as possible along a branch.
BFS visits nodes randomly, while DFS follows a strict order of exploration.
BFS goes deep into a branch first, while DFS checks all neighbors at once.
What is a minimum spanning tree and how is it used?
A minimum spanning tree is a cycle that includes all edges in a graph.
A minimum spanning tree connects all vertices in a graph with the least total edge weight.
A minimum spanning tree connects vertices with the highest total edge weight.
A minimum spanning tree is a subset of edges that forms a complete graph.
Describe the difference between directed and undirected graphs.
Directed graphs have edges with direction; undirected graphs have edges without direction.
Directed graphs have no edges; undirected graphs have edges that connect nodes.
Directed graphs are always weighted; undirected graphs are never weighted.
Directed graphs can be traversed in any order; undirected graphs require a specific path.
What are the common methods for representing graphs in computer science?
Graphs can be represented using arrays and stacks.
Graph representations include binary trees and linked lists.
Common methods for graphs are hash tables and queues.
Common methods for representing graphs include adjacency lists, adjacency matrices, edge lists, and incidence matrices.
What is the purpose of tree balancing techniques?
To maintain efficient operations by keeping the tree balanced.
To simplify the structure of the tree.
To increase the number of nodes in the tree.
To enhance the aesthetic appeal of the tree.
How can you determine if a binary tree is a binary search tree?
A binary tree is a binary search tree if it contains unique values only.
A binary tree is a binary search tree if in-order traversal yields sorted values.
A binary tree is a binary search tree if all nodes have two children.
A binary tree is a binary search tree if it has a balanced structure.
What are the applications of tree data structures in real-world scenarios?
Applications of tree data structures include social media analytics, video streaming, and cloud storage.
Applications of tree data structures include sorting algorithms, search engines, and machine learning.
Applications of tree data structures include image processing, web scraping, and data compression.
Applications of tree data structures include file systems, databases, network routing, compilers, and hierarchical data representation.
Explain the concept of a leaf node in a tree.
A leaf node is a node in a tree that has no children.
A leaf node is a node that connects two branches.
A leaf node is a node that has at least one child.
A leaf node is the root node of a tree.
What is the time complexity of searching for an element in a binary search tree?
O(n), where n is the number of nodes.
O(log n), assuming a balanced tree.
O(1), for constant time access.
O(h), where h is the height of the tree.
How do you convert a binary tree into a doubly linked list?
Use pre-order traversal to connect nodes.
Apply level-order traversal for linking nodes.
Perform in-order traversal and link nodes accordingly.
Perform post-order traversal and join nodes.
What is the significance of the root node in a tree structure?
The root node is the final point of a tree structure, where all nodes converge.
The root node is the starting point of a tree structure, from which all other nodes descend.
The root node is an optional element that can be removed without affecting the tree.
The root node represents the end of the hierarchy in a tree structure.
How can you find the shortest path in a weighted graph?
Use a brute-force search.
Apply the Bellman-Ford method.
Implement a depth-first search.
Use Dijkstra's algorithm.
What is the role of adjacency lists in graph representation?
Adjacency lists are used to visualize graphs without storing any connections.
Adjacency lists represent graphs by listing all vertices in a single array.
Adjacency lists store only the weights of edges, limiting traversal options.
Adjacency lists efficiently represent graphs by storing each vertex's neighbors, allowing for quick access and traversal.
What are the advantages of using a directed graph over an undirected graph?
Directed graphs are simpler to visualize and understand than undirected graphs.
Directed graphs can only represent bidirectional relationships effectively.
Directed graphs can represent one-way relationships, model flows, and enable efficient algorithms for specific tasks.
Directed graphs are always more efficient in terms of memory usage than undirected graphs.
How do you implement a graph using an adjacency matrix?
An adjacency matrix is a graph representation using linked lists.
An adjacency matrix is a list of edges for each vertex.
An adjacency matrix is a single-dimensional array of vertex connections.
An adjacency matrix is a 2D array where the element at row i and column j indicates the presence of an edge between vertex i and vertex j.
What distinguishes a complete binary tree from a regular binary tree?
A complete binary tree is always balanced in height.
A complete binary tree is fully filled at all levels except possibly the last, while a regular binary tree can have varying structures.
A complete binary tree can have any number of children per node.
A complete binary tree has nodes only on the left side.
Explain the concept of a binary search tree.
A binary search tree is a data structure that only allows duplicate values in the left child.
A binary search tree is a linear data structure where each node can have any number of children.
A binary search tree is a type of graph where nodes are connected in a circular manner.
A binary search tree is a hierarchical data structure where each node has at most two children, with the left child containing values less than the node and the right child containing values greater.
What is a heap in the context of trees?
A heap is a database management system used for storing large datasets.
A heap is a tree-based data structure that satisfies the heap property, allowing efficient access to the maximum or minimum element.
A heap is a type of graph that represents relationships between nodes.
A heap is a linear data structure that stores elements in a sorted order.
Define the term 'root' in a tree structure.
The root is any node in a tree structure.
The root is the node with the highest value in a tree structure.
The root is the topmost node in a tree structure.
The root is the last node in a tree structure.
What is the degree of a node?
The degree of a node is the total number of nodes in the graph.
The degree of a node is the number of edges connected to it.
The degree of a node is the average distance to other nodes.
The degree of a node is its value in the graph.
Differentiate between terminal nodes and non-terminal nodes.
Both terminal and non-terminal nodes are leaf nodes.
Terminal nodes are always at the top of a tree; non-terminal nodes are at the bottom.
Terminal nodes are leaf nodes with no children; non-terminal nodes are internal nodes with children.
Terminal nodes can have children; non-terminal nodes cannot.
What are siblings in a tree?
Nodes that share the same parent in a tree.
Nodes that are at the same level in a tree.
Nodes that are connected by a direct edge in a tree.
Nodes that share the same grandparent in a tree.
Define the level of a node in a tree.
The level of a node is its value in the tree.
The level of a node is the depth of the tree.
The level of a node is the number of edges from the root to that node.
The level of a node is the total number of nodes in the tree.
Explain what a path is in the context of trees.
A path is the total number of nodes in a tree.
A path is a single node in a tree.
A path is a method for balancing trees.
A path in trees is a sequence of nodes connected by edges, representing a route from one node to another.
What is the depth of a node?
The depth of a node is the total number of nodes from the root to that node.
The depth of a node is the number of edges from the root to that node.
The depth of a node is the height of the tree minus the level of that node.
The depth of a node is the number of children that node has.
Who is the parent node of a given node?
The node that is directly connected and one level higher in the hierarchy.
The node that is the lowest in the hierarchy.
The node that is not connected to any other nodes.
The node that is directly connected and one level lower in the hierarchy.
What are ancestors of a node?
The root node of the tree.
All nodes in the tree structure.
Nodes that are on the path from a node to the root in a tree structure.
Nodes that are only leaves in the tree.
What is the height of a tree?
The height of a tree is the number of edges on the longest path from the root to a leaf.
The height of a tree is the total number of nodes in the tree.
The height of a tree is the number of levels in the tree.
The height of a tree is the maximum degree of any node in the tree.
What is the purpose of a traversal in a tree?
A traversal is used to visit all the nodes in a tree in a specific order.
A traversal is used to delete nodes from a tree.
A traversal is used to create a new tree structure.
A traversal is used to find the height of a tree.
In a full binary tree if number of internal nodes is I, then number of leaves L are?
a) L = 2*I
b) L = I + 1
c) L = I – 1
d) L = 2*I – 1
. Construct a binary tree by using postorder and inorder sequences given below.
Inorder: N, M, P, O, Q
Postorder: N, P, Q, O, M
What is the difference between a binary tree and a binary search tree?
A binary tree can have any number of children per node; a binary search tree has at most two children with specific ordering.
A binary tree is always balanced; a binary search tree can be unbalanced.
A binary tree allows duplicate values; a binary search tree does not.
A binary tree is a type of graph; a binary search tree is a linear data structure.
What is a subtree?
A subtree is a tree consisting of a node and all its descendants.
A subtree is a tree that has no nodes.
A subtree is a part of a tree that contains only leaf nodes.
A subtree is a tree that is disconnected from the main tree.
What is the purpose of a binary tree traversal algorithm?
To rearrange the nodes in a binary tree.
To visit all the nodes in a binary tree in a specific order.
To find the maximum value in a binary tree.
To delete nodes from a binary tree.
Construct a binary search tree by using postorder sequence given below.
Postorder: 2, 4, 3, 7, 9, 8, 5.
For the given graph(G), which of the following statements is true?
G is a complete graph
G is not a connected graph
The vertex connectivity of the graph is 2
The edge connectivity of the graph is 1
What is the number of edges present in a complete graph having n vertices?
a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient
Which of the following properties does a simple graph not hold?
Must be connected
Must be unweighted
Must have no loops or multiple edges
Must have no multiple edges
Which of the following is true?
a) A graph may contain no edges and many vertices
b) A graph may contain many edges and no vertices
c) A graph may contain no edges and no vertices
d) A graph may contain no vertices and many edges
For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?
a) v=e
b) v = e+1
c) v + 1 = e
d) v = e-1
