Data Structure Interview Questions
A list of most frequently asked Data Structure interview questions and answers are given below.
1) 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
2) Describe the types of Data Structures?
Data Structures are mainly classified into two types:
Linear Data Structure: A data structure is called linear if all of its elements are arranged in the sequential order. In linear data structures, the elements are stored in a non-hierarchical way where each item has the successors and predecessors except the first and last element.
Non-Linear Data Structure: The Non-linear data structure does not form a sequence i.e. each item or element is connected with two or more other items in a non-linear arrangement. The data elements are not arranged in the sequential structure.
3) List the area of applications of Data Structure.
Data structures are applied extensively in the following areas of computer science:
4) What is the difference between file structure and storage structure?
Difference between file structure and storage structure:
The main difference between file structure and storage structure is based on memory area that is being accessed.
Storage structure: It is the representation of the data structure in the computer memory.
File structure: It is the representation of the storage structure in the auxiliary memory.
5) List the data structures which are used in RDBMS, Network Data Modal, and Hierarchical Data Model.
6) 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
7) What is a Stack?
Stack is an ordered list in which, insertion and deletion can be performed only at one end that is called the top. It is a recursive data structure having pointer to its top element. The stack is sometimes called as Last-In-First-Out (LIFO) list i.e. the element which is inserted first in the stack will be deleted last from the stack.
8) List the area of applications where stack data structure can be used?
9) What are the operations that can be performed on a stack?
10) Write the stack overflow condition.
Overflow occurs when top = Maxsize -1
11) What is the difference between PUSH and POP?
PUSH and POP operations specify how data is stored and retrieved in a stack.
PUSH: PUSH specifies that data is being "inserted" into the stack.
POP: POP specifies data retrieval. It means that data is being deleted from the stack.
12) Write the steps involved in the insertion and deletion of an element in the stack.
13) What is a postfix expression?
An expression in which operators follow the operands is known as postfix expression. The main benefit of this form is that there is no need to group sub-expressions in parentheses or to consider operator precedence.
The expression "a + b" will be represented as "ab+" in postfix notation.
14)Write the postfix form of the expression: (A + B) * (C - D)
)15) Which notations are used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
Polish and Reverse Polish notations.
16)What is an array?
Arrays are defined as the collection of similar types of data items stored at contiguous memory locations. It is the simplest data structure in which each data element can be randomly accessed by using its index number.
17) How to reference all the elements in a one-dimension array?
It can be done by using an indexed loop such that the counter runs from 0 to the array size minus one. In this manner, you can reference all the elements in sequence by using the loop counter as the array subscript.
18) What is a multidimensional array?
The multidimensional array can be defined as the array of arrays in which, the data is stored in tabular form consists of rows and columns. 2D arrays are created to implement a relational database lookalike data structure. It provides ease of holding the bulk of data at once which can be passed to any number of functions wherever required.
19) 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.
20) Calculate the address of a random element present in a 2D array, given base address as BA.
Row-Major Order: If array is declared as a[m][n] where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in row major order is calculated as,
Address(a[i][j]) = B. A. + (i * n + j) * size
Column-Major Order: If array is declared as a[m][n] where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in column major order is calculated as
Address(a[i][j]) = ((j*m)+i)*Size + BA.
21) Define Linked List Data structure.
Linked List is the collection of randomly stored data objects called nodes. In Linked List, each node is linked to its adjacent node through a pointer. A node contains two fields, i.e. Data Field and Link Field.
22) Are linked lists considered linear or non-linear data structures?
A linked list is considered both linear and non-linear data structure depending upon the situation.
23) What are the advantages of Linked List over an array?
24) Write the syntax in C to create a node in the singly linked list.
25) If you are using C language to implement the heterogeneous linked list, what pointer type should be used?
The heterogeneous linked list contains different data types, so it is not possible to use ordinary pointers for this. For this purpose, you have to use a generic pointer type like void pointer because the void pointer is capable of storing a pointer to any type.
26) What is doubly linked list?
The doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. In a doubly linked list, a node consists of three parts:
27) Write the C program to insert a node in circular singly list at the beginning.
28) Define the queue data structure.
A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.
29) List some applications of queue data structure.
The Applications of the queue is given as follows:
30) What are the drawbacks of array implementation of Queue?
31) What are the scenarios in which an element can be inserted into the circular queue?
32) What is a dequeue?
Dequeue (also known as double-ended queue) can be defined as an ordered set of elements in which the insertion and deletion can be performed at both the ends, i.e. front and rear.
33) What is the minimum number of queues that can be used to implement a priority queue?
Two queues are needed. One queue is used to store the data elements, and another is used for storing priorities.
34) Define the tree data structure.
The Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root. The nodes other than the root node are partitioned into the nonempty sets where each one of them is to be called sub-tree.
35) List the types of tree.
There are six types of tree given as follows.
36) What are Binary trees?
A binary Tree is a special type of generic tree in which, each node can have at most two children. Binary tree is generally partitioned into three disjoint subsets, i.e. the root of the node, left sub-tree and Right binary sub-tree.
37) Write the C code to perform in-order traversal on a binary tree.
38) What is the maximum number of nodes in a binary tree of height k?
2k+1-1 where k >= 1
39) Which data structure suits the most in the tree construction?
Queue data structure
40) Which data structure suits the most in the tree construction?
Queue data structure
41) Write the recursive C function to count the number of nodes present in a binary tree.
42) Write a recursive C function to calculate the height of a binary tree.
43) How can AVL Tree be useful in all the operations as compared to Binary search tree?
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.
44) State the properties of B Tree.
A B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties.
45) What are the differences between B tree and B+ tree?
46) List some applications of Tree-data structure?
Applications of Tree- data structure:
47) Define the graph data structure?
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.
48) Differentiate among cycle, path, and circuit?
49) Mention the data structures which are used in graph implementation.
For the graph implementation, following data structures are used.
50) Which data structures are used in BFS and DFS algorithm?
51) What are the applications of Graph data structure?
The graph has the following applications:
54) In what scenario, Binary Search can be used?
Binary Search algorithm is used to search an already sorted list. The algorithm follows divide and conqer approach
52) What are the advantages of Binary search over linear search?
There are relatively less number of comparisons in binary search than that in linear search. In average case, linear search takes O(n) time to search a list of n elements while Binary search takes O(log n) time to search a list of n elements.
53) What are the advantages of Selecetion Sort?
55) List Some Applications of Multilinked Structures?
56) What is the difference between NULL and VOID?