Data Structure Interview Questions – Set 03

by

Which data structure is used to perform recursion?

Stack data structure is used in recursion due to its last in first out nature. Operating system maintains the stack in order to save the iteration variables at each function call

Write the syntax in C to create a node in the singly linked list.

struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));

Write the steps involved in the insertion and deletion of an element in the stack.

Push:

  • Increment the variable top so that it can refer to the next memory allocation
  • Copy the item to the at the array index value equal to the top
  • Repeat step 1 and 2 until stack overflows
    Pop:
  • Store the topmost element into the an another variable
  • Decrement the value of the top
  • Return the topmost element

List Some Applications of Multilinked Structures?

  • Sparse matrix,
  • Index generation.

What are the drawbacks of array implementation of Queue?

Memory Wastage: The space of the array, which is used to store queue elements, can never be reused to store the elements of that queue because the elements can only be inserted at front end and the value of front might be so high so that, all the space before that, can never be filled.
Array Size: There might be situations in which, we may need to extend the queue to insert more elements if we use an array to implement queue, It will almost be impossible to extend the array size, therefore deciding the correct array size is always a problem in array implementation of queue.

Write a recursive C function to calculate the height of a binary tree.

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));
}

What is Data Structure? Explain.

The data structure is a way that specifies how to organize and manipulate the data. It also defines the relationship between them. Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are the central part of many computer science algorithms as they enable the programmers to handle the data in an efficient way

How are the elements of a 2D array are stored in the memory?

There are two techniques by using which, the elements of a 2D array can be stored in the memory.

Row-Major Order: In row-major ordering, all the rows of the 2D array are stored into the memory contiguously. First, the 1st row of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last row.
Column-Major Order: In column-major ordering, all the columns of the 2D array are stored into the memory contiguously. first, the 1st column of the array is stored into the memory completely, then the 2nd row of the array is stored into the memory completely and so on till the last column of the array.

Write the C code to perform in-order traversal on a binary tree.

void in-order(struct treenode *tree)
{
if(tree != NULL)
{
in-order(tree→ left);
printf(“%d”,tree→ root);
in-order(tree→ right);
}
}

What is the difference between NULL and VOID?

  • Null is actually a value, whereas Void is a data type identifier.
  • A null variable simply indicates an empty value, whereas void is used to identify pointers as having no initial size.