Data structure Interview Questions and Answers
Question - 51 : - Write the C code to perform in-order traversal on a binary tree.
Answer - 51 : -
void in-order(struct treenode *tree)
{
if(tree != NULL)
{
in-order(tree→ left);
printf("%d",tree→ root);
in-order(tree→ right);
}
}
Question - 52 : - What is the maximum number of nodes in a binary tree of height k?
Answer - 52 : -
2k+1-1 where k >= 1
Question - 53 : - Which data structure suits the most in the tree construction?
Answer - 53 : -
Queue data structure
Question - 54 : - Write the recursive C function to count the number of nodes present in a binary tree.
Answer - 54 : -
int count (struct node* t)
{
if(t)
{
int l, r;
l = count(t->left);
r=count(t->right);
return (1+l+r);
}
else
{
return 0;
}
}
Question - 55 : - Write a recursive C function to calculate the height of a binary tree.
Answer - 55 : -
int countHeight(struct node* t)
{
int l,r;
if(!t)
return 0;
if((!(t->left)) && (!(t->right)))
return 0;
l=countHeight(t->left);
r=countHeight(t->right);
return (1+((l>r)?l:r));
}
Question - 56 : - How can AVL Tree be useful in all the operations as compared to Binary search tree?
Answer - 56 : -
AVL tree controls the height of the binary search tree by not letting it be skewed. The time taken for all operations in a binary search tree of height h is O(h). However, it can be extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this height to log n, AVL tree imposes an upper bound on each operation to be O(log n) where n is the number of nodes.
Question - 57 : - State the properties of B Tree.
Answer - 57 : -
A B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties.
Every node in a B-Tree contains at most m children.
Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
The root nodes must have at least 2 nodes.
All leaf nodes must be at the same level.
Question - 58 : - List some applications of Tree-data structure?
Answer - 58 : -
Applications of Tree- data structure:
- The manipulation of Arithmetic expression,
- Symbol Table construction,
- Syntax analysis
- Hierarchal data model
Question - 59 : - Define the graph data structure?
Answer - 59 : -
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent-child relations.
Question - 60 : - Differentiate among cycle, path, and circuit?
Answer - 60 : -
- Path: A Path is the sequence of adjacent vertices connected by the edges with no restrictions.
- Cycle: A Cycle can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex in the path can not be visited twice
- Circuit: A Circuit can be defined as the closed path where the intial vertex is identical to the end vertex. Any vertex may be repeated.