# freshers data structure interview questions

What is shell sort?

Shell sort can be said a variant of insertion sort. Shell sort divides the list into smaller sublist based on some gap variable and then each sub-list is sorted using insertion sort. In best cases, it can perform up to Ο(n log n).

How depth-first traversal works?

Depth First Search algorithm(DFS) traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.

What is a binary search tree?

A binary search tree is a binary tree with a special provision where a node’s left child must have value less than its parent’s value and node’s right child must have the value greater than it’s parent value.

How many stacks are required to implement a Queue?

Two, Have two stacks S1 and S2.

For Enqueue, perform push on S1. For Dequeue, if S2 is empty pop all the elements from S1 and push it to S2. The last element you popped from S1 is an element to be dequeued. If S2 is not empty, then pop the top element in it.

What is a node?

The data element of a linked list is called a node.

What is the Brute Force algorithm?

The algorithm used to search the contents by comparing each element of an array is called Brute Force algorithm.

A stack can be described as a pointer explain this?

Because stack will contain a head pointer which will always point to the top of the Stack. All Stack Operations are done using a head pointer. Hence stack can be described as a pointer

What do you mean by Syntax Error, Logical Error, Run time Error?

- Syntax Error: Syntax Error is due to lack of knowledge in a specific language. It is due to somebody does not know how to use the features of a language. We can know the errors at the time of compilation.
- Logical Error: It is due to the poor understanding of the requirement or problem.
- Run time Error: The exceptions like divide a number by 0, overflow and underflow comes under this.

What are the methods available in storing sequential files?

Straight merging, Natural merging, Polyphase sort, Distribution of Initial runs.

What is the AVL tree?

AVL tree is a self binary tree in which balancing factor lies between the -1 to 1. It is also known as a self-balancing tree.

## data structure freshers interview questions

What is a binary tree?

A binary tree is a tree which has maximum no. of children either 0 or 1 or 2. i.e., there is at the most 2 branches in every node.

What is an ordered list?

An ordered list is a list in which each node’s position in the list is determined by the value of its key component, so that the key values form an increasing sequence, as the list is traversed.

A linear search refers to the way a target key is being searched in a sequential data structure. In this method, each element in the list is checked and compared against the target key. The process is repeated until found or if the end of the file has been reached.

How does variable declaration affect memory allocation?

The amount of memory to be allocated or reserved would depend on the data type of the variable being declared. For example, if a variable is declared to be of integer type, then 32 bits of memory storage will be reserved for that variable.

What is the advantage of the heap over a stack?

The heap is more flexible than the stack. That’s because memory space for the heap can be dynamically allocated and de-allocated as needed. However, the memory of the heap can at times be slower when compared to that stack.

# data structure interview questions with answers

What is the difference between a stack and a Queue?

**Stack**: Represents the collection of elements in last in first out order. Operations include testing null stack, finding the top element in the stack, removal of topmost element and adding elements on the top of the stack.**Queue**: Represents the collection of elements in first in first out order. Operations include testing a null queue, finding the next element, removal of elements and inserting the elements from the queue. Insertion of elements is at the end of the queue. Deletion of elements is from the beginning of the queue

What do you mean by overflow and underflow?

When new data is to be inserted into the data structure but there is no available space i.e.free storage list is empty this situation is called overflow. When we want to delete data from a data structure that is empty this situation is called underflow.

What are the applications of a binary tree?

A binary tree is used in data processing.

What is a string?

A sequential array of characters is called a string.

Translate infix expression into its equivalent postfix expression: (A-B)*(D/E)

(A-B)*(D/E) = [AB-]*[DE/] = AB-DE/*

What is the 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.

What are the types of Collision Resolution Techniques and the methods used in each of the types?

- Open addressing (closed hashing)
- The methods used include: Overflow block
- Closed addressing (open hashing),
- The methods used include: Linked list, Binary tree

How can you overcome the limitations of arrays?

Limitations of arrays can be solved by using the linked list.

What are multidimensional arrays?

Multidimensional arrays make use of multiple indexes to store data. It is useful when storing data that cannot be represented using single dimensional indexing, such as data representation in a board game, tables with data stored in more than one column.

Are linked lists considered linear or non-linear data structures?

It depends on where you intend to apply linked lists. If you based it on storage, a linked list is considered non-linear. On the other hand, if you based it on access strategies, then a linked list is considered linear.

How does dynamic memory allocation help in managing data?

Apart from being able to store simple structured data types, dynamic memory allocation can combine separately allocated structured blocks to form composite structures that expand and contract as needed.

What is merge sort?

Merge sort, is a divide-and-conquer approach for sorting the data. In a sequence of data, adjacent ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged again to form an even bigger sorted list, which continues until you have one single sorted list.

What is the primary advantage of a linked list?

A linked list is an ideal data structure because it can be modified easily. This means that editing a linked list works regardless of how many elements are in the list.

How do you insert a new item in a binary search tree?

Assuming that the data to be inserted is a unique value (that is, not an existing entry in the tree), check first if the tree is empty. If it’s empty, just insert the new item in the root node. If it’s not empty, refer to the new item’s key. If it’s smaller than the root’s key, insert it into the root’s left subtree, otherwise, insert it into the root’s right subtree.

How does a selection sort work for an array?

The selection sort is a fairly intuitive sorting algorithm, though not necessarily efficient. In this process, the smallest element is first located and switched with the element at subscript zero, thereby placing the smallest element in the first position.

The smallest element remaining in the subarray is then located next to subscripts 1 through n-1 and switched with the element at subscript 1, thereby placing the second smallest element in the second position. The steps are repeated in the same manner until the last element.

How do sign and unsigned numbers affect memory?

In the case of signed numbers, the first bit is used to indicate whether positive or negative, which leaves you with one bit short. With unsigned numbers, you have all bits available for that number. The effect is best seen in the number range (an unsigned 8-bit number has a range 0-255, while the 8-bit signed number has a range -128 to +127.

What is the minimum number of nodes that a binary tree can have?

A binary tree can have a minimum of zero nodes, which occurs when the nodes have NULL values. Furthermore, a binary tree can also have 1 or 2 nodes.

What are dynamic data structures?

Dynamic data structures are structures that expand and contract as a program runs. It provides a flexible means of manipulating data because it can adjust according to the size of the data.

In what data structures are pointers applied?

Pointers that are used in the linked list have various applications in the data structure. Data structures that make use of this concept include the Stack, Queue, Linked List and Binary Tree.

What are ARRAYs?

When dealing with arrays, data is stored and retrieved using an index that refers to the element number in the data sequence. This means that data can be accessed in any order. In programming, an array is declared as a variable having a number of indexed elements.

Which sorting algorithm is considered the fastest?

There are many types of sorting algorithms: quick sort, bubble sort, balloon sort, radix sort, merge sort, etc. Not one can be considered the fastest because each algorithm is designed for a particular data structure and data set. It would depend on the data set that you would want to sort.