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;

}