DS - Unit-4 Previous Questions

Syllabus

Advanced concepts in Trees: AVL Search Trees: Need for AVL Search Trees, Definition, Balancing Trees (L-L Rotation, R-R Rotation, L-R Double Rotation, R-L Double Rotation)-, AVL tree Operations: Insertion, Deletion.

Heaps – Definition, Heap Maintenance operations: insertion and deletion. Rheapup, Rheapdown algorithms and heap implementation, Applications.

SEMESTER END EXAMINATIONS – JUNE 2024

Discuss algorithms used in Heap construction with a suitable example: i) reheap up ii) reheap down

Construct an AVL tree utilizing the given dataset. Display the balance factors in the resultant tree. Data: 17, 28, 9, 13, 35, 42, 65, 50, 73 After insertion of 20 and 45, update the AVL tree.

Show construction of a heap from the following data 30, 4, 12, 9, 19, 50, 65, 60, 20, 17. Insert 75 into the Heap and reheapify.

How you balance an unbalanced AVL trees in the following cases: i. Left of Left(L-L) ii. Right of Right(R-R) iii. Right of Left(R-L) iv. Left of Right(L-R) Explain with suitable examples.

BACKLOG SUBJECT EXAMINATIONS – SEPTEMBER / OCTOBER 2023

Show the AVL tree that results after each of the integer keys 9, 27, 50, 15, 2, 21, and 36 are inserted, in that order, into an initially empty AVL tree. Clearly show the tree that results after each insertion, and make clear any rotations that must be performed.

Explain the algorithms to perform following operations with an example: i) Max heap construction ii) Max heap deletion.

Explain the Rotate Left and Double Rotation Left algorithms used for AVL tree balancing with a suitable example. Show construction of a heap from the following data read from the keyboard: 42, 23, 74, 11, 65, 58, 94. Insert 36 into the heap and reheapify

SEMESTER END EXAMINATIONS – MAY / JUNE 2023

How to overcome the drawbacks of Binary Search Tree (BST) using AVL tree? Illustrate with an example.

Show the construction of max-heap to sort the following numbers by mentioning the steps clearly: 82, 90, 10, 12, 15, 77, 55, 23 Delete 90 from the heap and heapify.

Write algorithms to RotateRight and RotateLeft in an AVL tree.

Construct AVL tree for the following data: 21,26,30,9,4,14,28,18,15,10,2,3,7

Another 13, 5, 1, 7, 8, 98, 67, 26, 33, 12, 6, 7, 8

What are the applications of Heap? Write the algorithm for Reheap UP and Reheap Down operation.

SUPPLEMENTARY SEMESTER EXAMINATIONS - NOVEMBER 2022

Discuss algorithms used in Heap construction with a suitable example: reheap up and reheap down

Create an AVL tree using the following data. Show the balance factors inthe resulting tree. 14 23 7 10 33 56 80 66 70 Insert 44 and 50 into the tree created.

Show construction of a heap from the following data read from the keyboard: 20, 35, 9, 26, 49, 78, 2 Insert 46 into the heap and reheapify

Explain the following AVL Tree balancing procedures giving suitable examples: Double Rotation Right and Double Rotation Left.

SEMESTER END EXAMINATIONS – JUNE 2022

Write the algorithm for Reheap UP and Reheap Down operation.

Define AVL tree. Construct the AVL tree mentioning the balance factor from the following data: 14, 6, 1, 7, 8, 99, 68, 26, 33, 12, 6, 7, 8.

Show construction of a heap from the following data 30, 4, 12, 9, 19, 50, 65, 60, 20, 17. Insert 75 into the Heap and reheapify.

How you balance an unbalanced AVL trees in the following cases: i. Left of Left(L-L) ii. Right of Right(R-L) iii. Right of Left(R-L) iv. Left of Right(L-R) Explain with suitable examples.

EXAMINATIONS SEPTEMBER /OCTOBER 2021

Discuss AVL tree and Write code to create AVL tree.

Construction the heap tree from the following data 32, 8, 21, 18, 39, 55, 75, 80, 40,99. Design an algorithm for the same.

Create an AVL tree using the following data .Show the balance factors in the resulting tree 24,45, 28, 12,23, 32,14,67. Insert 48 and 52 into the tree created.

Define Heap? Write Heap sort Algorithm and sort the below tree.

                    27
                  /    \
                14      35
               /  \    /  \
             10   19  31   42

SEMESTER END EXAMINATIONS – JULY / AUGUST 2021

Explain the Rotate right and Double Rotation Right algorithms used for AVL Tree balancing with a suitable example

Show construction of a heap from the following data read from the keyboard: 20, 35, 9, 26, 49, 78, 2 Insert 46 into the heap and reheapify.

Construct the AVL tree mentioning the balance factor from the following data 13, 5, 1, 7, 8, 98, 67, 26, 33, 12, 6, 7, 8.

Explain the reheap up and reheap down algorithms used in Heap construction with a suitable example.

EXAMINATIONS SEPTEMBER /OCTOBER 2020

Explain the following AVL Tree balancing procedures giving suitable examples: Double Rotation Right and Double Rotation Left.

Show construction of a heap from the following data read from the keyboard: 21, 37, 10, 26, 50, 76, 5 Insert 45 into the heap and reheapify.

Create an AVL tree using the following data. Show the balance factors in the resulting tree. 14 23 7 10 33 56 80 66 70 Insert 44 and 50 into the tree created.

Define heap. Write the algorithm for reheap up and reheap down