Data structures and Algorithms

1


Arulmigu Meenakshi Amman college of Engineering
Vadamavandal-604410.
Prepared by
V.Umapathy
Prof./Mech.
Important Questions and Answers
CS25C04- Data Structures and Algorithms
Syllabus
1. Data Types: Abstract Data Types (ADTs), ADTs and classes, introduction to OOP, Classes
in Python, Inheritance, Namespaces, Shallow and Deep Copying.
Practical: Implement simple ADTs as Python classes.
2. Linear Structures: List ADT, array-based implementations, linked list implementations,
singly linked lists, circularly linked lists, doubly linked lists, Stack ADT, Queue ADT,
double ended queues, applications .
Practical: List ADT using Python arrays, Linked list, Stack and Queue ADTs and
Applications.
3. Tree Structures: Tree ADT, Binary Tree ADT, tree traversals, binary search trees, AVL
trees, heaps, multi-way search trees .
Practical: Tree representation and traversal algorithms, Binary Search Trees, Heaps.
4. Graph Structures: Graph ADT, representations of graph, graph traversals, DAG,
topological ordering, greedy algorithms, dynamic programming, shortest paths, minimum
spanning trees, introduction to complexity classes and intractability.
Practical: Graph representation and Traversal algorithms, Single source shortest path
algorithm, Minimum spanning tree algorithms.
5. Algorithm: Analysis of algorithms, Asymptotic notations, Divide & Conquer, Recursion,
Recursive Algorithms.
Practical: Implement recursive algorithms in Python.
6. Sorting and Searching: Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort,
V.




Analysis of sorting algorithms, Linear & Binary search, Hashing, Hash functions, Collision
U
m




handling, Load factors, Rehashing, and Efficiency.
ap




Practical: Sorting and searching algorithms, Hash tables.
at




S.No Description
hy
,P




.
ro




Unit-I
f./
M
ec
h.

, 2


Data Types
Introduction
- Abstract Data Types (ADTs): define data and operations
- Classes: blueprint for objects in OOP
- Python classes, inheritance, and namespaces
- Shallow vs deep copying

Key Concepts
- ADTs: stack, queue, etc.
- OOP: encapsulation, inheritance, polymorphism
- Python: classes, objects, self
- Copying: shallow (reference) vs deep (new object)
Basic Concepts
Data Types & OOP: Basic Concepts
- ADTs: define data and operations (e.g., stack, queue)
- Classes: blueprint for objects; encapsulate data and methods
- OOP principles: inheritance, polymorphism, encapsulation
- Python classes: class, self, methods
- Inheritance: subclass inherits from superclass
- Namespaces: scope for names (variables, functions)
- Copying: shallow (references), deep (new objects)

Key Points
- ADTs focus on what, classes implement how
- Use copy() or deepcopy() in Python
Two Marks QA
1. What is an Abstract Data Type (ADT)?
- Defines data and operations

2. What is OOP?
- Object-Oriented Programming

3. What is inheritance in Python?
V.




- Subclass inherits from superclass
U
m
ap




4. What is a namespace?
at




- Scope for names (variables, functions)
hy
,P




5. Difference between shallow and deep copy?
ro




- Shallow: references, Deep: new objects
f./
M
ec
h.

, 3

6. What is self in Python classes?
- Reference to the instance

7. How to create a class in Python?
- Use class keyword
13 and 15 Marks QA
1. Explain Abstract Data Types (ADTs) with an example.




Abstract Data Types (ADTs): Explained
- ADTs define data and operations without implementation
- Focus on what, not how
- Example: Stack ADT
- Data: elements
- Operations: push, pop, isEmpty, size

Stack ADT Example- push(item): add to top
- pop(): remove top
- isEmpty(): check if empty
V.




- size(): return number of elements
U
m
ap




Implementation
at




- Can be implemented using arrays or linked lists
hy




- Details hidden from user
,P




2. How do ADTs relate to classes in OOP?
ro
f./
M
ec
h.

, 4




ADTs and Classes in OOP: Relationship
- ADTs define interface (what)
- Classes implement ADTs (how)
- Classes encapsulate data and methods
- Example: Stack ADT → Stack class in Python

Key Points
- ADTs focus on operations
- Classes provide implementation
- Encapsulation: hide data, expose methods

Python Example
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
V.




def pop(self):
U
m




return self.items.pop()
ap




3. Describe the principles of Object-Oriented Programming (OOP).
at
hy
,P
ro
f./
M
ec
h.