CD3291 Data Structures and Algorithms Previous Year Question Papers - Anna University

UNIT I: Abstract Data Types & Algorithm Analysis

Part A (2 Marks)

• What is an Abstract Data Type (ADT)?
• Differentiate between Shallow and Deep copying in Python.
• Define Recursion and state its importance.
• List the three types of Asymptotic Notations.

Part B (13/16 Marks)

• Asymptotic Notations: Explain Big-Oh, Omega, and Theta notations with suitable examples.
• Object-Oriented Programming: Discuss the concepts of Inheritance (Single, Multiple, Hybrid) with Python example programs.
• Algorithm Analysis: Explain the Divide and Conquer technique and solve the Towers of Hanoi problem using recursion.

UNIT II: Linear Structures

Part A (2 Marks)

• What are the advantages of Linked Lists over Arrays?
• Define DEQUE (Double Ended Queue).
• List any four applications of a Stack.

Part B (13/16 Marks)

• Linked Lists: Detailed explanation and implementation of Singly, Doubly, and Circular Linked Lists.
• Stack & Queue ADT: Write the array-based and linked list-based implementations for Stack and Queue operations.
• Applications: Discuss the role of stacks in expression evaluation (Infix to Postfix conversion) and polynomial manipulation.

UNIT III: Sorting and Searching

Part A (2 Marks)

• Differentiate between Internal and External sorting.
• What is Hashing and why is it used?
• Compare the time complexities of Linear and Binary search.

Part B (13/16 Marks)

• Sorting Algorithms: Detailed study and Python implementation of Quick Sort, Merge Sort, and Insertion Sort.
• Hashing Techniques: Explain various hash functions and collision handling techniques (Linear Probing, Quadratic Probing, and Separate Chaining).
• Rehashing: When and why do we perform rehashing? Illustrate with an example.

UNIT IV: Tree Structures

Part A (2 Marks)

• Define a Binary Search Tree (BST).
• What is the Balance Factor in an AVL tree?
• Construct an Expression Tree for the expression A+(B-C)*D.

Part B (13/16 Marks)

• Tree Traversals: Explain In-order, Pre-order, and Post-order traversal techniques with examples.
• AVL Trees: Explain AVL rotations (LL, RR, LR, RL) with suitable examples to maintain balance during insertion.
• Binary Search Tree: Write the procedures for insertion and deletion of nodes in a BST.
• Heaps: Explain the insert and delete operations of a Min/Max Heap and the Heap Sort algorithm.

UNIT V: Graph Structures

Part A (2 Marks)

• Define Topological Sort.
• What is the difference between BFS and DFS?
• Define Minimum Spanning Tree (MST).

Part B (13/16 Marks)

• Graph Traversals: Detailed explanation of Breadth-First Search (BFS) and Depth-First Search (DFS).
• Shortest Path: State and explain Dijkstra's algorithm with a numerical example.
• Minimum Spanning Tree: Compare Prim's and Kruskal's algorithms for finding the MST of a graph.

Most Repeated / High-Weight Questions

Asymptotic analysis and complexity calculations, linked list operations and applications, sorting algorithms with implementations, tree traversals and AVL rotations, graph traversals and shortest path algorithms.