Scribd
Upload
13 views

Important Topics Data Structure Notes

Ds

Uploaded by

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

Important Topics Data Structure Notes

Ds

Uploaded by

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

Important Topics for Data Structure Exams

1. Data Structures Comparison

- Linear vs Non-Linear Data Structures: Linear data structures (arrays, linked lists, stacks, queues) have

elements arranged in a sequential manner, whereas non-linear data structures (trees, graphs) have

hierarchical or network structures.

- Linear Search vs Binary Search: Linear search checks each element one by one, while binary search

halves the data set in each step but requires sorted data.

2. Stack and Queue Operations

- Postfix Expression Evaluation using Stacks: Convert infix expressions to postfix, then evaluate using a

stack. Push operands, pop and apply operators.

- Circular Queue: A queue that wraps around once it reaches the end, solving the issue of wasted space in

linear queues.

- Stack Algorithms: Well-formedness check for parentheses ensures that each opening bracket has a

matching closing bracket using a stack.

3. Graph Algorithms

- BFS (Breadth-First Search): Explores nodes level by level, using a queue to track the next node to visit.

- DFS (Depth-First Search): Explores as far as possible along each branch before backtracking, using a stack

(or recursion).

- Topological Sorting: An ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed

edge u -> v, vertex u comes before v.

4. Tree Structures

- Binary Search Tree (BST): A binary tree in which the left child contains only nodes with values less than the

parent node, and the right child only nodes with values greater than the parent.

- AVL Tree: A self-balancing BST where the difference in heights of left and right subtrees of any node is less
than or equal to 1.

- B-trees: Generalized binary trees used for storing data, often used in databases.

5. Huffman Coding

- Huffman Tree: A tree used to compress data by assigning shorter codes to more frequent characters and

longer codes to less frequent ones, based on frequency of occurrence.

- The process involves building a tree where each leaf node represents a character, and the path to the node

represents the binary code for that character.

6. Hashing Techniques

- Hashing: A process that maps data to a fixed-size value (hash). Used for efficient look-up and retrieval.

- Collision Handling: Methods like linear probing handle hash collisions by finding the next available slot in the

array.

7. Linked List Operations

- Doubly Linked List: Each node contains pointers to both the next and previous nodes. Operations include

insertion, deletion, and traversal in both directions.

- Circular Linked List: The last node points back to the first node, forming a circle. Efficient for situations

where the list needs to be traversed repeatedly.

You might also like