[go: up one dir, main page]
Scribd
Upload
3 views2 pages

DSA Questions UnitWise

The document covers key concepts in data structures, specifically focusing on AVL Trees, Depth-First Search (DFS), and Radix Sort. It explains AVL Trees as self-balancing binary search trees and includes examples of tree rotations, as well as programs for insertion in AVL Trees and DFS traversal. Additionally, it describes Radix Sort as a non-comparative sorting algorithm with examples and implementation details.

Uploaded by

iswarnav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views2 pages

DSA Questions UnitWise

The document covers key concepts in data structures, specifically focusing on AVL Trees, Depth-First Search (DFS), and Radix Sort. It explains AVL Trees as self-balancing binary search trees and includes examples of tree rotations, as well as programs for insertion in AVL Trees and DFS traversal. Additionally, it describes Radix Sort as a non-comparative sorting algorithm with examples and implementation details.

Uploaded by

iswarnav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Data Structures and Algorithms -

Questions & Answers


Unit III: Tree ADT

5-Mark Question:
1. Explain AVL Trees and their rotations with an example.

Answer:
An AVL Tree is a self-balancing binary search tree. The difference between the heights of the
left and right subtrees (called the balance factor) of any node is at most 1.
Rotations are used to balance the tree when it becomes unbalanced:
Left Rotation (LL), Right Rotation (RR), Left-Right Rotation (LR), and Right-Left Rotation
(RL).

Example: Insert 10, 20, 30 into a tree and perform rotations.


1. Insert 10:
10
2. Insert 20:
10
\
20
3. Insert 30: Unbalanced. Perform Left Rotation:
20
/ \
10 30

10-Mark Question:
2. Write a program to perform Insertion in an AVL Tree.

Answer:
Insert function for AVL Tree, balancing after insertion with right and left rotations and
inorder traversal program.

Unit IV: Graph

10-Mark Question:
1. Write a program to perform Depth-First Search (DFS).
Answer:
DFS performs graph traversal with a stack or recursion. It explores all adjacent unvisited
nodes from each node.
Example: The traversal for the graph with vertices 0, 1, 2, 3, 4.

DFS Traversal: 0 1 3 2 4

Unit V: Searching and Sorting

5-Mark Question:
1. Explain the Radix Sort algorithm with an example.

Answer:
Radix Sort is a non-comparative sorting algorithm that processes the digits of numbers
starting from the least significant digit (LSD) to the most significant digit (MSD).
Example: Sorting [170, 45, 75, 90, 802, 24, 2, 66] by LSD.
Sorted Array: [2, 24, 45, 66, 75, 90, 170, 802]

10-Mark Question:
2. Write a program to implement Radix Sort.

Answer:
Radix Sort uses Counting Sort as a subroutine to sort digits. It sorts the array based on each
digit place from LSD to MSD.

Radix Sort example implementation and sorted result for the array: [170, 45, 75, 90, 802,
24, 2, 66].
Sorted Array: [2, 24, 45, 66, 75, 90, 170, 802]

You might also like