Top 50 Data Structures Interview Questions You Must Prepare 19.May.2024

A connected graph G is said to be biconnected, if it remains connected after removal of any one vertex and the edges that are incident upon that vertex. A connected graph is biconnected, if it has no articulation points.

In sequential search each item in the array is compared with the item being searched until a match occurs. It is applicable to a table organized either as an array or as a linked list.

A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.

Path compression is performed during a Find operation. Suppose if we want to perform Find(X), then the effect of path compression is that every node on the path from X to the root has its parent changed to the root.

Some of the static data structures in C are arrays, pointers, structures etc.

In binary search tree, the nodes are arranged in such a way that the left node is having less data value than root node value and the right nodes are having larger value than that of root. Because of this while searching any node the value of the target node will be compared with the parent node and accordingly either left sub branch or right sub branch will be searched. So, one has to compare only particular branches. Thus searching becomes efficient.

  • Jobs submitted to printer
  • Real life line
  • Calls to large companies
  • Access to limited resources in Universities
  • Accessing files from file server

i) Return address is retrieved.
ii) Function’s data area is freed.
iii) Branch is taken to the return address.

NULL can be value for pointer type variables.
VOID is a type identifier which has not size.
NULL and void are not same. Example: void* ptr = NULL;

A node class is a class that, relies on the base class for services and implementation, provides a wider interface to users than its base class, relies primarily on virtual functions in its public interface depends on all its direct and indirect base class can be understood only in the context of the base class can be used as base for further derivation can be used to create objects. A node class is a class that has added new services or functionality beyond the services inherited from its base class.

The symbol “*” tells the computer that you are declaring a pointer. Actually it depends on context.

In a statement like int *ptr; the ‘*’ tells that you are declaring a pointer.
In a statement like int i = *ptr; it tells that you want to assign value pointed to by ptr to variable i.

The symbol “*” is also called as Indirection Operator/ Dereferencing Operator.

A binary search tree is a special binary tree, which is either empty or it should satisfy the following characteristics:

  • Every node has a value and no two nodes should have the same value i.e) the values in the binary search tree are distinct.
  • The values in any left sub-tree is less than the value of its parent node.
  • The values in any right sub-tree is greater than the value of its parent node.
  • The left and right sub-trees of each node are again binary search trees.

Prefix Notation:

^ – * +ABC – DE + FG

postfix Notation:

AB + C * DE – – FG + ^

Linear data structures are data structures having a linear relationship between its adjacent elements.

Eg; Linked lists.

Unfortunately, the only way to search a linked list is with a linear search, because the only way a linked list's members can be accessed is sequentially. Sometimes it is quicker to take the data from a linked list and store it in a different data structure so that searches can be more efficient.

  • According to Access strategies Linked list is a linear one.
  • According to Storage Linked List is a Non-linear one.

Definitions of member functions for the Linked List class are contained in the LinkedList.cpp file.

It is a collection of data elements called nodes, where each node is divided into three parts

i) An info field that contains the information stored in the node.
ii) Left field that contain pointer to node on left side.
iii) Right field that contain pointer to node on right side.

 

Precision refers the accuracy of the decimal portion of a value. Precision is the number of digits allowed after the decimal point.

  • Visiting a node.
  • Traverse the left sub-tree.
  • Traverse the right sub-tree.

A linked list application can be organized into a header file, source file and main application file. The first file is the header file that contains the definition of the NODE structure and the LinkedList class definition. The second file is a source code file containing the implementation of member functions of the LinkedList class. The last file is the application file that contains code that creates and uses the LinkedList class.

The root node is always considered at level zero, then its adjacent children are supposed to be at level 1 and so on.

Here, node A is at level 0, nodes B and C are at level 1 and nodes D and E are at level 2.

Let A be the nearest ancestor of the newly inserted nod which has the balancing factor ±@Then the rotations can be classified into the following four categories:

Left-Left: The newly inserted node is in the left subtree of the left child of A.
Right-Right: The newly inserted node is in the right subtree of the right child of A.
Left-Right: The newly inserted node is in the right subtree of the left child of A.
Right-Left: The newly inserted node is in the left subtree of the right child of A.

  • Given a node structure, it is difficult to determine its parent node.
  • Memory spaces are wasted for storing null pointers for the nodes, which have one or no sub-trees.
  • It requires dynamic memory allocation, which is not possible in some programming language.

The node which is having further sub-branches is called the parent node of those sub-branches.

Here C is the parent node of D and E.

There are two main parts, variable identifier and data type and the third type is optional which is type qualifier like signed/unsigned.

Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.

Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.

Linear probing is an open addressing collision resolution strategy in which F is a linear function of i, F(i)=i. This amounts to trying sequentially in search of an empty cell. If the table is big enough, a free cell can always be found, but the time to do so can get quite large.

  • It is the mathematical way of representing the expression.
  • It is easier to see visually which operation is done from first to last.

  • Structure Property.
  • Heap Order Property.

The difference between queues and linked lists is that insertions and deletions may occur anywhere in the linked list, but in queues insertions can be made only in the rear end and deletions can be made only in the front end.

A Queue is a sequential organization of data. A queue is a first in first out type of data structure. An element is inserted at the last position and an element is always taken out from the first position.

A splay tree is a binary search tree in which restructuring is done using a scheme called splay. The splay is a heuristic method which moves a given vertex v to the root of the splay tree using a sequence of rotations.

isEmpty() checks if the stack has at least one element. This method is called by Pop() before retrieving and returning the top element.

The nodes other than the root and the leaves are called internal nodes.

The total number of sub-trees attached to that node is called the degree of the node.

BFS performs simultaneous explorations starting from a common point and spreading out independently.

In threaded binary tree, the NULL pointers are replaced by some addresses. The left pointer of the node points to its predecessor and the right pointer of the node points to its successor.

  • It is not necessary to specify the number of elements in a linked list during its declaration.
  • Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list.
  • Insertions and deletions at any place in a list can be handled easily and efficiently.
  • A linked list does not waste any memory space.

We can assign a memory address to an element of a pointer array by using the address operator, which is the ampersand (&), in an assignment statement such as ptemployee[0] = &projects[2];

A path having minimum weight between two vertices is known as shortest path, in which weight is always a positive number.

For any node ni, the depth of ni is the length of the unique path from the root to ni. The height of ni is the length of the longest path from ni to a leaf.

The disadvantages of array are:

i) unlike linked list it is expensive to insert and delete elements in the array.
ii) One can’t double or triple the size of array as it occupies block of memory space.

In linked list

i) each element in list contains a field, called a link or pointer which contains the address of the next element.
ii) Successive element’s need not occupy adjacent space in memory.

 

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

If w is undiscovered at the time vw is explored, then vw is called a tree edge and v becomes the parent of w.

  • It is not necessary to specify the number of elements to be stored in a stack during its declaration, since memory is allocated dynamically at run time when an element is added to the stack.
  • Insertions and deletions can be handled easily and efficiently.
  • Linked list representation of stacks can grow and shrink in size without wasting memory space, depending upon the insertion and deletion that occurs in the list.
  • Multiple stacks can be represented efficiently using a chain for each stack.

A node that has no children is called a terminal node. It is also referred to as leaf node.

A data structure formed when the number of data items are not known in advance is known as dynamic data structure or variable size data structure.

Insertions and deletions in a node take an excessive amount of processing time due to data movement up and down the array.