300+ [LATEST] Data Structures Interview Questions and Answers

Posted on by engineerComments Off on 300+ [LATEST] Data Structures Interview Questions and Answers

Q1. Define Biconnectivity?

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.

Q2. What Is Sequential Search?

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.

Q3. What Is A Spanning Tree?

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.

Q4. What Is The Need For Path Compression?

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.

Q5. List Some Of The Static Data Structures In C?

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

Q6. Why It Is Said That Searching A Node In A Binary Search Tree Is Efficient Than That Of A Simple Binary Tree?

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.

Q7. List The Applications Of Queues?

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

Q8. What Actions Are Performed When A Function Returns?

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

Q9. What Is The Difference Between Null And Void Pointer?

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;

Q10. What Is A Node Class?

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.

Q11. What Is Significance Of ” * ” ?

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.

Q12. Define A Binary Search Tree?

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.

Q13. Convert The Expression ((a + B) * C – (d – E) ^ (f + G)) To Equivalent Prefix And Postfix Notations?

Prefix Notation:

^ – * +ABC – DE + FG

postfix Notation:

AB + C * DE – – FG + ^

Q14. Define Linear Data Structures?

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

Eg; Linked lists.

Q15. How Can I Search For Data In A Linked List?

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.

Q16. Whether Linked List Is Linear Or Non-linear Data Structure?

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

Q17. Which File Contains The Definition Of Member Functions?

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

Q18. Define Double Linked List?

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.

 

Q19. What Is Precision?

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

Q20. What Are The Tasks Performed While Traversing A Binary Tree?

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

Q21. How Is Any Data Structure Application Is Classified Among Files?

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.

Q22. What Is The Type Of The Algorithm Used In Solving The 8 Queens Problem?

Backtracking.

Q23. What Do You Mean By Level Of The Tree?

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.

Q24. What Are The Categories Of Avl Rotations?

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.

Q25. State The Demerits Of Linked Representation Of Binary Trees?

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

Q26. Define Parent Node?

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.

Q27. How Many Parts Are There In A Declaration Statement?

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

Q28. What Is The Data Structures Used To Perform Recursion?

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.

Q29. What Do You Mean By Linear Probing?

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.

Q30. State The Advantages Of Using Infix Notations?

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

Q31. What Are The Properties Of Binary Heap?

  • Structure Property.
  • Heap Order Property.

Q32. State The Difference Between Queues And Linked Lists?

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.

Q33. What Is A Queue ?

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.

Q34. Define Splay Tree?

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.

Q35. What Does Isempty() Member Method Determines?

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

Q36. Define Internal Nodes?

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

Q37. Define Degree Of The Node?

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

Q38. What Do You Mean By Breadth First Search (bfs)?

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

Q39. What Is The Use Of Threaded Binary Tree?

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.

Q40. List Out The Advantages Of Using A Linked List?

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

Q41. How Do You Assign An Address To An Element Of A Pointer Array ?

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];

Q42. What Do You Mean By Shortest Path?

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

Q43. Define Depth And Height Of A Node?

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.

Q44. What Are The Advantages Of Linked List Over Array (static Data Structure)?

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.

 

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

Q46. What Do You Mean By Tree Edge?

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

Q47. Mention The Advantages Of Representing Stacks Using Linked Lists Than Arrays?

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

Q48. Define Terminal Nodes In A Tree?

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

Q49. Define Dynamic Data Structures?

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.

Q50. State The Demerit Of Linear Representation Of Binary Trees?

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