Home | | **Object Oriented Programming and Data Structures** | Important short questions and answers: Non-Linear Data Structures

Object Oriented Programming and Data Structure - Non-Linear Data Structures - Important short questions and answers: Non-Linear Data Structures

**1. Define non-linear data structure?**

Data structure which is capable of expressing more complex
relationship than that of physical adjacency is called non-linear data
structure.

**2. Define tree?**

A tree is a data structure, which represents hierarchical
relationship between individual Data items.

**3. Define child and parent of a tree.**

The root of each subtree is said to be a child of ‘r’ and ‘r’ is the parent of each subtree root.

**4. Define leaf?**

In a directed tree any node which has out degree o is called a
terminal node or a leaf.

**5. What is a Binary tree?**

A Binary tree is a finite set of elements that is either empty
or is partitioned into three disjoint subsets. The first subset contains a
single element called the root of the tree. The other two subsets are
themselves binary trees called the left and right sub trees.

**6. What are the applications of
binary tree?**

Binary tree is used in data processing.

a. File index schemes

b. Hierarchical database management system

**7. What is meant by traversing?**

Traversing a tree means processing it in such a way, that each
node is visited only once.

**8. What are the different types of
traversing?**

The different types of traversing are

a.Pre-order traversal-yields prefix form of expression.

b. In-order traversal-yields infix form of expression.

c. Post-order traversal-yields postfix form of expression.

**9. What are the two methods of binary
tree implementation?**

Two methods to implement a binary tree are,

a. Linear representation.

b. Linked representation

**10. Define Graph?**

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).

**11. Define adjacent nodes?**

Any two nodes which are connected by an edge in a graph are
called adjacent nodes. For Example, if and edge xÎE is associated with a pair
of nodes (u,v) where u, v Î V, then we say that the edge x connects the nodes u
and v.

**12.Name the different ways of
representing a graph?**

a. Adjacency matrix

b. Adjacency list

**13.
****What are the two traversal strategies used in traversing a
graph?**

a. Breadth first search

b. Depth first search

**14.
****What is an acyclic graph?**

A simple diagram which does not have any cycles is called an
acyclic graph.

**15. Give some example of NP complete
problems.**

Hamiltonian circuit.

Travelling salesmen problems

**16.
****What are AVL trees?**

An AVL tree is a binary search tree with a balancing condition.
For every node in the tree the heigh of the left and right subtrees can differ
at most by 1.

·
The height of an empty tree is
defined to be -1.It ensures that the depth of the tree is O(log N)**1**

**7.
****What is topological sort?**

A topological sort is an ordering of vertices in a directed
acyclic graph, such that if there is a path from vi then vj appears after vi in
the ordering.

**18. What is single source shortest
path problem?**

Given as an input a weighted graph, G=(V,E) and a distinguished
vertex, ’s’ find the shortest weighted path from ‘s’ to every other vertex in
G.

**19.
****Mention some shortest –path problems.**

·
Unweighted shortest paths

·
Dijikstra’s algorithm

·
All-pairs shortest paths

**20.
****What are the algorithms used to find the minimum spanning tree?**

§ Prim’s algorithm § Kruskal’s algorit

**21.
****Define
complete binary tree.**

It is a
complete binary tree only if all levels, except possibly the last level have
the maximum number of nodes maximum. A complete binary tree of height ‘h’ has
between 2h and

2h+1 – 1
node

**22. Define binary search tree. Why it is preferred
rather than the sorted linear array and linked list?**

Binary
search tree is a binary tree in which key values of the left sub trees are
lesser than the root value and the key values of the right sub tree are always
greater than the root value.

In linear
array or linked list the values are arranged in the form of increasing or
decreasing order. If we want to access any element means, we have to traverse
the entire list. But if we use BST, the element to be accessed is greater or
smaller than the root element means we can traverse either the right or left
sub tree and can access the element irrespective of searching the entire tree.

**23.
****Give
various implementations of trees.**

· Linear implementation

·
Linked list implementation

**24.
****List out
the application of trees.**

·
Ordered tree

·
“C” – representation of tree

**25.
****What is
the difference between binary tree and binary search tree?**

·
Binary Tree Binary Search Tree

·
A tree is said to be a binary tree if it A BST is binary
tree in which the key values in the left sub tree is lesser than the has at
most two children root and key values of the right sub tree is greater than the
root value.

·
It doesn’t have any order. It should be in order.

**26.
****Show the
maximum number of nodes in a binary tree of height H is 2H+1 – 1.**

Consider
H = 3

No. of
nodes in a full binary tree = 2H+1 – 1

= 23+1 – 1

= 24 – 1

= 15 nodes

We know
that a full binary tree with height h=3 has maximum 15 nodes.

Hence
proved.

**27. List out the cases involved in deleting a node
from a binary search tree.**

Case 1:
Node to be deleted is a Leaf node

Case 2:
Node to be deleted has one child

Case:3:
Node to be deleted has two children.

**28. A + (B-C)*D+(E*F), if the above arithmetic
expression is represented using a binary tree, Find the number of non-leaf
nodes in the tree.**

Expression
tree is a binary tree in which non – leaf nodes are operators and the leaf
nodes are operands.

In the
above example, we have 5 operators. Therefore the number of non-leaf nodes in
the tree is 5.

**29. What is a BST – binary search tree? **

Binary
search tree is a binary tree in which key values of the left sub trees are
lesser than the root value and the key values of the right sub tree are always
greater than the root value.

**30. Define threaded Binary Tree. **

A binary
tree is threaded by making all right child pointers that would normally be null
point to the inorder successor of the node, and all left child pointers that
would normally be null point to the inorder predecessor of the node.

**31 Write the advantages of threaded binary tree. **

**1. **By doing threading we avoid the
recursive method of traversing a Tree ,** **which
makes use of stack and consumes a lot of memory and time.

2. The node
can keep record of its root

**32.
****Write an
algorithm to declare nodes of a tree structure. **

Struct
tree node

{

int
element; Struct tree *left; Struct tree *right;

}

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Non-Linear Data Structures : Important short questions and answers: Non-Linear Data Structures |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.