Friday, 17 November 2017

What are the limitations of arrays in data structure?
1. Arrays are of fixed size.
2. Data elements are stored in continuous memory locations which may not be available always.
3. Adding and removing of elements is problematic because of shifting the locations.

How can you overcome the limitations of arrays in data structure?
Limitations of arrays can be solved by using the linked list.

What is a linked list in data structure?
Linked list is a data structure which store same kind of data elements but not in continuous memory locations and size is not fixed. The linked lists are related logically.

What is the difference between an array and a linked list in data structure?
Ans :The size of an array is fixed whereas size of linked list is variable. In array the data elements are stored in continuous memory locations but in linked list it is non continuous memory locations. Addition, removal of data is easy in linked list whereas in arrays it is complicated.

What is a node in linked list?
The data element of a linked list is called a node.

What does node consist in linked list?
Node consists of two fields: data field to store the element and link field to store the address of the next node.

Write the syntax of node creation in linked list?
Syntax:
struct node
{
data type ;
struct node *ptr; 
};

Write the syntax for pointing to next node in linked list?
Syntax:
node->link = node1;


Thanks 
Mukesh Rajput

Thursday, 16 November 2017

Non-Linear Data Structure

What do you mean by binary search tree. Why it is preferred over sorted linear array and linked list?

Binary search tree is a binary tree in which key values of the left sub trees are lesser than the root value and the key values of the right sub tree are always greater than the root value. In linear array or linked list the values are arranged in the form of increasing or decreasing order. If we want to access any element means, we have to traverse the entire list. But if we use binary search tree, the element to be accessed is greater or smaller than the root element means we can traverse either the right or left sub tree and can access the element irrespective of searching the entire tree.

What do you mean by a complete binary tree?
A binary tree is known as a complete binary tree only if all of its levels, except possibly the last level have the maximum number of nodes. 

What do you mean by an AVL trees?
An AVL tree is a binary search tree with a balancing condition to balance the height of left sub-tree and height of right sub-tree. For every node in the tree the height of the left and right sub-trees can differ at most by 1.The height of an empty tree is defined to be -1.It ensures that the depth of the tree is O(log N)


Thanks 
Mukesh Rajput
Non-Linear Data Structure

What do you mean by a Graph in non-linear data structure?
A graph G which consist of a nonempty set V which is a set of nodes and 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).

What do you mean by adjacent nodes in non-linear data structure?
Any two nodes which are connected by an edge in a graph are called adjacent nodes. For Example, if an edge (x) is connected with a pair of nodes (u,v) then we say that the edge x connects the nodes u and v.

Name the different ways of representing a graph in non-linear data structure?
1. Adjacency matrix represention
2. Adjacency list represention

What are the two traversal methods used in traversing a graph in non-linear data structure?
1. Breadth first search
2. Depth first search

What do you mean by an acyclic graph in non-linear data structure?
A simple diagram which does not have any cycles is called an acyclic graph in non-linear data structure.

What do you mean by topological sort?
A topological sort is an ordering of vertices in a directed acyclic graph,such that if there is a path from vi then vj appears after vi in the ordering.

What do you mean by single source shortest path problem in non-linear data structure?
If input a weighted graph, G=(V,E) and a distinguished vertex,'s' find the shortest weighted path from 's' to every other vertex in G.


Thanks
Mukesh Rajput
Non-Linear Data Structure

What do you mean by non-linear data structure?
Data structure which is capable of expressing more complex relationship than that of physical adjacency is known as non-linear.

What do you mean by a tree in data structure?
A tree is a non-linear data structure, which represents hierarchical relationship between individual data elementss.

What do you mean by a child and parent of a tree in non-linear data structure?
The root (R) of each subtree is said to be a child of R and R is the parent of each subtree root.

What do you mean by a leaf node in tree data structure?
In a tree any node which has out degree zero(0) is known as leaf node.

What do you mean by a binary tree in data structure?
A Binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree. The other two subsets are called the left and right sub trees.

What are the different applications of binary tree in data structure?
a. Hierarchical database management system
b. File index schemes 

What do you mean by traversing in non-linear data structure like trees? 
Traversing a tree means processing it in such a way, that each node is visited only once.

What are the different types of traversing in non-linear data structure like trees? 
a. Pre-order traversal
b. In-order traversal
c. Post-order traversal

What are the different methods of binary tree implementation?
a. Linear implementation.
b. Linked implementation.


Thanks
Mukesh Rajput

Friday, 10 November 2017

Hashing in Data Structure

Hash function is a mathematical formula which when applied to a key, produces an integer which can be used as an index for the key in the hash table. Hash table is a data structure in which keys are mapped to array positions by a hash function. The main aim of the hash function is that elements should be relatively, randomly and uniformaily distributed. It produces aunique set of integers within some suitable range in order to reduce the number of collisions. In practice, there is no hash function that eliminates collisions completely. So a good hash function only minimize the number of collisions by spreading the elements uniformaily throughtout the array.

Different hash functions:
1. Division Method
2. Multiplication Method
3. Mid-Square Method
4. Folding Method

Different Collision resolution methods:
1. Open Addressing
   1.1 Linear Probing
   1.2 Quadratic Probing
   1.3 Double Hashing
2. Chaining 
   2.1 Chained Hash Table
   2.2 Bucket Hashing


Thanks
Mukesh Rajput