The document explains key concepts in data structures and algorithms, including the differences between data types and structures, advantages and disadvantages of linked lists, and properties of binary trees and AVL trees. It also covers expressions in different notations, limitations of queues and stacks, and algorithms like Dijkstra's and Kruskal's for finding shortest paths and minimum spanning trees. Additionally, it discusses the balance factor in AVL trees and the maximum number of edges in a graph.
The document explains key concepts in data structures and algorithms, including the differences between data types and structures, advantages and disadvantages of linked lists, and properties of binary trees and AVL trees. It also covers expressions in different notations, limitations of queues and stacks, and algorithms like Dijkstra's and Kruskal's for finding shortest paths and minimum spanning trees. Additionally, it discusses the balance factor in AVL trees and the maximum number of edges in a graph.
The document explains key concepts in data structures and algorithms, including the differences between data types and structures, advantages and disadvantages of linked lists, and properties of binary trees and AVL trees. It also covers expressions in different notations, limitations of queues and stacks, and algorithms like Dijkstra's and Kruskal's for finding shortest paths and minimum spanning trees. Additionally, it discusses the balance factor in AVL trees and the maximum number of edges in a graph.
The document explains key concepts in data structures and algorithms, including the differences between data types and structures, advantages and disadvantages of linked lists, and properties of binary trees and AVL trees. It also covers expressions in different notations, limitations of queues and stacks, and algorithms like Dijkstra's and Kruskal's for finding shortest paths and minimum spanning trees. Additionally, it discusses the balance factor in AVL trees and the maximum number of edges in a graph.
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 7
1. Differentiate between data type and data structures.
A data type serves as a categorization of data,
defining the specific type of value that can be stored in a variable or expression. On the other hand, a data structure is a method of organizing and storing data in computer memory, ensuring efficient access and manipulation of the stored information. 2. What are the advantages and disadvantages of linked list?
Advantages Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list. No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-allocate the memory. Disadvantages Memory usage: More memory is required in the linked list as compared to an array. Because in a linked list, a pointer is also required to store the address of the next element and it requires extra memory for itself. Traversal: In a Linked list traversal is more time- consuming as compared to an array. Direct access to an element is not possible in a linked list as in an array by index. For example, for accessing a node at position n, one has to traverse all the nodes before it.
3. Convert the infix (a+b)*(c+d)/f into postfix & prefix expression
Postfix: ab+cd+*f/ Prefix*+ab+cd/f 4. What are the limitations of linear queue? How they can be rectified?
In a linear queue, the traversal through the queue is
possible only once,i.e.,once an element is deleted, we cannot insert another element in its position. This disadvantage of a linear queue is overcome by a circular queue, thus saving memory. first-out (FIFO) principle. 5. State the properties of a Binary Tree.
Each node has a maximum of up to two children. The
value of all the nodes in the left sub-tree is less than the value of the root. The value of all the nodes in the right subtree is greater than or equal to the value of the root. 6. If the depth of the binary tree is k, the maximum number of nodes in the binary tree is 2k-1, Justify.
The maximum number of nodes in a binary tree of
depth k is 2k−1, k≥1. Here the depth of the tree is 1. So according to the formula, it will be 21−1=1. 7. Define a path in a graph.
In a graph, a path is a sequence of nodes in which
each node is connected by an edge to the next. The path length corresponds to the number of edges in the path. 8. What is the use of Dijksra’s algorithm? Dijkstra's algorithm is used to find the shortest path between the two mentioned vertices of a graph by applying the Greedy Algorithm as the basis of principle. For Example: Used to find the shortest between the destination to visit from your current location on a Google map. 9. How does the AVL tree differ from binary search tree?
Difference between Binary Search Tree
and AVL Tree Binary Search Tree AVL Tree
In Binary Search Tree, every node In AVL Tree, every node follows does not follow the balance factor. the balance factor i.e. 0, 1, -1.
Every Binary Search tree is not an Every AVL tree is a Binary
AVL tree. Search tree.
Simple to implement. Complex to implement.
The height or depth of the tree is The height or depth of the tree is O(n). O(logn)
10 List out the properties of AVL Tree.
.
1. Balance Factor:
Each node in an AVL tree maintains a balance
factor, which is the difference in height between its left and right subtrees.
Mathematically, the balance factor of a node N is
defined as balanceFactor(N) = height(N.left) -
height(N.right).
2. Balanced Condition:
In an AVL tree, the balance factor of every node
must be in the range [-1, 1].
This means that for every node in the tree, the
heights of its left and right subtrees can differ by at most one level.
1. What do you mean by Abstract Data Types?
Abstract data types, commonly abbreviated ADTs,
are a way of classifying data structures based on how they are used and the behaviors they provide. They do not specify how the data structure must be implemented or laid out in memory, but simply provide a minimal expected interface and set of behaviors. 2. Illustrate the difference between a queue and linked list with an example.
Queue Queue is a collection of one or more elements arranged Static Queue is always fixed size. in memory in a contiguous fashion. In Queue, only one and single type of information is stored because static Queue implementation is through Array. Static Queue is index based.
Singly Linked List
A linked list is a collection of one or more elements arranged in memory in a dis-contiguous fashion. List size is never fixed. List also stored the address for the next node along with it’s content.
3. Why infix expression should be converted to Prefix / Postfix?
Infix expressions are easily readable and solvable by
humans whereas the computer cannot differentiate the operators and parenthesis easily so, it is better to convert the expression to postfix(or prefix) form before evaluation. 4. What are the limitations in the stack, when array used as home of stack? Fixed Size: Arrays have a fixed size, which means the maximum number of elements in the stack must be known beforehand. If the stack size exceeds this limit, it can lead to overflow errors. 5. Create an expression tree for the expression. a+(b*c)+((d-e*f)/g). 6. What is the algorithm to delete the root’s key from the heap?
1. The key in the root is the maximum key. Save its value to return. 2. Identify the node to be deleted, unfilling bottom level right-to-left. 3. Move the key in the node to be deleted to the root, and delete the node.
7. Prove that the maximum number of edges that a graph with n Vertices is n*(n- 1)/2.
The maximum number of edges in a graph with n vertices
is n*(n-1)/2. To prove that the maximum number of edges in a graph with n vertices is n*(n-1)/2, we can use the concept of a complete graph. A complete graph is a graph in which every pair of distinct vertices is connected by a unique edge. In a complete graph with n vertices, each vertex is connected to every other vertex, resulting in a total of n*(n- 1)/2 edges.
8. What is the use of Kruskal’s algorithm?
Kruskal's Algorithm is a classic algorithm used in graph theory to find the Minimum Spanning Tree (MST) of a connected, undirected graph. The MST is a subset of the edges that connects all the vertices without any cycles and with the minimum possible total edge weight. 9. What are the various rotations in AVL tree? To maintain balance, an AVL tree uses four types of rotations: left rotation, right rotation, left-right rotation, and right-left rotation. 10 How do we calculate the balance factor for each node in an AVL tree? . It is calculated by subtracting the height of the right subtree from the height of the left subtree of any given node. Therefore, for every node in the tree, the balance factor can only be -1 , 0 , or 1 . A balance factor of 0 signifies a perfectly balanced node, with both left and right subtrees having equal heights.
