Sale notes online your Nr 1 Resource,for passing Exam at VCU

EXCEL ENGINEERING COLLEGE
(Autonomous)
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
II Semester
20CS202- Programming and Data Structures
Regulations 2021
Question Bank with Answer Key
UNIT – 4 (NON-LINEAR DATA STRUCTURES)
PART- A
Q. No Questions Marks
Define tree and root node.
 A tree is a non-linear and a hierarchical data structure consisting of a collection of
nodes such that each node of the tree stores a value and a list of references to other
1 2
nodes (the “children”)
 The topmost node of a tree or the node which does not have any parent node is called
the root node.
Compare binary tree and binary search tree.
Sl.No Binary Tree Binary Search Tree
1. It is a tree with only two children It is also a tree with only two children
2 2
2. It has no restrictions regarding its In this, the left child is lesser than the
children parent and the right child is greater than
the parent
Write the Routine of creating tree using linked list.
struct tree
{
3 int data; 2
struct tree *leftchild;
struct tree *rightchild;
};
List any four terminologies of trees.
 Root
4  Node 2
 Leaf node
 Siblings
Recall the types of tree traversal techniques
 Inorder traversal
5 2
 Preorder traversal
 postorder traversal
List out the applications of tree.
 Manipulate hierarchical data.
 Make information easy to search
6 2
 Manipulate sorted lists of data.
 As a workflow for compositing digital images for visual effects.
 Router algorithms
Define the following terms
(a) Internal nodes In a tree data structure, the node which has atleast one child is called
7 as internal node. Internal nodes are also called as 'Non-Terminal' nodes. 2
(b) Edge. In a tree data structure, the connecting link between any two nodes is called as edge.
In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of edges.
8 Write the Routine of Inorder Traversal. 2
Recursive Routine for Inorder Traversal
void Inorder (Tree T)
{
if (T!=NULL)

, {
Inorder (T->left);
printf(“%d”,T->data);
Inorder (T->right);
}
}
Compare Cycle and Acyclic Graph.

Cyclic Graph Acyclic Graph
9 A path from a node to itself is called cycle. A directed graph which has no cycles is 2
Thus, a cycle is a path in which the initial referred to as acyclic graph. It is abbreviated
and final vertices are same. as DAG [Directed Acyclic Graph]

Define Graph with example
 A graph G consist of a nonempty set V which is a set of nodes of the graph, a set E
which is the set of edges of the graph, and a mapping from the set for edge E to a set of
pairs of elements of V. It can also be represented as G=(V, E).
 Vertices are referred to as nodes and the arc between the nodes are referred to as Edges.

10 2




Write the Inorder, Preorder and Postorder traversals in the given tree




11 2


 Inorder : D H B E A F C I G J
 Preorder: A B D H E C F G I J
 Postorder: H D E B F I J G C A

List out the types of Graph
12  Direct Graph 2
 Un Direct Graph
Recall indegree, out degree and total degree.
 Total number of entering vertices is known as indegree.
13 2
 Total number of leaving vertices is known as outdegree.
 The summation of indegree and outdegree is known as total degree.
How to find whether the graph is weakly connected or not ?
 Strongly Connected Graph If there is a path from every vertex to every other vertex in a 2
14
directed graph then it is said to be strongly connected graph.
 Otherwise, it is said to be weakly connected graph.
State the merits of linear representation of binary trees.
 Storage method is easy and can be easily implemented in arrays
 When the location of a parent/child node is known, other one can be determined
15 2
easily
 It requires static memory allocation so it is easily implemented in all
programming language
16 What is meant by path in graph? 2

,  A path is a sequence of distinct vertices, each adjacent to the next.
 The length of such a path is number of edges on that path.
Contrast between full binary tree and complete binary tree.

Full Binary Tree Complete Binary Tree
17 A full binary tree is a tree in which all the A complete binary tree is a tree in which 2
leaves are on the same level and every non- every non-leaf node has exactly two
leaf node has exactly two children children not necessarily to be on the same
level.
List the two important key points of depth first search.
 If path exists from one node to another node, walk across the edge – exploring the
18 edge. 2
 If path does not exist from one specific node to any other node, return to the previous
node where we have been before – backtracking.
Write the Routine of preorder Traversal.
Recursive Routine for Preorder Traversal
void Preorder (Tree T)
{
if (T ! = NULL) 2
19
{
printf(“%d”,T->data);
Preorder (T ->left);
Preorder (T ->right);
}
Name the various representations Of Disjoint Set ADT.
20  Array Representation 2
 Linked List Representation

PART- B

Q.No Questions Marks
1 Explain the three methods of tree traversal with suitable example
 Traversal is a process to visit all the nodes of a tree and may print their values too.
Because, all nodes are connected via edges (links) we always start from the root (head)
node.
 That is, we cannot randomly access a node in a tree. There are three ways which we
use to traverse a tree –
o In-order Traversal
o Pre-order Traversal
o Post-order Traversal
16
 Generally, we traverse a tree to search or locate a given item or key in the tree or to
print all the values it contains.

In-order Traversal:
 In this traversal method, the left subtree is visited first, then the root and later the right
sub-tree.
 We should always remember that every node may represent a subtree itself.
 If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.