Font size
WorksheetsTrees and Graphs
Total questions: 85
Worksheet time: 1hrs 4mins
What is the preorder traversal of the given binary tree?
A B D E H I J K L C F G
A B D H I E J K C F L G
H D I B J E K A L F C G
H I D J K E B L F G C A
What is the postorder traversal of the given binary tree?
H D I B J E K A L F C G
H I D J K E B L F A C G
H I D J K E B L F G C A
A B C D H I E J K F L G
What is LR Rotation?
Inserted node is in the left subtree of left subtree of node A
Inserted node is in the right subtree of right subtree of node A
Inserted node is in the right subtree of left subtree of node A
Inserted node is in the left subtree of the right subtree of node A
What is an AVL tree?
a tree which is balanced and is a height balanced tree
a tree which is unbalanced and is a height balanced tree
a tree with three children
a tree with atmost 3 children
Why do we need AVL tree?
To save memory
To avoid formation of skewed trees
To simplify storing
To attain faster memory access
Which of the following is TRUE?
The cost of searching an AVL tree is θ(log n) but that of a binary search tree can be O(n)
The cost of searching an AVL tree is θ(log n) but that of a complete binary tree is θ(n log n)
The cost of searching a binary search tree is O(log n ) but that of an AVL tree is θ(n)
The cost of searching an AVL tree is θ(n log n) but that of a binary search tree is O(n)
Which rotation is required in the given AVL tree?
LL Rotation
RR Rotation
LR Rotation
RL Rotation
What is the balance factor of any node in AVL tree?
Height of right subtree - Height of left subtree
Height of left subtree - Height of right subtree
Level number of right subtree - Level number of left subtree
Level number of left subtree - Level number of right subtree
There are two types of data structures, they are
Static and dynamic
Fast and slow
Large and small
Ascending and descending
Weighted graph
a graph that has a data value labelled on each edge.
The underlying mathematical principles behind the use of graphs.
An object in a graph. Also know as a node (vertices is the plural).
A join (relationship) between two nodes - sometimes called an edge.
A graph where the relationship between vertices is two way.
Undirected Graph
Directed Graph
Adjacency List
Adjacency Matrix
a data structure that stores a list of nodes with their adjacent nodes.
Undirected Graph
Directed Graph
Adjacency List
Adjacency Matrix
a data structure set up as a two dimensional array or grid that shows where there is an edge between each pair of nodes.
Undirected Graph
Directed Graph
Adjacency List
Adjacency Matrix
Tree
data structure similar to a graph, with no loops.
an object in a graph also known as a vertex
a join of relationship between nodes - also know as an arc
the starting node in a rooted tree structure from which all other nodes branch off./
In a dynamic data structure where is the memory allocated from to hold the data structure?
Heap
Cache
Secondary Storage
ROM
Virtual Memory
In terms of data structures, what does mutable mean?
A mutable structure is one which can only have data added to it
A mutable structure is one which is fixed in size
A mutable structure is one which allows data to be added, edited, deleted or moved
What does the term immutable mean?
unable to be changed
unable to speak
can be modified
can be increased in size
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
The degree of any vertex of graph is .... ?
The number of edges incident with vertex
Number of vertex in a graph
Number of vertices adjacent to that vertex
Number of edges in a graph
Which of the above graphs is/are NOT planar?
G1
G2
G3
G4
What will be the number of edges in a complete bipartite graph Km,n
m+n
m.n
Data Insufficient
A graph is a collection of
Row and columns
Vertices and edges
Equations
Childrens and parents
Determine whether the graph is a bipartite.
Yes, the graph is a bipartite.
No, the graph is not a bipartite.
Find a length of a shortest path between a -- g
7
10
5
4
9
Is the graph is planar or not?
Planar
Not planar
Which of the following graphs is not a regular graph?
Isolated Graph
Cycle
Complete Graph
Wheel
Which type of graph has all the vertex of the first set connected to all the vertex of the second set?
Regular Graph
Wheel
Bipartite Graph
Complete Bipartite Graph
The degree of any vertex of graph is .... ?
The number of edges incident with vertex
Number of vertex in a graph
Number of vertices adjacent to that vertex
Number of edges in a graph
Which of the following is a correct representation of a complete bipartite graph?
K2,2
K4
K5
C3
Vertex
a line connecting two vertices
a point
an edge
an edge that starts and ends at the same vertex
A loop is when
there is a path going from a vertex back to itself
An edge that starts and ends at the same vertex
if it were removed, the graph would be disconnected
connects two vertices to each other
A path is
an edge that starts and ends at the same vertex
a connection between two vertices
a series of consecutive edges in which no edge is repeated
a complete graph
A graph is connected if
Each vertex can reach any other vertex
each vertex is adjacent to every other vertex
All the vertices are odd
the length of all the edges are equal
Which of the following statements is NOT true?
The points in a graph are called vertices.
There are only three types of graphs in discrete mathematics.
The lines between points in a graph are called edges.
A graph is a collection of points and lines between those points.
What is the difference between a directed and an undirected graph?
A directed graph uses arrows to indicate one-way relationships, but an undirected graph does not.
A directed graph can contain weights on the edges, but an undirected graph cannot.
A directed graph can contain multiple edges and loops, but an undirected graph cannot.
There is no difference between directed and undirected graphs.
Which type of traversal of binary search tree outputs the value in sorted order?
Pre-order
Post-order
In-Order
None
Which of the following sequences denotes the post order traversal sequence of the tree?
f e g c d b a
g c b d a f e
g c d b f e a
f e d g c b a
In a tree data structure, any nodes that have no children (where the tree ends) are called ___
boundary nodes
leaf nodes
orphan nodes
terminal nodes
Which data structure is used for data that links arbitrarily, and includes things like loops?
binary trees
circular trees
graphs
dynamic linked stacks
What is the value of the ROOT node in this Tree?
35
24
42
20
Root
data structure similar to a graph, with no loops.
an object in a graph also known as a vertex
a join of relationship between nodes - also know as an arc
the starting node in a rooted tree structure from which all other nodes branch off./
Tree
data structure similar to a graph, with no loops.
an object in a graph also known as a vertex
a join of relationship between nodes - also know as an arc
the starting node in a rooted tree structure from which all other nodes branch off./
How many leaf are there in the tree?
1
3
4
7
What are the 3 depth traversals for a tree data structure?
Pre-, In- and Post-order
Pro-, In- and Past-order
Pre-, Out- and Post-order
Pre-, In- and New-order
Select the correct tree traversal method for the following description:
Root - Left Subtree - Right Subtree
Pre-Order
In-Order
Post-Order
Select the correct tree traversal method for the following description:
Left Subtree - Root - Right Subtree
Pre-Order
In-Order
Post-Order
Select the correct tree traversal method for the following description:
Left Subtree - Right Subtree - Root
Pre-Order
In-Order
Post-Order
Is the graph is planar or not?
Planar
Not planar
List item used in graph
node, junction, branch
root, leaf, flower
child, parent, siblings
edge, vertices, degree
