Data structures using C++

1



Arulmigu Meenakshi Amman college of Engineering
Vadamavandal-604410.
Prepared by,
V.Umapathy,
Prof./Mech.
Imortant Questions and Answers
CS25C05 - Data Structures using C++
Syllabus
1. Data Abstraction & Overloading: Overview of C++, Structures, Class Scope and
Accessing Class Members, Reference Variables, Initialization, Constructors, Destructors,
Member Functions and Classes, Friend Function, Dynamic Memory Allocation, Static Class
Members, Container Classes and Integrators, Proxy Classes, Overloading: Function
overloading and Operator Overloading.
Practical:
1. Program to Implement Constructors and Destructors.
2. Program to implement Member Functions, Classes and Friend Functions.
3. Program to Implement Dynamic Memory Allocation and Overloading.

2. Inheritance & Polymorphism: Base Classes and Derived Classes, Protected Members,
Casting Class pointers and Member Functions, Overriding, Public, Protected and Private
Inheritance–Constructors and Destructors in derived Classes, Implicit Derived, Class Object
to Base, Class Object Conversion, Composition Vs. Inheritance, Virtual functions, This
Pointer, Abstract Base Classes and Concrete Classes, Virtual Destructors, Dynamic Binding.
Practical:
1. Program to Implement various inheritances.
2. Program to Implement virtual functions and dynamic binding.
3. Implementation of method overriding and operator overloading.

3. Linear Data Structures: Asymptotic Notations: Big-Oh, Omega and Theta, Best, Worst and
Average case Analysis: Definition and an example, Arrays and its representations, Stacks
and Queues, Linked lists, Linked list based implementation of Stacks and Queues,
Evaluation of Expressions, Linked list based polynomial addition.
Practical:

, 2


1. Program to implement various operations on arrays and linked lists.
2. Program to implement various operations on stacks and queues using array and linked
list.
3. Program to evaluate the infix expressions by converting into prefix and postfix
expressions

4. Non-Linear Data Structures: Trees, Binary Trees, Binary tree representation and
traversals, Threaded binary trees, Binary tree representation of trees, Application of trees:
Set representation and Union, Find operations, Graph and its representations, Graph
Traversals, Connected components. Standard template library.
Practical:
1. Program to Implement Binary Tree Traversal and Graph Traversal Algorithm.
2. Program to Implement the Single Source Shortest Path Algorithm and All Pair Shortest
Path Algorithm.
3. Program to find the Minimal Spanning Tree for a Graph.

5. Searching, Sorting and Complexity Analysis: Insertion sort, Merge sort, Quicksort,
Heapsort, Linear Search, Binary Search.
Practical:
1. Program to Implement Linear Search and Binary Search Algorithms.
2. Program to Implement Insertion Sort, Merge Sort, Quick Sort and Heap Sort Algorithms.

S.No Description
.
Unit-I
Data Abstraction & Overloading
Introduction
Data Abstraction
- Hiding implementation details, showing only essential info
- Achieved using classes, access specifiers (public, private, protected)

Overview of C++
- Object-Oriented Programming (OOP) language
- Combines data and functions

Structures
- Similar to classes, but default access is public

struct Student {

, 3


int rollNo;
char name[20];
};


Class Scope and Accessing Members
- Class scope: Where class members are defined
- Access members using: dot (.) or arrow (->) operators

class Student {
public:
void display() {}
};

Student s;
s.display();


Reference Variables
- Alias for existing variable

int x = 10;
int& ref = x; // ref is alias for x


Initialization
- Assigning initial value to variables

int x = 10; // initialization


*_Constructors & Destructors_- Constructors: Initialize objects
- Destructors: Release resources

class Student {
public:
Student() {} // constructor
~Student() {} // destructor
};

, 4




Member Functions & Classes
- Functions inside classes
- Can access class members

class Student {
public:
void display() {}
};


Friend Function
- Non-member function with access to private members

class Student {
friend void display(Student s);
};


Dynamic Memory Allocation
- Allocate memory at runtime
- new, delete operators

int* ptr = new int;
// ...
delete ptr;


Static Class Members
- Shared by all objects

class Student {
public:
static int count;
};
int Student::count = 0;


Overloading
1. Function Overloading