A data structure is a model for organizing and storing data. Stacks, Queue, Linked Lists, and Trees are the examples of different data structures. Data structures are classified as either linear or non-linear:
A data structure is said to be linear if only one element can be accessed from an element directly. Eg: Stacks, Lists, Queues.
A data structure is non-linear if more than one elements can be accessed from an element directly. Eg: Trees, Graphs, Heap.
2. Define ADT?
arrow_forward
An abstract data type is a set of objects together with a set of operations. Abstract data types are mathematical abstraction. Objects such as lists, sets, graphs, trees can be viewed as abstract data types.
3. What do you mean by LIFO and FIFO?
arrow_forward
LIFO stands for 'Last In First Out', it says how the data to be stored and retrieved. It means the data or element which was stored last should come out first. Stack follows LIFO.
arrow_forward
FIFO stands for 'First In First Out', here the data(or element) which was stored first should be the one to come out first. It is implemented in Queue.
4. What is Stack?
arrow_forward
A stack is a list of elements in which insertion and deletions can take place only at one end, this end is called as stack 'top'. Only top element can be accessed. A stack data structure has LIFO (Last In First Out) property. A stack is an example of linear data structure.
5. What operations can be done on Stack?
arrow_forward
The following operations can be performed on stack:
Push operation inserts new element into stack.
Pop operation deletes the top element from the stack.
Peek returns or give the top element without deleting it.
Isempty() operation returns whether stack is empty or not.
6. List some applications of stack?
arrow_forward
Some well-known applications of stack are as follow:
Infix to Postfix conversion.
Evaluatiion of postfix expression.
Check for balanced parantheses in an expression.
Stack is very important data structure being used to implement function calls efficiently.
Parsing
Simulation of recursion function.
String reverse using stack.
7. What is a Queue?
arrow_forward
A Queue is a particular data structure in which the elements in the collection are kept in order. Unlike Stack, queue is opened at both end. Queue follows 'FIFO' method where element is inserted from rear end and deleted or removed from front end.
8. What operations can be done on Queue?
arrow_forward
The following operations can be performed on queue:
Enqueue operation inserts new element in rear of the list.
Dequeue operation deletes the front element from the list.
Isempty() operation checks whether queue is empty or not.
9. Where do we use Queue?
arrow_forward
Some well-known applications of queue are as follow:
For findind level order traversal efficiently.
For implementing BFS efficiently.
For implementing Kruskal algorithm efficiently.
10. What is Binary Tree?
arrow_forward
A binary tree is a 2-ary tree in which each node(N) has atmost 2 children (either 0 or 1). The node with 2 children are called internal nodes, and the nodes with 0 children are called external nodes or leaf nodes.
11. What is Complete Binary Tree?
arrow_forward
A Binary tree is complete binary tree if all levels are completely filled except possibly the last/lowest level are full and in the last/lowest level all the items are on the left.
12. What is Perfect Balanced Binary Tree?
arrow_forward
A perfect balanced binary tree is a binary tree where each node has same number of nodes in both subtrees.
13. Define Height in a tree?
arrow_forward
Height is a general measured as number of edges from the root to deepest node in the tree.
14. What is tree traversal?
arrow_forward
Traversal is used to visit each node in the tree exactly once. A full traversal of a binary tree gives a linear ordering of the data in the tree. There are 3 different type of tree traversal:
Inorder Traversal
Preorder Traversal
Postorder Traversal
15. How does Inorder Traversal work?
Traverse the left sub tree of the root node R in inorder.
Visit the root node R.
Traverse the right sub tree of the root node R in inorder.
16. How does Preorder Traversal work?
Traverse the left sub tree of the root node R in preorder.
Traverse the right sub tree of the root node R in preorder.
Visit the root node R.
17. How does Postorder Traversal work?
Visit the root node R.
Traverse the left sub tree of the root node R in postorder.
Traverse the right sub tree of the root node R in postorder.
18. What is a Binary Search Tree?
arrow_forward
A BST(Binary Search Tree) is a binary tree in which each node satisfies search property. Each node's key value must be greater than all values in its left subtree and must be less than all values in its right subtree.
19. What is a AVL Tree?
arrow_forward
AVL tree is a self-balancing binary search tree with height-balanced condition. For every node the height of left subtree and right subtree can be differ by at most 1.
20. What is a B-tree?
arrow_forward
A B-Tree is a tree data structure that keeps data sorted and allows searches, insertions, deletions, and sequential access in logarithmic amount of time.
arrow_forward
In B-Tree, internal nodes can have a variable number of child nodes within some pre-defined range. A B-tree is kept balanced by requiring that all leaf nodes are at the same depth.
arrow_forward
A B-tree of order m is a tree which satisfies the following properties:
Every node has atmost 2m children.
Every node (except root and leaves) has atleast m children.
The root has atleast two children if it is not a leaf node.
All leaves appear in the same level, and carry information.
A non-leaf node with k children contain k-1 keys.
Leaf nodes contain atleast m-1 children and atmost 2m-1 keys.
21. What is a B+ Tree?
arrow_forward
A B+ Tree is a tree data structure which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic multilevel index, with maximum and minimum bounds on the number of keys in each segment (usually called a 'block' or 'node')
22. What is a Binary Heap Tree?
arrow_forward
A Binary Heap tree is a balanced binary tree where root node are compared with its children and placed accordingly. Heap have two properties namely, structure and order property. Structure Property
It is a complete binary tree where all the levels except possibly the last/lower level are full and in the last/lower level all the items are on the left. Due to this fact that binary heap is a complete binary it can be implemented using a simple array. Order Property
The heap order property for MinHeap is 'a parent is less than (or equal to) its children' whereas for MaxHeap 'a parent is greater than its children'.
23. What is a bubble sort?
arrow_forward
Bubble sort is a simple sorting algorithm, it works by repeatedly stepping through the list to be sorted comparing each pair of adjacent items and swapping if they are in the worng order.
arrow_forward
First pass bubbles out the largest element and places it in the last position and second pass places the second largest element in the second last position and so on. Thus in the last pass smallest element is placed in the first position.
arrow_forward
The running time is the total number of comparisons that is n(n-1)/2 which implies O(n2) time complexity.
24. What is Insertion Sort?
arrow_forward
Insertion sort is a simple comparison sorting algorithm, every iteration of insertion sort removes an element from the input data and insert it into the correct position in the already sorted list until no input element remains.
arrow_forward
The running time is the total number of comparisons that is n(n-1)/2 which implies O(n2) time complexity.
25. What is Selection Sort?
arrow_forward
Insertion sort is a simple comparison sorting algorithm, the algorithm works as follows:
Find the minimum value in the list.
Swap it with the minimum value in the first position.
Repeat the steps above for the remainder of the list (starting at the second position and advancing each time).
arrow_forward
The running time is the total number of comparisons that is n(n-1)/2 which implies O(n2) time complexity.
26. What is Merge Sort?
arrow_forward
Merge sort is an O(nlogn) comparison-based divide and conquer sorting algorithm, it works as follows:
If the list is of length 0 or 1, then it is already sorted.
Divide the unsorted list into two sub lists of about half the size.
Sort each sublist recursively by re-applying merge sort algorithm.
Merge the two sublists back into one sorted list.
arrow_forward
If the running time of merge sort for a list of length n is T(n) then the recurrence relation is T(n) = 2T(n/2) + n, thus after simplifying the recurrence relation T(n) = O(nlogn).
27. What is Heap Sort?
arrow_forward
Heap Sort is a comparison-based sorting algorithm which is much more efficient version of selection sort, it works by determining the largest (or smallest) element of the list, placing that at the end (or beginning)of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap. Once the data list has been made into a heap, the root node is gurantedd to be the largest (or smallest) element.
28. What is Quick Sort?
arrow_forward
Quick sort sorts by employing a divide and conquer strategy to divide a list into two sub-lists. The steps are:
Pick an element, called a pivot, from the list.
Reorder the list so the elements which are less than the pivot come before the pivot and the elements greater than pivot come after it. After this partitioning the pivot is in its final positon.
Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
arrow_forward
The running time complexity for worst case is O(n2) and for best and average case it is same i.e., O(nlogn).
29. What is a Graph?
arrow_forward
A graph is a pair of sets (V,E), where V is the sets of vertices and E is the set of edges connecting the pair of vertices.
30. What is a Directed and Undirected Graph?
arrow_forward
A graph is directed if each edge of graph has a direction between vertices.
arrow_forward
A graph is undirected if there are no direction between vertices.
31. What is a Connected Graph?
arrow_forward
A undirected graph is connected if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected.
32. What is a Complete Graph?
arrow_forward
A complete graph is a graph in which every vertex is connected to every other vertex. That means each vertex's degree in undirected graph is n-1.
33. What is a Acyclic Graph?
arrow_forward
An acyclic graph is a graph which does not have cycles.
34. How are graph represented?
arrow_forward
A graph can be represented in two forms 'Adjacency matrix' and 'Adjacency list'.
arrow_forward
Adjacency matrix is a two dimensional arrays where for each edge, (u,v) A[u,v] = true otherwise it will be false. The space complexity to represent a graph using this is O(|V|2).
arrow_forward
Adjacency list are used where each list stores adjacent vertices of the corresponding vertex. The space complexity to represent a graph using this is O(|V|+|E|).
35. What is a Spanning Tree?
arrow_forward
A Spanning tree is a graph which must include every vertex and if the graph contain n vertices, spanning tree must contain exactly (n-1) edges and is a subgraph of G.
36. What is a Minimum Spanning Tree?
arrow_forward
A Minimum Spanning tree is a spanning tree such that the summ of all the weights of edges in spanning tree is minimum.
37. Explain algorithm for finding Minimum Spanning Tree?
arrow_forward
There are 2 widely used algorithm for finding minimum spanning tree:
Prim's Algorithm
Kruskal Algorithm
arrow_forward
Prims Algorithm computes the minimum spanning tree by including appropriate vertex and thus one edge into existing partially constructed tree in successive stages. The time complexity of the Prim’s Algorithm is O((V+E)logV).
arrow_forward
Kruskal Algorithm computes the minimum spanning tree by adding edges one by one into a growing spanning tree.
arrow_forward
Initially from the graph G, consider a forest of all the vertices without any edge.
Sort all the edges in ascending order to their costs.
Include the edge with minimum cost into the forest if it does not form a cycle in the partially condtructed tree.
Repeat step (2) until no edge can be added to the tree.
Arrange the character frequency in ascending order.
Create a new node where the left child is the lowest in the sorted list and the right child is the second lowest in the sorted list.
Chop of that two elements in the sorted list as they ate now part of one node and add the probabilities. The result is the probability of the new node.
Perform insertion sort on the list with the new node.
Repeat step 3, 4 and 5 until you have just one node left.
Huffman Coding Algorithm:
Given an alphabetical 'A' with frequency distribution { f(a): a ∈ A }, the binary Huffman tree is constructed using priority 'Q', of nodes with frequencies as keys.
Huffman(A)
{
n = |A|;
Q = A;
for i = 1 to n-1
{
z = new_node;
left[z] = Extract_min(Q);
right[z] = Ectract_min(Q);
f[z] = f[left[z]] + f[right[z]];
Insert(Q, Z);
}
return Extract_min(Q);
}
There is two variance of Huffman Coding: 1) Fixed Length Coding
2) Variable Length Coding
In Fixed Length Coding method, a fixed number of bits will be achieved for each character.
In Variable Length Coding method, the most frequently used character will have less number of bits while the least use character will be represented by more number of bits.
