DATA STRUCTURES
51.Construction of expression trees?
1.convert the given infix expression into postfix notation
2. Create a stack and read each character of the expression and push into the stack, if operands are encountered.
3.when an operator is encountered pop 2 values from the stack. From a tree using the operator.
52.Define lazy deletion?
When an element is to be deleted it is left in the tree itself and marked a s being deleted. This is called as lazy deletion and is an efficient procedure if duplicate keys are present in the binary search tree, because the field
that keeps count of the frequency of appearance of the element can be decremented of the element can be decremented.
53.Define AVL tree?
AVL tree also called as height balanced tree .It is a height balanced tree in which every node will have a balancing factor of –1,0,1 Balancing factor Balancing factor of a node is given by the difference between the
height of the left sub tree and the height of the right sub tree.
54.what are the various operation performed in the binary search tree ?
1.insertion
2.deletion
3.find
4.find min
5.find max
55. What are the various transformation performed in AVL tree?
1.single rotation
- single L rotation
- single R rotation
2.double rotation
-LR rotation
-RL rotation
56.General idea of hashing and what is the use of hashing function?
A hash table similar to an array of some fixes size-containing keys. The keys specified here might be either integer or strings, the size of the table is taken as table size or the keys are mapped on to some number on the hash table from a range of 0 to table size
57.what is priority queue?
A priority queue is a data structure that allows at least the following two operations: insert which does the obvious thing; and Deletemin, which finds, returns, and removes the minimum element in the priority queue. The Insert operation is the equivalent of Enqueue.
58.Applecation of priority queues?
1.for scheduling purpose in operating system
2.used for external sorting
3.important for the implementation of greedy algorithm, which operate by repeatedly finding a minimum.
59.what are the main properties of a binary heap?
1.structure property
2.heaporder property
60. Define tree traversal and mention the type of traversals?
Visiting of each and every node in the tree exactly is called as tree
traversal
Three types of tree traversal
1.inorder traversal
2.preoder traversal
3.postorder traversal.
No comments:
Post a Comment