Hey Shouters!! In this tutorial, we will discuss the most important Data Structure interview questions.
These questions are simple and easy to remember. Read the answers carefully.
25> Does the minimal spanning tree of a graph give the shortest distance between any 2 specified nodes?
No, it doesn’t. Minimal Spanning tree assures that the total weight of the tree is kept to minimum.
It doesn’t imply that the distance between any two nodes involved in the minimum-spanning tree is minimum.
24> Differentiate between selection sort and insertion sort?
In Selection Sort, take the current element and exchange it with the smallest element on the right hand side of the current element. whereas,
In Insertion Sort, take the current element and insert it at the appropriate position of the list, adjusting the list every time you insert.
The difference is in what the inner loop does:
In selection sort, the inner loop is over the unsorted elements. Each pass selects one element, and moves it to its final location.
In insertion sort, each pass of the inner loop iterates over the sorted elements. Sorted elements are displaced until the loop finds the correct place to insert the next unsorted element.
More no of swaps are needed in Selection sort. whereas, Less no of swaps are needed in Insertion sort.
23> What is Fibonacci Search?
Fibonacci search is a search algorithm that applies to a sorted array.
It uses divide-and-conquer approach that reduces the time needed to reach the targer element.
22> When is a binary search algorithm best applied ?
It is best applied to search a list when the elements are already in order or sorted.
The list here is searched starting in the middle. If that middle value is not the correct one, the lower or the upper half is searched in the similar way.
21> How do you reference all the elements in a one-dimension array?
This is done using an indexed loop. The counter runs from 0 to the array size minus one.
Using the loop counter as the array subscript helps in referencing all the elements in one-dimensional array.
20> list out the advantages of circular queue over linear queue?
Memory Space: Linear queue drains the memory space while the circular queue makes the valuable and efficient use of space.
ORDER: Linear queue follows first in first out order whereas the Circular queue doesn’t have any specific order.
Insert & delete: The insertion and deletion of the elements are fixed in linear queue i.e, addition from the rear end and deletion from the front end. On the other hand, the circular queue is capable of inserting and deleting the element from any point or any side until it is abandoned or unoccupied.
19> Is it possible to store any number of data elements in stack?
Yes, it is possible to insert different types of elements in a stack. Elements in a stack can be inserted using the “Push” operation. This operation writes an element on the stack and moving the pointer.
18> How does dynamic memory allocation help in managing data?
A Dynamic memory allocation helps to store simple structured data types.
It can combine separately allocated structure blocks to form composite structures that expand and contract as required.
17> What is a bubble sort and how do you perform it?
Bubble sort is a sorting technique which can be applied to data structures like arrays.
Here, the adjacent values are compared and their positions are exchanged if they are out of order.
The smaller value bubbles up to the top of the list, while the larger value sinks to the bottom.
16> You want to insert a new item in a binary search tree. How would you do it?
Let us assume that the you want to insert is unique.
First of all, check if the tree is empty.
If it is empty, you can insert the new item in the root node.
If it is not empty, refer to the new item’s key.
If the data to be entered is smaller than the root’s key, insert it into the root’s left subtree.
Otherwise, insert it into the root’s right sub tree.
15> Give some examples whereof the greedy algorithm, divide and conquer algorithm, dynamic programming algorithm, and backtracking algorithm are used?
Some example of the greedy algorithm is:
Kruskal’s algorithm and Prim’s algorithm for finding minimum spanning trees, and the algorithm for finding optimum Huffman trees.
Some example of divide and conquer algorithm are:
Binary search, Quick sort, Merge sort, closest pair of points, Strassen’s algorithm, etc.
Some example of dynamic programming algorithm are:
Longest common subsequence
Some example of the backtracking algorithm is:
Sudoko, eight queen problems, crossword, etc.
14> Why is the isEmpty() member method called?
The isEmpty() member method is called during the dequeue process.
It helps in ascertaining if there exists any item in the queue which needs to be removed.
This method is called by the dequeue() method before returning the front element.
13> What is Spooling?
Spooling is a process in which data is temporarily held to be used and executed by a device, program or the system. “Spool” is technically an acronym for simultaneous peripheral operations online.
“acronym” means another word.
12> What is Dequeue?
A dequeue is a double-ended-queue.
The elements here can be inserted or removed from either end.
11> What is post fix expression?
It is an expression in which each operator follows its operands.
Here, There is no need to group sub-expressions in parentheses or to consider operator precedence.
10> How to find middle element of linked list in one pass?
To find length of linked list we need to first traverse through linked list till we find last node, which is pointing to null, and then is second pass we can find middle element by traversing only half of length.
9> What is the difference between Singly Linked List and Doubly LinkedList data structure?
Main difference between Singly linked list and doubly linked list is ability to traverse.
In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you cannot traverse back on a singly linked list.
8> What is a binary search tree?
Binary search tree is binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than x.
7> Tell something about time complexity.
For seaching techniques,
For linear search, best case: O(1), Average case: O(n) and for worst case: O(n).
For binary search, best case: O(1), Average case: O(log n) and for worst case: O(log n).
For sorting techniques,
For bubble sort, best case: O(n), Average case: O(n^2) and for worst case: O(n^2).
For selection sort, best case: O(n^2), Average case: O(n^2) and for worst case: O(n^2).
For Insertion sort, best case: O(n), Average case: O(n^2) and for worst case: O(n^2).
For Merge sort, best case: O(n log n), Average case: O(n log n) and for worst case: O(n log n).
For Quick sort, best case: O(n log n), Average case: O(n log n) and for worst case: O(n^2).
6> What are the objectives of studying data structures?
- To identify and create useful mathematical entities and operations to determine what classes of problems can be solved using these entities and operations
- To determine the representation of these abstract entities and to implement the abstract operations on these concrete representations.
5> Define ADT.
An abstract datatype is a set of operations. ADTs are mathematical abstractions, nowhere, in an ADTs definition is there any mention of how the set of operations is implemented. Objects such as lists, sets and graphs along with their operations can be viewed as abstract data types.
4> What are the advantages of modularity?
It is much easier to debug small routines than large routines.
It is easier for several people to work on a modular program simultaneously.
A well written modular program places certain dependencies in only one routine, making changes easier.
3> Define LINKED LIST.
Linked list consists of a series of structures, which are not necessarily adjacent in memory. Each structure contains the element and a pointer to a structure contains its successor. We call this the Next Pointer. The last call’s Next pointer points to Null.
2> State the different ways of representing expressions.
The different ways of representing expressions are
- Infix Notation
- Prefix Notation
- Postfix Notation
1> Any two properties of Binary Tree.
Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1.
The maximum number of nodes at level ‘l’ of a binary tree is 2^l.
If you have any doubt regarding any question. Feel Free to comment below and if you to add any questions. Write your suggestion below in the comment box.